Original Author: LambdaClass

Original Translation: mutourend; Yiping, IOSG Ventures

1. Introduction

Zero-knowledge, succinct, non-interactive knowledge proofs (zk-SNARKs) are 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 itself. Due to their applications in verifiable private computation, proving the correctness of computer program execution, and blockchain scalability, zk-SNARKs have garnered widespread attention. We believe that, as we describe in this article, zk-SNARKs will have a significant impact on shaping the world. zk-SNARKs encompass different types of proof systems, using different polynomial commitment schemes, arithmetic schemes, interactive oracle proofs, or probabilistically checkable proofs. However, these fundamental ideas and concepts can be traced back to the mid-1980s.

Since the introduction of Bitcoin and Ethereum, the development of zk-SNARKs has greatly accelerated, as they can be extended using 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 described, there has been a Cambrian explosion of cryptographic proofs in recent years. Each proof system has its advantages and disadvantages, and specific trade-offs are considered in their design. Advances in hardware, algorithms, new proofs, and tools continuously improve performance and give rise to 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 applies to all applications, or will there be several systems for different needs? We believe the possibility of a proof system that can dominate all other systems is small, for reasons including:

1) Diversity of applications.

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

3) Need for robustness (if one proof system is compromised, there are others).

Even as proof systems undergo significant changes, they provide an important feature: proofs can be quickly verified. Having a layer that can verify proofs and easily adapt to new proof systems solves the difficulties associated with changing the base layer (such as Ethereum). This article will outline the different features of SNARKs:

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

2) Transparent vs trusted setups.

3) Proof time: linear vs superlinear.

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

5) Proof size.

6) Ease of recursion.

7) Arithmetic schemes.

8) Univariate polynomials vs multivariate polynomials.

This article will explore the origins of SNARKs, some basic building blocks, and the rise (and fall) of different proof systems. This article does not intend to provide a comprehensive analysis of proof systems. Instead, it focuses only on those that are relevant to us. Of course, these developments are only possible through the great work and ideas of the pioneers in this field.

2. Basic Knowledge

Zero-knowledge proofs are not new. Definitions, foundations, important theorems, and even important protocols have been formulated since the mid-1980s. Some key ideas and protocols used to build modern SNARKs were proposed in the 1990s (sumcheck protocol) and even before the emergence of Bitcoin (GKR in 2007). The main issues with using it are related to the lack of strong use cases (the internet was not developed in the 1990s) and the required computational power.

1) Zero-knowledge proofs: Origins (1985/1989).

The field of zero-knowledge proofs appeared in 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 ZKP MOOC Lecture 1: Introduction and History of ZKP video from January 2023. The paper introduced the concepts of completeness, soundness, and zero-knowledge, and provided constructions for quadratic residuosity and quadratic non-residuosity.

2) Sumcheck protocol (1992).

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

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

The GKR protocol (see the paper "Delegating Computation: interactive Proofs for Muggles") is an interactive protocol where the prover runs linearly in the number of gates of the circuit, and the verifier runs sublinearly in the size of the circuit. In the protocol, the prover and verifier agree on a fan-in-two operation circuit over a finite field of depth d, where layer d corresponds to the input layer and layer 0 corresponds to the output layer. The protocol starts with a claim about the circuit output, which is simplified to a claim about the previous layer's values. Using recursion, it can be transformed into a claim about the circuit's inputs, making it easy to check. These reductions are achieved through the sumcheck protocol.

4) KZG polynomial commitment scheme (2010).

Kate, Zaverucha, and Goldberg introduced the polynomial commitment scheme using bilinear pairing groups in the paper "Constant-Size Commitments to Polynomials and Their Applications" in 2010. The commitment consists of a single group element, and the committer can efficiently open commitments to any correct evaluation of the polynomial. Additionally, due to batching techniques, multiple evaluations can be opened. KZG commitments provide a fundamental building block for several efficient SNARKs, such as Pinocchio, Groth16, and Plonk. It is also at the core of EIP-4844. For an intuitive understanding of batching techniques, refer to the Mina to Ethereum ZK bridge.

3. Practical SNARKs Using Elliptic Curves

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

