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
 16% prevent warnings of underfull \hbox:
 17\usepackage{etoolbox}
 18\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 19
 20\theoremstyle{definition}
 21\newtheorem{definition}{Def}[section]
 22\newtheorem{theorem}[definition]{Thm}
 23
 24
 25\title{Paper notes}
 26\author{arnaucube}
 27\date{}
 28
 29\begin{document}
 30
 31\maketitle
 32
 33\begin{abstract}
 34	Notes taken while reading papers. Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 35
 36	The notes are not complete, don't include all the steps neither all the proofs.
 37\end{abstract}
 38
 39\tableofcontents
 40
 41\section{SnarkPack}
 42Notes taken while reading SnarkPack paper \cite{cryptoeprint:2021/529}.
 43
 44Groth16 proof aggregation.
 45
 46\begin{enumerate}[i.]
 47    \item Simple verification:\\
 48	Proof: $\pi_i = (A_i, B_i, C_i)$\\
 49	Verifier checks: $e(A_i, B_i) == e(C_i, D)$\\
 50	Where $D$ is the $CRS$.
 51    \item Batch verification:
 52	$r \in^\$ F_q$\\
 53	$r^i \cdot e(A_i, B_i) == e(C_i, D)$\\
 54	$\Longrightarrow \prod e(A_i, B_i)^{r^i} == \prod e(C_i, D)^{r^i}$\\
 55	$\Longrightarrow \prod e(A_i, B_i^{r^i}) == \prod e(C_i^{r^i}, D)$
 56    \item Snark Aggregation verification:\\
 57	$z_{AB} = \prod e(A_i, B_i^{r^i})$\\
 58	$z_C = \prod C_i^{r^i}$\\
 59	Verification: $z_{AB} == e(z_C, D)$
 60\end{enumerate}
 61
 62\section{Sonic}
 63Notes taken while reading Sonic paper \cite{cryptoeprint:2019/099}. Does not include all the steps, neither the proofs.
 64
 65\subsection{Structured Reference String}
 66$\{ \{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) \}$
 67
 68\subsection{System of constraints}
 69Multiplication constraint: $a \cdot b = c$
 70
 71$Q$ linear constraints:
 72$$
 73a \cdot u_q + b \cdot v_q + c \cdot w_q = k_q
 74$$
 75
 76with $u_q, v_q, w_q \in \mathbb{F}^n$, and $k_q \in \mathbb{F}_p$.
 77
 78\vspace{0.5cm}
 79Example: $x^2 + y^2 = z$
 80
 81$$a = (x, y), \qquad b = (x, y), \qquad c = (x^2, y^2)$$
 82\begin{enumerate}[i.]
 83    \item $(x, y) \cdot (1, 0) + (x, y) \cdot (-1, 0) + (x^2, y^2) \cdot (0, 0) = 0 \longrightarrow x - x = 0$
 84    \item $(x, y) \cdot (0, 1) + (x, y) \cdot (0, -1) + (x^2, y^2) \cdot (0, 0) = 0 \longrightarrow y - y = 0$
 85    \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$
 86\end{enumerate}
 87
 88So,
 89$$u_1 = (1, 0) \quad v_1=(-1, 0) \quad w_1=(0, 0) \quad k_1=0$$
 90$$u_2 = (0, 1) \quad v_2=(0, -1) \quad w_2=(0, 0) \quad k_2=0$$
 91$$u_3 = (0, 0) \quad v_3=(0, 0) \quad w_3=(1, 1) \quad k_2=z$$
 92
 93\vspace{1cm}
 94
 95Compress n multiplication constraints into an equation in formal indeterminate $Y$:
 96$$\sum_{i=1}^n (a_i b_i - c_i) \cdot Y^i = 0$$
 97encode into negative exponents of $Y$:
 98$$\sum_{i=1}^n (a_i b_i - c_i) \cdot Y^-i = 0$$
 99
