Do all elliptic curves support recovering the public key from a signature?

[Coin-1]

As far as I know, the secp256k1 elliptic curve used in Bitcoin supports extracting the public key from an ECDSA signature (i.e. from the r and s values). The recovery flag, which is a binary number from 28 to 35 (inclusive), is used to uniquely extract the public key.

The coordinates of the point lying on the secp256k1 elliptic curve are calculated by the following formula:
y² = x³ + 7

It is possible to derive two public keys from an ECDSA signature if you know the parameters of this elliptic curve, the hash algorithm and the text of the signed message:
Q₁ = r⁻¹ * (sR − zG)
Q₂ = r⁻¹ * (sR' − zG)
where R and R' are two points that have the X coordinate equal to the r value.

But only one of these public keys really corresponds to the private key that was used to sign the message. As I understand, it is needed to consequently check the four variants for the recovery flag when signing a message in order to avoid such a discrepancy. If it is possible to uniquely extract the public key from the ECDSA signature, such a recovery flag will be added to the r and s values.

See also here.


But I'm curious whether all the elliptic curves support recovering the public key from a signature or not.

For example, the coordinates of the point lying on the ed25519 elliptic curve, which is used in some well-known alternative cryptocurrencies, are calculated by the following formula:
y² = x³ + 486662 * x² + x

Does this curve support extracting the public key from an ECDSA signature? Which of the elliptic curves do not support such a function?

[achow101]

Public key recovery is a function of ECDSA and is not restricted to any particular curves. It is a property of the signature algorithm (ECDSA), not of the curve. So yes, you can do public key recovery with any curve if they are using ECDSA.

The Schnorr signature scheme that is described in the proposed Schnorr BIP doesn't allow for public key recovery even though it uses the same secp256k1 curve that is currently used by Bitcoin.

[Coding Enthusiast]

Note that the formula is longer than that, you are missing the first steps for calculating x¹. For secp256k1 curve (and all the Koblitz curves over F_p defined by SEC-2) since the cofactor of the curve (or h) is equal to 1, you may only recover up to 4 possible public keys from the ECDSA signature. But cofactor of other curves may not be the same. For instance curve25519 cofactor is 8 and if you were doing ECDSA on this curve² then the number of possible recovered public keys would have been 16.

¹. Refer to page 47 of Standards for Efficient Cryptography 1, section 4.1.6 Public Key Recovery Operation https://www.secg.org/sec1-v2.pdf
². Technically you could implement ECDSA algorithm on edwards curve but it is not going to be the standard defined by ANSI X9.62

[Coin-1]

Public key recovery is a function of ECDSA and is not restricted to any particular curves. It is a property of the signature algorithm (ECDSA), not of the curve.

Thanks for the correction. Of course, I asked about the recovery function supported by the ECDSA scheme.

Note that the formula is longer than that, you are missing the first steps for calculating x¹. For secp256k1 curve (and all the Koblitz curves over F_p defined by SEC-2) since the cofactor of the curve (or h) is equal to 1, you may only recover up to 4 possible public keys from the ECDSA signature.

Yes, I looked into the source code that implements the signing of the Bitcoin message, and noticed that it uses the cycle for iterating over the 4 variants for the recovery flag.

But cofactor of other curves may not be the same. For instance curve25519 cofactor is 8 and if you were doing ECDSA on this curve² then the number of possible recovered public keys would have been 16.

As far as I understand, the elliptic curve cofactor is calculated by the following formula:
h = n / r
If h is equal to 1, then the subgroup is a whole elliptic curve.

I know that curve25519 is one of the fastest elliptic curves widely used in the Diffie-Hellman key agreement protocol. Some anonymous alternative cryptocurrencies use this curve. But it seems that curve25519 has a disadvantage compared to secp256k1, because checking 16 variants for the recovery flag when signing a message consumes additional computational resources.

[Coding Enthusiast]

I know that curve25519 is one of the fastest elliptic curves widely used in the Diffie-Hellman key agreement protocol. Some anonymous alternative cryptocurrencies use this curve.

Generally the speed is about the Digital Signature Algorithm (DSA) not the curve itself. This means in case of Curve25519, Edwards variant of DSA (or EDDSA) is used which is fast and makes the whole thing faster. Similarly using a curve like Secp256k1 with EC-DSA (what bitcoin has been using so far) is slower than using it with ECS-DSA (Schnorr algorithm).
Although I believe in case of these curves (Edwards curves) the form of the curve is contributing to the speed ups.

But it seems that curve25519 has a disadvantage compared to secp256k1, because checking 16 variants for the recovery flag when signing a message consumes additional computational resources.

Public key recovery is not something that we really need to perform. All transactions include the public key so there is no need to recover it. The only time such functions are called is for message signature verification, and such operation is only performed once so it doesn't matter if it takes 1 milisecond or 10!
Also remember that public key recovery is not possible on EDDSA in first place, I only mentioned it above as a hypothetical example for ECDSA case with h>1.

[Coin-1]

Public key recovery is not something that we really need to perform. All transactions include the public key so there is no need to recover it. The only time such functions are called is for message signature verification, and such operation is only performed once so it doesn't matter if it takes 1 milisecond or 10!

You're right. There is almost no difference between the time spent checking 4 or 16 variants. In any case, I wonder why such a helpful function as recovering the public key from a signature is [/u]not[/u] used in Bitcoin transactions?


I suggest introducing a new OP_RECOVER-PUBKEY-FROM-SIG instruction which will extract the public key (that is, the X and Y coordinates of the point lying on the secp256k1 elliptic curve) from an ECDSA signature using the recovery flag and will replace the top stack item.


Thus, the "scriptPubKey" output script for P2PK will have the following format:

Code:

OP_RECOVER-PUBKEY-FROM-SIG OP_DUP OP_HASH160 <pubKeyHash>
OP_EQUALVERIFY OP_CHECKSIG

By the way, the first three instructions can be combined into one OP_P2PK-USING-RECOVERY-FLAG.


Accordingly, the "scriptSig" input script used to redeem coins will look like this:

Code:

<sig> <recoveryFlag>

Obviously, the size of the <recoveryFlag> component is one byte, so its value is much smaller than the size of the <pubKey> component. Hence, the size of transactions will be significantly reduced, and as a result, the total number of transactions included in one Bitcoin block can be increased.

[gmaxwell]

If you actually cared about size you'd drop the hash entirely-- the result is much smaller still.  Recovery is pretty slow, unbatchable (which means another 2x slowdown), and has a complicated patent situation.

[Coin-1]

If you actually cared about size you'd drop the hash entirely-- the result is much smaller still.

As far as I know, the standard P2PKH transaction has an input ScriptSig that contains 107 bytes:
1) OP_PUSH (1 byte)
2) <sig> (72 bytes)
3) OP_PUSH (1 byte)
4) <compressedPubKey> (33 bytes)