1) Having more efficient provers.

2) Reducing the amount of preprocessing.

3) Having universal setups instead of circuit-specific setups.

4) Avoiding the use of trusted setups.

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

Currently, practical SNARKs schemes using elliptic curves include:

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 the paper Pinocchio: Nearly Practical Verifiable Computation) is the first practical and usable zk-SNARK. The SNARK is based on Quadratic Arithmetic Programs (QAP). The proof size was initially 288 bytes. Pinocchio's toolchain provides a compiler from C code to arithmetic circuits, further transformed 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 linear with the computation size, and verification time is linear with the size of public inputs and outputs.

3.2 Groth 16 (2016)

The Groth 2016 paper "On the Size of Pairing-based Non-interactive Arguments" introduced 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 a preprocessing step to obtain a structured reference string. The main drawback is that each program to be proven requires a different trusted setup, which is inconvenient. Groth16 was used in ZCash. For more details, 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. introduced an efficient zero-knowledge argument system for Pedersen commitment openings satisfying inner product relations in the paper "Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting" in 2016. The inner product proof system has a linear prover, logarithmic communication and interaction, but linear verification time. 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 solved the trusted setup problem in Groth16 by introducing a universal and updatable structured reference string. Marlin provides a proof system based on R1CS and is at the core of Aleo.

Plonk introduced a new arithmetic scheme (later known as Plonkish) and used grand-product check for copy constraints. Plonkish also allows for the introduction of specialized gates for certain operations, known as custom gates. Several projects have customized versions of Plonk, including Aztec, ZK-Sync, Polygon ZKEVM, Mina’s Kimchi, Plonky2, Halo 2, and Scroll, among others. For more information, refer to the blog "All you wanted to know about Plonk."

3.5 Lookups (2018/2020)

Gabizon and Williamson introduced plookup in 2020, using grand product check to prove that a value is contained in a precomputed table of values. While lookup arguments were previously proposed in Arya, their construction required determining the multiplicities of lookups, resulting in low efficiency. The PlonkUp paper demonstrates how to introduce plookup argument into Plonk. The issue with these lookup arguments is that they force the prover to pay for the entire table, regardless of the number of lookups. This means the cost for large tables is significant, and considerable effort has been put into reducing the prover's cost to the number of lookups they use.

Haböck introduced LogUp, which uses logarithmic derivatives to transform product checks into sums of reciprocals. LogUp is crucial for the performance of Polygon plonky2 ZKEVM (Beyond Limits: Pushing the Boundaries of ZK-EVM), which requires splitting the entire table into multiple STARK modules. These modules must be correctly linked and cross-table lookups are used to reinforce this operation. The introduction of LogUp-GKR utilizes the GKR protocol to improve the performance of LogUp. Caulk is the first lookup argument with sublinear prover time in relation to table size, with preprocessing time of O(N log N) and storage of O(N), where N is the table size. Several other schemes have since emerged, such as Baloo, flookup, cq, and caulk+. Lasso proposed multiple improvements, avoiding commitment to the table when it has a given structure. Additionally, the prover of Lasso only pays for the table entries accessed by the lookup operation. Jolt utilizes Lasso to prove the execution of a virtual machine through lookups.

3.6 Spartan (2019)

Spartan provides an IOP for circuits described using R1CS, leveraging the properties of multivariate polynomials and the sumcheck protocol. With the appropriate polynomial commitment scheme, it produces a transparent SNARK with linear prover time.

3.7 HyperPlonk (2022)

HyperPlonk is built on the Plonk idea using multivariate polynomials. It does not rely on quotients to check constraint execution but depends on the sumcheck protocol. It also supports high-degree constraints without compromising the prover's runtime. As it relies on multivariate polynomials, it does not require FFT and the prover's runtime is linear with the circuit size. HyperPlonk introduces new permutation IOP suitable for smaller fields and a batch opening protocol based on sumcheck, reducing the workload of the prover, proof size, and verifier's time.

3.8 Folding schemes (2008/2021)

