Nexus Proof System

The second main component of the Nexus zkVM is the Nexus Proof System, which provides proofs of correctness for any computation being run on the Nexus VM. In order to realize this goal and be able to support arbitrarily large computations, the Nexus Proof System relies on modern recursive zero-knowledge proof systems such as folding and accumulation schemes [KST22; KS22; BC23] to achieve a high level of parallelization.

Let $P$ be a program that has been compiled to the Nexus VM, possibly with access to co-processors. The proof generation process for $P$ has four main steps:

1. zkVM initialization;
2. program execution;
3. proof accumulation; and
4. proof compression.

The following subsections provide an overview of each of these components.

Initialization

Let $P$ be a program which we want to execute in a verifiable manner. As described above, before loading $P$ into the memory starting at address $\mathtt{0x0000}$, the Nexus VM initially sets the contents of its general-purpose registers to 0 and the value of each memory location is assumed to be undefined.

In order to enforce the consistency of the memory throughout the execution of the program $P$, the Nexus zkVM currently uses Merkle Trees [M87] for memory checking together with the Poseidon hash function [GKR21]. In this method, we compute a Merkle root associated with the current contents of the memory and we update its value whenever the contents of the memory change.

Once the Merkle Root for the initial state is computed, the Nexus zkVM starts loading the program $P$ one instruction at a time, updating the Merkle Tree Root accordingly after each memory update.

Finally, once $P$ is fully loaded into the memory, we use the Merkle Root for the current state of the memory as the public input to the execution step of the proof system.

Program Execution

After receiving a Merkle proof from the initialization step with a Merkle proof for the initial memory state with the program loaded at address $\mathtt{0x0000}$, the Nexus zkVM runs the program on the Nexus VM and generates a full execution trace for it. This execution trace is then passed to the proof accumulation step, as indicated in the following diagram, where each step $F$ denotes one step of the Nexus VM.

Proof Accumulation

In order to enable a high-level of parallelization without impacting the efficiency of the scheme, the Nexus zkVM uses proof accumulation (without SNARKs), represented by the IVC step in the diagram above. The main advantage of using such a scheme is that it realizes the notion of Incrementally Verifiable Computation (IVC) [Val08] and its Proof-Carrying Data (PCD) [CT10] generalization to the distributed setting.

Nova Folding Scheme

In the current version of the Nexus zkVM, this step makes use of the Nova folding scheme [KST22] over a cycle of elliptic curves. At a high level, Nova provides a method to prove correctness of a repeated computation $F^{(n)}(z) = F(F(F(\ldots F(z))))$ by reducing this claim to a claim about the correctness of a single invocation of $F$, where $F$ is encoded using a generalized version of the Rank 1 Constraint System, called Relaxed R1CS. In the context of the Nexus zkVM, one can think of $F$ as representing the state transition corresponding to a single machine instruction of the Nexus VM and $z$ as representing the state of the machine's memory and registers, as well as the program itself.

One main advantage of using Nova is that it has a small recursion overhead, which denotes the number of steps that a prover must prove in addition to proving an invocation of $F$ [KST22]. In particular, when used to realize an IVC scheme, Nova's recursion overhead is dominated by two group scalar multiplications and three hash computations. When used within a PCD, this overhead is slightly higher but still reasonable.

In terms of prover costs, the most expensive part of the prover's work at each folding step is to compute two multi-scalar multiplications (MSMs) of size proportional to the size of $F$. This is because the prover needs to commit to two large witness vectors at each folding step using a Pedersen commitment scheme. Despite being the most computationally expensive part of the proof generation, this computation is highly parallelizable.

Cycles of Curves

One difficulty that arises in the Nova implementation is that the group scalar multiplications used in the recursive step involve operations over a field that is different than the native field used by the proof system. Hence, as mentioned above, the Nova reference implementation (opens in a new tab) by Microsoft uses a cycle of elliptic curves to reduce the number of non-native arithmetic operations and improve its overall efficiency, This is a well-known technique introduced in [BCTV14] to improve the efficiency of elliptic-curve-based SNARK recursions. In a $2$-cycle of elliptic curves $(\mathbb{G}_1, \mathbb{G}_2)$, the size of the base field of one curve equals the scalar field (i.e., group order) of the other curve, and vice-versa.

