GoKawiilWith co-author Chris Gregory!
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.
%0 0 0 1 1 0--1 2 2 0--2 1--2 3 3 2--3 4 4 3--4 4--0
%0 0 0 1 1 0--1 2 2 0--2 1--2 3 3 2--3 4 4 3--4 4--0
... continue reading