Clarify the historical development of ZK technology

ZK Proofs is a powerful cryptographic primitive that allows one party (proverb) to convince the other party (verb) 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 proof of effectiveness 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 accelerated significantly.Because blockchain can prove its effectiveness through SNARK and STARK, and greatly enhance its scalability, this makes ZK popular in the blockchain field.

As Starkware founder Eli Ben-Sasson said, in recent years we have witnessed the “Cambrian explosion” of the cryptographic proof system.Each proof system has its own unique strengths and weaknesses and is traded down when designed.The advancement of hardware, better algorithms, new arguments and peripheral tools have all stimulated the performance improvement of the ZK system and the birth of a new system.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 for all applications?We don’t think this is likely to be true.There are three reasons:

1. Diversity of applications;

2. Different constraint types (including memory, verification time, and proof time);

3. The need for robustness (if one proof system is hacked, we can still switch to other systems as insurance).

Based on the above reasons, the ZK proves that the system should be diverse.But even if there are many types of proof systems, there must be a significant commonality: ZK proof can be quickly verified.And having a verification layer can easily adapt to the new proof system to solve the relevant difficulties of the underlying layer it depends on (such as Ethereum).

In the ZK field, zk-SNARK is frequently mentioned.It is a form of realizing zero-knowledge proof, enabling efficient zero-knowledge proof by using complex mathematical tools such as bilinear pairing and arithmetic circuits.The characteristic of zk-SNARK is that the proof process is simple and non-interactive, and only a single communication is required between the prover and the verifier and the verifier, no multiple interactions are required.also,The proof size of zk-SNARK is very short and has high verification efficiency, making it suitable for use in resource-constrained environments.

And zk-STARK is another common form designed to overcome some limitations of zk-SNARK.zk-STARK does not rely on trusted settings and uses more transparent mathematical construction systems such as polynomial commitment and finite domain operations, hash collisions, etc. to generate and verify proofs.zk-STARK is more scalable than zk-SNARK, suitable for larger-scale computing, proving to generate faster, but the Proof itself is usually larger in size.

It can be said that zk-SNARK and zk-STARK are both commonly used forms in zero-knowledge proof, but they vary in terms of transparency, scalability, proof size, etc.

Overall,A ZK proof system usually includes two parts: PIOP (polynomial interactive oracle) and PCS (polynomial commitment scheme).Common PIOP solutions include PLONKish, GKR, etc., while common PCS solutions include FRI, KZG, IPA, etc. For example, the Zcash version of Halo2 uses the implementation method of Plonkish+IPA. As for zk-STARK, it can actually be regarded as a FRI-basedSpecial zk-SNARK.

If more detailed, different types of proof systems will use different polynomial commitment schemes (PCS), arithmetic schemes, interactive oracle proofs (IOP), or probability checkable proofs (PCP).

Further,Different ZK proof systems often differ in the following indicators:

• Cryptographic hypothesis: anti-collision hash function, discrete logarithmic problems on elliptic curves, exponential knowledge

• Transparent settings vs trusted settings

• Time-consuming to generate proofs: linear vs hyperlinear

• Time-consuming for verification of proofs: constant time, log time, sublinear, linear

• Prove the size of the size

• The simplicity of recursion

• Arithmetic scheme

• Univariate vs multivariate polynomial

Below we will briefly talk about the origin 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 conduct a detailed analysis of the proof system itself, but 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 appealing to practice.

The historical development context of zk-SNARK

Origin: 1980s to 1990s

As we mentioned, zero-knowledge proof is not a new concept. Its definition, foundation, important theorems, and even relevant important protocols appeared as early as the mid-1980s.The first appearance was in Goldwasser, Micali (founder of Algorand) and Rackoff’s papersThe Knowledge Complexity of Interactive Proof Systems“middle.

andThe key ideas and protocols we use to build ZK-SNARK technology were released in the 1990s.For example, the Sumcheck protocol simplifies the declaration of sum of evaluation of multiple polynomials to single evaluation of randomly selected points on the elliptic curve, which lays an important foundation for ZK technology.

Therefore, the emergence of ZK ideas is actually far earlier than the emergence of Bitcoin.However, at that time, there was a general lack of applicable cases for ZK, and people could not provide the powerful computing power required to meet the ZK proof system. After all, the Internet and hardware equipment were not developed in the 1990s.

GKR Protocol (2007)

GKR (Goldwasser-Kalai-Rothblum) is an interactive protocol. The running time of the prover is linearly correlated with the number of logic gates in the circuit, while the time of the verifier is sub-linearly correlated with the circuit size.In the GKR protocol, the prover and the verifier need to agree on the operation results of the dual input arithmetic circuit in a finite domain, the depth of which is d, the d-th layer is the input layer, and the 0-th layer is the output layer.The protocol starts with a declaration about the output of the circuit and simplifies it to a declaration of the previous layer by recursively.Finally, we can convert the declaration to the output into a declaration of the input parameters of the circuit, which is easily verified.It can be said that the GKR protocol is highly simplified based on the aforementioned Sumcheck protocol.

