10 Must-Read Papers That Shaped Modern Zero-Knowledge Proofs

This 2000 paper, written by Micali, is an important contribution in the history of zero-knowledge proofs. It could even be considered the first SNARK construct, although the term SNARK had not yet been coined!

Micali's construction transforms any Probabilistically Checkable Proof (PCP) into a concise and non-interactive proof. PCP is a proof that can be verified by just reading a few bits, and a key result, the PCP Theorem [^7], shows that every language in NP has a proof that can be verified by just reading a Constant bits to verify PCP!

Micali is constructed using a Merkle tree as follows:

• The prover builds a Merkle tree for the proof and sends the root to the verifier,
• Verifiers query for specific bits they wish to check,
  span>
• The prover provides the authentication path of these bits, and the verifier Verify these paths.

This construction can be made non-interactive (such An interactive version of the transformation was proposed by Kilian [^8]). The paper also focuses on computational efficiency: in fact, the verifier does not need to receive the entire proof, but only a constant number of bits and the certification path, which makes the proof compact. The main drawback of this system was that PCP construction was impractical, which led to the development of interactive oracle proofs (IOPs), a generalization of PCP that can produce practical arguments.

5 - Dual efficient IPs

Goldwasser, Kalai, Rothblum - Delegated Computing: Interactive Proofs for Muggles (2015) [^9]

This paper focuses strongly onefficiency and introduces the well-knownGKR protocol, a public coin interactive protocol for available arithmetic circuits. Notably, both the verifier and prover run in polynomial time, making it adoubly efficient interactive proof.

The protocol begins with the prover and verifier agreeing on an arithmetic circuit with input fan-in of 2. The prover then sends the circuit's claimed output given the input values. The protocol proceeds by examining the circuits layer by layer, starting at the output layer and moving toward the input layer. Each step reduces the assertions of the current layer to assertions of the previous layer, until the verifier reaches the input layer, where they can check that it matches the original input.

In each step, the main primitive used is the sum check protocol [^10], which is an interactive Proof that enables the prover to convince the verifier about the sum of values ​​of a v-variable polynomial g with oracle access, defined over a Boolean hypercube:

Due to its efficiency and simplicity, the sum check protocol and the GKR protocol are widely used in practice. For further explanation, an alternative overview of these protocols can be found in Thaler's notes [^11].

6 - The first practical SNARK

Gennaro, Gentry, Parno, Raykova - Quadratic Span Programs and Succinct NIZKs without PCPs (2013) [^12]

We now jump to a paper introducing the first practical SNARK construct! This work marks the culmination of research aimed at creating SNARKs that do not rely on inefficient PCP theorems. While the PCP theorem provided a theoretical SNARK construction, it was too slow for practical applications, so researchers tried to find more efficient alternatives. For example, Groth in 2010 proposed a non-interactive argument system based on bilinear groups and pairings [^13] , although it requires quadratic time on the prover's part. However, this paper achieves linear prover time, representing a significant improvement for practical applications.

This work paved the way for other important protocols, such as thePinocchio Protocol[^14] and the ultimately famousGroth16[^15]  Proof system. The paper also introduces quadratic span programs and quadratic arithmetic programs, constructs that remain crucial in these systems.

A significant disadvantage of these constructs is the need for a trusted setup, which means secret information produced during the public reference string generation phase (often calledToxic Waste) may be used to create false certifications if not destroyed properly. Additionally, this setup is not universal, which means a new setup is required for each circuit. Despite these limitations, the generated proof size is still minimal among different constructions, making it a popular choice for a variety of applications.

It’s also worth mentioning that the first iteration of Zerocash [^16] was an early and influential zone Blockchain applications, utilizing zk-SNARKs, are built on top of these systems.

7 - PlonK SNARK

Gabizon, Williamson, Ciobotaru - PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019) [^17]

