Self-Study | zkSNARKs in first views.

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.

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.

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.

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.

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.

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.

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.