Validating keys and verifying signatures is very slow
Validating a public key takes around 1.7 seconds on the Galaxy Nexus. Verifying a pseudonymous message takes around 2.9 seconds, versus 1 ms for an anonymous message.
We can cache validated public keys, but we'll need to find some other way to improve the performance of signature verification.