[Ethereum] During ECDSA signing, how to generate the Recovery ID

ecdsarecoverytransactions

I'm working on authoring Ethereum transactions using ECDSA with SECP256K1. On the tail end of an Ethereum transaction is the V, R, and S values of signing a hash of the message. V is defined as chainID * 2 + 35 + RecoveryID where chainID is some value unrelated to this question and RecoveryID is somehow extracted from the signing process or signing keys.

I'm working with the mbedtls library to generate private keys, hash with keccak, and sign using the proper curve. However the output of the signature process is just the R and S values. I keep looking around and can't find a reputable source of what the RecoveryID value is and nothing in mbedtls's documentation talks about it.

In this random (poorly documented) library they check if the Y of the public key is odd. In that forum post they say it's the sign of the Y of the public key. I've tried both and for some private keys the V value works and others it fails to properly recover the public key.

Is there a definitive resource explaining where the Recovery ID comes from?

Best Answer

I never found any proper documentation about the Recovery ID but I did talk with somebody on Reddit and they gave me my answer:

id = y1 & 1; // Where (x1,y1) = k x G;
if (s > curve.n / 2) id = id ^ 1; // Invert id if s of signature is over half the n

I had to modify the mbedtls library to pass back the Recovery ID but when I did I could generate transactions that Geth accepted 100% of the time.

The long explanation:

During signing, a point is generated (X, Y) called R and a number called S. R's X goes on to become r and S becomes s. In order to generate the Recovery ID you take the one's bit from Y. If S is bigger than half the curve's N parameter you invert that bit. That bit is the Recovery ID. Ethereum goes on to manipulate it to indicate compressed or uncompressed addresses as well as indicate what chain the transaction was signed for (so the transaction can't be replayed on another Ethereum chain that the private key might be present on). These modifications to the Recovery ID become v.

There's also a super rare chance that you need to set the second bit of the recovery id meaning the recovery id could in theory be 0, 1, 2, or 3. But there's a 0.000000000000000000000000000000000000373% of needing to set the second bit according to a question on Bitcoin.SE.

Related Topic