Schnorr signatures for (not so) dummies

This article is a follow up Schnorr signatures for dummies, make sure you understand its content before reading this one. This article is a bit more technical and complex than the first one

Schnorr signatures are very interesting beasts. If you were interested in the first article and want to learn more about them you are at the right place. However, please be reminded that these blog posts won’t make you a cryptography expert, but simply to convey you a general intuition about how Schnorr works and what you can do with them.

Using (R, s) instead of (e, s)

In the previous article, we explained how the signature can be produced the pair of number (e, s). However, over the years a variation of this scheme has become popular. Instead of sharing (e, s) Alice will share a pair (R, s) with R = k * G. This may not be obvious at first, but this is completely equivalent. R can be computed from (e, s) via R = s * G + e * P and e can be computed from (R, s) via e = H(m || R). As a result, sharing (R, s) provides the same information as providing (e, s).

While computing e from R can be used to verify the signature, using (R, s) validation is usually done in a different manner, by checking that R = s * G + H(m || R) * P.

The important difference is that we run the hash function first, and then do elliptic curve operations, rather than starting with elliptic curves operations and then running the hash function like it is done with (e, s). This seemingly small difference in the way we compute things allows to do various interesting tricks.

Public key recovery

Schnorr signatures allow to recover a public key from a message and a signature via the procedure

1
2
R = s * G + H(m || R) * P
P = (R - s * G) * H(m || R) ^ (-1)

Hardened security

Let’s imagine Alice signed a message m with her public key P = x * G. It is possible for Bob to use Alice’s signature to forge another signature for another public key Q = P + y * G as (R, s – H(m || R) * y) on the same message.

1
2
3
4
5
e = H(m || R)
R = s * G + e * P
R + e * y * G = s * G + e * P + e * y * G
R + e * y * G = s * G + e * Q
R = (s - e * y) * G + e * Q

Depending on the situation, this may or may not be a problem. Because Bob doesn’t know x, Bob cannot create a signature with the public key of his choice. However, in some cases such as key derived using BIP32, it is possible if Bob knows Alice’s master public key to transform Alice’s signature using one public key into another for any public key derived for the same master public key. The details of how this works are a bit off topic here, so I won’t spend too much time on it. Long story short: this is something that could reduce Schnorr signature security in some specific scenarii, and so it is worth fixing.

To do so, we will hash the public key in addition of the m and R when signing and verifying the transaction, such as e = H(m || P || R). Because any change in the public key would produce unpredictable changes in e, Bob cannot use an existing signature to do anything but verify it. This also makes recovering the public key impossible.

Compact and private n-out-of-n multisig

Let’s assume Alice and Bob want to sign the same message. They could produce one signature each, but it would take twice as much space as one signature (!) and would require run the verify procedures twice (!!). Ideally, we’d like them to produce only one signature for both Alice and Bob, and this can be done using Schnorr.

Alice has a private key x0 and a public key P0 = x0 * G. Bob has a private key x1 and a public key P1 = x1 * G. They can add their public key to produce a multisig public key P = P0 + P1 that is common to both of them. We know that P = (x0 + x1) * G, but only Alice knows x0 and only Bob knows x1, so they will need to cooperate to produce a signature. Alice and Bob know that the public key is a multisig, but interestingly enough, it looks like a regular public key to everybody else, and the signature will look like any signature.

To do this, they’ll proceed in 2 rounds. First, Alice and Bob will chose a value for k: k0 and k1. Alice will compute R0 = k0 * G and give it to Bob. Bob compute R1 = k1 * G and give it Alice. Alice do not know k1 and Bob do not know k0, but both can compute R = R0 + R1 and e = H(m || P || R).

Alice will compute s0 = k0 – e * x0 and Bob s1 = k1 – e * x1. From s0 and s1, the value s = s0 + s1 is computed, forming the signature (R, s). This process can be extended to include an arbitrary number of participants.

The verification is done as explained before, by checking that R = s * G + H(m || P || R) * P.

By expanding this into Alice’s and Bob’s value, it is clear why. If we use e = H(m || P || R), we get R = s * G + e * P and further expansion gives:

1
2
3
R0 + R1 = (s0 + s1) * G + e * (P0 + P1)
(k0 + k1) * G = (s0 + s1) * G + e * (x0 + x1) * G
k0 + k1 = (s0 - e * x0) + (s1 - e * x1)

Which works if

1
2
k0 = s0 - e * x0
k1 = s1 - e * x1

