Zero-Knowledge Proofs

Goldwasser, Micali and Rackoff introduced the idea in 1985, and their paper was rejected three times before publication — reviewers doubted the concept was coherent. Their contribution was not a protocol so much as a definition: a way to say precisely what ‘revealed nothing' means. Claus-Peter Schnorr gave a compact and practical instance in 1989, and its non-interactive form became the template for a great many modern signature schemes. From 2012 the succinct variants known as zk-SNARKs made proofs small enough and fast enough to verify on a blockchain.

A zero-knowledge proof must satisfy three properties at once, and the third is the hard one:

• Completeness — an honest prover who really knows the secret always convinces the verifier.
• Soundness — a prover who does not know it is almost certain to be caught.
• Zero knowledge — the verifier learns nothing they could not have produced alone.

Schnorr's protocol demonstrates all three in three messages. The prover knows x; everyone knows y = g^x. The prover commits to a random r by sending t = g^r. The verifier replies with a random challenge c. The prover answers s = r + cx, and the verifier checks:

g^s  =  t · y^c  (mod p)

The response s is the secret x masked by the fresh random r, so it discloses nothing. But it could only have been produced by someone who knew x — unless they guessed the challenge in advance.

Arithmetic runs in a group of prime order 233 modulo 467 — small enough to print every value. Choose a secret, then play as an honest prover or as a cheat who does not know it.

Press Prove honestly.

Here is the argument that makes ‘zero knowledge' precise, and it is genuinely surprising. Take the protocol's steps out of order: choose the challenge and the response first, then work backwards to the commitment that makes the check succeed. The resulting transcript passes verification perfectly — and it was produced by someone with no secret at all.

So a recorded transcript is worthless as evidence. Anyone can forge one. The proof only convinces the verifier who chose the challenge themselves, after the commitment was locked in. Conviction lives in the ordering of the messages, not in their contents — which is exactly why the verifier learns nothing: everything they saw, they could have written themselves.

Forge a transcript and check it against the same verifier.

Schnorr's soundness is not perfect and is not meant to be: a cheat who guesses the challenge in advance succeeds, with probability 1 divided by the size of the challenge space. On this page that is 1 in 233, which you can watch happen. Real deployments use challenge spaces around 2²⁵⁶, where the same gap is unreachable.

Making the protocol non-interactive introduces the sharper risk. The Fiat–Shamir transform replaces the verifier's random challenge with a hash of the commitment, so the prover can generate the challenge themselves without being able to control it. This is how a Schnorr proof becomes a signature — but its security then rests on the hash behaving like an ideal random function, an assumption examined honestly in The Random Oracle. Implementations that hash too little into the challenge have been broken repeatedly; the class of bug is common enough to have a name, the ‘weak Fiat–Shamir' attack.

Succinct proof systems add their own concerns. Many pairing-based zk-SNARKs require a trusted setup whose discarded randomness would forge arbitrary proofs if retained — the reason for elaborate multi-party ceremonies. Transparent systems such as STARKs avoid that setup entirely, at the cost of larger proofs. Pairing-based constructions also inherit the discrete logarithm's vulnerability to quantum attack, while hash-based ones do not.

Zcash uses zk-SNARKs to validate shielded transactions without revealing sender, recipient or amount. Ethereum rollups post a succinct proof that thousands of transactions executed correctly, so the main chain need not re-run them. Anonymous credential systems let you prove an attribute — over eighteen, a citizen, a subscriber — without disclosing the underlying document. And every Schnorr or EdDSA signature you verify is a zero-knowledge proof of knowledge that has been made non-interactive.