A quick look at zero-knowledge proofs

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…