Original author:LambdaClass

Original compilation: mutourend; Yiping, IOSG Ventures

1 Introduction

Zero-knowledge, succinct, non-interactive knowledge proofs (zk-SNARKs) are powerful cryptographic primitives that allow a prover to convince a verifier of the correctness of a statement without revealing any information beyond the statement. zk-SNARKs have received widespread attention due to their applications in verifiable private computation, proof of correctness of computer program execution, and blockchain extensions. We believe that zk-SNARKs, as we describe in our article, will have a significant impact on shaping the world. zk-SNARKs cover different types of proof systems, using different polynomial commitment schemes, arithmetic schemes, interactive oracle proofs or probabilistic testable proofs. But these basic ideas and concepts date back to the mid-1980s.

The development of zk-SNARKs has accelerated significantly since the launch of Bitcoin and Ethereum due to their ability to scale through the use of zero-knowledge proofs (often referred to as validity proofs for this specific use case). zk-SNARKs play a crucial role in blockchain scalability. As Ben-Sasson describes, recent years have seen a Cambrian explosion in cryptographic proofs. Each proof system has advantages and disadvantages, and is designed with specific trade-offs in mind. Advances in hardware, algorithms, new proofs, and tools continue to improve performance and lead to the creation of new systems. Many of these systems are already in use and we continue to push the boundaries. Will we have a universal proof system that works for all applications, or will there be several systems suitable for different needs? We believe that it is highly unlikely that one proof system will dominate all others for several reasons:

1) Diversity of applications.

2) Different types of restrictions (regarding memory, verification duration, proof duration).

3) The need for robustness (if one proof system is broken, there are other proof systems).

Even though proof systems have changed significantly, they all provide an important property: proofs can be quickly verified. Having a layer that validates proofs and can easily adapt to new proof systems solves the difficulties associated with changing base layers such as Ethereum. This article will outline the different characteristics of SNARKs:

1) Cryptographic assumptions: collision-resistant hash function, discrete logarithm problem on elliptic curve, knowledge of exponent.

2) Transparent vs trusted settings.

3) Proof length: linear vs superlinear.

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

5）proof size。

6) Easy to recurse.

7) Arithmetic scheme.

8) Single-variable polynomial vs. multi-variable polynomial.

This article will explore the origins of SNARKs, some basic building blocks, and the rise (and fall) of different proof systems. This article is not intended to provide an exhaustive analysis of proof systems. Instead, focus only on those who have an impact on us. Of course, these developments were only possible through the great work and ideas of pioneers in the field.

2. Basic knowledge

Zero-knowledge proofs are not new. Definitions, foundations, important theorems, and even important protocols were all developed starting in the mid-1980s. Some of the key ideas and protocols used to build modern SNARKs were proposed in the 1990s (sumcheck protocol), even before Bitcoin emerged (GKR in 2007). The main problems with using it are related to the lack of strong use cases (the Internet was not developed in the 1990s) and the required computing power.

1) Zero-knowledge proof: origins (1985/1989).

The field of zero-knowledge proofs appeared in the academic literature with the paper The knowledge complexity of interactive proof systems by Goldwasser, Micali and Rackoff. For a discussion about the origins, you can watch the January 2023 video ZKP MOOC Lecture 1: Introduction and History of ZKP. This paper introduces the concepts of completeness, reliability and zero-knowledge, and provides the construction of quadratic residuosity and quadratic non-residuosity.

2) Sumcheck protocol (1992).

The sumcheck protocol was proposed by Lund, Fortnow, Karloff and Nisan in the 1992 Algebraic Methods for Interactive Proof Systems paper. It is one of the most important building blocks of concise interactive proofs. It helps us reduce the requirement of summing multivariable polynomials to a single evaluation of randomly selected points.

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

The GKR protocol (see paper Delegating Computation: interactive Proofs for Muggles) is an interactive protocol in which the prover operates linearly with the number of gates in the circuit and the verifier operates sublinearly with the size of the circuit. In the protocol, the prover and the verifier reach an agreement on the fan-in-two operation circuit of the finite field with depth d dd, where layer d dd corresponds to the input layer and layer 0 00 corresponds to the output layer. The protocol starts with a statement about the output of the circuit, which is reduced to a statement about the value of the previous layer. Using recursion, this can be transformed into a declaration of the circuits inputs, which can be easily checked. These reductions are implemented through the sumcheck protocol.

4）KZG polynomial commitment scheme ( 2010)。

Kate, Zaverucha, and Goldberg introduced a polynomial commitment scheme using bilinear pairing groups in 2010 Constant-Size Commitments to Polynomials and Their Applications. A commitment consists of a single group element, and the committer effectively opens a commitment to any correct evaluation of the polynomial. Furthermore, thanks to batching technology, multiple evaluations can be opened. The KZG commitment provides one of the basic building blocks for several efficient SNARKs, such as Pinocchio, Groth 16, and Plonk. It is also the core of EIP-4844. To understand batching technology intuitively, see Mina to Ethereum ZK bridge.

3. Practical SNARKs using elliptic curves

