Written by: Lambda Class
Compiled by: Bai Ding, Faust, Nickqiao
Original English version published on February 17, 2024
Zero-knowledge proofs (ZK Proofs) are powerful cryptographic primitives that allow one party (the prover) to convince another party (the verifier) that a given statement is true and valid without revealing any private information. In recent years, ZK has gained widespread attention in the fields of verifiable private computing, providing validity proofs for computer programs, and blockchain, and has played a significant positive role in the development of the world.
Although ZK is an emerging technology, its basic ideas and concepts date back to the 1980s. After being combined with blockchains such as Bitcoin and Ethereum, the development of ZK technology has been significantly accelerated, because the blockchain can verify the validity through SNARK and STARK, greatly enhancing the scalability, which makes ZK in the region Blockchain is a hot topic.
As Starkware founder Eli Ben-Sasson said, in recent years we have witnessed a "Cambrian explosion" of cryptographic proof systems, each with unique strengths and weaknesses, and trade-offs in design. Advances in hardware, better algorithms, new arguments, and peripheral tools have all stimulated the performance of ZK systems and the birth of new systems. Many proof systems have been adopted in practical applications, and people are still expanding the boundaries of ZK.
This also prompts people to think deeply about a question: Is there a universal ZK proof system that is applicable to all applications? We think this is unlikely for three reasons:
Diversity of applications;
Different types of constraints (including memory, verification time, proof time);
The need for robustness (if one proof system is hacked, we can still switch to something else as insurance).
Based on the above reasons, ZK proves that the system should be diverse. But even if there are many types of proof systems, there must be one significant commonality: ZK proofs can be quickly verified, and have a verification layer that can be easily adapted to new proof systems to solve the underlying layers (such as Ethereum) related difficulties.
In the ZK field, zk-SNARK is frequently mentioned. It is a form of zero-knowledge proof that uses complex mathematical tools such as bilinear pairing and arithmetic circuits to achieve efficient zero-knowledge proof. The characteristics of zk-SNARK are that the proof process is concise and non-interactive, and only a single communication is required between the prover and the verifier without multiple interactions. In addition, the proof size of zk-SNARK is very short, the verification efficiency is high, and it is suitable for use in resource-limited environments.
zk-STARK is another common form that aims to overcome some of the limitations of zk-SNARK. zk-STARK does not rely on a trusted setup and uses a more transparent mathematical construction system, such as polynomial commitments and finite field operations, hash collisions, etc., to generate and verify proofs. zk-STARK is more scalable than zk-SNARK, suitable for larger-scale calculations, and faster proof generation, but the size of the proof itself is usually larger.
It can be said that zk-SNARK and zk-STARK are both commonly used forms of zero-knowledge proofs, but they differ in transparency, scalability, proof size, etc.
In general, a ZK proof system usually consists of two parts: PIOP (Polynomial Interactive Oracle) and PCS (Polynomial Commitment Scheme). Common PIOP schemes include PLONKish, GKR, etc., while common PCS schemes include FRI, KZG, IPA, etc. For example, the Zcash version of Halo2 uses the Plonkish+IPA implementation. As for zk-STARK, it can actually be regarded as a special zk-SNARK based on FRI.
In more detail, different types of proof systems use different polynomial commitment schemes (PCS), arithmetic schemes, interactive oracle proofs (IOPs), or probabilistically checkable proofs (PCPs).
Furthermore, different ZK proof systems tend to differ in the following metrics:
Cryptographic assumptions: collision-resistant hash functions, discrete logarithm problems on elliptic curves, exponential knowledge
Transparent setup vs trusted setup
Proof Generation Time: Linear vs. Superlinear
Time to verify proof: constant time, logarithmic time, sublinear time, linear time
Proof of size
The simplicity of recursion
Arithmetic solution
Univariate vs Multivariate Polynomials
In the following, we will briefly touch upon the origins of ZK technology, explore its basic building blocks, and outline the rise and fall of different ZK proof systems. At the same time, this article does not provide an exhaustive analysis of the proof systems themselves, but rather focuses on those who have had a profound impact on the field. After all, the development of any industry is only possible through the great ideas of pioneers and their implementation.
The historical development of zk-SNARKs
Origin: 1980s-1990s
As we mentioned, zero-knowledge proof is not a new concept. Its definition, foundation, important theorems, and even related important protocols appeared as early as the mid-1980s. It first appeared in the paper "The Knowledge Complexity of Interactive Proof Systems" by Goldwasser, Micali (founder of Algorand) and Rackoff.
The key ideas and protocols that we use to build ZK-SNARK technology today were proposed in the 1990s. For example, the Sumcheck protocol simplifies the statement of the sum of multivariate polynomial evaluations into a single evaluation at a randomly selected point on an elliptic curve. This protocol laid an important foundation for ZK technology.
Therefore, the idea of ZK actually emerged long before the emergence of Bitcoin, but at that time there was a general lack of suitable use cases for ZK, and people could not provide the powerful computing power required for the ZK proof system. After all, the Internet and hardware equipment were not well developed in the 1990s.
GKR Agreement (2007)
GKR (Goldwasser-Kalai-Rothblum) is an interactive protocol where the prover's running time is linearly related to the number of logic gates in the circuit, while the verifier's time is sublinearly related to the circuit size. In the GKR protocol, the prover and the verifier need to agree on the results of running a two-input arithmetic circuit over a finite field, where the depth of the circuit is d, the dth layer is the input layer, and the 0th layer is the output layer. The protocol starts with a statement about the output of the circuit and recursively simplifies it to a statement about the previous layer. Finally, we can convert the statement about the output into a statement about the circuit input parameters, which is easy to verify. It can be said that the GKR protocol is a highly simplified version of the Sumcheck protocol mentioned above.
KZG Polynomial Commitment Scheme (2010)
In 2010, three experts in the ZK field, Kate from the German research institute MPI-SWS, Zaverucha from the Canadian cryptography company Certicom Research, and Goldberg from the University of Waterloo, jointly published a paper titled "Constant-Size Commitments to Polynomials and Their Applications". The paper proposed a polynomial commitment scheme using bilinear pairing groups, called KZG.
The commitment consists of a single group element, and the submitter can efficiently reveal any correct evaluation of the polynomial. With the help of batch processing technology, the evaluation of multiple polynomials can be revealed. KZG commitment has become one of the basic building blocks of some well-known ZK proof systems (such as halo2 used by the Ethereum PES group), and it plays a core role in Ethereum's EIP-4844. For a more intuitive understanding of the concept of batch processing technology, you can refer to the article Mina-Ethereum bridge Mina-Ethereum bridge.
Reference: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Practical ZK-SNARK system based on elliptic curves (2013)
The first practical construction of ZK-SNARK appeared in 2013, requiring a preprocessing step to generate the proving and verification keys, and was program- or circuit-specific, not generalizable. The size of these keys can be very large and depends on the secret parameters themselves; if this confidentiality is broken, an attacker can forge proofs. In this practical ZK-SNARK system, to convert the code into a form that can be proven, the code needs to be compiled into a set of polynomial constraints in mathematical form.
Initially, the above process had to be done manually, which was time-consuming and error-prone. Later, the technology changes in this direction mainly attempted to solve the following core problems:
Providing more efficient proof
Reduce the number of preprocessing
Implements a generic, non-circuit-specific setup
Avoid trusted setup
Develop methods for describing circuits using high-level languages rather than manually writing polynomial constraints
Pinocchio Protocol (2013)
The Pinocchio protocol is the first practical zk-SNARK system, based on quadratic arithmetic programs (QAPs), with an initial proof size of 288 bytes. Pinocchio's toolchain provides a compiler that compiles C to arithmetic circuits, which can be further converted to QAPs. The Pinocchio protocol requires the verifier to generate keys, which are not universal but circuit-specific. The asymptotic time complexity of the proof system for generation and key setup is linear in the size of the computation, and the verification time is linear in the size of the public input and output.
Groth16(2016)
Groth introduced a new ZK proof algorithm with higher performance in processing R1CS. R1CS is Rank-1 Constraint System, a first-order constraint system, which is a form of polynomial constraint in zk-SNARK. Gorth's proof has the smallest data size (containing only three group elements) and is very fast to verify, requiring only three pairing operations and a preprocessing step to structure the reference string. However, the main disadvantage of Gorth is that each program that needs to be proved requires a different trusted setup, which is quite inconvenient in practical applications.
Later, Groth16 was used in ZCash, a relatively well-known privacy blockchain project (in which Starkware founder Eli participated).
Bulletproofs and IPA (2016)
The KZG polynomial commitment scheme mentioned above has a major weakness that it requires a trusted setup. Bootle et al. proposed an effective zero-knowledge proof system that analyzes the opening of Pedersen commitments that satisfy the inner product relation. The inner product proof has a linear complexity proof time, the number of interactions between the prover and the verifier is logarithmic, but the verification time is linear. In addition, Bootle et al. developed a polynomial commitment scheme that does not require a trusted setup. These ideas were later adopted by Halo2 and Kimchi et al.
Sonic、Marlin 和 Plonk（2019）
Sonic, Plonk, and Marlin solve the problem that each program in the Groth16 algorithm requires a trusted setup, and introduce a universal and updateable structured reference string (used to implement a trusted setup that only needs to be done once). Among them, Marlin provides a proof system based on R1CS and has become the core technology of Aleo.
Plonk introduced a new arithmetic scheme (later called Plonkish) and the use of grand-product to check replication constraints. Plonkish also allows the introduction of specialized circuit logic gates for specific operations, so-called "custom gates". Many well-known blockchain projects have used customized versions of Plonk, including Aztec, zkSync, Polygon zkEVM, Mina, Ethereum PSE Group, and Scroll.
Spartan（2019）
Spartan provides an IOP for circuits described using R1CS, leveraging properties of multivariate polynomials and sum-check protocols. By using a suitable polynomial commitment scheme, it implements a zk-SNARK system with transparency and linear time complexity for generating proofs.
Lookups(2020)
Gabizon and Williamson proposed plookup in their 2020 paper, using grand-product to prove that a value is contained in a precomputed truth table, and showed how to introduce plookup parameters into the Plonk algorithm.
However, these lookup arguments have a common problem: the prover needs to spend a huge amount of money to build a complete truth table, so previous work around Lookups has been dedicated to reducing the proof cost.
Haböck later introduced LogUp in his paper, which uses logarithmic derivatives to transform grand-product checks into sums of reciprocals. LogUp was critical to the performance improvements of Polygon zkEVM because they needed to split the entire truth table into multiple STARK modules. These modules must be correctly linked, and cross-table lookups can enforce this. The introduction of LogUp-GKR has since improved the performance of LogUp through the GKR protocol.
Caulk was the first scheme to make proof time sublinear in the size of the truth table, with O(NlogN) preprocessing time and O(N) storage space, where N is the size of the truth table. Other schemes followed, such as Baloo, flookup, cq, and caulk+. In addition, Lasso proposed several improvements to avoid commitments to truth tables when they have a specific structure.
HyperPlonk（2022）
HyperPlonk was proposed in the paper "HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates". HyperPlonk is based on the idea of Plonk and uses multivariate polynomials. It does not use division to check the execution of constraints, but relies on a summation verification protocol. At the same time, it also supports high-order constraints without affecting the time of proof generation.
Due to the use of multivariate polynomials, there is no need to perform Fast Fourier Transforms (FFTs), and the time for proof generation is linear with the circuit size. HyperPlonk also introduces a new permutation IOP suitable for small fields and adopts a sum-check-based protocol to reduce the prover's workload, proof size, and verification time.
ZK proof system using collision-resistant hash functions
At the same time as Pinocchio was proposed in 2013, there were some proposals for generating circuits/arithmetic schemes that could prove that the virtual machine executed the instructions correctly. Although developing an arithmetic scheme for a virtual machine is more complicated or less efficient than writing a dedicated circuit for some program, it has an important advantage: no matter how complex the program is, it only needs to be proven that it is executed correctly in the virtual machine.
Some ideas from TinyRAM were later improved in the design of the Cairo virtual machine, which was followed by zk-evm, general zkvm, etc. Using collision-resistant hash functions in the proof system eliminates the need for a trusted setup or elliptic curve operations, but at the cost of longer proof times.
TinyRAM（2013）
In "SNARKs for C", they developed a proof system based on PCP to prove that the execution results of a program written in C are correct. The program is compiled into TinyRAM, a simplified VM. The VM has byte-level addressable random access memory, and the circuit size grows quasi-linearly in the computational scale, which can efficiently handle operations such as loops, control flow, and memory access.
PCP stands for Probabilistically Checkable Proof, which means probabilistically checkable proof. The verifier only needs to read a small randomly selected part of the proof to check the validity of the proof with a high degree of confidence. Unlike traditional proof systems where the verifier needs to check the entire proof, PCP only requires limited randomness to achieve efficient verification.
Light（2017）
Ligero introduced a proof system that allows proofs of size O(√￣n), where n is the size of the circuit. It arranges the polynomial coefficients in a matrix form. Brakedown builds on Ligero and introduces the concept of domain-independent polynomial commitment schemes.
STARKs（2018）
STARKs (Scalable Transparent ARguments of Knowledge) were proposed by Eli Ben-Sasson et al. in 2018. They achieve a proof complexity of 𝑂(log²𝑛), have fast verification speed, do not require trusted setup, and are speculated to be post-quantum secure. They are adopted by Starkware/Starknet together with the Cairo virtual machine. Its key innovations include Algebraic Intermediate Representation (AIR) and Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI) protocol. In addition, STARKs are also used by many well-known blockchain projects (such as Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync, etc.).
New development direction
The use of different proof systems in practical applications demonstrates the advantages of different approaches and promotes the development of ZK. For example, Plonkish's arithmetic scheme provides a simple way to include custom logic gates and lookup arguments; FRI has shown excellent performance as a PCS, leading to the birth of Plonky. At the same time, the use of grand-products checks in AIR (which brings pre-processed randomized AIR) improves its performance and simplifies memory access parameters. zk-STARK is becoming more and more popular due to its better generation efficiency and the introduction of more and more ZK-friendly hash functions.
New Polynomial Commitment Scheme (2023)
With the advent of efficient SNARKs based on multivariate polynomials (such as Spartan or HyperPlonk), there has been an increasing interest in new commitment schemes suitable for such polynomials. Binius, Zeromorph, and Basefold all propose new ways to commit to multilinear polynomials. Binius has the advantage of having no additional overhead when representing data types (while many other proof systems use at least 32-bit field elements to represent a single bit) and working on a binary domain. The commitment scheme uses a brakedown designed for domain independence. Basefold generalizes FRI to beyond Reed-Solomon, thus achieving a domain-independent polynomial commitment scheme (PCS).
Domain independence is a property of polynomial commitment schemes, which means that the commitment process does not depend on any specific properties of a specific domain. This means that commitments can be made to polynomials of any algebraic structure, such as finite fields, elliptic curves, and even integer rings.
Customizable restraint systems (2023)
CCS generalizes R1CS, capturing the arithmetic of R1CS, Plonkish, and AIR without the overhead. Using CCS in conjunction with Spartan IOP yields SuperSpartan, which supports high-dimensional constraints without the prover incurring cryptographic costs proportional to the constraint order. In particular, SuperSpartan provides a SNARK for AIR with linear-time proofs.
Summarize
This post reviews the progress of ZK technology since the mid-1980s. Advances in computer science, mathematics, and hardware, combined with the introduction of blockchains, have led to the emergence of new and more efficient ZK proof systems, opening the way to many applications that could change society.
Researchers and engineers have proposed improvements to the ZK system based on demand, focusing on proof size, memory usage, transparency, quantum security, proof time, and verification time. Although there have always been two major mainstream implementations of ZK (SNARKs and STARKs), the boundary between the two has gradually blurred, and the advantages of different proof systems are being combined, such as combining different arithmetic schemes with new polynomial commitment schemes.
We can expect that new ZK proof systems will continue to emerge and their performance will continue to improve. For applications that use these proof systems, if they cannot keep up with the latest iterations of the technology and continuously refactor and apply the latest algorithms, their current leading position will only be temporary.
