NB: This isn’t about crypto. I don’t care about crypto. Chris messaged me the other week asking if I wanted to implement zero-knowledge proofs. I initially was not interested, but then he said: What if I told you there’s a version of them that has nothing to do with cryptocurrencies? What if I told you it involves graph theory? What if I told you there’s a 30 line implementation? Now that was interesting. The idea of a zero-knowledge proof (ZKP) is that there are two parties: the prover and the verifier. The prover asserts that it has a solution to a (generally NP-complete) problem. The prover can convince the verifier of this without sharing the actual solution to the problem. The canonical example is 3-coloring a graph. That is, the prover asserts that, for a given (shared) graph, it has a valid 3-coloring. It wants to convince the verifier of this without revealing the actual color assignment. As a quick recap, graph coloring is the problem where given a graph, we find a way to assign each node a color such that no two adjacent nodes have the same color. 3-coloring is coloring with at most 3 colors. How do you do this? Assorted blog posts and fancy-looking demonstrations were interesting but did not help us understand much. Chris and I went around in circles for a bit until we decided to take a look at one of the original papers (PDF) by Goldreich, Micali, and Widgerson. We only really read page 23 (labeled page 713 in the PDF) but that was enough to get things going. Protocol 4 from the paper describes an interactive 3-color proof session between the prover (P, with numbered steps) and the verifier (V, with numbered steps), reproduced here: common input A graph G(V, E) (n = |V|, m = |E|). The following four steps are executed m² times, each time using independent coin tosses. (P1) The prover chooses at random an assignment of three colors to the three independent sets induced by φ, colors the graph using this 3-coloring, and places these colors in n...