go-snark/bn128/README.md
bn128/README.mdRaw
1## Bn128
2[](https://godoc.org/github.com/arnaucube/go-snark/bn128) bn128
3Implementation of the bn128 pairing in Go.
4
5
6Implementation followng the information and the implementations from:
7- `Multiplication and Squaring on Pairing-Friendly
8Fields`, Augusto Jun Devegili, Colm Ó hÉigeartaigh, Michael Scott, and Ricardo Dahab https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf
9- `Optimal Pairings`, Frederik Vercauteren https://www.cosic.esat.kuleuven.be/bcrypt/optimal.pdf , https://eprint.iacr.org/2008/096.pdf
10- `Double-and-Add with Relative Jacobian
11Coordinates`, Björn Fay https://eprint.iacr.org/2014/1014.pdf
12- `Fast and Regular Algorithms for Scalar Multiplication
13over Elliptic Curves`, Matthieu Rivain https://eprint.iacr.org/2011/338.pdf
14- `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
15- `New software speed records for cryptographic pairings`, Michael Naehrig, Ruben Niederhagen, Peter Schwabe https://cryptojedi.org/papers/dclxvi-20100714.pdf
16- `Implementing Cryptographic Pairings over Barreto-Naehrig Curves`, Augusto Jun Devegili, Michael Scott, Ricardo Dahab https://eprint.iacr.org/2007/390.pdf
17- https://github.com/zcash/zcash/tree/master/src/snark
18- https://github.com/iden3/snarkjs
19- https://github.com/ethereum/py_ecc/tree/master/py_ecc/bn128
20
21- [x] Fq, Fq2, Fq6, Fq12 operations
22- [x] G1, G2 operations
23- [x] preparePairing
24- [x] PreComupteG1, PreComupteG2
25- [x] DoubleStep, AddStep
26- [x] MillerLoop
27- [x] Pairing
28
29### Installation
30```
31go get github.com/arnaucube/bn128
32```
33
34#### Usage
35
36- Pairing
37```go
38bn128, err := NewBn128()
39assert.Nil(t, err)
40
41big25 := big.NewInt(int64(25))
42big30 := big.NewInt(int64(30))
43
44g1a := bn128.G1.MulScalar(bn128.G1.G, big25)
45g2a := bn128.G2.MulScalar(bn128.G2.G, big30)
46
47g1b := bn128.G1.MulScalar(bn128.G1.G, big30)
48g2b := bn128.G2.MulScalar(bn128.G2.G, big25)
49
50pA, err := bn128.Pairing(g1a, g2a)
51assert.Nil(t, err)
52pB, err := bn128.Pairing(g1b, g2b)
53assert.Nil(t, err)
54assert.True(t, bn128.Fq12.Equal(pA, pB))
55```
56
57#### Test
58```
59go test -v
60```
61
62##### Internal operations more deeply
63
64First let's assume that we have these three basic functions to convert integer compositions to big integer compositions:
65```go
66func iToBig(a int) *big.Int {
67 return big.NewInt(int64(a))
68}
69
70func iiToBig(a, b int) [2]*big.Int {
71 return [2]*big.Int{iToBig(a), iToBig(b)}
72}
73
74func iiiToBig(a, b int) [2]*big.Int {
75 return [2]*big.Int{iToBig(a), iToBig(b)}
76}
77```
78- Finite Fields (1, 2, 6, 12) operations
79```go
80// new finite field of order 1
81fq1 := NewFq(iToBig(7))
82
83// basic operations of finite field 1
84res := fq1.Add(iToBig(4), iToBig(4))
85res = fq1.Double(iToBig(5))
86res = fq1.Sub(iToBig(5), iToBig(7))
87res = fq1.Neg(iToBig(5))
88res = fq1.Mul(iToBig(5), iToBig(11))
89res = fq1.Inverse(iToBig(4))
90res = fq1.Square(iToBig(5))
91
92// new finite field of order 2
93nonResidueFq2str := "-1" // i/j
94nonResidueFq2, ok := new(big.Int).SetString(nonResidueFq2str, 10)
95fq2 := Fq2{fq1, nonResidueFq2}
96nonResidueFq6 := iiToBig(9, 1)
97
98// basic operations of finite field of order 2
99res := fq2.Add(iiToBig(4, 4), iiToBig(3, 4))
100res = fq2.Double(iiToBig(5, 3))
101res = fq2.Sub(iiToBig(5, 3), iiToBig(7, 2))
102res = fq2.Neg(iiToBig(4, 4))
103res = fq2.Mul(iiToBig(4, 4), iiToBig(3, 4))
104res = fq2.Inverse(iiToBig(4, 4))
105res = fq2.Div(iiToBig(4, 4), iiToBig(3, 4))
106res = fq2.Square(iiToBig(4, 4))
107
108
109// new finite field of order 6
110nonResidueFq6 := iiToBig(9, 1) // TODO
111fq6 := Fq6{fq2, nonResidueFq6}
112
113// define two new values of Finite Field 6, in order to be able to perform the operations
114a := [3][2]*big.Int{
115 iiToBig(1, 2),
116 iiToBig(3, 4),
117 iiToBig(5, 6)}
118b := [3][2]*big.Int{
119 iiToBig(12, 11),
120 iiToBig(10, 9),
121 iiToBig(8, 7)}
122
123// basic operations of finite field order 6
124res := fq6.Add(a, b)
125res = fq6.Sub(a, b)
126res = fq6.Mul(a, b)
127divRes := fq6.Div(mulRes, b)
128
129
130// new finite field of order 12
131q, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208583", 10) // i
132if !ok {
133 fmt.Println("error parsing string to big integer")
134}
135
136fq1 := NewFq(q)
137nonResidueFq2, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208582", 10) // i
138assert.True(t, ok)
139nonResidueFq6 := iiToBig(9, 1)
140
141fq2 := Fq2{fq1, nonResidueFq2}
142fq6 := Fq6{fq2, nonResidueFq6}
143fq12 := Fq12{fq6, fq2, nonResidueFq6}
144
145```
146
147- G1 operations
148```go
149bn128, err := NewBn128()
150assert.Nil(t, err)
151
152r1 := big.NewInt(int64(33))
153r2 := big.NewInt(int64(44))
154
155gr1 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r1))
156gr2 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r2))
157
158grsum1 := bn128.G1.Add(gr1, gr2)
159r1r2 := bn128.Fq1.Add(r1, r2)
160grsum2 := bn128.G1.MulScalar(bn128.G1.G, r1r2)
161
162a := bn128.G1.Affine(grsum1)
163b := bn128.G1.Affine(grsum2)
164assert.Equal(t, a, b)
165assert.Equal(t, "0x2f978c0ab89ebaa576866706b14787f360c4d6c3869efe5a72f7c3651a72ff00", utils.BytesToHex(a[0].Bytes()))
166assert.Equal(t, "0x12e4ba7f0edca8b4fa668fe153aebd908d322dc26ad964d4cd314795844b62b2", utils.BytesToHex(a[1].Bytes()))
167```
168
169- G2 operations
170```go
171bn128, err := NewBn128()
172assert.Nil(t, err)
173
174r1 := big.NewInt(int64(33))
175r2 := big.NewInt(int64(44))
176
177gr1 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r1))
178gr2 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r2))
179
180grsum1 := bn128.G2.Add(gr1, gr2)
181r1r2 := bn128.Fq1.Add(r1, r2)
182grsum2 := bn128.G2.MulScalar(bn128.G2.G, r1r2)
183
184a := bn128.G2.Affine(grsum1)
185b := bn128.G2.Affine(grsum2)
186assert.Equal(t, a, b)
187```