<i>Alice sends a message to Bob, her device asks the messaging service for Bob&#x27;s account&#x27;s identify and public keys.</i><p>This is a classic trusted third party problem. We need to trust the service that the public key provided (and stored in the blockchain) actually belongs to Bob.<p>This boils down to Zooko&#x27;s triangle: if the service allows to associate the account with a new key, there is no way to prove the new key actually belongs to Bob. If there is no such way, Alice will have to somehow figure out the undecipherable new ID of Bob.<p>The only benefit I can see of backing the keys in a blockchain is that your own client can monitor the blockchain for new keys associated with your account, ringing alarm bells in such a case.