Zero-knowledge proofs

Can you convince someone you know a secret without telling them the secret, or anything about it at all? It sounds like a contradiction. It isn't, and the answer underpins private payments, anonymous credentials and a good share of modern cryptography.

Proving without telling

Normally, proving you know something means showing it. To prove you know a password, you type it in, and now the server has seen it. To prove you're over 18, you show an ID card, and now the bouncer also knows your name, address and exact birthday.

A zero-knowledge proof lets a prover convince a verifier that a statement is true while revealing nothing beyond the fact that it's true. The verifier walks away certain, and yet unable to tell anyone else the secret, or even to prove to anyone else that they saw a proof.

The idea was introduced in 1985 by Shafi Goldwasser, Silvio Micali and Charles Rackoff. Goldwasser and Micali later won the Turing Award, partly for this work. By convention the prover is called Peggy and the verifier Victor.

The cave of Ali Baba

The classic explanation comes from a 1989 paper titled How to Explain Zero-Knowledge Protocols to Your Children. Picture a ring-shaped cave with a single entrance. The path splits into two passages, A and B, which meet again at the back, where a magic door blocks the way. Only someone who knows the secret word can open the door.

Peggy claims she knows the word. Victor wants proof, but Peggy won't say it. So they play a game:

1. Peggy goes in alone Victor waits outside while Peggy walks into either passage A or B. He can't see which.
2. Victor shouts a challenge Victor steps to the fork and calls out a passage at random: “Come out of A!” or “Come out of B!”
3. Peggy comes out If she's already in that passage, she walks back. If she isn't, she has to open the magic door and come round the other way. Without the word, she's stuck on the wrong side.

A bluffer has a 50% chance of having picked the right passage by luck. But the game can be repeated, and a bluffer has to be lucky every single time. You be Victor. This Peggy may or may not know the word.

After 10 successful rounds, a bluffer would have had to guess right 10 times in a row: a chance of 1 in 1,024. After 20 rounds it's about one in a million. Victor never becomes 100% certain, but he can get as close as he likes.

Two details are easy to miss. First, Victor's challenge has to be unpredictable. If he always shouts the same side, Peggy can simply walk into that side every time, as this Peggy will if she's bluffing and you fall into a pattern. Second, Victor learns nothing about the word. All he ever sees is Peggy walking out of the passage he asked for.

The three properties

Every zero-knowledge proof has to satisfy three conditions. The cave meets all three:

Completeness and soundness are what any proof needs. The third property is the strange one, and it needs a more careful argument.

Why Victor learns nothing

Suppose Victor filmed the whole thing and showed the video to a friend. Would the friend be convinced? It turns out they shouldn't be, because a video like that is easy to fake.

Peggy and Victor could make one without knowing the word at all. Victor tosses a coin and shouts. If Peggy happens to come out the right side, they keep the clip. If not, they cut it and try again. After enough takes, they have a flawless-looking video of Peggy succeeding every time.

The two videos are indistinguishable, and not because the fake is clever. Both are just a list of random challenges, each followed by a success. Nothing in the real one depends on the secret word.

This is how cryptographers define zero knowledge formally. A proof is zero-knowledge if there's a simulator: a procedure that, without the secret, produces conversations that can't be told apart from real ones. If Victor could have produced the transcript himself, then seeing it can't have taught him anything.

So what convinced the live Victor? Only the order of events. He chose his challenge after Peggy was already inside. The video can't prove that, so it's worthless to anyone else. The proof convinces exactly one person: the one who chose the challenges.

Proving any secret: graph colouring

Caves are charming, but real secrets are things like passwords, keys and solutions to puzzles. In 1986, Oded Goldreich, Silvio Micali and Avi Wigderson showed something remarkable: any statement whose solution can be checked efficiently has a zero-knowledge proof. Their construction uses a puzzle called graph colouring.

Take a network of dots joined by lines. The puzzle is to colour every dot with one of three colours so that no line joins two dots of the same colour. For big networks, finding a colouring can be enormously hard, but checking one is easy. And any problem of that “hard to find, easy to check” kind can be translated into a colouring puzzle.

Peggy knows a valid colouring. To prove it without revealing it, she needs one more tool.

Sealed answers: commitments

A commitment is the digital version of writing an answer on a card and sealing it in an envelope. Peggy picks a long random number, called a nonce, and publishes the hash of her answer together with that nonce. The hash reveals nothing, because the nonce makes it unguessable. That property is called hiding. Later she can open it by revealing the answer and the nonce, and anyone can recompute the hash to check. She can't open it as a different answer, because she'd need a different input with the same hash. That's called binding.

The protocol

