What makes zero-knowledge proofs continuously innovative and enduring?

Author: LambdaClass

Translation: mutourend; Yiping, IOSG Ventures

1. Introduction

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) are a powerful cryptographic primitive that allows a prover to convince a verifier of the truth of a statement without revealing any information beyond the validity of the statement itself. Due to their applications in verifiable private computation, proving correct execution of computer programs, and blockchain scalability, zk-SNARKs have received widespread attention. We believe, as described in this article, that zk-SNARKs will significantly shape the world. zk-SNARKs encompass various types of proof systems using different polynomial commitment schemes, arithmetization methods, Interactive Oracle Proofs (IOPs), or Probabilistically Checkable Proofs (PCPs). However, these fundamental ideas and concepts trace back to the mid-1980s.

Since the launch of Bitcoin and Ethereum, progress in zk-SNARKs has accelerated dramatically due to their ability to scale blockchains via zero-knowledge proofs—often referred to in this specific context as validity proofs. zk-SNARKs play a crucial role in blockchain scalability. As Ben-Sasson noted, we have recently witnessed a Cambrian explosion of cryptographic proofs. Each proof system comes with its own trade-offs, strengths, and weaknesses, designed with specific constraints in mind. Advances in hardware, algorithms, new proofs, and tooling continuously improve performance and give rise to new systems. Many of these systems are already deployed, and we continue to push boundaries. Will we eventually have one universal proof system for all applications, or will multiple systems coexist for different use cases? We believe it is unlikely that one proof system will dominate all others, due to:

1) The diversity of applications.

2) Different types of constraints (regarding memory, verification time, proof generation time).

3) The need for resilience (if one proof system is compromised, alternatives remain available).

Even though proof systems have evolved significantly, they share an important property: proofs can be verified quickly. Having a layer that verifies proofs and can easily adapt to new proof systems solves the difficulty associated with modifying base layers (like Ethereum). This article outlines key characteristics of SNARKs:

1) Cryptographic assumptions: collision-resistant hash functions, discrete logarithm hardness on elliptic curves, knowledge of exponent assumption.

2) Transparent vs trusted setup.

3) Prover time: linear vs superlinear.

4) Verifier time: constant, logarithmic, sublinear, linear.

5) Proof size.

6) Ease of recursion.

7) Arithmetization schemes.

8) Univariate vs multivariate polynomials.

This article explores the origins of SNARKs, some foundational building blocks, and the emergence (and decline) of different proof systems. It does not aim to provide an exhaustive analysis of proof systems. Instead, it focuses only on those that have influenced us. Of course, these developments were made possible only through the great work and ideas of pioneers in the field.

2. Foundations

Zero-knowledge proofs are not new. Definitions, foundations, key theorems, and even major protocols were established starting in the mid-1980s. Some key ideas and protocols used to build modern SNARKs were proposed in the 1990s (the sumcheck protocol), or even before Bitcoin emerged (GKR in 2007). The main obstacles to their adoption were the lack of compelling use cases (the internet was underdeveloped in the 1990s) and the required computational power.

1) Zero-Knowledge Proofs: Origins (1985/1989)

The field of zero-knowledge proofs entered academic literature with Goldwasser, Micali, and Rackoff’s paper “The Knowledge Complexity of Interactive Proof Systems.” For a discussion on the origins, see the January 2023 video ZKP MOOC Lecture 1: Introduction and History of ZKP. This paper introduced the concepts of completeness, soundness, and zero-knowledge, providing constructions for quadratic residuosity and quadratic non-residuosity.

2) Sumcheck Protocol (1992)

The sumcheck protocol was introduced by Lund, Fortnow, Karloff, and Nisan in their 1992 paper “Algebraic Methods for Interactive Proof Systems.” It is one of the most important building blocks for succinct interactive proofs. It reduces the requirement of summing evaluations of a multivariate polynomial to evaluating it at a single randomly chosen point.

