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
| Word | What it means |
|---|---|
| Prover | the one who claims to know a secret |
| Verifier | the one who checks the claim |
| Challenge | a random question the verifier picks |
| Completeness | an honest prover always passes |
| Soundness | a cheating prover almost always fails |
| Zero knowledge | the 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
docker exec jupyter python3 steps/cave.pyShown 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
| Rounds | Chance a cheater passes them all | As a fraction |
|---|---|---|
| 1 | 1 in 2 | 0.5 |
| 2 | 1 in 4 | 0.25 |
| 3 | 1 in 8 | 0.125 |
| 10 | 1 in 1024 | about 0.001 |
| 20 | 1 in 1048576 | about 0.000001 |
The cells students fill in are left blank in this preview.
Try it: a cheater in the cave
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
docker exec jupyter ls stepsShown here, not run. Press Start lab to type it into your own lab’s terminal.