1% TODO
  2% - notation: Z(X) -> t(X), q(X) -> h(X)
  3
  4
  5\documentclass{article}
  6\usepackage[utf8]{inputenc}
  7\usepackage{amsfonts}
  8\usepackage{amsthm}
  9\usepackage{amsmath}
 10\usepackage{enumerate}
 11\usepackage{hyperref}
 12\usepackage{amssymb}
 13\usepackage{tikz} % diagram
 14
 15\begin{filecontents}[overwrite]{pinocchio-groth16.bib}
 16@misc{cryptoeprint:2013/279,
 17  author = {Bryan Parno and Craig Gentry and Jon Howell and Mariana Raykova},
 18  title = {Pinocchio: Nearly Practical Verifiable Computation},
 19  howpublished = {Cryptology {ePrint} Archive, Paper 2013/279},
 20  year = {2013},
 21  url = {https://eprint.iacr.org/2013/279}
 22}
 23@misc{cryptoeprint:2016/260,
 24  author = {Jens Groth},
 25  title = {On the Size of Pairing-based Non-interactive Arguments},
 26  howpublished = {Cryptology {ePrint} Archive, Paper 2016/260},
 27  year = {2016},
 28  url = {https://eprint.iacr.org/2016/260}
 29}
 30
 31@misc{pairings,
 32  note = {\url{https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}},
 33  url = {https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}
 34}
 35\end{filecontents}
 36\nocite{*} % TODO review
 37
 38
 39\newtheorem{thm}{Theorem}[section]
 40\newtheorem{lemma}[thm]{Lemma}
 41\newtheorem{prop}[thm]{Proposition}
 42\newtheorem{cor}[thm]{Corollary}
 43\newtheorem{defn}[thm]{Definition}
 44
 45
 46\title{Pinocchio and Groth16 notes}
 47\author{arnaucube}
 48\date{2026}
 49
 50\begin{document}
 51
 52\maketitle
 53
 54\begin{abstract}
 55    Notes taken while studying the schemes Pinocchio (\cite{cryptoeprint:2013/279}) and Groth16 (\cite{cryptoeprint:2016/260}).
 56
 57    Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
 58
 59    The proofs may slightly differ from the ones from the books or papers, since I try to extend them for a deeper understanding.
 60\end{abstract}
 61
 62\tableofcontents
 63\newpage
 64
 65
 66\section{Introduction}
 67
 68% TODO.
 69% what we want to prove, how it connects with R1CS & QAP
 70
 71
 72\section{Notation}
 73
 74Let $g \in \mathbb{G}$ be the generator of the group $\mathbb{G}$, ie. $\mathbb{G}=<g>$, then denote with $[a]$ by $g^a \in \mathbb{G}$.
 75
 76\section{R1CS}
 77% TODO Add R_{R1CS} relation definition.
 78
 79Rank-One Constraint System (R1CS) is the representation of the constraints of the circuit by 3 linear combinations, where there is one constraint per operation.
 80
 81$$
 82\begin{aligned}
 83(a_{11}w_1 + a_{12}w_2 + ... + a_{1n}w_n) \cdot (b_{11}w_1 + b_{12}w_2 + ... + b_{1n}w_n)\\- (c_{11}w_1 + c_{12}w_2 + ... + c_{1n}w_n) = 0
 84\\
 85(a_{21}w_1 + a_{22}w_2 + ... + a_{2n}w_n) \cdot (b_{21}w_1 + b_{22}w_2 + ... + b_{2n}w_n)\\- (c_{21}w_1 + c_{22}w_2 + ... + c_{2n}w_n) = 0
 86\\
 87(a_{31}w_1 + a_{32}w_2 + ... + a_{3n}w_n) \cdot (b_{31}w_1 + b_{32}w_2 + ... + b_{3n}w_n)\\- (c_{31}w_1 + c_{32}w_2 + ... + c_{3n}w_n) = 0
 88\\
 89\ldots
 90\\
 91(a_{m1}w_1 + a_{m2}w_2 + ... + a_{mn}w_n) \cdot (b_{m1}w_1 + b_{m2}w_2 + ... + b_{mn}w_n)\\- (c_{m1}w_1 + c_{m2}w_2 + ... + c_{mn}w_n) = 0
 92\end{aligned}
 93$$
 94
 95Where the R1CS linear combinations can be represented by three matrices $A$, $B$ and $C$:
 96$$
 97\begin{aligned}
 98A =
 99\begin{pmatrix}
100a_{11} & a_{12} & ... & a_{1n}\\
101a_{21} & a_{22} & ... & a_{2n}\\
102a_{31} & a_{32} & ... & a_{3n}\\
103...\\
104a_{m1} & a_{m2} & ... & a_{mn}
105\end{pmatrix}
106B =
107\begin{pmatrix}
108b_{11} & b_{12} & ... & b_{1n}\\
109b_{21} & b_{22} & ... & b_{2n}\\
110b_{31} & b_{32} & ... & b_{3n}\\
111...\\
112b_{m1} & b_{m2} & ... & b_{mn}
113\end{pmatrix}
114\\
115C =
116\begin{pmatrix}
117c_{11} & c_{12} & ... & c_{1n}\\
118c_{21} & c_{22} & ... & c_{2n}\\
119c_{31} & c_{32} & ... & c_{3n}\\
120...\\
121c_{m1} & c_{m2} & ... & c_{mn}
122\end{pmatrix}
123\end{aligned}
124$$
125
126Where
127$(A, B, C) = A w \circ B w - C w = 0$
128
129The process that converts the \emph{flat constraints} into \emph{R1CS} is the following:
130
131Lets assume that we have a constraint $5 w_3 = w_1 \cdot 2 w_2$ (being $w_1$, $w_2$ and $w_3$ the signals 1, 2 and 3 respectively)). We can represent this constraint in the matrices form by:
132
133$$
134\begin{aligned}
135A =
136\begin{pmatrix}
1371 & 0 & 0 & ... & 0\\
138\end{pmatrix}
139\\
140B =
141\begin{pmatrix}
1420 & 2 & 0 & ... & 0\\
143\end{pmatrix}
144\\
145C =
146\begin{pmatrix}
1470 & 0 & 5 & ... & 0\\
148\end{pmatrix}
149\end{aligned}
150$$
151
152
153Which in the R1CS equation form would look as:
154$$
155\begin{aligned}
156(1 \cdot w_1 + 0 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) \cdot
157(0 \cdot w_1 + 2 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) -\\
158(0 \cdot w_1 + 0 \cdot w_2 + 5 \cdot w_3 + ... + 0 \cdot w_n) = 0
159\end{aligned}
160$$
161
162If we simplify the previous liniar combination we get:
163$$
164\begin{aligned}
165(1 \cdot w_1) \cdot (2 \cdot w_2) - (5 \cdot w_3) = 0
166\\
167w_1 \cdot 2w_1 - 5 w_3 = 0
168\\
1695 w_3 = w_1 \cdot 2w_1
170\end{aligned}
171$$
172Where $5 w_3 = w_1 \cdot 2w_1$ is the constraint that we wanted to represent in the R1CS format.
173
174The nice thing from R1CS is that allows us to standaridze the constraints in an equation fashion, where all the signals are involved and we 'activate' these ones that are used in each constraint.
175Since we have now the constraints in a polynomial format, we can do work with it in the polynomial way.
176
177
178\section{QAP (Quadratic Arithmetic Programs)} \label{qap}
179\subsection{QAP}
180
181Once we have the constraints of a circuit represented in \emph{R1CS}, we can do one more iteration and represent it in \emph{Quadratic Arithmetic Programs (QAP)}.
182%% TODO %%
183\emph{QAP} is a representation of the XXX in a linear combination of the \emph{R1CS}, represented by 3 polynomials $a(X)$, $b(X)$ and $c(X)$.
184The \emph{QAP} consists of the 3 polynomials $a(X)$, $b(X)$ and $c(X)$, plus a divisor polynomial $h(X) \in \mathbb{F}[X]^{<d}$.
185
186The main idea behind the \emph{QAP} is that they 'contain' all the constraints of the circuit, meaning that these polynomials need to be able to generate all the constraints.
187
188In order to 'collapse' the \emph{R1CS} polynomials into the 3 polynomials of the \emph{QAP}, we make use of \emph{polynomial interpolation}, also named \emph{Lagrange interpolation}. \emph{Lagrange interpolation} allows for a group of points, to find the smallest degree and unique polynomial that goes through all those points. It can be calculated by computing:
189
190$$L(X) = \sum_{j=0}^{n} y_j l_j(X)$$
191
192where $l_j(X)$ is:
193$$
194l_j(X) = \prod_{0\leq m \leq k ; m\neq j}
195\frac{X-x_m}{x_j - x_m}
196...
197\frac{(X-x_{j-1})}{(x_j - x_{j-1})}
198\frac{(X-x_{j+1})}{(x_j - x_{j+1})}
199...
200\frac{X-x_k}{x_j - x_k}
201$$
202
203The intuition behind the \emph{Lagrange interpolation} is quite simple. If we have two points (on a 2 dimensional plane) we can find a line that goes through both points (this can be done with a pen and a ruler on a paper), if we have 3 points we can find a curved line that goes through all the three points, if we do this through math trying to get the lowest degree curve we obtain a  2nd degree polynomial. This can be generalized using the *Lagrange interpolation*, allowing us for a group of $n$ points to find a $n-1$ degree polynomial that goes through all of them.
204
205In our case, \emph{Lagrange interpolation} is used to go from the \emph{R1CS} polynomials into the \emph{QAP} polynomials, which are defined by:
206
207$$
208\begin{aligned}
209    a(X) = (a_1(X)w_1 + a_2(X)w_2 + ... + a_n(X)w_n) = \sum_{i=1}^n a_i(X) w_i\\
210    b(X) = (b_1(X)w_1 + b_2(X)w_2 + ... + b_n(X)w_n) = \sum_{i=1}^n b_i(X) w_i\\
211    c(X) = (c_1(X)w_1 + c_2(X)w_2 + ... + c_n(X)w_n) = \sum_{i=1}^n c_i(X) w_i
212\end{aligned}
213$$
214
215The polynomials $a(X), b(X), c(X)$ are the QAP, such that
216$$a(X) \cdot b(X) = c(X)$$
217so that
218$$p(X) = a(X) \cdot b(X) - c(X) = 0$$
219
220that is,
221$$
222\begin{aligned}
223    p(X) = &(a_1(X)w_1 + a_2(X)w_2 + ... + a_n(X)w_n)\\
224	 &\cdot (b_1(X)w_1 + b_2(X)w_2 + ... + b_n(X)w_n)\\
225	 &- (c_1(X)w_1 + c_2(X)w_2 + ... + c_n(X)w_n)\\
226    = &(\sum_{i=1}^n a_i(X) w_i) \cdot (\sum_{i=1}^n b_i(X) w_i) - (\sum_{i=1}^n c_i(X) w_i) = 0
227\end{aligned}
228$$
229
230The main idea, is that $p(X)$ defines the constraints of our circuit, so that when evaluating $p(X)$ at the challenge, it will be equal to zero.
231
232
233\vspace{0.5cm}
234
235\subsection{QAP Relation} \label{qap-relation}
236
237Want to ensure that
238$$
239(\sum_{i=1}^n a_i(X) w_i) \cdot (\sum_{i=1}^n b_i(X) w_i) - (\sum_{i=1}^n c_i(X) w_i) = 0
240$$
241
242for a given witness $(w_1, \ldots, w_n) \in \mathbb{F}^n$, which we divide between public inputs and private inputs:
243\begin{align*}
244    \text{public inputs:}~~ io &= \phi = (w_1, \ldots, w_l) \in \mathbb{F}^l, \\
245    \text{private inputs:}~~ s &= (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},
246\end{align*}
247
248We denote the relation
249
250$$
251R_{QAP} =
252\left\{
253\begin{aligned}
254    &w=(1, \phi, s) \in \mathbb{F}^n ~\text{such that:}\\
255    &\phi = (w_1, \ldots, w_l) \in \mathbb{F}^l,~
256    s = (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},\\
257& (\sum_{i=0}^n a_i(X) \cdot w_i) \cdot (\sum_{i=0}^n b_i(X) \cdot w_i)
258= \sum_{i=0}^{n} c_i(X) \cdot w_i 
259~\bmod Z(X)
260\end{aligned}
261\right.
262$$
263
264where $Z(X)$ is the "zero polynomial" or "vanishing polynomial", such that
265$$Z(X)= \prod_{i=0}^d (X-x_i) \in \mathbb{F}[X]^{<d}$$
266
267Set
268$$a(X) = \sum_{i=1}^n a_i(X) w_i,~~~~ b(X) = \sum_{i=1}^n b_i(X) w_i),~~~~ c(X) = \sum_{i=1}^{n} c_i(X) w_i$$
269
270so that
271$$a(X) \cdot b(X) \equiv c(X) \bmod Z(X)$$
272
273which means that we can prove that
274$$\exists~ h(X) \in \mathbb{F}[X]^{<d}~~ \text{s.th.}~
275a(X) \cdot b(X) - c(X) = h(X) \cdot Z(X)$$
276
277
278\vspace{1.0cm}
279\section{Preliminar protocols}
280\subsection{Sigma protocol}
281
282Let $q$ be a prime, $q$ a prime divisor in $p-1$, and $g$ and element of order $q$ in $\mathbb{Z}_p^a$. Then we have $G = \langle g \rangle$.
283\\
284We assume that computationally for a given $A$ it's hard to find $a \in \mathbb{F}$ such that $A = g^a$.
285\\
286Alice wants to prove that knows the \emph{witness} $w \in \mathbb{F}$, such that the \emph{statement} $X = g^w$, without revealing $w$.
287
288\begin{enumerate}[1.]
289	\item Alice generates a random $a \in^R \mathbb{F}$, and computes $A=g^a$. And sends $A$ to Bob.
290	\item Bob generates a challenge $c \in^R \mathbb{F}$, and sends it to Alice.
291	\item Alice computes $z=a + c \cdot w$, and sends it to Bob.
292	\item Bob verifies it by checking that $g^z == X^c \cdot A$.
293\end{enumerate}
294
295We can unfold Bob's verification and see that:
296$$g^z == X^c \cdot A$$
297$$g^{a+cw} == g^{wc} g^a$$
298$$g^{a+cw} == g^{wc+a}$$
299
300Properties:
301\begin{enumerate}[i.]
302	\item \emph{correctness/completness}: if Alice know the witness for the statement, then they can create a valid proof.
303	\item \emph{soundness}: if someone does not have knowledge of the witness, can not form a valid proof (verifier will always reject).
304	\item \emph{zero knowledge}: nobody gains knowledge of anything new with the proof. prior knowledge + proof = prior knowledge
305\end{enumerate}
306
307\paragraph{Non interactive protocol:}
308With the \emph{Fiat-Shamir Heuristic}, we model a hash function as a random oracle, thus we can replace Bob's role by a hash function in order to obtain the challenge $c \in \mathbb{F}$.
309\\
310So, we replace the step 2 from the described protocol by $c = H(X || A)$ (where $H$ is a known hash function).
311
312\paragraph{What could go wrong (Simulator).}
313If the verifier (Bob) sends $c \in \mathbb{F}$, prior to the prover committed to $A$, the prover could create a proof about a public key which they don't know $w$.
314\begin{enumerate}[1.]
315	\item Bob sends $c \xleftarrow{r} \mathbb{F}$ to Alice
316	\item Alice generates $z \xleftarrow{r} \mathbb{F}$
317	\item Alice then computes $A = g^z X^{-c}$, and sends $z, A$ to Bob
318	\item Bob would check that $g^z == X^c A$ and it would pass the verification, as $g^z== X^c \cdot A \Rightarrow g^z==X^c \cdot g^z X^{-c} \Rightarrow g^z == g^z$.
319\end{enumerate}
320
321As we've seen, it's really important the order of the steps, so Alice must commit to $A$ before knowing $c$.\\
322This 'fake' proof generation is often called the \emph{simulator} and used for further constructions.
323
324\vspace{1.0cm}
325\subsection{Proof of Exponent}
326This is a protocol used for when the prover want to convince the verifier about $p(X)|t(X)$. Assume that we have $g^{\tau^i}$.
327
328The prover can compute
329\begin{align*}
330    g^{p(\tau)} &= \sum (g^{\tau^i})^{p_i}\\
331    g^{h(\tau)} &= \sum (g^{\tau^i})^{h_i}\\
332    g^{t(\tau)} &= \sum (g^{\tau^i})^{t_i}
333\end{align*}
334
335where $p_i, h_i, t_i$ are the coefficients of $p(X), h(X), t(X)$ respectively.
336
337So that the verifier can check
338$$g^{p(\tau)}=(g^{h(\tau)})^{t(\tau)}$$
339through a pairing check as
340$$e([p(\tau)], [1])=e([h(\tau)], [t(\tau)])$$
341
342Notice that this is not enough, since the prover could use a $h(X)$ such that $h(\tau)=r$, and then produce a valid proof where $g^{r \cdot t(\tau)} = (g^r)^{t(\tau)}$.
343
344The solution is to add the $\alpha$-shifted evaluation:
345
346The verifier would then check
347$$g^{p(\alpha \cdot \tau)} = (g^{p(\tau)})^\alpha$$
348$$g^{h(\alpha \cdot \tau)} = (g^{h(\tau)})^\alpha$$
349$$g^{t(\alpha \cdot \tau)} = (g^{t(\tau)})^\alpha$$
350through the pairing checks as
351$$e([p(\alpha \cdot \tau)], [1])=e([p(\tau)], [\alpha])$$
352$$e([h(\alpha \cdot \tau)], [1])=e([h(\tau)], [\alpha])$$
353$$e([t(\alpha \cdot \tau)], [1])=e([t(\tau)], [\alpha])$$
354
355
356\vspace{1.0cm}
357\subsection{Simplified QAP check protocol}
358Protocol to prove $a(X)b(X)-c(X)=0$ in order to provide intuition on what we're trying to do.
359
360\paragraph{Setup.}
361The protocol requires a secret random value, which it is encrypted over the elliptic curve group. That is, for given $g_1 \in \mathbb{G}_1$ and $g_2 \in \mathbb{G}_2$ generators of curves $\mathbb{G}_1$ and $\mathbb{G}_2$ respectively, set $[\tau]_1 = g_1^\tau$ and $[\tau]_2 =g_2^\tau$.
362
363$$\{ [\tau^i]_1 \}_0^n = ( [\tau^0]_1, [\tau^1]_1, [\tau^2]_1, \ldots, [\tau^{n-1}]_1)$$
364$$\{ [\tau^i]_2 \}_0^n = ( [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{n-1}]_2)$$
365
366\paragraph{Prover.}
367\begin{enumerate}[i.]
368    \item commit to $a(X), b(X), c(X) \in \mathbb{F}[X]$
369
370	$$cm(a) = [a(\tau)]_1 = \sum_{i=0}^{\delta a} a_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
371
372	notice that it is equal to $\sum a_i \cdot g_1^{\tau^i}$ without knowing $\tau$.
373	
374	Same is done for $b(X)$ and $c(X)$:
375	$$cm(b) = [b(\tau)]_2 = \sum_{i=0}^{\delta b} b_i \cdot [\tau^i]_2 \in \mathbb{G}_2$$
376	$$cm(c) = [c(\tau)]_1 = \sum_{i=0}^{\delta c} c_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
377
378
379	For a challenge $z \in^R \mathbb{F}$, set by the verifier, open the commitments:
380
381	$$q_a(X) = \frac{a(X) - a(z)}{X-z}$$
382
383	Since $a(X)-\underbrace{a(z)}_{=y}$ should be zero at $X-z$, so $a(X) - a(z)$ has a root at $z$, hence it is divisible by $(X-z)$, therefore,
384	$$\exists ~q_a(X) ~~\text{such that}~ a(X)-a(z) = (X-z) \cdot q_a(X)$$
385	therefore
386	$$q_a(X) = \frac{a(X)-a(z)}{X-z}$$
387
388	Same is done for $b(X)$ and $c(X)$,
389	$$q_b(X) = \frac{b(X)-b(z)}{X-z}$$
390	$$q_c(X) = \frac{c(X)-c(z)}{X-z}$$
391
392	And then, evaluate them at the encrypted $\tau$:
393	$$[q_a(\tau)]_1 = \sum_{i=0}^{\delta q_a} q_{a_i} \cdot [\tau^i]_1 \in \mathbb{G}_1$$
394	similarly for $[q_b(\tau)]_2 \in \mathbb{G}_2$ and $[q_c(\tau)]_1 \in \mathbb{G}_1$.
395
396    \item for the relation that we want to prove, $a(X) \cdot b(X) - c(X)=0$,
397	$$\exists~ q(X) \in \mathbb{F}[X] ~~\text{s.th.}~~ a(X)b(X)-c(X)=q(X) \cdot z(X)$$
398	So the prover computes
399	$$q(X) = \frac{a(X) \cdot b(X) - c(X)}{z(X)}$$
400	and it's encrypted evaluation
401	$$[q(\tau)]_1 = \sum_{i=0}^{\delta q} q_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
402\end{enumerate}
403
404\paragraph{Verifier.}
405\begin{enumerate}[i.]
406    \item verify the commitments:\\
407	The prover has sent the commitments $[a(\tau)]_1,~ [b(\tau)]_2,~ [c(\tau)]_1$, and their respective evaluations at the challenge $z \in \mathbb{F}$: $a(z), b(z), c(z) \in \mathbb{F}$; together with their respective opening proofs: $[q_a(\tau)]_1, [q_b(\tau)]_2, [q_c(\tau)]_1$
408
409	For each commitment, the verifier checks:
410	$$e([q_a(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([a(\tau)]_1 - [a(z)]_1, [1]_2)$$
411	which is a way of checking the existence of $q_a(X)$ such that $q_a(X) \cdot (X-z) = a(X) - a(z)$.
412
413	If the checks passes, it means that $q_a \in \mathbb{F}[X]$ exists, and thus $a(X) - a(z)$ is divisible ("vanishes") at $(X-z)$, hence $a(X) - a(z)$ has a root at $z$.
414
415	Same is done for $b(X)$ and $c(X)$ commitments:
416	$$e([\tau]_1 - [z]_2, [q_b(\tau)]_1) \stackrel{?}{=} e([1]_1, [b(\tau)]_1 - [b(z)]_1)$$
417	$$e([q_c(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([c(\tau)]_1 - [c(z)]_1, [1]_2)$$
418
419    \item check the $a(X) \cdot b(X) - c(X) = 0$ relation:
420	$$e([a(\tau)]_1, [b(\tau)]_2) \stackrel{?}{=} e([q(\tau)]_1, [z(\tau)]_2) \cdot e([c(s)]_1, [1]_2)$$
421	which ensures that $\exists~ q(X) \in \mathbb{F}[X] ~\text{s.th.}~ a(X) b(X) - c(X) = q(X) z(X)$.
422\end{enumerate}
423
424\section{Pinocchio}
425
426\subsection{Conceptual version}
427\emph{(this is what the paper names "Protocol 1")}
428
429Recall, from \ref{qap-relation}, 
430public inputs: $\phi = (w_1, \ldots, w_l) \in \mathbb{F}^l$, and private inputs: $s = (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1}$.
431
432\vspace{0.5cm}
433Let $[m]= \{ l+1, \ldots, n \}$.
434
435\paragraph{SRS}
436Let $\tau, \alpha, \beta_a, \beta_b, \beta_c, \gamma \in^R \mathbb{F}$ be the \emph{secret} challenges for the protocol.
437
438The \emph{proving key} will be
439% TODO align vertically:
440\begin{align*}
441    &\{ [a_i(\tau)] \}_{i \in [m]},~ \{ [b_i(\tau)] \}_{i \in [n]},~ \{ [c_i(\tau)] \}_{i \in [n]}\\
442    &\{ [\alpha \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [\alpha \cdot b_i(\tau)] \}_{i \in [n]},~ \{ [\alpha \cdot c_i(\tau)] \}_{i \in [n]}\\
443    &\{ [\beta_a \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [\beta_b \cdot b_i(\tau)] \}_{i \in [n]},~ \{ [\beta_c \cdot c_i(\tau)] \}_{i \in [n]}\\
444    &\{ [\tau^i] \}_{i \in [d]},~ \{ [\alpha \cdot \tau^i] \}_{i \in [d]}\\
445\end{align*}
446
447The \emph{verifying key} will be
448\begin{align*}
449    (&[1], [\alpha], [\gamma], [\beta_a \cdot \gamma], [\beta_b \cdot \gamma], [\beta_c \cdot \gamma], [Z(\tau)],\\
450     &\{[a_i(\tau)]\}_{i \in l}, [a_0(\tau)], [b_0(\tau)], [c_0(\tau)])
451\end{align*}
452
453\paragraph{Prover}
454Solve for $h(X)$ such that $p(X)=h(X) \cdot t(X)$, then
455
456Let
457$$a_m(X) = \sum_{i \in [m]} w_i \cdot a_i(X)$$
458
459Denote $a(X), b(X), c(X)$ as
460\begin{align*}
461    a(X) = \sum_{i \in [n]} &w_i \cdot a_i(X), ~~ b(X) = \sum_{i \in [n]} w_i \cdot b_i(X)\\
462				&c(X) = \sum_{i \in [n]} w_i \cdot c_i(X)
463\end{align*}
464
465Then the proof $\pi$ is
466\begin{align*}
467    \pi = (&[a_m(\tau)],~ [b(\tau)],~ [c(\tau)],~ [h(\tau)],~\\
468	   &[\alpha \cdot a_m(\tau)],~ [\alpha \cdot b(\tau)],~ [\alpha \cdot c(\tau)],~[\alpha \cdot h(\tau)],\\
469	   &\hspace*{2em}\text{\emph{(ie. same as first line but $\alpha$-shifted)}}\\
470	   &[ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) + \beta_c \cdot c(\tau)]
471    )
472\end{align*}
473
474Since $a(X), b(X), c(X)$ are linear equations, we can compute them in the exponent of $g$, eg.
475$$g^{a(\tau)} = \prod_{i \in n} (g^{a_i(\tau)})^{w_i}$$
476which in our notation is
477$$[a(\tau)] = \sum_{i \in n} [a_i(\tau) \cdot w_i]$$
478
479\paragraph{Verifier}
480
481First check that $\alpha, \beta$ related terms are correct:
482
483$\alpha$-terms:
484\begin{align*}
485    e([a_m(\tau)], [\alpha]) &= e([\alpha \cdot a_m(\tau)], [1])\\
486    e([b(\tau)], [\alpha]) &= e([\alpha \cdot b(\tau)], [1])\\
487    e([c(\tau)], [\alpha]) &= e([\alpha \cdot c(\tau)], [1])\\
488    e([h(\tau)], [\alpha]) &= e([\alpha \cdot h(\tau)], [1])
489\end{align*}
490
491which we can group as:
492$$\prod_{p \in \{a_m, b, c, h\}} e([p(\tau)], [\alpha]) = \prod_{p \in \{a_m, b, c, h\}} e([\alpha \cdot p(\tau)], [1])$$
493
494$\beta$-terms:
495\begin{align*}
496    e([ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) &+ \beta_c \cdot c(\tau)], [1]) =\\
497			      &e([a_m(\tau)], [\beta_a]) \cdot e([b(\tau)], [\beta_b]) \cdot e([c(\tau)], [\beta_c])
498\end{align*}
499
500This is, 8 pairings for $\alpha$ terms, and 3 pairings for the $\beta$ terms.
501
502% TODO think if put this check first, since it's the natural one, the other ones are extra to ensure alpha,beta are used correctly
503Then, computes the term representing the public inputs:
504$$g^{a_{io}} = \prod_{i \in l} (g^{a_i(\tau)})^{w_i}$$
505ie.
506$$[a_{io}] = \sum_{i \in l} [a_i(\tau) \cdot w_i]$$
507
508in order to do the final check, verifying the divisibility, and therefore the QAP relation:
509$$e([a_0(\tau) + a_{io} + a(\tau)], [b_0(\tau) + b(\tau)]) = e([c_0(\tau) + c(\tau)], [1]) \cdot e([h(\tau)], [Z(\tau)])$$
510
511\section{Groth16}
512
513\vspace{1cm}
514
515\section{Powers of tau (trusted setup)}
516\subsection{Main idea}
517% TODO. mention "SRS" concept
518
519\subsection{Participant contribution}
520In the context of SRS (Structured Reference String), the powers of tau consist of an array containing the scalar multiplication of the generator point by each power of tau, eg. $\tau^0 \cdot G,~\tau^1 \cdot G,~\tau^2 \cdot G,~\tau^3 \cdot G \ldots$
521
522For our case, we'll generate $n$ powers of tau on $\mathbb{G}_1$, and $m$ on $\mathbb{G}_2$. We will denote the combination of both $\mathbb{G}_1$ and $\mathbb{G}_2$ powers of tau by SRS.
523
524Each participant will obtain the previous-participant generated SRS, which is formed by
525
526\begin{align*}
527        \{ [\tau^0]_1, [\tau^1]_1, [\tau^2]_2, \ldots, [\tau^{n-1}]_1 \},\\
528        \{ [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{m-1}]_2 \}
529\end{align*}
530
531for simplicity, we will represent it as
532
533$$\{~[~\tau^i]_1~\}^{n-1}_{i=0},~\{~[~\tau^i]_2~\}^{m-1}_{j=0}$$
534
535
536Each participant generates their secret random tau $\tau_p$, which to avoid confusion we will denote as $p \in \mathbb{F}_r$. From it, the participant can compute $[p]_2 \in \mathbb{G}_2$.
537
538Then the participant proceeds to update the reference string (SRS), by multiplying each element by $p^i$:
539$$\{~ p^i \cdot [~ \tau^i]_1~\}^{n-1}_{i=0},~\{~ p^i \cdot [~\tau^i]_2~\}^{m-1}_{j=0}$$
540which, by the properties of scalar multiplication of a point, is equivalent to
541$$\{~ [~ (p \cdot \tau)^i]_1~\}^{n-1}_{i=0},~\{~ [~ (p \cdot \tau)^i]_2~\}^{m-1}_{j=0}$$
542and we denote $p \cdot \tau$ as $\tau'$, so we can write the previous expression as
543$$\{~[~\tau'^i]_1~\}^{n-1}_{i=0},~\{~[~\tau'^i]_2~\}^{m-1}_{j=0}$$
544
545which is
546\begin{align*}
547        \{ [(\tau \cdot p)^0]_1, [(\tau \cdot p)^1]_1, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{n-1}]_1 \},\\
548        \{ [(\tau \cdot p)^0]_2, [(\tau \cdot p)^1]_2, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{m-1}]_2 \}
549\end{align*}
550
551Notice that the contributor does not know the previous $\tau$, but can obtain $(\tau \cdot p)^i$.
552
553
554\subsection{Proof of correct computation}
555The participant will compute the proof, which consists of
556$$\pi = ([\tau']_1,~[p]_2)$$
557which is equivalent to $\pi = (\tau' \cdot G,~p \cdot H) = ((p \cdot \tau) \cdot G,~p \cdot H)$
558
559In the next section we will see how this is used to verify the contribution correct computation.
560
561
562\subsection{Contribution verification}
563This is the interesting part. We want to check that the new SRS is well computed from the previous SRS together with the new tau. We want to avoid accepting contributions that do not follow the powers of tau structure, or that contain empty elements or that do not derive from the previous SRS.
564
565Following the powers of tau structure means that
566$$\tau'^{i+1} = \tau' \cdot \tau'^i ~~\forall~i \in [1, n-1]$$
567
568And the relation between the new SRS and the previous SRS is
569$$\tau' = \tau \cdot p$$
570where $\tau$ is the secret element from the previous SRS and $p$ is the secret one from the new SRS, resulting in the combined $\tau'$.
571
572Now, we're interested into how we can check these relations in the context of the SRS elements. A new contribution can be verified as follows:
573
574\begin{enumerate}
575        \item Check that elements of the new SRS are non-empty, non-zero and in the correct prime order subgroups.
576\item Get the proof ($\pi = ([\tau']_1, [p]_2)$), and confirm that the 1st element is equal to the element in position 1 $[\tau'^1]_1$ of the new SRS (which corresponds to $\tau'$ powered to $1$).
577
578\item Check that $\tau'$ (the new SRS) is correctly related to $\tau$ (the previous SRS).
579
580    To check this, we rely on the pairing properties and we use the proof value generated by the contributor, which consists of $[p]_2$
581    $$e([\tau]_1, [p]_2) \stackrel{?}{=} e([\tau']_1, [1]_2)$$
582    
583    We can see how this holds, as $\tau' = p \cdot \tau$, and by the bilinear property of the pairing (see \cite{pairings}) we have $e(a \cdot G, b \cdot H) = e((a \cdot b) \cdot G, H)$, which in our notation is represented as
584    $$e([a]_1, [b]_2) = e([a \cdot b]_1, [1]_2)$$
585    by applying this to our case we can see that:
586    $$e([\tau]_1, [p]_2) = e([\tau \cdot p]_1, [1]_2) = e([\tau']_1, [1]_2)$$
587
588\item Check if the new SRS follows the powers of tau structure:
589    $$e([\tau'^i]_1, [\tau']_2) \stackrel{?}{=} e([\tau'^{i+1}]_1, [1]_2) ~~ \forall ~i \in [1, n-1]$$
590    $$e([\tau']_1, [\tau'^j]_2) \stackrel{?}{=} e([1]_1, [\tau'^{j+1}]_2) ~~ \forall ~i \in [1, m-1]$$
591    
592    Which, again, by the bilinarity property, we can see that
593    $$e([\tau'^i]_1, [\tau']_2) = e([\tau'^{i+1}]_1, [1]_2)$$
594    is enforcing that $\tau'^i \cdot \tau'^1 = \tau'^{i+1}$.
595    
596    And the same for
597    $$e([\tau']_1, [\tau'^j]_2) = e([1]_1, [\tau'^{j+1}]_2)$$
598    which checks that $\tau'^1 \cdot \tau'^j = \tau'^{j+1}$.
599    
600    With this check, we're ensuring that each power of tau of the SRS is consistent with the previous one.
601\end{enumerate}
602
603
604
605\bibliographystyle{unsrt}
606\bibliography{pinocchio-groth16.bib}
607
608\end{document}