BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage Articles Zero-Knowledge Proofs for the Layman

Zero-Knowledge Proofs for the Layman

Key Takeaways

  • There is a surge in interest in zero-knowledge proofs, particularly in the context of blockchain-based decentralized systems.
  • Challenges exist in explaining zero-knowledge proofs, therefore most articles target either mathematically-inclined readers or offer examples limited to specific scenarios.
  • Zero-knowledge proofs can be used to demonstrate knowledge of various secret solutions, such as hash preimages, private keys for public keys, or specific transactions for maintaining blockchain integrity.
  • Zero-knowledge proofs can establish the reliability of a method without disclosing the method itself.
  • Check out a simple algorithm to implement zero-knowledge proof using logic gates to any problem that requires hiding secrets.
     

Zero-knowledge proofs have come up with a lot of buzz in recent times, thanks to the advent of blockchain-based decentralized systems. For example, cryptocurrencies like ZCash and Monero provide private transactions on a public blockchain based on zero-knowledge proofs.

But what exactly is this magical cryptography that can provide the answer to any kind of privacy requirements on a blockchain? As expected, there is no shortage of articles trying to explain what a zero-knowledge proof is and how it works.

However, they are either targeted to a mathematically equipped audience or they are simple examples of specialized zero-knowledge proof systems. By specialized, I mean they are meant to accommodate only specific kinds of proofs. The question is: "what can you prove with a zero-knowledge proof?" The short answer is: "almost everything". The long answer requires a little bit of explanation.

When we say 'zero-knowledge proof' in the context of cryptography, we mean the proof of the knowledge of a secret solution to a problem (or a puzzle). It can be the knowledge of the preimage of a hash function, or the knowledge of the private for a public key, or the knowledge of specific transactions that would maintain the integrity of a blockchain.

In this article, I will try to convince you that you can prove the knowledge of any such secret solution to any problem in zero-knowledge, i.e. without sharing anything about the secret. For example, if Alice knows the preimage of a specific SHA256 hash value, she can prove her knowledge to Bob without giving up even a single bit of the preimage.

A Simple Example

Let us consider a fictional story. Say Mary is an inventor of a mechanism to determine whether a very small amount of arsenic impurity is present in steel. She does not want to disclose it, but wants to get paid by the industry per test. Let Tom be a manager at a steel factory who has no reason to believe that Mary's methods are correct. But, in case it is, Tom would like to buy her services. How would Mary convince Tom that her method is a hundred percent reliable without disclosing how she does it?

Mary proposes the following  - Tom would prepare 128 samples of either pure steel or steel with the specified amount of arsenic impurity based on a coin toss. For each sample, Tom tosses a coin, if it is heads, he produces pure steel. If it is tails, he produces steel with arsenic impurity. He writes down which one is which and then hands the samples over to Mary. Mary can only see the sample identifiers without knowing which one has impurities. Now, her job is to tell which sample is of which kind, and Tom accepts her proof if she is correct in every case. Now, if Mary had no reliable method, and she was just guessing, then the probability of her being correct for every sample is only 2-128, which is very small. So, if she is correct in every case, Tom has every reason to believe that she does have a method to distinguish the pure samples from the impure samples.

This is an example of a zero-knowledge proof. Mary could convince Tom that her method works without disclosing how she is doing it. The question is, what kind of proofs can be provided in zero-knowledge. It turns out that almost anything that can be proven can be proven in zero-knowledge. Let us say that if you have the solution to a puzzle or you know the private key corresponding to a public key, all of these can be proven in zero-knowledge, i.e. without giving up the solution to the puzzle or your private key.

In this article, we will try to see that this is possible without having to go into the math required for the efficient zero-knowledge proof systems that are used in the industry.

Blind Dates

Let us imagine a different scenario. Mary and Tom went on a blind date and want to decide whether they want to go on a second date. However, it would be  awkward if either of them wanted to go on a second date, but the other one did not. So, they have to ask each other in such a way that if either does want to go, the other cannot know that unless they want to go as well.

Essentially, we want to implement an AND gate, where each one wanting to go represents an input of 1 while not wanting to go is represented by a 0. If the output of the AND gate is 1, that means each input must also have been 1, so they both want to go. However, no one can know the other person's input beyond what can be derived from their input and the result of the computation.