The first practical construction of SNARKs appeared in 2013. These constructions require preprocessing steps to generate proofs and verification keys and are program/circuit specific. These keys can be very large and depend on secret parameters that are unknown to all parties; otherwise, proofs can be forged. Transforming code into provable code requires compiling the code into a system of polynomial constraints. Initially, this had to be done manually, which was time-consuming and error-prone. Advances in this field attempt to eliminate some major problems:

1) Have more efficient provers.

2) Reduce the amount of preprocessing.

3) Have setups that are generic rather than circuit specific.

4) Avoid using trusted settings.

5) Develop ways to describe circuits using high-level languages ​​instead of manually writing polynomial constraints.

Currently, practical SNARKs solutions using elliptic curves are:

1）Pinocchio ( 2013)

2）Groth 16 ( 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) is the first practical, usable zk-SNARK. SNARK is based on quadratic arithmetic programs (QAP). The proof size is initially 288 bytes. Pinocchios tool chain provides a compiler from C code to arithmetic circuits and further conversion to QAP. The protocol requires the verifier to generate circuit-specific keys. It uses elliptic curve pairings to check equations. The asymptotics of proof generation and key setting are asymptotically linear with the size of the computation, and the length of verification is linear with the size of the public inputs and outputs.

3.2 Groth 16 ( 2016)

Groths 2016 paper On the Size of Pairing-based Non-interactive Arguments introduced a new knowledge argument that improved the performance of problems described by R 1 CS. It has minimal proof size (only three group elements) and fast verification involving three pairings. It also involves the preprocessing step of obtaining a structured references string. The main disadvantage is that each program to be certified requires a different trusted setup, which is inconvenient. Groth 16 was used in ZCash. For details, please also refer to the blog An overview of the Groth 16 proof system.

3.3 Bulletproofs & IPA ( 2016)

One of the weaknesses of KZG PCS is that it requires a trusted setup. In the 2016 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting paper by Bootle et al., an efficient zero-knowledge argument system for Pedersen commitment openings that satisfies the inner product relationship was introduced. Inner product proof systems have a linear prover, with logarithmic communication and interaction, but with linear duration verification. It also developed a polynomial commitment scheme that does not require a trusted setup. Both Halo 2 and Kimchi adopt the idea of ​​using IPA PCS.

3.4 Sonic, Marlin, and Plonk ( 2019)

Sonic, Plonk, and Marlin solve the problem of trust settings for each program in Groth 16 by introducing a common and updateable structured reference string. Marlin provides a proof system based on R 1 CS, which is the core of Aleo.

Plonk introduced a new arithmetic scheme (later called Plonkish) and used a grand-product check for copy constraints. Plonkish also allows the introduction of specialized doors for certain operations, so-called custom doors. Several projects have customized versions of Plonk, including Aztec, ZK-Sync, Polygon ZKEVM, Minas Kimchi, Plonky 2, Halo 2, and Scroll. See the blog All you wanted to know about Plonk.

3.5 Lookups ( 2018/2020)

Gabizon and Williamson introduced plookups in 2020, using grand product checks to prove that a value is contained in a table of precomputed values. Although lookup arguments were previously proposed in Arya, their construction requires determining the multiplicities of lookups, which is less efficient. The PlonkUp paper shows how to introduce the plookup argument into Plonk. The problem with these lookup arguments is that they force the prover to pay for the entire table, regardless of its number of lookups. This means that the cost of large tables is considerable, and a lot of effort has been put into reducing the cost of the prover to the number of lookups it uses.

Haböck introduced LogUp, which uses logarithmic derivatives to convert product checks into sums of reciprocals. LogUp is critical to the performance of Polygon plonky 2 ZKEVM (Beyond Limits: Pushing the Boundaries of ZK-EVM), which requires splitting the entire table into multiple STARK modules. The modules must be properly linked, and lookups across tables are required to enforce this operation. The launch of LogUp-GKR leverages the GKR protocol to improve the performance of LogUp. Caulk is the first lookup argument whose prover time has a sublinear relationship with table size. Its preprocessing time is O (N log N) and storage is O (N), where N is the table size. Several other solutions followed, such as Baloo, flookup, cq and caulk+. Lasso proposed several improvements to avoid committing a table when it has a given structure. Furthermore, Lassos prover only pays for table entries accessed by lookup operations. Jolt uses Lasso to prove the execution of virtual machines through lookups.

3.6 Spartan ( 2019)

Spartan provides IOPs for circuits described using R 1 CS, taking advantage of the properties of multivariable polynomials and the sumcheck protocol. Using a suitable polynomial commitment scheme, it produces a transparent SNARK with a linear duration prover.

3.7 HyperPlonk ( 2022)

HyperPlonk is built on the idea of ​​Plonk using multivariable polynomials. It does not rely on quotient to check the enforcement of constraints, but relies on the sumcheck protocol. It also supports high degree constraints without hurting the provers running time. Since it relies on multivariable polynomials, there is no need to perform an FFT, and the provers running time scales linearly with circuit size. HyperPlonk introduces new permutation IOPs suitable for smaller domains and a sumcheck-based batch opening protocol, which reduces prover workload, proof size, and verifier time.

3.8 Folding schemes ( 2008/2021)