3) Goldwasser-Kalai-Rothblum (GKR) (2007)

The GKR protocol (see paper “Delegating Computation: Interactive Proofs for Muggles”) is an interactive protocol where the prover runs in time linear in the number of gates in the circuit, while the verifier runs in sublinear time relative to the circuit size. In the protocol, the prover and verifier agree on a finite-field fan-in-two arithmetic circuit of depth d, where layer d corresponds to the input layer and layer 0 to the output layer. The protocol starts with a claim about the circuit's output, which is reduced to claims about values in the previous layer. Using recursion, this is transformed into a claim about the circuit inputs, which can then be easily checked. These reductions are achieved via the sumcheck protocol.

4) KZG Polynomial Commitment Scheme (2010)

Kate, Zaverucha, and Goldberg introduced in 2010 a polynomial commitment scheme using bilinear pairing groups in their paper “Constant-Size Commitments to Polynomials and Their Applications.” The commitment consists of a single group element, and the committer can efficiently open the commitment at any correct evaluation of the polynomial. Additionally, batching techniques allow openings at multiple points. The KZG commitment serves as a fundamental building block for several efficient SNARKs such as Pinocchio, Groth16, and Plonk. It is also central to EIP-4844. For an intuitive understanding of batching, see the Mina-to-Ethereum ZK bridge.

3. Practical SNARKs Using Elliptic Curves

The first practical constructions of SNARKs appeared in 2013. These constructions require a preprocessing step to generate proving and verification keys and are program/circuit-specific. These keys can be very large and depend on secret parameters unknown to all parties; otherwise, proofs could be forged. Converting code into provable form requires compiling it into a polynomial constraint system. Initially, this had to be done manually—time-consuming and error-prone. Progress in the field aimed to address several key issues:

1) More efficient provers.

2) Reduced preprocessing overhead.

3) Universal rather than circuit-specific setups.

4) Avoidance of trusted setup.

5) Development of methods to describe circuits using high-level languages instead of manually writing polynomial constraints.

Currently, practical SNARKs using elliptic curves include:

1) Pinocchio (2013)

2) Groth16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin, and Plonk (2019)

