<style>
h5 {
font-size: 10px;
}
</style>
## Introduction to Folding
PSE Summer Program (Sep, 2023)
![](https://hackmd.io/_uploads/SyIwrKS03.png)
---
# 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
Note:
with commonly repeated patterns
---
## About me
- [@oskarth](https://twitter.com/oskarth), independent researcher, Taiwan 5y
- Founded [Vac.dev](https://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
Note:
Other approaches: Problems they solve
---
## 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?
Note:
Some questions you should be able to answer after this talk
https://hackmd.io/wtTwtyoMSg2sCwVqp1m88Q
---
## 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, ...
Note:
VM: Both opcodes (Supernova) and aggregate (compress) transactions; Rollup and other VMs.
ML: Layers in neural network, e.g.
VDFs: take long time to execute but quick to verify (randomness in consensus)
Innovative DSLs like Lurk, a Lisp for ZK - recursion step in computation
---
## ETHDOS
![](https://hackmd.io/_uploads/BkNQsYSA3.png)
Note:
Composability: Hide social graph
Prove X degrees, w/o knowing particulars
---
# 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
Note:
Other notions like "split accumulation" around same time
By Srinath Setty at MS Research, also others
Type of IVC; no SNARK for it, instead 'folding scheme'
Efficient: recursion overhead at each step constant 2 MSM
No FFTs, so more flexibility with choice of EC
Proof linear to F, but we add final SNARK at the end
---
## 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)
Note:
Can't update means have to re-do if another step
Verification time depends on n
---
## Incrementally Verifiable Computation (IVC)
- IVC solves this
- Proceed in incremental steps, prove each step
- Verifier only looks at final proof
---
## Prior approaches
![](https://hackmd.io/_uploads/SJ_hwcHC2.png)
##### (Source: Srinath Setty's [presentation](https://www.youtube.com/watch?v=mY-LWXKsBLc))
Note:
We see e.g. Halo has a SNARK at each step; recent work on split accumulation too
Won't go into details; important part is we don't produce/verify SNARK at each step
Instead, we only have commitments and RLC, which is a lot more efficient
In Nova we defer checking entire R1CS instance => folding scheme
Let's look at this in more detail
---
## 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$
Note:
Folding schemes work for NP-complete languages, Nova focuses on R1CS
Assume people are familiar with R1CS basics, \circ is entry-wise mul
W and x private and public input
RLC allows us to commit to set of values w/o revealing, later can reveal and prove
Verifier chooses random field element r
---
## 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)$
Note:
R1CS expansion
Skipping details here but more to build intuition
So what do we do about these cross-terms? We encapsulate them, of course!
---
## 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$
Note:
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
Note:
Commit to W an E using Pedersen
Assume familiar with commitments, hiding, binding, succinct, add. homomorphic
Witness r from commitment
$\overline{E}$ and $\overline{W}$ are commitments
---
## Folding scheme
![](https://hackmd.io/_uploads/BJfzgoSRh.png)
##### (Source: Srinath Setty's [presentation](https://www.youtube.com/watch?v=ilrvqajkrYY))
Note:
Diff view, want to fold two R1CS instances, introduce E and u
Interactive: Commit to it, get challenge r back
End result: folded two things together
Cost: Commitments and 2 MSM (r \cdot...) (third one disappears)
---
## Folding flow
![](https://hackmd.io/_uploads/S1T9X2HRn.png)
##### (Source: Srinath Setty's [presentation](https://www.youtube.com/watch?v=mY-LWXKsBLc))
Note:
Source: Srinath presentation
Folding steps same size, supply witness at each point
Public output becomes new public input
Keep running relaxed R1CS instance and fold/accumulate each step
---
## 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
Note:
Size of IVC is linear to computation, so we do a final SNARK at end
Also IVC not ZK
Spartan no trusted setup, verifying is sublinear, fast prover, short proofs, short verification
Similar to e.g. Polygon Hermez, combines STARK(FRI)+SNARK
---
# 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
Note:
Recursion overhead is additional constraints apart from F
Recursion overhead x10-x100 SNARK-based; (x7 lower than Halo)
HyperNova is just 1 MSM
Outer proof compare apples-to-apples,
E.g. comparable with STARK also big proofs in practice
Also new folding schemes even faster, parallelism
---
## 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]([/0gVClQ9IQiSXHYAK0Up9hg](https://hackmd.io/u3qM9s_YR1emHZSg3jteQA?both=))
Note:
Celer Network did SHA256 benchmarks to compare proof systems
Diff preimage: 64B...64KB
SHA256 not a SNARK friendly hash function
These are benchmarks we took a few months ago for Nova to compare
Nova also memory-efficient, no SRS (powers of tau) needed like Groth16/Halo2(KZG)
As fast as Starky and x100 Halo2/Plonky2
Memory efficient useful for client-side proving
W/o final SNARK, so depends on how big circuit is etc, what is apples to apples
HN even faster, and there's also a lot of room for parallelism etc
---
## Using Nova with Nova Scotia
- [Nova](https://github.com/microsoft/Nova) circuits in Bellman
- Circom has a lot of dev tooling
- [Nova Circuit](https://github.com/nalinbhardwaj/Nova-Scotia): Compile Circom circuits to Nova
![](https://hackmd.io/_uploads/HkkOh2HRh.png)
##### (Source: Nova Scotia [repo](https://github.com/nalinbhardwaj/Nova-Scotia))
Note:
Written by Nalin while at 0xPARC, picture from Nova Scotia repo
Bellman in Rust, many of you familiar with Circom
Just R1CS, so this translates well
---
## 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 } */
```
Note:
This is from Nova Scotia README
Tiny bit of Rust useful but all application logic in Circom
Verifying Bitcoin SHA256 example in README too
---
## Zator: Neural network with Nova
![](https://hackmd.io/_uploads/ryCt2tHC2.png)
##### (Source: Zator [repo](https://github.com/lyronctk/zator))
Note:
Written using Nova Scotia
ZK-ML, 512-layer neural network, 2.5B constraints!
Used to classify digits (MNIST)
...can we put Stable Diffusion in ZK?
---
# 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
Note:
(Origami is a folding scheme for Halo2 lookups)
(Sangria for higher-degree gates)
Many of these more PoC stage, not really usable for real yet
---
## ParaNova: Parallelize steps
![](https://hackmd.io/_uploads/S1RdZTr02.png)
Note:
Big idea is to parallelize steps, prove each intermediate step
Treat as binary tree, e.g. over multiple cores or machines
Distributed prover, make e.g. zkVM very fast
A bunch of us worked on PoC for this in Vietnam earlier this year, quite buggy though
Related idea: not 2-1 folding but n-1 folding
---
## SuperNova: Different functions
![](https://hackmd.io/_uploads/BkuKMTrC3.png)
Note:
Big idea is to allow for non-uniform IVC
Imagine VM, different opcodes, don't want to pay cost of all opcodes every F
Instead split up and have a "selector", only pay cost of function executing
---
## HyperNova: Customizable Constraint System
- Generalize R1CS with CCS
- Enable R1CS, Plonkish, AIR
- Plonkish (custom degree gates + lookups)
- Multifolding, 1 MSM
Note:
Nova problem only R1CS, Plonkish (custom degree gates + lookups) often better
Generalizes R1CS into CCS, allow for Plonkish circuit, and AIR
Different method, uses sumcheck and step dominated by 1 MSM
(Multifolding different NP relations)
WIP impl in upstream repo and also in new imp under PSE
CCS still a bit buggy for Plonkish, get rid of cross-terms tho (due to sumcheck)
---
## Other stuff
- Folding schemes: ProtoStar, ProtoGalaxy
- Better lookups: Lasso, Jolt
- All this is very experimental
Note:
ProtoStar poss more efficient, different approach
ProtoGalaxy like SuperNova but for ProtoStar
Lookup functions new research by Srinath, e.g. Lasso, very efficient
Lookup centric, x20 better than Plonkish
Complement well
Sangria (Nova workaround) and Origami (Halo2) less relevant now I believe
Very new: need implementations and benchmarks
---
## Where to go from here?
- Code: [microsoft/Nova](https://github.com/microsoft/Nova), [Nova-Scotia](https://github.com/nalinbhardwaj/Nova-Scotia), [pse/folding-schemes](https://github.com/privacy-scaling-explorations/folding-schemes/)
- Papers: [Nova](https://eprint.iacr.org/2021/370.pdf), [SuperNova](https://eprint.iacr.org/2022/1758.pdf), [HyperNova](https://eprint.iacr.org/2023/573.pdf)
- Misc: [Nova-based ZK-VM](https://zkresear.ch/t/towards-a-nova-based-zk-vm/105), [Nova benchmarks](https://hackmd.io/u3qM9s_YR1emHZSg3jteQA?view), [awesome-folding](https://github.com/lurk-lab/awesome-folding/), [this presentation](https://hackmd.io/S13_6zqxTi2BKAtW1UxJOw?view=)
- Talks: [Nova (Srinath)](https://www.youtube.com/watch?v=mY-LWXKsBLc), [SuperNova (Srinath)](https://drive.google.com/file/d/1pIPoRUcMvhsoSWLami5T1KHc5oqkUAZH/view)
Note:
Some links that might be useful
Srinath has given a few talks too and ZK podcast
Carlos from PSE has given talks on Nova-related stuff, and Nalin as well probably on YT
See awesome-folding from Lurk Labs for more
---
## Thanks! Questions?
![](https://hackmd.io/_uploads/SyRrFpBA2.png =400x400)
Note:
QR code to talk

{"description":"![[Pasted image 20230905181258.png]]","title":"Introduction to Folding","contributors":"[{\"id\":\"87bf749a-9a51-43dd-8c18-1ff87c4baaab\",\"add\":17982,\"del\":4125}]"}