<style> h5 { font-size: 10px; } </style> ## Introduction to Folding PSE Summer Program (Sep, 2023)  --- # 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  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  ##### (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  ##### (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  ##### (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  ##### (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  ##### (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  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  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?  Note: QR code to talk