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
209Recall that we are folding 2 instances:
210\begin{itemize}
211 \item[] LCCCS: $(C, u, \textcolor{orange}{x_1}, \textcolor{magenta}{r_x}, \textcolor{orange}{v_1, \ldots, v_t})$
212 \item[] CCCS: $(C, \textcolor{cyan}{x_2})$
213\end{itemize}
214
215Now, to see the verifier check from step 5, observe that in LCCCS, since $\widetilde{w}$ satisfies,
216\begin{align*}
217 \textcolor{orange}{L_j(x)} &:= \widetilde{eq}(\textcolor{magenta}{r_x}, x) \cdot \left(
218 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{orange}{\widetilde{z}_1(y)}
219 \right)\\
220 &\textcolor{orange}{v_j}= \sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(\textcolor{magenta}{r_x}, y) \cdot \textcolor{orange}{\widetilde{z}_1(y)})\\
221 &~~=\sum_{x \in \{0,1\}^s} \widetilde{eq}(\textcolor{magenta}{r_x},y) \cdot (\sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(x,y)\cdot \textcolor{orange}{\widetilde{z}_1(y)})\\
222 &~~=\sum_{x \in \{0,1\}^s} \textcolor{orange}{L_j(x)}
223\end{align*}
224
225
226Observe also that in CCCS, since $\widetilde{w}$ satisfies,\\
227we have that
228$$
229G(X) = \sum_{x \in \{0,1\}^s} \widetilde{eq}(X, x) \cdot \textcolor{cyan}{q(x)}
230$$
231is multilinear, and can be seen as a Lagrange polynomial where coefficients are evaluations of $q(x)$ on the hypercube.
232
233\begin{align*}
234 \textcolor{cyan}{Q(x)} := &\widetilde{eq}(\textcolor{magenta}{\beta}, x) \cdot \left(
235 \overbrace{ \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}_2(y)} \right)
236 }^\textcolor{cyan}{q(x)}
237 \right)\\
2380= &\sum_{i=1}^q c_i \prod_{j\in S_i} \left( \sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(\textcolor{magenta}{\beta}, y) \cdot \textcolor{cyan}{\widetilde{z}_2(y)}\right)\\
239 =&\sum_{x \in \{0,1\}^s} \widetilde{eq}(\textcolor{magenta}{\beta}, x) \cdot \left( \sum_{i=1}^q c_i \prod_{j\in S_i} ( \sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{cyan}{\widetilde{z}_2(y)}) \right) \\
240 =&\sum_{x \in \{0,1\}^s} \textcolor{cyan}{Q(x)} = G(\textcolor{magenta}{\beta})
241\end{align*}
242
243%
244For 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$.
245
246\vspace{1cm}
247
248We can now see that
249
250$$\textcolor{orange}{\sigma_j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(\textcolor{pink}{r_x'}, y) \cdot \textcolor{orange}{\widetilde{z}_1(y)},
251~~~\textcolor{cyan}{\theta_j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(\textcolor{pink}{r_x'}, y) \cdot \textcolor{cyan}{\widetilde{z}_2(y)}$$
252$$e_1 \leftarrow \widetilde{eq}(\textcolor{magenta}{r_x}, \textcolor{pink}{r_x'}),~ e_2 \leftarrow \widetilde{eq}(\textcolor{magenta}{\beta}, \textcolor{pink}{r_x'})$$
253
254so the Verifier's check:
255\begin{align*}
256c &= \left(
257\sum_{j \in [t]} \gamma^j \cdot \underbrace{e_1 \cdot \textcolor{orange}{\sigma_j} }_\textcolor{orange}{L_j}(\textcolor{pink}{r_x'})
258\right)
259+ \gamma^{t+1} \cdot
260\underbrace{e_2 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \textcolor{cyan}{\theta_j} \right) }_\textcolor{cyan}{Q}(\textcolor{pink}{r_x'})\\
261&= \left( \sum_{j\in [t]} \gamma^j \cdot \textcolor{orange}{L_j}(\textcolor{pink}{r_x'}) \right) + \gamma^{t+1} \cdot \textcolor{cyan}{Q}(\textcolor{pink}{r_x'})\\
262&= g(\textcolor{pink}{r_x'})
263\end{align}
264$$\textcolor{gray}{(Recall,~ g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) + \gamma^{t+1} \cdot Q(x))}$$
265
266Outputted LCCCS: $(C', u', x', \textcolor{pink}{r_x'}, v_1', \ldots, v_t')$
267
268
269\framebox{\begin{minipage}{4.3 in}
270\begin{footnotesize}
271
272\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
273
274$$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)$$
275
276for our R1CS example, we can restrict it to just $M_0,M_1,M_2$, which would be
277
278$$=\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)$$
279
280and we can see that $q(x)$ is the same equation $\widetilde{F}_{io}(x)$ that we had in Spartan:
281
282$$
283\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)
284$$
285
286where
287$$Q_{io}(t) = \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t,x)=0$$
288and 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$.
289
290$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.
291\begin{align*}
292 \text{Spartan} &\longleftrightarrow \text{HyperNova}\\
293 \tau &\longleftrightarrow \beta\\
294 \widetilde{F}_{io}(x) &\longleftrightarrow q(x)\\
295 Q_{io}(\tau) &\longleftrightarrow G(\beta)
296\end{align*}
297
298So, in HyperNova
299$$0 = \sum_{x \in \{0,1\}^s} Q(x) = \sum_{x \in \{0,1\}^s} \widetilde{eq}(\beta,x) \cdot q(x)$$
300
301\end{footnotesize}
302\end{minipage}}
303
304\vspace{1cm}
305
306\subsection{Multifolding for multiple instances}
307The 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.
308
309We'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.
310
311Assume 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.
312
313In \emph{step 3} of the multifolding with more than one LCCCS and more than one CCCS instances, we have:
314
315\begin{align*}
316 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)
317+ \gamma^{2t+1} \cdot Q_1(x) + \textcolor{cyan}{\gamma^{2t+2} \cdot Q_2(x)} \\
318 &L_{1,j}(x) := \widetilde{eq}(r_{1,x}, x) \cdot \left(
319 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)
320\right)\\
321 &\textcolor{orange}{L_{2,j}(x)} := \widetilde{eq}(\textcolor{orange}{r_{2,x}}, x) \cdot \left(
322 \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}
323\right)\\
324 &Q_1(x) := \widetilde{eq}(\beta, x) \cdot \left(
325\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)\\
326 &\textcolor{cyan}{Q_2(x)} := \widetilde{eq}(\textcolor{cyan}{\beta}, x) \cdot \left(
327 \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)
328\end{align*}
329
330\framebox{\begin{minipage}{4.3 in}
331A generic definition of $g(x)$ for $\mu>1~\nu>1$, would be
332
333$$
334g(x) := \left( \sum_{i \in [\mu]} \left( \sum_{j \in [t]} \gamma^{i \cdot t+j} \cdot L_{i,j}(x) \right) \right)
335+ \left( \sum_{i \in [\nu]} \gamma^{\mu \cdot t + i} \cdot Q_i(x) \right)
336$$
337\end{minipage}}
338
339Recall, the original $g(x)$ definition was
340$$\textcolor{gray}{g(x) := \left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right) + \gamma^{t+1} \cdot Q(x)}$$
341
342
343
344\vspace{0.5cm}
345In \emph{step 4}, $P \rightarrow V$:
346$(\{\sigma_{1,j}\}, \textcolor{orange}{\{\sigma_{2,j}\}}, \{\theta_{1,j}\}, \textcolor{cyan}{\{\theta_{2,j}\}}),~ \text{where} ~\forall j \in [t]$,
347
348$$\sigma_{1,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
349$$\textcolor{orange}{\sigma_{2,j}} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{orange}{\widetilde{z}_2(y)}$$
350$$\theta_{1,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_3(y)$$
351$$\textcolor{cyan}{\theta_{2,j}} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \textcolor{cyan}{\widetilde{z}_4(y)}$$
352
353\framebox{\begin{minipage}{4.3 in}
354 so in a generic way,\\
355$P \rightarrow V$:
356$(\{\sigma_{i,j}\}, \{\theta_{k,j}\}),~ \text{where} ~\forall~ j \in [t],~ \forall~ i \in [\mu],~ \forall~ k \in [\nu]$
357where
358$$\sigma_{i,j} = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_i(y)$$
359$$\theta_{k,j} = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_{\mu+k}(y)$$
360\end{minipage}}
361
362\vspace{1cm}
363
364And in \emph{step 5}, $V$ checks
365
366\begin{align*}
367 c &= \left(\sum_{j \in [t]} \gamma^j \cdot e_1 \cdot \sigma_{1,j}
368~\textcolor{orange}{+ \gamma^{t+j} \cdot e_2 \cdot \sigma_{2,j}}\right)\\
369 &+ \gamma^{2t+1} \cdot e_3 \cdot \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \theta_j \right)
370 + \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)}
371\end{align*}
372
373where
374$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')$.
375
376\vspace{0.5cm}
377
378\framebox{\begin{minipage}{4.3 in}
379A generic definition of the check would be
380$$
381c = \sum_{i \in [\mu]} \left(\sum_{j \in [t]} \gamma^{i \cdot t + j} \cdot e_i \cdot \sigma_{i,j} \right) \\
382+ \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)
383$$
384\end{minipage}}
385
386where the original check was\\
387$\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)}$
388
389% TODO
390% Pending questions:
391% - \beta & \beta' can be the same? or related somehow like \beta'=\beta^2 ?
392
393\vspace{0.5cm}
394
395And for the \emph{step 7},
396\begin{align*}
397 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 \\
398 u' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot u_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot 1\\
399 \mathsf{x}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot \mathsf{x}_i\\
400 v_i' &\leftarrow \sum_{i \in [\mu]} \rho^i \cdot \sigma_i + \sum_{i \in [\nu]} \rho^{\mu + i-1} \cdot \theta_i\\
401\end{align*}
402
403and \emph{step 8},
404\begin{align*}
405 \widetilde{w}' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i\cdot \widetilde{w}_i\\
406 r_w' &\leftarrow \sum_{i \in [\mu+\nu]} \rho^i \cdot r_{w_i}\\
407\end{align*}
408
409
410Note that over all the multifolding for $\mu >1$ and $\nu>1$, we can easily parallelize most of the computation.
411
412
413\vspace{2cm}
414
415%%%%%% APPENDIX
416\appendix
417\section{Appendix: Some details}
418This 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.
419
420\subsection{Matrix and Vector to Sparse Multilinear Extension}
421
422Let $M \in \mathbb{F}^{m \times n}$ be a matrix. We want to compute its MLE
423$$\widetilde{M}(x_1, \ldots, x_l) = \sum_{e \in \{0, 1 \}^l} M(e) \cdot \widetilde{eq}(x, e)$$
424
425We can view the matrix $M \in \mathbb{F}^{m \times n}$ as a function with the following signature:
426$$M(\cdot): \{0,1\}^s \times \{0,1\}^{s'} \rightarrow \mathbb{F}$$
427where $s = \lceil \log m \rceil,~ s' = \lceil \log n \rceil$.
428
429An entry in $M$ can be accessed with a $(s+s')$-bit identifier.
430
431eg.:
432$$
433M = \begin{pmatrix}
4341 & 2 & 3\\
4354 & 5 & 6\\
436\end{pmatrix}
437\in \mathbb{F}^{3 \times 2}
438$$
439
440$m = 3,~ n = 2,~~~ s = \lceil \log 3 \rceil = 2,~ s' = \lceil \log 2 \rceil = 1$
441
442So, $M(x, y) = x$, where $x \in \{0,1\}^s,~ y \in \{0,1\}^{s'},~ x \in \mathbb{F}$
443
444$$
445M = \begin{pmatrix}
446M(00,0) & M(01,0) & M(10,0)\\
447M(00,1) & M(01,1) & M(10,1)\\
448\end{pmatrix}
449\in \mathbb{F}^{3 \times 2}
450$$
451
452This logic can be defined as follows:
453
454\begin{algorithm}[H]
455\caption{Generating a Sparse Multilinear Polynomial from a matrix}
456\begin{algorithmic}
457 \State set empty vector $v \in (\text{index:}~ \mathbb{Z}, x: \mathbb{F}^{s \times s'})$
458 \For {$i$ to $m$}
459 \For {$j$ to $n$}
460 \If {$M_{i,j} \neq 0$}
461 \State $v.\text{append}( \{ \text{index}: i \cdot n + j,~ x: M_{i,j} \} )$
462 \EndIf
463 \EndFor
464 \EndFor
465 \State return $v$ \Comment {$v$ represents the evaluations of the polynomial}
466\end{algorithmic}
467\end{algorithm}
468
469Once we have the polynomial, its MLE comes from
470$$\widetilde{M}(x_1, \ldots, x_{s+s'}) = \sum_{e \in \{0,1\}^{s+s'}} M(e) \cdot \widetilde{eq}(x, e)$$
471
472$$M(X) \in \mathbb{F}[X_1, \ldots, X_s]$$
473
474\paragraph{Multilinear extensions of vectors}
475Given 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$)
476$$u(x): \{0,1\}^s \rightarrow \mathbb{F}$$
477$\widetilde{u}(x, e)$ is the multilinear extension of the function $u(x)$
478$$\widetilde{u}(x_1, \ldots, x_s) = \sum_{e \in \{0,1\}^s} u(e) \cdot \widetilde{eq}(x, e)$$
479
480\bibliography{paper-notes.bib}
481\bibliographystyle{unsrt}
482
483\end{document}