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 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!

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.