Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

What a zero-knowledge proof is

After this lesson: I can explain completeness, soundness and zero knowledge using an interactive proof.

60 min lesson2 commandsZero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Proving you know a secret without telling it

A zero-knowledge proof lets one person convince another that they know a secret, without showing the secret. It is used to sign in without sending a password and to prove facts about private data.

Today you play a game that shows the idea, then measure why it works.

By the end of this lesson

Note

I can explain completeness, soundness and zero knowledge using an interactive proof.

Key words

WordWhat it means
Proverthe one who claims to know a secret
Verifierthe one who checks the claim
Challengea random question the verifier picks
Completenessan honest prover always passes
Soundnessa cheating prover almost always fails
Zero knowledgethe verifier learns nothing except that the claim is true

The cells students fill in are left blank in this preview.

The cave game is an interactive proof

A cave has two paths, A and B, joined by a locked door at the back. The prover says they know the password for the door.

The prover walks in by one path while the verifier waits outside. Then the verifier shouts a random path, A or B. The prover must come out of that path. With the password they always can. Without it, they only succeed if they guessed right, one time in two.

Play the cave game many times

Command
docker exec jupyter python3 steps/cave.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Read what the lab printed

The prover who knows the password passed 20 of 20 rounds. That is completeness.

Then 1000 cheaters played. After round 1, 493 were still passing, after round 2 only 243, and after round 10 none. Each round roughly halves them. Twenty rounds leave a cheater one chance in 1048576. That is soundness.

Worked example: a cheater's chance

RoundsChance a cheater passes them allAs a fraction
11 in 20.5
21 in 40.25
31 in 80.125
101 in 1024about 0.001
201 in 1048576about 0.000001

The cells students fill in are left blank in this preview.

Try it: a cheater in the cave

Code: python
import random

rng = random.Random(3)

def one_round(knows_password):
    went_in = rng.choice("AB")
    asked_for = rng.choice("AB")
    if knows_password:
        return True
    return went_in == asked_for

passed = 0
for n in range(10):
    if one_round(False):
        passed = passed + 1
    else:
        print("caught in round", n + 1)
        break
print("rounds passed:", passed)
# Change False to True, so the prover knows the password, and run again.

Why the verifier learns nothing

Watch from outside and you see the prover come out of the path that was asked for. You never hear the password.

Worse for a spy: a film of the game proves nothing. The two people could have agreed the paths in advance and cut the film. If a fake record looks just like a real one, the real one gives nothing away. That is the idea of zero knowledge.

A common mistake

Warning

Many people think zero knowledge means the verifier learns nothing at all. The verifier learns one thing: that the claim is true. What they do not learn is the secret, or anything that helps them find it.

List the scripts in the lab

Command
docker exec jupyter ls steps

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

About this lab and its source: Zero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.