1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{enumerate}
  7\usepackage{hyperref}
  8\hypersetup{
  9    colorlinks,
 10    citecolor=black,
 11    filecolor=black,
 12    linkcolor=black,
 13    urlcolor=blue
 14}
 15\usepackage{xcolor}
 16
 17% prevent warnings of underfull \hbox:
 18\usepackage{etoolbox}
 19\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 20
 21\theoremstyle{definition}
 22\newtheorem{definition}{Def}[section]
 23\newtheorem{theorem}[definition]{Thm}
 24
 25
 26\title{Paper notes}
 27\author{arnaucube}
 28\date{}
 29
 30\begin{document}
 31
 32\maketitle
 33
 34\begin{abstract}
 35	Notes taken while reading papers. Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 36
 37	The notes are not complete, don't include all the steps neither all the proofs.
 38\end{abstract}
 39
 40\tableofcontents
 41
 42\section{SnarkPack}
 43Notes taken while reading SnarkPack paper \cite{cryptoeprint:2021/529}.
 44
 45Groth16 proof aggregation.
 46
 47\begin{enumerate}[i.]
 48    \item Simple verification:\\
 49	Proof: $\pi_i = (A_i, B_i, C_i)$\\
 50	Verifier checks: $e(A_i, B_i) == e(C_i, D)$\\
 51	Where $D$ is the $CRS$.
 52    \item Batch verification:
 53	$r \in^\$ F_q$\\
 54	$r^i \cdot e(A_i, B_i) == e(C_i, D)$\\
 55	$\Longrightarrow \prod e(A_i, B_i)^{r^i} == \prod e(C_i, D)^{r^i}$\\
 56	$\Longrightarrow \prod e(A_i, B_i^{r^i}) == \prod e(C_i^{r^i}, D)$
 57    \item Snark Aggregation verification:\\
 58	$z_{AB} = \prod e(A_i, B_i^{r^i})$\\
 59	$z_C = \prod C_i^{r^i}$\\
 60	Verification: $z_{AB} == e(z_C, D)$
 61\end{enumerate}
 62
 63\section{Sonic}
 64Notes taken while reading Sonic paper \cite{cryptoeprint:2019/099}. Does not include all the steps, neither the proofs.
 65
 66\subsection{Structured Reference String}
 67$\{ \{g^{x^i}\}_{i=-d}^d, \{ g^{\alpha x^i} \}_{i=-d, i \neq 0}^d, \{ h^{x^i}, h^{\alpha x^i} \}_{i=-d}^d, e(g, h^\alpha) \}$
 68
 69\subsection{System of constraints}
 70Multiplication constraint: $a \cdot b = c$
 71
 72$Q$ linear constraints:
 73$$
 74a \cdot u_q + b \cdot v_q + c \cdot w_q = k_q
 75$$
 76
 77with $u_q, v_q, w_q \in \mathbb{F}^n$, and $k_q \in \mathbb{F}_p$.
 78
 79\vspace{0.5cm}
 80Example: $x^2 + y^2 = z$
 81
 82$$a = (x, y), \qquad b = (x, y), \qquad c = (x^2, y^2)$$
 83\begin{enumerate}[i.]
 84    \item $(x, y) \cdot (1, 0) + (x, y) \cdot (-1, 0) + (x^2, y^2) \cdot (0, 0) = 0 \longrightarrow x - x = 0$
 85    \item $(x, y) \cdot (0, 1) + (x, y) \cdot (0, -1) + (x^2, y^2) \cdot (0, 0) = 0 \longrightarrow y - y = 0$
 86    \item $(x, y) \cdot (0, 0) + (x, y) \cdot (0, 0) + (x^2, y^2) \cdot (1, 1) = z \longrightarrow x^2 + y^2 = z$
 87\end{enumerate}
 88
 89So,
 90$$u_1 = (1, 0) \quad v_1=(-1, 0) \quad w_1=(0, 0) \quad k_1=0$$
 91$$u_2 = (0, 1) \quad v_2=(0, -1) \quad w_2=(0, 0) \quad k_2=0$$
 92$$u_3 = (0, 0) \quad v_3=(0, 0) \quad w_3=(1, 1) \quad k_2=z$$
 93
 94\vspace{1cm}
 95
 96Compress n multiplication constraints into an equation in formal indeterminate $Y$:
 97$$\sum_{i=1}^n (a_i b_i - c_i) \cdot Y^i = 0$$
 98encode into negative exponents of $Y$:
 99$$\sum_{i=1}^n (a_i b_i - c_i) \cdot Y^-i = 0$$
