Zero-knowledge proofs have evolved remarkably over nearly 40 years, achieving unprecedented levels of sophistication and efficiency. Today, new papers and projects emerge daily, building on a rich foundation of ideas and innovations.

Curious about how it all started? In this post, we’ll dive into the history of zero-knowledge proofs, exploring 10 milestone papers that helped shape the field as we know it.

#1 - The origins

Goldwasser, Micali, Rackoff - The knowledge complexity of interactive proof-systems (1985) ¹

Our first milestone takes us back to the paper that started it all in 1985! This work introduced much of the terminology and foundational concepts that remain central to zero-knowledge proofs today.

To begin with, the paper defines a proof system modeled as a two-party protocol involving two probabilistic Turing machines: a Prover and a Verifier. The objective of a proof system for a formal language $L$ is to enable the Prover to convince the Verifier that a given input $x$ belongs to $L$. In most early works, the Prover is computationally unbounded, while the Verifier is limited to polynomial-time computation. At the end of the interaction, the Verifier outputs either “accept” or “reject.”

A proof system has two main properties: completeness (if $x \in L$, then the Verifier accepts with high probability) and soundness (if the Prover attempts to cheat and $x \notin L$, the Verifier rejects with high probability). One trivial proof system involves the Prover simply sending the witness $w$ to the Verifier. However, this approach reveals information or knowledge about the witness to the Verifier. To formalize this notion, the paper introduces knowledge complexity: $KC(f(x))$ represents the class of languages that admit a proof system where the Prover communicates at most $f(n)$ bits of knowledge about its input $x$.

Are there languages within $KC(0)$, meaning they admit a zero-knowledge proof system? Remarkably, there are! The paper presents a famous example involving a proof system for quadratic residuosity, where the Prover can convince the Verifier that a given number $x$ is a quadratic residue modulo a composite number $n$ without revealing any additional knowledge about $x$.

#2 - The first application

Fiat, Shamir - How to prove yourself: Practical solutions to identification and signature problems (1986) ²

This paper by Fiat and Shamir, published just a year after the foundational work on zero-knowledge proofs, introduced the first practical application of these concepts. They proposed two protocols: an identification scheme, which is interactive, and a signature scheme, which is non-interactive. The key difference between the two is that in an identification scheme, a third party could convince themselves of a false statement by crafting a valid transcript. In a signature protocol, even a dishonest prover cannot convince themselves of a false statement, making signatures unforgeable.

The identification scheme applies the quadratic residuosity proof system as an interactive protocol, where the Verifier sends random challenges, and the Prover responds accordingly. The signature scheme modifies this by replacing the Verifier’s challenges with a call to a hash function.

Do the authors’ names sound familiar? This is the first instance of a powerful general technique, now widely known as the Fiat-Shamir heuristic. It enables converting any public-coin interactive proof system into a non-interactive one by replacing the Verifier’s challenges with a query to a random oracle (in practice, a cryptographic hash function).

#3 - What exactly can we prove?

Goldreich, Micali, Wigderson - How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design (1987) ³

This 1986 paper gives a remarkable result: every language in $NP$ admits a zero-knowledge proof system. This is significant because it means we can prove the truth of any statement verifiable in polynomial time without revealing additional information. The authors show this by providing a proof system for graph 3-colorability, the problem of determining whether the nodes of a graph can be colored with three colors such that no two adjacent nodes share the same color. Moreover, the proof only assumes the existence of probabilistic encryption.

The intuition for the proof is as follows: in each round,

• the Prover selects a random permutation of the three colors,
• the Prover commits to the permuted color of each node,
• the Verifier queries two adjacent nodes and asks for their colors,
• the Prover opens the commitment by revealing the colors of the queried nodes.
• If the colors match, the Verifier immediately rejects.

By running this protocol a polynomial number of times, the Verifier is convinced that the Prover knows a valid 3-coloring with high probability, without learning any information since the opened colors are randomized each step!

Also notable in this line of work are two other papers: Everything Provable is Provable in Zero-Knowledge ⁴, which shows that every language in $IP$ has a zero-knowledge proof system, and IP = PSPACE ⁵, showing that $IP$ is as powerful as $PSPACE$.

#4 - PCPs and the origins of succinct and non-interactive proofs

Micali - Computationally sound proofs (2000) ⁶

This 2000 paper by Micali is an important contribution to the history of zero-knowledge proofs. It could even be considered the first SNARK construction, though the term SNARK hadn’t yet been coined!

Micali’s construction transforms any Probabilistically Checkable Proof (PCP) into a succinct and non-interactive proof. PCPs are proofs that can be verified by reading only a few bits, and a key result, known as the PCP theorem ⁷, shows that every language in $NP$ has a PCP that can be verified by reading only a constant number of bits from the proof!

Micali’s construction uses Merkle trees as follows:

