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[Preliminaries]{Preliminaries}
 93\begin{frame}{Homomorphic commitments}
 94  [TODO] Homomorphic commitment definition
 95
 96  ie. Pedersen commitments\\
 97  Let $g \in \mathbb{G}^n,~ v \in \mathbb{F}_r^n$,\\
 98  $$Com(v) = \langle g, v \rangle =g_1 \cdot v_1 + g_2 \cdot v_2 + \ldots + g_n \cdot v_n$$
 99
100  % \pause
101
102  RLC\\
103  Let $v_1, v_2 \in \mathbb{F}_r^n$, set $cm_1 = Com(v_1),~ cm_2=Com(v_2)$.
104  \\then,
105  \begin{align*}
106    v_3 &= v_1 + r \cdot v_2\\
107    cm_3 &=cm_1 + r \cdot cm_2
108  \end{align*}
109  \\so that
110  $$cm_3 = Com(v_3)$$
111
112\end{frame}
113
114\section[Folding]{Folding}
115\begin{frame}{Relaxed R1CS}
116  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$,
117
118$$Az \circ Bz = Cz$$
119
120% \pause
121
122Relaxed R1CS:
123
124$$Az \circ Bz = uCz + E$$
125
126for $u \in \mathbb{F},~~ E \in \mathbb{F}^n$.
127
128\vspace{1cm}
129
130Committed Relaxed R1CS instance: $CI = (\overline{E}, u, \overline{W}, x)$\\
131Witness of the instance: $WI=(E, W)$
132
133
134\end{frame}
135
136\begin{frame}{NIFS - Non Interactive Folding Scheme}
137  \scriptsize{
138  \begin{align*}
139    CI_1 &=(\overline{E}_1, u_1, \overline{W}_1, x_1) ~~~~~~WI_1=(E_1, W_1)\\
140    CI_2 &=(\overline{E}_2, u_2, \overline{W}_2, x_2) ~~~~~~WI_2=(E_2, W_2)
141  \end{align*}
142  where $\overline{V}=Com(V)$
143
144
145% \pause
146
147  \begin{align*}
148    T &= Az_1 \circ Bz_1 + Az_2 \circ Bz_2 - u_1 C z_1 - u_2 C z_2\\
149    \overline{T}&=Com(T)
150  \end{align*}
151  % \pause
152
153\begin{minipage}[t]{.45\textwidth}
154  NIFS.P
155  \begin{align*}
156    E &= E_1 + r \cdot T + r^2 \cdot E_2\\
157    W &= W_1 + r \cdot W
158  \end{align*}
159\end{minipage}
160\hfill\vline\hfill
161\begin{minipage}[t]{.45\textwidth}
162  NIFS.V
163  \begin{align*}
164    \overline{E} &= \overline{E}_1 + r \cdot \overline{T} + r^2 \cdot \overline{E}_2\\
165    u &= u_1 + r \cdot u_2\\
166    \overline{W} &= \overline{W}_1 + r \cdot \overline{W}\\
167    x &= x_1 + r \cdot x_2
168  \end{align*}
169\end{minipage}
170
171New folded Committed Instance: $(\overline{E}, u, \overline{W}, x)$\\
172New folded witness: $(E, W)$
173}
174\end{frame}
175
176\begin{frame}{IVC}
177  \small{
178  $U_i$: committed instance for the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
179  $u_i$: committed instance for the correct execution of invocation $i$ of $F'$
180  }
181
182  % draw: sketch of the Augmented F Circuit
183  % big box for F', inside small box for F. NIFS.V box, how things connect to next iteration
184
185  \vspace{4cm}
186  
187  \small{
188  F':\\
189  i) execute a step of the incremental computation, $z_i+1 = F(z_i)$\\
190  ii) invoke the NIFS.V to fold $U_i, u_i$ into $U_{i+1}$\\
191  iii) other checks to ensure that the IVC is done properly
192  }
193\end{frame}
194
195\begin{frame}{Cycle of curves}
196  \small{
197  NIFS.V involves $\mathbb{G}$ point scalar mults, which are not native over $\mathbb{F}_r$.
198  \\$\longrightarrow$ delegate them into a circuit over a 2nd curve.
199
200  \vspace{0.3cm}
201
202  We 'mirror' the main $F'$ circuit into the 2nd curve\\
203  each circuit computes natively the point operations of the other curve
204  }
205
206  % draw:
207  % 1st the Nova with duplicated F' circuits over 2 curves
208  % 2nd the Nova with CycleFold circuits sketch
209\end{frame}
210
211
212\begin{frame}{Augmented F Circuit + CycleFold Circuit}
213  \includegraphics[width=\textwidth]{cyclefold-nova-diagram}
214\end{frame}
215
216\begin{frame}{Other Folding Schemes}
217  % TODO
218  % HyperNova
219  % ProtoGalaxy
220  % ProtoStar
221  % LatticeFold
222  % etc
223  % mention a bit the different characteristics and folding techniques
224\end{frame}
225
226\section{Decider (Final Proof)}
227
228\begin{frame}{Decider}
229  \includegraphics[width=\textwidth]{cyclefold-paper-diagram}
230
231  With Prover knowing the respective witnesses for $U_n, u_n, U_{EC,n}$
232
233  \vspace{1cm}
234
235  Issue: IVC proof is not succinct
236\end{frame}
237
238\begin{frame}{Decider}
239  Original Nova: generate a zkSNARK proof with Spartan for $U_n, u_n, U_{EC, n}$\\
240  $\longrightarrow$ 2 Spartan proofs, one on each curve (with CycleFold is 1 Spartan proof)\\
241  (not EVM-friendly)
242
243  % draw of the 2 circuits over the curves, and how we generate a Spartan proof for each one
244
245\end{frame}
246
247\begin{frame}{Decider}
248  checks (simplified)
249  \begin{enumerate}
250    \item $(U_{n+1}, W_{n+1})$ satisfy Relaxed R1CS relation of AugmentedFCircuit
251    \item verify commitments of $U_{n+1}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{n+1}.\{E,W\}$
252    \item $(U_{EC,n}, W_{EC,n})$ satisfy Relaxed R1CS relation of CycleFoldCircuit
253    \item verify commitments of $U_{EC,n}.\{\overline{E}, \overline{W}\}$ w.r.t. $W_{EC,n}.\{E,W\}$
254    \item $u_n.E==0,~ u_n.u==1$, ie. $u_n$ is a fresh not-relaxed instance
255    \item $u_n.x_0==H(n, z_0, z_n, U_n)$\\
256          $u_n.x_1==H(U_{EC,n})$
257    \item $NIFS.V(U_n, u_n)==U_{n+1}$
258  \end{enumerate}
259
260  % by draw show which are native and not native
261  % and that the NIFS.V we do it in Solidity
262\end{frame}
263
264\begin{frame}{Decider}
265  \includegraphics[width=\textwidth]{decider-onchain-flow-diagram}
266  % draw of the full flow: from inputting the circuit, to folding to generating the Decider proof to verifying in Ethereum
267\end{frame}
268
269\section{Sonobe}
270\begin{frame}{Sonobe}
271  \footnotesize{
272  Experimental folding schemes library implemented jointly by 0xPARC and PSE.
273
274  \vspace{0.3cm}
275
276  Dev flow:
277  \begin{enumerate}
278    \item Define a circuit to be folded
279    \item Set which folding scheme to be used (eg. Nova with CycleFold)
280    \item Set a final decider to generate the final proof (eg. Spartan over Pasta curves)
281    \item Generate the the decider verifier
282  \end{enumerate}
283  }
284
285  \vspace{1cm}
286
287  \includegraphics[width=\textwidth]{sonobe-lib-pipeline}
288\end{frame}
289
290\begin{frame}{Code example}
291
292\end{frame}
293
294
295\begin{frame}
296\frametitle{Wrappup}
297\begin{itemize}
298  \item \href{https://github.com/privacy-scaling-explorations/sonobe}{https://github.com/privacy-scaling-explorations/sonobe}
299  \item \href{https://privacy-scaling-explorations.github.io/sonobe-docs/}{https://privacy-scaling-explorations.github.io/sonobe-docs/}
300\end{itemize}
301
302  \includegraphics[width=4cm]{qr-sonobe-repo-link}
303
304\tiny{
305  $$\text{2024-04-22}$$
306  $$\text{\href{https://0xparc.org}{0xPARC}~\&~\href{https://pse.dev/}{PSE.}}$$
307}
308\end{frame}
309
310\end{document}