100
101Also, compress the $Q$ linear constraints, scaling by $Y^n$ to preserve linear independence:
102$$
103\sum_{q=1}^Q (a \cdot u_q + b \cdot v_q + c \cdot w_q - k_q) \cdot Y^{q+n} = 0
104$$
105
106Polys:
107
108\begin{align}
109\nonumber & u_i(Y) = \sum_{q=1}^Q Y^{q+n} \cdot u_{q, i}\\
110\nonumber & v_i(Y) = \sum_{q=1}^Q Y^{q+n} \cdot v_{q, i}\\
111\nonumber & w_i(Y) = -Y^i - Y^{-1} + \sum_{q=1}^Q Y^{q+n} \cdot w_{q, i}\\
112\nonumber & k(Y) = \sum_{q=1}^Q Y^{q+n} \cdot k_q
113\end{align}
114
115Combine the multiplicative and linear constraints to:
116
117\begin{align}
118\nonumber & a \cdot u(Y) + b \cdot v(Y) + c \cdot w(Y)
119+ \sum_{i=1}^n a_i b_i (Y^i + Y^{-i}) - k(Y) = 0
120\end{align}
121
122where $a \cdot u(Y) + b \cdot v(Y) + c \cdot w(Y)$ is embeded into the constant term of the polynomial $t(X, Y)$.
123
124
125Define $r(X, Y)$ s.t. $r(X, Y) = r(XY, 1)$.
126
127$$\Longrightarrow r(X, Y) = \sum_{i=1}^n (a_i X^i Y^i + b_i X^{-i} Y^{-i} + c_i X^{-i-n} Y^{-i-n})$$
128
129$$s(X, Y) = \sum_{i=1}^n (u_i(Y) X^{-i} + v_i(Y) X^i + w_i(Y) X^{i+n})$$
130
131$$r'(X, Y) = r(X, Y) + s(X, Y)$$
132$$t(X, Y) = r(X, Y) + r'(X, Y) - k(Y)$$
133
134The coefficient of $X^0$ in $t(X, Y)$ is the left-hand side of the equation.
135
136Sonic demonstrates that the constant term of $t(X, Y)$ is zero, thus demonstrating that our constraint system is satisfied.
137
138
139\subsubsection{The basic Sonic protocol}
140
141\begin{enumerate}[1.]
142    \item Prover constructs $r(X, Y)$ using their hidden witness
143    \item Prover commits to $r(X, 1)$, setting the maximum degree to n
144    \item Verifier sends random challenge $y$
145    \item Prover commits to $t(X, y)$. The commitment scheme ensures that $t(X, y)$ has no constant term.
146    \item Verifier sends random challenge $z$
147    \item Prover opens commitments to $r(z, 1), r(z, y), t(z, y)$
148    \item Verifier calculates $r'(z, y)$, and checks that
149	$$r(z, y) \cdot r'(z, y) - k(y) == t(z, y)$$
150\end{enumerate}
151
152Steps $3$ and $5$ can be made non-interactive by the Fiat-Shamir transformation.
153
154\subsubsection{Polynomial Commitment Scheme}
155Sonic uses an adaptation of KZG \cite{kzg-tmp}, want:
156
157\begin{enumerate}[i.]
158    \item \emph{evaluation binding}, i.e. given a commitment $F$, an adversary cannot open F to two different evaluations $v_1$ and $v_2$
159    \item \emph{bounded polynomial extractable}, i.e. any algebraic adversary that opens a commitment $F$ knows an opening $f(X)$ with powers $-d \leq i \leq max, i \neq 0$.
160\end{enumerate}
161
162\vspace{0.5cm}
163PC scheme (adaptation of KZG):
164
165\begin{enumerate}[i.]
166    \item Commit(info, $f(X)$) $\longrightarrow F$:
167	$$F = g^{\alpha \cdot x^{d-max}} \cdot f(x)$$
168    \item Open(info, $F$, $z$, $f(x)$) $\longrightarrow (f(z), W)$:
169	$$w(X) = \frac{f(X) - f(z)}{X-z}$$
170	$$W = g^{w(x)}$$
171    \item Verify(info, $F$, $z$, $(v, W)$) $\longrightarrow 0/1$:\\
172	Check:
173	$$e(W, h^{\alpha \cdot x}) \cdot
174	e(g^v W^{-z}, h^{\alpha})
175	== e(F, h^{x^{-d+max}})$$
176\end{enumerate}
177
178\subsection{Succint signatures of correct computation}
179Signature of correct computation to ensure that an element $s=s(z, y)$ for a known polynomial
180$$s(X, Y) = \sum_{i, j = -d}^d s_{i, j} \cdot X^i \cdot Y^i$$
181
182Use the structure of $s(X, Y)$ to prove its correct calculation using a \emph{permutation argument} $\longrightarrow$ \emph{grand-product argument} inspired by Bayer and Groth, and Bootle et al.
183
184Restrict to constraint systems where $s(X, Y)$ can be expressed as the sum of $M$ polynomials. Where $j-th$ poly is of the form:
185$$
186\Psi_j(X, Y) =
187    \sum_{i=1}^n \psi_{j, \sigma_{j, i}}
188    \cdot X^i \cdot Y^{\sigma_{j, i}}
189$$
190
191where $\sigma_j$ is the fixed polynomial permutation, and $\phi_{j, i} \in \mathbb{F}$ are the coefficients.
192
193\vspace{1cm}
194\framebox{WIP}
195\vspace{1cm}
196
197\section{BLS signatures}
198Notes taken while reading about BLS signatures \cite{bls-sig-eth2}.
199
200\paragraph{Key generation}
201$sk \in \mathbb{Z}_q$, $pk = [sk] \cdot g_1$, where $g_1 \in G_1$, and is the generator.
202
203\paragraph{Signature}
204$$\sigma = [sk] \cdot H(m)$$
205where $H$ is a function that maps to a point in $G_2$. So $H(m), \sigma \in G_2$.
206
207\paragraph{Verification}
208$$e(g_1, \sigma) == e(pk, H(m))$$
209
210Unfold:
211$$e(pk, H(m)) = e([sk] \cdot g_1, H(m) = e(g_1, H(m))^{sk} = e(g_1, [sk] \cdot H(m)) = e(g_1, \sigma))$$
212
213\paragraph{Aggregation}
214Signatures aggregation:
215$$\sigma_{aggr} = \sigma_1 + \sigma_2 + \ldots + \sigma_n$$
216where $\sigma_{aggr} \in G_2$, and an aggregated signatures is indistinguishible from a non-aggregated signature.
217
218\paragraph{Public keys aggregation}
219$$pk_{aggr} = pk_1 + pk_2 + \ldots + pk_n$$
220where $pk_{aggr} \in G_1$, and an aggregated public keys is indistinguishible from a non-aggregated public key.
221
222
223\paragraph{Verification of aggregated signatures}
224Identical to verification of a normal signature as long as we use the same corresponding aggregated public key:
225$$e(g_1, \sigma_{aggr})==e(pk_{aggr}, H(m))$$
226
227Unfold:
228$$\fbox{e(pk_{aggr}, H(m))}= e(pk_1 + pk_2 + \ldots + pk_n, H(m)) =$$
229$$=e([sk_1] \cdot g_1 + [sk_2] \cdot g_1 + \ldots + [sk_n] \cdot g_1, H(m))=$$
230$$=e([sk_1 + sk_2 + \ldots + sk_n] \cdot g_1, H(m))=$$
231$$=e(g_1, H(m))^{(sk_1 + sk_2 + \ldots + sk_n)}=$$
232$$=e(g_1, [sk_1 + sk_2 + \ldots + sk_n] \cdot H(m))=$$
233$$=e(g_1, [sk_1] \cdot H(m) + [sk_2] \cdot H(m) + \ldots + [sk_n] \cdot H(m))=$$
234$$=e(g_1, \sigma_1 + \sigma_2 + \ldots + \sigma_n)= \fbox{e(g_1, \sigma_{aggr})}$$
235
236
237
238
239
240\section{modified IPA (from Halo)}
241Notes taken while reading about the modified Inner Product Argument (IPA) from the Halo paper \cite{cryptoeprint:2019/1021}.
242
243\subsection{Notation}
244\begin{description}
245    \item[Scalar mul] $[a]G$, where $a$ is a scalar and $G \in \mathbb{G}$
246    \item[Inner product] $<\overrightarrow{a}, \overrightarrow{b}> = a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$
247    \item[Multiscalar mul] $<\overrightarrow{a}, \overrightarrow{b}> = [a_0] G_0 + [a_1] G_1 + \ldots [a_{n-1}] G_{n-1}$
248\end{description}
249
250
251\subsection{Transparent setup}
252$\overrightarrow{G} \in^r \mathbb{G}^d$, $H \in^r \mathbb{G}$
253
254Prover wants to commit to $p(x)=a_0$
255\subsection{Protocol}
256Prover:
257$$P=<\overrightarrow{a}, \overrightarrow{G}> + [r]H$$
258$$v=<\overrightarrow{a}, \{1, x, x^2, \ldots, x^{d-1} \} >$$
259
260where $\{1, x, x^2, \ldots, x^{d-1} \} = \overrightarrow{b}$.
261
262We can see that computing $v$ is the equivalent to evaluating $p(x)$ at $x$ ($p(x)=v$).
263
264We will prove:
265\begin{enumerate}[i.]
266    \item polynomial $p(X) = \sum a_i X^i$\\
267	$p(x) = v$ (that $p(X)$ evaluates $x$ to $v$).
268    \item $deg(p(X)) \leq d-1$
269\end{enumerate}
270
271
272Both parties know $P$, point $x$ and claimed evaluation $v$. For $U \in^r \mathbb{G}$,
273
274$$P' = P + [v] U = <\overrightarrow{a}, G> + [r]H + [v] U$$
275
276Now, for $k$ rounds ($d=2^k$, from $j=k$ to $j=1$):
277\begin{itemize}
278    \item random blinding factors: $l_j, r_j \in \mathbb{F}_p$
279    \item
280	$$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U$$
281	$$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U$$
282    \item Verifier sends random challenge $u_j \in \mathbb{I}$
283    \item Prover computes the halved vectors for next round:
284	$$\overrightarrow{a} \leftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j$$
285	$$\overrightarrow{b} \leftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j$$
286	$$\overrightarrow{G} \leftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j$$
287\end{itemize}
288
289After final round, $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ are each of length 1.
290
291Verifier can compute
292$$G = \overrightarrow{G}_0 = < \overrightarrow{s}, \overrightarrow{G} >$$
293and $$b = \overrightarrow{b}_0 = < \overrightarrow{s}, \overrightarrow{b} >$$
294where $\overrightarrow{s}$ is the binary counting structure:
295
296\begin{align*}
297    &s = (u_1^{-1} ~ u_2^{-1} \cdots ~u_k^{-1},\\
298    &~~~~~~u_1 ~~~ u_2^{-1} ~\cdots ~u_k^{-1},\\
299    &~~~~~~u_1^{-1} ~~ u_2 ~~\cdots ~u_k^{-1},\\
300    &~~~~~~~~~~~~~~\vdots\\
301    &~~~~~~u_1 ~~~~ u_2 ~~\cdots ~u_k)
302\end{align*}
303
304
305And verifier checks:
306$$[a]G + [r'] H + [ab] U == P' + \sum_{j=1}^k ( [u_j^2] L_j + [u_j^{-2}] R_j)$$
307
308where the synthetic blinding factor $r'$ is $r' = r + \sum_{j=1}^k (l_j u_j^2 + r_j u_j^{-2})$.
309
310\vspace{1cm}
311
312Unfold:
313
314$$
315\textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}
316==
317\textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})
318$$
319
320\begin{align*}
321&Right~side = \textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})\\
322&= \textcolor{blue}{< \overrightarrow{a}, \overrightarrow{G}> + [r] H + [v] U}\\
323&+ \sum_{j=1}^k (\\
324&\textcolor{violet}{[u_j^2] \cdot <\overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [<\overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U}\\
325&\textcolor{orange}{+ [u_j^{-2}] \cdot <\overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [<\overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U}
326)
327\end{align*}
328
329\begin{align*}
330&Left~side = \textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}\\
331& = \textcolor{brown}{< \overrightarrow{a}, \overrightarrow{G} >}\\
332&+ \textcolor{cyan}{[r + \sum_{j=1}^k (l_j \cdot u_j^2 + r_j u_j^{-2})] \cdot H}\\
333&+ \textcolor{magenta}{< \overrightarrow{a}, \overrightarrow{b} > U}
334\end{align*}
335
336
337\bibliography{paper-notes.bib}
338\bibliographystyle{unsrt}
339
340\end{document}