ECDSA public key recovery: recovery id, v and ecrecover

Short answer. From an ECDSA signature (r, s) and the message hash e, the signer's public key is Q = r⁻¹(s·R − e·G), where R is the curve point whose x-coordinate is r. There are up to four such points, so the signer attaches a recovery id: one bit for the parity of R's y-coordinate and, in theory, one for whether R.x was reduced modulo n. Ethereum encodes it as v (27/28 in messages, chainId·2 + 35 + yParity in legacy transactions, yParity in typed transactions), Bitcoin as the header byte of a 65-byte compact signature (27 to 42). Recovery always returns some key for well-formed input: it is verification only when you compare the result with the address or key you expected. Ethereum's ecrecover precompile returns nothing on malformed input, which Solidity turns into address(0), and it accepts both s and n − s.

The math

ECDSA signing picks a nonce k, computes R = kG, sets r = R.x mod n and s = k⁻¹(e + r·d) mod n. Rearranging the second equation with Q = dG gives

s·k = e + r·d → s·R = e·G + r·Q → Q = r⁻¹(s·R − e·G).

Everything on the right is known except R itself, and the signature contains only its x-coordinate, reduced modulo n. To rebuild R, a verifier needs:

• The parity of R.y. For a given x there are two points, (x, y) and (x, p − y); one has even y.
• Whether R.x ≥ n. On secp256k1 the field prime p is a little larger than the group order n, so an x-coordinate in [n, p) would have been reduced. The chance is (p − n)/p, about 2⁻¹²⁷; it never happens in practice, and Ethereum's v cannot even express it.

That is the recovery id: recid = 2·[R.x ≥ n] + (R.y mod 2), specified in SEC 1 v2.0 §4.1.6 (SEC 1). Written out in Python, with nothing hidden:

