Zero-Knowledge Proof Reconstruction for Graph 3-colorability

Zero-Knowledge Proof Reconstruction for Graph 3-colorability

GitHub Repository

I have included an in-depth description and explanation of the application here: Zero-Knowledge Proof Reconstruction for Graph 3-Colourability

The concept of a zero-knowledge proof consists of a prover attempting to convince the verifier that they possess certain information, or that the information they possess meets certain standards, without revealing anything about said information.

In the following interplay the application is the prover and you, esteemed audience, are the verifier. The application will attempt to convince you that it possesses a valid 3-color scheme for either following graph.

Press any edge

Confidence: 0%

Tries: 0

There are a few steps to remember in order to conceptualize the proof.

Prover: Shuffles the graph coloring (changing the coloring scheme or choosing a different coloring permutation).
Prover: Assigns and commits to each node the appropriate color. Once it is committed, it's impossible to tamper with the chosen coloring.
Prover: Presents the verifier with the graph.
Verifier: Chooses an edge at random.
Prover: Reveals the coloring of the two end-point nodes for the chosen edge in front of the verifier.
Verifier: If the colors of the two nodes are the same, then the verifier is 100% certain that the prover does not possess a valid 3-color scheme for the subject graph and the proving process is over.
If the colors of the two nodes are different, however, the verifier is a little more certain that the prover has a valid 3-color scheme for the subject graph. (The certainty in the prover at each repetition of these steps is represented using the Confidence value at the top of the graph). The verifier can continue participating in more repetitions of this process until they are sufficiently confident that the prover has a valid 3-color scheme.

In this way the verifier will never be able to figure out the colorings that the prover possesses while being able to achieve an infinitely high level of confidence in the prover's claims.
This proof hinges on the idea that the more repetitions happen without finding similarly colored nodes, the less likely it is to eventually find two nodes of the same color (which would invalidate the proof). So the higher the confidence rises, the more willing the verifier is to bet on the assumption that the prover is honest.

I got to know about zero-knowledge proofs through their use in zk-rollups to increase blockchain scalability, but since then I've come to like them as close friends and highly trusted confidants.

I used these course notes to guide my logic and Edward Z. Yang's demo to help me visualize what the application could look like. And last but not least an honourable mention to a few trusty StackOverflow posts.