Interactive zero knowledge 3-colorability demonstration

This is an interactive demonstration of the zero knowledge proof protocol for 3-colorable graphs. Zero-knowledge proofs permit you to convince a verifier of the truth of a fact (namely, that a graph is three colorable), without revealing the actual three coloring of the graph.

This application allows you to play the game as a verifier. The application (the prover) offers you a graph whose colorings are obscured from you, and you are allowed to pick an edge, which the verifier will reveal the coloring of. Select a graph and try clicking on some edges.

Pick a graph
Confidence: 0%

You may notice that the colors change between different rounds of the game; this ensures that you never learn anything about the graph, but also raises the question whether or not the prover is just outright cheating. An important property of this protocol is that once you see the graph, all of the colors are predetermined. While the prover is allowed to mix up the colors in between rounds of the protocol, once it has presented you with a graph, it's not allowed to change any of its choices. If the verifier is lying (the graph is not 3-colorable), then if you pick the uncolorable edge, the verifier has to fess up and admit they were lying.

In practice, such a guarantee would be made with a commitment scheme, but for this demo, you can check that the application is not reneging on its promises by pressing the Reveal button. (Since this tells you what the true coloring is, this button is obviously not part of the zero-knowledge protocol!)

Once you get tired of clicking edges manually, you can select Turbo to speed things up. As you play more rounds of the protocol, the probability that the prover is lying but has managed to get lucky and avoid getting exposed goes down: this is reflected in the confidence metric.

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?

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?

Liked this? Check out my blog!