Understanding the history of zero-knowledge proofs

Source: Denglian Community

Zero-knowledge, succinct, non-interactive knowledge proofs (zk-SNARKs) are a powerful cryptographic primitive that allows one party, i.e. The prover convinces another party, the verifier, that a certain statement is true without revealing any other information other than the validity of the statement. They have attracted widespread attention due to their applications in verifiable private computation, providing proof of correctness of computer program execution, and helping to scale blockchains. We believe SNARKs will have a significant impact on shaping our world, as we describe in our article ^[6]. SNARKs is an umbrella term for different types of proof systems, using different polynomial commitment schemes (PCS), arithmetic schemes, interactive Oracle proofs (IOP) or probabilistic checkable proofs (PCP). However, these basic ideas and concepts date back to the mid-1980s. After the introduction of Bitcoin and Ethereum, development work accelerated significantly, which proved to be an exciting and powerful use case because you can use zero-knowledge proofs (often called validity proofs for this specific use case) to extend them. SNARKs are an important tool for blockchain scalability. As Ben-Sasson describes it, the past few years have witnessed the Cambrian explosion of cryptographic proofs^[7] . Every proof system has advantages and disadvantages, and is designed with certain trade-offs in mind. Advances in hardware, better algorithms, new arguments and gadgets have led to improved performance and the creation of new systems. Many of these systems are being used in production, and we continue to push the boundaries. Will we have one universal proof system that works for all applications, or several systems suitable for different needs? We think it is unlikely that one proof system will dominate all applications because of:

1. The diversity of applications.

2. We have different types of constraints (regarding memory, verification time, proof time).

3. The need for robustness (if one proof system is broken, we still have other systems).

Even if proof systems have changed a lot, they all share an important property: proofs can be verified quickly. The difficulties associated with changing base layers such as Ethereum are also solved by having a layer that validates proofs and can be easily adapted to handle new proof systems.

To give an overview of the different characteristics of SNARKs:

• Cryptographical assumptions: collision-resistant hash functions, discretization on elliptic curves Logarithmic problems and exponent knowledge.

• Transparent vs trusted settings.

• Prover time: linear vs superlinear.

• Verifier time: constant time, logarithmic, sublinear, linear.

• Prove size.

• The convenience of recursion.

• Arithmetic scheme.

• Univariable vs multivariable 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 an exhaustive analysis of proof systems. Instead, we focus on those that have an impact on us in the present. Of course, these developments were only possible on the basis of the great work and ideas of pioneers in this field.

Basics

As we mentioned, zero-knowledge proofs are not new. Definitions, foundations, important theorems and even important protocols were established from 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 (GKR in 2007). The main problems with adoption at the time were mainly related to the lack of strong use cases (the Internet was not as developed as it is today in the 1990s) and the required computing power.

Zero-knowledge proofs: origins (1985/1989)

