ECDSA Signatures allow recovery of the public key

[Pieter Wuille]

Hello all,

I recently read in the sec pdf file (see http://www.secg.org/download/aid-780/sec1-v2.pdf, pages 47-48, section 4.1.6) that it is possible to recover the public key used in an ECDSA signature. After an IRC conversation, this was implemented and tested by roconnor, and it seems to be possible indeed.

Currently, bitcoin txin's for spend-to-address transactions use a DER-encoded signature + DER-encoded public key, resulting in 139-byte scripts. Assuming we drop the DER-encoding (except for a version byte), we could reduce this to 65 bytes.

[ByteCoin]

... it is possible to recover the public key used in an ECDSA signature.
...
... resulting in 139-byte scripts.
... we could reduce this to 65 bytes.

Great catch! Your solution would be a very elegant way of signing a transaction and implicitly revealing the public key.

ByteCoin

[Gavin Andresen]

What's the extra CPU cost for recovering the public key?  Current bottleneck for bitcoin transaction processing is the CPU cost of ECDSA signature verification, not disk space or bandwidth, so saving bytes at the expense of more CPU is not the right thing to do.

[Stefan Thomas]

Cool stuff!

Are there any patents covering the extraction of the pubkey from the signature? I'm reminded of ECDSA point compression which would make the public keys half size, but I believe the reason Bitcoin doesn't use it is that it's covered by patents. (As well as being additional load on the CPU.)

The CPU cost seems to be mostly in step 1.6.1.: two ECPoint scalar multiplications. I believe the step is executed 1-4 times (outer loop j from 0 to 1, inner loop k from 1 to 2) depending on which candidate key matches. The verification step 1.6.2. in our case would be a SHA256+RIPEMD160 to compare it to the pubkey hash? So if I'm right, pubkey recovery would be 1-4 times as expensive as a signature verification (which is also mostly two ECPoint scalar multiplications.)

(Disclaimer: I have no idea what I'm talking about, somebody with some actual skill please confirm. )

[ByteCoin]

What's the extra CPU cost for recovering the public key?  Current bottleneck for bitcoin transaction processing is the CPU cost of ECDSA signature verification, not disk space or bandwidth, so saving bytes at the expense of more CPU is not the right thing to do.

There is some extra CPU cost certainly. If the goal is to reduce the CPU cost of transaction processing then there are other low-hanging fruit to pick beforehand.

• Change the software so that not all clients have to check all signatures. This was raised in http://bitcointalk.org/index.php?topic=6373.msg94314#msg94314 in the context of speeding transaction propagation.
• Use a smaller curve - 256 bits is very conservative
• Use a different group with faster operations like curve25519
• Remove the incentive for generating lots of transactions

Not recording the public key in the scriptSig would be a breaking change and so there are many other improvements we could apply at the same time.

ByteCoin

[xf2_org]

ArtForz notes some possibly low-hanging fruit: we verify the same TX multiple times.

[Pieter Wuille]

A suggestion: introduce an additional OP_GENPUBKEY, which pops a signature and a 2-bit number from the stack (which states which of the 4 possible generated keys is the right one), and pushes the generated public key (for this transaction and signature) itself onto the stack. From then on, it can be processed by the existing infrastructure, such as checking it against a known value, or first hashing it using OP_HASH160 before comparing it to an address.

A typical scriptPubKey for consuming a spend-to-address would then become:

  OP_GENPUBKEY OP_HASH160 <address> OP_EQUALVERIFY

With corresponding scriptSig:

  <signature> <generatedId>

If we drop the DER-encoding of the signature and just give the 2 256-bit numbers, prefixed with a version byte maybe, this is a 24-byte scriptPubKey, and a 67-byte scriptSig (compared to a 25-byte scriptPubKey and a 139-byte scriptSig now)

As suggested by [mike], we could go for an even smaller but slightly less flexible OP_CHECKSPEND, that does everything:

  <address> OP_CHECKSPEND

Which is only 22 bytes. We could do without the generatedId (allowing a 66-byte scriptSig) in this case, but at a potentially increased verification cost (2 to 4 possible pubkeys need to be verified).

[Pieter Wuille]

ArtForz notes some possibly low-hanging fruit: we verify the same TX multiple times.

Can you elaborate?

[ByteCoin]

ArtForz notes some possibly low-hanging fruit: we verify the same TX multiple times.

Can you elaborate?

I believe that transactions are verified when they are received before they are relayed. When a block is received, all the transactions in it are also checked before the block is relayed even though most of the transactions in the block have already been verified in the process of relaying them to the miner.

ByteCoin

[Pieter Wuille]

What's the extra CPU cost for recovering the public key?  Current bottleneck for bitcoin transaction processing is the CPU cost of ECDSA signature verification, not disk space or bandwidth, so saving bytes at the expense of more CPU is not the right thing to do.

I implemented this in bitcoin using openssl libraries. I tested it on existing signatures (converting them to the 65-byte "compact" signature format described above), and that signatures are always valid for their corresponding recovered public keys (even when recovering from random data).

I benchmarked both signature verification and key recovery. On my system, signature verification takes around 650us, key recovery takes around 685us, so there is a 5% CPU penalty. Note that signing does have a larger overhead (around 150%)

[Pieter Wuille]

Patch is here: https://github.com/sipa/bitcoin/commit/6e223c405988a1002eeeee69db88a1128a38b0a3

[runeks]

I benchmarked both signature verification and key recovery. On my system, signature verification takes around 650us, key recovery takes around 685us, so there is a 5% CPU penalty. Note that signing does have a larger overhead (around 150%)

I've done some stats on signature verification as well, and I'm posting them in this thread so I know where to look the next time I forget the numbers, and for others to reference as well.
This was measured using gettimeofday. Around 4500 signature verifications were performed.
The mean was 1029 µs, and the median 1152 µs. The fastest verification took 797 µs and the slowest 11,224 µs.
Using clock_gettime instead (though only with 110 samples) returned some prettier values. Minimum: 807 µs, maximum: 1372 µs, mean: 1084 µs, median: 1172 µs. So more or less the same.
This was done using a Core 2 Quad (Q9550) processor clocked at 2 GHz (downclocked from 2.83 GHz).

Also, according to my stats, the block chain currently contains around 5.1 million OP_CHECKSIG operations. So CPU time spent merely doing signature verifications in order to verify the current block chain would be around 1 hour and 30 minutes.

[DeathAndTaxes]

Revisting this topic.   While changing the protocol to allow transactions with implicit public key recovery is worthwhile it would be a breaking change so I understand not moving on this.  However there is absolutely no reason for the Bitcoin-Core client to require an address when verifying the signature.  The PubKey can be recovered from the signature the PubKeyHash produced from that and then the address generated from that.  

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?
I would add the UI in the core client for this section is not user friendly.  A user verifying signature has to copy and paste three separate components into three different boxes (one of which is pointless).  How about a unified copy and paste of a single signed message block?
Why not have the user supply the message & signature (preferably in a unified encoded form (i.e. similar to PGP signed message) and then the client verifies the signature and computes and displays the results?

An example which puts it all together.

Input

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

and the client responds with either
Message verified to be signed by 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

or

Message not verified.  Please double check signed message is copied in it entirety including the BEGIN and END lines.


Brainwallet.org has something similar and is more intuitive than the Bitcoin Core client.  Still even the brainwallet website adds a "warning" that is pointless and vague.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T (but address was not found in the signature!)

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

The address is not found in the signature?  Is that bad?  Should I be worried?  Am I being scammed?  To most users, yellow is a color of caution.   The expected outcome would be a definitive "SUCCESS" (and green) but instead there is this ambiguous partial success.  The "yellow" response is pointless as anyone can add the address in after the signature is created to remove the warning.  So what is is warning about.  Adding the address 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T just above the signature looks like this and provides the expected "good" response.

Message verified to be from 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T

Code:

-----BEGIN BITCOIN SIGNED MESSAGE-----
This is an example of a signed message.
-----BEGIN BITCOIN SIGNATURE-----
1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=
-----END BITCOIN SIGNATURE-----

The "caution" response only undermines the point of even allowing signatures that don't include the (unnecessary) address.  Imagine you are a company which sends out signed messages to customers.   Lets use the 80/20 rule.  If you exclude the address 80% of your users will understand the "warning" is pointless however that means you are going to confuse 20% of your customers and that means extra cost and work.  So why not just include the (pointless) address so it shows up as green.

Still the behavior isn't as bad as the core client which refuses to validate the signatures and throws an error.

[Pieter Wuille]

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?

It's done to force people to verify the public key.

As any combination of signature and message results in a recovered public key. you may incorrectly assume it's a valid signature without verifying it is coming from whom you think it is.

[DeathAndTaxes]

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?

It's done to force people to verify the public key.

As any combination of signature and message results in a recovered public key. you may incorrectly assume it's a valid signature without verifying it is coming from whom you think it is.

I can see that as a valid point, I just wonder how much security it really adds.  Unless user already has the address in the wallet ahead of time or gets the address out of band it is very likely they are copying and pasting the signature as provided by the signer (potentially an attacker).  In a case like that the attacker could provide the user the "spoofed" (technically similar) address and most users will copy and paste it along with the other components and get a "good" response.  I think showing the computed address and an explanation (maybe a "what does this mean? link) would do more to prevent social engineering type attacks.  A user controlled preference would be nice, Bitcoin-Core is targeting power users.

Still lets put that aside, a unified signed message block containing the message and signature ("PGP style") should be pretty straightforward.  It would help reduce issues with trailing spaces and copying errors.  Is there a reason that Base64 is used over Base58? One reason Satoshi outlined for using Bas58 over Base64 is that it can be easily copied, try double clicking to copy each of these two signatures.

Code:

HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=

26pGMkiBRMqfZL1ELka3Nd6CSsJWUBdRioWnrvQ4hCejYw9d6ac9oPf6Q7GXfbRnWro7TVysuZeZQf2qgcnhBxhM2

[Abdussamad]

Can anyone think of any reason why the Bitcoin client requires the user provide the address (something it can and already does compute)?

It's done to force people to verify the public key.

As any combination of signature and message results in a recovered public key. you may incorrectly assume it's a valid signature without verifying it is coming from whom you think it is.

I can see that as a valid point, I just wonder how much security it really adds.  Unless user already has the address in the wallet ahead of time or gets the address out of band it is very likely they are copying and pasting the signature as provided by the signer (potentially an attacker).  In a case like that the attacker could provide the user the "spoofed" (technically similar) address and most users will copy and paste it along with the other components and get a "good" response. 

Say this individual you are dealing with wants to prove they sent you bitcoins. You copy paste the address from a block explorer like blockchain.info or your wallet's transaction history. The sig you get from him. If they match you know it's good.

If you just have the sig, and the UI doesn't force you to enter an address, then you have to verify the address in the sig with the one from bc.i manually. So, if the attacker has used a similar address, with say the same first few characters, you might be fooled.

Is there a reason that Base64 is used over Base58? One reason Satoshi outlined for using Bas58 over Base64 is that it can be easily copied, try double clicking to copy each of these two signatures.

Double click selects this which I think is base64:
HHfUi9n72BxXottUu+AbU4iS0QQLxPtAtuydgRcjc+XoY9Hzw8u6Z+wbzDV+owVLiQR85OwioPcUVJcT+LHjqCE=

This requires a triple click:
26pGMkiBRMqfZL1ELka3Nd6CSsJWUBdRioWnrvQ4hCejYw9d6ac9oPf6Q7GXfbRnWro7TVysuZeZQf2 qgcnhBxhM2

[DeathAndTaxes]

Double click selects this which I think is base64 ...

This requires a triple click ...

Stupid forum software inserted html span code into sequence.  I put it into a code box so it should illustrate it better now.