ArkStream Capital: Milestones in Forty Years of Zero-Knowledge Proof Technology Development
TechFlow Selected TechFlow Selected
ArkStream Capital: Milestones in Forty Years of Zero-Knowledge Proof Technology Development
This paper provides a systematic review of the historical literature and latest research on zero-knowledge proof technology over the past four decades.
Navigating Web3 tides with focused insightsAuthor: @renkingeth
Abstract
Zero-knowledge proofs (ZKP) are widely regarded in the blockchain field as one of the most significant technological innovations since distributed ledger technology and are also a key focus area for venture capital. This article provides a systematic review of nearly four decades of historical literature and recent research on zero-knowledge proof technology.
First, it introduces the fundamental concepts and historical background of zero-knowledge proofs. Then, it focuses on circuit-based zero-knowledge proof technologies, including design, application, and optimization methods of models such as zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, and Ligero. In the computing environment domain, this article discusses ZKVM and ZKEVM, exploring how they enhance transaction processing capacity, protect privacy, and improve verification efficiency. The article also covers zero-knowledge rollups (ZK Rollup) as a Layer 2 scaling solution, detailing their working mechanisms and optimization approaches, along with recent advancements in hardware acceleration, hybrid solutions, and dedicated ZK EVMs.
Finally, the article looks ahead to emerging concepts such as ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, and ZK StateChannels, examining their potential in blockchain scalability, interoperability, and privacy protection.
By analyzing these latest technologies and development trends, this article offers a comprehensive perspective on understanding and applying zero-knowledge proof technology, demonstrating its immense potential in enhancing the efficiency and security of blockchain systems and providing valuable insights for future investment decisions.
Introduction
Today, as the internet progresses into the Web3 era, blockchain applications (DApps) are rapidly evolving, with new applications emerging almost daily. In recent years, blockchain platforms have handled millions of user activities every day and processed billions of transactions. The vast amount of data generated by these transactions typically includes sensitive personal information such as user identities, transaction amounts, account addresses, and balances. Given the open and transparent nature of blockchains, all this stored data is publicly accessible, raising multiple security and privacy concerns.
Currently, several cryptographic techniques can address these challenges, including homomorphic encryption, ring signatures, secure multi-party computation, and zero-knowledge proofs. Homomorphic encryption allows computations on encrypted data without decryption, helping protect account balances and transaction amounts but cannot safeguard account addresses. Ring signatures provide a special form of digital signature that hides the signer's identity, thus protecting account addresses, but offer no protection for account balances or transaction amounts. Secure multi-party computation enables distributed computation tasks among multiple participants without any participant knowing others' data, effectively protecting account balances and transaction amounts, but similarly fails to protect account addresses. Moreover, homomorphic encryption, ring signatures, and secure multi-party computation cannot be used to verify whether a prover possesses sufficient funds in a blockchain environment without revealing transaction amounts, account addresses, and balances (Sun et al., 2021).
Zero-knowledge proof is a more comprehensive solution—a verification protocol that allows verifying the truth of certain statements without disclosing any intermediate data (Goldwasser, Micali & Rackoff, 1985). This protocol does not require complex public-key infrastructure, and repeated executions do not give malicious users opportunities to extract additional useful information (Goldreich, 2004). With ZKP, verifiers can confirm whether a prover has sufficient funds without exposing any private transaction data. The verification process involves generating a proof containing the transaction amount claimed by the prover, transmitting this proof to the verifier, who then performs predefined calculations and produces a final result to determine whether to accept the prover’s claim. If the claim is accepted, it means the prover indeed has sufficient funds. Such verification processes can be recorded on the blockchain without forgery (Feige, Fiat & Shamir, 1986).
This characteristic makes ZKP play a central role in blockchain transactions and cryptocurrency applications, particularly in privacy protection and network scalability, making it not only a focal point of academic research but also widely recognized as one of the most important technological innovations since the successful implementation of distributed ledger technology—especially Bitcoin. It is also a key area for industry applications and venture capital investment (Konstantopoulos, 2022).
Consequently, numerous ZKP-based network projects have emerged, such as ZkSync, StarkNet, Mina, Filecoin, and Aleo. As these projects evolve, algorithmic innovations around ZKP emerge continuously, reportedly with new algorithms appearing almost weekly (Lavery, 2024; AdaPulse, 2024). Additionally, hardware development related to ZKP technology is advancing rapidly, including chips specifically optimized for ZKP. For example, projects like Ingonyama, Irreducible, and Cysic have completed large-scale fundraising, reflecting not only rapid progress in ZKP technology but also a shift from general-purpose hardware to specialized hardware such as GPUs, FPGAs, and ASICs (Ingonyama, 2023; Burger, 2022).
These developments indicate that zero-knowledge proof technology is not only a major breakthrough in cryptography but also a key driving force for broader blockchain technology adoption—particularly in improving privacy protection and processing capabilities (Zhou et al., 2022).
Therefore, we decided to systematically organize knowledge about zero-knowledge proofs (ZKP) to better support our future investment decisions. To this end, we comprehensively reviewed core academic papers on ZKP (ranked by relevance and citation count) and thoroughly analyzed materials and whitepapers from leading projects in the field (ranked by funding size). This integrated collection and analysis of information laid a solid foundation for writing this article.
I. Fundamentals of Zero-Knowledge Proofs
1. Overview
In 1985, scholars Goldwasser, Micali, and Rackoff first introduced zero-knowledge proof (Zero-Knowledge Proof, ZKP) and interactive zero-knowledge (Interactive Zero-Knowledge, IZK) in their paper "The Knowledge Complexity of Interactive Proof-Systems." This paper laid the foundation for zero-knowledge proofs and defined many influential concepts for subsequent academic research. For instance, knowledge was defined as "the output of an unfeasible computation," meaning knowledge must be both an output and a non-trivial computation—that is, it cannot be a simple function but rather a complex one. Unfeasible computation is typically understood as an NP problem—one whose solution can be verified for correctness in polynomial time, where polynomial time refers to an algorithm whose running time can be expressed as a polynomial function of input size. This is a crucial standard in computer science for measuring algorithmic efficiency and feasibility. Since solving NP problems is computationally complex, they are considered infeasible; however, verifying solutions is relatively straightforward, making them ideal for zero-knowledge proof verification (Goldwasser, Micali & Rackoff, 1985).
A classic example of an NP problem is the traveling salesman problem, which seeks the shortest path visiting a series of cities and returning to the origin. While finding the shortest route may be difficult, verifying whether a given path is optimal is relatively easy because calculating the total distance of a specific path can be done in polynomial time.
In their paper, Goldwasser et al. introduced the concept of "knowledge complexity" to quantify the amount of knowledge revealed by the prover to the verifier in an interactive proof system. They also proposed interactive proof systems (Interactive Proof Systems, IPS), where the prover and verifier interact through multiple rounds to prove the truth of a statement (Goldwasser, Micali & Rackoff, 1985).
In summary, Goldwasser et al. defined zero-knowledge proof as a special kind of interactive proof in which the verifier learns nothing beyond the truth of the statement being proved. They outlined three fundamental properties:
-
Completeness: If the statement is true, an honest prover can convince an honest verifier;
-
Soundness: If the prover does not know the statement, they can only deceive the verifier with negligible probability;
-
Zero-knowledge: After the proof process, the verifier only knows that the prover possesses the knowledge, without learning anything else (Goldwasser, Micali & Rackoff, 1985).
2. Example of Zero-Knowledge Proof
To better understand zero-knowledge proofs and their properties, here is an example illustrating how a prover can demonstrate possession of some secret information, divided into three stages: setup, challenge, and response.
Step 1: Setup
In this step, the prover aims to create evidence proving knowledge of a secret number s without directly revealing s. Define the secret number;
Choose two large primes p and q, compute their product. Let primes p and q, compute the resulting n;
Compute v = s² mod n, where v is sent to the verifier as part of the proof but is insufficient for the verifier or any observer to deduce s;
Randomly select an integer r, compute x = r² mod n and send it to the verifier. This value x is used in later verification but does not expose s. Let random integer r, compute resulting x.
Step 2: Challenge
The verifier randomly selects a bit a (either 0 or 1) and sends it to the prover. This "challenge" determines the next steps the prover must take.
Step 3: Response
Based on the value of a sent by the verifier, the prover responds:
If a = 0, the prover sends r (where r is the previously randomly chosen number).
If a = 1, the prover computes z = r × s mod n and sends it. Suppose the verifier sends random bit a; based on the value of a, the prover computes z;
Finally, the verifier uses received g to check whether g² ≡ x × va mod n. If the equation holds, the verifier accepts the proof. When a = 0, the verifier computes r² ≡ x mod n; when a = 1, the verifier computes (r × s)² ≡ x × v mod n.
Here, we see that the verifier's calculation confirms the prover successfully passed verification without revealing the secret number s. Since a can only be 0 or 1, there are only two possibilities, so the probability of the prover passing by luck is 1/2. But if the verifier repeats the challenge multiple times, and the prover consistently changes relevant numbers and always passes verification, the probability of success by luck becomes (1/2)k (approaching zero), thereby proving the prover indeed knows secret s. This example demonstrates completeness, soundness, and zero-knowledge properties of the zero-knowledge proof system (Fiat & Shamir, 1986).
II. Non-Interactive Zero-Knowledge Proofs
1. Background
Traditionally, zero-knowledge proofs (ZKP) are conceptualized as interactive and online protocols—for example, Sigma protocols typically require three to five interaction rounds to complete authentication (Fiat & Shamir, 1986). However, in scenarios such as instant transactions or voting, there is often no opportunity for multiple interactions, especially within blockchain applications where offline verification capability is particularly important (Sun et al., 2021).
2. Introduction of NIZK
In 1988, Blum, Feldman, and Micali first proposed the concept of non-interactive zero-knowledge (NIZK) proofs, demonstrating that provers and verifiers could complete authentication without multiple rounds of interaction. This breakthrough made real-time transactions, voting, and blockchain applications feasible (Blum, Feldman & Micali, 1988).
They proposed that NIZK consists of three phases:
-
Setup
-
Computation
-
Verification
In the setup phase, a computational function converts security parameters into common knowledge (accessible to both prover and verifier), usually encoded in a common reference string (CRS). This defines how proofs are computed and verified using correct parameters and algorithms.
In the computation phase, a computational function takes inputs and a proving key to generate the result and proof.
In the verification phase, the validity of the proof is checked using a verification key.
Their proposed common reference string (CRS) model enables non-interactive zero-knowledge proofs for NP problems based on all participants sharing a string. The operation of this model relies on the trusted generation of the CRS, requiring all participants to access the same string. Only when the CRS is correctly and securely generated can schemes built upon it ensure security. For a large number of participants, generating the CRS can be both complex and time-consuming, so although such schemes are generally easy to operate and produce small proof sizes, their setup process remains challenging (Blum, Feldman & Micali, 1988).
Subsequently, NIZK technology experienced rapid development, giving rise to various methods for transforming interactive zero-knowledge proofs into non-interactive ones. These methods differ in assumptions about system construction or underlying cryptographic models.
3. Fiat-Shamir Transform
The Fiat-Shamir transform, also known as the Fiat-Shamir heuristic or Fiat-Shamir paradigm, was proposed by Fiat and Shamir in 1986 as a method to convert interactive zero-knowledge proofs into non-interactive ones. This approach reduces interaction rounds by introducing hash functions and relies on security assumptions to ensure proof authenticity and resistance to forgery. The Fiat-Shamir transform uses public cryptographic hash functions to replace parts of randomness and interactivity, with its output serving somewhat as a CRS. Although considered secure in the random oracle model, it depends on the assumption that hash outputs are uniformly random and independent across different inputs (Fiat & Shamir, 1986). Canetti, Goldreich, and Halevi (2003) showed that while this assumption holds in theoretical models, it may face challenges in practice, posing risks when applied. Micali later improved this method by compressing multiple rounds into a single round, further simplifying the interaction process (Micali, 1994).
4. Jens Groth and His Research
Jens Groth's subsequent research greatly advanced the application of zero-knowledge proofs in cryptography and blockchain technology. In 2005, he, Ostrovsky, and Sahai jointly proposed the first perfect non-interactive zero-knowledge proof system applicable to any NP language, ensuring universal composability (UC) security even against dynamic/adaptive adversaries. Additionally, leveraging number-theoretic complexity assumptions, they designed a concise and efficient non-interactive zero-knowledge proof system that significantly reduced CRS and proof sizes (Groth & Sahai, 2005).
In 2007, Groth, Cramer, and Damgård began commercializing these technologies. Through experimental validation, their public-key encryption and signature schemes showed significant improvements in efficiency and security, although based on bilinear group assumptions (Groth & Sahai, 2007). In 2011, Groth further explored integrating fully homomorphic encryption with non-interactive zero-knowledge proofs, proposing a scheme that reduced communication overhead so that NIZK size matched witness size (Groth, 2011). In subsequent years, he collaborated with other researchers on deep studies of pairing-based techniques, providing compact and efficient non-interactive proofs for large-scale statements, though still within the bilinear group framework (Bayer & Groth, 2012; Groth, Kohlweiss & Pintore, 2016; Bootle, Cerulli, Chaidos, Groth & Petit, 2015; Groth, Ostrovsky & Sahai, 2012; Groth & Maller, 2017).
5. Other Research
In specific application scenarios, designated-verifier non-interactive zero-knowledge proofs have demonstrated unique practical value. For example, Cramer and Shoup developed a public-key encryption scheme using universal hash functions that effectively resisted chosen-ciphertext attacks in 1998 and 2002. Furthermore, in the key registration model, a new non-interactive zero-knowledge proof method was successfully developed, suitable for solving all NP-class problems, with the key requirement that participants register their own keys for subsequent verification (Cramer & Shoup, 1998, 2002).
Additionally, Damgård, Fazio, and Nicolosi (2006) proposed an improved version of the existing Fiat-Shamir transform, enabling non-interactive zero-knowledge proofs without direct interaction. In their method, the verifier first registers a public key for subsequent encryption operations. The prover uses additive homomorphic encryption to perform computations on data without knowing it, generating encrypted responses to challenges. The security of this method relies on the "complexity leverage assumption," positing that certain computationally hard problems might be solvable for adversaries with extraordinary resources (Damgård, Fazio & Nicolosi, 2006).
Ventre and Visconti (2009) introduced the concept of "weak accountability soundness" as an alternative to this assumption, requiring that an adversary attempting to produce a false proof must not only recognize its falsity but also clearly understand how they succeeded in creating it. This significantly increases the difficulty of deception, as the adversary must explicitly know their deceptive method. In practice, an adversary using this concept must provide a specific proof containing ciphertext information targeting a designated verifier, which cannot be completed without the verifier’s private key, thus exposing fraudulent behavior during detection (Ventre & Visconti, 2009).
The Unruh transform, proposed in 2015, is an alternative to the Fiat-Shamir transformation. The Fiat-Shamir method is generally insecure against quantum computing and may yield insecure schemes for certain protocols (Unruh, 2015). In contrast, the Unruh transform provides provably secure non-interactive zero-knowledge proofs (NIZK) against quantum adversaries in the random oracle model (ROM). Similar to the Fiat-Shamir method, the Unruh transform requires no additional setup steps (Ambainis, Rosmanis & Unruh, 2014).
Furthermore, Kalai et al. proposed an argument system for arbitrary decision problems based on private information retrieval techniques. This method uses a multi-prover interactive proof system (MIP) model and transforms MIP into an argument system via Aiello et al.'s method. This construction operates in the standard model without relying on random oracle assumptions and has been applied to some "Proofs-for-Muggles" zero-knowledge arguments (Kalai, Raz & Rothblum, 2014).
Building on these technologies, non-interactive zero-knowledge proofs (NIZK) have been widely applied in fields requiring high security and privacy protection, such as financial transactions, electronic voting, and blockchain technology. By reducing interaction rounds and optimizing proof generation and verification processes, NIZK not only improves system efficiency but also enhances security and privacy protection capabilities. In the future, as these technologies continue to advance and mature, we can expect NIZK to play increasingly important roles in more domains, providing a solid technical foundation for safer and more efficient information processing and transmission (Partala, Nguyen & Pirttikangas, 2020).
III. Circuit-Based Zero-Knowledge Proofs
1. Background
In cryptography, especially when handling highly parallelized and specific types of computational tasks (such as large-scale matrix operations), the traditional Turing machine model exhibits certain limitations. The Turing machine model requires complex memory management mechanisms to simulate an infinite tape and is unsuitable for directly expressing parallel computing and pipelining operations. In contrast, the circuit model, with its unique computational structure advantages, is better suited for certain specific cryptographic processing tasks (Chaidos, 2017). This article will detail circuit-based zero-knowledge proof systems (Zero-Knowledge Proof Systems Based on Circuit Models), which emphasize using circuits (typically arithmetic or Boolean circuits) to express and verify computational processes.
2. Fundamental Concepts and Characteristics of Circuit Models
In circuit-based computational models, a circuit is defined as a special computational model capable of converting any computational process into a series of gates and wires, where gates perform specific logical or arithmetic operations. Specifically, circuit models fall into two main categories:
-
Arithmetic circuits: Primarily composed of addition and multiplication gates, used to handle elements over finite fields. Arithmetic circuits are suitable for complex numerical computations and are widely used in cryptographic algorithms and numerical analysis.
-
Logic circuits: Composed of basic logic gates such as AND, OR, NOT, used for Boolean operations. Logic circuits are suitable for simple judgment logic and binary computations, commonly used in control systems and simple data processing tasks (Chaidos, 2017).
3. Circuit Design and Applications in Zero-Knowledge Proofs
In zero-knowledge proof systems, circuit design involves expressing the problem to be proven as a circuit. This process requires significant "reverse thinking" in designing zk circuits: "If the claimed output of a computation is true, the output must satisfy certain requirements. If these requirements are difficult to model using only addition or multiplication, we require the prover to perform extra work to make modeling easier." The design process typically follows these steps (Chaidos, 2017):
-
Problem representation: First, convert the problem to be proven—such as the computation process of a cryptographic hash function—into circuit form. This includes decomposing computational steps into basic circuit units like gates and wires.
-
Circuit optimization: Optimize circuit design through techniques such as gate merging and constant folding, reducing the number of required gates and computational steps to improve system efficiency and response speed.
-
Conversion to polynomial representation: Adapt the optimized circuit into polynomial form to suit zero-knowledge proof technology. Each circuit component and connection corresponds to specific polynomial constraints.
-
Generate common reference string (CRS): During system initialization, generate a CRS including proving and verification keys for use in subsequent proof generation and verification.
-
Proof generation and verification: The prover runs computations on the circuit using private inputs and the CRS to generate a zero-knowledge proof. The verifier can then validate the proof's correctness using the public circuit description and CRS without learning the prover's private information (Chaidos, 2017).
Designing zero-knowledge proof circuits involves converting specific computational processes into circuit representations and constructing polynomial constraints to ensure computational accuracy while avoiding disclosure of any extra personal information. Key tasks in circuit design include optimizing circuit structure and generating effective polynomial representations, aiming to enhance the efficiency of proof generation and verification. Through these steps, zero-knowledge proof technology can verify computational correctness without revealing additional information, satisfying dual needs for privacy protection and data security (Chaidos, 2017).
4. Potential Deficiencies and Challenges
Drawbacks include:
-
Circuit complexity and scale: Complex computations require large circuits, significantly increasing computational costs for proof generation and verification, especially when handling large datasets;
-
Optimization difficulty: Although techniques (e.g., gate merging, constant folding) can optimize circuits, designing and optimizing efficient circuits still requires deep expertise;
-
Adaptability to specific computational tasks: Different tasks require different circuit designs, making it time-consuming and difficult to generalize efficient circuits for each specific task;
-
Difficulty implementing cryptographic algorithms: Implementing complex cryptographic algorithms (e.g., hash functions or public-key encryption) may require numerous logic gates, complicating circuit design and implementation;
-
Resource consumption: Large-scale circuits demand substantial hardware resources, potentially encountering bottlenecks in power consumption, heat dissipation, and physical space in actual hardware implementations (Goldreich, 2004; Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
Solutions and improvement directions:
-
Circuit compression techniques: Reduce the number of required logic gates and computational resources through research and application of efficient circuit compression methods;
-
Modular design: Improve reusability and scalability of circuit design through modularization, reducing workload for redesigning circuits for different tasks;
-
Hardware acceleration: Use specialized hardware (e.g., FPGA or ASIC) to accelerate circuit computations, improving overall performance of zero-knowledge proofs (Goldreich, 2004; Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
IV. Zero-Knowledge Proof Models
1. Background
General-purpose circuit-based zero-knowledge proofs are limited, requiring new models and algorithms for specific problems. Various high-level language compilers and low-level circuit composition tools exist for circuit generation and design algorithms, with conversions performed manually or automatically via compiler. Manual conversion usually yields more optimized circuits, while automatic conversion is more convenient for developers. Performance-critical applications typically require manual conversion tools (Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
This article will discuss some of the most famous ones. Overall, these models are extensions or variants of zkSNARKs technology, each attempting to optimize for specific application requirements (e.g., proof size, computational complexity, setup needs).
Each protocol has specific applications, advantages, and limitations, particularly regarding setup requirements, proof size, verification speed, and computational overhead. They find applications across domains—from cryptocurrency privacy and secure voting systems to general computation verification in zero-knowledge settings (Čapko, Vukmirović & Nedić, 2019).
2. Common Algorithmic Models
1. zkSNARK Model: Proposed in 2011 by cryptographer Bitansky et al., an acronym for "Zero-Knowledge Succinct Non-Interactive Argument of Knowledge," it is an improved zero-knowledge proof mechanism. If extractable collision-resistant hash (ECRH) functions exist, SNARKs for NP problems are possible, demonstrating applicability in delegated computation, succinct non-interactive zero-knowledge proofs, and succinct two-party secure computation. This research also showed that SNARK existence implies ECRH necessity, establishing foundational links between these cryptographic primitives (Bitansky et al., 2011).
A zkSNARK system consists of setup, prover, and verifier components. The setup generates proving key (PK) and verification key (VK) using predefined security parameter l and F-arithmetic circuit C. All inputs and outputs of this circuit are elements in field F. PK is used to generate verifiable proofs, while VK verifies generated proofs. Using the generated PK, the prover creates proof p from inputs x ∈ Fⁿ and witness W ∈ Fʰ, where C(x, W) = 0ˡ. Here, C(x, W) = 0ˡ indicates the output of circuit C is 0ˡ, with x and W as input parameters. n, h, and l represent dimensions of x, W, and C's output, respectively. Finally, the verifier uses VK, x, and p to verify p, deciding whether to accept or reject the proof (Bitansky et al., 2011).
Additionally, zkSNARKs possess several extra features. First, verification completes quickly, and proof size is typically just a few bytes. Second, no synchronized communication is needed between prover and verifier—any verifier can verify the proof offline. Third, the prover algorithm runs in polynomial time. Since then, various improved zkSNARK models have emerged, further optimizing performance and application scope (Bitansky et al., 2011).
2. Ben-Sasson Model: Ben-Sasson et al. (2013, 2014) proposed a new zkSNARK model for program execution on von Neumann RISC architecture. Then, based on the proposed general-purpose circuit generator, Ben-Sasson et al. built a system demonstrating its application in verifying program execution. The system includes two components: a cryptographic proof system for verifying arithmetic circuit satisfiability, and a circuit generator converting program execution into arithmetic circuits. This design outperforms prior work in functionality and efficiency, especially due to the circuit generator's universality and additive dependency on output circuit size. Experimental evaluation shows the system can handle programs up to 10,000 instructions, generating succinct proofs at high security levels with verification time as low as 5 milliseconds. Its value lies in providing efficient, general, and secure zk-SNARK solutions for practical applications such as blockchains and privacy-preserving smart contracts (Ben-Sasson et al., 2013, 2014).
3. Pinocchio Model: Proposed by Parno et al. (2013), a complete non-interactive zero-knowledge argument generation suite (Parno et al., 2013). It includes a high-level compiler providing developers an easy way to convert computations into circuits. These compilers accept code written in high-level languages, allowing easy conversion of both old and new algorithms. However, code structure may have some restrictions to generate appropriately sized circuits.
Another feature of Pinocchio is using a mathematical structure called quadratic arithmetic programs (QAPs), efficiently converting computational tasks into verification tasks. QAPs can encode any arithmetic circuit into a set of polynomials, requiring only linear time and space complexity to generate them. Proofs generated by Pinocchio are 288 bytes in size, independent of computational task complexity and input/output size. This greatly reduces data transmission and storage overhead. Pinocchio's verification time is typically 10 milliseconds, reducing verification time by 5–7 orders of magnitude compared to previous work. For some applications, Pinocchio can even achieve faster verification than local execution. It also reduces the prover's proof overhead, decreasing it by 19–60 times compared to earlier works (Parno et al., 2013).
4. Bulletproofs Model: Designed in 2017 by Benedikt Bünz et al. (2018), a novel non-interactive ZKP model. It requires no trusted setup, and proof size grows logarithmically with witness size. Bulletproofs are especially suitable for range proofs in confidential transactions, able to prove a value lies within a certain range using minimal group and field elements. Additionally, Bulletproofs support aggregation of range proofs, enabling a single proof via a concise multiparty computation protocol, greatly reducing communication and verification time. Bulletproofs' design makes them highly efficient and practical in decentralized, trustless environments like cryptocurrencies. Strictly speaking, Bulletproofs are not traditional circuit-based protocols—their succinctness is inferior to SNARKs, and verifying Bulletproofs takes longer than verifying SNARK proofs. However, they are more efficient in scenarios not requiring trusted setup.
5. Ligero Model: A lightweight zero-knowledge argument model proposed by Ames et al. (2017). Ligero's communication complexity is proportional to the square root of verification circuit size. Additionally, Ligero can rely on any collision-resistant hash function. It can also function as a zkSNARK scheme in the random oracle model. This model requires neither trusted setup nor public-key cryptosystems. Ligero is suitable for very large verification circuits and medium-to-large circuits in applications.
3. Schemes Based on Linear PCP and Discrete Logarithm Problems
Ishai and Paskin (2007) proposed using additively homomorphic public-key encryption to reduce communication complexity in interactive linear PCPs. Subsequently, Groth et al. published multiple studies from 2006 to 2008 proposing NIZK schemes based on discrete logarithm problems and bilinear pairings, achieving perfect completeness, computational soundness, and perfect zero-knowledge. The scheme represents statements as algebraic constraint satisfaction problems, using Pedersen-commitment-like cryptographic commitment schemes to achieve sublinear proof length and non-interactivity without the Fiat-Shamir heuristic. Although requiring large CRS and strong cryptographic assumptions ("knowledge of exponent"), sufficiently long CRS enables constant proof length. Verification and proof costs are high, suggesting adoption of a "simulation-extractability" security model. These schemes are based on linear PCP and/or discrete logarithm problems but lack post-quantum security (Groth, 2006, 2006, 2008; Groth & Sahai, 2007).
6. Groth16 Model: An efficient non-interactive zero-knowledge proof system proposed by Jens Groth in 2016. The protocol is based on elliptic curve pairings and quadratic arithmetic programs (QAP), designed to provide concise, fast, and secure zero-knowledge proofs.
7. Sonic Model: Proposed by M. Maller et al. (2019), based on Groth's updatable CRS model, using polynomial commitment schemes, pairings, and arithmetic circuits. Requires trusted setup, achievable via secure multi-party computation. Once CRS is generated, supports circuits of arbitrary size.
8. PLONK Model: A general-purpose zk-SNARK proposed in 2019, using permutation polynomials to simplify arithmetic circuit representation, making proofs simpler and more efficient. It is versatile and supports recursive proof composition (Gabizon, Williamson & Ciobotaru, 2019). The PLONK model claims to reduce Sonic's proof length and improve proof efficiency, though it has not undergone peer review.
9. Marlin Model: An improved zk-SNARK protocol combining the efficiency of algebraic proof systems with the generic and updatable setup properties of Sonic and PLONK, offering improvements in proof size and verification time (Chiesa et al., 2019).
10. SLONK Model: A new protocol introduced by Zac and Ariel in an ethresear.ch document, an extension of PLONK aimed at addressing specific computational efficiency issues and enhancing original PLONK system functionality, typically involving changes in underlying cryptographic assumptions or implementation (Ethereum Research, 2019).
11. SuperSonic Model: Applies a novel polynomial commitment scheme to transform Sonic into a zero-knowledge scheme without trusted setup. Lacks post-quantum security (Bünz, Fisch & Szepieniec, 2019).
4. Schemes Based on Proofs-for-Muggles
"Proofs-for-Muggles," introduced by Goldwasser, Kalai, and Rothblum in 2008, is a new zero-knowledge proof method. It constructs interactive proofs with polynomial-time provers in the original interactive proof model, applicable to a wide range of problems. Through Kalai et al.'s transformation, these proofs can become non-interactive zero-knowledge proofs (Kalai, Raz & Rothblum, 2014).
12. Hyrax Model: Based on Proofs-for-Muggles, Wahby et al. (2018) first designed Hyrax, a low-communication, low-cost zero-knowledge argument scheme with low cost for both prover and verifier. This scheme does not require trusted setup. When applied to batch statements, verification time has sublinear relation to arithmetic circuit size with good constants. The prover's runtime scales linearly with arithmetic circuit size with good constants. Achieves non-interactivity via Fiat-Shamir heuristic, based on discrete logarithm problem, lacking post-quantum security.
13. Libra Model: The first ZKP model featuring linear prover time, succinct proof size, and verification time. In Libra, to reduce verification overhead, the zero-knowledge mechanism uses a slightly randomized polynomial method to mask the prover's response. Additionally, Libra requires one-time trusted setup depending only on circuit input size. Libra exhibits excellent asymptotic performance and superior prover efficiency. Its proof size and verification time performance are also highly efficient (Xie et al., 2019).
Regarding computational complexity of the prover algorithm, Libra outperforms Ben-Sasson's model, Ligero, Hyrax, and Aurora. Moreover, Libra's prover algorithm complexity is independent of circuit type (Partala, Nguyen & Pirttikangas, 2020).
14. Spartan Model: A zero-knowledge proof system proposed by Srinath Setty (2019), aiming to provide efficient proofs without trusted setup; achieves non-interactivity via Fiat-Shamir transformation. Known for its lightweight design and ability to efficiently handle large circuits.
5. Zero-Knowledge Based on Probabilistically Checkable Proofs (PCP)
Kilian (1992) constructed the first interactive zero-knowledge argument scheme for NP, achieving polylogarithmic communication. The scheme uses collision-resistant hash functions, interactive proof systems (IP), and probabilistically checkable proofs (PCP). The prover and verifier (as randomized algorithms) communicate through multiple rounds, with the verifier testing the prover's knowledge of the statement. Typically only one-sided error is considered: the prover can always defend true statements, but the verifier may accept false statements with low probability. In 2000, Micali used the Fiat-Shamir transformation to convert the scheme into a single-message non-interactive one. The following implementations can be seen as adopting this approach:
15. STARK Model: In 2018, ZK-STARKs (Scalable Transparent ARgument of Knowledge) technology was proposed by Ben-Sasson et al., aiming to solve inefficiencies in zk-SNARKs when handling complex proofs. Simultaneously, it addressed the issue of verifying computational integrity on private data, providing transparent and post-quantum secure proofs without relying on any trusted party.
That same year, Ben-Sasson et al. founded StarkWare Industries and developed StarkEx, the first scalability solution based on ZK-STARKs. According to Ethereum's official documentation, it achieves non-interactivity via the Fiat-Shamir paradigm in the random oracle model. The construction is post-quantum secure, though its security relies on non-standard cryptographic assumptions about Reed-Solomon codes. ZK-STARKs share characteristics with ZK-SNARKs but offer the following advantages: a) Scalability: Faster verification. b) Transparency: Verification process is public. c) Larger proof size: Requires higher transaction fees (StarkWare Industries, 2018, 2018).
16. Aurora Model: Proposed by Ben-Sasson et al. (2019), a succinct non-interactive argument (SNARG) based on STARK. Non-interactivity is based on the Fiat-Shamir construction. It applies to arithmetic circuit satisfiability. Aurora's argument size relates polylogarithmically to circuit size. Additionally, Aurora has several attractive features. It has a transparent setup. There are no known effective quantum computing attacks that can break Aurora. Fast symmetric encryption is used as a black box. Aurora optimizes proof size. For example, with a 128-bit security parameter, Aurora's proof size is up to 250 kilobytes. Aurora and Ligero, by optimizing proof size and computational overhead, are well-suited for zero-knowledge proofs on resource-constrained devices. These optimizations not only enhance efficiency but also expand the application scope of zero-knowledge proof technology, enabling its use in more practical scenarios.
17. Succinct Aurora Model: Proposed by Ben-Sasson et al. (2019) in the same paper—an extension of the Aurora protocol providing further optimized proof size and verification process. It retains Aurora's transparent setup and security features while enhancing efficiency.
18. Fractal Model: Proposed by Chiesa et al. (2020), a preprocessing SNARK using recursive composition to improve efficiency and scalability. It leverages logarithmic proof size and verification time, particularly suitable for complex computations.
6. Classification by CPC (Common Proof Construction) Setup Phase
-
First Generation (G1)—Each circuit requires separate trusted setup: zkSNARK, Pinocchio, Groth16
-
Second Generation (G2)—One-time setup for all circuits: PlonK, Sonic, Marlin, slonk, Libra
-
Third Generation (G3)—Proof systems requiring no trusted setup: Bulletproofs, STARKs, Spartan, Fractal, Supersonic, Ligero, Aurora, Succinct Aurora (Čapko, Vukmirović & Nedić, 2019; Partala, Nguyen & Pirttikangas, 2020).
V. Overview and Development of Zero-Knowledge Virtual Machines
1. Background
The previous sections focused more on the development of zero-knowledge proofs (ZKP) in cryptography. Next, we briefly introduce its development in computer science.
In 2019, Andreev et al. first proposed the concept of ZK-VM at the "ZkVM: Fast, Private, Flexible Blockchain Contracts" conference, as an implementation of zero-knowledge proof systems. The goal of ZK-VM is to generate zero-knowledge proofs by running virtual machine programs, verifying the correctness of program execution without revealing input data.
VM (Virtual Machine) is a software-simulated computer system capable of executing programs similar to physical computers. VMs are typically used to create isolated operating system environments for software testing and development. VM or VM abstraction can generally be understood as CPU abstraction—the process of abstracting the complex operations and architecture of a computer's processing unit (CPU) into a simple, operable instruction set architecture (ISA) to simplify the design and execution of computer programs. In this abstraction, computer programs can run via virtual machines (VMs) that simulate the operational behavior of real CPUs (Henderson, 2007).
Zero-knowledge proofs (ZKP) typically need to be executed via CPU abstraction. The setting is that the prover runs a public program on private inputs and wishes to prove to the verifier that the program executed correctly and produced the claimed output, without revealing the computation's inputs or intermediate states. CPU abstraction is very useful in this context because it allows programs to run in controlled virtual environments while generating proofs (Arun, Setty & Thaler, 2024).
Example: The prover wants to prove ownership of a password corresponding to a hash value without revealing the password:
Password → Hash Function → Hash Value
Private → Public
Typically, the prover should be able to run code performing the hash operation and generate a "proof" allowing anyone to verify the proof's correctness—i.e., the prover indeed owns a valid preimage for the given hash value.
Systems generating these VM abstraction proofs are commonly called "zkVMs." This name is actually misleading because ZKVMs do not necessarily provide zero-knowledge. In short, a ZKVM is a virtual machine focused on zero-knowledge proofs, extending traditional VM functionality to generally lower the development barrier for zero-knowledge circuits and enable immediate proof generation for arbitrary applications or computations (Zhang et al., 2023).
2. Classification of Existing ZKVMs
Based on design objectives, mainly categorized into three types:
1. Mainstream ZKVMs
These ZKVMs leverage existing standard instruction set architectures (ISA) and compiler toolchains, suitable for a wide range of applications and development environments.
-
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
Add to FavoritesShare to Social Media
Arkstream Capital