• the Prover constructs a Merkle tree for the proof and sends the root to the Verifier,
• the Verifier queries specific bits they wish to check,
• the Prover provides authentication paths for those bits, and the Verifier verifies the paths.

This construction can be made non-interactive by a straightforward application of the Fiat-Shamir heuristic (one interactive version of this transformation is due to Kilian ⁸). The paper also focuses on the computational efficiency: indeed the verifier does not need to receive the whole proof, but only a contant number of bits and the authentication paths, which makes the proof succinct. The main disadvantage of this system is that PCP constructions are impractical, which was the motivation behind the development of Interactive Oracle Proofs (IOPs), a generalization of PCPs that can yield practical arguments.

#5 - Doubly-efficient IPs

Goldwasser, Kalai, Rothblum - Delegating Computation: Interactive Proofs for Muggles (2015) ⁹

This paper takes a strong focus on efficiency and introduces what’s widely known as the GKR protocol, a public-coin interactive protocol for languages computable with arithmetic circuits. Notably, both the Verifier and Prover run in polynomial time, making it a doubly-efficient interactive proof.

The protocol begins with the Prover and Verifier agreeing on an arithmetic circuit of fan-in 2. The Prover then sends the claimed output of the circuit for a given input value. The protocol proceeds by examining the circuit layer by layer, starting from the output layer and moving towards the input layer. Each step reduces the claim for the current layer to a claim about the previous layer, until the Verifier reaches the input, where they can check that it matches the original input.

At each step, the main primitive used is the sum-check protocol ¹⁰, an interactive proof enabling a Prover to convince a Verifier of the sum of the values of a $v$-variate polynomial $g$, to which the Verifier has oracle access, over the boolean hypercube: $$ H = \sum_{b_1 \in {0,1}} \sum_{b_2 \in {0,1}} \dots \sum_{b_v \in {0,1}} g(b_1, b_2, \dots, b_v) $$

Due to its efficiency and simplicity, both the sum-check and GKR protocols are widely used in practice. For further explanation, an alternative overview of these protocols can be found in a note by Thaler ¹¹.

#6 - The first practical SNARK

Gennaro, Gentry, Parno, Raykova - Quadratic Span Programs and Succinct NIZKs without PCPs (2013) ¹²

We now leap forward to a paper that introduces one of the first practical SNARK constructions! This work marks the culmination of a lineage of research aiming to create SNARKs without relying on the inefficient PCP theorem. While the PCP theorem offers a theoretical SNARK construction, it’s far too slow for practical applications, so researchers have tried to find more efficient alternatives. For instance, Groth proposed a non-interactive argument system in 2010 based on bilinear groups and pairings¹³, though it required quadratic time for the Prover. This paper, however, achieves a linear Prover time, representing a major improvement for practical use.

This work paved the way for other significant protocols, such as the Pinocchio protocol¹⁴, and ultimately the well-known Groth16¹⁵ proof system. The paper also introduces Quadratic Span Programs and Quadratic Arithmetic Programs, essential constructions still used in these systems.

A notable downside of these constructions is the requirement for a trusted setup, meaning that the Common Reference String generation phase produces secret information (often called toxic waste) that could be used to create false proofs if not properly destroyed. Moreover, this setup isn’t universal, meaning a new setup is required for each circuit to be supported. Despite these limitations, the resulting proof size remains the smallest among the differnt constructions, making it a popular choice for various applications.

It’s also worth mentioning that the first iteration of Zerocash ¹⁶, an early and influential blockchain application utilizing zk-SNARKs, was built on these systems.

#7 - The PlonK SNARK

Gabizon, Williamson, Ciobotaru - PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019) ¹⁷

This influential paper from 2019 introduces the PlonK SNARK, a system based on polynomial Interactive Oracle Proofs (IOPs), which means that the Verifier has oracle access to some polynomials and can evaluate them at chosen points. The system uses various polynomial gadgets to prove statements about polynomials, the most notable of which is the Grand Product Argument, allowing the Prover to show that the product of evaluations over a domain is one. Using this, we can construct a permutation argument to prove that two sequences are permutations of each other. Using these gadgets, the Prover can construct a proof for any arithmetic circuit, and the Verifier can verify it in a non-interactive manner.

In practice, oracle access is achieved through a Polynomial Commitment Scheme (PCS), which allows the Prover to:

• commit to a polynomial, and
• provide openings for evaluating that polynomial at specific points.

This allows the Verifier to query the polynomial at any point and verify the IOP’s relations. The PCS suggested in the paper is the KZG commitment scheme ¹⁸, which is both efficient and practical. KZG enables the Prover’s commitment to a polynomial as a single group element, and the Verifier can confirm openings by computing a few elliptic curve pairings. While KZG requires a trusted setup, it is universal, and can be used for any circuit after the setup. However, PlonK can be combined with other PCS schemes, making it adaptable to transparent argument systems.

