NEXUS 백서

NEXUS

원문

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
프로젝트로 돌아가기