The field of zero-knowledge proofs first appeared in the academic literature in [Goldwasser, Micali and Rackoff](https://people.csail.mit.edu/silvio/Selected Scientific Papers/Proof Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf?ref=blog.lambdaclass.com "Goldwasser, Micali and Rackoff"). For a discussion of the origin, you can see the following video ^[8]. The paper introduces the concepts of completeness, correctness, and zero-knowledge, and provides the construction of quadratic residuosity and quadratic non-residuosity.

Sumcheck Protocol (1992)

The sumcheck protocol ^[9] was developed by Lund, Fortnow, Karloff, and Nisan^[10] Proposed in 1992. It is one of the most important building blocks of concise interactive proofs. It helps us reduce the statement of the sum of evaluations of a multivariate polynomial to a single evaluation at a randomly chosen point.

Goldwasser-Kalai-Rothblum (GKR) (2007)

The GKR protocol ^[11] is an interactive protocol whose prover's running time It scales linearly with the number of gates in the circuit, while the verifier's running time scales sublinearly with the size of the circuit. In this protocol, the prover and verifier agree on an arithmetic circuit of fan-in-two over a finite field of depth d, where layer d corresponds to the input layer and layer 0 corresponds to output layer. The protocol starts with a declaration of the circuit's output, reducing it to a declaration of the previous layer's value. With recursion, we can turn this into a declaration of the circuit's inputs, which can be easily checked. These reductions are achieved via the sumcheck protocol.

KZG polynomial commitment scheme (2010)

KZG polynomial commitment scheme (KZG polynomial commitment scheme (PCS)) Kate, Zaverucha, and Goldberg^[12] In 2010 a polynomial commitment scheme using bilinear pairing groups was introduced. The commitment consists of a single group element, and the committer can effectively open the commitment to any correct evaluation of the polynomial. Furthermore, thanks to batch processing technology, multiple assessments can be opened. KZG commitments provide the basic building blocks for several efficient SNARKs such as Pinocchio, Groth16, and Plonk. It is also the core of EIP-4844^[13]. For an intuitive understanding of batch processing technology, you can see our article on the Mina-Ethereum bridge^[14].

Practical SNARKs using elliptic curves

The first practical SNARKs construct appeared in 2013. These constructions require preprocessing steps to generate proofs and verification keys and are program/circuit specific. These keys can be quite large and depend on secret parameters that should remain unknown; otherwise, they can forge proofs. Converting the code into something provable requires compiling the code into a series of polynomial constraint systems. Initially, this had to be done manually, which was time-consuming and error-prone. Progress in the field attempts to eliminate some major problems:

1. There are more efficient provers.

2. Reduce the amount of preprocessing.

3. Have settings that are general rather than circuit specific.

4. Avoid trust settings.

5. Develop methods for describing circuits using high-level languages ​​rather than manually writing polynomial constraints.

Pinocchio (2013)

Pinocchio^[15] is the first practical, usable zk-SNARK. SNARK is based on the Quadratic Arithmetic Program (QAP). The proof size is initially 288 bytes. Pinocchio's toolchain provides a compiler from C code to arithmetic circuits and further conversion to QAP. The protocol requires the verifier to generate keys, which are circuit-specific. It uses elliptic curve pairings to check equations. Proof generation and key setting are asymptotically linear in the size of the computation, and verification time is linear in the size of the common inputs and outputs.

Groth 16 (2016)

Groth^[16] introduces a new knowledge argument with enhanced performance ^[17] , used to describe the problem of 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. Its main disadvantage is that it requires different trust settings for each program we want to certify, which is inconvenient. Groth16 is used by ZCash.

Bulletproofs & IPA (2016)

One weakness of KZG PCS is that it requires a trust setup. Bootle et al. ^[18] introduced an efficient zero-knowledge argumentation system that satisfies the inner product relation of Pedersen commitment openings. The inner product argument has a linear prover, logarithmic communication and interaction, but with linear time verification. They also developed a polynomial commitment scheme that does not require trust setup. The Polynomial Commitment Scheme (PCS) using these ideas is used by Halo 2 and Kimchi.

Sonic, Marlin and Plonk (2019)

Sonic^[19], Plonk^[20] and Marlin ^[21] Solve the problem in Groth16 that every program needs trust settings by introducing a universal and updateable structured reference string. Marlin provides a proof system based on R1CS (Rank-1 Constraint System), which is the core of Aleo.

Plonk^[22] introduced a new arithmetic scheme (later called Plonkish) and the use of grand-product checks for checking replication 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.

Lookups (2018/2020)

Gabizon and Williamson introduced plookup^[23] in 2020, using macro product checking to prove that a value is contained in in a table of precomputed values. Although the lookup parameter was previously proposed in Arya^[24], this construction requires the multiplicity of the lookup to be determined, which makes the construction less efficient. The PlonkUp^[25] paper shows how to introduce the plookup parameter into Plonk. The problem with these lookup parameters is that they force the prover to pay for the entire table, regardless of the number of lookups he performs. This means that the cost of large tables is considerable, and considerable efforts have been made to reduce the cost to the prover only paying for the number of lookups he uses. Haböck introduced LogUp^[26], which uses logarithmic derivatives to convert grand-product checks into sums of reciprocals. LogUp is critical for performance in Polygon ZKEVM^[27], where they require splitting the entire table into several STARK modules. These modules must be linked correctly, and cross-table lookups enforce this. Introduce LogUp-GKR^[28] to use the GKR protocol to improve the performance of LogUp. Caulk^[29] is the first scheme where prover time is sublinear with table size, using preprocessing time O(NlogN) and storage O(N), where N is the table size. Several other schemes subsequently emerged, such as Baloo^[30], flookup^[31], cq^[32] and caulk+^{[ 33]}. Lasso^[34] proposed several improvements to avoid committing a table if it has a given structure. Furthermore, Lasso's prover only pays for table entries accessed by lookup operations. Jolt^[35] uses Lasso to prove the execution of the virtual machine through lookups.

Spartan (2019)

Spartan^[36] provides an IOP ("Interactive Oracle Proof.") for circuits described using R1CS, taking advantage of multiple Properties of polynomials in variables and the sumcheck protocol. Using a suitable polynomial commitment scheme, it yields a linear-time proof transparent SNARK.

HyperPlonk (2022)

HyperPlonk^[37] Based on the idea of ​​Plonk, using multivariate polynomials. It relies on the sumcheck protocol rather than quotient to check the execution of constraints. It also supports higher-order constraints without affecting the prover's running time. Since it relies on multivariable polynomials, no FFT is required, and the prover's running time scales linearly with circuit size. HyperPlonk introduces a new permutation IOP for smaller fields, and a sumcheck-based batch open protocol, which reduces prover work, proof size, and verifier time.

Folding schemes (2008/2021)

Nova^[38] introduces the concept of folding schemes, which is a way to achieve incremental A new method for incrementally verifiable computation (IVC). The concept of IVC can be traced back to Valiant^[39], who showed how to merge two proofs of length k into a single proof of length k. The idea is that we can prove that by recursively proving that the execution from step i to step I +1 is correct, and verifying a proof that the transition from step i−1 to step i is correct Any long-running calculation. Nova handled unified computing well; it was subsequently extended to handle different types of circuits, introducing Supernova^[40]. Nova uses a relaxed version of R1CS and works on friendly elliptic curves. Implementing IVC using friendly loops of curves (such as Pasta curves) is also used in Pickles, Mina's main building block for implementing concise states. However, the concept of folding is different from recursive SNARK verification.

The idea of ​​accumulators is more deeply connected to the concept of batch proofs. Halo^[41] introduced the concept of accumulation as an alternative to recursive proof combinations. Protostar^[42] provides a non-uniform IVC scheme for Plonk, supporting high-order gates and vector lookups.

Using collision-resistant hash functions

While Pinocchio was being developed, there were some ideas to generate circuit/arithmetic schemes that could prove the correctness of a virtual machine's execution. Even though developing arithmetic for a virtual machine may be more complex or less efficient than writing dedicated circuits for some programs, it has the advantage that any complex program can be proven by showing that the program executes correctly in a virtual machine. The ideas in TinyRAM were subsequently refined through the design of the Cairo vm, and subsequent virtual machines such as zk-evms or general purpose zkvms. Using collision-resistant hash functions eliminates the need for trusted settings or elliptic curve operations, but at the cost of longer proofs.

TinyRAM (2013)

In SNARKs for C^[43], they developed PCP-based SNARKs to prove that C programs are executed correctly properties, the program is compiled into TinyRAM, a reduced instruction set computer.

Remarks: PCP,  Probabilistically Checkable Proof Probabilistically checkable proof. The verifier only needs to read a randomly selected small part of the proof to check the proof with a high degree of confidence. effectiveness. Unlike traditional proof systems where the verifier needs to check the entire proof, PCP requires only limited randomness to achieve efficient verification.

The computer uses a Harvard architecture with byte-level addressable random access memory. Taking advantage of non-determinism, the size of the circuit scales almost linearly with the size of the computation, allowing efficient processing of any data-related loops, control flow, and memory accesses.

STARKs (2018)

STARKs^[44] was proposed in 2018 by Ben Sasson et al. They achieve 0(log^2 n) proof size, have fast provers and verifiers, require no trusted setup, and are speculated to be post-quantum secure. They were first used by Starkware/Starknet, with the Cairo vm. Its key introductions include Algebraic Intermediate Representation (AIR) and the FRI protocol ^[45] (Fast Reed-Solomon Interactive Oracle Proof of Proximity). It is also used by other projects (Polygon Miden, Risc0, Winterfell, Neptune), or has seen the adaptation of some components (ZK-Sync's Boojum, Plonky2, Starky).

Ligero (2017)

Ligero^[46] proposed a proof system that achieved a proof size of O(√n), where n is The size of the circuit. It arranges polynomial coefficients into matrix form and uses linear codes. Brakedown^[47] builds on Ligero and introduces the concept of domain-independent polynomial commitment schemes.

Some new developments

Using different proof systems in production demonstrates 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 has shown excellent performance as a PCS, leading to Plonky. Likewise, the use of macro product checking in AIR (bringing preprocessed randomized AIR) improves its performance and simplifies memory access parameters. Promises based on hash functions become popular due to their speed in hardware or the introduction of new hash functions suitable for SNARKs.

New polynomial commitment schemes (2023)

With the emergence of efficient SNARKs based on multivariate polynomials, such as Spartan or HyperPlonk, there is interest in new commitment schemes suitable for such polynomials generated greater interest. Binius^[48], Zeromorph^[49] and Basefold^[50] all propose new forms of commitment to multilinear polynomials. Binius has the advantage of having no overhead in representing data types (whereas many proof systems use at least 32-bit field elements to represent a single bit) and can work on the binary domain. This commitment scheme uses brakedown, which is designed to be domain-agnostic. Basefold generalizes FRI to codes other than Reed-Solomon, resulting in a domain-independent PCS.

Note Domain-independent: In a domain-independent polynomial commitment scheme, the commitment process does not depend on any domain-specific properties. This means that commitments can be made to polynomials of any algebraic structure, such as finite fields, elliptic curves, or even integer rings.

Customizable Constraint System (2023)

CCS^[51] Generalizes R1CS while capturing R1CS, Plonkish and AIR Arithmetic, no additional overhead. Using CCS combined with Spartan IOP results in SuperSpartan, which supports high-dimensional constraints without the prover needing to bear the cryptographic costs that scale as the constraint metric increases. In particular, SuperSpartan provides a linear-time proof SNARK for AIR.

Conclusion

This paper describes the progress of SNARKs since the mid-1980s. Advances in computer science, mathematics, and hardware, as well as the introduction of blockchain, have led to the emergence of new and more efficient SNARKs, opening the door to many applications that could transform our society. Researchers and engineers proposed improvements and adaptations of SNARKs based on their needs, focusing on proof size, memory usage, transparency settings, post-quantum security, proof time, and verification time. While there were initially two main lines (SNARKs vs STARKs), the boundaries between the two have started to disappear in attempts to combine the advantages of different proof systems. For example, combining different arithmetic schemes with new polynomial commitment schemes. We can expect that new proof systems will continue to emerge and performance will improve, and it will be difficult to keep up with these developments for some systems that will take some time to adapt to, unless we can easily use these tools without changes. Some core infrastructure.

Reference materials

[1]Link: https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/< /span>

[2] Link translation plan: https://github.com /lbc-team/Pioneer

[3]Translation Team: https: //learnblockchain.cn/people/412

[4]Tiny Bear:  ;https://learnblockchain.cn/people/15

[5]learnblockchain .cn/article…: https://learnblockchain.cn/article/7422

[6]Article: https://blog.lambdaclass.com/transforming-the-future-with-zero-knowledge-proofs-fully-homomorphic-encryption-and-new-distributed-systems-algorithms/

[7] Cryptographically proven Cambrian explosion: https:/ /medium.com/starkware/cambrian-explosion-of-cryptographic-proofs-5740a41cdbd2?ref=blog.lambdaclass.com

[8]The following video: https://www.youtube.com/watch?v=uchjTIlPzFo&ref=blog.lambdaclass.com

[10]Lund, Fortnow, Karloff, and Nisan:  ;https://dl.acm.org/doi/pdf/10.1145/146585.146605?ref=blog.lambdaclass.com

[11]GKR protocol: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/2008-DelegatingComputation.pdf? ref=blog.lambdaclass.com

[12]Kate, Zaverucha, and Goldberg : https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf?ref=blog.lambdaclass.com

[13]EIP-4844: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-4844.md?ref=blog .lambdaclass.com

[14]Mina-Ethereum Bridge: https: //blog.lambdaclass.com/mina-to-ethereum-bridge/

[15]Pinocchio: https://eprint.iacr.org/2013/279?ref=blog.lambdaclass.com

< span style="font-size: 14px;">[16]Groth: https://eprint.iacr.org/2016/260.pdf?ref=blog.lambdaclass.com

[17] New knowledge argument with enhanced performance: https://blog.lambdaclass.com/groth16 /

[18]Bootle et al.: https://eprint. iacr.org/2016/263?ref=blog.lambdaclass.com

[ 19]Sonic: https://eprint.iacr.org/2019/099?ref=blog.lambdaclass.com

[20]Plonk: https://eprint.iacr.org/2019/953?ref=blog.lambdaclass.com

[21]Marlin: https://eprint.iacr.org/2019/1047?ref=blog.lambdaclass. com

[22]Plonk: https://blog.lambdaclass. com/all-you-wanted-to-know-about-plonk/

[23]plookup: https://eprint.iacr.org/2020/315?ref=blog.lambdaclass.com

< span style="font-size: 14px;">[24]Arya: https://eprint.iacr.org/2018/380?ref=blog.lambdaclass.com

[25]PlonkUp: https://eprint.iacr.org/2022/086?ref=blog.lambdaclass .com

[26]LogUp: https://eprint.iacr .org/2022/1530?ref=blog.lambdaclass.com

[27 ]Polygon ZKEVM: https://toposware.medium.com/beyond-limits-pushing-the-boundaries-of-zk-evm-9dd0c5ec9fca?ref=blog.lambdaclass.com

[29]Caulk: https:// eprint.iacr.org/2022/621?ref=blog.lambdaclass.com

[30]Baloo: https://eprint.iacr.org/2022/1565?ref=blog.lambdaclass.com

[31]flookup: https://eprint.iacr.org/2022/1447?ref=blog.lambdaclass.com

[33]caulk+: https://eprint. iacr.org/2022/957?ref=blog.lambdaclass.com

[ 34]Lasso: https://eprint.iacr.org/2023/1216?ref=blog.lambdaclass.com

[35]Jolt: https://eprint.iacr.org/2023/1217?ref=blog.lambdaclass.com

[36]Spartan: https://eprint.iacr.org/2019/550?ref=blog.lambdaclass. com

[37]HyperPlonk: https://eprint.iacr. org/2022/1355.pdf?ref=blog.lambdaclass.com

[ 38]Nova: https://eprint.iacr.org/2021/370?ref=blog.lambdaclass.com

[39]Valiant: https://https//iacr.org/archive/tcc2008/49480001/49480001.pdf?ref=blog.lambdaclass.com

[40]Supernova: https://eprint.iacr.org/2022/1758 ?ref=blog.lambdaclass.com

[41]Halo: https ://eprint.iacr.org/2019/1021.pdf?ref=blog.lambdaclass.com

[42]Protostar: https://eprint.iacr.org/2023/620?ref=blog.lambdaclass.com

[43]SNARKs for C: https://eprint.iacr.org/2013/507?ref=blog.lambdaclass.com

[44]STARKs: https://eprint.iacr.org/2018 /046?ref=blog.lambdaclass.com

[45]FRI protocol:  https://blog.lambdaclass.com/how-to-code-fri-from-scratch/

[46]Ligero: https://eprint.iacr.org/2022/1608?ref=blog.lambdaclass.com

[47]Brakedown: https://eprint.iacr.org/2021/1043?ref=blog.lambdaclass.com

[48]Binius: https://blog.lambdaclass.com/snarks -on-binary-fields-binius/

[49]Zeromorph:  https://eprint.iacr.org/2023/917?ref=blog.lambdaclass.com

[50]Basefold: https://blog.lambdaclass.com/how-does-basefold-polynomial-commitment-scheme-generalize-fri/

[51]CCS: https://eprint.iacr.org/2023/552?ref=blog.lambdaclass.com

[52]DeCert.me: https://decert.me /