math/slides_hypernova-part2-multifolding-unfolded.tex
slides_hypernova-part2-multifolding-unfolded.texRaw
1\documentclass{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\usepackage{pgf-umlsd} % diagrams
21
22\setbeamertemplate{itemize}{$\circ$}
23\setbeamertemplate{itemize items}{$\circ$}
24
25\beamertemplatenavigationsymbolsempty %% no navigation bar
26
27\setbeamertemplate{footline}{\hspace*{.1cm}\scriptsize{
28\hspace*{50pt} \hfill\insertframenumber/\inserttotalframenumber\hspace*{.1cm}\vspace*{.1cm}}}
29
30\setbeamertemplate{caption}[numbered]
31\setbeamerfont{caption}{size=\tiny}
32
33% message between threads. From https://tex.stackexchange.com/a/174765
34% Example:
35% \bloodymess[delay]{sender}{message content}{receiver}{DIR}{start note}{end note}
36\newcommand{\bloodymess}[7][0]{
37 \stepcounter{seqlevel}
38 \path
39 (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
40 \addtocounter{seqlevel}{#1}
41 \path
42 (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
43 \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
44 {#3};
45
46 \if R#5
47 \node (\detokenize{#3} from) at (mess from) {\llap{#6~}};
48 \node (\detokenize{#3} to) at (mess to) {\rlap{~#7}};
49 \else\if L#5
50 \node (\detokenize{#3} from) at (mess from) {\rlap{~#6}};
51 \node (\detokenize{#3} to) at (mess to) {\llap{#7~}};
52 \else
53 \node (\detokenize{#3} from) at (mess from) {#6};
54 \node (\detokenize{#3} to) at (mess to) {#7};
55 \fi
56 \fi
57}
58
59
60
61%Information to be included in the title page:
62\title{HyperNova's multifolding overview}
63\author{}
64\date{\scriptsize{2023-06-22\\\href{https://0xparc.org}{0xPARC} Novi team}}
65
66\begin{document}
67
68\frame{\titlepage}
69
70\section[Overview]{Overview}
71
72\begin{frame}{Multifolding - Overview}
73
74 \begin{tiny}
75 \begin{enumerate}
76 \item[1.] $V \rightarrow P: \gamma \in^R \mathbb{F},~ \beta \in^R \mathbb{F}^s$
77 \item[2.] $V: r_x' \in^R \mathbb{F}^s$
78 \item[3.] $V \leftrightarrow P$: sum-check protocol:
79 $c \leftarrow \langle P, V(r_x') \rangle (g, s, d+1, \underbrace{\sum_{j \in [t]} \gamma^j \cdot v_j}_\text{T})$, where:
80 \begin{align*}
81 g(x) &:= \underbrace{\left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right)}_\text{LCCCS check} + \underbrace{\gamma^{t+1} \cdot Q(x)}_\text{CCCS check}\\
82 L_j(x) &:= \widetilde{eq}(r_x, x) \cdot \left(
83 \underbrace{\sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)}_\text{LCCCS check}
84 \right)\\
85 Q(x) := &\widetilde{eq}(\beta, x) \cdot \left(
86 \underbrace{ \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right) }_\text{CCCS check}
87 \right)
88 \end{align*}
89 \end{enumerate}
90 \end{tiny}
91
92\end{frame}
93
94\begin{frame}{Multifolding - Overview}
95
96 \begin{tiny}
97 \begin{enumerate}
98 \item[4.] $P \rightarrow V$: $\left( (\sigma_1, \ldots, \sigma_t), (\theta_1, \ldots, \theta_t) \right)$, where $\forall j \in [t]$,
99 $$\sigma_j = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
100 $$\theta_j = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_2(y)$$
101 \item[5.] V: $e_1 \leftarrow \widetilde{eq}(r_x, r_x')$, $e_2 \leftarrow \widetilde{eq}(\beta, r_x')$\\
102 check:
103 $$c = \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_j \right) + \gamma^{t+1} \cdot e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)$$
104 \item[6.] $V \rightarrow P: \rho \in^R \mathbb{F}$
105 \item[7.] $V, P$: output the folded LCCCS instance $(C', u', \mathsf{x}', r_x', v_1', \ldots, v_t')$, where $\forall i \in [t]$:
106 \begin{align*}
107 C' &\leftarrow C_1 + \rho \cdot C_2\\
108 u' &\leftarrow u + \rho \cdot 1\\
109 \mathsf{x}' &\leftarrow \mathsf{x}_1 + \rho \cdot \mathsf{x}_2\\
110 v_i' &\leftarrow \sigma_i + \rho \cdot \theta_i
111 \end{align*}
112 \item[8.] $P$: output folded witness and the folded $r_w'$:
113 \begin{align*}
114 \widetilde{w}' &\leftarrow \widetilde{w}_1 + \rho \cdot \widetilde{w}_2\\
115 r_w' &\leftarrow r_{w_1} + \rho \cdot r_{w_2}
116 \end{align*}
117 \end{enumerate}
118 \end{tiny}
119
120\end{frame}
121
122
123
124\begin{frame}{Multifolding - Overview}
125 \begin{tiny}
126\begin{center}
127 \begin{sequencediagram}
128 \newinst[1]{p}{Prover}
129 \newinst[3]{v}{Verifier}
130
131 \bloodymess[1]{v}{$\gamma,~\beta,~r_x'$}{p}{L}{
132 \shortstack{
133 $\gamma \in \mathbb{F},~ \beta \in \mathbb{F}^s$\\
134 $r_x' \in \mathbb{F}^s$
135 }
136 }{}
137 \bloodymess[1]{p}{$c,~ \pi_{SC}$}{v}{R}{sum-check prove}{sum-check verify}
138 \bloodymess[1]{p}{$\{\sigma_j\},~\{\theta_j\}$}{v}{R}{compute $\{\sigma_j\}, \{\theta_j\}~ \forall j \in [t]$}{verify $c$ with $\{\sigma_j\}, \{\theta_j\}$ relation}
139 \bloodymess[1]{v}{$\rho$}{p}{L}{$\rho \in^R \mathbb{F}$}{}
140 \callself[0]{p}{fold LCCCS instance}{p}
141 \prelevel
142 \callself[0]{v}{fold LCCCS instance}{v}
143 \callself[0]{p}{fold $\widetilde{w}, r_w$}{p}
144 \end{sequencediagram}
145\end{center}
146 \end{tiny}
147\end{frame}
148
149
150\section[Checks]{Checks}
151
152\begin{tiny}
153\begin{frame}{LCCCS checks}
154$$
155\color{gray}{g(x) :=}
156\color{black}{\underbrace{\left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right)}_\text{LCCCS} }
157\color{gray}{+ \gamma^{t+1} \cdot Q(x)}
158$$
159$$
160L_j(x) := \widetilde{eq}(r_x, x) \cdot \left(
161\underbrace{\sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)}_\text{LCCCS check}
162\right)
163$$
164
165
166Notice that, $v_j$ from LCCCS relation check
167
168\begin{align*}
169v_j &= \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x, y) \cdot \widetilde{z}_1(y)\\
170 &= \sum_{x \in \{0,1\}^s}
171 \widetilde{eq}(r_x, x) \cdot \left( \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y) \right)\\
172 &= \sum_{x \in \{0,1\}^s} L_j(x)
173\end{align*}
174
175\end{frame}
176\begin{frame}{CCCS checks}
177 $$
178 \color{gray}{g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) +}
179 \color{black}{\underbrace{\gamma^{t+1} \cdot Q(x)}_\text{CCCS}}
180 $$
181$$Q(x) := \widetilde{eq}(\beta, x) \cdot \left(
182 \underbrace{ \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right) }_\text{CCCS check}
183 \right)$$
184
185 Recall that Spartan's $\widetilde{F}_{io}(x)$ here is $q(x)$, so we're doing the same Spartan check:
186
187$$
1880 =G(\beta) = \sum_{x \in \{0,1\}^s} Q(x) = \sum_{x \in \{0,1\}^s} eq(\beta, x) \cdot q(x)$$
189$$= \sum_{x \in \{0,1\}^s}
190 \underbrace{\widetilde{eq}(\beta , x) \cdot
191 \overbrace{
192 \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right)
193 }^{q(x)}
194}_{Q(x)}
195$$
196
197\end{frame}
198
199
200\begin{frame}{Verifier checks}
201 \textcolor{gray}{
202Recall:
203$$g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) + \gamma^{t+1} \cdot Q(x)$$
204$$c = \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_j \right) + \gamma^{t+1} \cdot e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)$$
205}
206
207We can see now that V's check in step 5,
208
209\begin{align*}
210 c &=
211\left( \sum_{j \in [t]} \gamma^j \cdot \overbrace{e_1 \cdot \sigma_j}^{L_j(r_x')} \right) + \gamma^{t+1} \cdot \overbrace{e_2 \cdot \sum_{i \in [q]} c_i \prod_{j \in S_i} \theta_j}^{Q(x)}\\
212&= \left( \sum_{j \in [t]} \gamma^j \cdot L_j(r_x') \right) + \gamma^{t+1} \cdot Q(r_x')\\
213&= g(r_x')
214\end{align*}
215
216where $e_1 = \widetilde{eq}(r_x, r_x')$, $e_2=\widetilde{eq}(\beta, r_x')$.
217\end{frame}
218\end{tiny}
219
220\section[Multiple instances]{Multiple instances}
221
222\begin{footnotesize}
223\begin{frame}{Multifolding multiple instances}
224Hypernova paper: $\mu=1, \nu=1$ \emph{(ie. 1 LCCCS instance and 1 CCCS instance)}
225
226\vspace{1cm}
227In next slides
228\begin{itemize}
229 \item example with: $\color{orange}{LCCCS: \mu = 2},~ \color{blue}{CCCS: \nu = 2}$
230 \item generalized equations for $\mu,~\nu$
231\end{itemize}
232
233Let $z_1,~ \color{orange}{z_2}$ be the two LCCCS instances, and $z_3,~ \color{blue}{z_4}$ be the two CCCS instances
234
235\end{frame}
236\end{footnotesize}
237
238\begin{tiny}
239\begin{frame}
240 In \emph{step 3},
241
242\begin{align*}
243 g(x) &:= \left( \sum_{j \in [t]} \gamma^j \cdot L_{1,j}(x) + \textcolor{orange}{\gamma^{t+j} \cdot L_{2,j}(x)} \right)
244+ \gamma^{2t+1} \cdot Q_1(x) + \textcolor{cyan}{\gamma^{2t+2} \cdot Q_2(x)} \\
245 &L_{1,j}(x) := \widetilde{eq}(r_{1,x}, x) \cdot \left(
246 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)
247\right)\\
248 &\textcolor{orange}{L_{2,j}(x)} := \widetilde{eq}(\textcolor{orange}{r_{2,x}}, x) \cdot \left(
249 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}
250\right)\\
251 &Q_1(x) := \widetilde{eq}(\beta, x) \cdot \left(
252\sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_3(y) \right)\right)\\
253 &\textcolor{cyan}{Q_2(x)} := \widetilde{eq}(\textcolor{cyan}{\beta}, x) \cdot \left(
254 \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{cyan}{\widetilde{z}_4(y)} \right)\right)
255\end{align*}
256
257\framebox{\begin{minipage}{4.3 in}
258A generic definition of $g(x)$ for $\mu>1~\nu>1$, would be
259
260$$
261g(x) := \left( \sum_{i \in [\mu]} \left( \sum_{j \in [t]} \gamma^{i \cdot t+j} \cdot L_{i,j}(x) \right) \right)
262+ \left( \sum_{i \in [\nu]} \gamma^{\mu \cdot t + i} \cdot Q_i(x) \right)
263$$
264\end{minipage}}
265
266Recall, the original $g(x)$ definition was
267$$\textcolor{gray}{g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) + \gamma^{t+1} \cdot Q(x)}$$
268
269
270\end{frame}
271
272\begin{frame}
273 In \emph{step 4}, $P \rightarrow V$: $(\{\sigma_{1,j}\}, \textcolor{orange}{\{\sigma_{2,j}\}}, \{\theta_{1,j}\}, \textcolor{cyan}{\{\theta_{2,j}\}}),~ \text{where} ~\forall j \in [t]$,
274
275$$\sigma_{1,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
276$$\textcolor{orange}{\sigma_{2,j}} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}$$
277$$\theta_{1,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_3(y)$$
278$$\textcolor{cyan}{\theta_{2,j}} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{cyan}{\widetilde{z}_4(y)}$$
279
280\framebox{\begin{minipage}{4.3 in}
281 so in a generic way,\\
282$P \rightarrow V$:
283$(\{\sigma_{i,j}\}, \{\theta_{k,j}\}),~ \text{where} ~\forall~ j \in [t],~ \forall~ i \in [\mu],~ \forall~ k \in [\nu]$
284where
285$$\sigma_{i,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_i(y)$$
286$$\theta_{k,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_{\mu+k}(y)$$
287\end{minipage}}
288
289\end{frame}
290
291\begin{frame}
292 And in \emph{step 5}, $V$ checks
293
294\begin{align*}
295 c &= \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_{1,j}
296~\textcolor{orange}{+ \gamma^{t+j} \cdot e_2 \cdot \sigma_{2,j}}\right)
297 + \gamma^{2t+1} \cdot e_3 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)
298 + \textcolor{cyan}{\gamma^{2t+2} \cdot e_4 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)}
299\end{align*}
300
301where
302$e_1 \leftarrow \widetilde{eq}(r_{1,x}, r_x'),~ e_2 \leftarrow \widetilde{eq}(r_{2,x}, r_x')$, $e_3, e_4 \leftarrow \widetilde{eq}(\beta, r_x')$.
303
304\vspace{0.5cm}
305
306\framebox{\begin{minipage}{4.3 in}
307A generic definition of the check would be
308$$
309c = \sum_{i \in [\mu]} \left(\sum_{j \in [t]} \gamma^{i \cdot t + j} \cdot e_i \cdot \sigma_{i,j} \right) \\
310+ \sum_{k \in [\nu]} \gamma^{\mu \cdot t+k} \cdot e_k \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_{k,j} \right)
311$$
312\end{minipage}}
313
314where the original check was\\
315$\textcolor{gray}{c = \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_j \right) + \gamma^{t+1} \cdot e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)}$
316
317\end{frame}
318
319\begin{frame}
320And for the \emph{step 7},
321\begin{align*}
322 C' &\leftarrow C_1 + \rho \cdot C_2 + \rho^2 C_3 + \rho^3 C_4 + \ldots = \sum_{i \in [\mu + \nu]} \rho^i \cdot C_i \\
323 u' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot u_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot 1\\
324 \mathsf{x}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot \mathsf{x}_i\\
325 v_i' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot \sigma_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot \theta_i\\
326\end{align*}
327
328and \emph{step 8},
329\begin{align*}
330 \widetilde{w}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i\cdot \widetilde{w}_i\\
331 r_w' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot r_{w_i}\\
332\end{align*}
333
334\end{frame}
335
336\end{tiny}
337
338\section[Wrappup]{Wrappup}
339
340\begin{frame}
341\frametitle{Wrappup}
342\begin{itemize}
343 \item HyperNova: \href{https://eprint.iacr.org/2023/573}{https://eprint.iacr.org/2023/573}
344 \item multifolding PoC on arkworks: \href{https://github.com/privacy-scaling-explorations/multifolding-poc}{github.com/privacy-scaling-explorations/multifolding-poc}
345\end{itemize}
346
347\vspace{2cm}
348\tiny{
349 $$\text{2023-06-22}$$
350 $$\text{\href{https://0xparc.org}{0xPARC} Novi team}$$
351}
352\end{frame}
353
354\end{document}