If <recoveryFlag> (1 byte) is used instead of <compressedPubKey>, the ScriptSig will contain only 75 bytes, so the size of the input script will be reduced by about 30%. If a transaction has many inputs, the total result will be significant.

Recovery is pretty slow, unbatchable (which means another 2x slowdown),

As Coding Enthusiast said:

it doesn't matter if it takes 1 milisecond or 10!

In any case, OP_RECOVER-PUBKEY-FROM-SIG can be optional and will not greatly affect node performance.

and has a complicated patent situation.

If the public key recovery function from an ECDSA signature is covered by a patent, this is a problem. I am surprised why didn't the patent owners restrict services such as Brainwalletx which sign Bitcoin messages using the recovery flag.

[Coding Enthusiast]

As Coding Enthusiast said:

it doesn't matter if it takes 1 milisecond or 10!

It doesn't matter when you are verifying a signed message (eg. proof of ownership), that would be a 1 time call to recover function. So that function being slow doesn't affect anything.
But when you are verifying transaction signatures, most of the times you are doing it hundreds of thousands of times (eg. a new block that contains 2000-3000 transactions or syncing your node and downloading ~600k blocks). In this case the slowness of that function is very important. And it is indeed quite slow:
2x square root (which a ModPow for secp256k1 curve with 256 bit numbers)
6x check point on curve
4x modular multiplicative inverse
6x point multiplication
2x point addition

In comparison the signature verification is:
1x modular multiplicative inverse
2x point multiplication
1x point addition
2x simple integer multiplication