FB Pixel

Part 1. The ideas behind zkSNARKs: Zero-knowledge proof

To start on journey, we need to clear a confusion that a lot of people still make about Zero-knowledge proof (ZKP) and zkSNARKs. They have connections, but are different definitions.

ZKP is a method or protocol by which one party (Prover) can prove to another party (Verifier) about a true statement without revealing the statement’s value. As for zkSNARKs, zkSNARKs is a scheme running on the idea of ZKP and used on Ethereum network and some other cryptocurrency systems.

Zero-knowledge proof with a story for children

There is a typical story used to show the fundamental ideas about ZKP called “Ali Baba Cave”. In this story, Peggy wants to show Victor that she knows about the incantation to open the magic door without revealing it to Victor.

Fortunately, with the special structure of Ali Baba Cave, Peggy can convince Victor by using the following scheme. Firstly, Peggy picks a way randomly to get into the cave and requests Victor to pick a way that he wants Peggy to appear. Then Victor comes to the entrance and waits for Peggy appear at the way he requested.

If Peggy turns up at the right place, it proves that she knows the incantation. By doing this repeatedly, Victor’s trust on Peggy will grow, in condition she makes no fail at all. If Peggy does incorrectly, even just one time, she will be labeled as a liar right away.

Figure 1: Peggy randomly goes in way A or B.

Figure 2: Victor chooses the way that Victor wants Peggy to appear.
Figure 3: Peggy turns up in the right way Victor chose.

Suppose Peggy does not know about the incantation and is standing at A. In case Victor wants to see Peggy at B, certainly there’s no way for Peggy to come to B and Victor will know instantly that Peggy is the liar. On the other hand, if Victor wants to see Peggy at A, Peggy could still trick that she knows about the incantation, just purely on luck.

But Peggy’s luck will run out by time, or you could say the chances of Victor detecting Peggy’s fraud will increase, if Victor and Peggy keep doing this scheme repeatedly. We can prove it by some simple equations.

Call the probability of Peggy detected at a trial is p=0.5, the number of trials is n and the probability of Peggy detected at n trials is pn. We will have this:

Table 1: Probability of detecting Peggy’s fraud is proportional to the number of trial and will reach nearly 100% after 100 trials.

Zero-knowledge proof with a game for computers

Now, we will introduce a game to help you to understand some computer algorithms that are applied to make ZKP possible. This game was named Colour Map with the following rules:

There is a white map. Two points are called a neighbor of each other if they are connected directly by a line. Our mission is to apply one of three colors as red, yellow, green to all points so that no point has the same color as it’s neighbors.

Figure 4: The white map
There’re a lot of solutions for this game but let’s choose one of them for example:
Figure 5: A solution of the game

This is a solution that Peggy (Prover) found. Peggy wants to prove to Victor that she already had a solution without revealing the true statement. To do it, Peggy replaces all colors by numbers and covers all of them. Only Peggy owns the privilege of uncovering those values. Then Peggy sends the result to Victor along with the new states which are 1, 2, 3 instead of red, yellow, green for verifying.

Figure 6: Replacing colors by numbers

Figure 7: Result after covering the values

Covering those values restricts Victor from collecting any information about the right solution and the possibilities of him recreating any other right solution. Let’s imagine what would happen if Peggy just sends the result at Figure 6? Victor could find a new solution just by replacing the original colors to the values of new states.

Verification phase will be implemented by Victor who requests Peggy to reveal two random neighbors and then check whether the revealed values are true to the rules or not. If it’s correct, Victor may believe Peggy. If it’s incorrect, Victor can make a conclusion that Peggy is cheating on him. This process will be repeated, and in every verification phase, Peggy will try to change the new states before resending to Victor.

Figure 8: Peggy reveals the values of two neighbors which Victor chose, Victor verifies whether the revealed values are true to the rules or not.

So, how can we implement it by programming? The answer is simply that we will use Hash function. Here, we won’t mention about the definition and attributes of Hash function. If you have never heard about it, please consult here.

Before getting to how to apply Hash function properly, we will try to brainstorm and apply Hash function to scheme in a naive way and see what restrictions we will meet, as well as what is the right solution.

Building a scheme in a naive way

Peggy replaces the colors of red, yellow, green by numeric values 1, 2, 3 and calculates hash value of each pair of neighbors. Then Peggy notifies Victor about new states are 1, 2, 3 and sends him the map of hash values.

Figure 9: Map of Hash values Peggy sent to Victor

Victor requests Peggy to reveal the value of a random pair of neighbors Victor wants. Peggy looks into her map of solution and responses, assuming value of that points are 1 and 2. Victor receives 1 and 2, then verifies them with the rules to see whether hash value of 1 and 2 is equal to 7f8b6 or not. Just like that, Victor iterates many times with many different states until having enough proofs to make a conclusion about Peggy.
Figure 10: Victor receives two values as he want from Peggy and then checks with the rules.

Here, hash function’s role is to protect and hide values at all points, keep Victor from finding them. However, Victor has an attack vector to find out a new right solution basing on the information that Peggy had sent. Victor realizes that values of hash function as AB, BC, CD are the same value so Victor can assume A = 1, B = 2, C = 1, D = 2, the other parts can be easily inferred to value 3. According to the process, Victor gains a new solution of the original game which completely valid.

We will not mention an attack vector which tries to brute force all possible hash values from the states 1, 2, 3. In case the number of states is massive, it’s almost impossible to find exactly Peggy’s solution with this attack vector. Covince yourself.

Figure 11: Victor uses information sent by Peggy to find out a new solution.

Building scheme by the right way

To solve problems of the method above, Peggy supplements an extra secret number every time calculating hash value and keeps secret about this until Victor’s requests. Victor has to verify by requesting Peggy to sent values at neighbors as well as the corresponding secret number. This secret number will help Peggy to keep every hash values different from each other and disable Victor’s attack vectors.

Figure 12: Peggy adds extra secret numbers every times calculating hash value.

Figure 13: Peggy sends values and the corresponding secret number as Victor’s request, Victor will calculate hash(1, 2, 10) ?= dda0f.

Table 2: Probability of detecting Peggy’s fraud in case she is cheating.

Conclusion & References

I’m a big fan of Ethereum and this is my first article about it. I certainly know it will have some mistakes so for sure that I’m pleased to get some comments from you. Try to get me down 🙂 Peace!!!