In a nutshell, Microsoft's reference implementation for Nova works by creating two parallel copies of the IVC chain linked together in a way that allows the recursive step of one IVC chain to be verified on the other chain using native elliptic curve arithmetic operations. As shown in [KST22], this results in a largely symmetric scheme with a recursion overhead in the order of $10{,}000$ constraints (opens in a new tab) in each of the curves. Though the Nova reference implementation can work over most cycles of curves, its current implementation provides support for the pasta cycle (opens in a new tab) of two curves and the bn254 (opens in a new tab)-grumpkin (opens in a new tab) curve cycle.

Thus, one consequence of using Nova over a cycles of curves is that the proof system ends up producing a pair of proofs instead of a single one. Hence, in order to verify a Nova proof, one needs to check instances over two different group-field pairs $(\mathbb{G}_1, \mathbb{F}_1)$ and $(\mathbb{G}_2, \mathbb{F}_2)$, where $\mathbb{F}_i$ is the scalar field of $\mathbb{G}_i$.

bn254-grumpkin Curve Cycle

In order to be able to produce proofs that can be cheaply verified on Ethereum, the Nexus zkVM currently implements the Nova folding scheme using the pairing-friendly bn254 (opens in a new tab) as the primary curve (also known as bn128 or bn256), since the latter has precompile support on Ethereum. Moreover, since bn254 forms a $2$-cycle along with the grumpkin (opens in a new tab) curve, grumpkin is used as the secondary curve.

Interestingly, choosing bn254 as the primary curve by itself is not enough to achieve cheap verification on Ethereum. For that, it is also important that later phases of the proof system, such as the compression phase, only require elliptic-curve operations on bn254. Unfortunately, this means that the IVC verifier for the secondary circuit will need to be implemented as a circuit over the bn254 scalar field using non-native arithmetic.

Hence, unlike Microsoft's reference implementation, the Nexus zkVM follows the approach proposed by CycleFold [KS23] in its implementation of Nova to address concerns about non-native elliptic-curve arithmetic operations in later phases of the proof system. In this approach, instead of duplicating the IVC chain in both curves, the circuit implemented over the second curve is only used to perform a single group scalar multiplication over the base field of the first curve. Moreover, this is done in a way that allows the verifier in the first curve to avoid non-native arithmetic operations by verifiably delegating its group scalar multiplications to the second curve.

Besides not having to reason about the 2-cycle of elliptic curves in the security proof of Nova [KS23], one important advantage of CycleFold's approach over the one used in Microsoft's reference implementation is that the circuit size over the secondary curve becomes significantly smaller. More concretely, the size of the IVC verifier of the Nexus zkVM on the secondary curve is in the order of $3{,}000$ constraints. Though this could in principle be reduced to around $1{,}500$ constraints in the IVC setting, the Nexus zkVM implementation of the secondary circuit currently unifies both the IVC and PCD settings.

The reduction in circuit complexity over the secondary curve has, however, implications on the size of the IVC verifier over the primary curve since the latter circuit now needs to keep track of additional witnesses and to perform several additional small multi-scalar multiplications and hashing operations related to these witnesses. More concretely, the recursion overhead over the primary curve is in the order of $120{,}000$ constraints when used to realize an IVC scheme and $340{,}000$ constraints when used to realize a PCD scheme.

Proof Compression

Despite being highly parallelizable, the accumulated proof generated in the IVC phase is quite large, which is undesirable in practice. Besides their sizes, such proofs are also not easily verifiable by other systems. For these reasons, the final step of the proof generation is to compress the accumulated proof with a sequence of succinct (zero-knowledge) Non-Interactive Arguments of Knowledge or (zk)-SNARKs for short.

In the current design of the Nexus zkVM, the final compression step is split into two phases. In the first phase, accumulated proofs generated in the IVC phase are turned into proofs of knowledge of valid IVC proofs, whose sizes are logarithmic in the size of the underlying Nova IVC proofs. Then, in the second phase, these proofs are converted into succinct proofs of constant size which can be cheaply verified on systems such as Ethereum.

