What Is A Zero-Knowledge Proof? [part 1] | by Niusha | The Capital | Oct, 2022

Zero-Knowledge Proof is a magical way to prove a statement without revealing extra information. Here, we provide a beginner intro to ZKPs…

You are playing “Where’s Waldo?” with your friends. The first one to find him wins the gold cup, and the second one gets the silver cup. You are the first one to find him, but, you can’t tell your friends where he is. Because you will ruin the chance for everyone else to win the second-place prize. What can you do? How can you prove to your friends you have actually found Waldo without revealing where exactly is he? Is there even a solution for that?

Fortunately, the answer is yes! Here is the solution: get a very big board (way bigger than the page where you had to find Waldo on it) with a small hole on it (as large as it fits Waldo). Go behind the board while everyone else is standing in front of it. Put the page behind the board so that no one knows where exactly you have put it. Justify the page in a way that Waldo can be seen from the hole on the board. Now, everyone can see you have found him! But they still have no idea where is it on the page, since they don’t know the position of the page behind the board. Cool! Right?

We call this a zero-knowledge proof (ZKP). A proof that shows you are honest, but gives no knowledge to the verifier about the secrets that you are hiding. Seems counterintuitive, I know! Let’s formulate the problem to understand it better. We have a prover that wants to prove his honesty in doing something. It can be telling the truth about finding Waldo or solving any other problem that we are trying to solve. On the other hand, he doesn’t want to reveal anything about the solution. We want a scheme using which the prover is enabled to prove his honesty to the verifier. The verifier should be able to verify the proof much faster than it takes to find the solution himself.

Other Examples

Suppose you have enough money to buy a car, but the dealer won’t trust you. You don’t want to reveal the amount of your income or savings to them. But you really want the car. A zero-knowledge proof can be used to prove to the dealer you have enough assets to pay him without sacrificing your privacy. Here, ZKP is used to add privacy.

Now let’s get into a more practical example. We have a huge computation problem that will take days to solve it using our personal computers and laptops. Also, we have access to a center that provides cloud services that can solve our problem in a couple of hours. We want to use their service, but how can we make sure they don’t send us a fake answer? If we want to validate their answer by simply computing the solution, it again takes days to do so. Then, why even bother to go with them in the first place? We need a proof along with the computation answer that can be verified efficiently. Much faster than the solution and the proof themselves. If we have such a mechanism that provides a proof that the whole computation is done correctly, then, we can use this center’s services without the need to trust them. Here, ZKP is used to add efficiency and scalability to our system.

Wait, what?

Basically, when we want to prove a statement, usually, we give way more information to the verifier than we need to. Let’s say we want to prove a three-coloring exists for a graph. Three-coloring is a famous problem for graphs that asks for coloring a graph’s vertices with at most three colors, in such a way that there exists no edge with the same colorings on its two ends.

Here is an example of a three-coloring for a graph:

To prove we know a coloring exists for a specific graph, we usually color the graph with the correct solution and show it to the verifier. Now, the verifier knows that the coloring actually exists, but, he also knows the coloring itself for every vertex of the graph. The information that the verifier needed was a single “yes” or “no” as the answer to the question “whether this graph has a three-coloring or not?”. Which is way less information than what we gave him as a proof. So, the proving system should be optimized. The analysis of such proof systems, and the information relayed in the process of proving, is done in 1985 [4] by Goldwasser, Micali, and Rackoff [1]. They defined something called zero-knowledge proofs in which no extra information is relayed while proving a statement.

Sometimes the proofs are not deterministic unlike the case of Waldo. There might be probabilistic proofs that let the verifier make sure of the honesty of the prover with an overwhelming probability (with the probability 1-e where e can be arbitrarily small). Let’s dive into the three-coloring example to understand it better.

A prover has a solution to a graph three-coloring and wants to prove that to a verifier, but he doesn’t want to reveal the solution. What can he do? Let us solve it step by step. If the prover is not honest (i.e. does not have a correct three-coloring), then, there exists an edge with the same colors on both ends of it. Suppose that the verifier randomly chooses an edge and asks the prover to reveal its colorings. If the edge contains different colors on its ends, the verifier will get a tiny bit convinced that the prover has the correct solution. To get more convinced, the verifier can keep asking the prover to reveal more and more edges. However, this way the verifier is learning the coloring edge by edge which is not desirable. To solve that, we ask the prover to switch the colors randomly between two rounds of revealing.

Problem solved! Now, the verifier cannot learn anything about the coloring (because changing the colors in each round, prevents the verifier from relating the colorings that he sees each time to the previous tries), but gets convinced that the prover is honest with an overwhelming probability. The verifier can increase the number of reveals to achieve the desirable probability he wants to know the prover is honest. The number of reveals needed to achieve high probabilities of certainty is relatively low, therefore, the proof system is efficient.

Conclusion

So far, I introduced zero-knowledge proofs and tried to convince you that they actually exist, by showing you some examples. I also discussed some of its applications.

Moreover, one of the main use cases of zero-knowledge proofs is in blockchains and cryptocurrencies. They can be used to help the scalability of blockchains (by offloading some portion of the on-chain computation to off-chain) or achieve higher levels of privacy.

If you feel interested or want to learn more, you can read the next part of this series of posts on ZKP.

Part 2 is coming soon…

References

[1] The Knowledge Complexity of Interactive Proof Systems: https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf

[2] Vitalik Buterin notes on Zero knowledge: https://vitalik.ca/general/2017/11/09/starks_part_1.html

[3] https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

[4] https://en.wikipedia.org/wiki/Interactive_proof_system