math/slides_sonobe-sf-2024-08-08.tex
slides_sonobe-sf-2024-08-08.texRaw
1\documentclass[t]{beamer}
2\usefonttheme[onlymath]{serif}
3
4\mode<presentation>
5{
6 \usetheme{Frankfurt}
7 \usecolortheme{dove} %% grey scale
8 \useinnertheme{circles}
9 % \setbeamercovered{transparent}
10}
11
12\hypersetup{
13 colorlinks,
14 citecolor=black,
15 filecolor=black,
16 linkcolor=black,
17 urlcolor=blue
18}
19\usepackage{graphicx}
20
21\graphicspath{ {../folding/sonobe-docs/src/imgs} }
22
23\usepackage{listings} % embed code
24
25\setbeamertemplate{itemize}{$\circ$}
26\setbeamertemplate{itemize items}{$\circ$}
27
28\beamertemplatenavigationsymbolsempty %% no navigation bar
29
30\setbeamertemplate{footline}{\hspace*{.1cm}\scriptsize{
31\hspace*{50pt} \hfill\insertframenumber/\inserttotalframenumber\hspace*{.1cm}\vspace*{.1cm}}}
32
33\setbeamertemplate{caption}[numbered]
34\setbeamerfont{caption}{size=\tiny}
35
36
37\title{An overview on folding schemes,\\and an introduction to Sonobe}
38\author{
39 % Folding polynomials and proving it onchain.\\
40 % \small{Sonobe: experimental folding schemes library implemented jointly by \href{https://0xparc.org}{0xPARC} and \href{https://pse.dev/}{PSE.}}\\
41 \vspace{0.2cm}
42 \includegraphics[width=3cm]{sonobe}
43}
44
45\date{\vspace{0.1cm}\scriptsize{2024-08-08\\San Francisco 0xPARC Summer}}
46
47\begin{document}
48
49\frame{\titlepage}
50
51
52
53\section[Motivation]{Motivation}
54
55\begin{frame}{Polynomials and SNARKs}
56 \begin{itemize}
57 \item define the 'program' that we want to be able to prove as a set of constraints
58 \item encode the constraints as polynomials
59 \\eg. R1CS: $Az \circ Bz - Cz == 0$
60 \\~~~~~~~~~~$A(X) \cdot B(X) - C(X) == 0$
61 \item and then use some scheme to prove that those polynomials satisfy the relation. eg. Groth16, Spartan, etc
62 \end{itemize}
63 tl;dr: want to prove polynomial relations
64\end{frame}
65
66\begin{frame}{Why folding}
67 \begin{itemize}
68 \item Repetitive computations take big circuits $\longrightarrow$ large proving time
69 \begin{itemize}
70 \item and in some cases takes too much memory and can not be even computed
71 \item eg. prove a chain of 10k sha256 hashes (>600M R1CS constraints, not feasible with most traditional SNARK proving systems)
72 \end{itemize}
73
74 % \pause
75
76 \item Traditional recursion: verify (in-circuit) a proof of the correct execution of the same circuit for the previous input
77 \begin{itemize}
78 \item issue: in-circuit proof verification is expensive (constraints)
79 \begin{itemize}
80 \item ie. verify a Groth16 proof inside a R1CS circuit
81 \end{itemize}
82 \end{itemize}
83 \end{itemize}
84
85 % DRAW: G16 proof being verified inside a circuit for which a new proof is generated
86\end{frame}
87
88\begin{frame}{IVC - Incremental Verifiable Computation}
89 {\tiny Valiant'08}\\
90 Folding schemes efficitently achieve IVC, where the prover recursively proves the correct execution of the incremental computations.
91 \vspace{0.5cm}
92
93 % For a function $F$, with initial input $z_0$, an IVC scheme allows a prover to produce a proof $\pi_i$ for the statement $z_i=F^{(i)}(z_0)$, given a proof $\pi_{i-1}$ for the statementkj
94 \emph{Prove that applying $n$ times the $F$ function (the circuit being folded) to the initial state ($z_0$) results in the final state ($z_n$).}
95
96
97 \includegraphics[width=\textwidth]{folding-main-idea-diagram}
98
99 In other words, it allows to prove efficiently that $z_n = F(...~F(F(F(F(z_0, w_0), w_1), w_2), ...), w_{n-1})$.
100\end{frame}
101
102
103\begin{frame}{Folding idea}
104 % DRAW of 2 instances being folded into a single one
105 % then add other instances to show k-to-1 folding
106\end{frame}
107
108
109% \section[Folding]{Folding}
110% \begin{frame}{Fold polynomials - a simple example}
111% TODO example folding poly
112% \end{frame}
113
114\begin{frame}{Random linear combination of homomorphic commitments}
115 \small{
116 We rely on homomorphic commitments, eg. Pedersen commitments\\
117 }
118
119 Let $g \in \mathbb{G}^n,~ v \in \mathbb{F}_r^n$,\\
120 $$Com(v) = \langle g, v \rangle =g_1 \cdot v_1 + g_2 \cdot v_2 + \ldots + g_n \cdot v_n \in \mathbb{G}$$
121
122 RLC:\\
123 Let $v, w \in \mathbb{F}_r^n$,
124 \\set $cm_v = Com(v),~ cm_w=Com(w) \in \mathbb{G}$.
125 \\then,
126 \begin{align*}
127 y &= v + r \cdot w\\
128 cm_{y} &=cm_v + r \cdot cm_w
129 \end{align*}
130 \\so that
131 $$cm_y = Com(y)$$
132
133\end{frame}
134
135\begin{frame}{Relaxed R1CS}
136 % TODO: think if maybe remove this slide and the next one (NIFS)\\
137
138 R1CS instance: $(\{A, B, C\} \in \mathbb{F}^{n \times n},~ n,~ l)$, such that for $z=(1, io \in \mathbb{F}^l, w \in \mathbb{F}^{n-l-1}) \in \mathbb{F}^n$,
139
140$$Az \circ Bz = Cz$$
141
142% \pause
143
144Relaxed R1CS:
145
146$$Az \circ Bz = uCz + E$$
147
148for $u \in \mathbb{F},~~ E \in \mathbb{F}^n$.
149
150\vspace{1cm}
151
152Committed Relaxed R1CS instance: $CI = (\overline{E}, u, \overline{W}, x)$\\
153Witness of the instance: $WI=(E, W)$
154
155\end{frame}
156
157\begin{frame}{Relaxed R1CS}
158 % \vspace{-1cm}
159 \scriptsize{
160 $u=u_1+r u_2,~~ z=z_1+r z_2,~~ x=x_1+r x_2$\\
161 $E=E_1 + r (A z_1 \circ B z_2 + A z_2 \circ B z_1 - u_1 C z_2 - u_2 C z_1) + r^2 E_2$\\
162 \text{Relaxed R1CS:} $Az \circ Bz = uCz + E,~~ with~ z=(u,~x,~W)$
163\begin{align*}
164 Az \circ Bz
165 &= A(z_1 + r \cdot z_2) \circ B(z_1 + r \cdot z_2)\\
166 &= A z_1 \circ B z_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 (A z_2 \circ B z_2)\\
167 &= (u_1 C z_1 + E_1) + r (A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 (u_2 C z_2 + E_2)\\
168 &= u_1 C z_1 + \underbrace{E_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 E_2}_\text{E} + r^2 u_2 C z_2\\
169 &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
170 &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
171 &= uCz + E
172\end{align*}
173
174For R1CS matrices $(A,~B,~C)$, the folded witness $W$ is a satisfying witness for the folded instance $(E,~u,~x)$, following the Relaxed R1CS relation: $Az \circ Bz - uCz - E ==0$.
175
176Since we don't want that the Verifier learning about the witness, we commit to it, and the Verifier will run the RLC on the commitment (not on the witness), obtaining the 'folded' commitment.
177
178\\\tiny{Full details at Nova's paper, pages 13-15 ("first attempt, second attempt, third attempt")}
179}
180\end{frame}
181% \begin{frame}{NIFS - Non Interactive Folding Scheme (in Nova)}
182% \vspace{-0.5cm}
183% \scriptsize{
184% \begin{align*}
185% CI_1 &=(\overline{E}_1 \in \mathbb{G}, u_1 \in \mathbb{F}, \overline{W}_1 \in \mathbb{G}, x_1 \in \mathbb{F}^n) ~~~~~~WI_1=(E_1 \in \mathbb{F}^n, W_1 \in \mathbb{F}^n)\\
186% CI_2 &=(\overline{E}_2, u_2, \overline{W}_2, x_2) ~~~~~~WI_2=(E_2, W_2)
187% \end{align*}
188% where $\overline{V}=Com(V)$
189%
190%
191%
192% \begin{align*}
193% T &= Az_1 \circ Bz_1 + Az_2 \circ Bz_2 - u_1 C z_1 - u_2 C z_2\\
194% \overline{T}&=Com(T)
195% \end{align*}
196%
197% \begin{minipage}[t]{.45\textwidth}
198% NIFS.P
199% \begin{align*}
200% E &= E_1 + r \cdot T + r^2 \cdot E_2\\
201% W &= W_1 + r \cdot W
202% \end{align*}
203% \end{minipage}
204% \hfill\vline\hfill
205% \begin{minipage}[t]{.45\textwidth}
206% NIFS.V
207% \begin{align*}
208% \overline{E} &= \overline{E}_1 + r \cdot \overline{T} + r^2 \cdot \overline{E}_2\\
209% u &= u_1 + r \cdot u_2\\
210% \overline{W} &= \overline{W}_1 + r \cdot \overline{W}\\
211% x &= x_1 + r \cdot x_2
212% \end{align*}
213% \end{minipage}
214%
215% New folded Committed Instance: $(\overline{E}, u, \overline{W}, x)$\\
216% New folded witness: $(E, W)$
217% }
218% \vspace{0.3cm}\\
219% \tiny{Nova's paper, pages 13-15 ("first attempt, second attempt, third attempt")}
220% \end{frame}
221
222\begin{frame}{NIFS - Non Interactive Folding Scheme (in Nova)}
223 \scriptsize{
224 Main idea:
225 \begin{itemize}
226 \item interactive protocol between P and V
227 \item where V obtains the 'folded' commitment that corresponds to the 'folded' witness that P computes
228 \item so V does not know the witness
229 \end{itemize}
230 We make it non-interactive with Fiat-Shamir.
231 }
232
233 \includegraphics[width=\textwidth]{./imgs/interactive-FS-nova-diagram}
234
235 Relation check:
236 \begin{align*}
237 &z=(1,x,W)\\
238 &\begin{cases}
239 Az \circ Bz - uCz - E \stackrel{?}{=} 0\\
240 \overline{W} \stackrel{?}{=} Com(W)\\
241 \overline{E} \stackrel{?}{=} Com(E)
242 \end{cases}
243 \end{align*}
244\end{frame}
245
246\begin{frame}{HyperNova NIMFS}
247 \includegraphics[width=8cm]{./imgs/hypernova-screenshot}
248\end{frame}
249
250\begin{frame}{ProtoGalaxy Folding}
251 \includegraphics[width=8cm]{./imgs/protogalaxy-screenshot}
252\end{frame}
253
254\section[IVC]{IVC}
255
256\begin{frame}{IVC}
257 \includegraphics[width=\textwidth]{folding-main-idea-diagram}
258 \begin{itemize}
259 \item We have our folding protocol, in which P \& V 'fold' the instances (witness \& commitments)
260 \item Will use it in the IVC setting
261 \item at each IVC step, need to ensure that the 'folding' of the previous step was done correctly
262 \item we 'augment' the circuit with extra checks that compute the folding Verifier
263 \end{itemize}
264\end{frame}
265
266\begin{frame}{IVC - Nova example}
267 \small{
268 $U_i$ (\emph{running instance}): committed instance for the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
269 $u_i$ (\emph{incoming instance}): committed instance for the correct execution of invocation $i$ of $F'$
270 }
271
272 % draw: sketch of the Augmented F Circuit
273 % big box for F', inside small box for F. NIFS.V box, how things connect to next iteration
274
275 \vspace{4cm}
276
277 \small{
278 F':\\
279 i) execute a step of the incremental computation, $z_{i+1} = F(z_i)$\\
280 ii) invoke the NIFS.V to fold $U_i, u_i$ into $U_{i+1}$\\
281 iii) other checks to ensure that the IVC is done properly
282 }
283\end{frame}
284
285\begin{frame}{Cycle of curves}
286 \small{
287 NIFS.V involves $\mathbb{G}$ point operation, which are not native over $\mathbb{F}_r$ of $\mathbb{G}$.
288 \\$\longrightarrow$ delegate them into a circuit over a 2nd curve
289 We use:
290 \begin{itemize}
291 \item $\mathbb{G}_1.\mathbb{F}_r = \mathbb{G}_2.\mathbb{F}_q$
292 \item $\mathbb{G}_1.\mathbb{F}_q = \mathbb{G}_2.\mathbb{F}_r$
293 \item eg. for Ethereum compatibility:\\
294 $\mathbb{G}_1$: BN254, $\mathbb{G}_2$: Grumpkin.
295 \end{itemize}
296
297 \vspace{0.3cm}
298
299 We 'mirror' the main $F'$ circuit into the 2nd curve\\
300 each circuit computes natively the point operations of the other curve
301 }
302
303 % DRAW:
304 % 1st the Nova with duplicated F' circuits over 2 curves
305 % 2nd the Nova with CycleFold circuits sketch
306\end{frame}
307
308
309\begin{frame}{Augmented F Circuit + CycleFold Circuit}
310 \includegraphics[width=\textwidth]{cyclefold-nova-diagram}
311 % mention TODO folding overhead - num constraints of overhead, so for small circuits it is not worth
312 explain: circuit overhead
313\end{frame}
314
315\begin{frame}{Adding zk to the IVC}
316 \begin{itemize}
317 \item fold the original witness with a randomized instance
318 \item then we can delegate the rest of the computation to a third party server
319 \end{itemize}
320\end{frame}
321
322\section{Decider (Final compressed proof)}
323
324\begin{frame}{Decider (Final compressed proof)}
325 \includegraphics[width=\textwidth]{cyclefold-paper-diagram}
326
327 With Prover knowing the respective witnesses for $U_n, u_n, U_{EC,n}$
328
329 \vspace{1cm}
330
331 Issue: IVC proof is not succinct
332\end{frame}
333
334\begin{frame}{Decider}
335 Original Nova: generate a zkSNARK proof with Spartan for $U_n, u_n, U_{EC, n}$\\
336 $\longrightarrow$ 2 Spartan proofs, one on each curve\\
337 (not EVM-friendly)
338
339 % DRAW of the 2 circuits over the curves, and how we generate a Spartan proof for each one
340
341\end{frame}
342
343\begin{frame}{Decider}
344 checks (simplified)
345 \begin{enumerate}
346 \item $(U_{n+1}, W_{n+1})$ satisfy Relaxed R1CS relation of AugmentedFCircuit
347 \item verify commitments of $U_{n+1}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{n+1}.\{E,W\}$
348 \item $(U_{EC,n}, W_{EC,n})$ satisfy Relaxed R1CS relation of CycleFoldCircuit
349 \item verify commitments of $U_{EC,n}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{EC,n}.\{E,W\}$
350 \item $u_n.E==0,~ u_n.u==1$, ie. $u_n$ is a fresh not-relaxed instance
351 \item $u_n.x_0==H(n, z_0, z_n, U_n)$\\
352 $u_n.x_1==H(U_{EC,n})$
353 \item $NIFS.V(U_n, u_n)==U_{n+1}$
354 \end{enumerate}
355
356 % DRAW; by draw show which are native and not native
357 % and that the NIFS.V we do it in Solidity
358\end{frame}
359
360\begin{frame}{Decider}
361 \includegraphics[width=\textwidth]{decider-onchain-flow-diagram}
362 % DRAW of the full flow: from inputting the circuit, to folding to generating the Decider proof to verifying in Ethereum
363\end{frame}
364
365\section{Sonobe}
366\begin{frame}{Sonobe}
367
368 \footnotesize{
369 Experimental folding schemes library implemented jointly by 0xPARC and PSE.\\
370 \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
371 \\Modular library,
372 \begin{itemize}
373 \item Be able to
374 \begin{itemize}
375 \item Add and test new folding schemes
376 \item Compare schemes 'apples-to-apples'
377 \item Researchers can easily add their own schemes (eg. Mova paper)
378 \end{itemize}
379 \item Make it easy for devs to use folding
380 \begin{itemize}
381 \item minimal code to fold your circuits ('plug-and-fold')
382 \item easy to switch between folding schemes and curves
383 \item support of multiple zk-circuit languages
384 \end{itemize}
385 \end{itemize}
386 }
387\end{frame}
388
389\begin{frame}{Sonobe - Dev experience}
390 \footnotesize{
391
392 Dev flow:
393 \begin{enumerate}
394 \item Define a circuit to be folded
395 \item Set which folding scheme to be used (eg. Nova with CycleFold)
396 \item Set a final decider to generate the final proof (eg. Groth16 over BN254 curve)
397 \item Generate the the decider verifier (EVM Solidity contract)
398 \end{enumerate}
399 }
400
401 \vspace{1cm}
402
403 \includegraphics[width=\textwidth]{sonobe-lib-pipeline}
404\end{frame}
405
406
407\begin{frame}{Status of Sonobe - dev experience}
408 \begin{itemize}
409 \item Verify in Ethereum
410 \begin{itemize}
411 \item solidity verifier contract generator
412 \end{itemize}
413 \item Frontends - how can the dev define a circuit to be folded
414 \begin{itemize}
415 \item Arkworks \href{https://github.com/arkworks-rs/}{https://github.com/arkworks-rs/}
416 \item Circom \href{https://github.com/iden3/circom}{https://github.com/iden3/circom}
417 \item Noir \href{https://noir-lang.org/}{https://noir-lang.org/}
418 \item Noname \href{https://github.com/zksecurity/noname}{https://github.com/zksecurity/noname}
419 \end{itemize}
420 \end{itemize}
421\end{frame}
422
423\begin{frame}{Status of Sonobe - schemes implemented}
424 \scriptsize{
425
426 Implemented:
427 \begin{itemize}
428 \item \textbf{Nova}: Recursive Zero-Knowledge Arguments from Folding Schemes\\ \href{https://eprint.iacr.org/2021/370.pdf}{https://eprint.iacr.org/2021/370.pdf}, Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla. 2021
429 \item \textbf{CycleFold}: Folding-scheme-based recursive arguments over a cycle of elliptic curves\\ \href{https://eprint.iacr.org/2023/1192.pdf}{https://eprint.iacr.org/2023/1192.pdf}, Abhiram Kothapalli, Srinath Setty. 2023
430 \item \textbf{HyperNova}: Recursive arguments for customizable constraint systems\\ \href{https://eprint.iacr.org/2023/573.pdf}{https://eprint.iacr.org/2023/573.pdf}, Abhiram Kothapalli, Srinath Setty. 2023
431 \end{itemize}
432 Almost finished:
433 \begin{itemize}
434 \item \textbf{ProtoGalaxy}: Efficient ProtoStar-style folding of multiple instances\\ \href{https://eprint.iacr.org/2023/1106.pdf}{https://eprint.iacr.org/2023/1106.pdf}, Liam Eagen, Ariel Gabizon. 2023
435 \end{itemize}
436 Soon:
437 \begin{itemize}
438 \item \textbf{Mova}: Nova folding without committing to error terms\\ \href{https://eprint.iacr.org/2024/1220.pdf}{https://eprint.iacr.org/2024/1220.pdf}, Nikolaos Dimitriou, Albert Garreta, Ignacio Manzur, Ilia Vlasov. 2024
439 \end{itemize}
440 Temptative:
441 \begin{itemize}
442 \item \textbf{LatticeFold}: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems\\ \href{https://eprint.iacr.org/2024/257.pdf}{https://eprint.iacr.org/2024/257.pdf}, Dan Boneh, Binyi Chen. 2024
443 \item Parallel folding
444 \end{itemize}
445
446 }
447\end{frame}
448
449\begin{frame}{Code example}
450 [show code with a live demo]
451\end{frame}
452
453\begin{frame}{Code example}
454 \footnotesize{
455 Some numbers (still optimizations pending):
456 \begin{itemize}
457 \item AugmentedFCircuit (Nova): $\sim 50k$ R1CS constraints
458 \item DeciderEthCircuit: $\sim 10M$ R1CS constraints
459 \begin{itemize}
460 \item $<3$ minutes in a 32GB RAM 16 core laptop
461 \end{itemize}
462 \item gas costs (DeciderEthCircuit proof): $\sim 800k$ gas
463 \begin{itemize}
464 \item mostly from G16, KZG10, public inputs processing
465 \item will be reduced by hashing the public inputs
466 \item expect to get it down to $< 500k$ gas.
467 \end{itemize}
468 \end{itemize}
469 }
470
471 \vspace{0.6cm}
472
473 Recall, this proof is proving that applying $n$ times the function $F$ (the circuit that we're folding) to an initial state $z_0$ results in the state $z_n$.
474
475 \vspace{0.4cm}
476
477 In Srinath Setty words, you can prove practically unbounded computation onchain by 800k gas (and soon $< 500k$).
478\end{frame}
479
480\begin{frame}{Wrappup}
481\begin{itemize}
482 \item \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
483 \item \href{https://privacy-scaling-explorations.github.io/sonobe-docs/}{https://privacy-scaling-explorations.github.io/sonobe-docs/}
484\end{itemize}
485
486 \begin{center}
487 \includegraphics[width=5cm]{./imgs/sonobe-link-qrcode}
488 \end{center}
489
490\tiny{
491 $$\text{2024-08-08}$$
492 $$\text{\href{https://0xparc.org}{0xPARC}~\&~\href{https://pse.dev/}{PSE.}}$$
493}
494\end{frame}
495
496\end{document}