nexus-xyz / nexus-zkvm Goto Github PK

In a new Nexus project, if one does cargo run, cargo successfully compiles / recompiles the project and then runs nexus-run <target>.

However, if one uses cargo nexus run instead, the compilation / recompilation step is skipped. Perhaps a user would expect cargo run and cargo nexus run to behave equally, so we might want to present the same behavior.

The README must be in sync with the QuickStart in the docs.

Add an example that computes a keccak hash.

A full description of the Nexus PCD Prover

PDC:

• A description of Binary-Tree Parallel Nova PDC with CycleFold
• Recursion overhead and benchmark results
• Asymptotic and concrete prover and verifier costs
• Links to the code implementation of Parallel Nova

Diagrams of the PCD tree and how it interleaves with CycleFold with the 2-cycle of curves.

Introduce the notion of a "memory controller" that is responsible for providing a backing store, reading and writing cache-lines, and generating proof objects.

We need a full description of the Nexus Proof Compression sequence:

• Architecture
• Theoretical prover costs
• Concrete prover costs
• Links to the sections in the code with the implementations
• Relevant diagrams that showcase the architecture

The current NVM needs to be extended in a number of ways. The most immediate changes needed are the ability to switch between different memory types, both for performance when not generating proofs, and for experimenting with new memory techniques; and the ability to handle input and output.

To this end, I propose the following changes to the NVM:

1. Introduce the notion of a "memory controller" that is responsible for providing a backing store, reading and writing cache-lines, and generating proof objects of some type (possibly unit).

2. Introduce a second memory controller that does not generate proofs and the ability to dynamically switch between this and the existing merkle tree (and future alternatives).

3. Modify the riscv crate to use the NVM memory controller. This reverses the dependency between these two crates, but unifies the memory implementation in one place. This will also be useful for sharing the I/O implementation.

4. Introduce private input to the riscv and NVM crates. This can be done with a single implementation in the NVM crate.

Sub-issues:

• #125
• #131
• #132

This repo will contain installable cargo commands. Initially:

• nexus new setup a new project
• nexus run run a nexus program (likely identical to cargo run)
• nexus package bundle nexus program
• nexus info get information about a nexus package
• nexus prove send program to prover network
• nexus verify verify a nexus proof
• nexus export etherum_verifier
• nexus export ethereum_calldata

The verifier reports back the time to verify, but not wether the proof was accepted or not. The verifier should give an explicit accept or reject message.
I tried using the Cargo.toml file as "proof". The verifier panicked. It would be nicer to reject the proof with an error message.

Tested with k=10 and k=100:

➜  prover git:(pg-virtual) ✗ cargo run -r -- gen -P -k 10

See the following output:

➜  nexus-project git:(master) ✗ cargo nexus local-prove
Executing program...
Hello World
Executed 64 instructions in 381.542µs. 11048 bytes used by trace.
Loading public parameters from nexus-public.zst...
Got public parameters in 20.770911208s
Primary Circuit 253502 vars x 260145 constraints, 2 io
Secondary Circuit 2870 vars x 3024 constraints, 11 io

proving 64 steps...
leaf step 0... 385.55925ms
leaf step 2... 376.617625ms
leaf step 4... 383.139542ms
leaf step 6... 378.766875ms
leaf step 8... 378.094708ms
leaf step 10... 378.335417ms
leaf step 12... 379.872208ms
leaf step 14... 380.508875ms
leaf step 16... 378.588042ms
leaf step 18... 376.722792ms
leaf step 20... 381.882542ms
leaf step 22... 384.942458ms
leaf step 24... 379.648917ms
leaf step 26... 384.359125ms
leaf step 28... 387.644583ms
leaf step 30... 381.953166ms
leaf step 32... 385.248833ms
leaf step 34... 378.290542ms
leaf step 36... 377.473042ms
leaf step 38... 386.345709ms
leaf step 40... 378.08625ms
leaf step 42... 383.498333ms
leaf step 44... 376.460458ms
leaf step 46... 386.909917ms
leaf step 48... 385.964125ms
leaf step 50... 398.792416ms
leaf step 52... 378.837083ms
leaf step 54... 382.648417ms
leaf step 56... 378.844083ms
leaf step 58... 382.05175ms
leaf step 60... 389.078542ms
leaf step 62... 392.670917ms
proving 16 vertex steps
vertex step ...  thread 'main' panicked at prover/src/error.rs:50:35:
R1CS Error InvalidWitnessLength
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

To replicate install nexus-tools, create a new Nexus project with cargo nexus new, generate the public params and copy them to the new project, and then run cargo nexus local-prove on the new project.

To reproduce, add the following code to main.rs on a new Nexus project.

#![no_std]
#![no_main]

fn fib(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 1) + fib(n - 2),
    }
}

#[nexus_rt::entry]
fn main() {
    let n = 7;
    let result = fib(n);
    assert_eq!(result, 13);
}

