I don't agree with requiring POW in the public key. But it could be added as a one-time challenge when a client connects to a relay. Or on each message (but too much overhead).