5) Lookups (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) Folding Schemes (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (see paper “Pinocchio: Nearly Practical Verifiable Computation”) was the first practical and usable zk-SNARK. The SNARK is based on Quadratic Arithmetic Programs (QAP). Initial proof size was 288 bytes. Pinocchio’s toolchain provided a compiler from C code to arithmetic circuits, and further transformation into QAP. The protocol requires the verifier to generate circuit-specific keys. It uses elliptic curve pairings to check equations. The asymptotic complexity of proof generation and key setup scales linearly with computation size, while verification time scales linearly with the size of public inputs and outputs.

3.2 Groth16 (2016)

Groth’s 2016 paper “On the Size of Pairing-based Non-interactive Arguments” introduced a new argument of knowledge that improved performance for problems described via Rank-1 Constraint Systems (R1CS). It features minimal proof size (only three group elements) and fast verification involving three pairings. It also involves a preprocessing step to obtain a structured reference string. The main drawback is that each program to be proven requires a separate trusted setup, which is inconvenient. Groth16 was used in ZCash. See blog post “An overview of the Groth 16 proof system” for more details.

3.3 Bulletproofs & IPA (2016)

One weakness of the KZG PCS is its reliance on trusted setup. Bootle et al. in their 2016 paper “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting” introduced an efficient zero-knowledge argument system for Pedersen commitments satisfying inner product relations. The inner product proof system has a linear-time prover, logarithmic communication and interaction, but linear-time verification. It also developed a polynomial commitment scheme that does not require trusted setup. Both Halo2 and Kimchi adopt ideas from IPA PCS.

3.4 Sonic, Marlin, and Plonk (2019)

Sonic, Plonk, and Marlin addressed the per-program trusted setup issue in Groth16 by introducing universal and updatable structured reference strings. Marlin provides an R1CS-based proof system and is core to Aleo.

Plonk introduced a new arithmetization scheme (later called Plonkish) and used a grand-product check for copy constraints. Plonkish also allows specialized gates for certain operations, known as custom gates. Multiple projects have customized versions of Plonk, including Aztec, ZK-Sync, Polygon ZKEVM, Mina’s Kimchi, Plonky2, Halo2, and Scroll. See blog “All you wanted to know about Plonk.”

3.5 Lookups (2018/2020)

Gabizon and Williamson introduced plookup in 2020, using a grand product check to prove that a value belongs to a precomputed table. Although lookup arguments were previously proposed in Arya, their construction required determining multiplicities of lookups and was less efficient. The PlonkUp paper showed how to integrate the plookup argument into Plonk. A key issue with these lookup arguments is that they force the prover to pay costs for the entire table regardless of how many lookups are performed. This makes large tables expensive, prompting significant efforts to reduce prover cost to scale with the number of actual lookups.

Haböck introduced LogUp, which uses logarithmic derivatives to convert product checks into sums of reciprocals. LogUp is critical to the performance of Polygon’s plonky2 ZKEVM (“Beyond Limits: Pushing the Boundaries of ZK-EVM”), which requires splitting the entire table across multiple STARK modules. These modules must be correctly linked, reinforced via cross-table lookups. The introduction of LogUp-GKR leverages the GKR protocol to boost LogUp performance. Caulk is the first lookup argument with prover time sublinear in table size, with preprocessing O(N log N) and storage O(N), where N is the table size. Several other schemes followed, such as Baloo, flookup, cq, and caulk+. Lasso introduced multiple improvements, avoiding commitment to the table when it has a given structure. Moreover, Lasso’s prover pays only for table entries accessed during lookups. Jolt leverages Lasso to prove virtual machine execution via lookups.

3.6 Spartan (2019)

Spartan provides an IOP for circuits described using R1CS, leveraging properties of multivariate polynomials and the sumcheck protocol. When combined with a suitable polynomial commitment scheme, it yields a transparent SNARK with a linear-time prover.

3.7 HyperPlonk (2022)

HyperPlonk builds on Plonk’s ideas using multivariate polynomials. Instead of relying on quotients to verify constraint satisfaction, it uses the sumcheck protocol. It supports high-degree constraints without compromising prover runtime. Since it relies on multivariate polynomials, no FFT is needed, and prover runtime scales linearly with circuit size. HyperPlonk introduces a new permutation IOP suitable for small fields and a sumcheck-based batch opening protocol, reducing prover workload, proof size, and verifier time.

3.8 Folding Schemes (2008/2021)

Nova introduced the idea of folding schemes—a new method for achieving Incrementally Verifiable Computation (IVC). The concept of IVC dates back to Valiant, who showed how to combine two proofs of length k into a single proof of length k. The idea is that correctness of a long-running computation can be proven by recursively verifying that each step from i to i+1 is correct and that the transition proof from i−1 to i is valid.

Nova handles uniform computations well; later extended via Supernova to support different circuit types. Nova uses a relaxed version of R1CS and operates over friendly elliptic curves. Using cycles of friendly curves (e.g., Pasta curves) for IVC was also employed in Pickles, a core building block of Mina for achieving succinct state. However, folding differs from recursive SNARK verification. The accumulator concept is more deeply connected to batching proofs. Halo introduced accumulation as an alternative to recursive proof composition. Protostar provides a non-uniform IVC scheme for Plonk, supporting high-degree gates and vector lookups.

4. SNARKs Using Collision-Resistant Hash Functions

Around the same time as Pinocchio’s development, ideas emerged for generating circuits/arithmetizations capable of proving correct execution of virtual machines. While arithmetizing a VM may be more complex or less efficient than designing dedicated circuits for specific programs, it offers the advantage that any program, no matter how complex, can be proven by showing its correct execution within the VM. Ideas from TinyRAM were later refined with designs like Cairo VM and subsequent virtual machines (e.g., zk-EVMs or general-purpose zkVMs). Using collision-resistant hash functions eliminates the need for trusted setup or elliptic curve operations, at the cost of longer proofs.

1) TinyRAM (2013)

