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.

The paper’s protocol

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 locked boxes each bearing the number of the corresponding vertex. More specifically, the prover chooses a permutation π ∈R S₃, places π(φ(i)) in a box marked i (∀ i ∈ V), locks all boxes 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 prover. (Intuitively, the verifier asks to examine the colors of the endpoints of e ∈ E.)

(P2) If e = (u, v) ∈ E, then the prover reveals the colors of u and v by sending the verifier the keys to boxes u and v. Otherwise, the prover does nothing.

(V2) The verifier opens boxes u and v using the keys received and checks whether they contain two different elements of {1, 2, 3}. If the keys do not match the boxes, or the contents violate the condition then the verifier rejects and stops. Otherwise, the verifier continues to the next 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 iteration. For each step, I’ll annotate the code with “Only prover” or “Only 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 graphviz graph above, we have the following edge list data structure:

# Shared between prover, verifier
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. Fancy stuff. Because it’s an undirected graph, (0, 1) means the same as (1, 0) so we don’t have to include both. We can also color it:

# Only prover
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 in the number of edges. Let’s verify that we have a valid sample coloring:

# For the reader
# Check each edge to make sure no edge has the same color on each node
assert all(coloring[u] != coloring[v] for u, v in edges)
# Check that the total number of colors used is 3
assert len(set(coloring.values())) <= 3

We’ll now go through the paper’s steps one by one, writing some code to accompany each step.

Tips and tricks

If you are building alongside the blog post, I recommend using random.seed(0) so your randomness doesn’t change between runs of your program. I also recommend setting the environment variable PYTHONHASHSEED to 0 if you are 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 should swap around the color values while maintaining the 3-color property.

Thankfully, this is easier than it might sound: the names of colors are meaningless to the 3-coloring; they need only be different along the edges. So if we do a bijective (A maps to one B, and B came from one A) mapping from old to new name, this will hold.

I came up with this function that shuffles the colors, lines them up side-by-side, makes a table, and then uses that to make a new coloring:

import random

# Only prover
def permute_three_coloring(coloring):
    all_colors = list(set(coloring.values()))
    new_colors = random.sample(all_colors, len(all_colors))
    permutation = {old: new for old, new in zip(all_colors, new_colors)}
    return {node: permutation[color] for node, color in coloring.items()}
# For example,
# {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"}

Then we have to place the colors in “locked boxes”. One way to proverbially lock a box is to apply a one-way function to it: for example, a hash function. If we hash each color and then pass only the hashes to the verifier, the verifier cannot open them.

This example uses the Python standard library hash function for brevity but it might be better to use a cryptographic hash function like hashlib.sha256:

# Only prover. Wrong!
def hash_coloring_wrong(coloring):
    return {node: hash(color) for node, color in coloring.items()}
# For example:
# {0: -6789624683659967261, 1: 7846608853949633950, 2: 6009240650600289446,
#  3: -6789624683659967261, 4: 7846608853949633950}

There’s just one problem with handing these locked boxes to the verifier: two boxes locked with the same colors will have the same hashes. The verifier would know the coloring. Even if the exact colors are now hidden, it’s really the structure of the coloring for which we want to give up zero knowledge.

To get around this, we can add what’s called a nonce to each node and its coloring. That is, each node gets a little bit of random data packed into the hash so that different nodes’ "darkgreen" hash values look different.

# Only prover
def nonce():
    return random.randrange(100)

def box_coloring(coloring):
    return {node: (color, nonce()) for (node, color) in coloring.items()}

def hash_values(coloring):
    return {k: hash(v) for (k, v) in coloring.items()}

permuted_coloring = permute_three_coloring(coloring)
# For example:
# {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"}
boxed_coloring = box_coloring(permuted_coloring)
# For example:
# {0: ("crimson", 33), 1: ("navy", 65), 2: ("darkgreen", 62),
#  3: ("crimson", 51), 4: ("navy", 38)}
hashed_coloring = hash_values(boxed_coloring)
# For example:
# {0: -2275004828450249492, 1: 2227921633151400991, 2: -5024343381376265886,
#  3: -5381005702768533635, 4: 1164729608819214729}

Again, you probably don’t want to use the standard library random number generator for your nonces. You should consider something like secrets.token_hex() from the secrets module (Python 3.6+). Maybe even consider using the hmac module.

Finally, we can send the hashed_coloring to the verifier and begin step V1.

Step V1

Since the verifier knows the graph (but not its colors), it can pick an arbitrary edge to inspect. It wants to verify that the arbitrary edge it picked satisfies the 3-color conditions. It sends off a request for an arbitrary edge e:

# Only verifier
e = random.choice(edges)
revealed = prover_please_reveal_colors(e)