To implement the first phase of the compression step, the current design uses two different proof systems, one for each curve in thebn254-grumpkin elliptic-curve cycle.

For IVC proofs associated with the primary bn254 curve, the Nexus zkVM uses the Nova-friendly Spartan SNARK [Set20] together with the Zeromorph [KT23] polynomial commitment scheme. This combination not only allows the Nexus zkVM to produce proofs which are logarithmic in the size of the underlying Nova IVC proofs, but it also avoids the need for the SNARK prover to compute multiscalar multiplications within the R1CS circuit. This is because, as described in [KST22], Spartan can be easily turned into a proof system for committed relaxed R1CS instead of ordinary R1CS, which helps avoid the need to include commitment checks as part of the circuit to be proved.

For IVC proofs associated with the secondary grumpkin curve, the same combination used for the primary curve is not possible as grumpkin is not a pairing-friendly elliptic curve. As a result, the current design of the Nexus zkVM uses a variant of Halo2 (opens in a new tab) by the Ethereum's Privacy-Scaling-Explorations team based on the Kate-Zaverucha-Goldberg (KZG) polynomial commitment scheme [KZG10]. Though this part of the proof system is required to perform in-circuit multiscalar multiplications, the blowup in the circuit size is manageable due to the smaller size of the secondary IVC circuit. We remark, however, that this part of the design is currently under active development and may change.

To implement the second part of the compression phase, the current plan is for the Nexus zkVM to use Groth16 proofs [Gro16]. This final stage of compression will recursively verify the Spartan proofs from the first stage, reducing the log-sized proofs to a constant size.

Nexus zkVM Parameters

In order to run the Nexus zkVM, certain values used by the proof system as well as the public parameters shared between the prover and the verifier need to be configured.

Two of the main configuration parameters for the Nexus zkVM are:

• Configuration parameters for the Poseidon hash function; and
• The number $k$ of Nexus VM instructions per folding step.

As for the public parameters, these consist essentially of the following:

• Parameters for the Pedersen commitment used by Nova in the proof accumulation phase for each curve in the cycle;
• Parameters for the Zeromorph commitment used by Spartan in the compression phase; and
• Parameters for the remaining SNARKs in the compression phase.

Hash Function Configuration

In order to configure the Poseidon hash function, we currently use the parameters proposed in the Poseidon paper [GKR21] to achieve a 128-bit level of security. More precisely, we use the following parameters:

const FULL_ROUNDS: usize = 8;
const PARTIAL_ROUNDS: usize = 57;
const ALPHA: u64 = 5;
const RATE: usize = 2;
const CAPACITY: usize = 1;
const MODULUS_BITS: u64 = 254;

Instructions Per Folding Step

The Nexus zkVM's approach based on Nova provides a proof system with a recursion overhead which is independent of the total number of computation steps and of the step function itself. However, in our current implementation, the recursion overhead remains quite high (in the order of $120{,}000$ and $340{,}000$ constraints in the IVC and PCD settings) compared to the cost of a single step of the Nexus VM (around $15{,}000$ constraints).

Hence, in order to offset the current recursion overhead, the Nexus zkVM includes a configuration parameter $k$ which allows the prover to combine several steps of the Nexus VM into a single folding step. Even though a higher value of $k$ will increase the overall complexity of the prover, the value $k$ has no impact on the recursion overhead. As a result, one can improve the overall performance of the Nexus zkVM by increasing the value $k$. For instance, by choosing $k=8$ in the IVC setting, the cost of each folding step will approximately double while the total number of folding steps will be reduced by a factor $8$.

The current default value for $k$ is 16, which seems to avoid large RAM requirements for the prover while providing a reasonable offset for the recursion overhead. This value can, however, be set by the user of the Nexus zkVM.

Public Parameters

As mentioned above, the public parameters for the Nexus zkVM consist of those needed by the Pedersen commitment scheme during the accumulation phase and by the Zeromorph commitment scheme during the compression phase. Other public parameters will also be needed for the remaining SNARKs of the compression, but these are currently under development and hence omitted for now.