Additionally, the permutation argument in PlonK inspired lookup arguments. A lookup argument enables the Prover to show that all elements of one sequence are contained within another sequence, which is highly useful fpr zkVM architectures. Lookup arguments allow for breaking down the witness into smaller traces and proving lookup relations between them, making complex proofs more efficient.

#8 - STARKs

Ben-Sasson, Bentov, Horesh, Riabzev - Scalable, transparent, and post-quantum secure computational integrity (2018) ¹⁹

This paper introduces the STARK proof system, another popular proof system that is based on FRI ²⁰, an IOP protocol for proximity testing of Reed-Solomon codes. In STARKs, the Prover commits to polynomials by constructing Merkle trees over the polynomial’s evaluations on a domain. Since the committed values are initially unknown, the Verifier uses FRI to confirm that these evaluations form a valid polynomial of sufficiently low degree. This protocol can also serve as a Polynomial Commitment Scheme, allowing the Verifier to check a committed polynomial’s evaluation at any point.

One of STARKs’ most compelling features is their reliance only on cryptographic collision-resistant hash functions rather than other cryptographic assumptions such as the discrete logarithm problem. This makes STARKs potentially post-quantum secure, as collision-resistant hash functions are widely considered secure even against quantum attacks. Additionally, STARKs are transparent, i.e., they do not require any trusted setup. They are also universal, meaning they aren’t restricted to a specific circuit, providing flexibility across various applications.

#9 - Recursion

Valiant - Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. (2008) ²¹

A significant concept that emerged over the years is recursion, which, in simple terms, means that a proof can be used to prove the correctness of another proof. The scenario presented in this paper involves a Prover wanting to prove the correctness of the result of a potentially long computation. Given a Turing machine, we can prove the correctness of a single step of the state transition function, but that’s not enough; we want to prove the correctness of the entire computation, which consists of a sequence of state transitions.

The idea behind Incrementally Verifiable Computation (IVC) is as follows: suppose we can prove that a single state transition, from $S_1$ to $S_2$, is correct. We can then merge two proofs into one: the Prover shows that they know two valid proofs:

• $\pi$ for the state transition from $S_1$ to $S_2$, and
• $\pi’$ for the state transition from $S_2$ to $S_3$.

The combined proof will convince the Verifier that the transition from $S_1$ to $S_3$ is correct. This process can be repeated for any number of steps, allowing us to compress arbitrarily long computations into a single proof (more specifically, polynomially long computations).

It’s important to note that this construction relies on two critical assumptions:

• Knowledge soundness of the proof system: The Prover must not only prove the existence of proofs for the individual state transitions but also prove that they know the proofs. The intuition is that, with knowledge extractability by induction, we can extract all the individual state transition proofs.
• Hash functions in practice are random oracles: This is a much stronger assumption but is necessary for verifying the correctness of the sub-proofs within the aggregation proof.

Although this construction is theoretically powerful, it is costly to apply in practice. To address this, new methods have been proposed to improve efficiency. One of these is the use of folding schemes ²², which relax the assumptions and avoid the need for recursive SNARK verification. The idea behind folding is that, given two proofs, $\pi$ and $\pi’$, we can “fold” them into a single proof, $\pi’’$. The Verifier is convinced that if the folded instance is satisfiable, the original instances are also satisfiable.

#10 - Verifiable computation through zkVMs

Ben-Sasson, Chiesa, Tromer, Virza - Succinct Non-Interactive zero knowledge for a von neumann architecture (2014) ²³

This final paper discusses the first practical construction of a zero-knowledge Virtual Machine (zkVM), a virtual machine capable of executing arbitrary programs and generating proofs for the correctness of those computations. The machine described follows a von Neumann architecture, meaning both the program and the data are stored in the same memory. Most modern CPUs operate based on this paradigm, so, in theory, any program that can run on a classical computer can also run on this architecture.

The paper introduces a RISC architecture called vnTinyRAM and presents a C compiler ported to target this instruction set. The proof system is designed to verify the correctness of program execution up to a fixed number of steps. The underlying idea is that the circuit is constructed as a repeated state transition function, unrolled until the instruction count limit is reached.

Today, zkVMs are increasingly popular. One of their key advantages is that users can write programs in high-level programming languages and use them to generate proofs. This provides a significant advantage over manually writing circuits, as many standard algorithms and data structures are already defined in these high-level languages. Additionally, developers can reuse a familiar model of computation, which greatly reduces the learning curve associated with using zero-knowledge proofs.

It is also worth noting that many zk-rollups are based on this model. For instance, zk-rollups supporting Ethereum Virtual Machine (EVM) executions use zkVMs to prove the correctness of EVM execution.

Lastly, the paper introduced its own architecture, optimized for use in zero-knowledge proof systems. Another popular example of a zk-friendly architecture is the Cairo CPU architecture ²⁴, a Turing-complete CPU optimized to be proven using STARKs.