Timeline of ZK Technology Development
TechFlow Selected TechFlow Selected
Timeline of ZK Technology Development
A linear timeline of the development history of ZK technology.
Navigating Web3 tides with focused insightsAuthor: Lambda Class
Translation: Baiding, Faust, Nickqiao
Original in English 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 without revealing any private information. In recent years, ZK has gained widespread attention in verifiable private computation, providing validity proofs for computer programs, and in blockchain technology, significantly contributing to global progress.
Although ZK is an emerging technology, its foundational ideas and concepts trace back to the 1980s. The integration with blockchains such as Bitcoin and Ethereum has dramatically accelerated ZK's development, as blockchains can leverage SNARKs and STARKs for validity proofs, greatly enhancing scalability—making ZK highly sought after in the blockchain space.
As Eli Ben-Sasson, co-founder of Starkware, noted, we have recently witnessed a "Cambrian explosion" in cryptographic proof systems. Each proof system has its own unique strengths and weaknesses, involving various trade-offs in design. Advances in hardware, improved algorithms, novel arguments, and supporting tools continue to boost ZK system performance and enable new systems. Many proof systems are already deployed in real-world applications, while researchers continue to expand the boundaries of ZK.
This raises an important question: Is there a universal ZK proof system suitable for all applications? We believe this is unlikely, for three main reasons:
-
Diversity of applications;
-
Different types of constraints (including memory, verification time, proof generation time);
-
Need for robustness (if one proof system is compromised, others can serve as fallback).
For these reasons, diversity among ZK proof systems is not only expected but necessary. Yet despite the variety of systems, one common trait stands out: ZK proofs must be quickly verifiable, and there should exist a verification layer that can easily adapt to new proof systems, helping address challenges related to their underlying base layers (such as Ethereum).
In the ZK domain, zk-SNARK is frequently mentioned. It is a form of zero-knowledge proof that uses advanced mathematical tools such as bilinear pairings and arithmetic circuits to achieve efficient zero-knowledge proofs. Key features of zk-SNARK include succinctness and non-interactivity—provers and verifiers require only a single round of communication. Moreover, zk-SNARK proofs are extremely compact and fast to verify, making them ideal for resource-constrained environments.
zk-STARK is another common form, designed to overcome certain limitations of zk-SNARK. zk-STARK does not rely on trusted setup and uses more transparent mathematical constructions such as polynomial commitments, finite field operations, and hash collisions to generate and verify proofs. zk-STARK offers better scalability than zk-SNARK, supports larger-scale computations, and generates proofs faster, though the proof size itself is typically larger.
In short, both zk-SNARK and zk-STARK are widely used forms of zero-knowledge proofs, differing in transparency, scalability, proof size, and other aspects.
Overall, a ZK proof system typically consists of two main components: PIOP (Polynomial Interactive Oracle Proof) and PCS (Polynomial Commitment Scheme). Common PIOP schemes include PLONKish and GKR, while common PCS schemes include FRI, KZG, and IPA. For example, Zcash’s version of Halo2 uses Plonkish+IPA, while zk-STARK can essentially be viewed as a special type of zk-SNARK based on FRI.
More specifically, different types of proof systems employ different polynomial commitment schemes (PCS), arithmetization methods, Interactive Oracle Proofs (IOP), or Probabilistically Checkable Proofs (PCP).
Furthermore, different ZK proof systems often differ along the following dimensions:
-
Cryptographic assumptions: collision-resistant hash functions, discrete logarithm problem on elliptic curves, knowledge of exponent
-
Transparent setup vs trusted setup
-
Proof generation time: linear vs superlinear
-
Verification time: constant, logarithmic, sublinear, linear
-
Proof size
-
Ease of recursion
-
Arithmetization scheme
-
Univariate vs multivariate polynomials
In the following sections, we briefly discuss the origins of ZK technology, explore its fundamental building blocks, and outline the rise and evolution of different ZK proof systems. This article does not aim to analyze proof systems in depth, but rather focuses on the individuals who have profoundly influenced the field, as progress in any industry depends on visionary pioneers turning bold ideas into reality.
Historical Development of zk-SNARK
Origins: 1980s–1990s
As mentioned, zero-knowledge proofs are not a new concept. Their definitions, foundations, key theorems, and even critical protocols emerged as early as the mid-1980s, first appearing in Goldwasser, Micali (founder of Algorand), and Rackoff’s paper “The Knowledge Complexity of Interactive Proof Systems.”
Moreover, the key ideas and protocols we now use to build zk-SNARKs were developed in the 1990s, such as the Sumcheck protocol, which reduces claims about the sum of evaluations of a multivariate polynomial to a single evaluation at a randomly chosen point on an elliptic curve—a foundational contribution to ZK technology.
Thus, the conceptual roots of ZK predate Bitcoin by decades, yet during that time, practical use cases were scarce, and the computational power required for ZK proof systems was simply unavailable, as the internet and hardware infrastructure were underdeveloped in the 1990s.
GKR Protocol (2007)
GKR (Goldwasser-Kalai-Rothblum) is an interactive protocol where the prover’s runtime scales linearly with the number of logic gates in the circuit, while the verifier’s time is sublinear in circuit size. In GKR, the prover and verifier agree on the output of a two-input arithmetic circuit over a finite field, with depth d, where layer d is the input layer and layer 0 is the output. Starting from a claim about the circuit output, the protocol recursively reduces it to claims about higher layers, ultimately reducing the output claim to one about the input values—which is easy to verify. Indeed, the GKR protocol can be seen as a significant simplification built upon the earlier Sumcheck protocol.
KZG Polynomial Commitment Scheme (2010)
In 2010, three ZK experts—Kate from MPI-SWS in Germany, Zaverucha from Certicom Research in Canada, and Goldberg from the University of Waterloo—jointly published a paper titled “Constant-Size Commitments to Polynomials and Their Applications.” This paper introduced a polynomial commitment scheme using bilinear pairing groups, known as KZG.
The commitment consists of a single group element, and the committer can efficiently reveal correct evaluations of the polynomial at any point. With batching techniques, multiple polynomial evaluations can be revealed simultaneously. KZG commitments became a foundational building block for several well-known ZK proof systems (e.g., Halo2 used by Ethereum’s PSE team) and played a central role in Ethereum’s EIP-4844. For a more intuitive understanding of batching, see the article on the Mina-Ethereum bridge.
Reference: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Practical Elliptic-Curve-Based ZK-SNARK Systems (2013)
The first practical construction of ZK-SNARK appeared in 2013, requiring a preprocessing step to generate proof and verification keys specific to a program or circuit—non-universal in nature. These keys could be very large and depended on secret parameters; if these secrets were compromised, attackers could forge proofs. In such practical ZK-SNARK systems, converting code into a provable form involves compiling it into a set of mathematical polynomial constraints.
Initially, this process had to be done manually—time-consuming and error-prone. Subsequent technical advances aimed to solve the following core issues:
-
Achieving more efficient proofs
-
Reducing the number of preprocessing steps
-
Enabling universal, rather than circuit-specific, setups
-
Avoiding trusted setup
-
Developing methods to describe circuits using high-level languages instead of writing polynomial constraints manually
Pinocchio Protocol (2013)
The Pinocchio protocol was the first practically usable zk-SNARK system, based on Quadratic Arithmetic Programs (QAP), with initial proof sizes of 288 bytes. Its toolchain included a compiler that translated C code into arithmetic circuits, which were then converted into QAPs. Pinocchio required the verifier to generate keys that were not universal but specific to each circuit. The asymptotic time complexity for proof generation and key setup scaled linearly with computation size, while verification time scaled linearly with the size of public inputs and outputs.
Groth16 (2016)
Groth introduced a new ZK proof algorithm with improved performance on R1CS (Rank-1 Constraint System), a polynomial constraint format used in zk-SNARKs. Groth’s proofs are among the smallest (containing just three group elements) and very fast to verify, requiring only three pairing operations and a preprocessing step that structures the reference string. However, Groth16’s major drawback is that each program requires a separate trusted setup, which is inconvenient in practice.
Groth16 was later adopted by ZCash, a well-known privacy-focused blockchain project (co-developed by Starkware founder Eli).
Bulletproofs and IPA (2016)
The earlier KZG polynomial commitment scheme had a key weakness: it required a trusted setup. Bootle et al. proposed an efficient zero-knowledge proof system analyzing openings of Pedersen commitments satisfying inner product relations. The inner product argument has linear proof time, logarithmic interaction rounds between prover and verifier, but linear verification time. Additionally, Bootle et al. developed a polynomial commitment scheme that does not require trusted setup. These ideas were later adopted by systems like Halo2 and Kimchi.
Sonic, Marlin, and Plonk (2019)
Sonic, Plonk, and Marlin addressed the issue in Groth16 where each program required its own trusted setup, introducing a universal and updatable structured reference string (enabling a single trusted setup). Among them, Marlin provides an R1CS-based proof system and became the core technology behind Aleo.
Plonk introduced a new arithmetization method (later called Plonkish) and used grand-product checks to enforce copy constraints. Plonkish also allows dedicated logic gates for specific operations—so-called “custom gates.” Many prominent blockchain projects have adopted customized versions of Plonk, including Aztec, zkSync, Polygon zkEVM, Mina, Ethereum’s PSE team, and Scroll.
Spartan (2019)
Spartan provides an IOP for circuits described using R1CS, leveraging properties of multivariate polynomials and sum-check protocols. By combining with suitable polynomial commitment schemes, it enables a transparent zk-SNARK system with linear proof generation time.
Lookups (2020)
Gabizon and Williamson introduced plookup in a 2020 paper, using grand-product arguments to prove that a value exists within a precomputed lookup table, demonstrating how to integrate plookup parameters into the Plonk framework.
However, these lookup arguments share a common issue: the prover incurs high costs to construct the full lookup table. Much subsequent work focused on reducing this cost.
Later, Haböck introduced LogUp, which uses logarithmic derivatives to transform grand-product checks into sums of reciprocals. LogUp was crucial for improving Polygon zkEVM’s performance, as they needed to split the entire lookup table into multiple STARK modules. These modules must be correctly linked, and cross-table lookups enforce this. Subsequently, LogUp-GKR further improved LogUp’s efficiency via the GKR protocol.
Caulk was the first scheme to achieve sublinear proof time relative to lookup table size, with preprocessing complexity O(N log N) and storage complexity O(N), where N is the table size. Other schemes followed, such as Baloo, flookup, cq, and caulk+. Lasso proposed several improvements to avoid committing to tables when they have specific structures.
HyperPlonk (2022)
HyperPlonk was introduced in the paper “HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates.” Based on Plonk’s philosophy, it uses multivariate polynomials. Instead of using division to check constraints, it relies on sum-check protocols. It also supports high-degree constraints without affecting proof generation time.
By using multivariate polynomials, Fast Fourier Transforms (FFT) are avoided, resulting in linear-time proof generation relative to circuit size. HyperPlonk also introduces a new permutation IOP suitable for small fields and leverages sum-check-based protocols to reduce prover workload, proof size, and verification time.
ZK Proof Systems Using Collision-Resistant Hash Functions
Around the same time Pinocchio was introduced in 2013, alternative approaches to circuit generation and arithmetization emerged, enabling proofs of correct execution of instructions in virtual machines. While developing arithmetization for VMs is more complex or less efficient than writing custom circuits for specific programs, it offers a key advantage: regardless of program complexity, one only needs to prove correct execution within the VM.
Ideas from TinyRAM were later refined in the design of the Cairo VM, followed by zk-EVM and general-purpose zkVMs. Using collision-resistant hash functions in proof systems eliminates the need for trusted setup or elliptic curve operations, albeit at the cost of longer proof times.
TinyRAM (2013)
In “SNARKs for C,” the authors developed a proof system based on PCP to prove correct execution of C programs. The program is compiled into TinyRAM, a simplified VM with byte-addressable random-access memory. Circuit size grows quasi-linearly with computation scale, efficiently handling loops, control flow, and memory access.
Here, PCP stands for Probabilistically Checkable Proof, where the verifier checks only a small, randomly selected portion of the proof to verify correctness with high confidence. Unlike traditional proof systems requiring full proof inspection, PCPs enable efficient verification with limited randomness.
Ligero (2017)
Ligero introduced a proof system achieving proof size O(√n), where n is the circuit size. It arranges polynomial coefficients in matrix form. Brakedown builds on Ligero and introduces the concept of domain-agnostic polynomial commitment schemes.
STARKs (2018)
STARKs (Scalable Transparent ARguments of Knowledge) were proposed in 2018 by Eli Ben-Sasson et al. They achieve 𝑂(log²𝑛) proof complexity, offer fast verification, require no trusted setup, and are conjectured to be post-quantum secure. They are adopted by Starkware/Starknet alongside the Cairo VM. Key innovations include Algebraic Intermediate Representation (AIR) and the Fast Reed-Solomon Interactive Oracle Proximity (FRI) protocol. STARKs are also used by many prominent blockchain projects (e.g., Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync).
New Directions
The practical deployment of different proof systems highlights the strengths of various approaches and drives ZK innovation. For example, the Plonkish arithmetization provides a simple way to incorporate custom gates and lookup arguments; FRI has proven excellent as a PCS, enabling Plonky. Also, using grand-products in AIR (leading to randomized preprocessing AIR) improves performance and simplifies memory access. zk-STARK is gaining popularity due to better proof generation efficiency and the emergence of more ZK-friendly hash functions.
New Polynomial Commitment Schemes (2023)
With the emergence of efficient SNARKs based on multivariate polynomials (e.g., Spartan or HyperPlonk), interest has grown in new commitment schemes for such polynomials. Binius, Zeromorph, and Basefold propose novel ways to commit to multilinear polynomials. Binius excels by representing data types without overhead (unlike other systems that use at least 32-bit field elements per bit) and operates over binary fields. Its commitment scheme adopts the domain-agnostic brakedown. Basefold extends FRI beyond Reed-Solomon codes, achieving domain-agnostic PCS.
Domain-agnosticism is a property of polynomial commitment schemes meaning the commitment process does not depend on specific properties of any algebraic domain. This allows commitments to polynomials over any algebraic structure—finite fields, elliptic curves, or even rings of integers.
Customizable Constraint Systems (2023)
CCS generalizes R1CS while capturing the arithmetization of R1CS, Plonkish, and AIR without added overhead. Combining CCS with the Spartan IOP yields SuperSpartan, which supports high-dimensional constraints without proportional cryptographic cost to constraint degree. Notably, SuperSpartan provides a SNARK for AIR with linear-time proving.
Conclusion
This article reviews the progress of ZK technology since the mid-1980s. Advances in computer science, mathematics, and hardware, combined with the advent of blockchain, have led to new and more efficient ZK proof systems, opening doors to transformative applications.
Researchers and engineers continue refining ZK systems, focusing on proof size, memory usage, transparency, quantum resistance, proof and verification time. While the dominant ZK implementations have historically fallen into two categories (SNARKs and STARKs), the boundary between them is blurring, as strengths from different systems are being combined—such as integrating diverse arithmetizations with new polynomial commitment schemes.
We can expect continued emergence of new ZK proof systems with ever-improving performance. For applications relying on these systems, failing to keep pace with technological advancements and continuously adopt the latest algorithms means any current lead is only temporary.
Join TechFlow official community to stay tuned
Telegram:https://t.me/TechFlowDaily
X (Twitter):https://x.com/TechFlowPost
X (Twitter) EN:https://x.com/BlockFlow_News
@class_lambda
