bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 2쪽
pute in the system, as clusters of GPUs, FPGAs or ASICs, optimized for
computing MSMs, are many times more powerful.
1.5 Open-Source Implementation
So what has been implemented? The Nexus zkVM and the Nexus Network are fully open source, and
both are implemented in Rust. These include:
1. Proof accumulation: Nova, CycleF old, and HyperNova. Following the original open-source
implementation of Nova [KST22] from Microsoft Research in 2022, we provide the first production-
grade implementation of the Nova and follow-up proof accumulation systems, all built from-the-
ground-up in arkworks [ark22]:
• The Nova folding scheme [KST22]
• The CycleFold multi-folding scheme [KS23a]
• The Nova + CycleFold IVC proof system (see Sec. 5.4)
• The binary-tree parallelized Nova scheme (see Sec. 5.6)
• In progress, the first implementations of CCS [STW23a] and HyperNova [KS23b]
We hope these are useful to the community and other projects as well. We are actively improving
these with new techniques [BC23; ZZD23; ZGGX23]. Our implementation presents concretely a
50k recursion overhead (measured in number of constraints) for Nova with CycleFold, and a 200k
recursion overhead for parallel Nova with CycleFold. We shall report measurements for HyperNova
in our follow-on technical paper.
2. The Nexus zkVM. An implementation of the Nexus zkVM, and all the steps in the execution
sequence: generation, compilation (witness extraction), execution, folding, and proof compression.
See Fig. 2.
Using the Nexus zkVM on any Rust program such as Example 1 is as simple as doing:
$ cargo nexus prove → $ cargo nexus verify
3. The Nexus Virtual Machine. An implementation of the NVM, and it’s arithmetized version in
R1CS, with Merkle proofs for memory checking, as well as a RISC-V-to-NVM compiler.
The NVM arithmetization, which is rather naive still, is a circuit of size 30k per CPU cycle. This
is a large circuit (mainly due to memory-checking), but we expect upcoming improved memory-
checking techniques to reduce the size of the machine by 10x, with further order-of-magnitude
9
improvements coming from the use of zkVM co-processors [KS22; ZGGX23; GHK23], and lookup
arguments [STW23b; AST23].
Normal users do not have to worry about this intermediate optimization, but it leads to significant
performance improvements from compiler optimizations, and better security due to the simplicity
of the machine.
4. The Nexus Network. An open-source implementation of the Nexus Network, featuring three
different types of nodes:
• The Nexus MSM Prover , a prover node that can be run on any machine with at least 1
GB of RAM. These nodes supply compute to the network by computing MSMs on-demand.
Supplying compute to the system is as simple as doing:
$ cargo nexus compute
• The Nexus PCD Prover , a prover node that can be run on any machine, and can supply
compute to the network by computing IVC proofs. The Nexus team currently operates these.
• The Nexus Aggregator, a node that aggregates proofs and compresses them with SNARKs,
by applying the Nexus zk-SNARK compression sequence (see Fig. 2).
5. The Nexus Proof Compression Sequence.
We present:
• A Nova-friendly zkSNARK . The first implementation (besides Microsoft’s [KST22]) of a
zk-SNARK for an aggregation-friendly generalization of R1CS: A modified Spartan [Set20] zk-
SNARK for the commited relaxed R1CS [KST22] relation, adapted from the original Spartan
arkworks [ark22] implementation for R1CS.
• An implementation of the Zeromorph [KT23] polynomial commitment scheme.
We further apply a final level of proof compression with other SNARKs [Gro16; BGH19; BGH20]
to achieve Ethereum verifiability for Nova proofs, which allows Nexus to conncect to Ethereum.
These details will be described in the technical paper.
What has not yet been implemented:
• Non-uniformity . Our current implementations do fully-uniform IVC (see Fig. 5), but not non-
uniform. Support for CCS extensions is actively being developed.
• zkVM I/O . The Nexus zkVM currently does not support I/O (e.g. loading a JSON file). All
input must be encoded in the program itself. This is a small but important limitation that will be
addressed in the comming weeks.
10
1.6 Example
1 #![no_std]
2 #![no_main]
3
4 #[nexus::main]
5 fn fib(n: u32) -> u32 {
6 match n {
7 0 => 1,
8 1 => 1,
9 _ => fib(n - 1) + fib(n - 2),
10 }
11 }
Listing 1: Example of a Rust program provable on the Nexus zkVM.
11
2 Introduction
T uring Machines. In his seminal 1936 paper [Tur+36], Turing introduced the Turing machine, a
formalization of the notion of computation. He was the first to observe that general-purpose computation
is possible and showed the existence of a universal Turing machine, a machine which can simulate the
execution of any other machine. Similarly, Kurt G¨ odel, Alonzo Church, and others had also arrived at
formal definitions of computation in the early 1930s, all of which ended up being identical in expressive
power.
The von Neumann Architecture. The notion of the Universal Turing Machine quickly led other
scientists, such as von Neumann, to construct implementations. Today, essentially all digital computers
follow the “von Neumann architecture” [Von93]. The Nexus VM also follows the von Neumann architec-
ture.
Classical Proofs. In 1956, G¨ odel wrote a letter to von Neumann [G¨ od56; Sip92], where he identified
how “it would have consequences of the greatest magnitude” if there existed a practical machine that
could efficiently prove mathematical theorems. As we will see, this notion is close to that of proving
computations. G¨ odel had essentially posed what we know today as the (still unsolved)P = NP question,
which deals with the relationship between deterministic (super-polynomial time) provers (i.e. the class
NP), (polynomial time) verifiers (i.e. the class P), and the notion of proofs 2.
Zero-Knowledge Proofs. Fast forward to 1985, the story of (zero-knowledge) interactive proofs be-
gan at MIT, in a paper by Goldwasser, Micali, and Rackoff [GMR19] that introduced the class IP, a
generalization of NP that allows randomness and interaction between the prover and verifier. This fun-
damentally changed the notion of proof itself. The definition of zero-knowledge, which they introduced
as well, considers proofs that reveal nothing besides their own validity. Their paper would win the first
ever G¨ odel Prize.
Since then, a cambrian explosion of research introduced other notions of proofs, such as Arthur-Merlin
protocols [Bab85] (concurrent work), MIPs [BGKW19; FRS88; BFL91], PCPs [FRS88; BFLS91; AS92;
Aro+92], IOPs [BCS16], NIZK [BFM88; BSMP91], proofs of knowlede [SP92], succinct arguments and
CS proofs [Kil92; Mic94], and (zk)-SNARKs [Mic94; Gro10; BCCT12; GGPR13]. For a short recap of
the history of zero-knowledge proofs and modern techniques until present, see Section 3.
The Nexus project builds upon these works and nearly four decades of research since the invention
of zero-knowledge proofs. We believe that due to very recent scientific progress, truly scalable zero-
knowledge for the Internet era is close within the horizon.
2.1 Why are zero-knowledge proofs still not practical?
The ASIC Approach. Current typical approaches to compute zero-knowledge proofs consist in writing
arithmetic circuits, either manually (e.g. R1CS, Plonkish, AIR, etc.), through libraries like Bellman
[Zkc15] or arkworks [ark22], or through a higher-level DSL (e.g. Circom [ide21], Zokrates [Zok17], Noir
[Noi20], Leo [Chi+21], etc.) with a DSL-to-circuit compiler, and then proving the circuit with a zk-
SNARK. For the zk-SNARK, Groth16 [Gro16] is the most widely used in practice (due to practical
Ethereum compatibility and its small proof size), followed by Halo and Halo2 [BGH20]. The ASIC
approach is thus coneptually similar to designing a custom ASIC for a given computation, and then
proving the ASIC’s execution with a zk-SNARK.
2For a more precise description, see the excellent books in computational complexity theory [AB09] and [Wig19].
12
Disadvantages. Unfortunately, this approach is very error prone and requires a high degree of
expertise. Further, the DSL approach places static bounds on the programs (e.g. arrays and loops must
have a fixed size known at compile-time) [Chi+21], does not support input-dependent control flow and
memory accesses [BCTV14], and does not allow for self-modifying code. This approach also results in
a different circuit being generated for every program, which requires redeploying new verifier code to be
deployed each time, a highly impractical and often undesirable operation.
These are all large limitations in practice: even if the developer is willing to learn a new DSL or to
manually write arithmetic circuits (which is a highly non-trivial task), they will learn that most programs
are practically uncomputable in this model.
The CPU Approach. A modern approach, introduced in [BCTV14], is to prove computer programs
as opposed to arithmetic circuits. This is done by emulating a CPU or Virtual Machine (VM), by
implementing the full VM as a single universal circuit. In this model, the size N of the universal circuit
is proportional to the sum of the sizes of the instructions in its instruction set. Then, a sequence of state
transitions of the VM is proven by glue-ing many such universal circuits together, up to a static bound T
on the runtime of the program, and then proving the ( N · T )-sized circuit with a SNARK. This approach
was introduced by TinyRAM [CGTV20], and has resulted in industry applications like the Cairo zkVM
[GPR21] and other zkEVM projects for the Ethereum Virtual Machine.
Advantages. The advantage of this approach is better developer experience. Writing programs for
a pre-existent or well-defined ISA is significantly simpler, as developers can exploit tooling and compiler
infrastructure. Moreover, since the circuit is universal, only a single verifier needs to be deployed (this is
in practice a significant advantage). Further, the large effort of writing the universal circuit for a given
VM like the EVM (a very large effort that has taken months or years to complete to serveral projects)
only needs to be done once, and then any program for that ISA, up to the specified time bound T , can
be proven.
Disadvantages. However, the CPU approach has several disadvantages, mainly related to perfor-
mance and scalability.
1. Bounded computation. This approach requires deciding on a static bound T on the runtime
of all possible program executions. Proving beyond T cycles requires either (1) generating new
public parameters and deploying a new verifier for a new bound T ′ (increasing also prover time
and memory) [Ben+13; BCTV14], or (2) doing SNARK recursion [BGH20; BCMS20; B¨ un+21;
CGSY23].
2. High cost of SNARK recursion. The second option consists in proving executions in chunks
of size T and “glue-ing” the proofs together by writing the full SNARK verifier itself as a circuit
(which is in practice very hard to do), and proving that the SNARK verifier at step i has accepted
the SNARK proof from step i − 1. This approach is extremely costly and is well-known to be
impractical [BCTV17; CCDW20; KST22]. In practice, this has led projects like TinyRAM, the
Cairo zkVM, and other zkEVM projects, to consume large computational resources while only
being able to prove practically small programs (e.g. smart contracts).
3. Low performance due to emulation. However, this approach faces serious scalability issues.
First, the VM abstraction leads to much larger circuits than circuits that do not. For example,
proving a keccak256 hash, verifying an ECDSA signature, or aggregating BLS signatures through
emulation consists on proving tens of thousands or millions of CPU cycles, as these operations have
to be emulated within the CPU abstraction [GPR21]. Secondly, proving T copies of a universal
circuit requires large prover machines with very large memory (e.g. about 100 GBs of RAM),
necessary to materialize the ( T · N )-sized witness.
13
4. Practical security .Lastly, these techniques are hardly auditable. Even if one implements a whole
VM as a circuit (after months or years of effort), and say, a full SNARK verifier as a circuit as
well (for recursion), it is still hard to convince oneself that the circuits are actually implemented
correctly, and have no vulnerabilities [OWBB23; CMS23; Cog+23]. Even a single missing constraint
in the circuit implementation would lead to a full soundness exploit (e.g. as shown in [NBS23]),
and the verifier would accept invalid proofs.
2.2 The Nexus System
The Nexus system addresses the above limitations in scalability:
• The Nexus Network. The network addresses problems (1) and (2), through unbounded SNARK-
less recursion and high-speed proof aggregation. In other words, the Nexus zkVM can connect to
the Nexus Network and perform massively parallelized proving of unbounded computations in a
distributed prover network, which partitions and aggregates proofs incrementally.
• The Nexus zkVM. The Nexus zkVM addresses problems (3) and (4), through the NVM and
the use of zkVM co-processors, which allow for ASIC-like performance for accelerated instructions
in the NVM instruction set. 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. Further, the NVM is extremely simple, auditable and highly modular.
We hope that these two systems combined will allow developers to focus on declaratively writing, in any
programming language, what they want to prove, and simply receive a proof within seconds.
We believe users should not have to think through the complex (and highly non-trivial) security and
performance properties behind the 40+ years of zero-knowledge research and related high-performance
engineering that power the Nexus system.
14
3 Background
We briefly review the history of scientific advancements that have led us up to this point in time. As we
shall see, we seem to sit at the brink of a time where a new form of computation, verifiable computation,
becomes available to humanity. We believe it is very few times in a civilization’s history that a new form
of computation is introduced, and we are excited to be part of this moment.
The Nexus project builds on the shoulders giants: great scientists and mathematicians, and their
decades-long work. For an in-depth discussion, see Goldreich’s excellent article [Gol93] A Taxonomy of
Proof Systems, or the summary in Ben-Sasson et al. [BCS16], both upon which we base our discussion.
Interactive Proofs. Goldwasser, Micali, and Rackoff [GMR19] introduced interactive proofs in 1985.
In a k-round interactive proof, a probabilistic polynomial time verifier exchanges k messages with an all
powerful prover, and then accepts or rejects. IP[k] is the class of languages with a k-round interactive
proof, which generalizes the class NP by allowing randomness and interaction between the prover and
verifier. Independently, Babai introduced Arthur-Merlin games [Bab85]. AM[k] is the class of languages
with a k-round Arthur–Merlin game. Goldwasser and Sipser [GS86] showed that the two models are
equally powerful, that is IP[k] ⊆ AM[k + 2]. In 1992, Lund, Fortnow, Karloff, and Nisan [LFKN92]
introduced the sum-check (interactive proof) protocol [LFKN92] (which now powers most of our system,
see Sec. 4.1, and our implementations for the [Set20; KS23b; STW23a] protocols), and Shamir [Sha92],
building on this, showed that IP = PSPACE. The latter was a major result showing that interactive
proofs are more powerful than previously thought.
Multi-prover interactive proofs (MIPs). Ben-Or, Goldwasser, and Widgerson [BGKW19] intro-
duced multi-prover interactive proofs in 1988. In a k-round p-prover interactive proof, a probabilistic
polynomial-time verifier interacts k times with p non-communicating all-powerful provers, and then ac-
cepts or rejects. MIP[p, k] is the class of languages that have a k-round p-prover interactive proof. In
[BGKW19], the authors prove that 2 provers always suffice (i.e. MIP[p, k] = MIP[2, k]). Fortnow, Rompel,
and Sipser [FRS88] show that MIP[poly(n), poly(n)] ⊆ NEXP. Two years later, Babai, Fortnow and Lund
[BFL91] showed that MIP[2, 1] = NEXP.
Probabilistically checkable proofs (PCPs). Probabilistically checkable proofs were introduced by
[FRS88; BFLS91; AS92; Aro+92]. In a probabilistically-checkable proof, a probabilistic polynomial-time
verifier has oracle access to a proof string; PCP[r, q] is the class of languages for which the verifier uses
at most r bits of randomness, and queries at most q locations of the proof. The above results on MIPs
imply that PCP[poly(n), poly(n)] = NEXP. Later works “scaled down” this result to NP: Babai, Fortnow,
Levin and Szegedy [BFLS91] show that NP = PCP[O(log n), poly(log n)]; Arora and Safra [AS92] show
that NP = PCP[O(log n), O(√log n)]; and Arora, Lund, Motwani, Sudan, and Szegedy [Aro+92] showed
that NP = PCP[O(log n), O(1)]. This last is known as the PCP Theorem, a major result in complexity
theory, and another a paper that would win the G¨ odel Prize.
Argument systems In cryptography, one often considers argument systems , which are IPs where
soundness is relaxed from perfect to only computational. This allows circumventing various well-known
limitations of IPs [BHZ87; PS05]. Kilian [Kil92] provided the first construction of a succinct interactive
argument system by employing PCPs in conjunction with Merkle trees [Mer87]. Micali [Mic94] through
his computationally sound proof construction made a similar protocol non-interactive in the random oracle
model [BR93] by applying the Fiat-Shamir transform [FS86], thereby obtaining the first zk-SNARK.
The Random Oracle Model (ROM). An idealized model for studying computationally-bounded
provers is the Random Oracle Model (ROM) [BR93; CGH04; KM15]. At a high level, the ROM is a
15
model where the prover has access to a random oracle, which is a function that returns random outputs for
each input. The ROM is used in conjunction with the Fiat-Shamir transform [FS86] to compile interactive
proofs into non-interactive ones, yielding NARKs (non-interactive argument systems) [BCCT12]. See Sec.
4.2 for the definition of NARKs.
zk-SNARKs Many works have obtained SNARK and zk-SNARK constructions [Kil92; Mic94]. Af-
ter Micali, Lipmaa [DL08] obtained a construction based on added assumptions. Groth [Gro10] ob-
tained the first pairing-based zk-SNARK. In practice, the most widely used zk-SNARK in industry is
Groth16 [Gro16] due to its small proof size. Other constructions that have seen success are Halo and
Halo2 [BGH20], Plonk [GWC19], Spartan [Set20], Marlin [Chi+20], HyperPlonk [CBBZ23], Bulletproofs
[B¨ un+18], and others [Wah+18; MBKM19; Xie+19; AHIV17; Ben+19; ZXZS20; Gol+21; XZS22].
Interactive Oracle Proofs (IOPs). IOPs were introduced by Ben-Sasson, Chiesa, and Spooner
[BCS16]. An IOP is a generalization of IPs, MIPs and PCPs, that can compiled to SNARKs using
a suitable commitment scheme. Using a univariate polynomial commitment scheme, one can compile
Polynomial-IOPs to SNARKs, yielding protocols like Sonic [MBKM19], Marlin [Chi+20], and Plonk
[GWC19]. Using multilinear polynomial commitment schemes, one can combine multilinear-IOPs to
SNARKs, yielding protocols like Hyrax [Wah+18], Libra [Xie+19], and Spartan [Set20]. Using vec-
tor commitment schemes, one can compile vector-IOPs to SNARKs, yielding protocols like STARK
[BBHR18b], Aurora [Ben+19], Virgo [ZXZS20], Brakedown [Gol+21], and Orion [XZS22], generally all
known as STARKs. While STARKs have the benefit of requiring no trusted setup and being plausibly
post-quantum secure, they have large proof sizes (e.g. tens of kilobytes) and long verification times, and
are therefore impractical for recursion.
Incrementally V erifiable Computation (IVC). Incrementally Verifiable Computation (IVC) was
introduced in 2008 at MIT by Valiant [Val프로젝트로 돌아가기