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
5Not finished, work in progress (doing this in my free time, so I don't have much time).
6
7
8
9#### Test
10```
11go test ./... -v
12```
13
14## R1CS to Quadratic Arithmetic Program
15- `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
16- Vitalik Buterin blog post about QAP https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
17- Ariel Gabizon in Zcash blog https://z.cash/blog/snark-explain5
18- Lagrange polynomial Wikipedia article https://en.wikipedia.org/wiki/Lagrange_polynomial
19
20#### Usage
21- R1CS to QAP
22```go
23b0 := big.NewFloat(float64(0))
24b1 := big.NewFloat(float64(1))
25b5 := big.NewFloat(float64(5))
26a := [][]*big.Float{
27 []*big.Float{b0, b1, b0, b0, b0, b0},
28 []*big.Float{b0, b0, b0, b1, b0, b0},
29 []*big.Float{b0, b1, b0, b0, b1, b0},
30 []*big.Float{b5, b0, b0, b0, b0, b1},
31}
32b := [][]*big.Float{
33 []*big.Float{b0, b1, b0, b0, b0, b0},
34 []*big.Float{b0, b1, b0, b0, b0, b0},
35 []*big.Float{b1, b0, b0, b0, b0, b0},
36 []*big.Float{b1, b0, b0, b0, b0, b0},
37}
38c := [][]*big.Float{
39 []*big.Float{b0, b0, b0, b1, b0, b0},
40 []*big.Float{b0, b0, b0, b0, b1, b0},
41 []*big.Float{b0, b0, b0, b0, b0, b1},
42 []*big.Float{b0, b0, b1, b0, b0, b0},
43}
44alpha, beta, gamma, z := R1CSToQAP(a, b, c)
45fmt.Println(alpha)
46fmt.Println(beta)
47fmt.Println(gamma)
48fmt.Println(z)
49/*
50out:
51alpha: [[-5 9.166666666666666 -5 0.8333333333333334] [8 -11.333333333333332 5 -0.6666666666666666] [0 0 0 0] [-6 9.5 -4 0.5] [4 -7 3.5 -0.5] [-1 1.8333333333333333 -1 0.16666666666666666]]
52beta: [[3 -5.166666666666667 2.5 -0.33333333333333337] [-2 5.166666666666667 -2.5 0.33333333333333337] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
53gamma: [[0 0 0 0] [0 0 0 0] [-1 1.8333333333333333 -1 0.16666666666666666] [4 -4.333333333333333 1.5 -0.16666666666666666] [-6 9.5 -4 0.5] [4 -7 3.5 -0.5]]
54z: [24 -50 35 -10 1]
55*/
56```
57
58## Bn128
59Implementation of the bn128 pairing in Go.
60
61
62Implementation followng the information and the implementations from:
63- `Multiplication and Squaring on Pairing-Friendly
64Fields`, Augusto Jun Devegili, Colm Ó hÉigeartaigh, Michael Scott, and Ricardo Dahab https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf
65- `Optimal Pairings`, Frederik Vercauteren https://www.cosic.esat.kuleuven.be/bcrypt/optimal.pdf , https://eprint.iacr.org/2008/096.pdf
66- `Double-and-Add with Relative Jacobian
67Coordinates`, Björn Fay https://eprint.iacr.org/2014/1014.pdf
68- `Fast and Regular Algorithms for Scalar Multiplication
69over Elliptic Curves`, Matthieu Rivain https://eprint.iacr.org/2011/338.pdf
70- `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
71- `New software speed records for cryptographic pairings`, Michael Naehrig, Ruben Niederhagen, Peter Schwabe https://cryptojedi.org/papers/dclxvi-20100714.pdf
72- `Implementing Cryptographic Pairings over Barreto-Naehrig Curves`, Augusto Jun Devegili, Michael Scott, Ricardo Dahab https://eprint.iacr.org/2007/390.pdf
73- https://github.com/zcash/zcash/tree/master/src/snark
74- https://github.com/iden3/snarkjs
75- https://github.com/ethereum/py_ecc/tree/master/py_ecc/bn128
76
77
78#### Usage
79
80- Pairing
81```go
82bn128, err := NewBn128()
83assert.Nil(t, err)
84
85big25 := big.NewInt(int64(25))
86big30 := big.NewInt(int64(30))
87
88g1a := bn128.G1.MulScalar(bn128.G1.G, big25)
89g2a := bn128.G2.MulScalar(bn128.G2.G, big30)
90
91g1b := bn128.G1.MulScalar(bn128.G1.G, big30)
92g2b := bn128.G2.MulScalar(bn128.G2.G, big25)
93
94pA, err := bn128.Pairing(g1a, g2a)
95assert.Nil(t, err)
96pB, err := bn128.Pairing(g1b, g2b)
97assert.Nil(t, err)
98assert.True(t, bn128.Fq12.Equal(pA, pB))
99```