def recover(e: int, r: int, s: int, recid: int):
    """Return the public key Q with s = k^-1 (e + r*d), or None if recid does not name a curve point."""
    if not (0 < r < n and 0 < s < n):
        raise ValueError("r and s must be in [1, n-1]")
    x = r + (recid >> 1) * n          # recid 2 and 3: R.x was >= n and got reduced
    if x >= p:
        return None
    alpha = (x * x * x + 7) % p
    y = pow(alpha, (p + 1) // 4, p)   # p % 4 == 3, so this is a square root if one exists
    if y * y % p != alpha:
        return None                   # r is not the x-coordinate of any point
    if y & 1 != recid & 1:
        y = p - y                     # recid bit 0 is the parity of R.y
    R = (x, y)
    r_inv = pow(r, -1, n)
    return add(mul(s * r_inv % n, R), mul(-e * r_inv % n, G))   # Q = r^-1 (sR - eG)


def eth_address(Q):
    k = keccak.new(digest_bits=256, data=Q[0].to_bytes(32, "big") + Q[1].to_bytes(32, "big"))
    return "0x" + k.hexdigest()[-40:]


def eth_personal_digest(message: bytes) -> int:
    data = b"\x19Ethereum Signed Message:\n" + str(len(message)).encode() + message
    return int.from_bytes(keccak.new(digest_bits=256, data=data).digest(), "big")

Nothing here is specific to secp256k1 except the constants and the square root shortcut; recovery works on P-256 too. It is a convention of the Bitcoin and Ethereum ecosystems, not a property of the curve, and JOSE, TLS and WebAuthn transmit or certify keys instead.

Ethereum: a signature from cast, recovered by hand

The lab generated a throwaway key with Foundry 1.8.5 and signed a message with personal_sign semantics (EIP-191):

KEY=$(cast wallet new --json | python3 -c "import json,sys; print(json.load(sys.stdin)['data'][0]['private_key'])")
ADDR=$(cast wallet address --private-key "$KEY")
SIG=$(cast wallet sign --private-key "$KEY" "hello from ecdsa.com")
cast wallet verify --address "$ADDR" "hello from ecdsa.com" "$SIG"
python3 eth_recover.py "hello from ecdsa.com" "$SIG" "$ADDR"

eth_recover.py splits the 65 bytes into r, s and v, tries all four recovery ids, then recovers the same signature against a slightly different message:

address: 0x22baE48F42D493eDcF82ddB7e47480B7233917b3
signature: 0x150e0d6f3cc85f603300fe1801bc4397021a51495c53186f15ecb05f9e57dcbe2a17a5521f6c42792fc22a98754e5c01dd26ac42009e8d24d3cb713a8fe96fed1c
Validation succeeded. Address 0x22baE48F42D493eDcF82ddB7e47480B7233917b3 signed this message.
r=0x150e0d6f3cc85f603300fe1801bc4397021a51495c53186f15ecb05f9e57dcbe
s=0x2a17a5521f6c42792fc22a98754e5c01dd26ac42009e8d24d3cb713a8fe96fed
v=28  (s is low)
recid 0: 0xb1775d58a680572a45fe5d6ba094c56b0b748c9d
recid 1: 0x22bae48f42d493edcf82ddb7e47480b7233917b3  <- v - 27
recid 2: no point (x = r + n is not below p)
recid 3: no point (x = r + n is not below p)
matches the signer: True
same signature, other message -> 0x994ba1aaf9e6b96710727d919140aff23f56407c

Two things to take from it. The wrong recovery id gives a different valid key, not an error, so a verifier that guesses v will happily "recover" someone else. And the same signature over a different message (ecdsa.org instead of ecdsa.com) recovers yet another well-formed address. Recovery has no failure mode for wrong data; only the comparison with an expected signer turns it into a check.

What ecrecover returns

Contracts call the precompile at address 0x01 with 128 bytes: the hash, then v, r and s as 32-byte words. The lab sent five inputs to it on a local anvil node with cast call:

as signed (v, r, s)                0x00000000000000000000000022bae48f42d493edcf82ddb7e47480b7233917b3
twin (55-v, r, n-s)                0x00000000000000000000000022bae48f42d493edcf82ddb7e47480b7233917b3
v = 29                             0x
s + 1                              0x000000000000000000000000412fbd6e833de18577db8f41022c54e852192b34
s = 0                              0x

• The twin (v flipped between 27 and 28, s replaced by n − s) recovers the same signer. EIP-2 made high-S transaction signatures invalid but left the precompile alone: it "will keep accepting high s-values". Any contract that uses the signature bytes as an identifier, for example to mark a signed voucher as spent, can be replayed with the twin. Mark the message (a nonce or the digest) as used, never the signature.
• Malformed input (v outside 27/28, s = 0) produces empty output. Solidity's ecrecover turns that into address(0); its documentation says it returns "zero on error". If the expected signer can ever be address(0) (an unset owner, a missing mapping entry), every invalid signature passes.
• A modified s recovers a random-looking address, as in the Python test.

The usual fix for all three is OpenZeppelin's ECDSA.recover (Contracts 5.6.1), which rejects s above n/2 with ECDSAInvalidSignatureS, a zero result with ECDSAInvalidSignature, and anything but 65 bytes in its bytes overload. Smart-contract wallets have no key to recover at all; they are verified with ERC-1271, as described in Sign-In with Ethereum.

The many shapes of v

Where the recovery bit lives depends on what was signed:

The lab signed with viem 2.57.7 and checked how its recovery functions handle the variants:

for (const [label, sig] of [
  ["65-byte", signature],
  ["64-byte compact", compact],
  ["63 bytes", signature.slice(0, -4)],
  ["v = 29", signature.slice(0, -2) + "1d"],
]) {
  try {
    const who = await recoverMessageAddress({ message, signature: sig });
    console.log(`recover ${label.padEnd(16)} ${who === account.address ? "signer" : who}`);
  } catch (e) {
    console.log(`recover ${label.padEnd(16)} ${e.shortMessage ?? e.message.split("\n")[0]}`);
  }
}

// The same recovery with noble: the recovery bit travels separately from the 64-byte (r, s).
const digest = hashMessage(message, "bytes");
const rs = Buffer.from(signature.slice(2, 130), "hex");
const pub = secp256k1.Signature.fromBytes(rs, "compact").addRecoveryBit(parsed.yParity).recoverPublicKey(digest);
console.log(`noble recovers    ${pub.toHex(true)} (compressed public key)`);

signer            0xa9650f6049917850af00B8e7Ffc386d9A3e18C08
signature         65 bytes, v=27, yParity=0
EIP-2098 compact  64 bytes, top bit of byte 32 = yParity: true
recover 65-byte          signer
recover 64-byte compact  invalid signature length
recover 63 bytes         invalid signature length
recover v = 29           Invalid yParityOrV value
noble recovers    036a079737b9587224344944600570a311f21b3b06f5c920b24bcd95e993afd7e0 (compressed public key)
legacy tx, chain 1: v=38 (yParity 1)
EIP-1559 tx, chain 1: v=28, yParity=1

viem's recoverMessageAddress does not take a 64-byte EIP-2098 string; convert it with compactSignatureToSignature first, or you get invalid signature length. A stray v gives Invalid yParityOrV value. The legacy transaction's v = 38 is 1·2 + 35 + 1. For the EIP-1559 transaction viem reports v = 28 for convenience, but the signed transaction itself only carries yParity. Python's web3.py is just as strict about lengths: Expected 65, but got 64 bytes.

A real bug from writing this lab: flipping the parity with v ^ 1 turns 27 into 26 and 28 into 29, because 27 is odd. Work with yParity = v − 27 (or (v − 35) mod 2 for EIP-155) and convert back at the edge.

Bitcoin: compact message signatures

Bitcoin Core's signmessage produces the same kind of signature with a header byte in front. With a throwaway key in regtest:

SIG=$($CLI signmessagewithprivkey "$WIF" "$MSG")
$CLI verifymessage "$ADDR" "$SIG" "$MSG"
python3 btc_recover.py "$MSG" "$SIG"      # recover by hand, then build three variants

address: mvzrMJdGFmYPJw79zHz5i2WqMHdwchtbr1
signature: H6uRgJJnTugkk5XeUQl+eE1oY5/L6yZZORJHwTn1ohJdFOWEPPUvL6oHzDx2lAeoI+l1d3ipt5sw3TmF/tkpz60=
verifymessage: true
65 bytes: header 31 -> recid 0, compressed key: True, s is low
recovered public key: 03b7b74bd1e7c935c284dbb71b48649f1ff6a5cb939d615061204271a61f4232e1
its regtest P2PKH address: mvzrMJdGFmYPJw79zHz5i2WqMHdwchtbr1
other recid (header 32)              verifymessage: false
uncompressed header (27)             verifymessage: false
high-S twin (header 32, n - s)       verifymessage: true

The digest is double SHA-256 of "\x18Bitcoin Signed Message:\n", the message length and the message. Header 31 means recid 0 and a compressed key; changing it to 27 recovers the same point but hashes the uncompressed encoding into a different address, so verification fails. Like ecrecover, Bitcoin Core's message verification accepted the high-S twin: low-S is a transaction relay rule, not a message rule. For SegWit and Taproot addresses this format falls short; Bitcoin message signing and BIP-322 covers the header variants wallets disagree on and the newer format.

Adding a recovery id to HSM and KMS signatures

Hardware security modules and cloud KMS sign a digest and return a DER-encoded (r, s): no recovery id, and no promise about low-S. To use such a key for Ethereum, you derive its address once from the public key, then for each signature normalize s and find the parity that recovers your own key. The lab simulates the HSM with a pyca/cryptography key that only signs prehashed digests:

"""Turn a DER ECDSA signature without a recovery id (what HSMs and cloud KMS return) into an Ethereum signature."""
import sys

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed, decode_dss_signature

from recover import eth_address, eth_personal_digest, n, recover

# Stand-in for the HSM: a secp256k1 key that signs a 32-byte digest and returns DER, nothing else.
hsm_key = ec.generate_private_key(ec.SECP256K1())
public = hsm_key.public_key().public_numbers()
expected = eth_address((public.x, public.y))     # what you would derive once from GetPublicKey


def hsm_sign_digest(digest: bytes) -> bytes:
    return hsm_key.sign(digest, ec.ECDSA(Prehashed(hashes.SHA256())))   # any 32-byte digest


message = sys.argv[1].encode()
e = eth_personal_digest(message)
der = hsm_sign_digest(e.to_bytes(32, "big"))
r, s = decode_dss_signature(der)
print(f"DER signature: {len(der)} bytes, s is {'high' if s > n // 2 else 'low'}")
if s > n // 2:
    s = n - s                                     # EIP-2: transactions need low-S; normalize everything
for recid in (0, 1):                              # find the parity that recovers our own key
    Q = recover(e, r, s, recid)
    if Q and eth_address(Q) == expected:
        break
else:
    raise SystemExit("neither recovery id matches the key")
sig = r.to_bytes(32, "big") + s.to_bytes(32, "big") + bytes([27 + recid])
print(f"address {expected}\nrecid {recid}\nsignature 0x{sig.hex()}")

DER signature: 71 bytes, s is high
address 0x3bf48296556c8b52217d22066c7239c50f2102e6
recid 1
signature 0x052fbd197e707e99a4c38648b4a65fb674b15c93025878c55b3950f876bb5cf634aa76d1ffe274696a3d94ba225ae72ab73af4292a0681dc7262dc8ef9495d071c
Validation succeeded. Address 0x3bf48296556c8B52217D22066C7239C50F2102E6 signed this message.

The Prehashed(hashes.SHA256()) wrapper only tells the library that the input is already a 32-byte digest; the digest itself is Keccak-256, as Ethereum requires. Trying both parities is safe here because the result is compared with one known address. Note the DER length of 71 bytes in this run against 72 in another: DER drops leading zero bytes and adds one when the top bit is set, which is why fixed-size buffers break (ECDSA signature formats). The same procedure applies to AWS KMS ECC_SECG_P256K1 keys; Google Cloud KMS already returns low-S for secp256k1, but still no recovery id.

When recovery is the right tool

Recovery saves 33 to 65 bytes per signature, which is why Ethereum uses it for every transaction. It also changes what a signature proves. With a transmitted key, a verifier checks "this key signed this message". With recovery it computes "some key signed this message" and must then decide whether that key is acceptable, usually by deriving an address and comparing it with an allowlist, a stored owner or the from the user claims. Code that skips the comparison verifies nothing.

Outside blockchains there is rarely a reason to use it. Protocols that can carry a key ID or a certificate (JWT kid, TLS, X.509) should, and the verifier then looks up exactly one key instead of trusting whatever the math produces.

Common mistakes

• Recovering without comparing. Logging "signature valid" after ecrecover succeeds. Every well-formed signature recovers something.
• Accepting address(0) as a signer, directly or through an uninitialized variable.
• Replay protection by signature bytes. The high-S twin is a second, equally valid signature for the same message.
• Guessing v. Trying both parities and accepting whichever recovers "a" key turns verification into a lookup of any key at all; only try both when you then compare against one expected address.
• Hashing the wrong thing. personal_sign adds the \x19Ethereum Signed Message:\n prefix and the decimal length; EIP-712 uses \x19\x01 and two struct hashes. Recovering with the wrong digest gives a wrong address without an error. The differences are in EIP-191 vs EIP-712.
• Format mismatches between 65-byte, 64-byte EIP-2098 and DER signatures. Convert explicitly at the boundary, and for HSM and KMS output add the recovery id as shown above.

Sources

• SEC 1 v2.0: Elliptic Curve Cryptography, §4.1.6 (public key recovery operation)
• Ethereum: EIP-2, EIP-155, EIP-191, EIP-2098, Solidity: mathematical and cryptographic functions
• OpenZeppelin Contracts ECDSA.sol
• Bitcoin: BIP-137 (signature header format)
• Libraries used: Foundry 1.8.5 (cast, anvil), Bitcoin Core 31.1, viem 2.57.7, @noble/curves 2.4.0, pycryptodome 3.23.0