A quick look at zero-knowledge proofs | Max Bernstein
home<br>blog<br>microblog<br>favorites<br>pl resources<br>bread<br>recipes<br>rss
A quick look at zero-knowledge proofs
August 7, 2026
With co-author Chris Gregory!
NB: This isn’t about crypto. I don’t care about crypto.
Chris messaged me the other week asking<br>if I wanted to implement zero-knowledge proofs. I initially was not interested,<br>but then he said:
What if I told you there’s a version of them that has nothing to do with<br>cryptocurrencies? What if I told you it involves graph theory? What if I told<br>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<br>prover and the verifier. The prover asserts that it has a solution to a<br>(generally NP-complete) problem. The prover can convince the verifier of this<br>without sharing the actual solution to the problem.
The canonical example is 3-coloring a graph. That is, the prover asserts that,<br>for a given (shared) graph, it has a valid 3-coloring. It wants to convince the<br>verifier of this without revealing the actual color assignment.
As a quick recap, graph coloring is the problem where given a graph,<br>we find a way to assign each node a color such that no two adjacent nodes<br>have the same color. 3-coloring is coloring with at most 3 colors.
%0
0--1
0--2
1--2
2--3
3--4
4--0
%0
0--1
0--2
1--2
2--3
3--4
4--0
How do you do this? Assorted blog posts and fancy-looking demonstrations were<br>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<br>one of the original papers<br>(PDF) by Goldreich, Micali, and Widgerson. We only really read page 23 (labeled<br>page 713 in the PDF) but that was enough to get things going.
The paper’s protocol
Protocol 4 from the paper describes an interactive 3-color proof session<br>between the prover (P, with numbered steps) and the verifier (V, with numbered<br>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<br>coin tosses.
(P1) The prover chooses at random an assignment of three colors to the<br>three independent sets induced by φ, colors the graph using this 3-coloring,<br>and places these colors in n locked boxes each bearing the number of the<br>corresponding vertex. More specifically, the prover chooses a permutation<br>π ∈R S₃, places π(φ(i)) in a box marked i (∀ i ∈ V), locks all boxes<br>and sends them (without the keys) to the verifier.
(V1) The verifier chooses at random an edge e ∈R E and sends it to the<br>prover. (Intuitively, the verifier asks to examine the colors of the endpoints<br>of e ∈ E.)
(P2) If e = (u, v) ∈ E, then the prover reveals the colors of u and<br>v by sending the verifier the keys to boxes u and v. Otherwise, the<br>prover does nothing.
(V2) The verifier opens boxes u and v using the keys received and<br>checks whether they contain two different elements of {1, 2, 3}. If the keys<br>do not match the boxes, or the contents violate the condition then the<br>verifier rejects and stops. Otherwise, the verifier continues to the next<br>iteration.
If the verifier has completed all m² iterations then it accepts.
We’ll come back to the number of iterations. For now let’s try to just do one<br>iteration. For each step, I’ll annotate the code with “Only prover” or “Only<br>verifier” so that it’s clear who can see what data.
One iteration
We’ll start by sketching out what it means to have a graph. For the example<br>graphviz graph above, we have the following edge list data structure:
# Shared between prover, verifier<br>edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)]
Each tuple in the list represents a connection between two numbered nodes.<br>Fancy stuff. Because it’s an undirected graph, (0, 1) means the same as (1,<br>0) so we don’t have to include both. We can also color it:
# Only prover<br>coloring = {0: "navy", 1: "darkgreen", 2: "crimson", 3: "navy", 4: "darkgreen"}
Each key is a node number and each value is a color.
Though finding a 3-coloring of a graph is slow, verifying one is fast—linear<br>in the number of edges. Let’s verify that we have a valid sample coloring:
# For the reader<br># Check each edge to make sure no edge has the same color on each node<br>assert all(coloring[u] != coloring[v] for u, v in edges)<br># Check that the total number of colors used is 3<br>assert len(set(coloring.values())) 3
We’ll now go through the paper’s steps one by one, writing some code to<br>accompany each step.
Tips and tricks
If you are building alongside the blog post, I recommend using random.seed(0)<br>so your randomness doesn’t change between runs of your program. I also<br>recommend setting the environment variable PYTHONHASHSEED to 0 if you are<br>using hash for the same stability reasons.
Step P1
The first thing we need to do is permute the coloring we have. That is, we<br>should swap around the color values while maintaining the 3-color property.
Thankfully, this is...