In “SNARKs for C,” a PCP-based SNARK was developed to prove correct execution of C programs compiled into TinyRAM (a reduced instruction set computer). This machine uses Harvard architecture with byte-addressable random-access memory. By leveraging nondeterminism, the circuit size grows quasilinearly with computation size, efficiently handling arbitrary and data-dependent loops, control flow, and memory access.

2) STARKs (2018)

STARKs were introduced by Ben-Sasson et al. in 2018. They achieve proof size O(log²n), with fast provers and verifiers, require no trusted setup, and are considered post-quantum secure. First implemented by Starkware/Starknet alongside the Cairo virtual machine. Key components include:

• Algebraic Intermediate Representation (AIR)

• FRI protocol (Fast Reed-Solomon Interactive Oracle Proof of Proximity).

STARKs are also used by other projects (Polygon Miden, Risc0, Winterfell, Neptune) or adapted in variants (ZK-Sync’s Boojum, Plonky2, Starky).

3) Ligero (2017)

• Ligero introduced a proof system with proof size O(√n), where n is the circuit size. It arranges polynomial coefficients in matrix form and uses linear codes.

• Brakedown builds on Ligero and introduces domain-agnostic polynomial commitment schemes.

5. Recent Advances in ZKPs

Deploying different proof systems in production has revealed the strengths of each approach and driven new developments. For example, Plonkish arithmetization provides a simple way to incorporate custom gates and lookup arguments; FRI as a PCS has shown excellent performance, leading Plonky. Similarly, using grand product checks in AIR (leading to randomized AIR with preprocessing) improves performance and simplifies memory access arguments. Hash-function-based commitments have gained popularity—driven by hardware speed of hash functions or the introduction of new SNARK-friendly hash functions.

1) New Polynomial Commitment Schemes (2023)

With the emergence of efficient SNARKs based on multivariate polynomials (e.g., Spartan or HyperPlonk), interest has grown in new commitment schemes suited for such polynomials. Binius, Zeromorph, and Basefold all propose novel approaches targeting multilinear polynomials. Binius has the advantage of zero overhead for representing data types (while many proof systems use at least 32-bit field elements to represent a single bit) and operates over binary fields. Binius commitments are based on Brakedown and designed to be domain-agnostic. Basefold generalizes FRI beyond Reed-Solomon codes, forming a domain-agnostic PCS.

2) Customizable Constraint Systems (CCS) (2023)

CCS generalizes R1CS while capturing R1CS, Plonkish, and AIR arithmetization without overhead. Combining CCS with the Spartan IOP yields SuperSpartan, which supports high-degree constraints without imposing cryptographic costs on the prover that scale with constraint degree. In particular, SuperSpartan generates SNARKs for AIR with linear-time provers.

6. Conclusion

This article describes the evolution of SNARKs since their inception in the mid-1980s. Advances in computer science, mathematics, and hardware, combined with the advent of blockchains, have led to new and more efficient SNARKs, opening doors to many applications that could transform society. Researchers and engineers have proposed improvements and adaptations tailored to specific needs, focusing on proof size, memory usage, transparent setup, post-quantum security, prover time, and verifier time.

While initially two main lines existed (SNARKs vs STARKs), the boundary between them is blurring, with efforts to combine advantages from different proof systems. For instance, integrating different arithmetization schemes with new polynomial commitment schemes. We can expect new proof systems to continue emerging with improved performance, while systems requiring significant adaptation may struggle to keep pace unless tools make integration easy without changing core infrastructure.