1% TODO
  2% - notation: Z(X) -> t(X), q(X) -> h(X)
  3% - on pairings, add suffix []_1, []_2
  4
  5
  6\documentclass{article}
  7\usepackage[utf8]{inputenc}
  8\usepackage{amsfonts}
  9\usepackage{amsthm}
 10\usepackage{amsmath}
 11\usepackage{enumerate}
 12\usepackage{hyperref}
 13\usepackage{amssymb}
 14\usepackage{tikz} % diagram
 15
 16\begin{filecontents}[overwrite]{pinocchio-groth16.bib}
 17@misc{cryptoeprint:2013/279,
 18  author = {Bryan Parno and Craig Gentry and Jon Howell and Mariana Raykova},
 19  title = {Pinocchio: Nearly Practical Verifiable Computation},
 20  howpublished = {Cryptology {ePrint} Archive, Paper 2013/279},
 21  year = {2013},
 22  url = {https://eprint.iacr.org/2013/279}
 23}
 24@misc{cryptoeprint:2016/260,
 25  author = {Jens Groth},
 26  title = {On the Size of Pairing-based Non-interactive Arguments},
 27  howpublished = {Cryptology {ePrint} Archive, Paper 2016/260},
 28  year = {2016},
 29  url = {https://eprint.iacr.org/2016/260}
 30}
 31
 32@misc{pairings,
 33  note = {\url{https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}},
 34  url = {https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}
 35}
 36\end{filecontents}
 37\nocite{*} % TODO review
 38
 39
 40\newtheorem{thm}{Theorem}[section]
 41\newtheorem{lemma}[thm]{Lemma}
 42\newtheorem{prop}[thm]{Proposition}
 43\newtheorem{cor}[thm]{Corollary}
 44\newtheorem{defn}[thm]{Definition}
 45
 46
 47\title{Pinocchio and Groth16 notes}
 48\author{arnaucube}
 49\date{2026}
 50
 51\begin{document}
 52
 53\maketitle
 54
 55\begin{abstract}
 56    Notes taken while studying the schemes Pinocchio (\cite{cryptoeprint:2013/279}) and Groth16 (\cite{cryptoeprint:2016/260}).
 57
 58    Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
 59
 60    The proofs may slightly differ from the ones from the books or papers, since I try to extend them for a deeper understanding.
 61\end{abstract}
 62
 63\tableofcontents
 64\newpage
 65
 66
 67\section{Introduction}
 68
 69% TODO.
 70% what we want to prove, how it connects with R1CS & QAP
 71
 72
 73\section{Notation}
 74
 75Let $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}$.
 76
 77\section{R1CS}
 78% TODO Add R_{R1CS} relation definition.
 79
 80Rank-One Constraint System (R1CS) is the representation of the constraints of the circuit by 3 linear combinations, where there is one constraint per operation.
 81
 82$$
 83\begin{aligned}
 84(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
 85\\
 86(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
 87\\
 88(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
 89\\
 90\ldots
 91\\
 92(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
 93\end{aligned}
 94$$
 95
 96Where the R1CS linear combinations can be represented by three matrices $A$, $B$ and $C$:
 97$$
 98\begin{aligned}
 99A =
100\begin{pmatrix}
101a_{11} & a_{12} & ... & a_{1n}\\
102a_{21} & a_{22} & ... & a_{2n}\\
103a_{31} & a_{32} & ... & a_{3n}\\
104...\\
105a_{m1} & a_{m2} & ... & a_{mn}
106\end{pmatrix}
107B =
108\begin{pmatrix}
109b_{11} & b_{12} & ... & b_{1n}\\
110b_{21} & b_{22} & ... & b_{2n}\\
111b_{31} & b_{32} & ... & b_{3n}\\
112...\\
113b_{m1} & b_{m2} & ... & b_{mn}
114\end{pmatrix}
115\\
116C =
117\begin{pmatrix}
118c_{11} & c_{12} & ... & c_{1n}\\
119c_{21} & c_{22} & ... & c_{2n}\\
120c_{31} & c_{32} & ... & c_{3n}\\
121...\\
122c_{m1} & c_{m2} & ... & c_{mn}
123\end{pmatrix}
124\end{aligned}
125$$
126
127Where
128$(A, B, C) = A w \circ B w - C w = 0$
129
130The process that converts the \emph{flat constraints} into \emph{R1CS} is the following:
131
132Lets 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:
133
134$$
135\begin{aligned}
136A =
137\begin{pmatrix}
1381 & 0 & 0 & ... & 0\\
139\end{pmatrix}
140\\
141B =
142\begin{pmatrix}
1430 & 2 & 0 & ... & 0\\
144\end{pmatrix}
145\\
146C =
147\begin{pmatrix}
1480 & 0 & 5 & ... & 0\\
149\end{pmatrix}
150\end{aligned}
151$$
152
153
154Which in the R1CS equation form would look as:
155$$
156\begin{aligned}
157(1 \cdot w_1 + 0 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) \cdot
158(0 \cdot w_1 + 2 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) -\\
159(0 \cdot w_1 + 0 \cdot w_2 + 5 \cdot w_3 + ... + 0 \cdot w_n) = 0
160\end{aligned}
161$$
162
163If we simplify the previous liniar combination we get:
164$$
165\begin{aligned}
166(1 \cdot w_1) \cdot (2 \cdot w_2) - (5 \cdot w_3) = 0
167\\
168w_1 \cdot 2w_1 - 5 w_3 = 0
169\\
1705 w_3 = w_1 \cdot 2w_1
171\end{aligned}
172$$
173Where $5 w_3 = w_1 \cdot 2w_1$ is the constraint that we wanted to represent in the R1CS format.
174
175The 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.
176Since we have now the constraints in a polynomial format, we can do work with it in the polynomial way.
177
178
179\section{QAP (Quadratic Arithmetic Programs)} \label{qap}
180\subsection{QAP}
181
182Once 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)}.
183%% TODO %%
184\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)$.
185The \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}$.
186
187The 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.
188
189In 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:
190
191$$L(X) = \sum_{j=0}^{n} y_j l_j(X)$$
192
193where $l_j(X)$ is:
194$$
195l_j(X) = \prod_{0\leq m \leq k ; m\neq j}
196\frac{X-x_m}{x_j - x_m}
197...
198\frac{(X-x_{j-1})}{(x_j - x_{j-1})}
199\frac{(X-x_{j+1})}{(x_j - x_{j+1})}
200...
201\frac{X-x_k}{x_j - x_k}
202$$
203
204The 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.
205
206In our case, \emph{Lagrange interpolation} is used to go from the \emph{R1CS} polynomials into the \emph{QAP} polynomials, which are defined by:
207
208$$
209\begin{aligned}
210    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\\
211    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\\
212    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
213\end{aligned}
214$$
215
216The polynomials $a(X), b(X), c(X)$ are the QAP, such that
217$$a(X) \cdot b(X) = c(X)$$
218so that
219$$p(X) = a(X) \cdot b(X) - c(X) = 0$$
220
221that is,
222$$
223\begin{aligned}
224    p(X) = &(a_1(X)w_1 + a_2(X)w_2 + ... + a_n(X)w_n)\\
225	 &\cdot (b_1(X)w_1 + b_2(X)w_2 + ... + b_n(X)w_n)\\
226	 &- (c_1(X)w_1 + c_2(X)w_2 + ... + c_n(X)w_n)\\
227    = &(\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
228\end{aligned}
229$$
230
231The 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.
232
233
234\vspace{0.5cm}
235
236\subsection{QAP Relation} \label{qap-relation}
237
238Want to ensure that
239$$
240(\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
241$$
242
243for a given witness $(w_1, \ldots, w_n) \in \mathbb{F}^n$, which we divide between public inputs and private inputs:
244\begin{align*}
245    \text{public inputs:}~~ io &= \phi = (w_1, \ldots, w_l) \in \mathbb{F}^l, \\
246    \text{private inputs:}~~ s &= (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},
247\end{align*}
248
249We denote the relation
250
251$$
252R_{QAP} =
253\left\{
254\begin{aligned}
255    &w=(1, \phi, s) \in \mathbb{F}^n ~\text{such that:}\\
256    &\phi = (w_1, \ldots, w_l) \in \mathbb{F}^l,~
257    s = (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},\\
258& (\sum_{i=0}^n a_i(X) \cdot w_i) \cdot (\sum_{i=0}^n b_i(X) \cdot w_i)
259= \sum_{i=0}^{n} c_i(X) \cdot w_i 
260~\bmod Z(X)
261\end{aligned}
262\right.
263$$
264
265where $Z(X)$ is the "zero polynomial" or "vanishing polynomial", such that
266$$Z(X)= \prod_{i=0}^d (X-x_i) \in \mathbb{F}[X]^{<d}$$
267
268Set
269$$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$$
270
271so that
272$$a(X) \cdot b(X) \equiv c(X) \bmod Z(X)$$
273
274which means that we can prove that
275$$\exists~ h(X) \in \mathbb{F}[X]^{<d}~~ \text{s.th.}~
276a(X) \cdot b(X) - c(X) = h(X) \cdot Z(X)$$
277
278
279\vspace{1.0cm}
280\section{Preliminar protocols}
281\subsection{Sigma protocol}
282
283Let $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$.
284\\
285We assume that computationally for a given $A$ it's hard to find $a \in \mathbb{F}$ such that $A = g^a$.
286\\
287Alice wants to prove that knows the \emph{witness} $w \in \mathbb{F}$, such that the \emph{statement} $X = g^w$, without revealing $w$.
288
289\begin{enumerate}[1.]
290	\item Alice generates a random $a \in^R \mathbb{F}$, and computes $A=g^a$. And sends $A$ to Bob.
291	\item Bob generates a challenge $c \in^R \mathbb{F}$, and sends it to Alice.
292	\item Alice computes $z=a + c \cdot w$, and sends it to Bob.
293	\item Bob verifies it by checking that $g^z == X^c \cdot A$.
294\end{enumerate}
295
296We can unfold Bob's verification and see that:
297$$g^z == X^c \cdot A$$
298$$g^{a+cw} == g^{wc} g^a$$
299$$g^{a+cw} == g^{wc+a}$$
300
301Properties:
302\begin{enumerate}[i.]
303	\item \emph{correctness/completness}: if Alice know the witness for the statement, then they can create a valid proof.
304	\item \emph{soundness}: if someone does not have knowledge of the witness, can not form a valid proof (verifier will always reject).
305	\item \emph{zero knowledge}: nobody gains knowledge of anything new with the proof. prior knowledge + proof = prior knowledge
306\end{enumerate}
307
308\paragraph{Non interactive protocol:}
309With 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}$.
310\\
311So, we replace the step 2 from the described protocol by $c = H(X || A)$ (where $H$ is a known hash function).
312
313\paragraph{What could go wrong (Simulator).}
314If 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$.
315\begin{enumerate}[1.]
316	\item Bob sends $c \xleftarrow{r} \mathbb{F}$ to Alice
317	\item Alice generates $z \xleftarrow{r} \mathbb{F}$
318	\item Alice then computes $A = g^z X^{-c}$, and sends $z, A$ to Bob
319	\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$.
320\end{enumerate}
321
322As we've seen, it's really important the order of the steps, so Alice must commit to $A$ before knowing $c$.\\
323This 'fake' proof generation is often called the \emph{simulator} and used for further constructions.
324
325\vspace{1.0cm}
326\subsection{Proof of Exponent}
327This 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}$.
328
329The prover can compute
330\begin{align*}
331    g^{p(\tau)} &= \sum (g^{\tau^i})^{p_i}\\
332    g^{h(\tau)} &= \sum (g^{\tau^i})^{h_i}\\
333    g^{t(\tau)} &= \sum (g^{\tau^i})^{t_i}
334\end{align*}
335
336where $p_i, h_i, t_i$ are the coefficients of $p(X), h(X), t(X)$ respectively.
337
338So that the verifier can check
339$$g^{p(\tau)}=(g^{h(\tau)})^{t(\tau)}$$
340through a pairing check as
341$$e([p(\tau)], [1])=e([h(\tau)], [t(\tau)])$$
342
343Notice 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)}$.
344
345The solution is to add the $\alpha$-shifted evaluation:
346
347The verifier would then check
348$$g^{p(\alpha \cdot \tau)} = (g^{p(\tau)})^\alpha$$
349$$g^{h(\alpha \cdot \tau)} = (g^{h(\tau)})^\alpha$$
350$$g^{t(\alpha \cdot \tau)} = (g^{t(\tau)})^\alpha$$
351through the pairing checks as
352$$e([p(\alpha \cdot \tau)], [1])=e([p(\tau)], [\alpha])$$
353$$e([h(\alpha \cdot \tau)], [1])=e([h(\tau)], [\alpha])$$
354$$e([t(\alpha \cdot \tau)], [1])=e([t(\tau)], [\alpha])$$
355
356\vspace{0.5cm}
357% TODO adding zk
358
359\vspace{1.0cm}
360\subsection{Simplified QAP check protocol}
361Protocol to prove $a(X)b(X)-c(X)=0$ in order to provide intuition on what we're trying to do.
362
363\paragraph{Setup.}
364The 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$.
365
366$$\{ [\tau^i]_1 \}_0^n = ( [\tau^0]_1, [\tau^1]_1, [\tau^2]_1, \ldots, [\tau^{n-1}]_1)$$
367$$\{ [\tau^i]_2 \}_0^n = ( [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{n-1}]_2)$$
368
369\paragraph{Prover.}
370\begin{enumerate}[i.]
371    \item commit to $a(X), b(X), c(X) \in \mathbb{F}[X]$
372
373	$$cm(a) = [a(\tau)]_1 = \sum_{i=0}^{\delta a} a_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
374
375	notice that it is equal to $\sum a_i \cdot g_1^{\tau^i}$ without knowing $\tau$.
376	
377	Same is done for $b(X)$ and $c(X)$:
378	$$cm(b) = [b(\tau)]_2 = \sum_{i=0}^{\delta b} b_i \cdot [\tau^i]_2 \in \mathbb{G}_2$$
379	$$cm(c) = [c(\tau)]_1 = \sum_{i=0}^{\delta c} c_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
380
381
382	For a challenge $z \in^R \mathbb{F}$, set by the verifier, open the commitments:
383
384	$$q_a(X) = \frac{a(X) - a(z)}{X-z}$$
385
386	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,
387	$$\exists ~q_a(X) ~~\text{such that}~ a(X)-a(z) = (X-z) \cdot q_a(X)$$
388	therefore
389	$$q_a(X) = \frac{a(X)-a(z)}{X-z}$$
390
391	Same is done for $b(X)$ and $c(X)$,
392	$$q_b(X) = \frac{b(X)-b(z)}{X-z}$$
393	$$q_c(X) = \frac{c(X)-c(z)}{X-z}$$
394
395	And then, evaluate them at the encrypted $\tau$:
396	$$[q_a(\tau)]_1 = \sum_{i=0}^{\delta q_a} q_{a_i} \cdot [\tau^i]_1 \in \mathbb{G}_1$$
397	similarly for $[q_b(\tau)]_2 \in \mathbb{G}_2$ and $[q_c(\tau)]_1 \in \mathbb{G}_1$.
398
399    \item for the relation that we want to prove, $a(X) \cdot b(X) - c(X)=0$,
400	$$\exists~ q(X) \in \mathbb{F}[X] ~~\text{s.th.}~~ a(X)b(X)-c(X)=q(X) \cdot z(X)$$
401	So the prover computes
402	$$q(X) = \frac{a(X) \cdot b(X) - c(X)}{z(X)}$$
403	and it's encrypted evaluation
404	$$[q(\tau)]_1 = \sum_{i=0}^{\delta q} q_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
405\end{enumerate}
406
407\paragraph{Verifier.}
408\begin{enumerate}[i.]
409    \item verify the commitments:\\
410	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$
411
412	For each commitment, the verifier checks:
413	$$e([q_a(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([a(\tau)]_1 - [a(z)]_1, [1]_2)$$
414	which is a way of checking the existence of $q_a(X)$ such that $q_a(X) \cdot (X-z) = a(X) - a(z)$.
415
416	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$.
417
418	Same is done for $b(X)$ and $c(X)$ commitments:
419	$$e([\tau]_1 - [z]_2, [q_b(\tau)]_1) \stackrel{?}{=} e([1]_1, [b(\tau)]_1 - [b(z)]_1)$$
420	$$e([q_c(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([c(\tau)]_1 - [c(z)]_1, [1]_2)$$
421
422    \item check the $a(X) \cdot b(X) - c(X) = 0$ relation:
423	$$e([a(\tau)]_1, [b(\tau)]_2) \stackrel{?}{=} e([q(\tau)]_1, [z(\tau)]_2) \cdot e([c(s)]_1, [1]_2)$$
424	which ensures that $\exists~ q(X) \in \mathbb{F}[X] ~\text{s.th.}~ a(X) b(X) - c(X) = q(X) z(X)$.
425\end{enumerate}
426
427\section{Pinocchio}
428
429The next couple of subsections provide first a description of the conceptual protocol, and then the optimized version of it, which reduces prover costs and key sizes.
430
431\subsection{Conceptual version}
432\emph{(this is what the paper names "Protocol 1")}
433
434Recall, from \ref{qap-relation}, 
435public 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}$.
436
437\vspace{0.3cm}
438Let $[m]= \{ l+1, \ldots, n \}$.
439
440\paragraph{SRS}
441Let $\tau, \alpha, \beta_a, \beta_b, \beta_c, \gamma \in^R \mathbb{F}$ be the \emph{secret} challenges for the protocol.
442
443The \emph{proving key} will be
444% TODO align vertically:
445\begin{align*}
446    &\{ [a_i(\tau)] \}_{i \in [m]},~ \{ [b_i(\tau)] \}_{i \in [n]},~ \{ [c_i(\tau)] \}_{i \in [n]}\\
447    &\{ [\alpha \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [\alpha \cdot b_i(\tau)] \}_{i \in [n]},~ \{ [\alpha \cdot c_i(\tau)] \}_{i \in [n]}\\
448    &\{ [\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]}\\
449    &\{ [\tau^i] \}_{i \in [d]},~ \{ [\alpha \cdot \tau^i] \}_{i \in [d]}\\
450\end{align*}
451
452The \emph{verifying key} will be
453\begin{align*}
454    (&[1], [\alpha], [\gamma], [\beta_a \cdot \gamma], [\beta_b \cdot \gamma], [\beta_c \cdot \gamma], [Z(\tau)],\\
455     &\{[a_i(\tau)]\}_{i \in l}, [a_0(\tau)], [b_0(\tau)], [c_0(\tau)])
456\end{align*}
457
458\paragraph{Prover}
459Solve for $h(X)$ such that $p(X)=h(X) \cdot t(X)$, then
460
461Let
462$$a_m(X) = \sum_{i \in [m]} w_i \cdot a_i(X)$$
463
464Denote $a(X), b(X), c(X)$ as
465\begin{align*}
466    a(X) = \sum_{i \in [n]} &w_i \cdot a_i(X), ~~ b(X) = \sum_{i \in [n]} w_i \cdot b_i(X)\\
467				&c(X) = \sum_{i \in [n]} w_i \cdot c_i(X)
468\end{align*}
469
470Then the proof $\pi$ is
471\begin{align*}
472    \pi = (&[a_m(\tau)],~ [b(\tau)],~ [c(\tau)],~ [h(\tau)],~\\
473	   &[\alpha \cdot a_m(\tau)],~ [\alpha \cdot b(\tau)],~ [\alpha \cdot c(\tau)],~[\alpha \cdot h(\tau)],\\
474	   &\hspace*{2em}\text{\emph{(ie. same as first line but $\alpha$-shifted)}}\\
475	   &[ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) + \beta_c \cdot c(\tau)]
476    )
477\end{align*}
478
479Since $a(X), b(X), c(X)$ are linear equations, we can compute them in the exponent of $g$, eg.
480$$g^{a(\tau)} = \prod_{i \in n} (g^{a_i(\tau)})^{w_i}$$
481which in our notation is
482$$[a(\tau)] = \sum_{i \in n} [a_i(\tau) \cdot w_i]$$
483
484\paragraph{Verifier}
485
486First check that $\alpha, \beta$ related terms are correct:
487
488$\alpha$-terms:
489\begin{align*}
490    e([a_m(\tau)], [\alpha]) &= e([\alpha \cdot a_m(\tau)], [1])\\
491    e([b(\tau)], [\alpha]) &= e([\alpha \cdot b(\tau)], [1])\\
492    e([c(\tau)], [\alpha]) &= e([\alpha \cdot c(\tau)], [1])\\
493    e([h(\tau)], [\alpha]) &= e([\alpha \cdot h(\tau)], [1])
494\end{align*}
495
496which we can group as:
497$$\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])$$
498
499$\beta$-terms:
500\begin{align*}
501    e([ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) &+ \beta_c \cdot c(\tau)], [1]) =\\
502			      &e([a_m(\tau)], [\beta_a]) \cdot e([b(\tau)], [\beta_b]) \cdot e([c(\tau)], [\beta_c])
503\end{align*}
504
505This is, 8 pairings for $\alpha$ terms, and 3 pairings for the $\beta$ terms.
506
507% 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
508Then, computes the term representing the public inputs:
509$$g^{a_{io}} = \prod_{i \in l} (g^{a_i(\tau)})^{w_i}$$
510ie.
511$$[a_{io}] = \sum_{i \in l} [a_i(\tau) \cdot w_i]$$
512
513in order to do the final check, verifying the divisibility, and therefore the QAP relation:
514$$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)])$$
515
516
517\vspace{1.0cm}
518\subsection{Actual Pinocchio protocol}
519
520Recall, from \ref{qap-relation}, 
521public 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}$.
522
523\vspace{0.3cm}
524Let $[m]= \{ l+1, \ldots, n \}$.
525\vspace{0.3cm}
526
527\paragraph{SRS}
528Let $r_a, r_b, \tau, \alpha_a, \alpha_b, \alpha_c, \beta, \gamma \in^R \mathbb{F}$ be the \emph{secret} challenges for the protocol.
529
530Also with $r_c = r_a \cdot r_b,~ g_a= g^{r_a},~ g_b=g^{r_b},~ g_c = g^{r_c}$.
531
532The \emph{proving key} will be
533% TODO align vertically:
534\begin{align*}
535    &\{ g_a^{a_i(\tau)} \}_{i \in [m]},~ \{ [g_b^{b_i(\tau)} \}_{i \in [m]},~ \{ [g_c^{c_i(\tau)} \}_{i \in [m]}\\
536    &\{ g_a^{\alpha_a \cdot a_i(\tau)} \}_{i \in [m]},~ \{ [g_b^{\alpha_b \cdot b_i(\tau)} \}_{i \in [m]},~ \{ [g_c^{\alpha_c \cdot c_i(\tau)} \}_{i \in [m]}\\
537    &\{ g^{\tau^i} \}_{i \in [d]},~
538    \{ g_a^{\beta a_i(\tau)} \cdot g_b^{\beta b_i(\tau)} \cdot g_c^{\beta c_i(\tau)} \}_{i \in [m]}
539\end{align*}
540ie, in our notation,
541\begin{align*}
542    &\{ [r_a \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [r_b \cdot b_i(\tau)] \}_{i \in [m]},~ \{ [r_c \cdot c_i(\tau)] \}_{i \in [m]}\\
543    &\{ [r_a \cdot \alpha_a \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [r_b \cdot \alpha_b \cdot b_i(\tau)] \}_{i \in [m]},~ \{ [r_c \cdot \alpha_c \cdot c_i(\tau)] \}_{i \in [m]}\\
544    &\{[\tau^i]\}_{i \in [d]},~ \{ [r_a \cdot \beta \cdot a_i(\tau) + r_b \cdot \beta \cdot b_i(\tau) + r_c \cdot \beta \cdot c_i(\tau) \}_{i \in [m]}
545\end{align*}
546
547The \emph{verifying key} will be
548\begin{align*}
549    &([1], [\alpha_a], [\alpha_b], [\alpha_c], [\gamma], [\beta \gamma], [r_c \cdot t(\tau)],\\
550     &\{[r_a \cdot a_i(\tau)],~ [r_b \cdot b_i(\tau)],~ [r_c \cdot c_i(\tau)] \}_{i \in \{0\} \cup [l]} )
551\end{align*}
552
553
554\paragraph{Prover}
555Solve for $h(X)$ such that $p(X)=h(X) \cdot t(X)$, then
556
557The proof $\pi$ is
558\begin{align*}
559    \pi = (&[r_a \cdot a_m(\tau)],~ [r_b \cdot b_m(\tau)],~ [r_c \cdot c_m(\tau)],~ [h(\tau)],~\\
560	   &[r_a \cdot \alpha \cdot a_m(\tau)],~ [r_b \cdot \alpha \cdot b(\tau)],~ [r_c \cdot \alpha \cdot c(\tau)],\\
561	   &[r_a \cdot \beta \cdot a_m(\tau) + r_b \cdot \beta \cdot b_m(\tau) + r_c \beta \cdot c_m(\tau)]
562\end{align*}
563
564where
565$$a_m(X) = \sum_{i \in [m]} w_i \cdot a_i(X)$$
566and similarly for $b_m(X),~ c_m(X)$.
567
568Note that the last element of $\pi$ is $g^z ~(ie.~ [z])$ later at the verifier.
569
570\paragraph{Verifier}
571The verifier receives the proof
572$$\pi = (g^{a_m}, g^{b_m}, g^{c_m}, g^h, g^{a_m'}, g^{b_m'}, g^{c_m'}, g^z)$$
573ie.
574$$\pi = ([a_m], [b_m], [c_m], [h], [a_m'], [b_m'], [c_m'], [z])$$
575
576
577First, it does the divisibility check:
578
579compute
580$$g_a^{a_{io}(\tau)} = \prod_{i \in l} (g_a^{a_{io}(\tau)})^{w_i}$$
581ie.
582$$[r_a \cdot a_{io}(\tau)] = [\sum_{i \in l} (r_a \cdot a_{io}(\tau) \cdot w_i)]$$
583similarly for $g_b^{b_{io}(\tau)},~ g_c^{c_{io}(\tau)}$.
584
585And then it checks
586$$e(g_a^{a_0(\tau)} \cdot g_a^{a_{io}(\tau)} \cdot g_a^{a_m},~ g_b^{b_0(\tau)} \cdot g_b^{b_{io}(\tau)} \cdot g_b^{b_m}) =
587e(g_c^{c_0(\tau)} \cdot g_c^{c_{io}(\tau)} \cdot g_c^{c_m}), g^1)$$
588
589ie.
590\begin{align*}
591    e([r_a \cdot (a_0(\tau) \cdot a_{io}(\tau) \cdot a_m)]_1,~ [r_b \cdot (b_0(\tau) &\cdot b_{io}(\tau) \cdot b_m)]_2) =\\
592&e([r_c \cdot (c_0(\tau) \cdot c_{io}(\tau) \cdot c_m)]_1, [1]_2)
593\end{align*}
594
595Next, it checks that the linear combinations computed over the QAP are in their appropriate spans:
596$$e([r_a \cdot a_m']_1, [1]_2) = e([r_a \cdot a_m]_1, [\alpha_a]_2)$$
597$$e([r_b \cdot b_m']_1, [1]_2) = e([r_b \cdot b_m]_1, [\alpha_b]_2)$$
598$$e([r_c \cdot c_m']_1, [1]_2) = e([r_c \cdot c_m]_1, [\alpha_c]_2)$$
599
600
601And finally, it checks that the same coefficients were used in each of the linear combinations over the QAP
602
603$$e(g^z, g^{\gamma}) = e(g_a^{a_m} \cdot g_b^{b_m} \cdot g_c^{c_m}, g^{\beta \gamma})$$
604ie.
605$$e([z]_1, [\gamma]_2 = e([r_a \cdot a_m]_1 \cdot [r_b \cdot b_m]_1 \cdot [r_c \cdot c_m]_1, [\beta \cdot \gamma]_2)$$
606
607recall that $[z]_1$ comes from the proof.
608
609\section{Groth16}
610
611\subsection{Conceptual version}
612As before, we want to prove the QAP relation $R_{QAP}$ (\ref{qap-relation}).
613
614We have, public 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}$.
615
616The prover will solve for $h(X)$ such that $p(X)=h(X) \cdot t(X)$, then we have
617$$
618(\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) + h(X) \cdot t(X)
619$$
620
621where $t(X)$ is the zero polynomial.
622
623\paragraph{SRS}
624
625Let $\alpha, \beta, \gamma, \delta, \tau \in^R \mathbb{F}$ be the \emph{secret} challenges for the protocol.
626
627Then
628\begin{align*}
629    \sigma &= \Bigg(
630	\alpha, \beta, \gamma, \delta, \{\tau^i \}_{i=0}^{n-1},
631	\left\{ \frac{\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau)}{\gamma} \right\}_{i=0}^l,\\
632	   &\left\{ \frac{\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau)}{\delta} \right\}_{i=0}^l,
633	   \left\{ \frac{\tau^i t(\tau)}{\delta} \right\}_{i=0}^{n-2}
634	\Bigg)
635\end{align*}
636
637\paragraph{Prover}
638
639Set random values $r, s \in^R \mathbb{F}$. Then compute
640
641\begin{align*}
642    A &= \alpha + \sum_{i=0}^n w_i a_i(\tau) + r \delta
643    ~~~~~~~~~~~~~~~~~~ B = \beta + \sum_{i=0}^n w_i b_i(\tau) + s \delta\\
644    C &= \frac{\sum_{i=l-1}^n w_i (\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau)) + h(\tau) + t(\tau)}{\delta} + A \cdot s + B \cdot r - r \cdot s \cdot \delta
645\end{align*}
646
647
648\paragraph{Verifier}
649The verifier wants to check that
650
651$$A \cdot B = \alpha \cdot \beta + \frac{\sum_{i=0}^l w_i (\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau))}{\gamma} \cdot \gamma + C \cdot \delta$$
652
653Here the
654\begin{itemize}
655    \item[$\gamma,\delta$:] make the two latter products of the verifier to be independent of the first product.
656    \item[$\alpha \cdot \beta$:] guarantee that $A, B$ involve nontrivial $\alpha, \beta$.\\
657	This is to prevent mixing and matching of elements intended for different products.
658    \item[$\alpha, \beta$:] ensure that $A, B, C$ are consistent with each other in the choice of\\
659	$w_1, w_2, \ldots, w_n$.
660    \item[$r, s$:] to randomize the proof to get the zero-knowledge property.
661\end{itemize}
662
663\vspace{1cm}
664
665\subsection{Actual Groth16 protocol}
666In practice, $\tau$ is kept secret, and the operations are done over the evaluations over the \emph{encrypted space}. Which is the reason of having computed the powers of tau in the SRS.
667
668\paragraph{Prover}
669Set random values $r, s \in^R \mathbb{F}$. Then compute
670
671\begin{align*}
672    A &= g_1^{\alpha + \sum_{i=0}^n w_i a_i(\tau) + r \delta} = \left[\alpha + \sum_{i=0}^n w_i a_i(\tau) + r \delta \right]_1\\
673    B &= g_2^{\beta + \sum_{i=0}^n w_i b_i(\tau) + s \delta} = \left[ \beta + \sum_{i=0}^n w_i b_i(\tau) + s \delta \right]_2\\
674    C &= g_1^{\frac{\sum_{i=l-1}^n w_i (\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau)) + h(\tau) + t(\tau)}{\delta} + A \cdot s + B \cdot r - r \cdot s \cdot \delta}\\
675      &= \left[ \frac{\sum_{i=l-1}^n w_i (\beta a_i(\tau) + \alpha b_i(\tau) + c_i(\tau)) + h(\tau) + t(\tau)}{\delta} + A \cdot s + B \cdot r - r \cdot s \cdot \delta \right]_1
676\end{align*}
677
678And the proof is $\pi = (A, B, C)$.
679
680\paragraph{Verifier}
681
682Verifier gets the proof $\pi = (A, B, C)$, and checks the following.
683
684First it computes
685$$ L = \sum_{i \in [0,l]} w_i \cdot [\gamma^{-1} \cdot L_i(\tau)]_1$$
686
687and then checks
688
689$$e(A, B) = e(g_1^{\alpha}, g_2^{\beta}) + e(L, g_2^{\gamma}) + e(C, g_2^{\delta})$$
690
691that is
692$$e(A, B) = e([\alpha]_1, [\beta]_2) + e(L, [\gamma]_2) + e(C, [\delta]_2)$$
693
694which is checking that $a(\tau) \cdot b(\tau) = c(\tau) + h(\tau) \cdot t(\tau)$.
695
696
697\vspace{1.0cm}
698
699\section{Powers of tau (SRS - trusted setup)}
700\subsection{Main idea}
701% TODO. mention "SRS" (Structured Reference String) concept
702
703\subsection{Participant contribution}
704In 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$
705
706For 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.
707
708Each participant will obtain the previous-participant generated SRS, which is formed by
709
710\begin{align*}
711        \{ [\tau^0]_1, [\tau^1]_1, [\tau^2]_2, \ldots, [\tau^{n-1}]_1 \},\\
712        \{ [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{m-1}]_2 \}
713\end{align*}
714
715for simplicity, we will represent it as
716
717$$\{~[~\tau^i]_1~\}^{n-1}_{i=0},~\{~[~\tau^i]_2~\}^{m-1}_{j=0}$$
718
719
720Each 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$.
721
722Then the participant proceeds to update the reference string (SRS), by multiplying each element by $p^i$:
723$$\{~ p^i \cdot [~ \tau^i]_1~\}^{n-1}_{i=0},~\{~ p^i \cdot [~\tau^i]_2~\}^{m-1}_{j=0}$$
724which, by the properties of scalar multiplication of a point, is equivalent to
725$$\{~ [~ (p \cdot \tau)^i]_1~\}^{n-1}_{i=0},~\{~ [~ (p \cdot \tau)^i]_2~\}^{m-1}_{j=0}$$
726and we denote $p \cdot \tau$ as $\tau'$, so we can write the previous expression as
727$$\{~[~\tau'^i]_1~\}^{n-1}_{i=0},~\{~[~\tau'^i]_2~\}^{m-1}_{j=0}$$
728
729which is
730\begin{align*}
731        \{ [(\tau \cdot p)^0]_1, [(\tau \cdot p)^1]_1, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{n-1}]_1 \},\\
732        \{ [(\tau \cdot p)^0]_2, [(\tau \cdot p)^1]_2, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{m-1}]_2 \}
733\end{align*}
734
735Notice that the contributor does not know the previous $\tau$, but can obtain $(\tau \cdot p)^i$.
736
737
738\subsection{Proof of correct computation}
739The participant will compute the proof, which consists of
740$$\pi = ([\tau']_1,~[p]_2)$$
741which is equivalent to $\pi = (\tau' \cdot G,~p \cdot H) = ((p \cdot \tau) \cdot G,~p \cdot H)$
742
743In the next section we will see how this is used to verify the contribution correct computation.
744
745
746\subsection{Contribution verification}
747This 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.
748
749Following the powers of tau structure means that
750$$\tau'^{i+1} = \tau' \cdot \tau'^i ~~\forall~i \in [1, n-1]$$
751
752And the relation between the new SRS and the previous SRS is
753$$\tau' = \tau \cdot p$$
754where $\tau$ is the secret element from the previous SRS and $p$ is the secret one from the new SRS, resulting in the combined $\tau'$.
755
756Now, 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:
757
758\begin{enumerate}
759        \item Check that elements of the new SRS are non-empty, non-zero and in the correct prime order subgroups.
760\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$).
761
762\item Check that $\tau'$ (the new SRS) is correctly related to $\tau$ (the previous SRS).
763
764    To check this, we rely on the pairing properties and we use the proof value generated by the contributor, which consists of $[p]_2$
765    $$e([\tau]_1, [p]_2) \stackrel{?}{=} e([\tau']_1, [1]_2)$$
766    
767    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
768    $$e([a]_1, [b]_2) = e([a \cdot b]_1, [1]_2)$$
769    by applying this to our case we can see that:
770    $$e([\tau]_1, [p]_2) = e([\tau \cdot p]_1, [1]_2) = e([\tau']_1, [1]_2)$$
771
772\item Check if the new SRS follows the powers of tau structure:
773    $$e([\tau'^i]_1, [\tau']_2) \stackrel{?}{=} e([\tau'^{i+1}]_1, [1]_2) ~~ \forall ~i \in [1, n-1]$$
774    $$e([\tau']_1, [\tau'^j]_2) \stackrel{?}{=} e([1]_1, [\tau'^{j+1}]_2) ~~ \forall ~i \in [1, m-1]$$
775    
776    Which, again, by the bilinarity property, we can see that
777    $$e([\tau'^i]_1, [\tau']_2) = e([\tau'^{i+1}]_1, [1]_2)$$
778    is enforcing that $\tau'^i \cdot \tau'^1 = \tau'^{i+1}$.
779    
780    And the same for
781    $$e([\tau']_1, [\tau'^j]_2) = e([1]_1, [\tau'^{j+1}]_2)$$
782    which checks that $\tau'^1 \cdot \tau'^j = \tau'^{j+1}$.
783    
784    With this check, we're ensuring that each power of tau of the SRS is consistent with the previous one.
785\end{enumerate}
786
787
788
789\bibliographystyle{unsrt}
790\bibliography{pinocchio-groth16.bib}
791
792\end{document}