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