KZG Polynomial Commitment Solution (2010)

In 2010, three experts in the ZK field——Kate from the German research institution MPI-SWS, Zaverucha from the Canadian cryptography company Certicom Research, and Goldberg from the University of Waterloo jointly published a paper called “Constant-Size Commitments to Polynomialsand Their Applications”.This paperA polynomial commitment scheme using bilinear pair groups is proposed, called KZG.

This promise consists of a separate group element, and the committer can efficiently reveal any correct evaluation of the polynomial, and with the help of batch processing technology, the evaluation of multiple polynomials can be revealed.KZG promised to 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 also played a core role in Ethereum’s EIP-4844.To understand the concept of batch processing technology more intuitively, you can refer to the article on Mina-Ethereum Bridge.

Reference: https://blog.lambdaclass.com/mina-to-ethereum-bridge/

Practical ZK-SNARK System Based on Elliptic Curves (2013)

The first practical structure of ZK-SNARK appeared in 2013 and required a preprocessing step to generate a proof key and a verification key, and is program- or circuit-specific and not universal.These keys can be of great size and depend on the secret parameters themselves; if this confidentiality is compromised, the attacker can forge proof.In this practical ZK-SNARK system, to convert the code into a proven form, it is necessary to compile the code into a set of mathematical forms of polynomial constraints.

At first, the above process must be completed manually, which is both time-consuming and error-prone.Later, in response to the technological changes in this direction, we mainly tried to solve the following core issues:

1. Provide more efficient proof

2. Reduce the number of preprocessing

3. Implement universal rather than circuit-specific settings

4. Avoid trusted settings

5. Develop methods to describe circuits in high-level languages, rather than manually writing polynomial constraints

Pinocchio Protocol (2013)

The Pinocchio protocol is the first zk-SNARK system to be actually available.Based on a quadratic arithmetic program (QAP), the initial proof size is 288 bytes.Pinocchio’s toolchain provides a compiler that compiles C language into arithmetic circuits, which can be further converted to QAP.The Pinocchio protocol requires the verifier to generate keys that are not universal but are circuit-specific.The progressive time complexity of the system generation and key settings of the proof system is linearly related to the calculation scale, and the verification time is linearly related to the size of the common input and output.

Groth16(2016)

Groth introduced a new ZK-ilm algorithm that has higher performance in handling R1CS.R1CS is a first-order constraint system, which is a polynomial constraint form in zk-SNARK.Gorth’s proof is the smallest data size (including only three group elements), and the verification speed is very fast.Just do three pairing operations, and a preprocessing step that structures 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.

Later, Groth16 was used in ZCash, a relatively famous privacy blockchain project (involved by Starkware founder Eli).

Bulletproofs and IPA (2016)

One of the major weaknesses of the aforementioned KZG polynomial commitment scheme is the need for a trusted setting.Bootle et al. proposed an effective zero-knowledge proof system that analyzes the opening of Pedersen’s commitments that satisfy the intrinsic product relationship.Proof of inner product proof with linear complexity takes time, 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 a trusted setting.These ideas were later adopted by Halo2 and Kimchi.

Sonic, Marlin, and Plonk (2019)

Sonic, Plonk, and Marlin solve the problem that every program in the Groth16 algorithm requires trusted settings, and introduces a common and updating structured reference string (used to implement trusted settings that only require one time).in,Marlin provides a proof system based on R1CS and has become Aleo’s core technology.

Plonk introduces a new arithmetic scheme (later known as Plonkish) and uses grand-product to check replication constraints.Plonkish also allows the introduction of dedicated 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, utilizing the characteristics of multivariate polynomials and sum-test protocols.By using a suitable polynomial commitment scheme, it implements a transparent zk-SNARK system and the time complexity of generating the proof is linear.

Lookups(2020)

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

However, these lookup arguments have a common problem, and provers need to spend a lot of money to build a complete truth table, so previous work around Lookups has been devoted to reducing the cost of proof.

Later Haböck introduced LogUp in his paper, which uses log derivatives to convert the grand-product check into the sum of the reciprocals.LogUp is critical for performance improvements in Polygon zkEVMs, as they need to split the entire truth table into multiple STARK modules.These modules must be correctly linked, and cross-table lookups can force this.Since then, the introduction of LogUp-GKR has improved the performance of LogUp through the GKR protocol.

