Three ZK Examples
Three ZK Examples
Graph 3-colouring
Details can be seen in the following two great lecture notes, which I have attached here. cornell_lecture18 more easier to understand cmu_lecture23 more formal There is a visual demonstration for Graph 3-coloring from MIT, Interactive zero knowledge 3-colorability demonstration.
The concept of simulator can be seen in note [4.simulator.md]
Some points should be highlight to understand the above materials better and deeper.
There are some common knowledge for the prover and verifers about 3-colorable graphs. The graph, three colors used, and the principles of the ZK-Graph 3-coloring protocol is known for both prover and the verifers. Therefore, the brute force from malicious verifier about the graph is nearly impossible. The reason is that the prover randomly permutes the colors in each round, and the color of a particular edge may be different in different rounds. The randomness make the brute force nearly impossible.
The verifier can only tell that the prover has at least one true witness, not whether it has a different true witness than it uses.
The answer of the two exercises from the visual demonstration of MIT.
Exercise 1: Currently, you can only select adjacent pairs of nodes to check. Would the proof still be zero knowledge if you could pick arbitrary pairs of nodes to check?
No. Why is this a zero-knowledge proof currently? the reason is that the verifier already knows the property that no two vertices of the same color are connected by an edge. If the verifier wants, it could also generate the same graph with the specific edge it just verified using two vertices of different colors. So in some sense, the information the prover give the verifier doesn't tell the verifier anything that it didn't already know.
The idea/intuition definition of zero-knowledge (Just three different ways of expressing the same thing)
- A proof system is zero knowledge if the verifier did not learn anything after the interaction that he could not have learned on his own.
- the proof should reveal nothing to the verifier beyond what the verifier already knows.
- Proof pi reveals nothing about the secret witness, other than its existence.
When you can only select adjacent pairs of nodes to check, you just get information about the (specific) adjacent pairs of nodes that are colored differently. This kind of information is what the verifier already knows, making it not knowledge for the verifier, because it can help nothing about the prover solving the 3-coloring problem. However, when the verifier can choose any pair of nodes to check, the verifier can gain some additional knowledge because it starts to know which two are the same color and which two are different colors. As the number of verifications increases, the accumulated knowledge may lead to the leakage of secrets.
Exercise 2: The equation currently being used for confidence is 1-(1/E)^n, where E is the number of edges in the graph, and n is the number of trials run. Is this the correct equation? Why is there no prior?
No, For n-iteration, the confidence metric should be \(1-(1-1/|E|)^n\). The colored graph committed by a cheating prover has at least 1 edge whose two endpoints are colored with the same color. The verifier can catch him whenever happens to request the colors for this edge with probability 1/|E|. By performing n sequential repetitions of the protocol, we can get the soundness error down to \((1-1/|E|)^n\), which is negligible. Hence the confidence metric should be \(1-(1-1/|E|)^n\)
Why is there no prior?
The prover can randomly permutate the secret coloring in each round, which makes each trial or verification independent of the other.
Hamilton Cycles of Graph
Hamilton cycle: a cycle going through every vertex of the graph exactly once and return to the start.
Hamilton Cycles is a NP problem. If you know a zero-knowledge protocol for Hamilton Cycles, you can reduce all NP problem to use this protocol, which means you know a zero-knowledge protocol for all NP problem.
Graph Hamiltonicity is also covered in cornell_lecture18 more easier to understand.
P: know a hamilton cycle C on graph G. Each round:
- P: random permutation \(\phi\) over G
- P: commit two commitment: the permutation \(\phi\) and edges in \(\phi(G)\)
- V: The verifier flip coin to get a challenge bit b ∈ {0, 1}.
- if b=0, for permutated graph, P reveal the permutation \(\phi\) and \(C_{i,j}\) edges in \(\phi\) to V for isomorphic verification, checking whether the graph is isomorphic to the public graph G
- if b=1, for hamilton cycle, P translate the Hamiltonian cycle \(C_H\) onto \(\phi(G)\), and reveal the translated corresponding edges of hamiltonian cycle in \(\phi(G)\) to verifier. The verifier unveil the received edges and check if they are a Hamiltonian cycle on the permuted graph \(\phi(G)\).
Note: verifier can simulate a permutated graph or a hamilton cycle, but not both at the same time.
Hamiltonian Cycles Lecture 7: Zero Knowledge II
Q: Why verifier need to flip a coin? A: If the challenge preference is known by proof, which might be malicious, the prover can forge the must-chosen one arbitrarily without caring about the other one, which make the proof invalid.
Q: One issuse is this protocol requires interaction. The interactive proof is non-practical for real-world application,such as blockchain, How about non-interactive proof? A: Fiat-Shamir heuristic: a way to turn interative proo to non-interactive proof and still maintain good properties.
The prover try to simulate the verifier by help the verifier pick the randomness. The prover is protentially malicious, and if it know in advance what coins the verifier will flip, it can do bad things. To make non-interactive proof, you need to make sure the prover cannot simulate the coin to its advantage.
Fiat-Shamir heuristic: The prover can simulate the verifier by running a cryptographic hash function on the transcript to generate the randomness, so P cannot cheating by adversarily choosing favorable so-call random but random challenge. You force it to flip a coins by applying a cryptographic hash function to everything that has happened in this interaction.
Q: Another issuse is the proof is so big. How to make it succinct? A:
