PART 1 - INTRO

Introduction

• Folding schemes like Nova are a new powerful primitive for recursive SNARKs
• For big circuits, we can fold similar computation into one big thing
• Useful in e.g. ZK-VM (Virtual Machines) and ZK-ML (Machine learning)
• Usable today with tools like Circom and Nova Scotia

About me

• @oskarth, independent researcher, Taiwan 5y
• Founded Vac.dev R&D org, created Waku.org p2p messaging protocol
• ZK: following the magic; first taste was 2019 looking into RLN for p2p, this year more focus
• Recently: writing ZKIntro.com; (Hyper)Nova/ZK-VM; mobile prover

Agenda

• What problem folding solves; examples
• Nova: Intro, how it works, performance
• Nova Scotia and step circuit; more example
• Other approaches to folding
• Where to go from here

Questions

1. What problem does folding solve?
2. What is a folding scheme?
3. Why is folding useful for ZK-VM and ZK-ML?
4. Which part of the steps in IVC does the verifier have to look at in Nova?
5. Why do we need relaxed R1CS?

Questions (cont)

6. Why do we need a final SNARK at the end?
7. What is recursion overhead and why care?
8. Why do we sometimes combine two proof systems?
9. What does Nova Scotia do?
10. What are some things that other folding schemes improve on over Nova?

What problem does folding solve?

• Prove things that require huge circuits
• Often have computation of a similar "shape"
• Recursive SNARKs: Verify a SNARK inside a SNARK
  • Why? Compression and interop
• Folding schemes provides a simple and more efficient way of doing this

Examples of folding stuff

• ZK-VM (ZK Virtual Machines)
• ZK-ML (ZK Machine Learning)
• VDF (Verifiable Delay Functions)
• Lurk (Lisp DSL), ETHDOS, …

ETHDOS

PART 2 - NOVA

Intro to Nova - first modern folding scheme*

• SNARK for iterative computation
  • prove \(y=F(F(F(F(F(x)))))\)
• Incrementally Verifiable Computation (IVC)
• Very simple, no trusted setup, efficient

How does Nova work?

• Naive approach: If we want \(y=F^n (x)\), we do all Fs in circuit and use SNARK
  • Requires a lot of memory (proportional to n)
  • Can't incrementally update
  • Verifier time inefficient
• => Incrementally Verifiable Computation (IVC)

Incrementally Verifiable Computation (IVC)

• IVC solves this
• Proceed in incremental steps, prove each step
• Verifier only looks at final proof

Prior approaches

(Source: Srinath Setty's presentation)

R1CS Folding (naive approach)

• R1CS: \(AZ \circ BZ = CZ\), where \(Z=(W,x,1)\)
  • Instance x Sat by witness W if above holds
• Goal: We want to combine two R1CS instances
• We use a Random Linear Combination (RLC) to combine naively
  • \(x \leftarrow x_1 + r \cdot x_2\)
  • \(W \leftarrow W_1 + r \cdot W_2\)

Naive approach (cont)

• \(AZ \circ BZ = A(Z_1 + r \cdot Z_2) \circ B(Z_1 + r \cdot Z_2)\)
  • Expanding out we get something \(\neq CZ\)
• This happens because of cross-terms that arise
  • Think \((a+b)^2 \neq a^2 + b^2\)
• Cross-terms: \(AZ_1 \circ BZ_1 + r \cdot \ldots + r^2 \cdot \ldots\)
• Also: \(Z=(W,x,1+r \cdot 1) \neq (W, x, 1)\)

Relaxed R1CS

• Cross-terms: Create error vector \(E\), scalar \(u\)
  • \(u \leftarrow u_1 + r \cdot u_2\)
  • \(E \leftarrow E_1 + r \cdot \ldots + r^2 \cdot E_2\)
• Now: \(AZ \circ BZ = \ldots = uCZ+E\)
  • Instance \((E,u, x)\) Sat by W if above holds
• Prover don't want to send \((W_1, W_2)\)
  • Needed by verifier to compute \(E\)

Committed Relaxed R1CS

• Treat \(W\) and \(E\) part of witness; commit to them

• Commitments: Com(\(v\), \(r\)) and Open(\(\overline{C}\),\(v\),\(r\))

• Committed relaxed R1CS

  • Instance: \((\overline{E}, u, \overline{W}, x)\)
  • Sat by Witness: \((E, W, r_E, r_W)\)

• Now we have something we can fold!

  • Non-interactivity via Fiat-Shamir

Folding scheme

(Source: Srinath Setty's presentation)

Folding flow

(Source: Srinath Setty's presentation)

Nova: Final SNARK

• Folding steps (inner proof)
• Final SNARK at the end (outer proof)
  • Spartan: efficient SNARK, no trusted setup
• Combine fast-but-big and small-but-slow

PART 3 - USING IT

How does Nova perform?

• Recursion overhead: ~20k constraints
  • Cost dominated by 2 MSMs, very fast
• Benchmarks for folding
  • Depends on a lot of factors
  • Need more data

SHA256 folding benchmarks

• SHA256 with different preimage size
• Nova ~same as Starky and x100 Halo2 (KZG)
  • Folding, w/o final SNARK
• Nova also memory-efficient
• See Nova benchmarks

Using Nova with Nova Scotia

• Nova circuits in Bellman
• Circom has a lot of dev tooling
• Nova Circuit: Compile Circom circuits to Nova

(Source: Nova Scotia repo)

Fibonacci step circuit

template Example () {
    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] } = Example();

/* INPUT =
  {"step_in": [1, 1], "step_out": [1, 2],"adder": 0 } */

Zator: Neural network with Nova

(Source: Zator repo)

PART 4: NOW WHAT

Other folding ideas

• Seen explosion in folding-related work this year
• ParaNova, SuperNova, HyperNova, Origami, Sangria, ProtoStar, ProtoGalaxy, …
  • What is going on!?
• What are the problems (some of) these solve?
  • Speedrun a few

ParaNova: Parallelize steps

SuperNova: Different functions

HyperNova: Customizable Constraint System

• Generalize R1CS with CCS
  • Enable R1CS, Plonkish, AIR
• Plonkish (custom degree gates + lookups)
• Multifolding, 1 MSM

Other stuff

• Folding schemes: ProtoStar, ProtoGalaxy
• Better lookups: Lasso, Jolt
• All this is very experimental

Where to go from here?

• Code: microsoft/Nova, Nova-Scotia, pse/folding-schemes
• Papers: Nova, SuperNova, HyperNova
• Misc: Nova-based ZK-VM, Nova benchmarks, awesome-folding, this presentation
• Talks: Nova (Srinath), SuperNova (Srinath)

Thanks! Questions?