Schnorr signatures for (not so) dummies

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

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

 12345 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:

 123 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

 12 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

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

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

Schnorr signatures for dummies

There has been a lot of hype about Schnorr signatures lately. The reason being that the patent expired few years ago and numerous people are working on using them instead of ECDSA.

If you are not familiar with math lingo, however, it may not be obvious what Schnorr signatures are and how they work. In this article I’ll try to demystify this signature scheme.

Using Merklix tree to shard block validation

When scaling a system, there always comes a time when all of the processing cannot be done on one machine. This problem is solved by spreading the workload across several machines. This presents some challenges however, solutions are well known in the industry.

In a trustless system such as Bitcoin, peers generally do not trust each other. Currently this is solved by having all peers doing all of the validation, which obviously doesn’t scale, at all. If we are to shard the blockchain, how can a node trust that other shards are validating properly ?

SegWit is not great

Let’s talk about SegWit. While I never was a fan of SegWit, the Hong Kong agreement seemed like a reasonable enough compromise to me to go along with it. Now that Bitcoin Core decided to betray the community by not abiding by its agreement, it is time for me to express why SegWit is not great.

Efficient mempool synchronization using bloom filters and entropy coding

One of the major challenge to scale bitcoin is that a lot of the work done by nodes is reactive. Nodes receive a block and start validating. This takes time and resources and is right in the hot path. The problem gets worse the bigger the block are, to the point were consensus takes more and more time to be reached. At some point, consensus cannot be reached.

In order to improve scaling capabilities of the network, it is key that nodes do as much work as possible ahead of time. When a block is received, node just have to assert that the node effectively contains what they expected, which speeds up validation significantly.

Using Merklix tree to checkpoint an UTXO set

In a previous article, I introduced Merklix trees as a way to cryptographically describe an unordered set or map. It is possible to produce proof that an element is contained or absent of the datastructure in o(ln(n)), and use these proof to mutate the structure, even without knowing its full content.

I will now explain how this can be used to help handling the UTXO set in blockchain technologies like Bitcoin.

Introducing Merklix tree as an unordered Merkle tree on steroid

Merkle tree are awesome. They allow to hash an ordered set of elements and provide a way, known as a Merkle proof, to prove that a given element is at some position in the set without having to provide the whole set. While this is a very useful tool, the fact that it is ordered can be somewhat troublesome. Inserting or removing an element in the middle of the set will require significant work and, more generally, 2 sets containing the same elements, but in a different order will yield 2 radically different trees.

Today, I’d like to introduce a new tool to the software engineer toolbox, which, as far as I know – and that probably tells more about my searching-foo than anything else, hasn’t been proposed before. The goal is to hash an unordered set in such a way that:

• The end result is the same, no matter in what way the tree is created
• Insertion and deletion are ln(n)
• It is possible to produce a proof that an element is contained in the set without producing the set