slides/src/zksnarks-from-scratch-a-technical-explanation/zksnarks-from-scratch-a-technical-explanation.md
src/zksnarks-from-scratch-a-technical-explanation/zksnarks-from-scratch-a-technical-explanation.mdRaw
1# zkSNARKs from scratch, a technical explanation
2
3<br><br><br>
4<div style="float:right; text-align:right;">
5 <img style="width:80px" src="imgs/arnaucube.png" /> <br>
6
7[arnaucube.com](https://arnaucube.com)
8[github.com/arnaucube](https://github.com/arnaucube)
9[twitter.com/arnaucube](https://twitter.com/arnaucube)
10 <br>
11 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png" /></a>
12 2019-08-20
13</div>
14
15<img style="width:200px;" src="imgs/iden3.png" /> <br>
16[iden3.io](https://iden3.io)
17[github.com/iden3](https://github.com/iden3)
18[twitter.com/identhree](https://twitter.com/identhree)
19
20
21---
22
23## Warning
24
25<div style="font-size:90%;">
26
27- I'm not a mathematician, this talk is not for mathematicians
28
29- In free time, have been studying zkSNARKS & implementing it in Go
30
31- Talk about a technical explaination from an engineer point of view
32- The idea is to try to transmit the learnings from long night study hours during last winter
33- Also at the end will briefly overview how we use zkSNARKs in iden3
34- This slides will be combined with
35 - parts of the code from https://github.com/arnaucube/go-snark
36 - whiteboard draws and writtings
37- Don't use your own crypto. But it's fun to implement it (only for learning purposes)
38
39</div>
40
41---
42
43## Contents
44
45<div style="font-size: 90%;">
46
47- Introduction
48 - zkSNARK overview
49 - zkSNARK flow
50 - Generating and verifying proofs
51- Foundations
52 - Basics of modular arithmetic
53 - Groups
54 - Finite fields
55 - Elliptic curve operations
56- Pairings
57 - Bilinear Pairings
58 - BLS signatures
59
60</div>
61
62---
63
64<div style="font-size: 90%;">
65
66- zkSNARK (Pinocchio)
67 - Circuit compiler
68 - R1CS
69 - QAP
70 - Lagrange Interpolation
71 - Trusted Setup
72 - Proofs generation
73 - Proofs verification
74- Groth16
75- How we use zkSNARKs in iden3
76- libraries
77- Circuit languages
78- utilities (Elliptic curve & Hash functions) inside the zkSNARK libraries
79 - BabyJubJub
80 - Mimc
81 - Poseidon
82- References
83
84</div>
85
86---
87
88## Introduction
89- zero knowledge concept
90- examples
91- some concept explanations
92 - https://en.wikipedia.org/wiki/Zero-knowledge_proof
93 - https://hackernoon.com/wtf-is-zero-knowledge-proof-be5b49735f27
94
95---
96
97
98## zkSNARK overview
99
100
101- protocol to prove the correctness of a computation
102- useful for
103 - scalability
104 - privacy
105 - interoperability
106- examples:
107 - Alice can prove to Brenna that knows $x$ such as $f(x) = y$
108 - Brenna can prove to Alice that knows a certain input which $Hash$ results in a certain known value
109 - Carol can proof that is a member of an organization without revealing their identity
110 - etc
111
112---
113
114### zkSNARK flow
115
116<div style="text-align:center;">
117 <img src="imgs/zksnark-concept-flow.png"/>
118</div>
119
120---
121
122
123### Generating and verifying proofs
124Generating a proof:
125
126<img src="imgs/zksnark-prover.png"/>
127
128<img src="imgs/cat04.jpeg" style="float:right; width:300px;" />
129
130<br><br>
131
132Verifying a proof:
133
134<img src="imgs/zksnark-verifier.png"/>
135
136
137
138
139---
140
141
142## Foundations
143- Modular aritmetic
144- Groups
145- Finite fields
146- Elliptic Curve Cryptography
147
148---
149
150## Basics of modular arithmetic
151- Modulus, `mod`, `%`
152- Remainder after division of two numbers
153
154
155
156```python
1575 mod 12 = 5
15814 mod 12 = 2
15983 mod 10 = 3
160```
161
162```python
1635 + 3 mod 6 = 8 mod 6 = 2
164```
165
166
167---
168
169## Groups
170- a **set** with an **operation**
171 - **operation** must be *associative*
172- neutral element ($identity$): adding the neutral element to any element gives the element
173- inverse: $e$ + $e_{inverse}$ = $identity$
174- cyclic groups
175 - finite group with a generator element
176 - any element must be writable by a multiple of the generator element
177- abelian group
178 - group with *commutative* operation
179
180---
181
182## Finite fields
183- algebraic structure like Groups, but with **two operations**
184- extended fields concept (https://en.wikipedia.org/wiki/Field_extension)
185
186---
187
188## Elliptic curve
189- point addition
190
191$(x_1, y_1) + (x_2, y_2) =
192(\dfrac{
193x_1 y_2 + x_2 y_1
194}{
1951 + d x_1 x_2 y_1 y_2
196},
197\dfrac{
198y_1 y_2 - x_1 x_2
199}{
2001-dx_1 x_2 y_1 y_2
201})$
202- G1
203- G2
204
205*(whiteboard explanation)*
206
207---
208
209## Pairings
210- 3 typical types used for SNARKS:
211 - BN (Barreto Naehrig) - used in Ethereum
212 - BLS (Barreto Lynn Scott) - used in ZCash & Ethereum 2.0
213 - MNT (Miyaji- Nakabayashi - Takano) - used in CodaProtocol
214- $y^2 = x^3 + b$ with embedding degree 12
215- function that maps (pairs) two points from sets `S1` and `S2` into another set `S3`
216- is a [bilinear](https://en.wikipedia.org/wiki/Bilinear_map) function
217- $e(G_1, G_2) -> G_T$
218- the groups must be
219 - cyclic
220 - same prime order ($r$)
221
222---
223
224- $F_q$, where $q=$`21888242871839275222246405745257275088696311157297823662689037894645226208583`
225- $F_r$, where $r=$`21888242871839275222246405745257275088548364400416034343698204186575808495617`
226
227---
228
229## Bilinear Pairings
230$e(P_1 + P_2, Q_1) == e(P_1, Q_1) \cdot e(P_2, Q_1)$
231
232$e(P_1, Q_1 + Q_2) == e(P_1, Q_1) \cdot e(P_1, Q_2)$
233
234$e(aP, bQ) == e(P, Q)^{ab} == e(bP, aQ)$
235
236<img src="imgs/cat01.jpeg" style="float:right; width:300px;" />
237
238$e(g_1, g_2)^6 == e(g_1, 6 \cdot g_2)$
239
240$e(g_1, g_2)^6 == e(6 \cdot g_1, g_2)$
241
242$e(g_1, g_2)^6 == e(3 \cdot g_1, 2 g_2)$
243
244$e(g_1, g_2)^6 == e(2 \cdot g_1, 3 g_2)$
245
246
247---
248
249### BLS signatures
250*(small overview, is offtopic here, but is interesting)*
251- key generation
252 - random private key $x$ in $[0, r-1]$
253 - public key $g^x$
254- signature
255 - $h=Hash(m)$ (over G2)
256 - signature $\sigma=h^x$
257- verification
258 - check that: $e(g, \sigma) == e(g^x, Hash(m))$
259 $e(g, h^x) == e(g^x, h)$
260
261
262---
263
264- aggregate signatures
265 - $s = s0 + s1 + s2 ...$
266- verify aggregated signatures
267
268<div style="font-size:75%">
269
270$e(G,S) == e(P, H(m))$
271
272$e(G, s0+s1+s2...) == e(p0, H(m)) \cdot e(p1, H(m)) \cdot e(p2, H(m)) ...$
273
274</div>
275
276
277More info: https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
278
279---
280
281## Circuit compiler
282- not a software compiler -> a constraint prover
283 - what this means
284- constraint concept
285 - `value0` == `value1` `<operation>` `value2`
286- want to proof that a certain computation has been done correctly
287- graphic of circuit with gates (whiteboard)
288
289- about high level programing languages for zkSNARKS, by *Harry Roberts*: https://www.youtube.com/watch?v=nKrBJo3E3FY
290
291---
292
293Circuit code example:
294$f(x) = x^5 + 2\cdot x + 6$
295
296```
297func exp5(private a):
298 b = a * a
299 c = a * b
300 d = a * c
301 e = a * d
302 return e
303
304func main(private s0, public s1):
305 s2 = exp5(s0)
306 s3 = s0 * 2
307 s4 = s3 + s2
308 s5 = s4 + 6
309 equals(s1, s5)
310 out = 1 * 1
311```
312
313---
314
315## Inputs and Witness
316For a certain circuit, with the inputs that we calculate the Witness for the circuit signals
317- private inputs: `[8]`
318 - in this case the private input is the 'secret' $x$ value that computed into the equation gives the expected $f(x)$
319- public inputs: `[32790]`
320 - in this case the public input is the result of the equation
321- signals: `[one s1 s0 b0 c0 d0 s2 s3 s4 s5 out]`
322- witness: `[1 32790 8 64 512 4096 32768 16 32784 32790 1]`
323
324---
325
326## R1CS
327- Rank 1 Constraint System
328- way to write down the constraints by 3 linear combinations
329- 1 constraint per operation
330- $(A, B, C) = A.s \cdot B.s - C.s = 0$
331- from flat code constraints we can generate the R1CS
332
333---
334
335## R1CS
336
337<div style="font-size:65%">
338
339$(a_{11}s_1 + a_{12}s_2 + ... + a_{1n}s_n) \cdot (b_{11}s_1 + b_{12}s_2 + ... + b_{1n}s_n) - (c_{11}s_1 + c_{12}s_2 + ... + c_{1n}s_n) = 0$
340
341$(a_{21}s_1 + a_{22}s_2 + ... + a_{2n}s_n) \cdot (b_{21}s_1 + b_{22}s_2 + ... + b_{2n}s_n) - (c_{21}s_1 + c_{22}s_2 + ... + c_{2n}s_n) = 0$
342$(a_{31}s_1 + a_{32}s_2 + ... + a_{3n}s_n) \cdot (b_{31}s_1 + b_{32}s_2 + ... + b_{3n}s_n) - (c_{31}s_1 + c_{32}s_2 + ... + c_{3n}s_n) = 0$
343[...]
344$(a_{m1}s_1 + a_{m2}s_2 + ... + a_{mn}s_n) \cdot (b_{m1}s_1 + b_{m2}s_2 + ... + b_{mn}s_n) - (c_{m1}s_1 + c_{m2}s_2 + ... + c_{mn}s_n) = 0$
345
346*where $s$ are the signals of the circuit, and we need to find $a, b, c$ that satisfies the equations
347</div>
348
349---
350
351R1CS constraint example:
352- signals: `[one s1 s0 b0 c0 d0 s2 s3 s4 s5 out]`
353- witness: `[1 32790 8 64 512 4096 32768 16 32784 32790 1]`
354- First constraint flat code: `b0 == s0 * s0`
355- R1CS first constraint:
356$A_1 = [00100000000]$
357$B_1 = [00100000000]$
358$C_1 = [00010000000]$
359
360---
361
362R1CS example:
363
364| $A$| $B$ | $C$: |
365|-|-|-|
366| $[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 0 0 0 0 1 1 0 0 0]$<br>$[6 0 0 0 0 0 0 0 1 0 0]$<br>$[0 0 0 0 0 0 0 0 0 1 0]$<br>$[0 1 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$ | $[0 0 1 0 0 0 0 0 0 0 0]$<br>$[0 0 0 1 0 0 0 0 0 0 0]$<br>$[0 0 0 0 1 0 0 0 0 0 0]$<br>$[0 0 0 0 0 1 0 0 0 0 0]$<br>$[2 0 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$<br>$[1 0 0 0 0 0 0 0 0 0 0]$ | $[0 0 0 1 0 0 0 0 0 0 0]$ <br>$[0 0 0 0 1 0 0 0 0 0 0]$<br>$[0 0 0 0 0 1 0 0 0 0 0]$<br>$[0 0 0 0 0 0 1 0 0 0 0]$<br>$[0 0 0 0 0 0 0 1 0 0 0]$<br>$[0 0 0 0 0 0 0 0 1 0 0]$<br>$[0 0 0 0 0 0 0 0 0 1 0]$<br>$[0 1 0 0 0 0 0 0 0 0 0]$<br>$[0 0 0 0 0 0 0 0 0 1 0]$<br>$[0 0 0 0 0 0 0 0 0 0 1]$ |
367
368
369---
370
371## QAP
372- Quadratic Arithmetic Programs
373- 3 polynomials, linear combinations of R1CS
374- very good article about QAP by Vitalik Buterin https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
375
376---
377
378
379
380---
381
382### Lagrange Interpolation
383(Polynomial Interpolation)
384- for a group of points, we can find the smallest degree polynomial that goees through all that points
385 - this polynomial is unique for each group of points
386
387
388
389---
390
391$L(x) = \sum_{j=0}^{n} y_j l_j(x)$
392
393<br><br>
394
395
396
397
398---
399
400#### Shamir's Secret Sharing
401*(small overview, is offtopic here, but is interesting)*
402
403- from a secret to be shared, we generate 5 parts, but we can specify a number of parts that are needed to recover the secret
404- so for example, we generate 5 parts, where we will need only 3 of that 5 parts to recover the secret, and the order doesn't matter
405- we have the ability to define the thresholds of $M$ parts to be created, and $N$ parts to be able the recover
406
407---
408
409##### Shamir's Secret Sharing - Secret generation
410- we want that are necessary $n$ parts of $m$ to recover $s$
411 - where $n<m$
412- need to create a polynomial of degree $n-1$
413$f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2 + \alpha_3 x^3 + ... + + \alpha_{n-1} x^{n-1}$
414- where $\alpha_0$ is the secret $s$
415- $\alpha_i$ are random values that build the polynomial
416*where $\alpha_0$ is the secret to share, and $\alpha_i$ are the random values inside the $Finite Field$
417
418---
419
420$f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2 + \alpha_3 x^3 + ... + + \alpha_{n-1} x^{n-1}$
421
422- the packets that we will generate are $P = (x, f(x))$
423 - where $x$ is each one of the values between $1$ and $m$
424 - $P_1=(1, f(1))$
425 - $P_2=(2, f(2))$
426 - $P_3=(3, f(3))$
427 - ...
428 - $P_m=(m, f(m))$
429
430---
431
432##### Shamir's Secret Sharing - Secret recovery
433- in order to recover the secret $s$, we will need a minimum of $n$ points of the polynomial
434 - the order doesn't matter
435- with that $n$ parts, we do Lagrange Interpolation/Polynomial Interpolation, recovering the original polynomial
436
437---
438
439## QAP
440
441<div style="font-size:50%">
442
443$(\alpha_1(x)s_1 + \alpha_2(x)s_2 + ... + \alpha_n(x)s_n) \cdot (\beta_1(x)s_1 + \beta_2(x)s_2 + ... + \beta_n(x)s_n) - (\gamma_1(x)s_1 + \gamma_2(x)s_2 + ... + \gamma_n(x)s_n) = P(x)$
444
445|----------------------- $A(x)$ -----------------------|------------------------ $B(x)$ -----------------------|------------------------ $C(x)$ ------------------------|
446
447</div>
448
449<div style="font-size:70%">
450
451- $P(x) = A(x)B(x)-C(x)$
452- $P(x) = Z(x) h(x)$
453- $Z(x)$: divisor polynomial
454 - $Z(x) = (x - x_1)(x-x_2)...(x-x_m) => ...=> (x_1, 0), (x_2, 0), ..., (x_m, 0)$
455 - optimizations with FFT
456- $h(x) = P(x) / Z(x)$
457
458</div>
459
460---
461
462*The following explanation is for the [Pinocchio protocol](https://eprint.iacr.org/2013/279.pdf), all the examples will be for this protocol. The [Groth16](https://eprint.iacr.org/2016/260.pdf) is explained also in the end of this slides.*
463
464---
465
466## Trusted Setup
467- concept
468- $\tau$ (Tau)
469- "Toxic waste"
470- Proving Key
471- Verification Key
472
473---
474
475$g_1 t^0, g_1 t^1, g_1 t^2, g_1 t^3, g_1 t^4, ...$
476$g_2 t^0, g_2 t^1, g_2 t^2, g_2 t^3, g_2 t^4, ...$
477
478---
479
480Proving Key:
481$pk = (C, pk_A, pk_A', pk_B, pk_B', pk_C, pk_C', pk_H)$ where:
482- $pk_A = \{ A_i(\tau) \rho_A P_1 \}^{m+3}_{i=0}$
483- $pk_A' = \{ A_i(\tau) \alpha_A \rho_A P_1 \}^{m+3}_{i=n+1}$
484- $pk_B = \{ B_i(\tau) \rho_B P_2 \}^{m+3}_{i=0}$
485- $pk_B' = \{ B_i(\tau) \alpha_B \rho_B P_1 \}^{m+3}_{i=0}$
486- $pk_C = \{ C_i(\tau) \rho_C P_1 \}^{m+3}_{i=0} = \{C_i(\tau) \rho_A \rho_B P_1\}^{m+3}_{i=0}$
487- $pk_C' = \{ C_i(\tau) \alpha_C \rho_C P_1 \}^{m+3}_{i=0} = \{ C_i(\tau) \alpha_C \rho_A \rho_B P_1 \}^{m+3}_{i=0}$
488- $pk_K = \{ \beta (A_i(\tau) \rho_A + B_i(\tau) \rho_B C_i(\tau) \rho_A \rho_B) P_1 \} ^{m+3}_{i=0}$
489- $pk_H = \{ \tau^i P_1 \}^d_{i=0}$
490
491where:
492- $d$: degree of polynomial $Z(x)$
493- $m$: number of circuit signals
494
495---
496
497Verification Key:
498$vk = (vk_A, vk_B, vk_C, vk_\gamma, vk^1_{\beta\gamma}, vk^2_{\beta\gamma}, vk_Z, vk_{IC})$
499- $vk_A = \alpha_A P_2$, $vk_B = \alpha_B P_1$, $vk_C = \alpha_C P_2$
500- $vk_{\beta\gamma} = \gamma P_2$, $vk^1_{\beta\gamma} = \beta\gamma P_1$, $vk^2_{\beta\gamma} = \beta\gamma P_2$
501- $vk_Z = Z(\tau) \rho_A \rho_B P_2$, $vk_{IC} = (A_i(\tau) \rho_A P_1)^n_{i=0}$
502
503---
504
505```go
506type Pk struct { // Proving Key pk:=(pkA, pkB, pkC, pkH)
507 G1T [][3]*big.Int // t encrypted in G1 curve, G1T == Pk.H
508 A [][3]*big.Int
509 B [][3][2]*big.Int
510 C [][3]*big.Int
511 Kp [][3]*big.Int
512 Ap [][3]*big.Int
513 Bp [][3]*big.Int
514 Cp [][3]*big.Int
515 Z []*big.Int
516}
517
518type Vk struct {
519 Vka [3][2]*big.Int
520 Vkb [3]*big.Int
521 Vkc [3][2]*big.Int
522 IC [][3]*big.Int
523 G1Kbg [3]*big.Int // g1 * Kbeta * Kgamma
524 G2Kbg [3][2]*big.Int // g2 * Kbeta * Kgamma
525 G2Kg [3][2]*big.Int // g2 * Kgamma
526 Vkz [3][2]*big.Int
527}
528```
529
530---
531
532```go
533// Setup is the data structure holding the Trusted Setup data. The Setup.Toxic sub struct must be destroyed after the GenerateTrustedSetup function is completed
534type Setup struct {
535 Toxic struct {
536 T *big.Int // trusted setup secret
537 Ka *big.Int
538 Kb *big.Int
539 Kc *big.Int
540 Kbeta *big.Int
541 Kgamma *big.Int
542 RhoA *big.Int
543 RhoB *big.Int
544 RhoC *big.Int
545 }
546 Pk Pk
547 Vk Vk
548}
549```
550
551---
552
553## Proofs generation
554- $A, B, C, Z$ (from the QAP)
555- random $\delta_1, \delta_2, \delta_3$
556- $H(z)= \dfrac{A(z)B(z)-C(z)}{Z(z)}$
557 - $A(z) = A_0(z) + \sum_{i=1}^m s_i A_i(x) + \delta_1 Z(z)$
558 - $B(z) = B_0(z) + \sum_{i=1}^m s_i B_i(x) + \delta_2 Z(z)$
559 - $C(z) = C_0(z) + \sum_{i=1}^m s_i B_i(x) + \delta_2 Z(z)$
560(where $m$ is the number of public inputs)
561
562---
563
564- $\pi_A = <c, pk_A>$
565- $\pi_A' = <c, pk_A'>$
566- $\pi_B = <c, pk_B>$
567 - example:
568 ```go
569 for i := 0; i < circuit.NVars; i++ {
570 proof.PiB = Utils.Bn.G2.Add(proof.PiB, Utils.Bn.G2.MulScalar(pk.B[i], w[i]))
571 proof.PiBp = Utils.Bn.G1.Add(proof.PiBp, Utils.Bn.G1.MulScalar(pk.Bp[i], w[i]))
572 }
573 ```
574($c=1+witness+\delta_1+\delta_2+\delta_3$
575- $\pi_B' = <c, pk_B'>$
576- $\pi_C = <c, pk_C>$
577- $\pi_C' = <c, pk_C'>$
578- $\pi_K = <c, pk_K>$
579- $\pi_H = <h, pk_KH>$
580- proof: $\pi = (\pi_A, \pi_A', \pi_B, \pi_B', \pi_C, \pi_C', \pi_K, \pi_H$
581
582---
583
584## Proofs verification
585
586<img src="imgs/cat03.jpeg" style="float:right; width:300px;" />
587
588- $vk_{kx} = vk_{IC,0} + \sum_{i=1}^n x_i vk_{IC,i}$
589
590Verification:
591- $e(\pi_A, vk_a) == e(\pi_{A'}, g_2)$
592- $e(vk_b, \pi_B) == e(\pi_{B'}, g_2)$
593- $e(\pi_C, vk_c) == e(\pi_{C'}, g_2)$
594- $e(vk_{kx}+\pi_A, \pi_B) == e(\pi_H, vk_{kz}) \cdot e(\pi_C, g_2)$
595- $e(vk_{kx} + \pi_A + \pi_C, V_{\beta\gamma}^2) \cdot e(vk_{\beta\gamma}^1, \pi_B) == e(\pi_k, vk_{\gamma}^1)$
596
597---
598
599
600<div style="font-size:60%">
601Example (whiteboard):
602<br><br>
603
604$\dfrac{
605 e(\pi_A, \pi_B)
606}{
607 e(\pi_C, g_2)
608}
609= e(g_1 h(t), g_2 z(t))
610$
611<br>
612$\dfrac{
613 e(A_1 + A_2 + ... + A_n, B_1 + B_2 + ... + B_n)
614}{
615 e(C_1 + C_2 + ... + C_n, g_2)
616}
617= e(g_1 h(t), g_2 z(t))
618$
619<br>
620$\dfrac{
621 e(g_1 \alpha_1(t) s_1 + g_1 \alpha_2(t) s_2 + ... + g_1 \alpha_n(t) s_n, g_2 \beta_1(t)s_1 + g_2 \beta_2(t) s_2 + ... + g_2 \beta_n(t) s_n)
622}{
623 e(g_1 \gamma_1(t) s_1 + g_1 \gamma_2(t) s_2 + ... + g_1 \gamma_n(t) s_n, g_2)
624}
625= e(g_1 h(t), g_2 z(t))
626$
627<br>
628$
629e(g_1 \alpha_1(t) s_1 + g_1 \alpha_2(t) s_2 + ... + g_1 \alpha_n(t) s_n, g_2 \beta_1(t)s_1 + g_2 \beta_2(t) s_2 + ... + g_2 \beta_n(t) s_n)$
630$= e(g_1 h(t), g_2 z(t)) \cdot e(g_1 \gamma_1(t) s_1 + g_1 \gamma_2(t) s_2 + ... + g_1 \gamma_n(t) s_n, g_2)
631$
632
633</div>
634
635
636---
637
638## Groth16
639
640
641<img src="imgs/cat02.jpeg" style="float:right; width:300px;" />
642
643### Trusted Setup
644$\tau = \alpha, \beta, \gamma, \delta, x$
645
646$\sigma_1 =$
647- $\alpha, \beta, \delta, \{ x^i\}_{i=0}^{n-1}$
648
649- $\{
650\dfrac{
651\beta u_i(x) + \alpha v_i(x) + w_i(x)
652}{
653\gamma
654}
655\}_{i=0}^l$
656
657- $\{
658\dfrac{
659\beta u_i(x) + \alpha v_i(x) + w_i(x)
660}{
661\delta
662}
663\}_{i=l+1}^m$
664
665- $\{
666\dfrac{x^i t(x)}{\delta}
667\}_{i=0}^{n-2}$
668
669$\sigma_2 = (\beta, \gamma, \delta, \{ x^i \}_{i=0}^{n-1})$
670
671*(where $u_i(x), v_i(x), w_i(x)$ are the $QAP$)*
672
673---
674
675```go
676type Pk struct { // Proving Key
677 BACDelta [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / δ } from l+1 to m
678 Z []*big.Int
679 G1 struct {
680 Alpha [3]*big.Int
681 Beta [3]*big.Int
682 Delta [3]*big.Int
683 At [][3]*big.Int // {a(τ)} from 0 to m
684 BACGamma [][3]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m
685 }
686 G2 struct {
687 Beta [3][2]*big.Int
688 Gamma [3][2]*big.Int
689 Delta [3][2]*big.Int
690 BACGamma [][3][2]*big.Int // {( βui(x)+αvi(x)+wi(x) ) / γ } from 0 to m
691 }
692 PowersTauDelta [][3]*big.Int // powers of τ encrypted in G1 curve, divided by δ
693}
694```
695
696---
697
698```go
699type Vk struct {
700 IC [][3]*big.Int
701 G1 struct {
702 Alpha [3]*big.Int
703 }
704 G2 struct {
705 Beta [3][2]*big.Int
706 Gamma [3][2]*big.Int
707 Delta [3][2]*big.Int
708 }
709}
710```
711
712
713---
714
715```go
716// Setup is the data structure holding the Trusted Setup data. The Setup.Toxic sub struct must be destroyed after the GenerateTrustedSetup function is completed
717type Setup struct {
718 Toxic struct {
719 T *big.Int // trusted setup secret
720 Kalpha *big.Int
721 Kbeta *big.Int
722 Kgamma *big.Int
723 Kdelta *big.Int
724 }
725 Pk Pk
726 Vk Vk
727}
728```
729
730---
731
732#
733## Proofs Generation
734$\pi_A=\alpha + \sum_{i=0}^m \alpha_i u_i(x) + r \delta$
735$\pi_B=\beta + \sum_{i=0}^m \alpha_i v_i(x) + s \delta$
736
737<div style="font-size:80%;">
738
739$\pi_C = \dfrac{
740\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)
741}{
742\delta
743} + \pi_As + \pi_Br -rs\delta$
744
745</div>
746
747$\pi=\pi_A^1, \pi_B^1, \pi_C^2$
748
749---
750
751### Proof Verification
752
753<div style="font-size:75%;">
754
755$[\pi_A]_1 \cdot [\pi_B]_2 = [\alpha]_1 \cdot [\beta]_2 +
756\sum_{i=0}^l a_i [
757\dfrac{
758\beta u_i(x) + \alpha v_i(x) + w_i(x)
759}{
760\gamma
761}
762]_1
763\cdot [\gamma]_2 + [\pi_C]_1 \cdot [\delta]_2
764$
765
766</div>
767
768$e(\pi_A, \pi_B) = e(\alpha, \beta) \cdot e(pub, \gamma) \cdot e(\pi_C, \delta)$
769
770
771---
772
773## How we use zkSNARKs in iden3
774- proving a credentials without revealing it's content
775- proving that an identity has a claim issued by another identity, without revealing all the data
776- proving any property of an identity
777- $ITF$ (Identity Transition Function), a way to prove with a zkSNARK that an identity has been updated following the defined protocol
778 - identities can not cheat when issuing claims
779- etc
780
781## Other ideas for free time side project
782- Zendermint (Tendermint + zkSNARKs)
783
784---
785
786
787<img src="imgs/cat05.jpeg" style="float:right; width:300px;" />
788
789## zkSNARK libraries
790- [bellman](https://github.com/zkcrypto/bellman) (rust)
791- [libsnark](https://github.com/scipr-lab/libsnark) (c++)
792- [snarkjs](https://github.com/iden3/snarkjs) (javascript)
793- [websnark](https://github.com/iden3/websnark) (wasm)
794- [go-snark](https://github.com/arnaucube/go-snark) (golang) <span style="font-size:80%;">[do not use in production]<span>
795
796## Circuit languages
797| language | snark library with which plugs in |
798|-----|-----|
799| [Zokrates](https://github.com/Zokrates/ZoKrates) | libsnark, bellman |
800| [Snarky](https://github.com/o1-labs/snarky) | libsnark |
801| [circom](https://github.com/iden3/circom) | snarkjs, websnark, bellman |
802| [go-snark-circuit](https://github.com/arnaucube/go-snark) | go-snark |
803
804---
805
806## Utilities (Elliptic curve & Hash functions) inside the zkSNARK
807- we work over $F_r$, where $r=$`21888242871839275222246405745257275088548364400416034343698204186575808495617`
808
809- BabyJubJub
810- Mimc
811- Poseidon
812
813---
814
815##### *Utilities (Elliptic curve & Hash functions) inside the zkSNARK*
816
817### BabyJubJub
818- explaination: https://medium.com/zokrates/efficient-ecc-in-zksnarks-using-zokrates-bd9ae37b8186
819- implementations:
820 - go: https://github.com/iden3/go-iden3-crypto
821 - javascript & circom: https://github.com/iden3/circomlib
822 - rust: https://github.com/arnaucube/babyjubjub-rs
823 - c++: https://github.com/barryWhiteHat/baby_jubjub_ecc
824
825---
826
827##### *Utilities (Elliptic curve & Hash functions) inside the zkSNARK*
828
829### Mimc7
830- explaination: https://eprint.iacr.org/2016/492.pdf
831- implementations in:
832 - go: https://github.com/iden3/go-iden3-crypto
833 - javascript & circom: https://github.com/iden3/circomlib
834 - rust: https://github.com/arnaucube/mimc-rs
835
836---
837
838##### *Utilities (Elliptic curve & Hash functions) inside the zkSNARK*
839
840### Poseidon
841- explaination: https://eprint.iacr.org/2019/458.pdf
842- implementations in:
843 - go: https://github.com/iden3/go-iden3-crypto
844 - javascript & circom: https://github.com/iden3/circomlib
845
846---
847
848# References
849- `Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture`, Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza https://eprint.iacr.org/2013/879.pdf
850- `Pinocchio: Nearly practical verifiable computation`, Bryan Parno, Craig Gentry, Jon Howell, Mariana Raykova https://eprint.iacr.org/2013/279.pdf
851- `On the Size of Pairing-based Non-interactive Arguments`, Jens Groth https://eprint.iacr.org/2016/260.pdf
852- (also all the links through the slides)
853
854---
855
856<div style="text-align:center;">
857Thank you very much
858<br>
859<img src="imgs/cat00.jpeg" style="width:300px;" />
860</div>
861
862
863<div style="float:right; text-align:right;">
864 <img style="width:80px" src="imgs/arnaucube.png" /> <br>
865
866[arnaucube.com](https://arnaucube.com)
867[github.com/arnaucube](https://github.com/arnaucube)
868[twitter.com/arnaucube](https://twitter.com/arnaucube)
869
870 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png" /></a>
871 2019-08-20
872</div>
873
874<img style="width:200px;" src="imgs/iden3.png" /> <br>
875[iden3.io](https://iden3.io)
876[github.com/iden3](https://github.com/iden3)
877[twitter.com/identhree](https://twitter.com/identhree)