Sadly, while this scheme is attractive, it is actually not secure if either Alice or Bob is trying to cheat. Let’s assume Alice wants to cheat. She will ask Bob’s public key P1, and then pretend her public key is Q = P0 – P1. This way, when Bob thinks he is committing to a public key P = P0 + P1, he is in fact committing to the public key P0 = Q + P1. Now Alice has full control and Bob doesn’t know it.

To work around this problem, we use a method to compute the multisig public key which is a bit more involved. First we compute C = H(P0 || P1), second we compute Q0 = H(C || P0) * P0 and Q1 = H(C || P1) * P1. The public key is P = Q0 + Q1. The same scheme as described above work if Alice uses y0 = x0 * H(C || P0) as private key and Bob y1 = x1 * H(C || P1). By using a different factor for Alice and Bob, and making this factor depends on the choice of Alice and Bob’s public keys, it becomes impossible for Alice to chose a key depending on Q1, Bob’s public key. Doing so would affect C, which in turn would affect Q1 in a non linear manner, making this task impossible.

Batch validation

It is common that a system needs to verify a large number of signatures instead of a single one. When validating a signature, the most expensive operations are the 2 elliptic curve multiplications involved. Using the (R, s) representation, we can verify the signature doing the hash operation first, and then perform elliptic curve operations. This means we can use various accounting tricks to validate a group of signature at once.

We established that a signature (R, s) is valid if R = s * G + H(m || P || R) * P. That means that a group of valid signature will verify

1
2
R0 + R1 = s0 * G + H(m0 || P0 || R0) * P0 + s1 * G + H(m1 || P1 || R1) * P1
R0 + R1 = H(m0 || P0 || R0) * P0 + H(m1 || P1 || R1) * P1 + (s0 + s1) * G

Because the multiplication by G can be factorized, by summing all the values of s before doing the multiplication, only one multiplication per signature is required, plus one for the sum of all s * G.

Sadly, this isn’t secure. This is because an attacker can produce a set of signatures that cancel each others. To work around this, we will introduce a random factor z per signature. Not knowing the factor z for each of his signatures, the attacker is now unable to have them cancel each others.

1
z0 * R0 + z1 * R1 = z0 * H(m0 || P0 || R0) * P0 + z1 * H(m1 || P1 || R1) * P1 + (z0 * s0 + z1 * s1) * G

While we defeated the attacker, we also defeated out nice batch optimization by adding one extra elliptic curve multiplication per signature: zn * Rn. Hopefully not, we have one more trick to pull using the fact that

1
z0 * Q0 + z1 * Q1 = (z0 - z1) * Q0 + z1 * (Q0 + Q1)

By keeping a sorted list of point and factors, we can recursively pick the 2 largest values of z and associated point, do the above mentioned transformation, and reinsert the 2 new z and associated points int he list. Every time z0 – z1 is 0, a point can be removed from the list. Doing so properly will see all values of z but one converge toward 0 and leave us with only one elliptic curve multiplication at the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
auto sumOfS = 0;
Heap!(Scalar, Point) heap;

// Ideally, we'd like to build the whole collection and then heapify
// because it is faster that way, but to keep things short
// we won't in this example.
foreach (sig; signatures) {
    auto z = getNewRandom();
    sumOfS += z * sig.s;
    heap.push(z * H(sig.m || sig.P || sig.R), sig.P);
    heap.push(-z, sig.R);
}

heap.push(sumOfS, G);

while (heap.size > 1) {
    (z0, Q0) = heap.pop();
    (z1, Q1) = heap.pop();
    heap.push(z1, Q0 + Q1);

    // We know that z0 >= z1, so z values will get smaller
    if (z0 != z1) heap.push(z0 - z1, Q0);
}

(z, Q) = heap.pop();
assert(z * Q == 0);

Obviously, reducing the number of multiplications come at the cost of having way more additions to do, but the more z values you have, the easier it becomes to find 2 that cancel each others, and the more multiplications you save. This quickly becomes profitable as the number of signatures to check grows.

Conclusion

We have seen variations of the Schnorr signature scheme that allow both more efficient signature verification using (R, s) instead of (e, s) and improve its security by using H(m || P || R), at the cost of being unable to recover the public key from the signature.

Alice signs with R = k * G and s = k – H(m || P || R) * x.
Bob verify with R = s * G + H(m || P || R) * P.

We also explained how we can create n-out-of-n multisig with a single Schnorr signature, and finally, how we can verify many signatures at once efficiently.

There are a few more fancy things you can do with these signatures, but with what was presented here you have enough to understand the main use cases and how they can be made secure and fast, which is where we wanted to go.

One thought on “Schnorr signatures for (not so) dummies

  1. Pingback: SegWit and technologies built on it are grossly oversold | Deadalnix's den

Leave a Reply

Your email address will not be published. Required fields are marked *