math/pinocchio-groth16.tex
pinocchio-groth16.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4\usepackage{amsthm}
5\usepackage{amsmath}
6\usepackage{enumerate}
7\usepackage{hyperref}
8\usepackage{amssymb}
9\usepackage{tikz} % diagram
10
11\begin{filecontents}[overwrite]{pinocchio-groth16.bib}
12@misc{cryptoeprint:2013/279,
13 author = {Bryan Parno and Craig Gentry and Jon Howell and Mariana Raykova},
14 title = {Pinocchio: Nearly Practical Verifiable Computation},
15 howpublished = {Cryptology {ePrint} Archive, Paper 2013/279},
16 year = {2013},
17 url = {https://eprint.iacr.org/2013/279}
18}
19@misc{cryptoeprint:2016/260,
20 author = {Jens Groth},
21 title = {On the Size of Pairing-based Non-interactive Arguments},
22 howpublished = {Cryptology {ePrint} Archive, Paper 2016/260},
23 year = {2016},
24 url = {https://eprint.iacr.org/2016/260}
25}
26
27@misc{pairings,
28 note = {\url{https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}},
29 url = {https://github.com/arnaucube/math/blob/master/weil-pairing.pdf}
30}
31\end{filecontents}
32\nocite{*} % TODO review
33
34
35\newtheorem{thm}{Theorem}[section]
36\newtheorem{lemma}[thm]{Lemma}
37\newtheorem{prop}[thm]{Proposition}
38\newtheorem{cor}[thm]{Corollary}
39\newtheorem{defn}[thm]{Definition}
40
41
42\title{Pinocchio and Groth16 notes}
43\author{arnaucube}
44\date{2026}
45
46\begin{document}
47
48\maketitle
49
50\begin{abstract}
51 Notes taken while studying the schemes Pinocchio (\cite{cryptoeprint:2013/279}) and Groth16 (\cite{cryptoeprint:2016/260}).
52
53 Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
54
55 The proofs may slightly differ from the ones from the books or papers, since I try to extend them for a deeper understanding.
56\end{abstract}
57
58\tableofcontents
59\newpage
60
61
62\section{Introduction}
63
64% TODO.
65% what we want to prove, how it connects with R1CS & QAP
66
67
68\section{Notation}
69
70Let $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}$.
71
72\section{R1CS}
73% TODO Add R_{R1CS} relation definition.
74
75Rank-One Constraint System (R1CS) is the representation of the constraints of the circuit by 3 linear combinations, where there is one constraint per operation.
76
77$$
78\begin{aligned}
79(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
80\\
81(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
82\\
83(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
84\\
85\ldots
86\\
87(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
88\end{aligned}
89$$
90
91Where the R1CS linear combinations can be represented by three matrices $A$, $B$ and $C$:
92$$
93\begin{aligned}
94A =
95\begin{pmatrix}
96a_{11} & a_{12} & ... & a_{1n}\\
97a_{21} & a_{22} & ... & a_{2n}\\
98a_{31} & a_{32} & ... & a_{3n}\\
99...\\
100a_{m1} & a_{m2} & ... & a_{mn}
101\end{pmatrix}
102B =
103\begin{pmatrix}
104b_{11} & b_{12} & ... & b_{1n}\\
105b_{21} & b_{22} & ... & b_{2n}\\
106b_{31} & b_{32} & ... & b_{3n}\\
107...\\
108b_{m1} & b_{m2} & ... & b_{mn}
109\end{pmatrix}
110\\
111C =
112\begin{pmatrix}
113c_{11} & c_{12} & ... & c_{1n}\\
114c_{21} & c_{22} & ... & c_{2n}\\
115c_{31} & c_{32} & ... & c_{3n}\\
116...\\
117c_{m1} & c_{m2} & ... & c_{mn}
118\end{pmatrix}
119\end{aligned}
120$$
121
122Where
123$(A, B, C) = A w \circ B w - C w = 0$
124
125The process that converts the \emph{flat constraints} into \emph{R1CS} is the following:
126
127Lets 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:
128
129$$
130\begin{aligned}
131A =
132\begin{pmatrix}
1331 & 0 & 0 & ... & 0\\
134\end{pmatrix}
135\\
136B =
137\begin{pmatrix}
1380 & 2 & 0 & ... & 0\\
139\end{pmatrix}
140\\
141C =
142\begin{pmatrix}
1430 & 0 & 5 & ... & 0\\
144\end{pmatrix}
145\end{aligned}
146$$
147
148
149Which in the R1CS equation form would look as:
150$$
151\begin{aligned}
152(1 \cdot w_1 + 0 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) \cdot
153(0 \cdot w_1 + 2 \cdot w_2 + 0 \cdot w_3 + ... + 0 \cdot w_n) -\\
154(0 \cdot w_1 + 0 \cdot w_2 + 5 \cdot w_3 + ... + 0 \cdot w_n) = 0
155\end{aligned}
156$$
157
158If we simplify the previous liniar combination we get:
159$$
160\begin{aligned}
161(1 \cdot w_1) \cdot (2 \cdot w_2) - (5 \cdot w_3) = 0
162\\
163w_1 \cdot 2w_1 - 5 w_3 = 0
164\\
1655 w_3 = w_1 \cdot 2w_1
166\end{aligned}
167$$
168Where $5 w_3 = w_1 \cdot 2w_1$ is the constraint that we wanted to represent in the R1CS format.
169
170The 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.
171Since we have now the constraints in a polynomial format, we can do work with it in the polynomial way.
172
173
174\section{QAP (Quadratic Arithmetic Programs)} \label{qap}
175
176Once 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)}.
177%% TODO %%
178\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)$.
179The \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}$.
180
181The 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.
182
183In 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:
184
185$$L(X) = \sum_{j=0}^{n} y_j l_j(X)$$
186
187where $l_j(X)$ is:
188$$
189l_j(X) = \prod_{0\leq m \leq k ; m\neq j}
190\frac{X-x_m}{x_j - x_m}
191...
192\frac{(X-x_{j-1})}{(x_j - x_{j-1})}
193\frac{(X-x_{j+1})}{(x_j - x_{j+1})}
194...
195\frac{X-x_k}{x_j - x_k}
196$$
197
198The 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.
199
200In our case, \emph{Lagrange interpolation} is used to go from the \emph{R1CS} polynomials into the \emph{QAP} polynomials, which are defined by:
201
202$$
203\begin{aligned}
204 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\\
205 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\\
206 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
207\end{aligned}
208$$
209
210The polynomials $a(X), b(X), c(X)$ are the QAP, such that
211$$a(X) \cdot b(X) = c(X)$$
212so that
213$$p(X) = a(X) \cdot b(X) - c(X) = 0$$
214
215that is,
216$$
217\begin{aligned}
218 p(X) = &(a_1(X)w_1 + a_2(X)w_2 + ... + a_n(X)w_n)\\
219 &\cdot (b_1(X)w_1 + b_2(X)w_2 + ... + b_n(X)w_n)\\
220 &- (c_1(X)w_1 + c_2(X)w_2 + ... + c_n(X)w_n)\\
221 = &(\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
222\end{aligned}
223$$
224
225The 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.
226
227
228\vspace{0.5cm}
229
230\section{QAP Relation} \label{qap-relation}
231
232Want to ensure that
233$$
234(\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
235$$
236
237for a given witness $(w_1, \ldots, w_n) \in \mathbb{F}^n$, which we divide between public inputs and private inputs:
238\begin{align*}
239 \text{public inputs:}~~ io &= \phi = (w_1, \ldots, w_l) \in \mathbb{F}^l, \\
240 \text{private inputs:}~~ s &= (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},
241\end{align*}
242
243We denote the relation
244
245$$
246R_{QAP} =
247\left\{
248\begin{aligned}
249 &w=(1, \phi, s) \in \mathbb{F}^n ~\text{such that:}\\
250 &\phi = (w_1, \ldots, w_l) \in \mathbb{F}^l,~
251 s = (w_{l+1}, \ldots, w_n) \in \mathbb{F}^{n-l-1},\\
252& (\sum_{i=0}^n a_i(X) \cdot w_i) \cdot (\sum_{i=0}^n b_i(X) \cdot w_i)
253= \sum_{i=0}^{n} c_i(X) \cdot w_i
254~\bmod Z(X)
255\end{aligned}
256\right.
257$$
258
259where $Z(X)$ is the "zero polynomial" or "vanishing polynomial", such that
260$$Z(X)= \prod_{i=0}^d (X-x_i) \in \mathbb{F}[X]^{<d}$$
261
262Set
263$$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$$
264
265so that
266$$a(X) \cdot b(X) \equiv c(X) \bmod Z(X)$$
267
268which means that we can prove that
269$$\exists~ h(X) \in \mathbb{F}[X]^{<d}~~ \text{s.th.}~
270a(X) \cdot b(X) - c(X) = h(X) \cdot Z(X)$$
271
272
273\section{Simplified protocol}
274Protocol to prove $a(X)b(X)-c(X)=0$ in order to provide intuition on what we're trying to do.
275
276\paragraph{Setup.}
277The 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$.
278
279$$\{ [\tau^i]_1 \}_0^n = ( [\tau^0]_1, [\tau^1]_1, [\tau^2]_1, \ldots, [\tau^{n-1}]_1)$$
280$$\{ [\tau^i]_2 \}_0^n = ( [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{n-1}]_2)$$
281
282\paragraph{Prover.}
283\begin{enumerate}[i.]
284 \item commit to $a(X), b(X), c(X) \in \mathbb{F}[X]$
285
286 $$cm(a) = [a(\tau)]_1 = \sum_{i=0}^{\delta a} a_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
287
288 notice that it is equal to $\sum a_i \cdot g_1^{\tau^i}$ without knowing $\tau$.
289
290 Same is done for $b(X)$ and $c(X)$:
291 $$cm(b) = [b(\tau)]_2 = \sum_{i=0}^{\delta b} b_i \cdot [\tau^i]_2 \in \mathbb{G}_2$$
292 $$cm(c) = [c(\tau)]_1 = \sum_{i=0}^{\delta c} c_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
293
294
295 For a challenge $z \in^R \mathbb{F}$, set by the verifier, open the commitments:
296
297 $$q_a(X) = \frac{a(X) - a(z)}{X-z}$$
298
299 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,
300 $$\exists ~q_a(X) ~~\text{such that}~ a(X)-a(z) = (X-z) \cdot q_a(X)$$
301 therefore
302 $$q_a(X) = \frac{a(X)-a(z)}{X-z}$$
303
304 Same is done for $b(X)$ and $c(X)$,
305 $$q_b(X) = \frac{b(X)-b(z)}{X-z}$$
306 $$q_c(X) = \frac{c(X)-c(z)}{X-z}$$
307
308 And then, evaluate them at the encrypted $\tau$:
309 $$[q_a(\tau)]_1 = \sum_{i=0}^{\delta q_a} q_{a_i} \cdot [\tau^i]_1 \in \mathbb{G}_1$$
310 similarly for $[q_b(\tau)]_2 \in \mathbb{G}_2$ and $[q_c(\tau)]_1 \in \mathbb{G}_1$.
311
312 \item for the relation that we want to prove, $a(X) \cdot b(X) - c(X)=0$,
313 $$\exists~ q(X) \in \mathbb{F}[X] ~~\text{s.th.}~~ a(X)b(X)-c(X)=q(X) \cdot z(X)$$
314 So the prover computes
315 $$q(X) = \frac{a(X) \cdot b(X) - c(X)}{z(X)}$$
316 and it's encrypted evaluation
317 $$[q(\tau)]_1 = \sum_{i=0}^{\delta q} q_i \cdot [\tau^i]_1 \in \mathbb{G}_1$$
318\end{enumerate}
319
320\paragraph{Verifier.}
321\begin{enumerate}[i.]
322 \item verify the commitments:\\
323 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$
324
325 For each commitment, the verifier checks:
326 $$e([q_a(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([a(\tau)]_1 - [a(z)]_1, [1]_2)$$
327 which is a way of checking the existence of $q_a(X)$ such that $q_a(X) \cdot (X-z) = a(X) - a(z)$.
328
329 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$.
330
331 Same is done for $b(X)$ and $c(X)$ commitments:
332 $$e([\tau]_1 - [z]_2, [q_b(\tau)]_1) \stackrel{?}{=} e([1]_1, [b(\tau)]_1 - [b(z)]_1)$$
333 $$e([q_c(\tau)]_1, [\tau]_2 - [z]_2) \stackrel{?}{=} e([c(\tau)]_1 - [c(z)]_1, [1]_2)$$
334
335 \item check the $a(X) \cdot b(X) - c(X) = 0$ relation:
336 $$e([a(\tau)]_1, [b(\tau)]_2) \stackrel{?}{=} e([q(\tau)]_1, [z(\tau)]_2) \cdot e([c(s)]_1, [1]_2)$$
337 which ensures that $\exists~ q(X) \in \mathbb{F}[X] ~\text{s.th.}~ a(X) b(X) - c(X) = q(X) z(X)$.
338\end{enumerate}
339
340\section{Pinocchio}
341
342\subsection{Conceptual version}
343\emph{(this is what the paper names "Protocol 1")}
344
345Recall, from \ref{qap-relation},
346public 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}$.
347
348\vspace{0.5cm}
349Let $[m]= \{ l+1, \ldots, n \}$.
350
351\paragraph{SRS}
352Let $\tau, \alpha, \beta_a, \beta_b, \beta_c, \gamma \in^R \mathbb{F}$ be the \emph{secret} challenges for the protocol.
353
354The \emph{proving key} will be
355% TODO align vertically:
356\begin{align*}
357 &\{ [a_i(\tau)] \}_{i \in [m]},~ \{ [b_i(\tau)] \}_{i \in [n]},~ \{ [c_i(\tau)] \}_{i \in [n]}\\
358 &\{ [\alpha \cdot a_i(\tau)] \}_{i \in [m]},~ \{ [\alpha \cdot b_i(\tau)] \}_{i \in [n]},~ \{ [\alpha \cdot c_i(\tau)] \}_{i \in [n]}\\
359 &\{ [\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]}\\
360 &\{ [\tau^i] \}_{i \in [d]},~ \{ [\alpha \cdot \tau^i] \}_{i \in [d]}\\
361\end{align*}
362
363The \emph{verifying key} will be
364\begin{align*}
365 (&[1], [\alpha], [\gamma], [\beta_a \cdot \gamma], [\beta_b \cdot \gamma], [\beta_c \cdot \gamma], [Z(\tau)],\\
366 &\{[a_i(\tau)]\}_{i \in l}, [a_0(\tau)], [b_0(\tau)], [c_0(\tau)])
367\end{align*}
368
369\paragraph{Prover}
370Solve for $h(X)$ such that $p(X)=h(X) \cdot t(X)$, then
371
372Let
373$$a_m(X) = \sum_{i \in [m]} w_i \cdot a_i(X)$$
374
375Denote $a(X), b(X), c(X)$ as
376\begin{align*}
377 a(X) = \sum_{i \in [n]} &w_i \cdot a_i(X), ~~ b(X) = \sum_{i \in [n]} w_i \cdot b_i(X)\\
378 &c(X) = \sum_{i \in [n]} w_i \cdot c_i(X)
379\end{align*}
380
381Then the proof $\pi$ is
382\begin{align*}
383 \pi = (&[a_m(\tau)],~ [b(\tau)],~ [c(\tau)],~ [h(\tau)],~\\
384 &[\alpha \cdot a_m(\tau)],~ [\alpha \cdot b(\tau)],~ [\alpha \cdot c(\tau)],~[\alpha \cdot h(\tau)],\\
385 &\hspace*{2em}\text{\emph{(ie. same as first line but $\alpha$-shifted)}}\\
386 &[ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) + \beta_c \cdot c(\tau)]
387 )
388\end{align*}
389
390Since $a(X), b(X), c(X)$ are linear equations, we can compute them in the exponent of $g$, eg.
391$$g^{a(\tau)} = \prod_{i \in n} (g^{a_i(\tau)})^{w_i}$$
392which in our notation is
393$$[a(\tau)] = \sum_{i \in n} [a_i(\tau) \cdot w_i]$$
394
395\paragraph{Verifier}
396
397First check that $\alpha, \beta$ related terms are correct:
398
399\begin{align*}
400 e([a_m(\tau)], [\alpha]) &= e([\alpha \cdot a_m(\tau)], [1])\\
401 e([b(\tau)], [\alpha]) &= e([\alpha \cdot b(\tau)], [1])\\
402 e([c(\tau)], [\alpha]) &= e([\alpha \cdot c(\tau)], [1])\\
403 e([h(\tau)], [\alpha]) &= e([\alpha \cdot h(\tau)], [1])
404\end{align*}
405\begin{align*}
406 e([ \beta_a \cdot a(\tau) + \beta_b \cdot b(\tau) &+ \beta_c \cdot c(\tau)], [1]) =\\
407 &e([a_m(\tau)], [\beta_a]) \cdot e([b(\tau)], [\beta_b]) \cdot e([c(\tau)], [\beta_c])
408\end{align*}
409
410This is, 8 pairings for $\alpha$ terms, and 3 pairings for the $\beta$ terms.
411
412Then, computes the term representing the public inputs:
413$$g^{a_{io}} = \prod_{i \in l} (g^{a_i(\tau)})^{w_i}$$
414ie.
415$$[a_{io}] = \sum_{i \in l} [a_i(\tau) \cdot w_i]$$
416
417in order to do the final check, verifying the divisibility, and therefore the QAP relation:
418$$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)])$$
419
420\section{Groth16}
421
422\vspace{1cm}
423
424\section{Powers of tau (trusted setup)}
425\subsection{Main idea}
426% TODO. mention "SRS" concept
427
428\subsection{Participant contribution}
429In 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$
430
431For 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.
432
433Each participant will obtain the previous-participant generated SRS, which is formed by
434
435\begin{align*}
436 \{ [\tau^0]_1, [\tau^1]_1, [\tau^2]_2, \ldots, [\tau^{n-1}]_1 \},\\
437 \{ [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{m-1}]_2 \}
438\end{align*}
439
440for simplicity, we will represent it as
441
442$$\{~[~\tau^i]_1~\}^{n-1}_{i=0},~\{~[~\tau^i]_2~\}^{m-1}_{j=0}$$
443
444
445Each 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$.
446
447Then the participant proceeds to update the reference string (SRS), by multiplying each element by $p^i$:
448$$\{~ p^i \cdot [~ \tau^i]_1~\}^{n-1}_{i=0},~\{~ p^i \cdot [~\tau^i]_2~\}^{m-1}_{j=0}$$
449which, by the properties of scalar multiplication of a point, is equivalent to
450$$\{~ [~ (p \cdot \tau)^i]_1~\}^{n-1}_{i=0},~\{~ [~ (p \cdot \tau)^i]_2~\}^{m-1}_{j=0}$$
451and we denote $p \cdot \tau$ as $\tau'$, so we can write the previous expression as
452$$\{~[~\tau'^i]_1~\}^{n-1}_{i=0},~\{~[~\tau'^i]_2~\}^{m-1}_{j=0}$$
453
454which is
455\begin{align*}
456 \{ [(\tau \cdot p)^0]_1, [(\tau \cdot p)^1]_1, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{n-1}]_1 \},\\
457 \{ [(\tau \cdot p)^0]_2, [(\tau \cdot p)^1]_2, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{m-1}]_2 \}
458\end{align*}
459
460Notice that the contributor does not know the previous $\tau$, but can obtain $(\tau \cdot p)^i$.
461
462
463\subsection{Proof of correct computation}
464The participant will compute the proof, which consists of
465$$\pi = ([\tau']_1,~[p]_2)$$
466which is equivalent to $\pi = (\tau' \cdot G,~p \cdot H) = ((p \cdot \tau) \cdot G,~p \cdot H)$
467
468In the next section we will see how this is used to verify the contribution correct computation.
469
470
471\subsection{Contribution verification}
472This 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.
473
474Following the powers of tau structure means that
475$$\tau'^{i+1} = \tau' \cdot \tau'^i ~~\forall~i \in [1, n-1]$$
476
477And the relation between the new SRS and the previous SRS is
478$$\tau' = \tau \cdot p$$
479where $\tau$ is the secret element from the previous SRS and $p$ is the secret one from the new SRS, resulting in the combined $\tau'$.
480
481Now, 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:
482
483\begin{enumerate}
484 \item Check that elements of the new SRS are non-empty, non-zero and in the correct prime order subgroups.
485\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$).
486
487\item Check that $\tau'$ (the new SRS) is correctly related to $\tau$ (the previous SRS).
488
489 To check this, we rely on the pairing properties and we use the proof value generated by the contributor, which consists of $[p]_2$
490 $$e([\tau]_1, [p]_2) \stackrel{?}{=} e([\tau']_1, [1]_2)$$
491
492 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
493 $$e([a]_1, [b]_2) = e([a \cdot b]_1, [1]_2)$$
494 by applying this to our case we can see that:
495 $$e([\tau]_1, [p]_2) = e([\tau \cdot p]_1, [1]_2) = e([\tau']_1, [1]_2)$$
496
497\item Check if the new SRS follows the powers of tau structure:
498 $$e([\tau'^i]_1, [\tau']_2) \stackrel{?}{=} e([\tau'^{i+1}]_1, [1]_2) ~~ \forall ~i \in [1, n-1]$$
499 $$e([\tau']_1, [\tau'^j]_2) \stackrel{?}{=} e([1]_1, [\tau'^{j+1}]_2) ~~ \forall ~i \in [1, m-1]$$
500
501 Which, again, by the bilinarity property, we can see that
502 $$e([\tau'^i]_1, [\tau']_2) = e([\tau'^{i+1}]_1, [1]_2)$$
503 is enforcing that $\tau'^i \cdot \tau'^1 = \tau'^{i+1}$.
504
505 And the same for
506 $$e([\tau']_1, [\tau'^j]_2) = e([1]_1, [\tau'^{j+1}]_2)$$
507 which checks that $\tau'^1 \cdot \tau'^j = \tau'^{j+1}$.
508
509 With this check, we're ensuring that each power of tau of the SRS is consistent with the previous one.
510\end{enumerate}
511
512
513
514\bibliographystyle{unsrt}
515\bibliography{pinocchio-groth16.bib}
516
517\end{document}