How can we achieve that? Let us assume that both of them are honest, i.e. they do what they are expected to do, but they are also inclined to remember anything they have seen. One solution then can be as follows. We assign each possible value of each input to the AND gate with a key. So, if Tom says 0, his input is represented by the key \(K_T^0\); on the contrary, if Tom says 1, his input is represented by the key \(K_T^1\). The superscripts here just represent the value the keys represent and are not exponents. Similarly, Mary's inputs are \(K_M^0\) and \(K_M^1\) for 0 and 1 respectively. Let us now have four boxes, each of them can be opened by two keys used together, one from Tom's keys and one from Mary's keys. We can have the boxes as follows:

  1.     Box \(B_0\)  can be opened using \(K_T^0\)  and \(K_M^0\) used together.
  2.     Box \(B_1\) can be opened using \(K_T^0\) and \(K_M^1\) used together.
  3.     Box \(B_2\) can be opened using \(K_T^1\) and \(K_M^0\) used together.
  4.     Box \(B_3\) can be opened using \(K_T^1\) and \(K_M^1\) used together.

The boxes look identical from the outside, but they contain a piece of paper with a value printed on it. Each of \(B_0\),\(B_1\), and \(B_2\) contains a paper with a zero. \(B_3\) contains a paper with a 1.

Now, if Tom could somehow provide the key corresponding to his input and Mary hers, any of them could open the box that can be opened with those keys  - by attempting to open each box with the pair of keys provided - and learn the outcome of their decisions. This does not tell the other person about their inputs because the keys are not marked with the values they represent, and the boxes look identical from the outside.

Either of them can be tasked with actually opening the box, as long as they are only allowed to try just one of their keys. If that person were allowed to try both of their keys, they could know which is the input of the other.

At the beginning of the protocol, one of them has to create the boxes and the keys. Let's say Tom creates the boxes. Then he knows all the values and what each key means. Hence, if he is allowed to see which key Mary chooses, he would know what her decision was. Hence, if Tom creates the keys and the boxes, it must be Mary who opens the box. Now, there needs to be a way for Tom to give Mary the key corresponding to her choice so that she gets only that key, but Tom has no way of knowing which one she picked.

Note that Tom must not give Mary both keys because that would allow Mary to compute the function for both of her possible inputs, thus disclosing Tom’s input to her. So Tom puts each of Mary's keys in an individual envelope and attaches a tag to each of them that tells Mary which is 0 and which is 1. Mary opens the one corresponding to her choice and removes the tag from the other envelope.

Then, they destroy the unopened envelopes in public and Mary opens the box that can be opened with the key provided by Tom and her own key. The piece of paper inside the box represents her answer, which she shows Tom. If Tom has signed each of the papers inside the boxes, there is no way for Mary to cheat by replacing a paper by her own. Tom can cheat by manipulating how he creates the boxes.

For example, Tom can choose to create the boxes in a way that both the boxes have 1 written on each piece of paper. This way the output would be 1 irrespective of the inputs. However, we have assumed Tom to be curious but honest at this point.
Now that I have discussed how to construct a protocol for an AND gate, I leave it to the reader to make the changes to implement a XOR gate and an OR gate.

Three-party Voting

Let us now consider a different scenario. Tom, Dick, and Harry want to decide which destination to visit for their vacation. There are two choices - 0 and 1. They decide that they must choose the location based on a majority vote. How can we get a Boolean circuit for a majority vote? The following circuit works as desired:

\((T∧H)∨ (H ∧ D) ∨ (D∧T)\)

Here, \(T\) is the input of Tom, \(D\) is the input of Dick, and \(H\) is the input of Harry, where \(∧\) represents an AND gate and \(∨\) represents an OR gate.

If the formula returns 1, at least one of the clauses in the parentheses has to evaluate to 1. Hence, at least two of the inputs have to be 1. So, our vote can be evaluated with a circuit with three AND gates and two OR gates.

Let’s say, now, that we have to make sure that people do not learn about who voted for the less popular choice. To this aim we can use the boxes and keys approach as seen before but, here, we need to use the output of the AND gates as inputs to the OR gates. This is very simple to do: instead of having the pieces of paper with 0 or 1 written in the box, we put the keys corresponding to the input of the next gate. There is a key corresponding to the output 0 and one for the output 1 for the gate. But since there are four boxes, the boxes that represent the same output for the gate must contain duplicates of the same key.

The system described here is called Yao's garbled circuit. Notice that this technique can be used for any computation using any Boolean circuit. Since all kinds of computations can be expressed in terms of Boolean circuits, we can make garbled circuits for any computation. The boxes are replaced by encryption and the keys are replaced by encryption keys in a cryptographic system. We will use this approach to build our zero-knowledge system.

