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 e_1 \sigma_j + \gamma^{t+1} e_2 \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \sigma \right) \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: $\widetilde{w}' \leftarrow \widetilde{w}_1 + \rho \cdot \widetilde{w}_2$.
177\end{enumerate}
178
179
180\vspace{1cm}
181Multifolding flow:
182\begin{center}
183 \begin{sequencediagram}
184 \newinst[1]{p}{Prover}
185 \newinst[3]{v}{Verifier}
186
187 \bloodymess[1]{v}{$\gamma,~\beta,~r_x'$}{p}{L}{
188 \shortstack{
189 $\gamma \in \mathbb{F},~ \beta \in \mathbb{F}^s$\\
190 $r_x' \in \mathbb{F}^s$
191 }
192 }{}
193 \bloodymess[1]{p}{$c,~ \pi_{SC}$}{v}{R}{sum-check prove}{sum-check verify}
194 \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}
195 \bloodymess[1]{v}{$\rho$}{p}{L}{$\rho \in^R \mathbb{F}$}{}
196 \callself[0]{p}{fold LCCCS instance}{p}
197 \prelevel
198 \callself[0]{v}{fold LCCCS instance}{v}
199 \callself[0]{p}{fold $\widetilde{w}$}{p}
200 \end{sequencediagram}
201\end{center}
202
203\vspace{1cm}
204
205Now, to see the verifier check from step 5, observe that in LCCCS, since $\widetilde{w}$ satisfies,
206\begin{align*}
207 v_j &= \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x, y) \cdot \widetilde{z}_1(y)\\
208 &= \sum_{x \in \{0,1\}^s}
209 \underbrace{
210 \widetilde{eq}(r_x, x) \cdot \left( \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y) \right)
211 }_{L_j(x)}\\
212 &= \sum_{x \in \{0,1\}^s} L_j(x)
213\end{align*}
214
215Observe also that in CCCS, since $\widetilde{w}$ satisfies,
216$$
2170=\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)}
218$$
219
220we have that
221$$
222G(X) = \sum_{x \in \{0,1\}^s} eq(X, x) \cdot q(x)
223$$
224is multilinear, and can be seen as a Lagrange polynomial where coefficients are evaluations of $q(x)$ on the hypercube.
225
226For 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$.
227\begin{align*}
228 % 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)\\
229 0&=G(\beta) = \sum_{x \in \{0,1\}^s} eq(\beta, x) \cdot q(x)\\
230 &= \sum_{x \in \{0,1\}^s}
231 \underbrace{\widetilde{eq}(\beta , x) \cdot
232 \overbrace{
233 \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)
234 }^{q(x)}
235 }_{Q(x)}\\
236 &= \sum_{x \in \{0,1\}^s} Q(x)
237\end{align*}
238
239\framebox{\begin{minipage}{4.3 in}
240\begin{footnotesize}
241
242\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
243
244$$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)$$
245
246for our R1CS example, we can restrict it to just $M_0,M_1,M_2$, which would be
247
248$$=\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)$$
249
250and we can see that $q(x)$ is the same equation $\widetilde{F}_{io}(x)$ that we had in Spartan:
251
252$$
253\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)
254$$
255
256where
257$$Q_{io}(t) = \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t,x)=0$$
258and 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$.
259
260$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.
261\begin{align*}
262 \text{Spartan} &\longleftrightarrow \text{HyperNova}\\
263 \tau &\longleftrightarrow \beta\\
264 \widetilde{F}_{io}(x) &\longleftrightarrow q(x)\\
265 Q_{io}(\tau) &\longleftrightarrow G(\beta)
266\end{align*}
267
268So, in HyperNova
269$$0 = \sum_{x \in \{0,1\}^s} Q(x) = \sum_{x \in \{0,1\}^s} \widetilde{eq}(\beta,x) \cdot q(x)$$
270
271\end{footnotesize}
272\end{minipage}}
273
274\vspace{1cm}
275
276Comming back to HyperNova equations, we can now see that
277
278\begin{align*}
279 c &= g(r_x')\\
280 &= \left( \sum_{j \in [t]} \gamma^j \cdot L_j(r_x') \right) + \gamma^{t+1} \cdot Q(r_x')\\
281 &= \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)}
282\end{align*}
283
284where $e_1 = \widetilde{eq}(r_x, r_x')$ and $e_2=\widetilde{eq}(\beta, r_x')$.
285
286Which is the check that $V$ performs at step $5$.
287
288
289
290%%%%%% APPENDIX
291\appendix
292\section{Appendix: Some details}
293This 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.
294
295\subsection{Matrix and Vector to Sparse Multilinear Extension}
296
297Let $M \in \mathbb{F}^{m \times n}$ be a matrix. We want to compute its MLE
298$$\widetilde{M}(x_1, \ldots, x_l) = \sum_{e \in \{0, 1 \}^l} M(e) \cdot \widetilde{eq}(x, e)$$
299
300We can view the matrix $M \in \mathbb{F}^{m \times n}$ as a function with the following signature:
301$$M(\cdot): \{0,1\}^s \times \{0,1\}^{s'} \rightarrow \mathbb{F}$$
302where $s = \lceil \log m \rceil,~ s' = \lceil \log n \rceil$.
303
304An entry in $M$ can be accessed with a $(s+s')$-bit identifier.
305
306eg.:
307$$
308M = \begin{pmatrix}
3091 & 2 & 3\\
3104 & 5 & 6\\
311\end{pmatrix}
312\in \mathbb{F}^{3 \times 2}
313$$
314
315$m = 3,~ n = 2,~~~ s = \lceil \log 3 \rceil = 2,~ s' = \lceil \log 2 \rceil = 1$
316
317So, $M(x, y) = x$, where $x \in \{0,1\}^s,~ y \in \{0,1\}^{s'},~ x \in \mathbb{F}$
318
319$$
320M = \begin{pmatrix}
321M(00,0) & M(01,0) & M(10,0)\\
322M(00,1) & M(01,1) & M(10,1)\\
323\end{pmatrix}
324\in \mathbb{F}^{3 \times 2}
325$$
326
327This logic can be defined as follows:
328
329\begin{algorithm}[H]
330\caption{Generating a Sparse Multilinear Polynomial from a matrix}
331\begin{algorithmic}
332 \State set empty vector $v \in (\text{index:}~ \mathbb{Z}, x: \mathbb{F}^{s \times s'})$
333 \For {$i$ to $m$}
334 \For {$j$ to $n$}
335 \If {$M_{i,j} \neq 0$}
336 \State $v.\text{append}( \{ \text{index}: i \cdot n + j,~ x: M_{i,j} \} )$
337 \EndIf
338 \EndFor
339 \EndFor
340 \State return $v$ \Comment {$v$ represents the evaluations of the polynomial}
341\end{algorithmic}
342\end{algorithm}
343
344Once we have the polynomial, its MLE comes from
345$$\widetilde{M}(x_1, \ldots, x_{s+s'}) = \sum_{e \in \{0,1\}^{s+s'}} M(e) \cdot \widetilde{eq}(x, e)$$
346
347$$M(X) \in \mathbb{F}[X_1, \ldots, X_s]$$
348
349\paragraph{Multilinear extensions of vectors}
350Given 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$)
351$$u(x): \{0,1\}^s \rightarrow \mathbb{F}$$
352$\widetilde{u}(x, e)$ is the multilinear extension of the function $u(x)$
353$$\widetilde{u}(x_1, \ldots, x_s) = \sum_{e \in \{0,1\}^s} u(e) \cdot \widetilde{eq}(x, e)$$
354
355\bibliography{paper-notes.bib}
356\bibliographystyle{unsrt}
357
358\end{document}