Zero Knowledge Proofs

Alice is busy trying to find Waldo in the picture above (or, Wally, for those outside of North America). After some time without success, she is doubtful that he is even in the image at all. Bob assures her that Waldo is there, since he already found him. However, this is not enough to satisfy Alice. She needs proof before spending any more time on the task. How is it possible for Bob to prove this to her, without giving the game away by pointing out his location?

Assuming that the picture is printed out on a sheet of paper, Bob could take a large piece of cardboard and cut out a small Waldo-shaped hole. Then, while keeping the hole covered, he slides the paper underneath and, after correctly positioning it, he uncovers the hole to reveal Waldo! Alice can look with her own eyes and see his face, which looks like this: . She agrees that Waldo is in the image but, since all of the rest of the picture is covered by the cardboard, Bob has not revealed the location. So, she continues with her task in the knowledge that, at least, it is possible.

What Bob has done here, is provided a zero-knowledge proof that Waldo is in the picture. That is, he did this while providing no information to Alice other than the fact that he is there. You could argue that he did provide some information. Specifically, he showed Alice the exact size and appearance of Waldo’s face. However, if we assume that this information is no secret and is already publicly known, then it is true that Bob did manage to prove Waldo’s existence in the image without revealing any other previously unknown information.

Zero-knowledge proofs are a very useful cryptographic technique, finding important applications in cryptocurrencies. This includes zk-SNARKs, zk-STARKs and zk-Rollups, in which there is a growing interest. I do not go into the details of such uses in this post, and concentrate on the idea of zero-knowledge. There are many other simple examples that can be given along the lines of the ‘Where’s Waldo?’ one above, but I will not go through these here. We will look instead at practical cases which can be performed by transferring digital information over a communication channel, such as the internet. For more examples similar to the one above, I refer to the Wikipedia article, which includes the ‘Ali Baba cave’ and ‘two balls’ demonstrations.

---

The Setup

The idea is that one party, Bob (the prover) is privy to some secret information. Maybe he has the private key associated with a publicly known Bitcoin address. Or, he knows how to prove some previously unsolved mathematical conjecture. Or, he has a file whose SHA256 hash is equal to a given value. He wants to prove to Alice (the verifier) that he has this information without revealing the information itself.

I consider interactive proof systems, which consist of the prover and verifier exchanging messages until, eventually, the verifier either accepts or rejects the prover’s claim to know the secret information. This is as in the figure below, showing the flow of information including messages sent between Alice and Bob, until Alice accepts or rejects the proof.

There are a few points worth noting. The last message will always be from the prover (Bob) to the verifier (Alice). This has to be the case, because if Bob does not respond to Alice’s final message then it cannot play any part in convincing Alice of the claim. Next, all of Alice’s messages will be chosen at random. Otherwise, if they are deterministic, then Bob would be able to predict her messages, so they would contain no information and would not be necessary.

The three properties that a zero-knowledge proof system should satisfy are:

• Completeness: If the statement is true, the verifier can be convinced of this fact by an untrusted prover.
• Soundness: If the statement is false, the prover cannot convince the verifier that it is true, except with a very small probability
• Zero-knowledge: The verifier learns no information beyond the fact that the statement is true.

The first two properties should hold for any proof system, and do not relate to the zero-knowledge property. Starting with the the first property, if the Bob has the claimed knowledge, there has to be some protocol which he can use to construct messages that convince Alice of this fact. For the second property we cannot assume that that Bob is honest, or is following any specific protocol. If we are not prepared to accept at face value that he is telling the truth about having the claimed knowledge, why would Alice trust him to be constructing his messages according to an agreed protocol? So, regardless of how he constructs his messages, if he does not have the claimed knowledge then it should not be possible to convince Alice that he does. There is a slight technical point here. Due to the randomness inherent in these proofs, there will be some probability that Alice erroneously accepts Bob’s claim. The idea is that this probability can be made negligible.

The third property is what concerns us in this post. The proof should be zero-knowledge, so that Bob does not leak any information about his secret. In fact, he should not leak any information beyond the fact that he has access to the claimed knowledge. It is tricky to make this idea mathematically precise. Bob does send messages but, what does it mean to say that these do not contain any information? The general approach is that Bob randomizes his messages to obscure any information, beyond the fact that he has access to the secret. I will look at how we can define and prove the zero-knowledge property later