Caulk is the first solution to make the proven time sublinear relationship with the truth table size. Its preprocessing time complexity is O(NlogN), and the storage space complexity is O(N), where N is the truth value.Table size.Other solutions followed, such as Baloo, flookup, cq and caulk+.Furthermore, Lasso proposes several improvements to avoid committing to the truth table when it has 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 Plonk’s concept and adopts multivariate polynomials.Instead of using division to check the execution of constraints, it relies on the sum-test protocol.At the same time, it also supports higher-order constraints without affecting the time of proof generation.

Because multivariate polynomials are used, there is no need to perform a fast Fourier transform (FFT), it is proved that the generated time is linearly related to the circuit scale.HyperPlonk also introduces a new permutation IOP for small fields and adopts a summation-based protocol that reduces the workload of provers, proof size, and verification time.

ZK proof system using anti-collision hash function

While Pinocchio was proposed in 2013, there are some solutions for generating circuit/arithmetic schemes that can prove that the virtual machine executes instructions correctly.Although developing an arithmetic scheme for a virtual machine is more complex or less efficient than writing dedicated circuits for some programs, it has an important advantage: no matter how complex the program is, just prove that it is executed correctly in the virtual machine..

Some ideas in TinyRAM were later improved in the design of Cairo virtual machines, followed by zk-evm and general-purpose zkvm.Using collision-resistant hash functions in proof systems eliminates the need for trusted settings or elliptic curve operations, but at the cost of proofing longer.

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 are correct.The program is compiled into TinyRAM, a simplified VM.The VM has byte-level addressable random memory, and the circuit size increases quasi-linearly in the computing scale, and can efficiently handle operations such as loops, control flows, and memory access.

in,PCP refers to Probabilistically Checkable Proof, which means that the probability checkable proof. Verifiers can check the validity of the proof with a high confidence by reading a small part of the randomly selected content in the proof.Unlike traditional proof systems where verifiers need to check the entire proof, PCP requires only limited randomness to achieve efficient verification.

Ligero (2017)

Ligero introduced a 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 a domain-independent polynomial commitment scheme.

STARKs (2018)

STARKs (Scalable Transparent ARguments of Knowledge) were proposed by Eli Ben-Sasson et al. in 2018.They implement proof complexity of ?(log²⁡?), have fast verification speeds, do not require a trusted setup, and are speculated to be post-quantum security.They are put into use by Starkware/Starknet and Cairo virtual machines.Its key innovations include Algebraic Intermediate Representation (AIR) and Fast Reed-Solomon Interactive Oracle Proof-Proof (FRI) protocols.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 methods and promotes the development of ZK.For example, Plonkish’s arithmetic scheme provides an easy way to include custom logic gates and lookup arguments; FRI has shown excellent performance as PCS, leading to the birth of Plonky.Meanwhile, using grand-products checking in AIR (randomized AIR that brings preprocessing) improves its performance and simplifies memory access parameters.zk-STARK is becoming more and more popular because it is better in generation efficiency and more ZK-friendly hash functions are being introduced.

New Polynomial Commitment Scheme (2023)

With the emergence of efficient SNARKs based on multivariate polynomials, such as Spartan or HyperPlonk, there is growing interest in new commitment schemes applicable to such polynomials.Binius, Zeromorph and Basefold all propose new ways to promise multilinear polynomials.Binius has the advantage of not having extra overhead when denoting data types (while many other proof systems use at least 32-bit field elements to represent single bits) and work on binary domains.The commitment scheme uses a brakedown designed for field-independent purposes.Basefold generalizes FRI to besides Reed-Solomon, thus achieving a domain-independent polynomial commitment scheme (PCS).

Domain-independent is a property of a polynomial commitment scheme, which refers to the commitment process in a polynomial commitment scheme that does not depend on specific properties of any particular domain.This means that commitments can be made to polynomials of any algebraic structure, such as finite domains, elliptic curves, and even integer rings.

Customizable constraint system (2023)

CCS generalizes R1CS while capturing the arithmetic of R1CS, Plonkish, and AIR without additional overhead.Using CCS in combination with Spartan IOP can generate SuperSpartan, which supports high-dimensional constraints without the need for the prover to bear the encryption cost proportional to the constraint order.In particular, SuperSpartan provides AIR with a linear time proof SNARK.

Summarize

This article reviews the progress of ZK technology since the mid-1980s.Advances in computer science, mathematics and hardware, coupled with the introduction of blockchain, have given rise to new and 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 demand, focusing on proof size, memory usage, transparency, quantum security resistance, proof time and verification time.Although there have always been two major categories of ZK’s mainstream implementation solutions (SNARK 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 solutions with new onespolynomial commitment scheme.

We can expect that the new ZK proof system will continue to emerge and performance will continue to improve.For applications using these proof systems, if they cannot follow the iterative development of the latest technologies and continuously reconstruct and apply the latest algorithms, their current leading position is only temporary.

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