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.

You may notice that the colors change between different rounds of the game; although the prover is not allowed to change its mind once it offers you a choice, it's allowed to mix up the colorings between choices. Indeed, if it didn't, you could reverse engineer the full coloring (making this not a zero-knowledge proof.) 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 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 (the graph is not 3-colorable) but has managed to get lucky in the edges you picked 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?