To summarise the ideas in an interactive proof protocol between prover Bob and verifier Alice:

• The verifier will have a specific method of constructing messages which ensures soundness. She does not have to behave according to this method but, if she does, then she is an honest verifier. Generally, out of all possible messages that she could send, only a small fraction would lead to Bob being able to fool her into incorrectly believing he knows the claimed secret. So, an honest verifier will select at random from the possible messages, to leave only a very small probability of being fooled.
• Assuming that he has access to the claimed secret, the prover will have a particular method of constructing messages to ensure completeness. This still leaves some flexibility and, by randomizing over all possibilities, he can ensure that his messages are distributed such that they do not reveal any information about the secret (zero-knowledge). A prover who knows the secret value and behaves in this way is honest.

There are actually two types of statements regarding existence of a secret that we could look at trying to prove.

• Existence: That there exists some object satisfying a claimed property, although we may not know what it is.
• Knowledge: That we know of an object satisfying a claimed property. For example, we may claim to know the private key associated with a public ECDSA/Bitcoin address. Simply claiming that a private key exists would not be useful, if it is not known to us.

We are only concerned with the second type of statement here. The prover Bob is trying to convince Alice that he knows of a secret satisfying some specific properties, rather than just that it exists. If he succeeds, then Alice will know that the secret exists, since she is convinced that Bob has this information She does not have the knowledge of what it is, so is not able to prove that she does to any third property. Interactive zero-knowledge proofs considered here are only able to convince the specific verifier who is taking part in the procedure. Bob would need to repeat the process if we later need to repeat the proof to a third party. For blockchain applications, the prover will typically be constructing a contract or transaction to be submitted to the chain. The verifier is any third party who is validating the blockchain. As such, there are no messages sent from the verifier to the prover, so interactive proofs cannot be used. For these uses, any of the interactive proofs discussed in this post would need to be transformed into a non-interactive format, which I will not look at here, but will follow up in a later post.

---

Graph Colouring

A colouring of a graph consists of assigning a colour to each vertex, so that no two vertices sharing an edge are assigned the same colour. It is called a k-colouring if it uses no more than k colours in total. While it is easy to check whether a graph has a k-colouring for k = 1 and k = 2, for any larger values of k, it is an NP-complete problem. I will consider 3-colourings.

Suppose that, for a specific graph, Bob has found a 3-colouring and wants to prove this fact to Alice without giving any information on the colouring itself besides the fact that it exists. The following interactive proof can be used.

1. Bob commits to a colouring using only red, green and blue, but covers up the vertices so that Alice cannot see the colours.
2. Alice chooses an edge of the graph.
3. Bob uncovers the vertices of this edge, so that Alice can confirm that they are coloured differently using only red, green or blue.

This example could be carried out either physically with a graph drawn on a piece of paper, or with digital data transmitted between Alice and Bob. In the physical case, in step one he ‘commits’ to a colouring by actually filling in each vertex using a red, green or blue pen, and covers them with small pieces of paper to hide the colours from Alice. In the third step, he uncovers them by removing the paper covering the two vertices of the selected edge.

For the situation involving a digital communication channel, we would agree on an ordering of the vertices so that a colouring is given by an array consisting of the symbols ‘R’, ‘G’ and ‘B’. To commit to a specific colouring while ‘covering up’ his choice, the following could be done. For each vertex, he selects a secret random string, starting with its colour symbol and long enough that it is not feasible for Alice to guess. He then computes their hashes, and sends the array of these hash values to Alice. Due to preimage resistance, she is not able to work out his colouring from this. In the third step, he ‘uncovers’ two vertices by sending their strings to Alice. She can check that they have the correct hash, and see Bob’s colour choice by looking at their initial characters. Due to collision resistance, it is not possible for Bob to change his colour choice after committing to them in the first step. For efficiency reasons, with large graphs Bob would likely just send Alice the Merkle root of his array of hashes rather than each individual vertex hash, but that is not important for the current discussion.

As finding graph-colourings is NP-complete, a zero knowledge proof for this implies that all problems in the NP complexity class have a zero knowledge proof. That is, whatever secret data Bob claims to have, if there is a polynomial-time algorithm verifying that it satisfies the required properties, then we could construct a zero knowledge proof that Bob has the data. This does not necessarily result in a practical procedure though.

