DocsWhat it is
What a zero-knowledge proof is
A way to prove that a statement is true while revealing nothing beyond the fact that it is true.
In plain words
You convince someone that you know a secret, such as a password, a private key or the answer to a puzzle, without telling them the secret, and without handing them anything they could use to convince someone else.
Two ideas make that possible, and the two demos below run both on your own device: a calculation that is easy one way and impossible the other, and a real proof built on it.
Easy one way, impossible the other
Take a large prime p, a number g and a secret x. Working out y = gx mod p (multiply by g, x times over, keeping only the remainder after dividing by p; done by repeated squaring, it takes a few hundred steps) is quick, even when x has 77 digits. Going back, from y to x, is the discrete logarithm problem, and no one knows a fast way to solve it on the computers that exist today.
Demo 1 · Easy one way, impossible the other
- p
- 2255 − 19
- g
- 2
- Secret x, made on your device
- ·
- y = gx mod p
- ·
Working out y…
With JavaScript on, this demo makes a 77-digit secret on your device, works out y from it and times that, and for a secret of up to 7 digits really searches for x. The estimates it shows:
| Digits in x | Steps, best known generic method | Every computer on Earth, at 1019 steps a second |
|---|---|---|
| 38 | 1019 | 1 second |
| 48 | 1024 | 28 hours |
| 57 | 3.2 × 1028 | 100 years |
| 60 | 1030 | 3,200 years |
| 73 | 3.2 × 1036 | 10 billion years |
| 77 | 2.4 × 1038 | 760 billion years: 55 times the age of the universe |
How the estimate is made. A search must cover every number up to that many digits (for 77 digits, every number below p − 1). The best known generic method, one that works in any group (Pollard's rho, 1978), needs about the square root of that many steps. We assume a generous 1019 steps a second for every computer on Earth together. The timeline is logarithmic: each equal step along it multiplies the time by the same amount. On it, a lifetime is 80 years, all of history the 5,000 years since writing began, and the age of the universe 13.8 billion years.
Pigeon's keys. Pigeon's elliptic-curve keys are on a curve over this same prime, 2255 − 19: X25519 and Ed25519 in its encryption (MLS), ristretto255 in its invite tokens. This demo uses the simpler group of numbers mod that prime to show the same one-way principle. In this simpler group, specialised methods (index calculus) do much better than the generic one, so its real strength is lower than the table shows; on the curve, no such method is known, and the generic estimate holds. Pigeon's curve has about 2252 keys, so the same estimate there is 2126 steps: about 270 billion years. A large quantum computer, which no one has built, would solve both; that is why Pigeon's network seal also uses a post-quantum key exchange (X-Wing).
A real zero-knowledge proof, live
This is Schnorr's protocol (1989): a prover shows that it knows the secret x behind a public y = gx mod p, without revealing x. It uses toy numbers, p = 467 and g = 4, so you can check the arithmetic by hand; with numbers this small, anyone could find x by trying every value, as the first demo does.
Demo 2 · Schnorr's protocol, one move at a time
- Public
- p = 467, g = 4, y = ·
- The prover's secret
- x = ·, r = –Hidden
1. Commit
The prover picks a fresh random r and sends t = gr mod p. It fixes r without showing it: getting r back from t is the one-way problem above.
2. Challenge
The verifier picks c at random, from 0 to 232. It comes after t, so the prover can't have chosen t to suit it.
3. Respond
The prover sends s = r + c × x mod 233 (233 is how many powers of 4 there are mod 467). The fresh random r masks c × x: on its own, s is a random number from 0 to 232 and says nothing about x.
4. Check
The verifier tests gs = t × yc mod p. It holds because gr + cx = gr × (gx)c.
| Round | t | c | s | Check |
|---|
With JavaScript on, you run the rounds yourself. A worked example, with secret x = 57, so y = 457 mod 467 = 366. The prover keeps r and sends t = 4r mod 467, the verifier picks c, the prover sends s = r + 57c mod 233, and the check compares 4s with t × 366c, both mod 467:
| Round | r | t | c | s | Check |
|---|---|---|---|---|---|
| 1 | 38 | 212 | 121 | 178 | 342 = 342 |
| 2 | 205 | 188 | 9 | 19 | 59 = 59 |
| 3 | 117 | 465 | 180 | 125 | 155 = 155 |
Why it convinces. A prover that doesn't know x can answer at most one challenge for each t: two right answers for the same t would give away x. So it passes a round only once in 233 tries, and each further round divides that again.
Why it's zero knowledge. Anyone can write rows exactly like the verifier's table without knowing x: pick c and s first, then set t = gs × y−c mod p. So, for a verifier that picks its challenges at random, as this one does, the table carries nothing about x, and it can't convince anyone else. The verifier is convinced only because it chose each c after it saw t.
In Pigeon today
When you join with an invite, your app blinds what it sends the invite server, so the server computes its answer without seeing your token (an oblivious pseudorandom function, RFC 9497). That blinding isn't a proof. The answer comes back with one: a zero-knowledge proof (a DLEQ proof) that the server used the key it published, so it can't single out your token with a key of its own.
That proof makes the same three moves, commit, challenge and respond, in the ristretto255 group instead of toy numbers, with the challenge computed as a hash (the Fiat-Shamir transform, below), so it is one message the app checks.
Precisely
A zero-knowledge proof is a protocol between a prover and a verifier about a public statement. The prover holds a witness, the secret that makes the statement true. For example, the statement "this public key is k times the generator G" has the private key k as its witness. A zero-knowledge proof has three properties:
- Completeness
- If the statement is true and both sides follow the protocol, the verifier accepts.
- Soundness
- If the statement is false, no prover, however it cheats, makes the verifier accept, except with a negligible probability (in the live proof above, 1 in 233 per round). A proof of knowledge says more: a prover that convinces the verifier must actually know a witness, in the sense that an algorithm (the extractor) could pull the witness out of it.
- Zero knowledge
- Everything the verifier sees could have been produced by an algorithm (the simulator) that doesn't know the witness. So the transcript teaches the verifier nothing it couldn't have worked out alone, beyond the fact that the statement is true.
Interactive and non-interactive
The live proof above is interactive: its soundness rests on the verifier's random challenge. It is a three-move sigma protocol: the prover commits, the verifier sends a random challenge, the prover responds. Schnorr's protocol (1989) proves knowledge of a discrete logarithm this way, and many practical proofs follow its pattern.
The Fiat-Shamir transform (1986) makes such a protocol non-interactive: the prover computes the challenge as a hash of the statement and its commitment, so the proof is one message that anyone can check later. Both proofs Pigeon has built are of this kind (in Pigeon today).
Succinct proofs: zk-SNARKs
A zk-SNARK (zero-knowledge succinct non-interactive argument of knowledge) proves a general statement written as an arithmetic circuit. The proof stays small and quick to verify however large the computation is. Many zk-SNARKs need public parameters made in a setup step, and the scheme's security depends on them. Midnight runs its contracts as circuits proved this way.
What isn't a zero-knowledge proof
- Encryption hides data from anyone without the key. A zero-knowledge proof shows that a statement about data is true; it hides nothing that isn't the witness.
- An oblivious pseudorandom function (OPRF) lets a client get a server's keyed function of its input while the server doesn't see the input and the client doesn't learn the key. Its privacy comes from blinding, not from a proof. A verifiable OPRF adds a zero-knowledge proof that the server used the key it committed to.
- A signature proves who signed, and anyone can show it to anyone. A signature of knowledge is built from a zero-knowledge proof and can be made to convince only the people it is meant for.
Where it comes from
Shafi Goldwasser, Silvio Micali and Charles Rackoff defined zero-knowledge proofs in "The Knowledge Complexity of Interactive Proof Systems", presented at the ACM Symposium on Theory of Computing in 1985 (journal version, SIAM Journal on Computing, 1989). The paper introduced interactive proofs and asked how much knowledge a proof gives away beyond its conclusion; a zero-knowledge proof gives away none.
The work that followed is the toolkit used today:
- Goldreich, Micali and Wigderson (1986) showed that every statement in NP has a zero-knowledge proof, if one-way functions exist.
- Fiat and Shamir (1986) turned interactive identification proofs into signatures with a hash function.
- Schnorr (1989) gave the efficient proof of knowledge of a discrete logarithm that most elliptic-curve proofs build on.
Read on
- Zero knowledge in Pigeon today: which piece is what.
- Midnight: what it is, who builds it, and Pigeon's key log.
- Glossary: the terms on these pages.