2

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?

migrated from crypto.stackexchange.com Mar 12 '18 at 7:59

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • 2
    Duplicate? bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v – Squeamish Ossifrage Mar 9 '18 at 20:17
  • I have been reading and re-reading that question trying to tweak my code so it always works. Even if I ignore the possibility of X being in that sweet spot for recovery to be 2 or 3 and only pay attention to if Y is even or odd then my code only works 50% of the time. I get that the "duplicate" question exists and explains what V or the RecoveryID is and what it does but it doesn't thoroughly explain how it's generated. – Corey Ogburn Mar 9 '18 at 20:21
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.