Soundness: If the above proof steps are carried out multiple times so that Alice is convinced that Bob will always correctly reveal two distinct colours in step 3, regardless of her choice of edge, then she would also agree that Bob has a correct 3-colouring. This is because, if the pair of vertices associated with every choice of edge shows up two distinct colours of either red, green, or blue then, by definition, it is a 3-colouring.

We can be a bit more precise. Suppose that, in step 2, Alice chooses one of the m graph edges uniformly at random. If Bob does not have a 3-colouring, then at least one of these choices would fail to be correctly verified in step 3. The probability of this happening is at least 1/m. Suppose that the procedure above is repeated n times, and Alice chooses her edge in step 2 independently and at random each time. Then, the probability of Bob revealing valid colours in step 3 every time is bounded by

The full interactive procedure is as follows. First, an integer n is chosen large enough that (1 - 1/m)ⁿ is negligible. The 3 steps above are executed in order n times with, at each stage, Alice making her choice in step 2 entirely randomly. If Bob reveals valid colours in step 3 for each of these runs, Alice concludes that he has a 3-colouring.

Completeness: If he really does have a 3-colouring, then it is straightforward to ensure that whenever the steps of the interactive proof are performed then valid colours are always revealed in step 3. All he has to do, is commit to a valid colouring in step 1. So long as he does this, Alice will conclude that he has a 3-colouring.

Zero-Knowledge: Bob does have to use some care to ensure that he does not reveal any information of his 3-colouring to Alice. Suppose, for example, multiple runs of the procedure are carried out, but Bob commits to this same 3-colouring every time. Alice could select different edges on each run so that, by the time she has chosen edges connecting every one of the vertices, she would know his entire 3-colouring.

To avoid such issues, Bob can do the following. He starts with a specific colouring using only red, green and blue. Before step 1 above for each run, he applies a random permutation to the colours. This means that step 3 will always reveal a pair of distinct colours chosen uniformly at random from red, green and blue. Since this is a known fixed distribution, not depending on Bob’s colouring, Alice gains no further information.

---

Private Key Ownership

In a public key cryptosystem, a participant starts by choosing a key pair consisting of a private (or secret) key and a public key. As the names suggest, the value of the private key is kept secret, whereas the public one can be freely distributed. The way that this works, is that the private key is chosen at random by the participant, making it virtually impossible for any third person to guess its value. The public key is computed from this by a one-way function, so that there is no known way to invert it to recover the private key. As discussed in the post on digital signatures, the private key is used by the participant to digitally sign messages, which can then be verified by any third party in possession of the public key.

Public key cryptography, such as that used by Bitcoin, is often based on an elliptic curve E. Assume that this curve is a cyclic group of order a huge prime number p. For example, the secp256k1 curve used by Bitcoin has order

0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

I use additive notation for elliptic curves, so that the group operation applied to two points P and Q is written as their sum P + Q. The product of an integer x and group element P is x.P. Note that multiplicative notation is often used, in which case the product is instead written as the power P^x, but this is nothing more than a notational difference. A public key cryptosystem starts by fixing a base element (or generator) G of the group.

A private key is nothing more than an integer x in the range from 0 to p – 1 inclusive. This is chosen at random, and the public key is simply the product of x with the group generator,

This setup is as I described previously for Schnorr signatures, but the ECDSA algorithm also has exactly the same setup for the key pair, differing only in the way signatures are constructed and verified.

Suppose that Bob claims to have the private key associated with a known public key P. How can he convince a third party, such as Alice, that he does indeed have this information? Clearly, he does not want to give away the private key, since this would also give access to any Bitcoin secured by it. One method, which is used in practice, is for Bob to sign a message of Alice’s choice (within reason…he would not sign a Bitcoin transaction giving Alice access to the coins). Alice can then verify the message. This is not truly zero knowledge. Even though Alice has no way of recovering the private key from a digital signature, she has still gained knowledge of a valid signature for that specific message which, if she was not trustworthy, she could try and pass off as her own signature to another party.

Instead, I look at a zero-knowledge approach by which Bob can convince Alice that he knows the private key. Consider the following exchange of messages between Bob and Alice.

