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 — false statements are accepted only with bounded probability. A proof of knowledge additionally formalizes possession of a witness.
• Zero knowledge — the verifier learns nothing they could not have produced alone.

This Schnorr identification example has perfect completeness, a knowledge-soundness argument and honest-verifier zero knowledge. 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) mod q, where q is the group order, 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. Its small group and teaching randomness are not secure parameters. 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.

For this interactive protocol with an honestly sampled uniform challenge, the simulator produces the same transcript distribution without the secret. This establishes honest-verifier zero knowledge; it is not by itself a proof for every malicious verifier. A recording of this exchange is not transferable evidence of knowledge, because a third party could have simulated it. That differs from a properly constructed non-interactive signature, whose public verification is intended to be transferable.

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.

The Fiat–Shamir transform derives a challenge by hashing the commitment together with the public statement and required application context. A signature must bind the message as well. Domain separation and unambiguous encodings matter. The prover can try different commitments, but should not be able to choose a useful challenge cheaply under the proof's hash model. A random-oracle proof is a conditional security argument, not a proof that a concrete hash is an ideal oracle.

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 suitably designed hash-based systems avoid that particular attack; their post-quantum security still depends on parameters and assumptions.

Zcash uses zero-knowledge proofs for shielded transactions. Validity rollups can prove that batches of transactions executed correctly; optimistic rollups use a different mechanism. Anonymous credentials can prove attributes without disclosing the full credential. Schnorr and EdDSA signatures use related commitment-and-challenge ideas, but it is misleading to call every signature a zero-knowledge transcript with the guarantees of this interactive demonstration.