How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser)

Shafi Goldwasser, Silvio Micali, and Charles Rackoff invented zero-knowledge proofs, a result that now underlies SNARKs and blockchain privacy tools. Zero knowledge guarantees that after an interaction a verifier believes a prover's claim but learns nothing beyond it, formalized through the simulation paradigm, which shows that whatever a verifier learns could have been simulated without the prover at all.

The work grew out of the mental poker problem, in which two players needed to deal cards over the phone without physical cards. A bug identified by Lipton showed that one bit of information about the cards could leak from the original protocol. The question of how to prove correct behavior without revealing the cards or the randomness used to encrypt them drove the team toward zero-knowledge interactive proofs. Their first result was a protocol for proving a card was properly opened using number theory, not yet a general result. The GMR paper was submitted six times and rejected each time before publication, partly because its complete novelty gave reviewers no prior art to compare against.

Goldwasser says the motivation for introducing interaction and randomness into proofs was privacy, not a mathematical proof metaphor, and that the realization interaction and probabilism allow proving harder statements came after the zero-knowledge example. Mathematicians resisted interactive proofs because they defined a proof as something with zero error, and accepting a small probability of error in the verifier was the conceptual move that made zero knowledge possible. Arthur-Merlin proofs, a simpler one-round system developed simultaneously, differ from zero-knowledge proofs in that the verifier tosses coins openly rather than sending a message whose underlying coins the prover cannot see.

Research on interactive proofs split into a complexity theory branch and a privacy branch. Work on two-prover systems, where suspects in separate rooms are questioned to check consistency, eventually led toward the result that IP equals PSPACE, with Adi Shamir taking that line to its conclusion. A postdoc named Nisan developed a protocol using two provers and a SumCheck to prove the value of the permanent, and researchers Fortnow, Karloff, and Lund converted that two-prover protocol into a single-prover protocol while Nisan was traveling. Goldwasser estimates it took approximately five years from publication, and perhaps nearly a decade from when the model was conceived, for its full power to be unlocked.

A classical mathematical proof can be rewritten using error-correcting codes so that any error in the original produces many errors in the new version, enabling random local checks. That ability leads toward SNARKs by enabling compression of long proofs using hash functions and Merkle trees. The Fiat-Shamir transformation removes interaction from protocols entirely, allowing SNARKs to be built without going through PCPs, though open theoretical questions about its security remain even as practitioners are generally comfortable using it. The prevailing trend in SNARK design today is writing out a computation transcript step by step using a virtual machine abstraction and applying SumCheck to prove every step was done correctly, which mirrors thinking from the late 1980s and early 1990s.

SNARKs rely on a computationally bounded prover who cannot find a convincing proof of a false statement, meaning convincing proofs of false statements exist in principle but nobody can find them. This contrasts with early interactive proofs, where the prover was assumed to be all-powerful. Goldwasser notes that the paradigm of treating reality as indistinguishable from a correct reality given available computational resources has driven efficiency improvements across the field. The SNARK community uses ZK to mean succinct rather than zero knowledge in the privacy sense, which Goldwasser described as among the most annoying terminological misuses in the field. Many popular SNARK applications such as scaling blockchains by posting proofs of correct computation off-chain do not actually require privacy, but ZCASH is a genuine exception because private currency transfers require zero knowledge in the original sense.

On the cryptographic assumptions underlying these systems, Goldwasser notes that the factoring assumption is now considered less safe because quantum computers under active development can address factorization. Lattice-based assumptions are believed to resist quantum computers but may not be efficient enough for the blockchain space. Bilinear pair assumptions favored in the blockchain space are in principle attackable by classical computers. Goldwasser has also worked on applying zero-knowledge proofs to legal contexts, including a proposal that wiretaps be stored on a blockchain encrypted until a future date, and a scenario in which the FBI needed to prove it used specific proprietary software to detect illegal activity without revealing the software itself. She collaborated with Guy Rothblum and others on training chatbots to produce a proof alongside every answer, noting that chatbots give correct answers approximately ninety percent of the time on average but not necessarily for any particular prompt, and that she personally spent approximately five thousand to six thousand dollars on lawyers after acting on financial advice from a chatbot that misunderstood a rule.