ECRecover and Signature Verification in Ethereum

Ethereum Digital Signatures

• Digital Signatures
• Details of ECDSA Signatures
• ECRecover and Signature Verification in Ethereum
• ECDSA Malleability

---

As seen in the previous post of this series, a signature scheme usually has a verification algorithm that computes directly over the public key and the signature to check if the latter is valid. Ethereum is different, and uses ECRecover instead.

ECDSA allows for an alternative approach, where a signature is not verified directly. Ethereum has adopted this method, which is specified in the Ethereum Yellow Paper. This is where things get complicated.

The rest of this post is dedicated to explaining how it all works. You may like to read it with the specification of ECDSA by your side, or open in another tab permanently.

The ECRecover Function

The Yellow Paper specifies 8 precompiled contracts, the first of which, called ECREC, is currently defined in Appendix E as the “public key recovery function”. It is given the alias ecrecover, which in turn is a function in Solidity that invokes this contract.

A reference in Appendix F points to an article from Certicom Research by Johnson, Menezes and Vanstone, but this only lists the traditional verification algorithm indicated above. There is a better reference from the same organization, that has the full recovery algorithm (sections 4.1.4, 4.1.6).

As explained in there, we can verify ECDSA signatures faster if we use some extra information to recover the public key first, and then check the signature. This is an ability provided by ECDSA itself, and is not a general property of other signature schemes.

How does ecrecover work?

Take an ECDSA signature: it is made of two fields, (r, s). Notice that r is the x-coordinate of a random curve point, kG, modulo n.

The y-coordinate of that point is never used in the signature, but s still depends on r.

Point coordinates are, themselves, integers in the field Fq, and since q is larger than n, there are several coordinates that map to the same r.

Ethereum Signatures Have an Extra Field

Now things get mysterious and hard to follow. Ecrecover requires a bit of extra information to recover the signature, a single byte that, according to the Yellow Paper, can take a value only between 27 and 30.

I could not find a reason for this specific range. I went into the source code of Geth to find a bit of a clue if I could, and let me tell you it felt like going into the underground with Theseus and wandering around the Labyrinth.

I looked for the actual implementation of the signature and the recovery algorithms, and this is what I found. In Geth, this extra parameter is called recid, for “recovery identfiier” and takes values between 0 and 3.

This is made clear in the function secp256k1_ecdsa_recoverable_signature_parse_compact in this file and its implementation.

But the most telling clue is in the function secp256k1_ecdsa_sig_sign in the ECDSA implementation, which computes the signature and sets recid. The relevant excerpt is here:

if (recid) {
        /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
         * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
         */
        *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
    }
    
    [...]

    if (secp256k1_scalar_is_high(sigs)) {
        secp256k1_scalar_negate(sigs, sigs);
        if (recid) {
            *recid ^= 1;
        }
    }

Why?

Well, that requires us going a little more into the maths. If you go back to my post on elliptic curves, you will see that they are symmetric over the x-axis. This means that if a point P = (x, y) is in the curve, so is the point P' = (x, -y), and indeed these are defined to be the additive inverses. That is, P’ = -P.

But this means we always have more than one valid signature.

Let’s see. In the signature verification algorithm, we are given a signature (r, s), a message m and a public key Q. We compute a point X = (x1, y1) and accept the signature if x1 == r mod n.

But this check would also return true for -X = (x1, -y1), since it has the same x-coordinate.Now, let’s see what that means about s.

The point X is computed as

X = (eG + rQ) / s mod n. 

And if you look closely, you’ll see we can obtain -X simply by changing s and keeping everything else with

-X = (eG + rQ) / -s mod n

This means, essentially, that if (r, s) is a valid signature, the pair (r, n - s) is valid as well for the same message and signing key.

Public Key Recovery

It is possible to recover a public key from the signature only. Let’s look again at the previous paragraphs and note this:

X = (eG + rQ) / s

Recall that Q is the public key, and that X is the random point chosen during signing. All the other values are publicly known during verification: the base point for the elliptic curve G, the signature pair (r, s),  and the hash of the message e. So, if we know the value of X we can find the public key Q by

Q = (sX - eG) / r

The value X = (x, y) is not known at the start, but it is strongly related to r. This is because x = r + kn for some integer k, where x is an element of the field Fq . In other words, x < q.

For the curve used in Ethereum and Bitcoin, secp256k1:

q = 115792089237316195423570985008687907853269984665640564039457584007908834671663
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

These values are relatively close, that is, the probability of a random element of Fq being greater than n is about 1/2128. This in turn means that the overwhelming majority of r determine a unique x

Conversely, with negligible probability, a random r will have two correspondences: x = r and x = r + n.

With a value of x, we can compute the corresponding y using the curve’s equation: y2 = x3 + 7, which gives us two possible solutions for y, for each given value of x.

The Recovery Identifier

The conclusion from the above is that any r can generate two valid signatures, and a few of them can generate up to 4. Each of them leads to the recovery of a different public key, and so we need a way to distinguish which is the real one.

This is why Ethereum signatures include a third element, the value v, called the recovery identifier. This is the recid variable you can see in the code.

Let’s look at that part again:

if (recid) {
        /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
         * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
         */
        *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
    }

If the value of x is larger than n, recid will be 2 or 3. If not, it will be 0 or 1. Which one it is is determined by the parity of the y coordinate.

As I told you above, there are two valid coordinates for each x. If one of them is y, the other is y' = q - y.  Because q is always odd (since it is a big prime number), if y is even then y' must be odd and vice-versa. That is, y and y' always have opposite parity. So, if the y coordinate of the random point is odd, recid will be odd as well.

We can summarize this in the following way:

Value of recid:
0 - y is even, x is finite
1 - y is odd, x is finite
2 - y is even, x is too large
3 - y is odd, x is too large

The Yellow Paper adds some further caveats to this. First, for some reason it does not explain, it adds a base 27 to these values, so that the results are in the range 27 to 30. Then, it defines that overflow (which it calls finiteness) situations are illegal, further reducing the range of v to 27 or 28.

This brings us to the end of this post. Hopefully, it clarifies the meaning and purpose of the mysterious extra value in an Ethereum signature.

If you like what I write, please hit the like button below, or share it with your contacts. And if you have any comments or questions, write them below and I’ll be happy to reply.

In the next post of this series, I will address one final question, regarding a potential weakness of ECDSA signatures. See you then.