Zero-knowledge Proof

We have already seen how to make a garbled circuit out of any circuit. How can we use it to make a zero-knowledge proof?

Let \(f\) be a function that takes a set of Boolean variables as input and outputs either 0 or 1. We can find such a function for anything we want to prove. For example, if the prover claims that he knows the factorization of a number \(n\), our \(f(n,x)\) will output 1 if and only if the input \(x\) represents two numbers greater than one whose product equals the input \(n\). We can represent the input numbers in binary, make a Boolean circuit to find the product of the number, and then make a circuit to check whether the output matches the binary representation of \(n\).
But how will the prover convince a verifier that he does know the factorization without giving the verifier any clue about what the factorization is? The following is a technique we can try to use:

  1. The prover makes a garbling of the circuit of \(f\) and gives it to the verifier.
  2. The prover then provides the keys corresponding to its input \(x\) to the verifier. Note that the verifier cannot tell whether the keys represent 0 or 1.
  3. The prover also gives the keys corresponding to the verifier's input n with the envelope trick. But since the verifier does not need to hide \(n\), he can open the envelopes in public.
  4. The verifier runs the garbled circuit and checks if the final output is 1.

The technique certainly hides the prover's input from the verifier, but it does not guarantee that the prover did not cheat by creating a garbled circuit of a function different from \(f\). To verify that the garbled circuit was created correctly, the verifier wants the prover to open all the boxes for all the gates in the circuit and also all the envelopes for the input keys. On the other hand, if the prover does that, the verifier will immediately know the prover's input since he will know which of the prover's input corresponds to which key.

The solution is as follows:

  1. The prover creates two copies of the garbled circuit, each with its unique set of keys.
  2. The prover puts both in public.
  3. The verifier chooses a random one to be opened by the prover.
  4. The prover has to open all the boxes and all the envelopes of the circuit copy chosen by the verifier.
  5. The verifier then evaluates the other copy with the keys provided by the prover and checks if it returns 1. [Note that the verifier does not have any secrets, so he can do the verification publicly and the prover also can make sure that the evaluation is correctly done by the verifier.]

Since each of the copies has a probability of 0.5 of being chosen to be opened, if the prover creates at least one of the garbled circuits incorrectly, he has a probability of 0.5 of being caught and losing his reputation. But what if that is not enough of a guarantee? What if we want almost a certainty of a dishonest prover being caught? Here is what we can do:

  1. The prover creates 256 copies of the garbled circuit, each with its unique set of keys.
  2. The prover puts all of them in public.
  3. The verifier chooses a random 128 of them to be opened by the prover.
  4. The prover has to open all the boxes and all the envelopes of the copies chosen by the verifier.
  5. The verifier then evaluates all the remaining copies with the keys provided by the prover and checks if all of them return 1.

Now, if any of the copies executed by the verifier is a correct circuit, the prover must provide the keys corresponding to the correct witness. Hence, if the prover does not have the factorization, the prover must make at least 128 copies incorrectly to have any chance of convincing the verifier. But, in that case, the prover will be caught unless the verifier chooses the correct ones to open. The number of ways the prover can choose 128 copies out of 250 is \(\begin{pmatrix} 256 \\ 128 \end{pmatrix}\). Only one of them would convince the verifier without the prover getting caught. The probability of that is \(1/ \begin{pmatrix} 256\\ 128 \end{pmatrix} <10^{-75}\). So, the dishonest prover will almost certainly be caught. So, we have a zero-knowledge proof system for proving any secret knowledge that satisfies a given condition.

More Than a Zero-knowledge Proof

The above technique provides a way to prove the knowledge of any secret satisfying any condition in zero-knowledge. However, the proof is very large in the amount of communication that is needed and also in the amount of computation that the verifier needs to do. Modern zero-knowledge proof systems let you create very short proofs that can be verified with a very small amount of computation.

These techniques require the knowledge of finite fields, which are finite sets that allow addition, subtraction, multiplication, and division among the set elements; so I will not cover them here but the interested reader can learn more here.

In this article, we have introduced a simple way to achieve a zero-knowledge proof for a general boolean circuit. It shows the reader that anything that can be proved without zero-knowledge can be proved in zero-knowledge, since any function can be expressed in terms of a boolean circuit and then we can create a zero-knowledge proof as shown in the article.

However, this method is quite expensive in terms of communication complexity. In practical systems, succinct zero-knowledge (SNARK) proofs are used instead.

About the Author

Rate this Article

Adoption
Style

BT