A brief historical overview of ZK technology

The first practical structure of ZK-SNARK appeared in 2013, requiring a preprocessing step to generate proof keys and verification keys, and was specific to the program or circuit and was not generalizable. The size of these keys can be very large and depends on the secret parameters themselves; if this confidentiality is breached, an attacker can forge the proof. In this practical ZK-SNARK system, converting the code into a form that can be proven requires compiling the code 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 technology changes in this direction mainly tried to solve the following core problems:

1. Provide more efficient proof

2. Reduce the number of preprocessing

3. Implement generic rather than circuit-specific settings

4. Avoid trusted settings

5. Avoid trusted settings

7. Develop ways to describe circuits using high-level languages ​​instead of manually writing polynomial constraints

Pinocchio Agreement (2013)

The Pinocchio protocol is the first practically usable zk-SNARK system,based on the Quadratic Arithmetic Program (QAP) with an initial proof size of 288 bytes. Pinocchio's toolchain provides a compiler that compiles C into arithmetic circuits, which can be further converted into QAP. The Pinocchio protocol requires the verifier to generate keys, which are not universal but circuit-specific. This proves that the asymptotic time complexity of system generation and key setup scales linearly with the size of the computation, and the verification time scales linearly with the size of the public inputs and outputs.

Groth16(2016)

Groth introduces a The new ZK algorithm has higher performance in processing R1CS. R1CS is Rank-1 Constraint System, a first-order constraint system, which is a polynomial constraint form in zk-SNARK. Gorth's proof has the smallest data size (containing only three group elements) and is fast to verify. Only three pairing operations and a preprocessing step to structure the reference string . But the main disadvantage of Gorth is that each program that needs to be proved requires different trusted settings, which is quite inconvenient in practical applications.

Groth16 was later used in ZCash, which is a well-known privacy blockchain project (Starkware founder Eli participated in it).

Bulletproofs and IPA (2016)

One of the major weaknesses of the KZG polynomial commitment scheme mentioned earlier is that it requires a trusted setting. Bootle et al. proposed an efficient zero-knowledge proof system that analyzes the opening of Pedersen commitments that satisfy the intrinsic product relationship. The inner product proves that the proof with linear complexity is time-consuming. The number of interactions between the prover and the verifier is logarithmic, but the verification time is linear. In addition, Bootle et al. also developed a polynomial commitment scheme that does not require trusted settings. These ideas were later adopted by Halo2 and Kimchi.

Sonic, Marlin and Plonk (2019)