100Also, compress the $Q$ linear constraints, scaling by $Y^n$ to preserve linear independence:
101$$
102\sum_{q=1}^Q (a \cdot u_q + b \cdot v_q + c \cdot w_q - k_q) \cdot Y^{q+n} = 0
103$$
104
105Polys:
106
107\begin{align}
108\nonumber & u_i(Y) = \sum_{q=1}^Q Y^{q+n} \cdot u_{q, i}\\
109\nonumber & v_i(Y) = \sum_{q=1}^Q Y^{q+n} \cdot v_{q, i}\\
110\nonumber & w_i(Y) = -Y^i - Y^{-1} + \sum_{q=1}^Q Y^{q+n} \cdot w_{q, i}\\
111\nonumber & k(Y) = \sum_{q=1}^Q Y^{q+n} \cdot k_q
112\end{align}
113
114Combine the multiplicative and linear constraints to:
115
116\begin{align}
117\nonumber & a \cdot u(Y) + b \cdot v(Y) + c \cdot w(Y)
118+ \sum_{i=1}^n a_i b_i (Y^i + Y^{-i}) - k(Y) = 0
119\end{align}
120
121where $a \cdot u(Y) + b \cdot v(Y) + c \cdot w(Y)$ is embeded into the constant term of the polynomial $t(X, Y)$.
122
123
124Define $r(X, Y)$ s.t. $r(X, Y) = r(XY, 1)$.
125
126$$\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})$$
127
128$$s(X, Y) = \sum_{i=1}^n (u_i(Y) X^{-i} + v_i(Y) X^i + w_i(Y) X^{i+n})$$
129
130$$r'(X, Y) = r(X, Y) + s(X, Y)$$
131$$t(X, Y) = r(X, Y) + r'(X, Y) - k(Y)$$
132
133The coefficient of $X^0$ in $t(X, Y)$ is the left-hand side of the equation.
134
135Sonic demonstrates that the constant term of $t(X, Y)$ is zero, thus demonstrating that our constraint system is satisfied.
136
137
138\subsubsection{The basic Sonic protocol}
139
140\begin{enumerate}[1.]
141    \item Prover constructs $r(X, Y)$ using their hidden witness
142    \item Prover commits to $r(X, 1)$, setting the maximum degree to n
143    \item Verifier sends random challenge $y$
144    \item Prover commits to $t(X, y)$. The commitment scheme ensures that $t(X, y)$ has no constant term.
145    \item Verifier sends random challenge $z$
146    \item Prover opens commitments to $r(z, 1), r(z, y), t(z, y)$
147    \item Verifier calculates $r'(z, y)$, and checks that
148	$$r(z, y) \cdot r'(z, y) - k(y) == t(z, y)$$
149\end{enumerate}
150
151Steps $3$ and $5$ can be made non-interactive by the Fiat-Shamir transformation.
152
153\subsubsection{Polynomial Commitment Scheme}
154Sonic uses an adaptation of KZG \cite{kzg-tmp}, want:
155
156\begin{enumerate}[i.]
157    \item \emph{evaluation binding}, i.e. given a commitment $F$, an adversary cannot open F to two different evaluations $v_1$ and $v_2$
158    \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$.
159\end{enumerate}
160
161\vspace{0.5cm}
162PC scheme (adaptation of KZG):
163
164\begin{enumerate}[i.]
165    \item Commit(info, $f(X)$) $\longrightarrow F$:
166	$$F = g^{\alpha \cdot x^{d-max}} \cdot f(x)$$
167    \item Open(info, $F$, $z$, $f(x)$) $\longrightarrow (f(z), W)$:
168	$$w(X) = \frac{f(X) - f(z)}{X-z}$$
169	$$W = g^{w(x)}$$
170    \item Verify(info, $F$, $z$, $(v, W)$) $\longrightarrow 0/1$:\\
171	Check:
172	$$e(W, h^{\alpha \cdot x}) \cdot
173	e(g^v W^{-z}, h^{\alpha})
174	== e(F, h^{x^{-d+max}})$$
175\end{enumerate}
176
177\subsection{Succint signatures of correct computation}
178Signature of correct computation to ensure that an element $s=s(z, y)$ for a known polynomial
179$$s(X, Y) = \sum_{i, j = -d}^d s_{i, j} \cdot X^i \cdot Y^i$$
180
181Use 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.
182
183Restrict to constraint systems where $s(X, Y)$ can be expressed as the sum of $M$ polynomials. Where $j-th$ poly is of the form:
184$$
185\Psi_j(X, Y) =
186    \sum_{i=1}^n \psi_{j, \sigma_{j, i}}
187    \cdot X^i \cdot Y^{\sigma_{j, i}}
188$$
189
190where $\sigma_j$ is the fixed polynomial permutation, and $\phi_{j, i} \in \mathbb{F}$ are the coefficients.
191
192\vspace{1cm}
193\framebox{WIP}
194\vspace{1cm}
195
196
197\bibliography{paper-notes.bib}
198\bibliographystyle{unsrt}
199
200\end{document}