math/notes_hypernova.tex
notes_hypernova.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4\usepackage{amsthm}
5\usepackage{amsmath}
6\usepackage{mathtools}
7\usepackage{enumerate}
8\usepackage{hyperref}
9\usepackage{xcolor}
10\usepackage{centernot}
11\usepackage{algorithm}
12\usepackage{algpseudocode}
13
14\usepackage{pgf-umlsd} % diagrams
15
16% message between threads. From https://tex.stackexchange.com/a/174765
17% Example:
18% \bloodymess[delay]{sender}{message content}{receiver}{DIR}{start note}{end note}
19\newcommand{\bloodymess}[7][0]{
20 \stepcounter{seqlevel}
21 \path
22 (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
23 \addtocounter{seqlevel}{#1}
24 \path
25 (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
26 \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
27 {#3};
28
29 \if R#5
30 \node (\detokenize{#3} from) at (mess from) {\llap{#6~}};
31 \node (\detokenize{#3} to) at (mess to) {\rlap{~#7}};
32 \else\if L#5
33 \node (\detokenize{#3} from) at (mess from) {\rlap{~#6}};
34 \node (\detokenize{#3} to) at (mess to) {\llap{#7~}};
35 \else
36 \node (\detokenize{#3} from) at (mess from) {#6};
37 \node (\detokenize{#3} to) at (mess to) {#7};
38 \fi
39 \fi
40}
41
42
43% prevent warnings of underfull \hbox:
44\usepackage{etoolbox}
45\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
46
47\theoremstyle{definition}
48\newtheorem{definition}{Def}[section]
49\newtheorem{theorem}[definition]{Thm}
50
51% custom lemma environment to set custom numbers
52\newtheorem{innerlemma}{Lemma}
53\newenvironment{lemma}[1]
54{\renewcommand\theinnerlemma{#1}\innerlemma}
55{\endinnerlemma}
56
57
58\title{Notes on HyperNova}
59\author{arnaucube}
60\date{May 2023}
61
62\begin{document}
63
64\maketitle
65
66\begin{abstract}
67 Notes taken while reading about HyperNova \cite{cryptoeprint:2023/573} and CCS\cite{cryptoeprint:2023/552}.
68
69 Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
70
71 The notes are not complete, don't include all the steps neither all the proofs.
72
73 Thanks to \href{https://twitter.com/asn_d6}{George Kadianakis} for clarifications, and the authors \href{https://twitter.com/srinathtv}{Srinath Setty} and \href{https://twitter.com/abhiramko}{Abhiram Kothapalli} for answers on chats and twitter.
74\end{abstract}
75
76\tableofcontents
77
78
79\section{CCS}
80\subsection{R1CS to CCS overview}
81
82\begin{description}
83 \item[R1CS instance] $S_{R1CS} = (m, n, N, l, A, B, C)$\\
84 where $m, n$ are such that $A \in \mathbb{F}^{m \times n}$, and $l$ such that the public inputs $x \in \mathbb{F}^l$. Also $z=(w, 1, x) \in \mathbb{F}^n$, thus $w \in \mathbb{F}^{n-l-1}$.
85 \item[CCS instance] $S_{CCS} = (m, n, N, l, t, q, d, M, S, c)$\\
86 where we have the same parameters than in $S_{R1CS}$, but additionally:\\
87 $t=|M|$, $q = |c| = |S|$, $d$= max degree in each variable.
88 \item[R1CS-to-CCS parameters] $n=n,~ m=m,~ N=N,~ l=l,~ t=3,~ q=2,~ d=2$, $M=\{A,B,C\}$, $S=\{\{0,~1\},~ \{2\}\}$, $c=\{1,-1\}$
89\end{description}
90
91The CCS relation check:
92$$\sum_{i=0}^{q-1} c_i \cdot \bigcirc_{j \in S_i} M_j \cdot z ==0$$
93
94where $z=(w, 1, x) \in \mathbb{F}^n$.
95
96In our R1CS-to-CCS parameters is equivalent to
97
98\begin{align*}
99 &c_0 \cdot ( (M_0 z) \circ (M_1 z) ) + c_1 \cdot (M_2 z) ==0\\
100 \Longrightarrow &1 \cdot ( (A z) \circ (B z) ) + (-1) \cdot (C z) ==0\\
101 \Longrightarrow &( (A z) \circ (B z) ) - (C z) ==0
102\end{align*}
103
104which is equivalent to the R1CS relation: $Az \circ Bz == Cz$
105
106An example of the conversion from R1CS to CCS implemented in SageMath can be found at\\
107\href{https://github.com/arnaucube/math/blob/master/r1cs-ccs.sage}{https://github.com/arnaucube/math/blob/master/r1cs-ccs.sage}.
108
109Similar relations between Plonkish and AIR arithmetizations to CCS are shown in the CCS paper \cite{cryptoeprint:2023/552}, but for now with the R1CS we have enough to see the CCS generalization idea and to use it for the HyperNova scheme.
110
111\subsection{Committed CCS}
112$R_{CCCS}$ instance: $(C, \mathsf{x})$, where $C$ is a commitment to a multilinear polynomial in $s'-1$ variables.
113
114Sat if:
115\begin{enumerate}[i.]
116 \item $\text{Commit}(pp, \widetilde{w}) = C$
117 \item $\sum_{i=1}^q c_i \cdot \left( \prod_{j \in S_i} \left( \sum_{y \in \{0,1\}^{\log m}} \widetilde{M}_j(x, y) \cdot \widetilde{z}(y) \right) \right)$\\
118 where $\widetilde{z}(y) = \widetilde{(w, 1, \mathsf{x})}(x) ~\forall x \in \{0, 1\}^{s'}$
119\end{enumerate}
120
121
122\subsection{Linearized Committed CCS}
123$R_{LCCCS}$ instance: $(C, u, \mathsf{x}, r, v_1, \ldots, v_t)$, where $C$ is a commitment to a multilinear polynomial in $s'-1$ variables, and $u \in \mathbb{F},~ \mathsf{x} \in \mathbb{F}^l,~ r \in \mathbb{F}^s,~ v_i \in \mathbb{F} ~\forall i \in [t]$.
124
125Sat if:
126\begin{enumerate}[i.]
127 \item $\text{Commit}(pp, \widetilde{w}) = C$
128 \item $\forall i \in [t],~ v_i = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_i(r, y) \cdot \widetilde{z}(y)$\\
129 where $\widetilde{z}(y) = \widetilde{(w, u, \mathsf{x})}(x) ~\forall x \in \{0, 1\}^{s'}$
130\end{enumerate}
131
132
133\section{Multifolding Scheme for CCS}
134Recall sum-check protocol notation: \underline{$C \leftarrow \langle P, V(r) \rangle (g, l, d, T)$} means
135$$T=\sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_l \in \{0,1\}} g(x_1, x_2, \ldots, x_l)$$
136where $g$ is a $l$-variate polynomial, with degree at most $d$ in each variable, and $T$ is the claimed value.
137
138\vspace{1cm}
139
140Let $s= \log m,~ s'= \log n$.
141
142\begin{enumerate}
143 \item $V \rightarrow P: \gamma \in^R \mathbb{F},~ \beta \in^R \mathbb{F}^s$
144 \item $V: r_x' \in^R \mathbb{F}^s$
145 \item $V \leftrightarrow P$: sum-check protocol:
146 $$c \leftarrow \langle P, V(r_x') \rangle (g, s, d+1, \underbrace{\sum_{j \in [t]} \gamma^j \cdot v_j}_\text{T})$$
147 (in fact, $T=(\sum_{j \in [t]} \gamma^j \cdot v_j) \underbrace{+ \gamma^{t+1} \cdot Q(x)}_{=0}) = \sum_{j \in [t]} \gamma^j \cdot v_j$)\\
148 where:
149 \begin{align*}
150 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}\\
151 \text{for LCCCS:}~ L_j(x) &:= \widetilde{eq}(r_x, x) \cdot \left(
152 \underbrace{\sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)}_\text{this is the check from LCCCS}
153 \right)\\
154 \text{for CCCS:}~ Q(x) := &\widetilde{eq}(\beta, x) \cdot \left(
155 \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{this is the check from CCCS}
156 \right)
157 \end{align*}
158 Notice that
159 $$v_j= \sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(r, y) \cdot \widetilde{z}(y) = \sum_{x\in \{0,1\}^s} L_j(x)$$
160 \item $P \rightarrow V$: $\left( (\sigma_1, \ldots, \sigma_t), (\theta_1, \ldots, \theta_t) \right)$, where $\forall j \in [t]$,
161 $$\sigma_j = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
162 $$\theta_j = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_2(y)$$
163 where $\sigma_j,~\theta_j$ are the checks from LCCCS and CCCS respectively with $x=r_x'$.
164 \item V: $e_1 \leftarrow \widetilde{eq}(r_x, r_x')$, $e_2 \leftarrow \widetilde{eq}(\beta, r_x')$\\
165 check:
166 $$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)$$
167 which should be equivalent to the $g(x)$ computed by $V,P$ in the sum-check protocol.
168 \item $V \rightarrow P: \rho \in^R \mathbb{F}$
169 \item $V, P$: output the folded LCCCS instance $(C', u', \mathsf{x}', r_x', v_1', \ldots, v_t')$, where $\forall i \in [t]$:
170 \begin{align*}
171 C' &\leftarrow C_1 + \rho \cdot C_2\\
172 u' &\leftarrow u + \rho \cdot 1\\
173 \mathsf{x}' &\leftarrow \mathsf{x}_1 + \rho \cdot \mathsf{x}_2\\
174 v_i' &\leftarrow \sigma_i + \rho \cdot \theta_i
175 \end{align*}
176 \item $P$: output folded witness and the folded $r_w'$ (random value used for the witness commitment $C$):
177 \begin{align*}
178 \widetilde{w}' &\leftarrow \widetilde{w}_1 + \rho \cdot \widetilde{w}_2\\
179 r_w' &\leftarrow r_{w_1} + \rho \cdot r_{w_2}
180 \end{align*}
181\end{enumerate}
182
183
184\vspace{1cm}
185Multifolding flow:
186\begin{center}
187 \begin{sequencediagram}
188 \newinst[1]{p}{Prover}
189 \newinst[3]{v}{Verifier}
190
191 \bloodymess[1]{v}{$\gamma,~\beta,~r_x'$}{p}{L}{
192 \shortstack{
193 $\gamma \in \mathbb{F},~ \beta \in \mathbb{F}^s$\\
194 $r_x' \in \mathbb{F}^s$
195 }
196 }{}
197 \bloodymess[1]{p}{$c,~ \pi_{SC}$}{v}{R}{sum-check prove}{sum-check verify}
198 \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}
199 \bloodymess[1]{v}{$\rho$}{p}{L}{$\rho \in^R \mathbb{F}$}{}
200 \callself[0]{p}{fold LCCCS instance}{p}
201 \prelevel
202 \callself[0]{v}{fold LCCCS instance}{v}
203 \callself[0]{p}{fold $\widetilde{w}$}{p}
204 \end{sequencediagram}
205\end{center}
206
207\vspace{1cm}
208
209Now, to see the verifier check from step 5, observe that in LCCCS, since $\widetilde{w}$ satisfies,
210\begin{align*}
211 v_j &= \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x, y) \cdot \widetilde{z}_1(y)\\
212 &= \sum_{x \in \{0,1\}^s}
213 \underbrace{
214 \widetilde{eq}(r_x, x) \cdot \left( \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y) \right)
215 }_{L_j(x)}\\
216 &= \sum_{x \in \{0,1\}^s} L_j(x)
217\end{align*}
218
219Observe also that in CCCS, since $\widetilde{w}$ satisfies,
220$$
2210=\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)}_{q(x)}
222$$
223
224we have that
225$$
226G(X) = \sum_{x \in \{0,1\}^s} eq(X, x) \cdot q(x)
227$$
228is multilinear, and can be seen as a Lagrange polynomial where coefficients are evaluations of $q(x)$ on the hypercube.
229
230For an honest prover, all these coefficients are zero, thus $G(X)$ must necessarily be the zero polynomial. Thus $G(\beta)=0$ for $\beta \in^R \mathbb{F}^s$.
231\begin{align*}
232 % 0&=\sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(\beta, y) \cdot \widetilde{z}_2(y) \right)\\
233 0&=G(\beta) = \sum_{x \in \{0,1\}^s} eq(\beta, x) \cdot q(x)\\
234 &= \sum_{x \in \{0,1\}^s}
235 \underbrace{\widetilde{eq}(\beta , x) \cdot
236 \overbrace{
237 \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)
238 }^{q(x)}
239 }_{Q(x)}\\
240 &= \sum_{x \in \{0,1\}^s} Q(x)
241\end{align*}
242
243\framebox{\begin{minipage}{4.3 in}
244\begin{footnotesize}
245
246\textbf{Note}: notice that this past equation is related to Spartan paper \cite{cryptoeprint:2019/550}, lemmas 4.2 and 4.3, where instead of
247
248$$q(x) = \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)$$
249
250for our R1CS example, we can restrict it to just $M_0,M_1,M_2$, which would be
251
252$$=\left( \sum_{y \in \{0,1\}^s} \widetilde{M_0}(x, y) \cdot \widetilde{z}(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} \widetilde{M_1}(x, y) \cdot \widetilde{z}(y) \right) - \sum_{y \in \{0,1\}^s} \widetilde{M_2}(x, y) \cdot \widetilde{z}(y)$$
253
254and we can see that $q(x)$ is the same equation $\widetilde{F}_{io}(x)$ that we had in Spartan:
255
256$$
257\widetilde{F}_{io}(x)=\left( \sum_{y \in \{0,1\}^s} \widetilde{A}(x, y) \cdot \widetilde{z}(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} \widetilde{B}(x, y) \cdot \widetilde{z}(y) \right) - \sum_{y \in \{0,1\}^s} \widetilde{C}(x, y) \cdot \widetilde{z}(y)
258$$
259
260where
261$$Q_{io}(t) = \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t,x)=0$$
262and V checks $Q_{io}(\tau)=0$ for $\tau \in^R \mathbb{F}^s$, which in HyperNova is $G(\beta)=0$ for $\beta \in^R \mathbb{F}^s$.
263
264$Q_{io}(\cdot)$ is a zero-polynomial ($G(\cdot)$ in HyperNova), it evaluates to zero for all points in its domain iff $\widetilde{F}_{io}(\cdot)$ evaluates to zero at all points in the $s$-dimensional boolean hypercube.
265\begin{align*}
266 \text{Spartan} &\longleftrightarrow \text{HyperNova}\\
267 \tau &\longleftrightarrow \beta\\
268 \widetilde{F}_{io}(x) &\longleftrightarrow q(x)\\
269 Q_{io}(\tau) &\longleftrightarrow G(\beta)
270\end{align*}
271
272So, in HyperNova
273$$0 = \sum_{x \in \{0,1\}^s} Q(x) = \sum_{x \in \{0,1\}^s} \widetilde{eq}(\beta,x) \cdot q(x)$$
274
275\end{footnotesize}
276\end{minipage}}
277
278\vspace{1cm}
279
280Comming back to HyperNova equations, we can now see that
281
282\begin{align*}
283 c &= g(r_x')\\
284 &= \left( \sum_{j \in [t]} \gamma^j \cdot L_j(r_x') \right) + \gamma^{t+1} \cdot Q(r_x')\\
285 &= \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)}
286\end{align*}
287
288where $e_1 = \widetilde{eq}(r_x, r_x')$ and $e_2=\widetilde{eq}(\beta, r_x')$.
289
290Which is the check that $V$ performs at step $5$.
291
292\subsection{Multifolding for multiple instances}
293The multifolding of multiple LCCCS \& CCCS instances is not shown in the HyperNova paper, but Srinath Setty gave an overview in the PSE HyperNova presentation. This section unfolds it.
294
295We're going to do this example with parameters \textcolor{orange}{LCCCS: $\mu = 2$}, \textcolor{cyan}{CCCS: $\nu = 2$}, which means that we have 2 LCCCS instances and 2 CCCS instances.
296
297Assume we have 4 $z$ vectors, $z_1,~ \textcolor{orange}{z_2}$ for the two LCCCS instances, and $z_3,~ \textcolor{cyan}{z_4}$ for the two CCCS instances, where $z_1,~z_3$ are the vectors that we already had in the example with $\mu=1,\nu=1$, and $z_2,~z_4$ are the extra ones that we're adding now.
298
299In \emph{step 3} of the multifolding with more than one LCCCS and more than one CCCS instances, we have:
300
301\begin{align*}
302 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)
303+ \gamma^{2t+1} \cdot Q_1(x) + \textcolor{cyan}{\gamma^{2t+2} \cdot Q_2(x)} \\
304 &L_{1,j}(x) := \widetilde{eq}(r_{1,x}, x) \cdot \left(
305 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)
306\right)\\
307 &\textcolor{orange}{L_{2,j}(x)} := \widetilde{eq}(\textcolor{orange}{r_{2,x}}, x) \cdot \left(
308 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}
309\right)\\
310 &Q_1(x) := \widetilde{eq}(\beta, x) \cdot \left(
311\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)\\
312 &\textcolor{cyan}{Q_2(x)} := \widetilde{eq}(\textcolor{cyan}{\beta'}, x) \cdot \left(
313 \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)
314\end{align*}
315
316\framebox{\begin{minipage}{4.3 in}
317A generic definition of $g(x)$ for $\mu>1~\nu>1$, would be
318
319$$
320g(x) := \left( \sum_{i \in [\mu]} \left( \sum_{j \in [t]} \gamma^{i \cdot t+j} \cdot L_{i,j}(x) \right) \right)
321+ \left( \sum_{i \in [\nu]} \gamma^{\mu \cdot t + i} \cdot Q_i(x) \right)
322$$
323\end{minipage}}
324
325Recall, the original $g(x)$ definition was
326$$\textcolor{gray}{g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) + \gamma^{t+1} \cdot Q(x)}$$
327
328
329
330\vspace{0.5cm}
331In \emph{step 4}, $P \rightarrow V$:
332$(\{\sigma_{1,j}\}, \textcolor{orange}{\{\sigma_{2,j}\}}, \{\theta_{1,j}\}, \textcolor{cyan}{\{\theta_{2,j}\}}),~ \text{where} ~\forall j \in [t]$,
333
334$$\sigma_{1,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
335$$\textcolor{orange}{\sigma_{2,j}} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}$$
336$$\theta_{1,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_3(y)$$
337$$\textcolor{cyan}{\theta_{2,j}} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{cyan}{\widetilde{z}_4(y)}$$
338
339\framebox{\begin{minipage}{4.3 in}
340 so in a generic way,\\
341$P \rightarrow V$:
342$(\{\sigma_{i,j}\}, \{\theta_{k,j}\}),~ \text{where} ~\forall~ j \in [t],~ \forall~ i \in [\mu],~ \forall~ k \in [\nu]$
343where
344$$\sigma_{i,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_i(y)$$
345$$\theta_{k,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_{\mu+k}(y)$$
346\end{minipage}}
347
348\vspace{1cm}
349
350And in \emph{step 5}, $V$ checks
351
352% TODO check orange gamma^j...
353\begin{align*}
354 c &= \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_{1,j}
355~\textcolor{orange}{+ \gamma^{t+j} \cdot e_1 \cdot \sigma_{2,j}}\right)\\
356 &+ \gamma^{2t+1} \cdot e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)
357 + \textcolor{cyan}{\gamma^{2t+2} \cdot e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)}
358\end{align*}
359
360where
361% TODO check e_4
362$e_1 \leftarrow \widetilde{eq}(r_{1,x}, r_x'),~ e_2 \leftarrow \widetilde{eq}(r_{2,x}, r_x')$, $e_3 \leftarrow \widetilde{eq}(\beta, r_x'),~ e_4 \leftarrow \widetilde{eq}(\beta', r_x')$ (note: wip, pending check for $\beta, \beta'$ used in step 3).
363
364\vspace{0.5cm}
365
366\framebox{\begin{minipage}{4.3 in}
367A generic definition of the check would be
368$$
369c = \sum_{i \in [\mu]} \left(\sum_{j \in [t]} \gamma^{i \cdot t + j} \cdot e_i \cdot \sigma_{i,j} \right) \\
370+ \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)
371$$
372\end{minipage}}
373
374where the original check was\\
375$\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)}$
376
377% TODO
378% Pending questions:
379% - \beta & \beta' can be the same? or related somehow like \beta'=\beta^2 ?
380
381\vspace{0.5cm}
382
383And for the \emph{step 7},
384\begin{align*}
385 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 \\
386 u' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot u_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot 1\\
387 \mathsf{x}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot \mathsf{x}_i\\
388 v_i' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot \sigma_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot \theta_i\\
389\end{align*}
390
391and \emph{step 8},
392\begin{align*}
393 \widetilde{w}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i\cdot \widetilde{w}_i\\
394 r_w' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot r_{w_i}\\
395\end{align*}
396
397
398Note that over all the multifolding for $\mu >1$ and $\nu>1$, we can easily parallelize most of the computation.
399
400
401\vspace{2cm}
402
403%%%%%% APPENDIX
404\appendix
405\section{Appendix: Some details}
406This appendix contains some notes on things that don't specifically appear in the paper, but that would be needed in a practical implementation of the scheme.
407
408\subsection{Matrix and Vector to Sparse Multilinear Extension}
409
410Let $M \in \mathbb{F}^{m \times n}$ be a matrix. We want to compute its MLE
411$$\widetilde{M}(x_1, \ldots, x_l) = \sum_{e \in \{0, 1 \}^l} M(e) \cdot \widetilde{eq}(x, e)$$
412
413We can view the matrix $M \in \mathbb{F}^{m \times n}$ as a function with the following signature:
414$$M(\cdot): \{0,1\}^s \times \{0,1\}^{s'} \rightarrow \mathbb{F}$$
415where $s = \lceil \log m \rceil,~ s' = \lceil \log n \rceil$.
416
417An entry in $M$ can be accessed with a $(s+s')$-bit identifier.
418
419eg.:
420$$
421M = \begin{pmatrix}
4221 & 2 & 3\\
4234 & 5 & 6\\
424\end{pmatrix}
425\in \mathbb{F}^{3 \times 2}
426$$
427
428$m = 3,~ n = 2,~~~ s = \lceil \log 3 \rceil = 2,~ s' = \lceil \log 2 \rceil = 1$
429
430So, $M(x, y) = x$, where $x \in \{0,1\}^s,~ y \in \{0,1\}^{s'},~ x \in \mathbb{F}$
431
432$$
433M = \begin{pmatrix}
434M(00,0) & M(01,0) & M(10,0)\\
435M(00,1) & M(01,1) & M(10,1)\\
436\end{pmatrix}
437\in \mathbb{F}^{3 \times 2}
438$$
439
440This logic can be defined as follows:
441
442\begin{algorithm}[H]
443\caption{Generating a Sparse Multilinear Polynomial from a matrix}
444\begin{algorithmic}
445 \State set empty vector $v \in (\text{index:}~ \mathbb{Z}, x: \mathbb{F}^{s \times s'})$
446 \For {$i$ to $m$}
447 \For {$j$ to $n$}
448 \If {$M_{i,j} \neq 0$}
449 \State $v.\text{append}( \{ \text{index}: i \cdot n + j,~ x: M_{i,j} \} )$
450 \EndIf
451 \EndFor
452 \EndFor
453 \State return $v$ \Comment {$v$ represents the evaluations of the polynomial}
454\end{algorithmic}
455\end{algorithm}
456
457Once we have the polynomial, its MLE comes from
458$$\widetilde{M}(x_1, \ldots, x_{s+s'}) = \sum_{e \in \{0,1\}^{s+s'}} M(e) \cdot \widetilde{eq}(x, e)$$
459
460$$M(X) \in \mathbb{F}[X_1, \ldots, X_s]$$
461
462\paragraph{Multilinear extensions of vectors}
463Given a vector $u \in \mathbb{F}^m$, the polynomial $\widetilde{u}$ is the MLE of $u$, and is obtained by viewing $u$ as a function mapping ($s=\log m$)
464$$u(x): \{0,1\}^s \rightarrow \mathbb{F}$$
465$\widetilde{u}(x, e)$ is the multilinear extension of the function $u(x)$
466$$\widetilde{u}(x_1, \ldots, x_s) = \sum_{e \in \{0,1\}^s} u(e) \cdot \widetilde{eq}(x, e)$$
467
468\bibliography{paper-notes.bib}
469\bibliographystyle{unsrt}
470
471\end{document}