During ECDSA signing, how do I generate the Recovery ID?

Question

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?

Answer 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.

Answer 2

• r is the R.x value of the signature's R point.
• s is the signature proof for R.x
• v is a recovery parameter used to ease the signature verification.

v is not required but often included. But what is v?

Since the signature only includes the x coordinate of the point R, there are either 0, 1, 2, 3, or 4 matching y coordinates over the Secp256k1 elliptic curve. These four potential candidates are encoded in something called recovery_id.

A recovery ID can have the values 0..3 depending on the following conditions:

• Is R.y even and R.x less than the curve order n: recovery_id := 0
• Is R.y odd and R.x less than the curve order n: recovery_id := 1
• Is R.y even and R.x more than the curve order n: recovery_id := 2
• Is R.y odd and R.x more than the curve order n: recovery_id := 3

Now we know how to get to the recovery ID. v is simply v = recovery_id + 27 for Bitcoin. In addition to v values of 27..30 that only reflect the recovery ID, there is also the notion of recovering compressed public keys, using the same recovery ID but a v of v = recovery_id + 31.

But we are not talking about Bitcoin, so last but not least, you want to look at EIP-155 because we no longer use the + 27 part that Bitcoin used to prevent replay protection:

v = chain_id * 2 + 35 + recovery_id

That's it.

Answer 3

There may be another method to determine the Recovery ID(rec_id). Since the Recovery ID can only have 4 possible values(0/1/2/3), if you already have the message to sign, public key, and signature, you can try each Recovery ID value and determine which one yields the correct public key value.

There is already an implementation of this function called "ecRecover". For example, in Python, you can use ecdsa_raw_recover from py_ecc library(source code). This function allows you to derive possible public key from the given Recovery ID:

def ecdsa_raw_recover(msghash: bytes, vrs: Tuple[int, int, int]) -> "PlainPoint2D":
    v, r, s = vrs
    if not (27 <= v <= 34):
        raise ValueError("%d must in range 27-31" % v)
    x = r
    xcubedaxb = (x * x * x + A * x + B) % P
    beta = pow(xcubedaxb, (P + 1) // 4, P)
    y = beta if v % 2 ^ beta % 2 else (P - beta)
    # If xcubedaxb is not a quadratic residue, then r cannot be the x coord
    # for a point on the curve, and so the sig is invalid
    if (xcubedaxb - y * y) % P != 0 or not (r % N) or not (s % N):
        raise ValueError("sig is invalid, %d cannot be the x coord for point on curve" % r)
    z = bytes_to_int(msghash)
    Gz = jacobian_multiply(cast("PlainPoint3D", (Gx, Gy, 1)), (N - z) % N)
    XY = jacobian_multiply(cast("PlainPoint3D", (x, y, 1)), s)
    Qr = jacobian_add(Gz, XY)
    Q = jacobian_multiply(Qr, inv(r, N))
    Q_jacobian = from_jacobian(Q)

    return Q_jacobian