Nova/IVC REPL

Point of contact: Nalin

Past few months of recursion-related work has revealed a requirement for ZK Proof Recursion, Aggregation and Composition friendly tooling. In particular, we’ve observed that https://zkrepl.dev has had an outsized impact in accelerating Circom learning/ZK educational programs for beginners and increased developer velocity for everyone else. It has also inspired other work on tooling/understanding zkSNARKs. Long term, we’d like to do the same for recursion.

In the short term, a REPL for writing ZK proofs using Nova in-browser is quite doable and would be a huge value add to accelerating Nova/SNARK recursion landscape, besides being a technically interesting and accelerationary challenge for the proving/application stack.

Nova is based on R1CS, so Circom is a great beginner friendly programming language as a substrate, and we have tooling in the form of https://github.com/nalinbhardwaj/Nova-Scotiato consume the I/O from Circom compiler and use it directly with Nova.

Additionally, the Nova/Nova-Scotia setup has full support for in-browser proving and verifying, serde for proofs/proving keys/verifying keys etc., so there’s no major technical blockers. That said, there would be a lot of product dev work to build a great REPL in understanding the recursion use cases well and providing a understandable, beginner-friendly but powerful enough scaffold to write Circom code for Nova-based recursion.

In-browser proving/verifying tweet

Strawman Proposal

image
  • Fork ZKRepl with its existing Circom setup and Monaco integrations (with Circomspect etc.)
  • Input format for the REPL
  • pragma circom 2.0.3;
    
    // Prove that I know some set of "witness" adders such that starting a
    // Fibonacci sequence with some starting public inputs and getting to
    // some output public inputs
    template Fib () {
        signal input step_in[2];
    
        signal output step_out[2];
    
        signal input adder;
    
        step_out[0] <== step_in[0] + adder;
        step_out[1] <== step_in[0] + step_in[1];
    }
    
    component main { public [step_in] } = Fib();
    
    /* INPUT = {
    		"starting_step_in": [1, 1],
    		"witness": [
    			{"adder": 1},
    			{"adder": 2},
    			{"adder": 1},
    		],
    } */
  • Adds some basic metadata about recursion here (number of steps etc)
image
  • Separate logs by step index, same with output for each step index, and one for final output
image
  • The first step of artifact generation remains the same (but we need the wasm and r1cs only, others optional nice to have)
image
  • Add a check that input length at each step = output length at said step and error in witness gen if so
  • Actual proving: buttons to generate output change to “Generate params”, “Prove”, “verify”
    1. image
    2. Internally, these use some WASM compiled package that is quite like the browser-test practically. Minimal 4 functions include:
      • Public Param Generation: Generate CRS, return pk,vkpk, vk
      • Proving: Run NN steps of recursion given starting public input (z0z_0, W1,W2,WNW_1, W_2 \dots, W_N) and returns RecursiveSNARK proofproof and zNz_N, the output
      • Compressing: Input RecursiveSNARK proofproof, output CompressedSNARK proofproof using Spartan compression
      • Verify: Verify CompressedSNARK proofproof
      • These will require the WASM/r1cs generated by the previous step to be accessible by the rust runtime. Figure out how to.
      Nice to haves
      • Verify RecursiveSNARK proofproof button
      • Fix the hover info that’ll break and make it cleanly displayed, maybe in a table or something

I expect this can be done in one FTE week to a reasonable degree of polish. Additionally, there is likely a lot of optimisation work that can go into the Nova/Nova Scotia repos to improve performance and quality based on learned experience from building this strawman REPL, and on the other end we’ll learn more about what the devex want/love the most.

This probably wouldn’t cover all use cases for SNARK recursion, but should be extendable to cover IVC (incrementally verifiable computation) use cases really well (including with other SNARK schemes in future).

Background: Nova

Nova is a newish recursion scheme from Microsoft that’s getting a lot of traction and interest in the last few months. Many teams are building on it and the tooling around it is mature enough to make the task of building a REPL possible in a short time.

For more about Nova, see https://youtu.be/SwonTtOQzAk https://youtu.be/g9ZZVTnW7lw?t=2462 and https://twitter.com/CPerezz19/status/1637764330140897281?s=20

Background: Nova Scotia

Since Nova is based on R1CS, the Circom compiler’s output is sufficient to replace the proving system from groth16/plonk to nova.

We have no dependency on snarkjs or its other (somewhat dubiously secure) JS dependencies, all proving/verifying code is Rust compiled to WASM, along with Circom’s witness generation and R1CS file