go-snark/README.md
README.mdRaw
1# go-snark [](https://goreportcard.com/report/github.com/arnaucube/go-snark)
2
3zk-SNARK library implementation in Go
4
5
6#### Test
7```
8go test ./... -v
9```
10
11
12## R1CS to Quadratic Arithmetic Program
13- `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
14- Vitalik Buterin blog post about QAP https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
15- Ariel Gabizon in Zcash blog https://z.cash/blog/snark-explain5
16- Lagrange polynomial Wikipedia article https://en.wikipedia.org/wiki/Lagrange_polynomial
17
18#### Usage
19- R1CS to QAP
20```go
21pf := NewPolynomialField(f)
22
23b0 := big.NewInt(int64(0))
24b1 := big.NewInt(int64(1))
25b3 := big.NewInt(int64(3))
26b5 := big.NewInt(int64(5))
27b9 := big.NewInt(int64(9))
28b27 := big.NewInt(int64(27))
29b30 := big.NewInt(int64(30))
30b35 := big.NewInt(int64(35))
31a := [][]*big.Int{
32 []*big.Int{b0, b1, b0, b0, b0, b0},
33 []*big.Int{b0, b0, b0, b1, b0, b0},
34 []*big.Int{b0, b1, b0, b0, b1, b0},
35 []*big.Int{b5, b0, b0, b0, b0, b1},
36}
37b := [][]*big.Int{
38 []*big.Int{b0, b1, b0, b0, b0, b0},
39 []*big.Int{b0, b1, b0, b0, b0, b0},
40 []*big.Int{b1, b0, b0, b0, b0, b0},
41 []*big.Int{b1, b0, b0, b0, b0, b0},
42}
43c := [][]*big.Int{
44 []*big.Int{b0, b0, b0, b1, b0, b0},
45 []*big.Int{b0, b0, b0, b0, b1, b0},
46 []*big.Int{b0, b0, b0, b0, b0, b1},
47 []*big.Int{b0, b0, b1, b0, b0, b0},
48}
49alphas, betas, gammas, zx := pf.R1CSToQAP(a, b, c)
50fmt.Println(alphas)
51fmt.Println(betas)
52fmt.Println(gammas)
53fmt.Println(z)
54
55w := []*big.Int{b1, b3, b35, b9, b27, b30}
56ax, bx, cx, px := pf.CombinePolynomials(w, alphas, betas, gammas)
57fmt.Println(ax)
58fmt.Println(bx)
59fmt.Println(cx)
60fmt.Println(px)
61
62hx := pf.DivisorPolinomial(px, zx)
63fmt.Println(hx)
64```
65
66## Bn128
67Implementation of the bn128 pairing in Go.
68
69
70Implementation followng the information and the implementations from:
71- `Multiplication and Squaring on Pairing-Friendly
72Fields`, Augusto Jun Devegili, Colm Ó hÉigeartaigh, Michael Scott, and Ricardo Dahab https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf
73- `Optimal Pairings`, Frederik Vercauteren https://www.cosic.esat.kuleuven.be/bcrypt/optimal.pdf , https://eprint.iacr.org/2008/096.pdf
74- `Double-and-Add with Relative Jacobian
75Coordinates`, Björn Fay https://eprint.iacr.org/2014/1014.pdf
76- `Fast and Regular Algorithms for Scalar Multiplication
77over Elliptic Curves`, Matthieu Rivain https://eprint.iacr.org/2011/338.pdf
78- `High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves`, Jean-Luc Beuchat, Jorge E. González-Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríguez-Henríquez, and Tadanori Teruya https://eprint.iacr.org/2010/354.pdf
79- `New software speed records for cryptographic pairings`, Michael Naehrig, Ruben Niederhagen, Peter Schwabe https://cryptojedi.org/papers/dclxvi-20100714.pdf
80- `Implementing Cryptographic Pairings over Barreto-Naehrig Curves`, Augusto Jun Devegili, Michael Scott, Ricardo Dahab https://eprint.iacr.org/2007/390.pdf
81- https://github.com/zcash/zcash/tree/master/src/snark
82- https://github.com/iden3/snarkjs
83- https://github.com/ethereum/py_ecc/tree/master/py_ecc/bn128
84
85
86#### Usage
87
88- Pairing
89```go
90bn128, err := NewBn128()
91assert.Nil(t, err)
92
93big25 := big.NewInt(int64(25))
94big30 := big.NewInt(int64(30))
95
96g1a := bn128.G1.MulScalar(bn128.G1.G, big25)
97g2a := bn128.G2.MulScalar(bn128.G2.G, big30)
98
99g1b := bn128.G1.MulScalar(bn128.G1.G, big30)
100g2b := bn128.G2.MulScalar(bn128.G2.G, big25)
101
102pA, err := bn128.Pairing(g1a, g2a)
103assert.Nil(t, err)
104pB, err := bn128.Pairing(g1b, g2b)
105assert.Nil(t, err)
106assert.True(t, bn128.Fq12.Equal(pA, pB))
107```
108
109
110---
111
112## Caution
113Not finished, work in progress (implementing this in my free time to understand it better, so I don't have much time).
114
115Thanks to @jbaylina, @bellesmarta, @adriamb for their explanations that helped to understand a little bit this.