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\begin{align*}
353 c &= \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_{1,j}
354~\textcolor{orange}{+ \gamma^{t+j} \cdot e_2 \cdot \sigma_{2,j}}\right)\\
355 &+ \gamma^{2t+1} \cdot e_3 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)
356 + \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)}
357\end{align*}
358
359where
360$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')$.
361
362\vspace{0.5cm}
363
364\framebox{\begin{minipage}{4.3 in}
365A generic definition of the check would be
366$$
367c = \sum_{i \in [\mu]} \left(\sum_{j \in [t]} \gamma^{i \cdot t + j} \cdot e_i \cdot \sigma_{i,j} \right) \\
368+ \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)
369$$
370\end{minipage}}
371
372where the original check was\\
373$\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)}$
374
375% TODO
376% Pending questions:
377% - \beta & \beta' can be the same? or related somehow like \beta'=\beta^2 ?
378
379\vspace{0.5cm}
380
381And for the \emph{step 7},
382\begin{align*}
383 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 \\
384 u' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot u_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot 1\\
385 \mathsf{x}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot \mathsf{x}_i\\
386 v_i' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot \sigma_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot \theta_i\\
387\end{align*}
388
389and \emph{step 8},
390\begin{align*}
391 \widetilde{w}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i\cdot \widetilde{w}_i\\
392 r_w' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot r_{w_i}\\
393\end{align*}
394
395
396Note that over all the multifolding for $\mu >1$ and $\nu>1$, we can easily parallelize most of the computation.
397
398
399\vspace{2cm}
400
401%%%%%% APPENDIX
402\appendix
403\section{Appendix: Some details}
404This 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.
405
406\subsection{Matrix and Vector to Sparse Multilinear Extension}
407
408Let $M \in \mathbb{F}^{m \times n}$ be a matrix. We want to compute its MLE
409$$\widetilde{M}(x_1, \ldots, x_l) = \sum_{e \in \{0, 1 \}^l} M(e) \cdot \widetilde{eq}(x, e)$$
410
411We can view the matrix $M \in \mathbb{F}^{m \times n}$ as a function with the following signature:
412$$M(\cdot): \{0,1\}^s \times \{0,1\}^{s'} \rightarrow \mathbb{F}$$
413where $s = \lceil \log m \rceil,~ s' = \lceil \log n \rceil$.
414
415An entry in $M$ can be accessed with a $(s+s')$-bit identifier.
416
417eg.:
418$$
419M = \begin{pmatrix}
4201 & 2 & 3\\
4214 & 5 & 6\\
422\end{pmatrix}
423\in \mathbb{F}^{3 \times 2}
424$$
425
426$m = 3,~ n = 2,~~~ s = \lceil \log 3 \rceil = 2,~ s' = \lceil \log 2 \rceil = 1$
427
428So, $M(x, y) = x$, where $x \in \{0,1\}^s,~ y \in \{0,1\}^{s'},~ x \in \mathbb{F}$
429
430$$
431M = \begin{pmatrix}
432M(00,0) & M(01,0) & M(10,0)\\
433M(00,1) & M(01,1) & M(10,1)\\
434\end{pmatrix}
435\in \mathbb{F}^{3 \times 2}
436$$
437
438This logic can be defined as follows:
439
440\begin{algorithm}[H]
441\caption{Generating a Sparse Multilinear Polynomial from a matrix}
442\begin{algorithmic}
443 \State set empty vector $v \in (\text{index:}~ \mathbb{Z}, x: \mathbb{F}^{s \times s'})$
444 \For {$i$ to $m$}
445 \For {$j$ to $n$}
446 \If {$M_{i,j} \neq 0$}
447 \State $v.\text{append}( \{ \text{index}: i \cdot n + j,~ x: M_{i,j} \} )$
448 \EndIf
449 \EndFor
450 \EndFor
451 \State return $v$ \Comment {$v$ represents the evaluations of the polynomial}
452\end{algorithmic}
453\end{algorithm}
454
455Once we have the polynomial, its MLE comes from
456$$\widetilde{M}(x_1, \ldots, x_{s+s'}) = \sum_{e \in \{0,1\}^{s+s'}} M(e) \cdot \widetilde{eq}(x, e)$$
457
458$$M(X) \in \mathbb{F}[X_1, \ldots, X_s]$$
459
460\paragraph{Multilinear extensions of vectors}
461Given 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$)
462$$u(x): \{0,1\}^s \rightarrow \mathbb{F}$$
463$\widetilde{u}(x, e)$ is the multilinear extension of the function $u(x)$
464$$\widetilde{u}(x_1, \ldots, x_s) = \sum_{e \in \{0,1\}^s} u(e) \cdot \widetilde{eq}(x, e)$$
465
466\bibliography{paper-notes.bib}
467\bibliographystyle{unsrt}
468
469\end{document}