IOSG: What is the driving force for continuous innovation in zero-knowledge proofs?

Author: LambdaClass

Translation: mutourend; Yiping, IOSG Ventures

1. Introduction

Zero-knowledge, concise, non-interactive knowledge proof (zk-SNARKs) , is a powerful cryptographic primitive that allows 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 computer program execution correctness, 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 vital role in blockchain scalability. As Ben-Sasson states, 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 share one important characteristic: fast verifiability. Difficulties associated with modifying base layers such as Ethereum can be solved by having a layer that verifies proofs and can flexibly adapt to new proof systems. This article will briefly outline the various characteristics of SNARKs:

1) Cryptographical 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.

2. Basic knowledge

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 proof 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 multivariate polynomial evaluations 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 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 circuit's 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 Constant-Size Commitments to Polynomials and Their Applications in 2010. A commitment consists of a single group element, and the committer effectively opens a commitment to any correct evaluation of the polynomial. In addition, 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.

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 the field attempt to eliminate some major problems:

1) Having more efficient provers.

2) Reduce the amount of preprocessing.

3) Have universal rather than circuit specific setups.

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 and 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 into 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 setup 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)

Groth’s 2016 paper On the Size of Pairing-based Non-interactive Arguments introduces a new knowledge argument that improves the performance of problems described by R1CS . 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. 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. 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 trustworthiness of each program in Groth16 by introducing a universal and updateable structured reference string. Setting issues. 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 checks to prove that a certain value is contained in a table of precomputed values. Although lookup arguments have been proposed in Arya before, 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 introduces 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 launch of LogUp-GKR leverages the GKR protocol to improve the performance of LogUp. Caulk is the first lookup argument in which the prover time has a sublinear relationship with the table size. Its preprocessing time is ‍O (N log ⁡ N) and the 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, Lasso's 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 R1CS, 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 multi-variable polynomials. It does not rely on quotient to check the enforcement of constraints, but 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 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 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 very 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.

4. SNARKs using collision-resistant hash functions

Around the same time as Pinocchio was being developed, there were some ideas for generating circuits/arithmetic schemes that could prove the correctness of virtual machine 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 C program execution, which is compiled into TinyRAM (simplified instruction set computer). The computer uses Harvard architecture with byte-level addressable random access memory. Taking advantage of non-determinism, the size of the circuit is quasilinearly related to the size of the computation, thereby efficiently handling 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(log2n), 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, 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.

5. Some new developments in ZKP

Using different proof systems in production shows the advantages of each method and brings new developments. For example, plonkish arithmetic provides an easy way to include custom gates and lookup arguments; FRI as PCS shows excellent performance, 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 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 schemes (2023)

With the emergence of efficient SNARKs based on multivariable polynomials (such as Spartan or HyperPlonk), people are interested in new commitment schemes suitable for such polynomials More and more interested. Binius, Zeromorph and Basefold all propose new forms dedicated to multilinear polynomials. Binius has the advantage of representing data types with zero overhead (while many proof systems use at least 32-bit field elements to represent a single bit) and works on the binary field. Binius promises to be 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, capturing R1CS, 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 bear 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 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 IOSG: What is the driving force for continuous innovation in zero-knowledge proofs?. For more information, please follow other related articles on the PHP Chinese website!