Symptom
A user wants to prove they are over 18. Your options all leak: send the birth date, send a scan of the passport, or trust a third party who then learns every site the user visits.
Generalize it and the problem is everywhere. Prove you know the password without sending the password. Prove your income exceeds a threshold without disclosing it. Prove a transaction is valid without revealing amounts or parties. Prove a computation was performed correctly without redoing it.
Every one of these has the same shape: convince someone a statement is true while revealing nothing beyond its truth. Stated plainly it sounds impossible, because a proof is a piece of information and information is what you are trying not to give. The resolution requires making “reveals nothing” precise, and once it is precise the impossibility evaporates.
Statement
An interactive protocol between a prover and a verifier for a statement $x$ is a zero-knowledge proof if it satisfies three properties.
Completeness. If $x$ is true and both follow the protocol, the verifier accepts with probability 1.
Soundness. If $x$ is false, no cheating prover convinces the verifier except with negligible probability.
Zero-knowledge. For every verifier there is a polynomial-time simulator that, without access to the secret, produces transcripts computationally indistinguishable from real ones.
The third condition is the definitional achievement. It does not say the transcript looks random. It says the transcript could have been manufactured by the verifier alone, so whatever the verifier learned, it could have derived without ever talking to the prover. A transcript you could have written yourself carries no information from anyone else.
Scope. Assuming one-way functions exist (T076), every language in NP has a zero-knowledge proof. Not a special class of statements: everything with an efficiently checkable witness.
Argument
Graph 3-colouring, the construction that proves the general theorem. 3-colouring is NP-complete, so a zero-knowledge protocol for it gives one for all of NP by reduction (T017).
The prover knows a 3-colouring of a public graph $G$ with $n$ vertices and $m$ edges. One round:
- The prover randomly permutes the three colours, then commits to each vertex’s colour separately — think of each vertex covered by a locked box.
- The verifier picks one edge at random and asks for both endpoints.
- The prover opens those two boxes. The verifier accepts if the colours differ.
Soundness. If $G$ is not 3-colourable, any assignment the prover commits to has at least one improperly coloured edge, so the verifier catches it with probability at least $1/m$. Repeat $m \cdot k$ times independently and the cheating probability drops below $2^{-k}$. 40 repetitions gives a cheating probability of $2^{-40} \approx 9.1 \times 10^{-13}$, which is comfortably below the chance of a hardware error during verification.
Zero-knowledge. What does the verifier see in one round? Two commitments opened to two different colours from ${1,2,3}$, uniformly random because the colour permutation was fresh, and $n-2$ unopened commitments. The simulator produces exactly this without knowing any colouring: guess which edge the verifier will query, commit to two random distinct colours there and arbitrary values elsewhere, and if the guess was wrong, rewind and try again. It succeeds in expected $m$ attempts, and the transcripts are identically distributed.
The rewinding is the whole trick, and it is worth pausing on. The simulator has a power the real prover lacks: it can back up time and retry. That single extra ability compensates exactly for not knowing the secret, which is what makes the transcripts producible without knowledge. Every zero-knowledge proof works this way.
The relation to IP = PSPACE, which is why this post depends on T036. Zero-knowledge is a property of interactive proofs, and interaction plus randomness is what makes it possible at all. A non-interactive, deterministic proof is a fixed string the verifier can copy and show to someone else, and such a string cannot be zero-knowledge for a hard statement — it would be transferable evidence. T036 established that interaction plus randomness buys real power; this post is that power aimed at privacy rather than at verification strength.
Fiat–Shamir, and how interaction is removed anyway. Interaction is inconvenient: it needs both parties online, and it makes proofs non-transferable by design. The Fiat–Shamir transform replaces the verifier’s random challenges with a hash of the transcript so far. Since the prover cannot control the hash output, it cannot choose favourable challenges, and the protocol becomes a single message.
The proof of security holds in the random oracle model, which is an idealization that treats the hash as a truly random function and is known to be unsound in contrived cases. It is also universally deployed: Schnorr signatures, EdDSA, and essentially every practical non-interactive proof system are Fiat–Shamir applied to a zero-knowledge identification protocol. Digital signatures are zero-knowledge proofs of knowledge of a private key, non-interactively.
Proof of knowledge, a distinct and often-needed property. Soundness says a false statement cannot be proved. It does not say the prover knows a witness. A protocol is a proof of knowledge if there is an extractor that, given rewinding access to a successful prover, recovers the witness. Authentication needs this: proving that a valid password exists is worthless, and proving you know it is the point. The extractor and the simulator are mirror images — one recovers the secret with rewinding, the other fabricates a transcript without it.
SNARKs and STARKs, where the field went. Modern systems add succinctness: the proof is short and verification is fast independent of the computation size. A SNARK can prove correct execution of a program with millions of steps in a proof of a few hundred bytes verified in milliseconds.
The costs are real and specific. SNARKs such as Groth16 need a trusted setup, whose secret randomness — the “toxic waste” — would allow forging proofs if retained, which is why Zcash ran a multi-party ceremony where a single honest participant suffices. STARKs avoid trusted setup and are post-quantum secure, relying only on hash functions, at the cost of larger proofs. Proving remains expensive: generation is typically orders of magnitude slower than running the computation directly, which is the reason these are used where verification is repeated many times or must happen on expensive infrastructure.
Where it actually runs. Zcash shields transaction amounts and addresses while proving no double-spend. Ethereum’s zk-rollups — zkSync, StarkNet, Scroll, Polygon zkEVM — execute transactions off-chain and post a single proof, so the chain verifies a batch of thousands in the cost of one verification. Signal uses zero-knowledge proofs in its private group system for anonymous credentials. Tornado Cash proved membership in a set of deposits without identifying which. And nuclear warhead verification research has used zero-knowledge protocols to let inspectors confirm a warhead is genuine without learning its design, which is the least software-shaped application on the list and the one that best conveys the generality.
Forbids
Transferring a zero-knowledge proof to a third party. An interactive transcript is simulatable, so it convinces nobody who was not the live verifier. This is deniability, and it is a feature: it is why an interactive proof cannot be used against you as evidence.
Learning anything beyond the statement’s truth. That is the definition. A protocol that leaks even a single bit of the witness is not zero-knowledge.
Perfect zero-knowledge for all of NP with unconditional soundness. Statistical zero-knowledge proofs for NP-complete languages would collapse the polynomial hierarchy, so one of the two properties must be computational.
Efficient proving, so far. Succinct verification does not make proving cheap. Proof generation is the practical bottleneck in every deployed system.
Does not forbid
It does not mean the verifier learns literally nothing, and this is the misreading that makes people distrust it. The verifier learns the statement is true, which is often exactly the sensitive fact. A zk-rollup proof reveals that a batch of transactions was valid, and an age proof reveals that the user is over 18. Zero-knowledge protects the witness, not the claim.
It does not require interaction in deployment. Fiat–Shamir removes it, and every EdDSA signature is a non-interactive zero-knowledge proof of knowledge that you already rely on.
It does not require a trusted setup. That is a property of specific SNARK constructions. STARKs, Bulletproofs, and Halo2 are all transparent, needing only public randomness.
It does not make proofs unforgeable by a computationally unbounded prover. Most efficient systems are arguments, sound only against polynomial-time provers, because that is what makes them succinct. Bulletproofs and Groth16 are arguments, not proofs, and the distinction matters for long-term security.
It does not require the statement be about a secret you hold. You can prove statements about others’ data given the witness, which is the basis of verifiable computation and delegated proving services.
Boundary
- Computational assumptions required. Commitments need one-way functions (T076); no unconditional construction for NP exists.
- Soundness is statistical. Repetition drives the error down, never to zero.
- Simulation is against a defined verifier class. Honest-verifier zero-knowledge is weaker than the malicious-verifier variety and is what many efficient protocols actually prove.
- Fiat–Shamir needs the random oracle model, and implementation mistakes here — omitting public inputs from the hash — have caused real breaks in deployed proof systems.
- Prover cost dominates. Succinctness is on the verifier’s side only.
The move to carry: “reveals nothing” was made checkable by asking whether the verifier could have produced the transcript alone. Once that definition existed, the impossible became constructive, and it now underwrites signatures you use every day.