Nova introduced the concept of folding schemes, a new approach to implementing Incrementally Verifiable Computation (IVC). The concept of IVC can be traced back to Valiant, who demonstrated how to merge two proofs of length k into one proof of length k. The idea is to prove, through recursive proofs, that the execution from step i to step i + 1 is correct, and the proof of the transition from step i - 1 to step i 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 operates on friendly elliptic curves. The use of friendly curve cycles (such as Pasta curves) to implement IVC is also used in Pickles, which is a core module of Mina for achieving succinct state. However, the concept of folding is different from recursive SNARK verification. The concept of accumulators has deeper connections with the idea of batching proofs. Halo introduced the concept of 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. Using Collision-Resistant Hash Functions in SNARKs

Around the time of Pinocchio's development, there were ideas for generating circuits/arithmetic schemes to prove the correctness of virtual machine execution. While developing arithmetic for virtual machines may be more complex or less efficient than writing dedicated circuits for certain programs, it offers the advantage that any program, no matter how complex, can be proven to execute correctly in the virtual machine. The ideas in TinyRAM were later improved with the design of Cairo vm and subsequent virtual machines (such as zk-evms or general zkvms). The use of collision-resistant hash functions eliminates the need for a trusted setup or the use of elliptic curve operations, but at the cost of longer proofs.

1) TinyRAM (2013)

In SNARKs for C, a PCP-based SNARK was developed to prove the correctness of C program execution, compiled into TinyRAM (Tiny Random Access Memory). The computer uses Harvard architecture with byte-addressable random access memory. Using non-determinism, the circuit size is quasi-linearly related to the computation size, effectively handling arbitrary and data-dependent loops, control flow, and memory access.

2) STARKs (2018)

STARKs were proposed by Ben Sasson et al. in 2018. Its implemented proof size is O(log2n), with fast provers and verifiers, no need for a trusted setup, and is considered post-quantum secure. It was initially used by Starkware/Starknet with 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 some adaptations (ZK-Sync's Boojum, Plonky2, Starky).

3) Ligero (2017)

• Ligero introduced a proof system with a proof size of 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 the idea of domain-independent polynomial commitment schemes.

5. Some New Developments in ZKP

Using different proof systems in production has shown the advantages of each method and brought new developments. For example, the Plonkish arithmeticization provides a simple way to include custom gates and lookup arguments; FRI as a PCS shows excellent performance, leading Plonky. Similarly, using grand product check in AIR (resulting in randomized AIR with preprocessing) improved its performance and simplified memory access arguments. Hash-based commitments have become popular—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 multivariate polynomials (such as Spartan or HyperPlonk), there is growing interest in new commitment schemes suitable for such polynomials. Binius, Zeromorph, and Basefold have all proposed new forms dedicated to 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 works in the binary field. The Binius commitment is based on Brakedown, designed to be domain-independent. Basefold extends FRI beyond Reed-Solomon codes, forming a domain-independent PCS.

2) Customizable Constraint Systems (CCS) (2023)

CCS encompasses 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 the prover incurring encrypted costs that scale with constraint degree. In particular, SuperSpartan generates SNARKs for AIR with linear time prover.

6. Conclusion

This paper describes the progress of SNARKs since their introduction in the mid-1980s. Advances in computer science, mathematics, and hardware, coupled with the introduction of blockchain, have led to new and more efficient SNARKs, opening the door to many applications that can potentially change our society. Researchers and engineers have proposed improvements and adjustments to SNARKs based on their needs, focusing on proof size, memory usage, transparent setups, post-quantum security, prover time, and verifier time.

While there were initially two main lines (SNARKs and STARKs), the boundaries between them have begun to blur, attempting to combine the strengths 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, with improved performance, and for some systems that take time to adapt, it will be difficult to keep up with these developments unless these tools can be easily used without changing some core infrastructure.

免责声明：本文章仅代表作者个人观点，不代表本平台的立场和观点。本文章仅供信息分享，不构成对任何人的任何投资建议。用户与作者之间的任何争议，与本平台无关。如网页中刊载的文章或图片涉及侵权，请提供相关的权利证明和身份证明发送邮件到support@aicoin.com，本平台相关工作人员将会进行核查。