This is implicitly relying on some global state (the prover knowing what “session” is active with the verifier). If you have multiple verifiers or concurrent sessions or something, you may need to thread through some context identifier in the communication.

Step P2

The prover, having received this request, sends over the colors and nonces for each of the nodes in the edge.

# Only prover
def prover_please_reveal_colors(edge):
    u, v = edge
    return {u: boxed_coloring[u], v: boxed_coloring[v]}
# For example:
# {3: ('crimson', 51), 4: ('navy', 38)}

You may be suspicious at this point because we’re leaking some information about the coloring.

Note that it’s ok for the prover to reveal the color for one edge, because 1) the colors have been shuffled once per round and 2) we’re going to apply our box locking protocol each time we reveal an edge (also once per round), so the verifier accumulates no information about our colors between iterations.

Step V2

The verifier can check that the color+nonce hashes to the hash value given for each node in step P1. This ensures that the prover is not changing colors around mid-round. This relies on the verifier and the prover using the same hash function (and the same hash seed if using hash).

# Only verifier
for (node, (color, nonce)) in revealed.items():
    assert hashed_coloring[node] == hash((color, nonce)), f"Hash mismatch!"

The verifier can then inspect that the two color values are different. This gives a small amount of credence (1/|E| because you know something about one edge now) that the graph is 3-colored appropriately because the prover had no way of knowing which edge the verifier would want to inspect.

If either of these two conditions doesn’t check out, the verifier rejects.

Probabilities

You have to do at least a couple of rounds of this for the verifier to believe the prover about the 3-coloring.

The paper goes on to assert that “the probability that the verifier will accept (i.e., complete all the m² rounds without detecting that “something is wrong”) is bounded above by (1 - m⁻¹)^(m²)” (where m = |E|). Which is pretty good. For a large graph (say, 1000 edges), this falls off reasonably quickly:

m = 1000
for i in range(1, 4600):
    print("(1 - m⁻¹)^round = ", (1 - m**-1)**i)

At 4600 rounds, you’re at 1% possibility of “cheating”. At 10,000 rounds, you’re at 0.0045% possibility of “cheating”. At m² = 1,000,000 rounds, it’s very low.

A networked demo

Writing Python code that runs in a single process with comments denoting “prover” and “verifier” is not very satisfying. It does not preclude accidental data leaking in the slightest. It would be much more satisfying if there was some sort of barrier, like a process barrier or a network barrier, between the prover and the verifier.

For this reason, Chris and I have prepared a server (prover) and client (verifier) demo. You can click “Run Round” to run a round (and show the permuted colors). You can visit the docs page to see the API docs and build a client yourself!

(If you don't see a graph right below this message, please wait a moment for the server to wake up.)

Encoding other NP-complete problems

At this point, we’ve shown how you can use a zero-knowledge interactive proof to verify that someone has a valid 3-coloring of a graph without learning any information about the 3-coloring. So what? Is there anything else we can prove with zero knowledge? Is the interactive proof of 3-coloring just a contrived party trick without real applications?

Well…

Sudoku

Sudoku puzzles are another example of a problem that’s hard to solve and easy to verify. It is algorithmically hard to fill in 81 squares to satisfy the constraints of all rows, columns, and boxes containing the digits 1-9, but the verifier is extremely quick.

Let’s say we wanted to prove we’ve finished a Sudoku, but we don’t want to give up a morsel of information about the solution. We can execute an interactive proof very analogous to 3-coloring! Instead of shuffling colors, we shuffle digits. Instead of revealing edges, we reveal rows, columns, and boxes.

Next time your fellow bus rider leans over asking to see your Sudoku solution, just ask them to go through 90,000 easy steps first!

Reduction

Let’s say we have a hard problem and we’ve computed a solution it, but we don’t have an obvious algorithm on hand to execute an interactive proof for it. Thanks to the authors of the paper above, we know that if the problem is NP-complete there’s an interactive proof for it!

We use the power of a polynomial time reduction. We (somehow) convert our solution to a graph and its 3-coloring, then just follow the steps and code above! The “somehow” is the tricky part, but much research exists on converting between different NP-complete problems.

For example, you may want to create a zero-knowledge proof that you know the prime factors for a very large composite number. Unfortunately, for only double digit numbers your graph is thousands of nodes, so reducing to 3-coloring has its limits in practice and you’re better off with more sophisticated proof techniques than a reduction to 3-coloring.

Wrapping up

After doing a bit of research, we decided that the most common real world use cases of zero-knowledge proofs (age verification, crypto, etc) aren’t particularly interesting to us. We enjoyed the graphs and theory of computation and networked computing though. We hope you had fun playing around with interactive proofs too.