Is normal ECDSA verification slower than a verification method based on Public Key Recovery?

Question

Background info:

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.

Main Question:

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 (S, 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.

So,

1. Is verification through public key recovery more or less time intensive than the usual ECDSA verification?
2. 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.

Answer 1

Verification w/ Public key recovery is never going to be faster than normal verification however it is only marginally slower. I benchmarked it a while back and PubKey recovery added about 5% overhead.

Changing the txn format would require a hard fork so it is unlikely that is going to happen but the advantage of pubkey recovery is that it trades storage for time. This could be useful for Bitcoin as processor power is less of a bottleneck than WAN bandwidth especially in residential 'last mile' scenarios.

A typical 2in, 2out P2PkH transaction is 373 bytes with compressed keys and 437 bytes using uncompressed keys). The same transaction without pubkeys would be 309 bytes resulting in a storage (bandwidth and memory) reduction of 17% to 29% in exchange for 5% increase in CPU time.

Hashing is extremely fast so performing 4 hashes vs 1 hash is negligible but a single byte can remove that overhead. The protocol would require using a flag with the signature to indicate which form to use when recovering the PubKey.

0x02 = compressed even
0x03 = compressed odd
0x04 = uncompressed even
0x05 = uncompressed odd

This really only saves significant space in P2PkH transactions. For P2SH (i.e. multisig) the script is very likely to contain full pubkeys instead of keyhashes.

While using PubKey recovery initially would have made sense the cost in terms of needing a hardfork doesn't make that change very viable. If putting a hardfork on the table there are a lot of more interesting things that could be done instead. For example switching from ECDSA to Schnorr signatures would allow native thresholding signatures. This would reduce the number of signatures from one (or more in the case of multisig) per input to just one per transaction. As 64 bytes each that would really add up.