Zero-knowledge proofs, explained

ZK-proofs allow a prover to persuade a verifier of a statement’s veracity without disclosing any information about the assertion itself. The prover and verifier interact in multiple rounds of the protocol, and in the conclusion, the verifier develops confidence in the veracity of the claim without learning any additional information about the secret.

Let’s use the “Three Color Problem,” also known as the “Graph Coloring Problem,” as an illustration of how ZK-proofs function.

The problem

Imagine that you have a map with multiple areas (vertices) connected by lines (edges), and this is the issue. The goal is to use one of three colors to color each region so that no two neighboring parts have the same color. Can you persuade someone that you are aware of the correct coloring without exposing the actual hues given to each region?

Solution using the ZK-proofs protocol

Setup

The prover and the verifier both agree on the regions and links of the graph (map).

Statement

The prover asserts to have a reliable three-coloring for the provided graph.

Round 1: Commitment

The prover chooses colors at random for each location in secret without disclosing them. Instead, the prover provides the verifier with one encrypted promise for each region. The verifier cannot see what colors are inside the commitments because they are locked like boxes.

Round 2: Challenge 

The verifier chooses a random region and requests that the prover open the commitment for that particular zone. The prover must disclose the hue of that area’s commitment.

Round 3: Response

After committing to the colors, the prover must now prove that the revealed coloring is accurate. This entails displaying the color differences between adjacent sections. The verifier examines the response to ensure that the prover correctly followed the rules.

Iteration

Rounds 2 and 3 are repeated numerous times using various regions that are chosen at random. This procedure is repeated as many times as necessary to establish a high degree of trust in the veracity of the prover’s assertion.

Conclusion

The verifier becomes confident that the prover actually has a valid three-coloring without knowing the actual colors used if the prover regularly produces valid responses for each round.

The verifier gradually increases the prover’s capacity to recognize a valid three-coloring of the graph by repeating the procedure for various regions. However, the zero-knowledge…