This post on the Cryptography stack exchange shows how to almost uniquely recover the public key from the signature, hash of the signed data, and knowledge of the curve: https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work. I believe it basically produces two public keys for which the signature given will validate for the hash.
Given a public key
Q, a signature
S, and the hash of some data
H, it seems that there are two ways that we can verify that this triple is valid.
- We can run the usual ECDSA verification routine, which is somewhat time intensive.
- We can run public key recovery with (
H, Curve) and verify that one of the 2 possible returned public keys (4, really, since each can be either compressed/decompressed) is the point
Q. I am not sure if this is more/less time intensive.
- Is verification through public key recovery more or less time intensive than the usual ECDSA verification?
- If less, then couldn't bitcoin do all it's ECDSA verification through public key recovery and save time? Granted, checking a pubkey-hash would involve taking each candidate public key, OP_HASH160 hashing it and seeing if it comes out to the right 20 bytes of the address. And if none of the 4 possibilities hash to the correct value, then the signature verification failed.
My only reason for asking this is that ECDSA verification is slow, and I read somewhere that public key recovery is very fast, so just wanted to see if anyone has any insight into this.