{"id":23317,"date":"2026-08-07T00:00:00","date_gmt":"2026-08-07T00:00:00","guid":{"rendered":"https:\/\/scannn.com\/a-quick-look-at-zero-knowledge-proofs\/"},"modified":"2026-08-07T00:00:00","modified_gmt":"2026-08-07T00:00:00","slug":"a-quick-look-at-zero-knowledge-proofs","status":"publish","type":"post","link":"https:\/\/scannn.com\/lv\/a-quick-look-at-zero-knowledge-proofs\/","title":{"rendered":"A quick look at zero-knowledge proofs"},"content":{"rendered":"\n
\n

NB: This isn\u2019t about crypto. I don\u2019t care about crypto.<\/em><\/p>\n

Chris<\/a> messaged me the other week asking
\nif I wanted to implement zero-knowledge proofs. I initially was not interested,
\nbut then he said:<\/p>\n

\n

What if I told you there\u2019s a version of them that has nothing to do with
\ncryptocurrencies? What if I told you it involves graph theory? What if I told
\nyou there\u2019s a 30 line implementation?<\/p>\n<\/blockquote>\n

Now that<\/em> was interesting.<\/p>\n

The idea of a zero-knowledge proof (ZKP) is that there are two parties: the
\nprover and the verifier. The prover asserts that it has a solution to a
\n(generally NP-complete) problem. The prover can convince the verifier of this
\nwithout sharing the actual solution to the problem.<\/p>\n

The canonical example is 3-coloring a graph. That is, the prover asserts that,
\nfor a given (shared) graph, it has a valid 3-coloring. It wants to convince the
\nverifier of this without revealing the actual color assignment.<\/p>\n

\n

As a quick recap, graph coloring is the problem where given a graph,
\nwe find a way to assign each node a color such that no two adjacent nodes
\nhave the same color. 3-coloring is coloring with at most 3 colors.<\/p>\n<\/blockquote>\n

<\/p>\n

<\/p>\n

How do you do this? Assorted blog posts and fancy-looking demonstrations were
\ninteresting but did not help us understand much.<\/p>\n

Chris and I went around in circles for a bit until we decided to take a look at
\none of the original papers<\/a>
\n(PDF) by Goldreich, Micali, and Widgerson. We only really read page 23 (labeled
\npage 713 in the PDF) but that was enough to get things going.<\/p>\n

The paper\u2019s protocol<\/h2>\n

Protocol 4 from the paper describes an interactive 3-color proof session
\nbetween the prover (P, with numbered steps) and the verifier (V, with numbered
\nsteps), reproduced here:<\/p>\n

\n

common input<\/em> A graph G(V, E)<\/code> (n = |V|<\/code>, m = |E|<\/code>).<\/p>\n

The following four steps are executed m\u00b2<\/code> times, each time using independent
\ncoin tosses.<\/p>\n

(P1) The prover chooses at random an assignment of three colors to the
\nthree independent sets induced by \u03c6<\/code>, colors the graph using this 3-coloring,
\nand places these colors in n<\/code> locked boxes each bearing the number of the
\ncorresponding vertex. More specifically, the prover chooses a permutation
\n\u03c0 \u2208R S\u2083<\/code>, places \u03c0(\u03c6(i))<\/code> in a box marked i<\/code> (\u2200 i \u2208 V<\/code>), locks all boxes
\nand sends them (without the keys) to the verifier.<\/p>\n

(V1) The verifier chooses at random an edge e \u2208R E<\/code> and sends it to the
\nprover. (Intuitively, the verifier asks to examine the colors of the endpoints
\nof e \u2208 E<\/code>.)<\/p>\n

(P2) If e = (u, v) \u2208 E<\/code>, then the prover reveals the colors of u<\/code> and
\nv<\/code> by sending the verifier the keys to boxes u<\/code> and v<\/code>. Otherwise, the
\nprover does nothing.<\/p>\n

(V2) The verifier opens boxes u<\/code> and v<\/code> using the keys received and
\nchecks whether they contain two different elements of {1, 2, 3}<\/code>. If the keys
\ndo not match the boxes, or the contents violate the condition then the
\nverifier rejects<\/em> and stops. Otherwise, the verifier continues to the next
\niteration.<\/p>\n

If the verifier has completed all m\u00b2<\/code> iterations then it accepts<\/em>.<\/p>\n<\/blockquote>\n

We\u2019ll come back to the number of iterations. For now let\u2019s try to just do one<\/em>
\niteration. For each step, I\u2019ll annotate the code with \u201cOnly prover\u201d or \u201cOnly
\nverifier\u201d so that it\u2019s clear who can see what data.<\/p>\n

One iteration<\/h2>\n

We\u2019ll start by sketching out what it means to have a graph. For the example
\ngraphviz graph above, we have the following edge list data structure:<\/p>\n

\n
\n
# Shared between prover, verifier\n<\/span>edges<\/span> =<\/span> [(<\/span>0<\/span>,<\/span> 1<\/span>),<\/span> (<\/span>1<\/span>,<\/span> 2<\/span>),<\/span> (<\/span>2<\/span>,<\/span> 3<\/span>),<\/span> (<\/span>3<\/span>,<\/span> 4<\/span>),<\/span> (<\/span>4<\/span>,<\/span> 0<\/span>),<\/span> (<\/span>0<\/span>,<\/span> 2<\/span>)]<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
Each tuple in the list represents a connection between two numbered nodes.
\nFancy stuff. Because it\u2019s an undirected graph, (0, 1)<\/code> means the same as (1,
\n0)<\/code> so we don\u2019t have to include both. We can also color it:<\/p>\n
\n
\n
# Only prover\n<\/span>coloring<\/span> =<\/span> {<\/span>0<\/span>:<\/span> \"navy\"<\/span>,<\/span> 1<\/span>:<\/span> \"darkgreen\"<\/span>,<\/span> 2<\/span>:<\/span> \"crimson\"<\/span>,<\/span> 3<\/span>:<\/span> \"navy\"<\/span>,<\/span> 4<\/span>:<\/span> \"darkgreen\"<\/span>}<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
Each key is a node number and each value is a color.<\/p>\n
Though finding a 3-coloring of a graph is slow, verifying one is fast\u2014linear
\nin the number of edges. Let\u2019s verify that we have a valid sample coloring:<\/p>\n
\n
\n
# For the reader\n# Check each edge to make sure no edge has the same color on each node\n<\/span>assert<\/span> all<\/span>(<\/span>coloring<\/span>[<\/span>u<\/span>]<\/span> !=<\/span> coloring<\/span>[<\/span>v<\/span>]<\/span> for<\/span> u<\/span>,<\/span> v<\/span> in<\/span> edges<\/span>)<\/span>\n# Check that the total number of colors used is 3\n<\/span>assert<\/span> len<\/span>(<\/span>set<\/span>(<\/span>coloring<\/span>.<\/span>values<\/span>()))<\/span> <=<\/span> 3<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
We\u2019ll now go through the paper\u2019s steps one by one, writing some code to
\naccompany each step.<\/p>\n
Tips and tricks<\/h3>\n
If you are building alongside the blog post, I recommend using random.seed(0)<\/code>
\nso your randomness doesn\u2019t change between runs of your program. I also
\nrecommend setting the environment variable PYTHONHASHSEED<\/code> to 0<\/code> if you are
\nusing hash<\/code> for the same stability reasons.<\/p>\n
Step P1<\/h3>\n
The first thing we need to do is permute the coloring we have. That is, we
\nshould swap around the color values while maintaining the 3-color property.<\/p>\n
Thankfully, this is easier than it might sound: the names of colors are
\nmeaningless to the 3-coloring; they need only be different along the edges. So
\nif we do a bijective (A maps to one B, and B came from one A) mapping from old
\nto new name, this will hold.<\/p>\n
I came up with this function that shuffles the colors, lines them up
\nside-by-side, makes a table, and then uses that to make a new coloring:<\/p>\n
\n
\n
import<\/span> random<\/span>\n\n# Only prover\n<\/span>def<\/span> permute_three_coloring<\/span>(<\/span>coloring<\/span>):<\/span>\n    all_colors<\/span> =<\/span> list<\/span>(<\/span>set<\/span>(<\/span>coloring<\/span>.<\/span>values<\/span>()))<\/span>\n    new_colors<\/span> =<\/span> random<\/span>.<\/span>sample<\/span>(<\/span>all_colors<\/span>,<\/span> len<\/span>(<\/span>all_colors<\/span>))<\/span>\n    permutation<\/span> =<\/span> {<\/span>old<\/span>:<\/span> new<\/span> for<\/span> old<\/span>,<\/span> new<\/span> in<\/span> zip<\/span>(<\/span>all_colors<\/span>,<\/span> new_colors<\/span>)}<\/span>\n    return<\/span> {<\/span>node<\/span>:<\/span> permutation<\/span>[<\/span>color<\/span>]<\/span> for<\/span> node<\/span>,<\/span> color<\/span> in<\/span> coloring<\/span>.<\/span>items<\/span>()}<\/span>\n# For example,\n# {0: \"crimson\", 1: \"navy\", 2: \"darkgreen\", 3: \"crimson\", 4: \"navy\"}\n<\/span><\/code><\/pre>\n<\/div>\n<\/div>\n
Then we have to place the colors in \u201clocked boxes\u201d. One way to proverbially
\nlock a box is to apply a one-way function to it: for example, a hash function.
\nIf we hash each color and then pass only the hashes to the verifier, the
\nverifier cannot open them.<\/p>\n
This example uses the Python standard library hash function for brevity but it
\nmight be better to use a cryptographic hash function like hashlib.sha256<\/code>:<\/p>\n
\n
\n
# Only prover. Wrong!\n<\/span>def<\/span> hash_coloring_wrong<\/span>(<\/span>coloring<\/span>):<\/span>\n    return<\/span> {<\/span>node<\/span>:<\/span> hash<\/span>(<\/span>color<\/span>)<\/span> for<\/span> node<\/span>,<\/span> color<\/span> in<\/span> coloring<\/span>.<\/span>items<\/span>()}<\/span>\n# For example:\n# {0: -6789624683659967261, 1: 7846608853949633950, 2: 6009240650600289446,\n#  3: -6789624683659967261, 4: 7846608853949633950}\n<\/span><\/code><\/pre>\n<\/div>\n<\/div>\n
There\u2019s just one problem with handing these locked boxes to the verifier: two
\nboxes locked with the same colors will have the same hashes. The verifier would
\nknow the coloring. Even if the exact colors are now hidden, it\u2019s really the
\nstructure of the coloring for which we want to give up zero knowledge.<\/p>\n
To get around this, we can add what\u2019s called a nonce<\/em> to each node and its
\ncoloring. That is, each node gets a little bit of random data packed into the
\nhash so that different nodes\u2019 \"darkgreen\"<\/code> hash values look different.<\/p>\n
\n
\n
# Only prover\n<\/span>def<\/span> nonce<\/span>():<\/span>\n    return<\/span> random<\/span>.<\/span>randrange<\/span>(<\/span>100<\/span>)<\/span>\n\ndef<\/span> box_coloring<\/span>(<\/span>coloring<\/span>):<\/span>\n    return<\/span> {<\/span>node<\/span>:<\/span> (<\/span>color<\/span>,<\/span> nonce<\/span>())<\/span> for<\/span> (<\/span>node<\/span>,<\/span> color<\/span>)<\/span> in<\/span> coloring<\/span>.<\/span>items<\/span>()}<\/span>\n\ndef<\/span> hash_values<\/span>(<\/span>coloring<\/span>):<\/span>\n    return<\/span> {<\/span>k<\/span>:<\/span> hash<\/span>(<\/span>v<\/span>)<\/span> for<\/span> (<\/span>k<\/span>,<\/span> v<\/span>)<\/span> in<\/span> coloring<\/span>.<\/span>items<\/span>()}<\/span>\n\npermuted_coloring<\/span> =<\/span> permute_three_coloring<\/span>(<\/span>coloring<\/span>)<\/span>\n# For example:\n# {0: \"crimson\", 1: \"navy\", 2: \"darkgreen\", 3: \"crimson\", 4: \"navy\"}\n<\/span>boxed_coloring<\/span> =<\/span> box_coloring<\/span>(<\/span>permuted_coloring<\/span>)<\/span>\n# For example:\n# {0: (\"crimson\", 33), 1: (\"navy\", 65), 2: (\"darkgreen\", 62),\n#  3: (\"crimson\", 51), 4: (\"navy\", 38)}\n<\/span>hashed_coloring<\/span> =<\/span> hash_values<\/span>(<\/span>boxed_coloring<\/span>)<\/span>\n# For example:\n# {0: -2275004828450249492, 1: 2227921633151400991, 2: -5024343381376265886,\n#  3: -5381005702768533635, 4: 1164729608819214729}\n<\/span><\/code><\/pre>\n<\/div>\n<\/div>\n
Again, you probably don\u2019t want to use the standard library random number
\ngenerator for your nonces. You should consider something like
\nsecrets.token_hex()<\/code> from the secrets<\/code> module (Python 3.6+). Maybe even
\nconsider using the hmac<\/code> module.<\/p>\n
Finally, we can send the hashed_coloring<\/code> to the verifier and begin step V1.<\/p>\n
Step V1<\/h3>\n
Since the verifier knows the graph (but not its colors), it can pick an
\narbitrary edge to inspect. It wants to verify that the arbitrary edge it picked
\nsatisfies the 3-color conditions. It sends off a request for an arbitrary edge
\ne<\/code>:<\/p>\n
\n
\n
# Only verifier\n<\/span>e<\/span> =<\/span> random<\/span>.<\/span>choice<\/span>(<\/span>edges<\/span>)<\/span>\nrevealed<\/span> =<\/span> prover_please_reveal_colors<\/span>(<\/span>e<\/span>)<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
This is implicitly relying on some global state (the prover knowing what
\n\u201csession\u201d is active with the verifier). If you have multiple verifiers or
\nconcurrent sessions or something, you may need to thread through some context
\nidentifier in the communication.<\/p>\n
Step P2<\/h3>\n
The prover, having received this request, sends over the colors and nonces for
\neach of the nodes in the edge.<\/p>\n
\n
\n
# Only prover\n<\/span>def<\/span> prover_please_reveal_colors<\/span>(<\/span>edge<\/span>):<\/span>\n    u<\/span>,<\/span> v<\/span> =<\/span> edge<\/span>\n    return<\/span> {<\/span>u<\/span>:<\/span> boxed_coloring<\/span>[<\/span>u<\/span>],<\/span> v<\/span>:<\/span> boxed_coloring<\/span>[<\/span>v<\/span>]}<\/span>\n# For example:\n# {3: ('crimson', 51), 4: ('navy', 38)}\n<\/span><\/code><\/pre>\n<\/div>\n<\/div>\n
You may be suspicious at this point because we\u2019re leaking some information
\nabout the coloring.<\/p>\n
Note that it\u2019s ok for the prover to reveal the color for one edge, because 1)
\nthe colors have been shuffled once per round and 2) we\u2019re going to apply our
\nbox locking protocol each time we reveal an edge<\/em> (also once per round), so
\nthe verifier accumulates no information about our colors between iterations.<\/p>\n
Step V2<\/h3>\n
The verifier can check that the color+nonce hashes to the hash value given for
\neach node in step P1. This ensures that the prover is not changing colors
\naround mid-round. This relies on the verifier and the prover using the same
\nhash function (and the same hash seed if using hash<\/code>).<\/p>\n
\n
\n
# Only verifier\n<\/span>for<\/span> (<\/span>node<\/span>,<\/span> (<\/span>color<\/span>,<\/span> nonce<\/span>))<\/span> in<\/span> revealed<\/span>.<\/span>items<\/span>():<\/span>\n    assert<\/span> hashed_coloring<\/span>[<\/span>node<\/span>]<\/span> ==<\/span> hash<\/span>((<\/span>color<\/span>,<\/span> nonce<\/span>)),<\/span> f<\/span>\"Hash mismatch!\"<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
The verifier can then inspect that the two color values are different. This
\ngives a small amount of credence (1\/|E|<\/code> because you know something about one
\nedge now) that the graph is 3-colored appropriately because the prover had no
\nway of knowing which edge the verifier would want to inspect.<\/p>\n
If either of these two conditions doesn\u2019t check out, the verifier rejects<\/em>.<\/p>\n
Probabilities<\/h2>\n
You have to do at least a couple of rounds of this for the verifier to believe
\nthe prover about the 3-coloring.<\/p>\n
The paper goes on to assert that \u201cthe probability that the verifier will
\naccept (i.e., complete all the m\u00b2<\/code> rounds without detecting that \u201csomething is
\nwrong\u201d) is bounded above by (1 - m\u207b\u00b9)^(m\u00b2)<\/code>\u201d (where m = |E|<\/code>). Which is
\npretty good. For a large graph (say, 1000 edges), this falls off reasonably
\nquickly:<\/p>\n
\n
\n
m<\/span> =<\/span> 1000<\/span>\nfor<\/span> i<\/span> in<\/span> range<\/span>(<\/span>1<\/span>,<\/span> 4600<\/span>):<\/span>\n    print<\/span>(<\/span>\"(1 - m\u207b\u00b9)^round = \"<\/span>,<\/span> (<\/span>1<\/span> -<\/span> m<\/span>**-<\/span>1<\/span>)<\/span>**<\/span>i<\/span>)<\/span>\n<\/code><\/pre>\n<\/div>\n<\/div>\n
At 4600 rounds, you\u2019re at 1% possibility of \u201ccheating\u201d. At 10,000 rounds,
\nyou\u2019re at 0.0045% possibility of \u201ccheating\u201d. At m\u00b2 = 1,000,000<\/code> rounds, it\u2019s
\nvery low<\/em>.<\/p>\n
A networked demo<\/h2>\n
Writing Python code that runs in a single process with comments denoting
\n\u201cprover\u201d and \u201cverifier\u201d is not very satisfying. It does not preclude accidental
\ndata leaking in the slightest. It would be much more satisfying if there was
\nsome sort of barrier, like a process barrier or a network barrier, between the
\nprover and the verifier.<\/p>\n
For this reason, Chris and I have prepared a server (prover) and client
\n(verifier) demo. You can click \u201cRun Round\u201d to run a round (and show the
\npermuted colors). You can visit the docs
\npage<\/a> to see the API docs and build a
\nclient yourself!<\/p>\n
\n