1. Bob sends a curve point R to Alice.
2. Alice chooses a curve point Q equal to either R or P + R, and sends to Bob.
3. Bob sends an integer s satisfying Q = s.G to Alice.

Soundness: In the second step, Alice has a binary choice to make. If Bob is able to respond correctly, regardless of her choice, then we can argue that he has access to the private key. This is because, he must be able to come up with two integers s₁ and s₂ satisfying,

Taking the difference of these,

So, if Bob is able to produce numbers s₁ and s₂ corresponding to Alice’s available choices at the second step, he just needs to take their difference to obtain the private key, x = s₂ – s₁ (modulo p). Hence, if Bob is consistently able to send a valid integer s in step 3 for multiple runs of the protocol above, Alice will conclude that he has access to the private key.

We can be a bit more precise. Suppose that, in step 2, Alice makes her choice of Q at random, with equal chance of picking R and P + R. If Bob did not know the private key, then he would only be able to give a successful response in step 3 for one of these, which has a probability of 1/2. So, it is possible that Bob manages to fool Alice entirely by chance with a single run through the procedure, but only with a probability of 1/2. Suppose that we were to repeat the procedure a number n times, with Alice making her choice in step 2 independently for each run. If Bob does not know the private key, then the probability that he successfully sends a valid value for s in step 3 on all runs is no more than 2^–n.

The full interactive procedure is to first pick n large enough that 2^–n is negligible (e.g., n = 128). The 3 steps above are executed in order n times with, at each stage, Alice making her choice in step 2 entirely randomly. If Bob is able to send a valid integer s in every one of these runs, Alice concludes that he has the private key.

Completeness: Suppose that Bob starts by choosing an integer t and sets R = t.G. Then, if Alice chooses Q = R in step 2, he responds with s = t in step 3. On the other hand, if she chooses Q = P + R, then he responds with s = x + t (modulo p). This satisfies the requirements since,

Hence, Alice will be convinced that he knows the private key x.

Zero-Knowledge: In the procedure followed by Bob in the completeness argument, he needs to be careful about how his initial number t is chosen. For example, if he used the same value for two separate runs, so that Alice is sent the the same point R, then she would be able to learn the private key. To do this, she simply makes a different choice in step 2 of each of these runs. Suppose she chooses R and P + R in the two runs, and Bob responds with numbers s₁ and s₂ respectively. Alice verifies that,

Taking the difference gives,

so that she can compute the private key as x = s₂ – s₁ (modulo p).

To avoid leaking such information, Bob can make his choice of t uniformly at random over the integers from 0 to p – 1 inclusive, and independently for each run of the procedure. Then, R = t.G will be a uniformly random point of the curve. It follows that P + R is also a uniformly random point, and the integer s sent at the final step will also be uniformly random, for each of the choices that Alice can make. The only information that Alice ends up with is a random integer s and a random point on the curve equal to s.G, which she is able to compute herself already. So, there is no information to be gained other than the fact that Bob could respond regardless of which choice she made, giving a zero-knowledge proof. This is a little vague, and we still do not have a precise definition of ‘zero-knowledge’, but it gives the idea and I will make this a bit more precise in a moment.

---

Proof of Private Key Mk2

In the examples above, I argued that they were zero-knowledge proofs, so long as Bob randomizes his messages in the proposed fashion. My arguments were a bit handwavy, which is inevitable since we have not yet given a proper logical description of what ‘zero-knowledge’ even means. It is important to have a definition, so that we are able to evaluate whether or not a proof is really zero-knowledge. We need this since, otherwise, it is possible for it to leak information in ways that we had not considered.

The proof system described above for Bob to convince Alice that he has possession of a private key x corresponding to known public key P could be generalized in the following way, known as the Schnorr protocol.

1. Bob sends curve point R to Alice.
2. Alice chooses integer e and sends to Bob.
3. Bob sends integer s satisfying e.P + R = s.G to Alice.

The procedure given previously was just the same as this but, effectively, only allowed Alice to select e equal to 0 or 1 in the second step. This updated version is also both sound and complete. Suppose that, for two different possible choices e₁ and e₂ in step 2, Bob is able to answer with valid values s₁ and s₂ respectively in step 3. This implies that he knows solutions to,

