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

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

Questions (cont)

Why do we need a final SNARK at the end?
What is recursion overhead and why care?
Why do we sometimes combine two proof systems?
What does Nova Scotia do?
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\)

Introduce extra terms to deal with cross-terms

error vector E for error, also slack vector
scalar u also necessary for cross-terms, and Z expression
R1CS trivially subset
Instance is now this tuple, not just x as public input, sat by witness W
Prover don't want to send \((W_1, W_2)\) => use a commitment
(Non-trivial (communication cost) and ZK)

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

Introduction to Folding