Nova introduces the idea of ​​folding scheme, which is a new method to implement incremental verifiable computation (IVC). The concept of IVC can be traced back to Valiant, who showed how to combine 2 proofs of length k kk into a single proof of length k kk . The idea is that recursive proof can be used to prove that the execution from step i ii to step i + 1 i+ 1 i+ 1 is correct, and to verify the transition from step i − 1 i-1 i− 1 to step i ii is correct, thus proving the case for any long-running computation.

Nova can handle uniform computations very well; later with the introduction of Supernova, it was extended to handle different types of circuits. Nova uses a relaxed version of R 1 CS and works on friendly elliptic curves. Implementing IVC using friendly curve cycles (e.g., Pasta curves) is also used in Pickles, the main base module of Mina, to achieve concise states. However, the idea of ​​folding is different from recursive SNARK verification. The idea of ​​accumulators is more deeply related to the concept of batching proofs. Halo introduces the concept of accumulation as an alternative to recursive proof combinations. Protostar provides a non-uniform IVC solution for Plonk, supporting high-degree gates and vector lookups.

4. SNARKs using collision-resistant hash functions

Around the same time as Pinocchio was being developed, there were some ideas for generating circuit/arithmetic schemes that could prove the correctness of a virtual machines execution. Although the arithmetic of developing a virtual machine may be more complex or less efficient than writing dedicated circuits for some programs, it provides the advantage that any program, no matter how complex, can be proven by demonstrating that it executes correctly in a virtual machine . The ideas in TinyRAM were later refined with the design of Cairo vm and subsequent virtual machines such as zk-evms or universal zkvms. Using a collision-resistant hash function eliminates the need for a trusted setup or the use of elliptic curve arithmetic, but at the cost of longer proofs.

1）TinyRAM ( 2013)

In SNARKs for C, a PCP-based SNARK is developed to prove the correctness of execution of a C program compiled into TinyRAM (Reduced Instruction Set Computer). The computer uses Harvard architecture with byte-level addressable random access memory. Taking advantage of non-determinism, circuit size scales quasilinearly with computation size, allowing efficient handling of arbitrary data-related loops, control flow, and memory accesses.

2）STARKs ( 2018)

STARKs was proposed by Ben Sasson et al. in 2018. The proof size it implements is O(log 2 n), it has fast provers and verifiers, does not require a trusted setup, and is considered post-quantum safe. It was first used by Starkware/Starknet with the Cairo virtual machine. Its key components include:

• Algebraic Intermediate Representation (AIR)

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

STARKs are also used by other projects (Polygon Miden, Risc 0, Winterfell, Neptune), or some adaptations of them (ZK-Syncs Boojum, Plonky 2, Starky).

3）Ligero ( 2017)

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

• Brakedown builds on Ligero and introduces the idea of ​​domain-independent polynomial commitment schemes.

5. Some new developments in ZKP

Using different proof systems in production shows the advantages of each approach and leads to new developments. For example, plonkish arithmetic provides an easy way to include custom gates and lookup arguments; FRI shows excellent performance as PCS, ahead of Plonky. Likewise, using grand product check in AIR (resulting in randomized AIR with preprocessing) improves its performance and simplifies memory access arguments. Promises based on hash functions have become popular - based on the speed of hash functions in hardware or the introduction of new SNARK friendly hash functions.

1) New polynomial commitment scheme (2023)

With the emergence of efficient SNARKs based on multivariate polynomials (such as Spartan or HyperPlonk), there is increasing interest in new commitment schemes suitable for such polynomials. Binius, Zeromorph, and Basefold all propose new forms dedicated to multilinear polynomials. Binius has the advantage of zero overhead to represent data types (whereas many proof systems use at least 32-bit field elements to represent a single bit) and works on the binary field. The Binius commitment is based on Brakedown and is designed to be domain-agnostic. Basefold generalizes FRI to codes beyond Reed-Solomon, resulting in domain-independent PCS.

2）Customizable Constraint Systems（CCS） ( 2023)

CCS generalizes R 1 CS, capturing R 1 CS, Plonkish, and AIR arithmetic simultaneously without any overhead. Combining CCS with Spartan IOP results in SuperSpartan, which supports high-degree constraints without requiring the prover to incur cryptographic costs that scale with the degree of the constraint. In particular, SuperSpartan generates SNARKs for AIR with a linear time prover.

6 Conclusion

This article describes SNARKs progress since its introduction in the mid-1980s. Advances in computer science, mathematics, and hardware, coupled with the introduction of blockchain, have given rise to new, more efficient SNARKs, opening the door to many applications that could transform our society. Researchers and engineers proposed improvements and adjustments to SNARKs based on their needs, focusing on proof size, memory usage, transparency settings, post-quantum security, prover time, and verifier time.

Although there were initially two main lines (SNARK and STARK), the boundaries between the two have begun to fade, trying to combine the advantages of different proof systems. For example, combining different arithmetic schemes with new polynomial commitment schemes. It can be expected that new proof systems will continue to emerge and performance will improve, and it will be difficult for some systems that require some time to adapt to keep up with these developments, unless the tools can be easily used without changing some core infrastructure.