bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 1쪽
Nexus 1.0: Enabling Verifiable Computation
Daniel Marin ∗,
Michel Abdalla, Paul Govereau, Jens Groth, Samuel Judson, Kristian Sosnin, Guru Vamsi
Policharla, and Yinuo Zhang†
Nexus Labs
{daniel,michel,paul,jens,sam,kristian,vamsi,yinuo}@nexus.xyz
January, 2024
Abstract
We introduce the Nexus project, an endeavor to enable verifiable computation, at Internet scale.
The world has come a long way since Turing introduced in 1936 a universal computing machine , a
hypothetical machine capable of executing any computation. This concept is considered the origin
of the general-purpose computer, and was used by von Neumann to introduce the von Neumann
architecture, a physical instantiation of the Universal Turing Machine. This architecture now powers
virtually all modern computers.
In this paper, we introduce the Nexus zkVM (zero-knowledge virtual machine), a machine capable
of proving any computation. That is, the machine produces succinct zero-knowledge proofs of correct
program execution for any stateful machine (e.g. RISC-V, EVM, Wasm) with any particular instruction
set. The Nexus zkVM focuses on proving large computations (e.g. 1B+ CPU cycles), and is architected
to enable massively parallelized incremental proof generation, well suited for parallel proving in a
distributed prover network.
The zkVM is powered by modern high-speed recursive proof systems (i.e. folding / accumulation)
that allow proofs to be combined and aggregated, realizing the notions of Incrementally Verifiable
Computation (IVC) and its generalization, Proof-Carrying Data (PCD). Further, we introduce the
Nexus Virtual Machine (NVM), a simple, minimal, and extensible Universal Turing Machine: a vir-
tual CPU architecture specifically designed to maximize prover performance. The NVM is the core
computational model of the Nexus zkVM, and can simulate with minimal overhead any other ISA like
RISC-V, EVM, Wasm, etc, through compilation and emulation techniques, as well as extensions in the
instruction set (e.g. SHA-256).
We briefly describe the Nexus Network, an upcoming large-scale distributed prover network that
aggregates the collective CPU / GPU power of a pool of heterogeneous computers to instantiate
an extremely parallelized large-scale proof generation system for the Nexus zkVM. This enables the
zkVM to operate at a scale (measured in CPU cycles proved per second) proportional to the collective
computing power of the network.
Fundamentally, the Nexus project seeks to bring the concrete cost of verifiable computation down
by orders of magnitude through a variety of scientific, engineering, and economic techniques, so that
it may finally become a practical form of computation. The project builds upon decades of scientific
research in cryptography, complexity theory, compilers, and high-performance computing. We focus on
delivering a simple developer experience and a system designed to power production-grade applications,
with initial support for Rust programs.
We envision a future for the Internet where the integrity of computations and data are protected
by proofs: a future where human cooperation is enhanced by mathematical truth. This constitutes
our first construction towards that vision.
∗Main author.
†Thanks to the Nexus team for helpful discussions, listed here in alphabetical order.
1
Contents
1 Summary 3
1.1 The Nexus zkVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 The Nexus Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 The Nexus zkVM co-processors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 The Nexus Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Open-Source Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Introduction 12
2.1 Why are zero-knowledge proofs still not practical? . . . . . . . . . . . . . . . . . . . . . . 12
2.2 The Nexus System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Background 15
4 Preliminaries 18
4.1 The Sum-Check Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Non-Interactive Arguments of Knowledge (NARKs) . . . . . . . . . . . . . . . . . . . . . 18
4.3 Incrementally Verifiable Computation (IVC) . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Non-uniform Incrementally Verifiable Computation (NIVC) . . . . . . . . . . . . . . . . . 20
4.5 Proof-Carrying Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.6 Folding Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.7 Multi-Folding Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.8 Customizable Constraint Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.8.1 The CCS Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.8.2 The Committed CCS Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.8.3 The Linearized Committed CCS Relation . . . . . . . . . . . . . . . . . . . . . . . 26
5 Components 27
5.1 A Multi-Folding Scheme for CCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 A Generalized Multi-Folding Scheme for CCS . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.3 The Fiat-Shamir Transform For Multi-Folding Schemes . . . . . . . . . . . . . . . . . . . 30
5.4 The CycleFold Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.5 HyperNova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.6 Parallel Nova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.7 Parallel HyperNova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Defining Zero-Knowledge Virtual Machines 38
7 The Nexus zkVM: A General-Purpose IVC Machine 39
8 The Nexus Network: A V erifiable Supercomputer 41
2
1 Summary
In this whitepaper, we describe our vision for the Nexus project and our first set of technologies. For a
formal treatment and new techniques, please refer to our follow on technical paper.
TL;DR: Nexus is building a distributed zkVM,
designed to prove a trillion CPU cycles per second .
We believe that the world’s computers can unite into a single, verifiable supercomputer,
and jointly prove humanity’s computation.
How to read. This document progresses in an increasing level of technical detail.
• F or general readers: we recommend reading the Summary (Sec. 1) to learn about:
1. The Nexus zkVM (Sec. 1.1)
2. The Nexus Virtual Machine (Sec. 1.2 and 1.3)
3. The Nexus Network (Sec. 1.4)
• F or developers: we recommend checking out the Example (Sec. 1.6) and open-source implemen-
tation (Sec. 1.5), as well as the official Nexus documentation https://docs.nexus.xyz.
• F or advanced readers and cryptographers: we recommend reading the Introduction (Sec. 2),
and the historical Background (Sec. 3). For an in depth technical understanding of the Nexus
zkVM, we recommend Section 4 and onwards.
For questions, feedback, or to get involved, please reach out to us at hello@nexus.xyz.
1.1 The Nexus zkVM
We introduce the Nexus zkVM, a machine capable of proving any computation. Our implementation is
fully open source 1. The zkVM focuses on proving very large computations (say, 1B+ CPU cycles). It
achieves this through extreme parallelization: the zkVM realizes lightweight and unbounded Incremen-
tally Verifiable Computation (IVC) [Val08], a primitive that allows proofs of correct computation to be
computed and updated incrementally, through the use of modern high-speed recursive zero-knowledge
proof systems (i.e. folding / accumulation schemes) [KST22; KS22; KS23b; KS23a; BC23]. These tech-
niques allow for high-speed proof accumulation (see Fig 1), without using SNARKs at all.
Proof accumulation (without SNARKs), see Fig 1, is a novel technique that allows proofs to be
combined and aggregated, which in itself allows proof generation to be performed efficiently in a large-scale
network of untrusted computers. Through this, the zkVM effectivelly realizes the notion of Proof-Carrying
Data (PCD) [CT10], a generalization of IVC to the distributed setting, wherein proof computation is
performed by a distributed prover network. However, realizing high-speed IVC through SNARK-less
recursion comes at the expense of large proofs. To tackle this, we compress the final accumulated proof
with a recursive sequence of SNARKs.
Execution Sequence. The Nexus zkVM execution sequence is separated into three stages, with an
additional one-time setup phase. See Fig. 2 for a visual representation.
1https://github.com/nexus-xyz/nexus-zkvm
3
Figure 1: An r-ary proof accumulation tree of depth η, without SNARKs.
• One-time setup. Optionally specify a custom machine architecture Ξ = [ F1, . . . , Fℓ] as a list of
ℓ additional CPU instructions, and generate public parameters for the system. This only needs to
be done once for a given machine architecture.
The machine Ξ can be, for example, the empty list Ξ = [ ] (i.e. default execution on the NVM,
see Sec. 1.2), a single circuit Ξ = [ F1] (e.g. BLS signature aggregation [BLS01]), a full machine
architecture (e.g. EVM [Woo+14], RISC-V [WLPA14], Wasm [Haa+17]), or a list of custom user-
defined instructions (e.g. SHA-256, ECDSA sign) that extend the NVM.
We call these extensions zkVM co-processors, see Sec. 1.3.
Then, for every program Ψ encoded for the machine Ξ, we execute the following steps:
• Compilation. Compile the program to the Nexus Virtual Machine (NVM) instruction set. The
NVM will execute the the program Ψ on the machine Ξ.
• Execution. Execute the program on the NVM, generating the full execution trace.
• F olding.In a massively parallelized fashion, produce and accumulate IVC proofs πi for blocks of
execution. This step is the core of the proving process, and is the most computationally intensive.
However, it is extremely parallelizable, and can be done by a distributed prover network.
Every folding step requires computing a single multi-scalar multiplication (MSM). This is also the
lowest prover overhead in the context of recursive proof composition [KS23b]. In addition, MSMs
are themselves highly parallelizable, as has been well studied by industry efforts [Aas+22].
• Compression. Finally, compress the accumulated proof with a sequence of (zk)-SNARKs.
1.2 The Nexus Virtual Machine
The Nexus Virtual Machine (NVM) is a simple, minimal, and extensible Instruction Set Architecture
(ISA) and Random-Access Machine (RAM) with a von Neumann architecture that enables universal
computation. That is, it is a Universal Turing Machine. The NVM is inspired by vnTinyRAM [CGTV20]
and the RISC-V [WLPA14] ISA, but unlike the latter, it designed to maximize prover performance.
The NVM features:
• A simple CPU architecture : simple 32-bit instruction set, 40 instructions, and simplified in-
struction decoding.
4
Figure 2: The Nexus zkVM execution sequence. Here, F represents a CPU cycle on the Nexus Virtual
Machine. Step 2 (IVC / PCD) is the massively parallelized distributed SNARK-less incremental proof
generation, which happens (for technical reasons) in a 2-cycle of elliptic curves [TG14; NBS23; KS23a].
• A simple memory model : a simple 32-bit address space, with a single stack and heap, proved
incrementally with Merkle Trees [Mer87] and Poseidon hashes [Gra+21].
• A simple I/O model: a simple 32-bit input / output model, with single tapes for public input (x),
private input ( w), and public output ( y). Given a program Ψ, the NVM executes its instructions
according to the ISA on the public and private inputs and records the resulting output.
• Extensibility: the NVM can be extended with custom instructions, which we call zkVM co-
processors. These are user-defined instructions written as CCS circuits [STW23a], a generalization
of R1CS [GGPR13], Plonkish [GWC19; CBBZ23], and AIR [BBHR19; Sta21; BCKL22], that extend
the NVM instruction set, and can be used to accelerate custom instructions, without affecting per-
cycle prover performance. Nexus co-processors are thus conceptually similar to EVM precompiles
[Woo+14].
The Nexus zkVM can be seen as a combination of the NVM (the computational model) and a proof
system (the prover). The zkVM runs the NVM and produces exactly the same output. In addition, it
also constructs a succinct proof of correct computation. That is, the zkVM proves in zero knowledge,
knowledge of a private witness w such that Ψ(x, w) = y. Note that, due to the zk-SNARK at the end of
the compression step (see Fig. 2), the Nexus zkVM is actually zero knowledge (i.e. not only succinct)
and, assuming the prover does not leak it, it hides the (optional) private witness w.
5
Figure 3: The Nexus Virtual Machine.
1.3 The Nexus zkVM co-processors.
The notion of zkVM co-processors is a powerful one inspired by [KS22]. While in theory any program can
be proven as a sequence of CPU instructions, proving many kinds of simple programs in this model is prac-
tically infeasible. For example, proving even a single SHA-256 hash in the virtual machine model would
involve proving about 64,000 CPU cycles that emulate the SHA-256 function in-software. In contrast,
proving a manually-written SHA-256 hash circuit (like an ASIC) directly, outside of the abstraction of a
VM, would involve proving only about 30k constraints, which requires roughly 1000x less computation.
Such is the cost of abstraction.
In the traditional zkVM design (e.g. vnTinyRAM [CGTV20]), one uses universal circuits to simulate
a whole CPU. Adding a new instruction to the CPU, involves increasing the total number of constraints
proved per step, so the natural strategy is to minimize the size of the CPU being proven.
To escape this CPU vs. ASIC dilema, the Nexus zkVM introduces the concept of zkVM co-processors,
where the cost of proving custom co-processor extensions of the NVM instruction set, is only paid for by
the prover when that particular co-processor is executed by the guest program. This allows the Nexus
zkVM to maintain the developer-friendly CPU abstraction with a small Turing-complete ISA, while
allowing ASIC-like extensions on the instruction set (see Fig. 5), while only paying for the cost of those
instructions when they are actually executed. These techniques are possible due to recent advancements
in non-uniform IVC and related folding / accumulation techniques [KS22; BC23; ZGGX23; AST23;
GHK23].
In particular, zkVM co-processors allow the zkVM to accelerate custom cryptographic primitives
(e.g. SHA-256, ECDSA signatures), higher-level operations (e.g. matrix multiplications, computing
square roots, etc.), and even recursively composing with other SNARKs by injecting their verifier circuits
as custom instructions in the zkVM. The downside is that these custom-purpose circuits need to be
6
Figure 4: The Nexus Virtual Machine (NVM) Instruction Set Architecture (ISA).
Figure 5: The Nexus Virtual Machine zkVM co-processors, designed to allow for ASIC-like performance
for accelerated instructions as extensions on the NVM instruction set.
manually implemented, but they only need to be implemented once.
Simplicity and Universality . Beyond optimizing for prover performance, the NVM seeks to answer
a secondary question, of a social nature: Can we design a simple enough universal model of computation
(i.e. a concrete instantiation of the Universal Turing Machine), such that a proof of computation on the
NVM is universally convincing?
For example, consider proving the Fibonacci function Fib(n) by producing a proof π1 through em-
ulation of an x86 machine (with 2 120 potential instructions, and large architectural complexity), versus
obtaining a proof π2 through emulation on a say, 32-instruction machine, with only basic ADD, SUB,
XOR, etc. instructions. Which proof, π1 or π2, might be more convincing as a faithful proof of the Fib(n)
computation? Which proof, π1 or π2, might be more convincing to someone living 10 years in the future?
Which verifier circuit might be simpler to implement and audit?
1.4 The Nexus Network
The Nexus project seeks to enable verifiable computation at Internet scale. To this end, we present a
system by which the total throughput of the Nexus zkVM can be increased by orders of magnitude.
We call this system the Nexus Network, a system that aggregates the collective CPU / GPU power of
a heterogeneous computer network to instantiate an extremely parallelized large-scale proof generation
7
system for the Nexus zkVM. This allows the zkVM to operate at a scale (measured in CPU cycles proved
per second) proportional to the collective computing power of the network.
Distributed Supercomputers. Large-scale volunteer computing over the Internet has seen great
success in some notable projects. These projects have harnessed the collective computing power of
millions of volunteers to solve large-scale scientific problems, with the total computing power of these
systems measured in FLOPS (floating point operations per second). Examples include:
• The Great Internet Mersenne Prime Search (GIMPS) [96] in 1996, reaching 14 teraFLOPS in the
early 2004s.
• SETI@Home [And+02] in 1999 from NASA, which received the 2008 Guinness World Records for
the largest computation in history, reaching 668 teraFLOPS.
• Folding@Home [Beb+09] in 2000 from Stanford University, reaching 2.43 exaFLOPS, making it the
first exaFLOP computing system.
The Nexus Network seeks to do the same, but for the problem of verifiable computation. Thus, the
Nexus Network can be seen as a distributed verifiable supercomputer, that allows the zkVM to scale its
throughput in a way proportional to the collective computing power of the network.
(a) Tree view.
(b) Aerial view.
Figure 6: The Nexus Network. Proof aggregation happens in a tree-like fashion.
V erifiability in Distributed Computation. The projects mentioned above relied on varied heuristics
for ensuring the integrity of the distributed computation. For example, SETI@Home relied on replicating
computations between multiple nodes, and then comparing results amongst them. If there was a dis-
agreement, the computation would be repeated with another randomly selected set of volunteers. This
gave at best probabilistic guarantees on the integrity of the computation.
In contrast, the Nexus Network gives provable guarantees on the integrity of the distributed compu-
tation, as the output itself is a proof. Note that this is not only true of the final proof, but also of all the
intermediate proofs in the incrementally verifiable computation. For the first time, such a distributed
verifiable computation system is practically possible due to the instantiation of the Proof-Carrying Data
system based on the high-speed recursive proof aggregation techniques of the Nexus Network.
8
A V erifiable Supercomputer. Thus, we pose a bold question:
Can we unite the world’s computers into a single, verifiable supercomputer?
In particular, we think that, provided enough computing power, the Nexus zkVM may reach trillions of
CPU cycles proved per second, and so be able to prove computations that are orders of magnitude larger
than what is currently possible. The Nexus Network is the first step towards this vision.
Practical matters. The Nexus zkVM partitions the proving process into chunks of computation, which
can be arbitrarily small, and then accumulates proofs incrementally. Thanks to this, the Nexus provers
can operate with as little as 1GB of RAM. This allows even small devices like smartphones, and laptops
to participate in the network and supply useful compute. In practice, we expect large powerful provers
to dominate the supply of com프로젝트로 돌아가기