Written by: LambdaClass
Compiled by: mutourend; Yiping, IOSG Ventures
Zero-knowledge, succinct, non-interactive knowledge proofs (zk-SNARKs) are a powerful cryptographic primitive that allow the prover to convince the verifier of a certain statement correctness without disclosing any information other than 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 greatly accelerated 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 of 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 think it is very unlikely that one proof system will dominate all others, for reasons including:
1) Diversity of applications.
2) Different restriction types (regarding memory, verification duration, proof duration).
3) The need for robustness (if one proof system is broken, there are other proof systems).
Although proof systems may undergo significant changes, they still share an important property: rapid verifiability of proofs. The difficulties associated with changing base layers such as Ethereum are solved in a layer that can verify proofs and easily adapt to new proof systems. This article will provide a brief overview of the various 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) Univariable polynomial vs multivariable 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.
Zero-knowledge proofs are not new. Definitions, foundations, important theorems, and even important protocols were 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 existed (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 proofs: Origins (1985/1989).
The field of zero-knowledge proofs emerged in the academic literature with the paper "The knowledge complexity of interactive proof systems" by Goldwasser, Micali and Rackoff. For a discussion of the origins, watch the January 2023 video ZKP MOOC Lecture 1: Introduction and History of ZKP. This paper introduces the concepts of ploidy, 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 summation of multivariate polynomials to a single evaluation of randomly selected points.
3) Goldwasser-Kalai-Rothblum (GKR) (2007).
The GKR protocol (see the 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 agree 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 circuit's inputs, which can be easily checked. These reductions are implemented via 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, Groth16, and Plonk. It is also the core of EIP-4844. To understand batching technology intuitively, see Mina to Ethereum ZK bridge.
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 the field attempt to eliminate some major problems:
1) Having 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. Pinocchio's toolchain provides a compiler from C code to arithmetic circuits and further translation to QAP. The protocol requires the verifier to generate circuit-specific keys. It uses elliptic curve pairings to check equations. Asymptotic asymptotics for proof generation and key setting scale linearly with computation size, and verification duration scales linearly with the size of the public inputs and outputs.
3.2 Groth 16 (2016)
Groth’s 2016 paper On the Size of Pairing-based Non-interactive Arguments introduces a new knowledge argument that improves The performance of the problem is described by R1CS. It has minimal proof size (only three group elements) and fast verification involving three pairings. It also involves preprocessing steps to obtain a string of structured references. The main disadvantage is that each program to be certified requires a different trusted setup, which is inconvenient. Groth16 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. Bootle et al.'s 2016 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting paper introduced an efficient zero-knowledge argument system for Pedersen commitment openings that satisfies the inner product relationship. 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 IPA PCS idea.
3.4 Sonic, Marlin, and Plonk (2019)
Sonic, Plonk and Marlin solve the problem of Groth16 by introducing a universal and updateable structured reference string. Issues with trusted settings for each program. Marlin provides a proof system based on R1CS, 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 custom versions of Plonk, including Aztec, ZK-Sync, Polygon ZKEVM, Mina’s Kimchi, Plonky2, Halo 2, and Scroll, among others. 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 check to prove that a certain value is contained in a pre-computed value table. Although lookup arguments were previously proposed in Arya, their construction required determining the multiplicities of the lookups, which was 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 plonky2 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 introduction 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, with preprocessing time of O ( N log N ) and storage of 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, Lasso's prover only pays for table entries accessed by lookup operations. Jolt leverages Lasso to prove virtual machine execution through lookups.
3.6 Spartan (2019)
Spartan provides IOPs for circuits described using R1CS, leveraging 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 quotients to check the enforcement of constraints, but instead relies on the sumcheck protocol. It also supports high degree constraints without hurting the prover's running time. Since it relies on multivariable polynomials, there is no need to perform an FFT, and the prover's 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 schemes, which is a new method to implement incremental verifiable computation (IVC) . The concept of IVC goes 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 1i 1 is correct, and to verify that the transition proof from step i − 1 i-1i−1 to step i ii is correct. , thus proving any long-running computation.
Nova can handle uniform computations well; later with the introduction of Supernova, it was extended to handle different types of circuits. Nova uses a relaxed version of R1CS and works on friendly elliptic curves. Using friendly curve cycles (e.g., Pasta curves) to implement IVC 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.
Around the same time as Pinocchio's development, there were some ideas for generating circuits/arithmetic schemes that could prove the correctness of a virtual machine's 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 generic 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 for TinyRAM (Reduced Instruction Set Computer). The computer uses Harvard architecture with byte-level addressable random access memory. Leveraging 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. Its implementation has a proof size of O(log2n), has fast provers and verifiers, does not require a trusted setup, and is considered post-quantum secure. 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, Risc0, Winterfell, Neptune), or some adaptations of them (ZK-Sync's Boojum, Plonky2, Starky).
3) Ligero (2017)
Ligero introduces 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.
Using different proof systems in production shows the advantages of each method 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 arguments) improves its performance and simplifies memory access arguments. Promises based on hash functions have caught on - either 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 (while many proof systems use at least 32-bit field elements to represent a single bit) and works on the binary domain. The Binius promise 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 R1CS while capturing R1CS, Plonkish and AIR arithmetic 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.
This article describes the progress of SNARK 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.
The above is the detailed content of Explore the real reasons behind the emergence of timeless innovations in zero-knowledge proofs. For more information, please follow other related articles on the PHP Chinese website!