Before starting, 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.
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 appears at 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 computer
Now, we will introduce a game to help you understand some computer algorithms that are applied to make ZKP possible. This game was named Color 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: White map
There’re a lot of solutions for this game but let’s choose only one for example:
Figure 5: One 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, then 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: Replace colors by numbers
Figure 7: Result after covering the values
Covering the 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 easily 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 are 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 simple that we will use Hash function. Here, we won’t mention about 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 the naive way and see what restrictions we will meet, as well as what is the right solution.
Build scheme by 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 send to Victor
Victor requests Peggy to reveal 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 and 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 proof to make a conclusion about Peggy.
Figure 10: Victor recieves two values as he want from Peggy and then check with the rules.
Here, hash function’s role is to protect and hide values at all points, keeping Victor from finding them. But Victor has an attack plan 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 if assumes that A = 1, B = 2, C = 1, D = 2, the other parts can easily be inferred to have value 3. As the result, Victor gets a new solution of original game which is completely right.
(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. You could check that easily by yourself).
Figure 11: Victor uses information sent by Peggy to find out a new solution
Build scheme by a right way
To solve problems of the method above, Peggy adds an extra secret number every times calculating hash value and keeps secret about this until Victor 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 others 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 and verify.
Table 2: Probability of detecting Peggy’s fraud in case she is cheating.
Part One has introduced you some basic information about Zero-knowledge proof. We will continue to go deeper in this technique in the next article. Please look forwards to it. Thanks for reading.
＊＊Consutant: Nguyen The Luan