math/slides/slides_sonobe-zkSummit12-2024-10-08.tex
slides/slides_sonobe-zkSummit12-2024-10-08.texRaw
1\documentclass[t]{beamer} \usefonttheme[onlymath]{serif}
2\mode<presentation>
3{
4 \usetheme{Frankfurt}
5 \usecolortheme{dove} %% grey scale
6 \useinnertheme{circles}
7 \setbeamercovered{invisible}
8}
9
10\hypersetup{
11 colorlinks,
12 citecolor=black,
13 filecolor=black,
14 linkcolor=black,
15 urlcolor=blue
16}
17\usepackage{graphicx}
18
19\graphicspath{ {./imgs-zksummit12} }
20
21% \usepackage{listings} % embed code
22% \usepackage{minted} % embed code
23\usepackage{color}
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
38\title{Sonobe, a modular folding schemes library}
39\date{
40 \includegraphics[width=3cm]{sonobe}\\
41 \vspace{0.1cm}
42 \scriptsize{2024-10-08\\0xPARC \& PSE}
43}
44
45\begin{document}
46
47\frame{\titlepage}
48
49\section{Motivation}
50
51\begin{frame}{Polynomials and SNARKs}
52 \begin{itemize}
53 \item define the 'program' that we want to be able to prove as a set of constraints
54 \item encode the constraints as polynomials
55 \\eg. R1CS: $Az \circ Bz - Cz == 0$
56 \\~~~~~~~~~~$A(X) \cdot B(X) - C(X) == 0$
57 \item and then use some scheme to prove that those polynomials satisfy the relation. eg. Groth16, Spartan, etc
58 \end{itemize}
59 \vspace{0.5cm}
60 TL;DR: want to prove polynomial relations
61\end{frame}
62
63\begin{frame}{Why folding}
64 \begin{itemize}
65 \item Repetitive computations take big circuits $\longrightarrow$ large proving time
66 \begin{itemize}
67 \item in some cases takes too much memory and can not be even computed
68 \item eg. prove a chain of 10k sha256 hashes (>600M R1CS constraints, not feasible with most traditional SNARK proving systems)
69 \item eg. zkVM opcodes
70 \end{itemize}
71
72 \pause
73 \item Traditional recursion: verify (in-circuit) a proof of the correct execution of the same circuit for the previous input
74 \begin{itemize}
75 \item issue: in-circuit proof verification is expensive (constraints)
76 \begin{itemize}
77 \item ie. verify a Groth16 proof inside a R1CS circuit
78 \end{itemize}
79 \end{itemize}
80 \end{itemize}
81
82 \includegraphics[width=\textwidth]{brute-force-recursion}
83
84\end{frame}
85
86\begin{frame}{IVC - Incremental Verifiable Computation}
87 {\tiny Valiant'08}
88 % Folding schemes efficiently achieve IVC, where the prover recursively proves the correct execution of the incremental computations.
89 %\vspace{0.5cm}
90
91 \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$).}
92
93 \includegraphics[width=\textwidth]{folding-main-idea-diagram}
94
95 In other words, it allows to prove efficiently that
96 $$z_n = F(...~F(F(F(F(z_0, w_0), w_1), w_2), ...), w_{n-1})$$
97\end{frame}
98
99
100\begin{frame}{Folding scheme pipeline}
101 \includegraphics[width=\textwidth]{folding-scheme-pipeline}
102
103 \vspace{0.5cm}
104 {\scriptsize
105 The IVC folds the AugmentedFCircuit, which ensures that the NIFS.Verify checks out.
106 }
107\end{frame}
108
109
110\section{Recap on folding}
111
112% TODO MAYBE REMOVE SLIDE
113\begin{frame}{RLC of homomorphic commitments}
114 \small{
115 In the initial folding schemes, we rely on homomorphic commitments, eg. Pedersen commitments\\
116 }
117
118 Let $g \in \mathbb{G}^n,~ v \in \mathbb{F}_r^n$,\\
119 $$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}$$
120
121 RLC:\\
122 Let $v, w \in \mathbb{F}_r^n$,
123 \\set $cm_v = Com(v),~ cm_w=Com(w) \in \mathbb{G}$.
124 \\then,
125 \begin{align*}
126 y &= v + r \cdot w\\
127 cm_{y} &=cm_v + r \cdot cm_w
128 \end{align*}
129 \\so that
130 $$cm_y = Com(y)$$
131\end{frame}
132
133% TODO MAYBE REMOVE SLIDE
134%%%%%%%%%%%%%%%%% TODO maybe get rid of the slide if not enough time
135%%%%
136\begin{frame}{Random linearly combining 2 R1CS instances}
137 \scriptsize{
138
139 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$,
140
141 $$Az \circ Bz = Cz$$
142
143
144 If we try to do a RLC with two instances ($z = z_1 + r \dot z_2$):
145 \begin{align*}
146 Az \circ Bz &= A(z_1 + r z_2) \circ B(z_1 + r z_2)\\
147 &= (Az_1 \circ Bz_1) + r \cdot (A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 \cdot (A z_2 \circ B z_2)\\
148 &\neq C z = C(z_1 + r z_2) = C z_1 + r C z_2 = (A z_1 \circ B z_1) + r \cdot (A z_2 \circ B z_2)
149 \end{align*}
150 we end up with some inequality.
151
152
153 \pause
154
155 Nova's solution, Relaxed R1CS:
156
157 $$Az \circ Bz = uCz + E$$
158
159 for $u \in \mathbb{F},~~ E \in \mathbb{F}^n$.
160
161 \vspace{0.5cm}
162
163 Witness of the instance: $WI=(E, W)$\\
164 Committed Relaxed R1CS instance: $CI = (\overline{E}, u, \overline{W}, x)$
165 }
166
167 \vspace{0.3cm}
168 \tiny{Full details at Nova's paper, pages 13-15 ("first attempt, second attempt, third attempt")}
169
170\end{frame}
171
172% TODO MAYBE REMOVE SLIDE
173% \begin{frame}{Relaxed R1CS}
174% % \vspace{-1cm}
175% \scriptsize{
176% $u=u_1+r u_2,~~ z=z_1+r z_2,~~ x=x_1+r x_2$\\
177% $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$\\
178% \text{Relaxed R1CS:} $Az \circ Bz = uCz + E,~~ with~ z=(u,~x,~W)$
179% \begin{align*}
180% Az \circ Bz
181% &= A(z_1 + r \cdot z_2) \circ B(z_1 + r \cdot z_2)\\
182% &= 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)\\
183% &= (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)\\
184% &= 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\\
185% &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
186% &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
187% &= uCz + E
188% \end{align*}
189%
190% For 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$.
191%
192% Since 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.
193%
194% \\\tiny{Full details at Nova's paper, pages 13-15 ("first attempt, second attempt, third attempt")}
195% }
196% \end{frame}
197%%%%
198%%%%%%%%%%%%%%%%%
199
200\begin{frame}{NIFS: Non Interactive Folding Scheme (in Nova)}
201 {\tiny
202 Main idea:
203 \begin{itemize}
204 \item protocol between P (Prover) and V (Verifier)
205 \item where P and V obtain the 'folded' committed instance that corresponds to the 'folded' witness instance that P computes
206 \item so V does not know the witness
207 \end{itemize}
208 % We make it non-interactive with Fiat-Shamir.
209 RelaxedR1CS relation: $Az \circ Bz = uCz + E$, for $u \in \mathbb{F},~~ E \in \mathbb{F}^n$.
210 \\Witness of the instance: $WI=(E, W)$\\
211 Committed Relaxed R1CS instance: $CI = (\overline{E}, u, \overline{W}, x)$
212
213 \includegraphics[width=\textwidth]{interactive-FS-nova-diagram}
214
215 Relation check:
216 \begin{align*}
217 &z=(1,x,W)\\
218 &\begin{cases}
219 Az \circ Bz - uCz - E \stackrel{?}{=} 0\\
220 \overline{W} \stackrel{?}{=} Com(W)\\
221 \overline{E} \stackrel{?}{=} Com(E)
222 \end{cases}
223 \end{align*}
224 }
225\end{frame}
226
227\begin{frame}{NIMFS}
228 issue: the RLC with $>2$ instances makes the cross-terms grow
229 \\ie. some vectors ($T$) would get bigger and their commitments ($\overline{T}$) more expensive
230
231 \pause
232 \vspace{0.5cm}
233
234 NIMFS in HyperNova, ProtoGalaxy, etc
235 \begin{itemize}
236 \item instead of 2 RLC between 2 instances
237 \begin{itemize}
238 \item HyperNova: run SumCheck
239 \item ProtoGalaxy: protocol using Lagrange Basis (instead of random values) for the linear combinations and then the zero-check protocol
240 \\alternatively using MLE and SumCheck
241 \end{itemize}
242 \end{itemize}
243 Allowing to fold $>2$ instances at each folding step.
244\end{frame}
245
246\begin{frame}
247 \includegraphics[height=\textheight]{multifolding-idea}
248\end{frame}
249
250\begin{frame}{HyperNova NIMFS}
251 {\tiny src: \href{https://eprint.iacr.org/2023/573.pdf}{https://eprint.iacr.org/2023/573.pdf} (HyperNova paper)}
252 \vspace{-0.5cm}
253 \includegraphics[width=8cm]{./imgs/hypernova-screenshot}
254\end{frame}
255
256\begin{frame}{ProtoGalaxy Folding}
257 {\tiny src: \href{https://eprint.iacr.org/2023/1106.pdf}{https://eprint.iacr.org/2023/1106.pdf} (ProtoGalaxy paper)}
258 \includegraphics[width=8cm]{./imgs/protogalaxy-screenshot}
259\end{frame}
260
261\section{IVC}
262
263\begin{frame}{(Recall) Folding scheme pipeline}
264 \includegraphics[width=\textwidth]{folding-scheme-pipeline}
265
266 \vspace{0.5cm}
267 {\scriptsize
268 The IVC folds the AugmentedFCircuit, which ensures that the NIFS.Verify checks out.
269 }
270\end{frame}
271
272% ANNOTATION:
273% Now, we have this protocol between Prover and Verifier to 'fold', 'combine' 2 instances into a new instance, which if satisfies the relation checks, it means that the 2 original ones were satisfying it too.
274% We're going to see now how do we convert this into
275
276\begin{frame}{IVC - Incrementally Verifiable Computation}
277 \begin{itemize}
278 \item need to ensure that at each fold (IVC step), the NIFS is correctly done
279 \item want to have a construction where we fold the circuit that itself contains the checks of the Folding Scheme (NIFS.Verify)
280 \item we encode the NIFS.Verify inside a circuit (\emph{AugmentedFCircuit}), together with other checks that ensure the correct relations
281 \item and is this \emph{AugmentedFCircuit} ($F'$) the one which we actually fold
282 \end{itemize}
283
284 % TODO rm:
285 % \includegraphics[width=\textwidth]{folding-main-idea-diagram}
286 % $$z_n = F(...~F(F(F(F(z_0, w_0), w_1), w_2), ...), w_{n-1})$$
287\end{frame}
288
289\begin{frame}{Folding circuit - AugmentedFCircuit}
290 wrapper over the circuit that we want to fold
291 \begin{itemize}
292 \item contains the circuit that we want to fold
293 \item plus extra checks ensuring that the fold is being done correctly\\
294 \begin{itemize}
295 \item some hashing and values checks
296 \item run the NIFS.Verify in-circuit
297 \begin{itemize}
298 \item Nova: RLC of $\mathbb{F}$ and $\mathbb{G}$ elements
299 \item HyperNova: RLC of $\mathbb{F}$ and $\mathbb{G}$ elements + SumCheck verifier
300 \item ProtoGalaxy: linear combinations of $\mathbb{F}$ and $\mathbb{G}$ elements with the Lagrange basis and some polynomial evaluations + ... (alternatively SumCheck)
301 \end{itemize}
302 \end{itemize}
303 \end{itemize}
304
305
306\end{frame}
307
308\begin{frame}{Cycle of curves}
309 \scriptsize{
310 NIFS.V involves $\mathbb{G}$ point operation, which are not native over $\mathbb{F}_r$ of $\mathbb{G}$.
311 \\$\longrightarrow$ delegate them into a circuit over a 2nd curve
312 We use:
313 \begin{itemize}
314 \item $\mathbb{G}_1.\mathbb{F}_r = \mathbb{G}_2.\mathbb{F}_q$
315 \item $\mathbb{G}_1.\mathbb{F}_q = \mathbb{G}_2.\mathbb{F}_r$
316 \item eg. for Ethereum compatibility:\\
317 $\mathbb{G}_1$: BN254, $\mathbb{G}_2$: Grumpkin.
318 \end{itemize}
319
320 We 'mirror' the main $F'$ circuit into the 2nd curve\\
321 each circuit computes natively the point operations of the other curve's circuit
322 }
323 \vspace{0.3cm}
324
325 \includegraphics[width=\textwidth]{nova-cycle-of-curves-mirror}
326\end{frame}
327
328\begin{frame}{Cycle of curves}
329 \scriptsize{
330 NIFS.V involves $\mathbb{G}$ point operation, which are not native over $\mathbb{F}_r$ of $\mathbb{G}$.
331 \\$\longrightarrow$ delegate them into a circuit over a 2nd curve
332 We use:
333 \begin{itemize}
334 \item $\mathbb{G}_1.\mathbb{F}_r = \mathbb{G}_2.\mathbb{F}_q$
335 \item $\mathbb{G}_1.\mathbb{F}_q = \mathbb{G}_2.\mathbb{F}_r$
336 \item eg. for Ethereum compatibility:\\
337 $\mathbb{G}_1$: BN254, $\mathbb{G}_2$: Grumpkin.
338 \end{itemize}
339
340 We 'mirror' the main $F'$ circuit into the 2nd curve\\
341 each circuit computes natively the point operations of the other curve's circuit
342 }
343 \vspace{0.3cm}
344
345 \includegraphics[width=\textwidth]{nova-cycle-of-curves-cyclefold}
346\end{frame}
347
348% slide with only the image:
349{
350\usebackgroundtemplate{\includegraphics[width=\paperwidth]{cyclefold-nova-diagram}}
351\begin{frame}[plain]
352 \vskip0pt plus 1fill
353 {\tiny
354 Nova's Folding Circuit (F') + CycleFold circuit
355
356 src: \href{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}
357 }
358\end{frame}
359}
360% \begin{frame}{Augmented F Circuit + CycleFold Circuit}
361% \begin{frame}
362% \begin{tikzpicture}
363% \node at (current page.center) {\includegraphics[width=\paperwidth, height=\paperheight]{cyclefold-nova-diagram}}
364% \end{tikzpicture}
365% % \includegraphics[width=\textwidth]{cyclefold-nova-diagram}
366% % {\tiny src: \href{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}}
367% % mention TODO folding overhead - num constraints of overhead, so for small circuits it is not worth
368% % TODO explain: circuit overhead.
369% \end{frame}
370
371
372\section{Decider}
373
374\begin{frame}{(Recall) Folding scheme pipeline}
375 \includegraphics[width=\textwidth]{folding-scheme-pipeline}
376
377 \vspace{0.5cm}
378 {\scriptsize
379 The IVC folds the AugmentedFCircuit, which ensures that the NIFS.Verify checks out.
380 }
381\end{frame}
382
383
384\begin{frame}{Decider (Final compressed proof)}
385 \vspace{-0.5cm}
386 \includegraphics[width=\textwidth]{decider-instances}
387
388 {\scriptsize
389 Issue: IVC proof is not succinct.
390 \begin{itemize}
391 \item Committed Instances of the AugmentedFCircuit $U_n$, $u_n$, where each one is $\{ \overline{E} \in \mathbb{G}_1, \overline{W} \in \mathbb{G}_1, u \in \mathbb{F}_r, x \in \mathbb{F}_r^{|io|} \}$
392 \item and their respective Witnesses $W_n, w_n$, each one being $\{E \in \mathbb{F}_r^n, W \in \mathbb{F}_r^n \}$
393 \item Committed instance of the CycleFold circuit $U_{EC,n}$ contains: $\{ \overline{E} \in \mathbb{G}_2, \overline{W} \in \mathbb{G}_2, u \in \mathbb{F}_q, x \in \mathbb{F}_q^{|io|} \}$
394 \item and its Witnesses $W_{EC,n}$, being $\{E \in \mathbb{F}_r^n, W \in \mathbb{F}_r^n \}$
395 \end{itemize}
396 So the idea is to 'compress' the IVC proof into a zkSNARK proof, minimizing the size and the verifier computation.
397 }
398
399\end{frame}
400
401% TODO rm
402% \begin{frame}{Decider}
403% Original Nova: generate a zkSNARK proof with Spartan for $U_n, u_n, U_{EC, n}$\\
404% $\longrightarrow$ 2 Spartan proofs, one on each curve\\
405% (not EVM-friendly)
406%
407% \vspace{0.5cm}
408%
409% We need to do a bit of gymnastics to verify the folding proofs in Ethereum
410%
411% % TODO
412% % DRAW of the 2 circuits over the curves, and how we generate a Spartan proof for each one
413% \end{frame}
414
415\begin{frame}{Decider checks}
416 \begin{enumerate}
417 \item[1.] check $NIFS.V(r, U_n, u_n, \overline{T}) \stackrel{?}{=} U_{n+1}$
418 \item[2.] check that $u_n.\overline{E}=0$ and $u_n.u=1$
419 \item[3.] check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
420 \item[4.] correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
421 \item[5.] check commitments of $U_{n+1}.\{ \overline{E}, \overline{W} \}$ with respect $W_{n+1}$ (where $\overline{E}, \overline{W} \in E_1$)
422 \item[6.] check the correct RelaxedR1CS relation of $U_{EC,n}, W_{EC,n}$ of the CycleFoldCircuit
423 \item[7.] check commitments of $U_{EC,n}.\{ \overline{E}, \overline{W} \}$ with respect $W_{EC,n}$ (where $\overline{E},\overline{W} \in E_2$)
424 \end{enumerate}
425\end{frame}
426
427\begin{frame}{Decider checks}
428 \begin{enumerate}
429 \item[1.] check $NIFS.V(r, U_n, u_n, \overline{T}) \stackrel{?}{=} U_{n+1}$
430 \item[2.] check that $u_n.\overline{E}=0$ and $u_n.u=1$
431 \item[3.] check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
432 \item[4.] correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
433 \item[5.] check commitments of $U_{n+1}.\{ \overline{E}, \overline{W} \}$ with respect $W_{n+1}$ (where $\overline{E}, \overline{W} \in E_1$) \textcolor{cyan}{non-native!}
434 \item[6.] check the correct RelaxedR1CS relation of $U_{EC,n}, W_{EC,n}$ of the CycleFoldCircuit \textcolor{cyan}{non-native!}
435 \item[7.] check commitments of $U_{EC,n}.\{ \overline{E}, \overline{W} \}$ with respect $W_{EC,n}$ (where $\overline{E},\overline{W} \in E_2$)
436 \end{enumerate}
437\end{frame}
438
439\begin{frame}{Original Nova Decider}
440 \begin{itemize}
441 \item Original Nova: wrap these checks in 2 Spartan (zkSNARK) proofs (one over each curve of the cycle of curves).\\
442 $\longrightarrow$ 2 Spartan proofs, one on each curve\\
443 \item In our case we were interested into verifying the proofs in Ethereum's EVM.
444 \end{itemize}
445
446 Need to do a bit of gymnastics to verify the folding proofs in Ethereum,\\
447 EVM limitations:
448 \begin{itemize}
449 \item limited to BN254 curve
450 \item constrained by gas costs
451 \end{itemize}
452\end{frame}
453
454\begin{frame}{Onchain Decider}
455{\tiny
456 \begin{enumerate}
457 \item[1.1:] check that the given NIFS challenge $r$ is indeed well computed.
458 \\This challenge is then used outside the circuit by the Verifier to compute NIFS.V obtaining $U_{i+1}$
459 \item[2:] check that $u_n.\overline{E}=0$ and $u_n.u=1$
460 \item[3:] check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
461 \item[4:] correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
462 \item[5.1:] Check correct computation of the KZG challenges
463 \\$c_E = H(\overline{E}.\{x,y\}),~~c_W = H(\overline{W}.\{x,y\})$
464 \\which we do through in-circuit Transcript.
465 \item[5.2:] check that the KZG evaluations are correct, $eval_W == p_W(c_W),~~ eval_E == p_E(c_E)$
466 \\where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
467 \item[6:] check the correct RelaxedR1CS relation of $U_{EC,n}, W_{EC,n}$ of the CycleFoldCircuit
468 \\(this is non-native operations and with naive sparse matrix-vector product blows up the number of constraints)
469 \item[7:] Pedersen commitments verification of $U_{EC,n}.\{ \overline{E}, \overline{W} \}$ with respect $W_{EC,n}$
470 \\(the witness of the committed instance)
471 \\(where $\overline{E},\overline{W} \in E_2$, this check is native in $F_r$)
472 \end{enumerate}
473
474 \emph{The following check is done non-natively (in $F_r$):}
475 Additionally we would have to check (outside of the circuit):
476
477 \begin{enumerate}
478 \item[1.2:] check $NIFS.V(r, U_n, u_n, \overline{T}) \stackrel{?}{=} U_{n+1}$
479 \item[5.3:] Commitments verification of $U_{n+1}.\{ \overline{E}, \overline{W} \}$ with respect $W_{n+1}$ (where $\overline{E}, \overline{W} \in E_1$)
480 \end{enumerate}
481
482 {\tiny More details in Sonobe's docs: \href{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}{https://privacy-scaling-explorations.github.io/sonobe-docs/design/novacyclefold-circuit.html}}
483}
484\end{frame}
485
486\begin{frame}{Onchain Decider}
487 % DRAW of the full flow: from inputting the circuit, to folding to generating the Decider proof to verifying in Ethereum
488 \includegraphics[width=8cm]{folding-scheme-pipeline-without-augmentedfcircuit}
489 \pause
490 \includegraphics[width=\textwidth]{decider-onchain-flow-diagram}
491\end{frame}
492
493
494% TODO maybe remove
495% \begin{frame}{Offchain Decider}
496% {\tiny
497% \textbf{Circuit1} $\in \mathbb{F}_r$ ($E_1.\mathbb{F}_r$):
498% \begin{enumerate}
499% \item[1.1:] check that the given NIFS challenge $r$ is indeed well computed.
500% \\This challenge is then used outside the circuit by the Verifier to compute NIFS.V obtaining $U_{i+1}$
501% \item[2:] check that $u_n.\overline{E}=0$ and $u_n.u=1$
502% \item[3:] check that $u_n.x_0 = H(n, z_0, z_n, U_n)$ and $u_n.x_1 = H(U_{EC,n})$
503% \item[4:] correct RelaxedR1CS relation of $U_{n+1}, W_{n+1}$ of the AugmentedFCircuit
504% \item[5.1:] Check correct computation of the CommitmentScheme challenges for $U_{n+1}$
505% \\$$c_E = H(U_{n+1}.\overline{E}.\{x,y\}),~~c_W = H(U_{n+1}.\overline{W}.\{x,y\})$$
506% \\which we do through in-circuit Transcript.
507% \item[5.2:] check that the CommitmentScheme evaluations for $U_{n+1}$ are correct, $eval_W == p_W(c_W),~~~ eval_E == p_E(c_E)$
508% \\where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
509% \end{enumerate}
510%
511% \textbf{Circuit2} $\in \mathbb{F}_q$ ($E_2.\mathbb{F}_r$):
512% \begin{enumerate}
513% \item[6:] correct RelaxedR1CS relation of $U_{EC,d}, W_{EC,d}$
514% \item[7.1:] Check correct computation of the CommitmentScheme challenges for $U_{EC}$
515% \\$$c_E = H(U_{EC}.\overline{E}.\{x,y\}),~~c_W = H(U_{EC}.\overline{W}.\{x,y\})$$
516% \\which we do through in-circuit Transcript.
517% \item[7.2:] check that the CommitmentScheme evaluations for $U_{EC}$ are correct
518% - $eval_W == p_W(c_W)$
519% - $eval_E == p_E(c_E)$
520% \\where $p_W, p_E \in \mathbb{F}[X]$ are the interpolated polynomials from $W_{i+1}.W,~ W_{i+1}.E$ respectively.
521% \end{enumerate}
522%
523% \textbf{Outside the circuits}:
524% \begin{enumerate}
525% \item[1.2:] check $NIFS.V(r, U_d, u_d, \overline{T}) \stackrel{?}{=} U_{d+1}$
526% \item[5.3:] Commitments verification of $U_{d+1}.\{ \overline{E}, \overline{W} \}$
527% \\with respect $W_{d+1}$ (where $\overline{E}, \overline{W} \in E_1$)
528% \item[7.3:] Commitments verification of $U_{EC,d}.\{ \overline{E}, \overline{W} \}$
529% \\with respect $W_{EC,d}$
530% \\(where $\overline{E},\overline{W} \in E_2$)
531% \end{enumerate}
532% }
533% TODO fix that currently it does not fit in the slide
534
535\end{frame}
536
537
538\section{Sonobe}
539
540\begin{frame}{Sonobe}
541
542 \footnotesize{
543 Experimental folding schemes library implemented jointly by 0xPARC and PSE.\\
544 \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
545 \\Modular library,
546 \begin{itemize}
547 \item Be able to
548 \begin{itemize}
549 \item Add and test new folding schemes
550 \item Compare schemes 'apples-to-apples'
551 \item Researchers can easily add their own schemes (eg. Mova paper)
552 \end{itemize}
553 \item Make it easy for devs to use folding
554 \begin{itemize}
555 \item minimal code to fold your circuits ('plug-and-fold')
556 \item easy to switch between folding schemes and curves
557 \item support of multiple zk-circuit languages
558 \end{itemize}
559 \end{itemize}
560
561 \vspace{0.5cm}
562 \emph{Remark}: experimental and unoptimized.
563 }
564\end{frame}
565
566\begin{frame}{Sonobe - Dev experience}
567 \scriptsize{
568
569 Dev flow:
570 \begin{enumerate}
571 \item Define a circuit to be folded
572 \item Set which folding scheme to be used (eg. Nova with CycleFold)
573 \item Set a final decider to generate the final proof (eg. Groth16 over BN254 curve)
574 \item Generate the Solidity decider verifier (EVM Solidity contract)
575 \end{enumerate}
576 }
577
578 \includegraphics[width=\textwidth]{folding-scheme-pipeline-without-augmentedfcircuit}
579 Sonobe lib pipeline:
580 \includegraphics[width=\textwidth]{sonobe-lib-pipeline}
581\end{frame}
582
583
584\begin{frame}{Status of Sonobe - schemes implemented}
585 \scriptsize{
586 Implemented (fully implemented):
587 \begin{itemize}
588 \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
589 \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
590 \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
591 \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
592 \end{itemize}
593 {\tiny
594 Started (NIFS implemented, next: folding circuit, IVC, Decider, etc):
595 \begin{itemize}
596 \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
597 \item \textbf{Ova}: Reduce the accumulation verifier in Nova from 2 to just 1 group operation\\ \href{https://eprint.iacr.org/2024/1220.pdf}{https://eprint.iacr.org/2024/1220.pdf}, Benedikt Bünz. 2024
598 \end{itemize}
599 }
600
601 Frontends - how can the dev define a circuit to be folded
602 \begin{itemize}
603 \item Arkworks \href{https://github.com/arkworks-rs}{https://github.com/arkworks-rs}
604 \item experimental: Circom, Noir, Noname.
605 % Frontends - how can the dev define a circuit to be folded
606 % \begin{itemize}
607 % \item Arkworks \href{https://github.com/arkworks-rs/}{https://github.com/arkworks-rs/}
608 % \item experimental:
609 % \begin{itemize}
610 % \item Circom \href{https://github.com/iden3/circom}{https://github.com/iden3/circom}
611 % \item Noir \href{https://noir-lang.org/}{https://noir-lang.org/}
612 % \item Noname \href{https://github.com/zksecurity/noname}{https://github.com/zksecurity/noname}
613 % \end{itemize}
614 \end{itemize}
615
616 }
617\end{frame}
618
619\begin{frame}{Modularity}
620 % TODO
621 Big thanks to arkworks \href{https://github.com/arkworks-rs}{https://github.com/arkworks-rs}
622
623 \vspace{1cm}
624 [Code example in the code editor]
625
626\end{frame}
627
628\begin{frame}{Some numbers}
629 \footnotesize{
630 (code highly unoptimized)
631 \begin{itemize}
632 \item folding step $\sim 300 ms$
633 \begin{itemize}
634 \item Folding circuit (Nova+CycleFold): $\sim 50k$ R1CS constraints (overhead)
635 \end{itemize}
636 \item Offchain Decider prove: $< 1$ min
637 \item Onchain Decider Verification:
638 \begin{itemize}
639 \item DeciderEthCircuit: $\sim 10M$ R1CS constraints
640 \begin{itemize}
641 \item $<3$ minutes in a 32GB RAM 16 core laptop
642 \end{itemize}
643 \item gas costs (DeciderEthCircuit proof): $\sim 800k$ gas
644 \begin{itemize}
645 \item mostly from G16, KZG10, public inputs processing
646 \item can be reduced by hashing the public inputs \& batching the pairings check
647 \item expect to get it down to $< 500k$ gas.
648 \end{itemize}
649 \end{itemize}
650 \end{itemize}
651 }
652
653 \vspace{0.6cm}
654
655 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$.
656\end{frame}
657
658\begin{frame}{Wrappup}
659 \small{
660 \begin{itemize}
661 \item repo: \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
662 \item docs: \href{https://privacy-scaling-explorations.github.io/sonobe-docs/}{https://privacy-scaling-explorations.github.io/sonobe-docs/}
663 \end{itemize}
664 }
665
666 \begin{center}
667 \includegraphics[width=5cm]{./imgs/sonobe-link-qrcode}
668 \end{center}
669
670\tiny{
671 $$\text{2024-10-08}$$
672 $$\text{\href{https://0xparc.org}{0xPARC}~\&~\href{https://pse.dev/}{PSE.}}$$
673}
674\end{frame}
675
676% \begin{frame}{NEWFRAME}
677% \end{frame}
678%
679% \begin{frame}{NEWFRAME}
680% \end{frame}
681
682\end{document}