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.

Variable size integer encoding

It is a known fact of nature that most integers are small. When transferring data over the network, or to/from disk, or pretty much anywhere the IO is slow, keeping data compact is a plus. Obviously, compression is an option, but it is fairly CPU heavy. Taking advantage of the fact that, in practice, most integer values are small is an option to effectively reduce the amount of data for a modest cost in term of CPU.

Continue reading

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 ?

Continue reading

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.

Continue reading

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.

Continue reading

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

Continue reading

On code review

Code review has become a standard programming practice, for open source projects, but also for many companies that practice it in house. While this practice has proven to be very valuable, many developers struggle with it. So here are some tips and tricks that will help you work more efficiently when code review is involved.

There are (at least) 2 persons involved in code review. Someone that I’ll call a contributor, who want a piece of code to be merged, and a reviewer, who try to confirm that this piece of code meets quality standards and won’t introduce too much complexity compared to the value it provides. Making the whole exercise efficient requires each party to understand and empathize with the other and act accordingly.

Continue reading

Why Can’t Senior Programmers… Program?

This post is obviously a reference to the notorious Why Can’t Programmers.. Program?. I was earlier today reading an article about unreasonable assignment for junior programmer interview. In that article the author describe how some of one of his junior friend had to program a linked list in java that is compliant with the List interface during a job interview.

The whole assignment needed to be done in 30 minutes, and required to implement at least 2 classes and 37 public methods. It seems pretty unrealistic indeed to expect this from any programmer, especially from a junior programmer.

But that isn’t what is the most surprising about this article. The author then goes to mention he tried to do the assignment pair programming with another senior developer and they couldn’t get it nailed down in 6 hours. In fact, they didn’t even started the iterator part of the problem. Damn, 2 senior developers can’t do it that much time ? What can be so hard about it ?

And so I tried

I had to see by myself what was so hard about this, so I setup myself to do the assignment and see how it goes. It was understood that I had tight time constraint, so I had to blast through the spec getting all the methods do what they are supposed to with less than a minute each to get it by the time limit.

For reference, we are implementing the List interface and the ListIterrator interface.

Hopefully, most methods are actually quite trivial, and, without constraint on the complexity, I could do heavy code reuse. For instance, the addAll method will repeatedly call the add method, which is O((N + M) * M) while doing something in O(N + M) wouldn’t have been too hard. The documentation is also nice enough to provide you with all you need, even sometime sample code for complex condition.

Needless to say, I couldn’t get it done in 30 minutes. I needed 35. I would not recommend to use the result of these 35 minutes of intense coding in production. The complexity is high, allocations too frequent but overall, it works™. If I were to use that code, which would be stupid to boot, because Java already provide a linked list implementation in its standard library, but if I were, I would surely improve the test suite, fix the algorithms that exhibit high complexity and make the code more readable.

To my shame, I skipped retainAll, by choosing to throw an UnsupportedOperationException, which is valid per spec.

What to do during the next 5 hours and 25 minutes ?

As I expected, the assignment was way too complex for the time given, but I’m fairly confident that I can achieve some quality implementation in less than 6h by now. To boot, improving complexity, then, getting the gava test suite make sure all of it passes.

Which lead to the question: How come two senior developers can’t get it done in 6 hours ? The industry I work for is full of mysteries, and this is one of them. While I agree with the author sentiment on whiteboard interview to some extent, I may have some insight on the reasons why he never passes them. Sorry buddy.

Truth be told, pair programming, test driven development, denigrating recruiting practices and ruby on rail sounds very good on a blog, but all of it is no more than playing buzzword bingo if one can’t get shit done.

A good interview question ?

Asking to implement a List is a bad interview question. Its too long, and won’t give much signal, and don’t have a reachable first goal within the 30 minutes.

Ideally you want to have a question with an relatively easy answer, but on which one can improve. For instance, a problem with a relatively easy solution of high complexity. Various heuristics can be added and/or discussed to make it perform better.

The interviewer can get signal pretty quickly because there is an easy answer and discussion can follow on how to improve. The problem is open ended, which allow good candidates to really show how far they can go. It also allow for discussion between the interviewer and interviewee, the kind of which help to asses how one works.

Implementing List is tedious, with many corner cases, certainly not doable in 30 minutes and does not allow for much discussion between the interviewer and interviewee.

Don’t do that. Unless you want your candidate to suffer.

Especially for a ruby on rail position…