1. Shuffle the colours Peggy randomly renames her three colours, so amber might become violet this round. The colouring is still valid, but it looks different every time.
2. Seal every dot She publishes a commitment to each dot's colour.
3. Victor picks one line He chooses any line at random and asks to see its two ends.
4. Peggy opens two seals Victor checks that both seals open correctly and that the two colours differ. Then they start again with a fresh shuffle.

Look at the list of colour pairs you've seen. Every round shows two different colours, randomly renamed. That's all Victor ever learns, and he could have generated that list himself by picking two different colours at random. A simulator exists, so the proof is zero-knowledge.

Notice also what happens when Peggy lies while opening. The commitment catches her: the hash of her new answer doesn't match the seal she published before Victor chose. Commitments are what force Peggy to decide her answers before she knows the question, just like walking into the cave before Victor shouts.

Real cryptography: Schnorr's protocol

Colouring proofs work for anything, but they need many rounds. For the most common job, proving you hold a private key, there's a far more efficient protocol, published by Claus-Peter Schnorr in 1989. It uses the same arithmetic as Diffie–Hellman.

There's a public prime p, a generator g, and the size q of the group g produces. Peggy's private key is a number x. Her public key is y = g^x mod p. Working out x from y is the discrete logarithm problem, which is hard. Peggy wants to prove she knows x without revealing it.

1. Commit Peggy picks a fresh random number r and sends t = g^r mod p. This is her walk into the cave.
2. Challenge Victor sends a random number c between 0 and q − 1.
3. Respond Peggy sends s = r + c·x mod q. The random r completely masks x, the way a one-time pad masks a message.
4. Verify Victor checks that g^s = t · y^c mod p. This works because g^{r + c·x} = g^r · (g^x)^c.

A faker can pass only by guessing c in advance, which here means a 1 in 233 chance per round. With realistic sizes, q has about 2²⁵⁶ possible values, so a single round is enough.

Dropping the conversation: Fiat–Shamir

Interactive proofs have a practical problem: Victor has to be online, choosing challenges. And as the video showed, the proof convinces nobody else. In 1986, Amos Fiat and Adi Shamir proposed a trick: let a hash function play Victor.

Instead of waiting for a challenge, Peggy computes it herself as c = hash(t, message). A good hash behaves unpredictably, so Peggy can't choose t to suit a challenge she'd like. Changing t changes c completely. The result is a proof anyone can check later, with no conversation at all. Bind a message into the hash and you get a digital signature. Schnorr signatures, Ed25519, and the signatures Bitcoin has supported since 2021 all work this way.

Edit the received message and the hash produces a different challenge, so the check fails. Only someone who knows x can produce a valid s for a given message. With this toy group, a forger could still win 1 time in 233 by luck; real signatures use groups so large that luck never comes into it.

zk-SNARKs: proofs about anything, in a few hundred bytes

Combine the last two ideas, general statements and non-interactive proofs, and push them to the limit. That's a zk-SNARK: a zero-knowledge Succinct Non-interactive ARgument of Knowledge.

• Succinct: the proof is tiny, often a few hundred bytes, and checking it takes milliseconds, however large the computation it's about.
• Non-interactive: one message, verifiable by anyone, any time.
• Argument of knowledge: it proves the prover actually knows a valid secret, not just that one exists.

That means you can prove statements like “I know a password whose hash is this value”, “this transaction spends coins I own, and the amounts balance” or “I ran this program on this input and got this output”, without revealing the password, the coins or the input.

1. Write the statement as a circuit The check is turned into a long list of simple additions and multiplications, much like a hardware circuit. Proving “I know a valid secret” becomes proving “I know values that make every gate in this circuit correct”.
2. Turn the circuit into polynomials All those gate equations are packed into a few polynomials that only fit together if every gate is satisfied.
3. Check at one random point Two different polynomials can only agree at a handful of points. So instead of checking millions of gates, the verifier checks the polynomials at a single random point. If they match there, they almost certainly match everywhere. This is the step that makes the proof succinct.
4. Hide and compress Commitments and Fiat–Shamir hide the values and remove the conversation, leaving one short proof.

There's a security lesson here too. The maths of a SNARK can be flawless while the circuit is wrong. If a circuit forgets to enforce one condition, an attacker can produce a valid proof of a false statement. These “under-constrained circuit” bugs are one of the most common serious flaws found in real zero-knowledge systems.

Where it's used

Why this matters

• Proof without disclosure is possible. Three properties: completeness, soundness and zero knowledge.
• Unpredictable challenges are what convince. The prover has to commit first and answer second. A recording proves nothing to anyone else.
• Zero knowledge has a precise meaning. If a simulator could fake the conversation without the secret, the conversation can't leak the secret.
• Anything checkable can be proved this way. From a cave, to colourings, to signatures, to SNARKs that prove whole programs ran correctly in a few hundred bytes.