Taking the difference gives

allowing him to easily compute the private key x as (e₂–e₁)^-1(s₂–s₁) modulo p. So, if Bob does not have access to the private key, there is at most one value of e for which he could give a valid response in step 3. If Alice chooses e uniformly at random, the probability of selecting this specific value is 1/p, which is negligible, and much better than the previous 1/2 bound. So, only a single run through the steps should be enough to convince Alice that Bob has access to the private key.

For completeness, Bob can start by selecting an integer t and setting R = t.G in step 1. Then, in the final step, he can respond with s equal to the value ex + t to convince Alice that he has knowledge of the private key.

At first, you might think that this procedure is also zero-knowledge. After all, if Bob acts as just described and selects the value t uniformly at random on the range 0 to p – 1 inclusive, then his R value will be a uniformly random point on the curve. For each specific choice of e by Alice in step 2, the value of s that Bob responds with will also be uniformly random. However, it is not zero-knowledge.

Recall the Schnorr digital signature algorithm. A valid signature for a message string m is equivalent to a triple (R,e,s), for a curve point R and integers e and s (modulo p) satisfying,

Here, h is the hash function with argument being the concatenation of digital representations of R, P and m. If, in the interactive proof procedure outlined above, Alice computed the value of e as here, then Bob’s value of s in the final step would provide her with the digital signature. That is, the interactive proof procedure above allows Alice to trick Bob into signing any messages that she wants! This is not only not zero-knowledge, but gives away knowledge that could be catastrophic for Bob and allow his Bitcoin to be stolen.

We need a proper definition of zero-knowledge which ensures that Bob does not give away any sensitive information.

---

Proof of Private Key Mk3

It is possible to rescue the the second proof above that Bob knows a private key, and make it zero knowledge. The idea is to ensure that Alice’s choice of e does not depend on R in any way. This can be done by requiring Alice to commit to e by sending its hash before she receives R from Bob.

1. Alice commits to integer e by sending its hash to Bob.
2. Bob sends curve point R to Alice.
3. Alice sends e to Bob, who checks that it has the correct hash.
4. Bob sends integer s to Alice, who checks that it satisfies e.P + R = s.G.

The proof of soundness and completeness follows in much the same way as above. We could also make Alice concatenate e with a random string before taking its hash, just to make sure that Bob is not able guess its value before choosing R. However, since e is chosen randomly from such a large set that it is infeasible for Bob to check, this is not important. It is still the case that, if Bob does not know the private key, then the probability that he can fool Alice that he does is negligible, at about 1/p.

It is no longer possible for Alice to trick Bob into signing messages, since she cannot choose e to depend on R. Given that the previous proof leaked sensitive information when, at first glance it seemed good, we might still be a bit uneasy about using this modified version. However, as we will see, it is indeed zero-knowledge.

---

Simulation and Zero-Knowledge

An interactive proof procedure can be shown to be zero-knowledge by using a simulation to replace the role of the prover, Bob. This simulator is bound by the same rules as Bob, but does not have access to any private information. It is only allowed access to knowledge that Alice already has. At the same time, we ask that the simulation is able to fool Alice, via the interactive proof, that it does have access to the secret data. The idea is that, if Bob was to use the interactive proof to convince Alice that he knows the secret but, at each step, his messages have the same random distribution as the simulator, then it must be zero-knowledge. This is because he is only providing information that Alice can already compute by running the simulation by herself.

There is a rather big and obvious problem with this idea. If we can find a simulator which can fool Alice into believing that it has the secret data, then the interactive proof system cannot be sound. It is a basic requirement that it is not possible for anyone without knowledge of the secret data to be able to fool Alice into believing that they do. At least, not outside of a tiny probability.

To have any chance of finding a simulation which can fool Alice, we need to give it some ability not granted to any real prover. Specifically, the simulator is granted unlimited do-overs. This means that, at any time, it is allowed to effectively rewind time to an earlier point of the procedure and try again.

