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