Try It Yourself

Graph Coloring

Graph 3-coloring is the classic example used to explain zero-knowledge proofs. It is simple enough to understand in minutes, yet rich enough to illustrate every important property of the ZKP model. By the end of this page you will understand exactly what "zero-knowledge" means, why the proof is sound, and why the prover leaks nothing at all.

The Problem

A graph is a set of nodes connected by edges. A 3-coloring assigns one of three colors to every node such that no two nodes connected by an edge share the same color.

Finding a valid 3-coloring is an NP-complete problem — there is no known efficient algorithm that works for arbitrary graphs. Verifying a coloring, however, is trivial: just check every edge. This asymmetry is exactly what ZKPs exploit.

Why this matters

Any NP problem can be reduced to 3-coloring in polynomial time. That means a ZKP for graph coloring is, in principle, a ZKP for any NP statement.

The Setup

Two parties are involved:

Alice (Verifier) — has a graph and wants to know whether it is 3-colorable.
Bob (Prover) — claims he has a valid 3-coloring but refuses to reveal it before being paid.

The goal: Bob convinces Alice he has the solution, without Alice learning a single thing about what the coloring actually is.

The Protocol

Each round of the proof has three steps.

Step 1 — Commit

Bob takes his valid coloring and randomly permutes the three colors. If his original coloring used red/blue/green, he might swap so that red→green, blue→red, green→blue. The permuted coloring is still valid — only the labels changed.

He then commits to the permuted coloring by placing a cryptographic lock on each node. Alice sees only locked nodes — she knows a commitment exists for each node but cannot see the colors underneath.

Step 2 — Challenge

Alice picks any edge — any pair of adjacent nodes — and asks Bob to reveal the colors at both endpoints.

Step 3 — Reveal

Bob opens both locks. Alice checks that the two revealed colors are different. If they are, she has seen one valid edge. The rest of the graph remains hidden.

This process repeats from Step 1, with Bob using a fresh random permutation each round.

Try It Yourself

The graph below has 5 nodes and 6 edges. It is 3-colorable (you can see the solution in the first step). Click through each stage of one round of the protocol.

Rounds

—

Confidence

Figure 1. Interactive simulation of one round of the graph 3-coloring ZKP. In the commit phase all nodes are locked under a cryptographic commitment; Alice selects an edge as a challenge and Bob opens only those two commitments. Each round uses a fresh random permutation of the three colors.

Cryptographic Commitments

The "hat over a node" from the physical intuition is implemented using a hash function. Bob commits to the color of node $i$ by publishing:

$$\text{commitment}_i = H\!\left(\,\text{color}_i \;\|\; \text{nonce}_i\,\right)$$

where $\text{nonce}_i$ is a large random string chosen fresh every round, and $H$ is a cryptographic hash (e.g. SHA-256). The nonce prevents Alice from brute-forcing the color: even though there are only three possible colors, the commitment for $\text{red}$ is different every round.

When Bob reveals a node, he discloses (color, nonce). Alice recomputes the hash and checks it matches the commitment she received earlier. Bob cannot retroactively change a color — the commitment is binding. Alice cannot learn anything from the commitment alone — it is hiding.

A concrete example for one round might look like this:

-- Permuted coloring (private to Bob) --
Node  Color    Nonce          Commitment (SHA-256 prefix)
  1   green    x7fKqmNpRt     a3f92c1d...
  2   red      bYw3ZoLsVk     7e841bb0...
  3   blue     hJ6nPcXrWq     2d093fe4...
  4   green    mQ9sTuYdEa     c1a57830...
  5   red      kR2vBxFgNz     88f4120e...

-- Alice challenges edge (1, 2) --
Bob reveals: node 1 → green / x7fKqmNpRt
             node 2 → red   / bYw3ZoLsVk

Alice checks: H("green" || "x7fKqmNpRt") == a3f92c1d... ✓
              H("red"   || "bYw3ZoLsVk") == 7e841bb0... ✓
              green ≠ red ✓

Why Is This Zero-Knowledge?

A valid ZKP must satisfy three properties.

Completeness

If Bob genuinely has a valid coloring, every edge he is challenged on will have two different colors. Alice will always accept. An honest prover always convinces an honest verifier.

Soundness

Suppose Bob is cheating and has no valid coloring. Then at least one edge in his graph has two nodes of the same color. No matter how clever his permutation is, that edge is still broken. If Alice happens to challenge that edge, she catches him immediately.

With $m$ edges total, the probability of Alice not catching a cheater in a single round is at most $\tfrac{m-1}{m}$. After $k$ independent rounds:

$$P(\text{not caught after } k \text{ rounds}) \;\leq\; \left(\frac{m-1}{m}\right)^{\!k}$$

For the 5-node graph above (6 edges), after 100 rounds this is below $10^{-7}$. After 1000 rounds it is negligible.

Zero-Knowledge

This is the subtle and beautiful part. After seeing many rounds, what does Alice actually learn about Bob's coloring?

Nothing. In each round Bob uses a fresh random permutation of the colors. The two nodes Alice sees are always two different colors — but she already knew that any valid coloring of an edge would show two different colors. She sees (red, blue) in one round, (green, red) in the next — none of these pairs tell her anything about the original assignment, because the mapping between the original colors and the current colors changes every round unpredictably.

More formally, Alice could have simulated the entire transcript herself: just pick a random edge, pick two different colors for its endpoints, and write it down. The result is statistically indistinguishable from a real interaction with Bob. Because Alice could generate this herself, the interaction conveys no information about the actual solution.

The simulator argument

The standard definition of zero-knowledge says: a protocol is zero-knowledge if there exists a simulator — a program that, with no access to the prover's secret, produces a transcript that looks identical (in distribution) to a real transcript. The color permutation is exactly that simulator here.

How Many Rounds?

The table below shows the soundness error (probability a cheating prover survives) for the 6-edge graph after increasing numbers of rounds.

Rounds ($k$)	Soundness error $\left(\tfrac{5}{6}\right)^k$
1	83.3%
10	16.2%
30	0.42%
60	0.0018%
100	$\approx 1.2 \times 10^{-6}$%
200	$\approx 10^{-14}$%

In practice, interactive ZKPs are run for enough rounds to push the soundness error below any desired threshold. For real-world proofs of large graphs (or NP problems reduced to graph coloring), the number of required rounds grows with the number of edges, but the per-round cost is small.

← Ali Baba Cave Sudoku →