Then the error is:

Error: ELF format not supported: not enough room to expand code to NexusVM

Caused by:
    ELF format not supported: not enough room to expand code to NexusVM

This error is traceable to the initialization procedure of the Nexus VM at vm/src/riscv.rs.

see: https://allcontributors.org

Provide a description of the NVM I/O mechanism:

• Public input
• Private input
• Public output
• Serialization / Deserialization process
• Relationship with syscalls
• Relationship with memory-checking system

A full description of the size and architecture of the Nexus 1.0 Memory-Checking System

• Explanation for the in-memory-expansion mechanism from the RISC-V translation
• Concrete choice of parameters (leaf size, number of leafs, total memory size, arity of the memory tree, number of constraints)
• A diagram for the system.

it would be useful to have some concrete performance numbers for our system. this will be a little bit easier to do once we finish Issue #29, but it's not entirely necessary.

we have some benchmarks and profilers already in our repositories, so this should only require us to determine the right input sizes, run these, and collect the results.

• using the parallel pcd nova from the zkvm crate, compute nova proofs for the test no-op circuit. record the proof time and final proof size (say, after serialization)
  • we should do this for a range of values of k, the number of instructions per folding step: something like [1, 10, 100] should be good.
  • we should make sure the circuit is the correct size, e.g. including the memory operations.