Consider the graph-colouring problem. A simulator could be designed such that, at the first step, it colours each of the vertices independently red, green or blue at random. This is unlikely to be a valid colouring, but never mind. At step 3, when the simulated ‘Bob’ reveals the two vertex colours, they will both be independent and uniformly random. So, there is a 1 in 3 chance that they are the same, and he fails the test. If this happens, he requests a do-over, goes back to step 1, and starts again with a new random colouring of the vertices. If it goes wrong again, he just requests another do-over and, so-on, until eventually in step 3 the two uncovered vertices have distinct colours. When that happens, they will be uniformly distributed over all possible pairs of distinct colours from the allowed choices of red, green and blue. This is just the same as for the real Bob who uses an actual 3-colouring with a random permutation applied to the colours.

Consider the first interactive proof that Bob uses to convince Alice that he possesses the private key. This can also be done by simulation. At the first step, simulated Bob chooses a random integer s in the range from 0 to p – 1 and sets Q = s.G. He also randomly selects a curve point R equal to either Q or Q – P, both choices with 50% probability. This is the value he sends to Alice, and will be uniformly distributed over the curve and, independently, Q is equal to R or P + R, both with 50% probability. In step 2, Alice has a 50% chance of choosing the same value that the simulator has for Q, in which case it responds with its value of s. Otherwise, it requests a do-over and starts again. When the process successfully terminates, R will be uniformly distributed on the curve just as for the real Bob who sets R = t.G for a random integer t.

We also can try building a simulation for the second, non zero-knowledge proof of possessing the private key, and see what goes wrong. Simulated Bob would independently choose random integers s and e in the range from 0 to p – 1 and set R = s.G – e.P. If, in step 2, Alice chooses the same value for e, then he responds with his value of s, otherwise requests a do-over. While this technically works, the probability of Alice choosing the correct value of e is only 1/p, which is tiny. The expected number of do-overs is then p, which is huge, and is similar to simply trying to crack the private key by a brute-force search of the whole space. While theoretically possible, this is not feasible, and the simulation would never end in any reasonable length of time.

The third proof that Bob has the private key does have a practical simulation. In step 2, simulated Bob chooses R however he likes. Then, after Alice reveals e in step 3, Bob rewinds, chooses integer s uniformly at random, and replaces R by s.G – e.P. If he sends this same value of s in step 4, then the proof succeeds. This value of R is uniformly randomly distributed, just as with the real prover Bob, so we can conclude that it is a zero-knowledge proof.

These considerations show that we should put some restriction on the complexity of the simulation. A reasonable way to prove that an interactive proof is zero-knowledge is, then, to construct a simulation with unlimited do-overs, which almost surely terminates with a reasonable amount of computation. By ‘reasonable’ here, we mean that it can feasibly be performed by Alice. A more mathematical condition, is that it runs in probabilistic polynomial time. If the resulting messages have the same joint distributions as ones with the real Bob, who has access to the secret data, then we say that it is zero knowledge.

In the graph colouring problem, the simulated probability of having to re-do the steps was 1/3 each time, so the total expected number of repetitions is, on average, just

Similarly, for the first proof of private key possession, the probability of repeating was 1/2, so the expected number of repetitions is,

The argument why the existence of such a simulation implies zero knowledge, is that Alice could perform it all by herself. Since the messages will have the same distribution as those from real Bob, we can say that these do not provide any information that Alice can’t compute on her own, other than the simple fact that Bob is able to successfully pass the test without resorting to do-overs. If this can be done by anyone with access to the secret data, Alice does not obtain any knowledge beyond the fact that Bob knows the secret.

Simulation also shows why zero-knowledge proofs are probabilistic. At any time, the simulator has a non-zero chance of not requiring a do-over. There is a nonzero, but possibly vanishingly small, probability that it makes it all the way through the process without any do-overs at all. This fools Alice into erroneously accepting that it has access to the data.

A more technical definition is obtained by replacing the roles of the prover Bob, the verifier Alice, and the simulator, by probabilistic Turing machines. These compute the messages to be sent from the previously received messages. Let us suppose that the prover Bob’s messages are computed by Turing machine P. Suppose also that, for any choice of verifier Turing machine V which runs in probabilistic polynomial time (PPT), then there is a simulator S which is also a Turing machine running in PPT. This simulator generates both of Alice and Bob’s messages, and with the same joint distribution as the original prover/verifier combination. Then, we say that the interactive proof is zero-knowledge. In practice, the simulator would work by running the verifier Turing machine for Alice’s messages, and rewinding to an earlier state when it is not able to continue.