Regarding the public parameters for the Pedersen commitment scheme used in Nova, these consist of a vector of random group elements of sufficient size in the respective curve in the cycle. In the PCD setting with $k=1$, Nova circuits for the primary curve are represented by three sparse matrices $(A,B,C)$ each containing about $2^{19}$ rows and columns and about 8 non-zero entries per row. As a result, the size of the public parameters for the Pedersen commitment scheme contains about $2^{19}$ bn254 elliptic curve elements. Since larger values of $k$ would increase the witness size, the size of the vector would need to increase accordingly. For the secondary curve, the size of the vector depends on the size of the witness for the secondary circuit, containing about $3{,}000$ grumpkin elliptic curve elements.

As for the public parameters for the Zeromorph commitment scheme used in Spartan, these consist of a sufficiently large vector of group elements of the form $\tau^i g$, where $g$ is a generator for the group and $\tau$ is the “toxic waste” secret used to generate the vector. These public parameters are exactly the same as those used for the KZG polynomial commitment scheme [KZG10], requiring a trusted setup phase as well. As in the case of systems such as Plonk-KZG [GWC19], the trusted setup is universal and only depends on a global bound on the size of committed vectors. Regarding the actual size of this vector, the current implementation requires committing to a single vector of size $2^{26}$ when $k=1$ since the pre-processing phase of Spartan needs to commit to a specialized sparse matrix representation of $(A, B, C)$ used in Nova (see [Set20, Sections 6-7] for details). As for Pedersen commitments, larger values of $k$ would also result in larger parameters for Zeromorph.

Finally, since the parameters for the Pedersen and Zeromorph commitment schemes consist of a vector of group elements and need to be compatible in order to make Spartan a proof system for committed relaxed R1CS, the Nexus zkVM currently generates the parameters for the Pedersen commitment scheme by truncating the parameters used for Zeromorph, instead of randomly sampling a vector of fresh group elements. Note that this is cryptographically indistinguishable from a random vector, unless one knows the toxic waste secret.

References

[BC23 (opens in a new tab)] Benedikt Bünz and Binyi Chen. “Protostar: Generic efficient accumulation/folding for special sound protocols”. In: Cryptology ePrint Archive (2023).

[BCTV14 (opens in a new tab)] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. “Scalable Zero Knowledge via Cycles of Elliptic Curves”. In CRYPTO 2014.

[CT10 (opens in a new tab)] Alessandro Chiesa and Eran Tromer. “Proof-Carrying Data and Hearsay Arguments from Signature Cards.” In: ICS. Vol. 10. 2010, pp. 310–331.

[GKR21 (opens in a new tab)] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. “Poseidon: A new hash function for Zero-Knowledge proof systems”. In: 30th USENIX Security Symposium (USENIX Security 21). 2021, pp. 519–535.

[Gro16 (opens in a new tab)] Jens Groth. “On the Size of Pairing-Based Non-interactive Arguments”. In EUROCRYPT 2016.

[GWC19 (opens in a new tab)] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”. In: Cryptology ePrint Archive (2019).

[KS22 (opens in a new tab)] Abhiram Kothapalli and Srinath Setty. “SuperNova: Proving universal machine executions without universal circuits”. In: Cryptology ePrint Archive (2022).

[KS23 (opens in a new tab)] Abhiram Kothapalli and Srinath Setty. “CycleFold: Folding-scheme-based recursive arguments over a cycle of elliptic curves”. In: Cryptology ePrint Archive (2023).

[KST22 (opens in a new tab)] Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla. “Nova: Recursive zero-knowledge arguments from folding schemes”. In CRYPTO 2022.

[KT23 (opens in a new tab)] Tohru Kohrita and Patrick Towa. “Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments”. In: Cryptology ePrint Archive (2023).

[KZG10 (opens in a new tab)] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. “Constant-Size Commitments to Polynomials and Their Applications”. In ASIACRYPT 2010.

[M87 (opens in a new tab)] Ralph C. Merkle. “A digital signature based on a conventional encryption function”. In CRYPTO 1987.

[Set20 (opens in a new tab)] Srinath Setty. “Spartan: Efficient and general-purpose zkSNARKs without trusted setup”. In CRYPTO 2020.

[Val08 (opens in a new tab)] Paul Valiant. “Incrementally verifiable computation or proofs of knowledge imply time/space efficiency”. In TCC 2008.