• run the compression prover on this nova proof. record the proof time and final proof size.
  • at the moment, this can only be done from inside the supernova crate (but this is fixed by Issue #29).
• collect the results, write them down in a readable way, and add this to either the zkvm readme or as a separate file in the repo.

some notes:

• we should ignore the network for now and do everything on one machine.
• other interesting numbers to record include:
  • profiling memory usage (e.g. what's the minimum amount of memory a machine needs to be able to run each prover).
  • the sizes of the various parameter files generated during proof setup (i.e. the public parameters for nova and spartan).
• we should do this in a clean, reproducible runtime environment. running on e.g. a recent macbook should be fine. as long as we write down the specs with the results.
• it may be easiest to do all of this inside of the supernova crate instead of using the zkvm. we just need a dummy StepCircuit for Nova of the correct size.

When creating a new Nexus project with cargo nexus new, rust analyzer shows the following error.

It should be fixable as described here: rust-lang/vscode-rust#729 (comment)

The goal is to allow users to specify any type for the entry function. The inputs will be automatically loaded into memory by the VM from an input file (likely JSON), and the output automatically serialized out of memory upon termination. Importantly, we do not want this serialization and deserialization to be part of the proved computation---it is a VM function that occurs before and after the program has run.

The initial plan is define a derive macro for types that will output type layout information to a special section of the ELF file. The VM can then use this special section to encode and decode the inputs and outputs.

A full description of the Nexus IVC Prover for SuperNova with CycleFold

IVC:

• A description of SuperNova non-uniform IVC and CycleFold
• Recursion overhead and benchmark results
• Asymptotic and concrete prover and verifier costs
• A link to our SuperNova implementation
• A short discussion on our upgrade to non-uniform PCD

With relevant diagrams of the non-uniform IVC chain and how it interleaves with CycleFold and the 2-cycle of curves.

Create automated benchmark results that can be added to the docs for each release.

Computed jumps are unavoidable due to dyn traits being used in core. Recent changes created examples of dynamic dispatch that the rust compiler could not optimize away, so we have to deal with this.

This requires completion of the rv spliti: Issue #1

Implement a system for adding new instructions to the VM. This has two parts: adding new instructions to the parser and interpreter, and adding new circuits for the instructions.

• Implement CCS (#52)
• Implement NIMFS (#124)
• • Modify multilinear sumcheck implementation imported from Arkworks (c8fe9df) as needed
• Implement IVC (#144)
• • Implement folding verification gadget for R1CS-derived HyperNova, including in-circuit sumcheck (#141)

The existing rv repo contains the RISC-V VM, the arithmetization, and the code to interface with MS-Nova or Nexus-Nova. We want to split this up into separate repos as each may be open-sourced at different times.

Initially, there will be a repo containing the definition of the RISC-V instructions, parsers, and the interpreter. This repo can be used to implement a nexus-run command for development. A second repo will contain the circuits for the VM and the integration with Nexus-Nova. The MS-Nova integration will live in a third repo, which may not be maintained past a certain point if it becomes incomparable with the Nexus prover.

The README should specify the codebase structure, how to find our folding scheme implementations, compression schemes, etc.

The clean command should delete all public parameter files and run cargo clean under the hood to remove compilation targets as well.

The fix is found by modifying the docsRepositoryBase on docs/theme.config.tsx.

After the initial implementation of the network prover, we can improve:

• add encryption to network connection
• compress data before sending over network
• reduce VM witness sizes to minimize network traffic

Something similar to nextjs, reth or tokio.

For the v1 release we are setting the VM memory to less than 2^32 for better performance.

Doing cargo nexus new on a new machine that hasn't setup SSH keys fails because new adds the zkvm as a dependency using SSH and not HTTPs.

A detailed description of the public parameters generated by the Nexus zkVM.

• The value of k, the number of CPU cycles per fold, on how this value was chosen
• Details on the CRS and the trimming mechanism for the Pedersen bases
• Details on the choice of parameters for hash functions
• Size distribution (memory used) of the public parameters

A full description of the Nexus Phase 2 Nova Proof compression mechanism

A full detailed description of the Nexus 2.0 IVC Memory Checking System

• Description
• Detailed Comparison with Nexus 1.0 Memory Checking System
• Concrete choice of parameters
• Diagram(s) of the mechanism based on @JensNexus's talks, presentations, and designs.
• Reference to related literature
• Reference to our code implementation

the example runs successfully:

Executed 577470 instructions in 1.737721891s

but when running cargo nexus prove on the provided keccak example, we receive the following:

   Compiling nexus-project v0.1.0
    Finished release [optimized] target(s) in 0.09s
Executing program...
acaf3289d7b61cbd114fb36c4d29c85bbfd5e133f14cb355c3fd8d99367964f
Error: invalid instruction 48 at 14628174101512105900

Caused by:
    invalid instruction 48 at 14628174101512105900

Recent changes invalidated a number of tests which need to be updated.

When running cargo nexus run:

• Print number of NVM cycles executed

When running cargo nexus run -v:

• Print NVM execution trace
• Print number of NVM cycles executed

When running cargo nexus prove:

• Print number of NVM cycles proved

Building from PR #28, we need to add features to the nexus-zkvm prover and network crates to use the compression features in the supernova repo.

PR #28 adds a compressible option to the parameter generation methods which changes the way Nova's public parameters are set up: instead of sampling them, they are processed using a polynomial commitment scheme SRS which is loaded from file. This is required if we want to use compression later for the proof (we might want to make this behavior the default at some point, but it's optional for now to allow flexibility with testing and benchmarking).

Here's a rough outline of what needs to be done to complete this issue:

• Add a compress command to the top-level CLI (/the network API). This should do two tasks:
  • Handle the parameter setup and r1cs matrix preprocessing for Spartan, using the SNARK::setup() function from supernova. This takes both the Nova public parameters and the PCS's SRS as input, and both of these should be read from file, and creates a SNARKKey object, which should be saved to file.
  • read a proof from file, along with the Spartan parameters generated in the above step, then compress it using the SNARK::compress() function from supernova. Save the result to file: e.g. as an enum which is either a PCDNode or a CompressedPCDProof.
• Add logic to the prover's verify command to detect whether the proof is compressed or not, and if so, verify it using SNARK::verify(). This uses the SNARKKey object created in the first step above.

Note that only the parallel (PCD) version of Nova supports compression right now.

Note: (as of 1.4.24) we're in the process of merging together the supernova, spartan, and nexus-zkvm repos, and this will be cleaner to work on once that is completed. At the moment, the integration with spartan is done inside of supernova's PR #33, so this is the version of supernova that we need to use here. The integration is behind the spartan feature-flag. Working with the various private repos at the same time causes some headaches. In particular, the version of the committed-relaxed-spartan repo used here needs to match the version used in supernova. We don't yet have the ssh keys for the spartan repo saved in the secret store here, which means that for this to build, we need to point the Cargo.toml here to rev 92e884c of supernova rather than the head of the dorebell-spartan-integration branch. Once the repos (and the integration pr) are merged, we won't need to worry about this anymore. However, it should be safe to work on this issue locally before we finish merging if you can get it to build.

Self-explanatory.

Developers should be able to use Nexus Nova just as they would use Microsoft Nova

A full description of the Nexus IVC Prover

IVC:

• A description of Nova IVC and CycleFold
• A comparison of Nexus-Nova vs Microsoft Nova (recursion overhead, benchmarks)
• Asymptotic and concrete prover and verifier costs
• A reference link to Microsoft Nova
• #137

With relevant diagrams of the IVC chain and how it interleaves with CycleFold and the 2-cycle of curves.

A full description of the Nexus IVC Prover for HyperNova

IVC:

• A description of HyperNova IVC and CycleFold
• Recursion overhead and benchmarks
• Asymptotic and concrete prover and verifier costs
• A description of the sum-check protocol and our performance benchmarks for sum-check
• A link to our implementation of HyperNova
• A detailed comparison of HyperNova with Nova

No diagrams needed here.

Hi, this is really a good project!

I tried to use the VM to write some examples with crates (nostd, default-features = false) in a simple project, most work well for me!

But I failed in a simple example with sqlparser-rs in this code, it reports the error of misaligned memory access. This code could work well in a normal project (without VM), I tried to debug it, seems the SQL tokens are parsed wrong from the string (may be caused by macro).
Do you have any ideas about this eror? Thanks.