This influential 2019 paper introduces PlonK SNARK, a system based on interactive oracle proofs of polynomials (IOPs), which means that the verifier can perform operations on some polynomials oracle access and can evaluate it at selected points. The system uses various polynomial gadgets to prove statements about polynomials, the most notable of which is theLarge Product Argument, which allows the prover to show that the product of evaluations over a domain is 1. Using this, we can construct aPermutation Argument to prove that two sequences are substitutions of each other. Using these gadgets, a prover can construct a proof for any arithmetic circuit and a verifier can verify it in a non-interactive manner.

In practice, oracle access is achieved via the Polynomial Commitment Scheme (PCS), which allows the prover to:

• Commit to a polynomial and
• Provides open values ​​for evaluating the polynomial at a specific point.

This allows the verifier to query the polynomial at any point and verify the IOP relationship. The PCS suggested in the paper is theKZG Commitment Scheme [^18], which is both efficient and practical. KZG enables the prover to commit to a polynomial as a single group element, and the verifier can confirm open values ​​by computing several elliptic curve pairings. Although KZG requires a trusted setup, it is universal and can be used on any circuit once setup. However, PlonK can be combined with other PCS schemes to adapt it to transparent argumentation systems.

Furthermore, the permutation argument in PlonK inspired the find argument. Lookup arguments enable the prover to show that all elements of one sequence are contained in another sequence, which is useful for zkVM architectures. Lookup arguments allow decomposing a witness into smaller trajectories and proving lookup relationships between them, making complex proofs more efficient.

8 - STARKs

Ben-Sasson, Bentov, Horesh, Riabzev - Scalable, transparent, and post-quantum secure computational integrity (2018) [^19]

This paper introduces the STARK proof system, another popular proof system based onFRI [^20], a proximity test for Reed-Solomon codes IOP protocol. In STARKs, the prover commits to the evaluation of a polynomial by constructing a Merkle tree over 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. The protocol also works as a polynomial commitment scheme, allowing the verifier to check the evaluation of the commitment polynomial at any point.

One ​​of the most striking features of STARKs is that they rely solely on cryptographic collision-resistant hash functions and no other cryptography Learning assumptions, such as the discrete logarithm problem. This gives STARKs an advantage in terms of potential post-quantum security, as collision-resistant hash functions are widely considered to be secure even against quantum attacks. Furthermore, STARKs are transparent, i.e. they do not require any trusted setup. They are alsouniversal, meaning they are not restricted to a specific circuit, providing flexibility in a variety of applications.

9 - Recursion

Valiant - Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. (2008) [^21]

An important concept that has emerged over the years is recursion, which simply means that one proof can be used to prove that another proof is correct. The scenario presented in this article involves a prover wishing 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 this is not enough; we want to prove the correctness of the entire computation, which consists of a sequence of state transitions.

Incremental Verifiable Computation (IVC) The idea behind is as follows: Suppose we can prove that a single state transition from S1 to S2 is Correct. We can then combine the two proofs into one: the prover shows that they know two valid proofs:

The merged proof will convince the verifier that the transfer from S1 to S3 is correct. This process can be repeated for any number of steps, allowing us to condense arbitrarily long computations into a single proof (more specifically, polynomially long computations).

It is important to note that this construction relies on two key assumptions:

• Prove the intellectual soundness of the system: The prover must not only prove that a single state transition For proofs to exist, one must also show that they knew about them. Intuitively, through inductive knowledge extractability, we can extract the proofs of all individual state transitions.
• Hash function in practice is a random oracle: This is a stronger assumption, but necessary to verify the correctness of the aggregation proof neutron proof.

Although this construct is powerful in theory, it is costly to apply in practice. To solve this problem, new methods are proposed to improve efficiency. One of them is to use the folding scheme [^22] , which relaxes the assumptions and avoids the need for recursive SNARK verification. The idea of ​​folding is that given two proofs, π and π′, we can “fold” them into a single proof, π″. The verifier believes that if the folded instance is satisfiable, then the original instance is also satisfiable

10 - Verifiable computation via zkVM

Ben-Sasson, Chiesa, Tromer, Virza - Concise non-interactive zero-knowledge for von Neumann architectures (2014) [^23]