Sonic , Plonk and Marlin solved the problem of each program requiring trusted settings in the Groth16 algorithm and introduced a universal and updateable structured reference string (used to implement trusted settings that only need to be set 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 copy 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 team and Scroll, etc.

Spartan(2019)

Spartan provides an IOP for circuits described using R1CS, taking advantage of the features of multivariable polynomials and summation checking protocols. By using a suitable polynomial commitment scheme, it implements a transparent zk-SNARK system and the time complexity of generating proofs is linear.

Lookups(2020)

Gabizon and Williamson proposed plookup in his paper in 2020, using the grand-product to prove that a certain value is contained in a pre-calculated truth table, showing how to introduce plookup parameters into the Plonk algorithm.

However, these lookup arguments have a common problem. The prover needs to spend huge costs to build a complete truth table. Therefore, previous work around Lookups has been dedicated to Yu will prove cost reduction.

Later Haböck introduced LogUp in the paper, which uses logarithmic derivatives to transform the grand-product check into the sum of reciprocals. LogUp is critical to the performance improvement of Polygon zkEVM because they need to split the entire truth table into multiple STARK modules. These modules must be linked correctly, and cross-table lookups enforce this. Since then, the introduction of LogUp-GKR has improved the performance of LogUp through the GKR protocol.

Caulk is the first solution that makes the proof time have a sub-linear relationship with the size of the truth table. Its preprocessing time complexity is O(NlogN). The space complexity occupied by storage is O(N), where N is the truth table size. Other solutions followed, such as Baloo, flookup, cq and caulk+. Additionally, Lasso proposes several improvements to avoid committing to truth tables when they have a specific structure.

HyperPlonk (2022)

HyperPlonk in the paper "HyperPlonk : Plonk with Linear-Time Prover and High-Degree Custom Gates" was proposed. HyperPlonk is based on the concept of Plonk and uses multi-variable polynomials. It does not use division to check the enforcement of constraints, but relies on a summation checking protocol. At the same time, it also supports high-order constraints without affecting the time of proof generation.

Due to the use of multi-variable polynomials, there is no need to perform a fast Fourier transform (FFT), proving that the generation time scales linearly with the circuit size. HyperPlonk also introduces a new permutation IOP suitable for small fields and adopts a sum-check-based protocol, reducing the prover's workload, proof size, and verification time.

ZK proof system using anti-collision hash function

At the same time that Pinocchio was proposed in 2013, there were some proposals for generating circuit/arithmetic schemes that could prove that the virtual machine's execution of instructions was correct. Although developing arithmetic schemes for virtual machines is more complex or less efficient than writing special circuits for some programs, it has an important advantage: no matter how complex the program is, you only need to prove that it executes correctly in the virtual machine .

Some of the ideas in TinyRAM were later improved in the design of the Cairo virtual machine, followed by zk-evm and universal zkvm. Using collision-resistant hash functions in proof systems eliminates the need for trusted settings 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 programs written in C language are correct. The program is compiled into TinyRAM, a simplified VM. The VM has byte-level addressable random access memory, the circuit size grows quasi-linearly in the computational scale, and can efficiently handle operations such as loops, control flow, and memory accesses.

Among them, PCP refers to Probabilistically Checkable Proof, that is, probabilistically checkable proof. The verifier only needs to read a small part of the randomly selected content in the proof. The validity of the proof can be checked with a high level of confidence. Unlike traditional proof systems where the verifier needs to check the entire proof, PCP requires only limited randomness to achieve efficient verification.

Ligero (2017)

Ligero introduces a set Proof system that can implement proofs of size O(√￣n), where n is the size of the circuit. It arranges polynomial coefficients in matrix form. Brakedown is built on Ligero and introduces the concept of domain-independent polynomial commitment schemes.

STARKs（2018）

STARKs（2018） Scalable Transparent ARguments of Knowledge) was proposed by Eli Ben-Sasson et al. in 2018. They achieve ?(log²⁡?) proof complexity, have fast verification speeds, require no trusted setup, and are speculated to be post-quantum secure. They are used by Starkware/Starknet with the Cairo virtual machine. Its key innovations include Algebraic Intermediate Representation (AIR) and the Fast Reed-Solomon Interactive Oracle Proximity Proof (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

Different proof systems in Use in practical applications demonstrates the advantages of different approaches and drives 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 With the emergence of efficient SNARKs based on multivariate polynomials (such as Spartan or HyperPlonk), there is 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 extra overhead in representing data types (whereas many other proof systems use at least 32-bit field elements to represent individual bits) and working on the binary domain. This commitment scheme uses brakedown, which is designed to be domain-agnostic. Basefold generalizes FRI beyond Reed-Solomon, enabling domain-independent polynomial commitment schemes (PCS).

Domain independence is a property of the polynomial commitment scheme, which means that in the polynomial commitment scheme, the commitment process does not depend on the specific attributes of any specific domain. This means that commitments can be made to polynomials of any algebraic structure, such as finite fields, elliptic curves, or even rings of integers.

Customizable Constraint System (2023)

CCS Pan , while capturing the arithmeticization of R1CS, Plonkish, and AIR without additional overhead. Using CCS combined with Spartan IOP can produce SuperSpartan, which supports high-dimensional constraints without the prover needing to bear the encryption cost proportional to the constraint order. In particular, SuperSpartan provides a linear-time proof SNARK for AIR.

Summary

This article summarizes the Progress in ZK technology since the mid-1980s. Advances in computer science, mathematics, and hardware, coupled with the introduction of blockchain, have given rise to the emergence of new, more efficient ZK proof systems, opening the way for many applications that may change society.

Researchers and engineers proposed improvements to the ZK system based on needs, focusing on proving size, memory usage, transparency, and quantum resistance. aspects such as security, proof time and verification time. Although ZK’s mainstream implementation solutions have always been in two categories (SNARKs and STARKs), the boundaries between the two have gradually blurred, and the advantages of different proof systems are being combined, such as combining different arithmetic ization scheme and a new polynomial commitment scheme.

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 follow the iterative development of the latest technology and continuously reconstruct and apply the latest algorithms, the current leading position will only be temporary.

Original link: https://blog.lambdaclass.com/our-highly -subjective-view-on-the-history-of-zero-knowledge-proofs/