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
 38
 39\title{Anatomy of a folding scheme}
 40\author{\small{Sonobe, experimental folding schemes library implemented jointly by \href{https://0xparc.org}{0xPARC} and \href{https://pse.dev/}{PSE.}}}
 41
 42\date{\vspace{1cm}\\\scriptsize{2024-04-22\\Barcelona zkDay}}
 43
 44\begin{document}
 45
 46\frame{\titlepage}
 47
 48
 49% To mention at the beginning:
 50% we would need more than 2h to show a bit of more detail, but we only have 20min
 51
 52
 53\section[Motivation]{Motivation}
 54
 55\begin{frame}{Why folding}
 56  \begin{itemize}
 57    \item Repetitive computations take big circuits $\longrightarrow$ large proving time
 58    \begin{itemize}
 59      \item ie. prove a chain of 10k sha256 hashes
 60    \end{itemize}
 61
 62    % \pause
 63
 64    \item Traditional recursion: verify (in-circuit) a proof of the correct execution of the same circuit for the previous input
 65    \begin{itemize}
 66      \item issue: in-circuit proof verification is expensive (constraints)
 67      \begin{itemize}
 68        \item ie. verify a Groth16 proof inside a R1CS circuit
 69      \end{itemize}
 70    \end{itemize}
 71  \end{itemize}
 72
 73  % draw: G16 proof being verified inside a circuit for which a new proof is generated
 74\end{frame}
 75
 76\begin{frame}{IVC - Incremental Verifiable Computation}
 77  Folding schemes efficitently achieve IVC, where the prover recursively proves the correct execution of the incremental computations.
 78
 79  \includegraphics[width=\textwidth]{folding-main-idea-diagram}
 80
 81  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})$.
 82
 83\end{frame}
 84
 85
 86\begin{frame}{Folding idea}
 87  % draw of 2 instances being folded into a single one
 88  % then add other instances to show k-to-1 folding
 89\end{frame}
 90
 91
 92\section[Folding]{Folding}
 93\begin{frame}{Homomorphic commitments and RLC}
 94  We rely on homomorphic commitments\\
 95  ie. Pedersen commitments\\
 96  Let $g \in \mathbb{G}^n,~ v \in \mathbb{F}_r^n$,\\
 97  $$Com(v) = \langle g, v \rangle =g_1 \cdot v_1 + g_2 \cdot v_2 + \ldots + g_n \cdot v_n$$
 98
 99  % \pause
100
101  RLC:\\
102  Let $v_1, v_2 \in \mathbb{F}_r^n$, set $cm_1 = Com(v_1),~ cm_2=Com(v_2)$.
103  \\then,
104  \begin{align*}
105    v_3 &= v_1 + r \cdot v_2\\
106    cm_3 &=cm_1 + r \cdot cm_2
107  \end{align*}
108  \\so that
109  $$cm_3 = Com(v_3)$$
110
111\end{frame}
112
113\begin{frame}{Relaxed R1CS}
114  R1CS instance: $(\{A, B, C\} \in \mathbb{F}^{n \times n},~ io,~ n,~ l)$, such that for $z=(io \in \mathbb{F}^l, 1, w \in \mathbb{F}^{n-l-1}) \in \mathbb{F}^n$,
115
116$$Az \circ Bz = Cz$$
117
118% \pause
119
120Relaxed R1CS:
121
122$$Az \circ Bz = uCz + E$$
123
124for $u \in \mathbb{F},~~ E \in \mathbb{F}^n$.
125
126\vspace{1cm}
127
128Committed Relaxed R1CS instance: $CI = (\overline{E}, u, \overline{W}, x)$\\
129Witness of the instance: $WI=(E, W)$
130
131\vspace{0.5cm}
132\footnotesize{(We don't have time for it now, but there is a simple reasoning for the RelaxedR1CS usage explained in Nova paper)}
133
134
135\end{frame}
136
137\begin{frame}{NIFS - Non Interactive Folding Scheme}
138  \scriptsize{
139  \begin{align*}
140    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)\\
141    CI_2 &=(\overline{E}_2, u_2, \overline{W}_2, x_2) ~~~~~~WI_2=(E_2, W_2)
142  \end{align*}
143  where $\overline{V}=Com(V)$
144
145
146% \pause
147
148  \begin{align*}
149    T &= Az_1 \circ Bz_1 + Az_2 \circ Bz_2 - u_1 C z_1 - u_2 C z_2\\
150    \overline{T}&=Com(T)
151  \end{align*}
152  % \pause
153
154\begin{minipage}[t]{.45\textwidth}
155  NIFS.P
156  \begin{align*}
157    E &= E_1 + r \cdot T + r^2 \cdot E_2\\
158    W &= W_1 + r \cdot W
159  \end{align*}
160\end{minipage}
161\hfill\vline\hfill
162\begin{minipage}[t]{.45\textwidth}
163  NIFS.V
164  \begin{align*}
165    \overline{E} &= \overline{E}_1 + r \cdot \overline{T} + r^2 \cdot \overline{E}_2\\
166    u &= u_1 + r \cdot u_2\\
167    \overline{W} &= \overline{W}_1 + r \cdot \overline{W}\\
168    x &= x_1 + r \cdot x_2
169  \end{align*}
170\end{minipage}
171
172New folded Committed Instance: $(\overline{E}, u, \overline{W}, x)$\\
173New folded witness: $(E, W)$
174}
175\end{frame}
176
177\begin{frame}{IVC}
178  \small{
179  $U_i$: committed instance for the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
180  $u_i$: committed instance for the correct execution of invocation $i$ of $F'$
181  }
182
183  % draw: sketch of the Augmented F Circuit
184  % big box for F', inside small box for F. NIFS.V box, how things connect to next iteration
185
186  \vspace{4cm}
187  
188  \small{
189  F':\\
190  i) execute a step of the incremental computation, $z_{i+1} = F(z_i)$\\
191  ii) invoke the NIFS.V to fold $U_i, u_i$ into $U_{i+1}$\\
192  iii) other checks to ensure that the IVC is done properly
193  }
194\end{frame}
195
196\begin{frame}{Cycle of curves}
197  \small{
198  NIFS.V involves $\mathbb{G}$ point scalar mults, which are not native over $\mathbb{F}_r$.
199  \\$\longrightarrow$ delegate them into a circuit over a 2nd curve.
200
201  \vspace{0.3cm}
202
203  We 'mirror' the main $F'$ circuit into the 2nd curve\\
204  each circuit computes natively the point operations of the other curve
205  }
206
207  % draw:
208  % 1st the Nova with duplicated F' circuits over 2 curves
209  % 2nd the Nova with CycleFold circuits sketch
210\end{frame}
211
212
213\begin{frame}{Augmented F Circuit + CycleFold Circuit}
214  \includegraphics[width=\textwidth]{cyclefold-nova-diagram}
215\end{frame}
216
217\begin{frame}{Other Folding Schemes}
218  % TODO
219  % HyperNova
220  % ProtoGalaxy
221  % ProtoStar
222  % LatticeFold
223  % etc
224  % mention a bit the different characteristics and folding techniques
225\end{frame}
226
227\section{Decider (Final Proof)}
228
229\begin{frame}{Decider}
230  \includegraphics[width=\textwidth]{cyclefold-paper-diagram}
231
232  With Prover knowing the respective witnesses for $U_n, u_n, U_{EC,n}$
233
234  \vspace{1cm}
235
236  Issue: IVC proof is not succinct
237\end{frame}
238
239\begin{frame}{Decider}
240  Original Nova: generate a zkSNARK proof with Spartan for $U_n, u_n, U_{EC, n}$\\
241  $\longrightarrow$ 2 Spartan proofs, one on each curve (with CycleFold is 1 Spartan proof)\\
242  (not EVM-friendly)
243
244  % draw of the 2 circuits over the curves, and how we generate a Spartan proof for each one
245
246\end{frame}
247
248\begin{frame}{Decider}
249  checks (simplified)
250  \begin{enumerate}
251    \item $(U_{n+1}, W_{n+1})$ satisfy Relaxed R1CS relation of AugmentedFCircuit
252    \item verify commitments of $U_{n+1}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{n+1}.\{E,W\}$
253    \item $(U_{EC,n}, W_{EC,n})$ satisfy Relaxed R1CS relation of CycleFoldCircuit
254    \item verify commitments of $U_{EC,n}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{EC,n}.\{E,W\}$
255    \item $u_n.E==0,~ u_n.u==1$, ie. $u_n$ is a fresh not-relaxed instance
256    \item $u_n.x_0==H(n, z_0, z_n, U_n)$\\
257          $u_n.x_1==H(U_{EC,n})$
258    \item $NIFS.V(U_n, u_n)==U_{n+1}$
259  \end{enumerate}
260
261  % by draw show which are native and not native
262  % and that the NIFS.V we do it in Solidity
263\end{frame}
264
265\begin{frame}{Decider}
266  \includegraphics[width=\textwidth]{decider-onchain-flow-diagram}
267  % draw of the full flow: from inputting the circuit, to folding to generating the Decider proof to verifying in Ethereum
268\end{frame}
269
270\section{Sonobe}
271\begin{frame}{Sonobe}
272  \footnotesize{
273  Experimental folding schemes library implemented jointly by 0xPARC and PSE.
274
275  \vspace{0.3cm}
276
277  Dev flow:
278  \begin{enumerate}
279    \item Define a circuit to be folded
280    \item Set which folding scheme to be used (eg. Nova with CycleFold)
281    \item Set a final decider to generate the final proof (eg. Spartan over Pasta curves)
282    \item Generate the the decider verifier
283  \end{enumerate}
284  }
285
286  \vspace{1cm}
287
288  \includegraphics[width=\textwidth]{sonobe-lib-pipeline}
289\end{frame}
290
291\begin{frame}{Code example}
292  [show code with a live demo]
293  \vspace{0.5cm}
294
295  Some numbers (still optimizations pending):
296  \begin{itemize}
297  \item AugmentedFCircuit: $\sim 80k$ R1CS constraints
298  \item DeciderEthCircuit: $\sim 9.6M$ R1CS constraints
299  \begin{itemize}
300    \item $<3$ minutes in a 32GB RAM 16 core laptop
301  \end{itemize}
302  \item gas costs (DeciderEthCircuit proof): $\sim 800k$ gas
303  \begin{itemize}
304    \item mostly from G16, KZG10, public inputs processing
305    \item will be reduced by hashing the public inputs
306    \item expect to get it down to $< 600k$ gas.
307  \end{itemize}
308  \end{itemize}
309
310  \vspace{0.3cm}
311
312Recall, 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$.
313\\In Srinath Setty words, you can prove practically unbounded computation onchain by 800k gas (and soon $< 600k$).
314
315
316\end{frame}
317
318
319\begin{frame}
320\frametitle{Wrappup}
321\begin{itemize}
322  \item \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
323  \item \href{https://privacy-scaling-explorations.github.io/sonobe-docs/}{https://privacy-scaling-explorations.github.io/sonobe-docs/}
324\end{itemize}
325
326\begin{center}
327  \includegraphics[width=4cm]{qr-sonobe-repo-link}
328\end{center}
329
330\tiny{
331  $$\text{2024-04-22}$$
332  $$\text{\href{https://0xparc.org}{0xPARC}~\&~\href{https://pse.dev/}{PSE.}}$$
333}
334\end{frame}
335
336\end{document}