This final paper discusses the first practical Zero-Knowledge Virtual Machine (zkVM) construct, which is a A virtual machine that executes arbitrary programs and generates these computational correctness proofs. The machine described follows the von Neumann architecture, which means that programs and data are stored in the same memory. Most modern CPUs are therefore based on this paradigm. 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 shows a C compiler ported to this instruction set. The proof system is designed to verify the correctness of program execution up to a fixed number of steps. The basic idea is that the circuit is constructed as a repeating state transition function, unrolled until it is reached. Instruction count limit.

A key advantage of zkVMs becoming increasingly popular today is that they can be written in high-level programming languages. programs and use them to generate proofs. This provides significant advantages over manually writing circuits because many standard algorithms and data structures are already defined in these high-level languages. Additionally, developers can reuse familiar computational models, which greatly reduces the cost. Learning curve for using zero-knowledge proofs

It is also worth noting that many zk-rollups are based on this model, for example, supporting the Ethereum Virtual Machine (EVM). The executed zk-rollup uses zkVM to prove the correctness of the EVM execution.

Finally, the paper introduces its own architecture, optimized for zero-knowledge proof systems. Another popular example of a zk-friendly architecture is the Cairo CPU architecture [^24] , a Turing-complete CPU optimized for proofs using STARKs.

Reference papers

[^1]: Goldwasser, S., Micali, S., & Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. (link) ↩︎

[^2]: Fiat, A., & Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. (link) ↩︎
[^3]: Goldreich, O., Micali, S., & Wigderson, A. ( 1987). How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. (link) ↩︎
[^4]:  Ben-Or, M., Goldreich, O., Goldwasser, S ., Håstad, J., Kilian, J., Micali, S., & Rogaway, P. (1990). Everything provable is provable in zero-knowledge. (link) ↩︎
[^5]:   Shamir, A. (1992). IP=PSPACE. (link) ↩︎
[^6]: Micali, S. (2000). Computationally sound proofs. ([link](https://people.csail.mit .edu/silvio/Selected Scientific Papers/Proof Systems/Computationally_Sound_Proofs.pdf)) ↩︎
[^7]:  Cook, S. A. (1971). Proof Verification and Hardness of Approximation Problems. (link) ↩︎
[^8]:  Kilian, J. (1992, July). A note on efficient zero-knowledge proofs and arguments. (link) ↩︎
[^9]: Goldwasser, S., Kalai, Y. T., & ; Rothblum, G. N. (2015). Delegating computation: interactive proofs for muggles. (link, see also this note by Justin Thaler) ↩︎
[^10]: Lund, C., Fortnow, L., Karloff, H. , & Nisan, N. (1992). Algebraic methods for interactive proof systems. (link) ↩︎
[^11]: Thaler, J. (2015). A note on the GKR protocol. (link) ↩︎
[^12]: Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013). Quadratic span programs and succinct NIZKs without PCPs. (link) ↩︎
[^13]: Groth, J. (2010). Short pairing-based non-interactive zero-knowledge arguments. (link) ↩︎
[^14]: Parno, B., Howell, J., Gentry, C ., & Raykova, M. (2016). Pinocchio: Nearly practical verifiable computation. (link) ↩︎
[^15]:  Groth, J. (2016). On the size of pairing-based non- interactive arguments. (link) ↩︎
[^16]: Sasson, E. B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014). Zerocash: Decentralized anonymous payments from bitcoin. (link) ↩︎
[^17]: Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. (link) ↩︎
[^18]: Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. (link) ↩︎
[^19]:  Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post- quantum secure computational integrity. (link) ↩︎
[^20]:  Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Fast reed-solomon interactive oracle proofs of proximity. (link) ↩︎
[^21]: Valiant, P. (2008). Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. (link) ↩︎
[^22] : Kothapalli, A., Setty, S., & Tzialla, I. (2022, August). Nova: Recursive zero-knowledge arguments from folding schemes. (link) ↩︎
[^23]: Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014). Succinct Non-Interactive zero knowledge for a von neumann architecture. (link) ↩︎
[^24]: Goldberg, L ., Papini, S., & Riabzev, M. (2021). Cairo–a Turing-complete STARK-friendly CPU architecture. (link) ↩︎