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
30#### Usage
31
32- Pairing
33```go
34bn128, err := NewBn128()
35assert.Nil(t, err)
36
37big25 := big.NewInt(int64(25))
38big30 := big.NewInt(int64(30))
39
40g1a := bn128.G1.MulScalar(bn128.G1.G, big25)
41g2a := bn128.G2.MulScalar(bn128.G2.G, big30)
42
43g1b := bn128.G1.MulScalar(bn128.G1.G, big30)
44g2b := bn128.G2.MulScalar(bn128.G2.G, big25)
45
46pA, err := bn128.Pairing(g1a, g2a)
47assert.Nil(t, err)
48pB, err := bn128.Pairing(g1b, g2b)
49assert.Nil(t, err)
50assert.True(t, bn128.Fq12.Equal(pA, pB))
51```
52
53#### Test
54```
55go test -v
56```
57
58##### Internal operations more deeply
59
60First let's assume that we have these three basic functions to convert integer compositions to big integer compositions:
61```go
62func iToBig(a int) *big.Int {
63 return big.NewInt(int64(a))
64}
65
66func iiToBig(a, b int) [2]*big.Int {
67 return [2]*big.Int{iToBig(a), iToBig(b)}
68}
69
70func iiiToBig(a, b int) [2]*big.Int {
71 return [2]*big.Int{iToBig(a), iToBig(b)}
72}
73```
74- Finite Fields (1, 2, 6, 12) operations
75```go
76// new finite field of order 1
77fq1 := NewFq(iToBig(7))
78
79// basic operations of finite field 1
80res := fq1.Add(iToBig(4), iToBig(4))
81res = fq1.Double(iToBig(5))
82res = fq1.Sub(iToBig(5), iToBig(7))
83res = fq1.Neg(iToBig(5))
84res = fq1.Mul(iToBig(5), iToBig(11))
85res = fq1.Inverse(iToBig(4))
86res = fq1.Square(iToBig(5))
87
88// new finite field of order 2
89nonResidueFq2str := "-1" // i/j
90nonResidueFq2, ok := new(big.Int).SetString(nonResidueFq2str, 10)
91fq2 := Fq2{fq1, nonResidueFq2}
92nonResidueFq6 := iiToBig(9, 1)
93
94// basic operations of finite field of order 2
95res := fq2.Add(iiToBig(4, 4), iiToBig(3, 4))
96res = fq2.Double(iiToBig(5, 3))
97res = fq2.Sub(iiToBig(5, 3), iiToBig(7, 2))
98res = fq2.Neg(iiToBig(4, 4))
99res = fq2.Mul(iiToBig(4, 4), iiToBig(3, 4))
100res = fq2.Inverse(iiToBig(4, 4))
101res = fq2.Div(iiToBig(4, 4), iiToBig(3, 4))
102res = fq2.Square(iiToBig(4, 4))
103
104
105// new finite field of order 6
106nonResidueFq6 := iiToBig(9, 1) // TODO
107fq6 := Fq6{fq2, nonResidueFq6}
108
109// define two new values of Finite Field 6, in order to be able to perform the operations
110a := [3][2]*big.Int{
111 iiToBig(1, 2),
112 iiToBig(3, 4),
113 iiToBig(5, 6)}
114b := [3][2]*big.Int{
115 iiToBig(12, 11),
116 iiToBig(10, 9),
117 iiToBig(8, 7)}
118
119// basic operations of finite field order 6
120res := fq6.Add(a, b)
121res = fq6.Sub(a, b)
122res = fq6.Mul(a, b)
123divRes := fq6.Div(mulRes, b)
124
125
126// new finite field of order 12
127q, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208583", 10) // i
128if !ok {
129 fmt.Println("error parsing string to big integer")
130}
131
132fq1 := NewFq(q)
133nonResidueFq2, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208582", 10) // i
134assert.True(t, ok)
135nonResidueFq6 := iiToBig(9, 1)
136
137fq2 := Fq2{fq1, nonResidueFq2}
138fq6 := Fq6{fq2, nonResidueFq6}
139fq12 := Fq12{fq6, fq2, nonResidueFq6}
140
141```
142
143- G1 operations
144```go
145bn128, err := NewBn128()
146assert.Nil(t, err)
147
148r1 := big.NewInt(int64(33))
149r2 := big.NewInt(int64(44))
150
151gr1 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r1))
152gr2 := bn128.G1.MulScalar(bn128.G1.G, bn128.Fq1.Copy(r2))
153
154grsum1 := bn128.G1.Add(gr1, gr2)
155r1r2 := bn128.Fq1.Add(r1, r2)
156grsum2 := bn128.G1.MulScalar(bn128.G1.G, r1r2)
157
158a := bn128.G1.Affine(grsum1)
159b := bn128.G1.Affine(grsum2)
160assert.Equal(t, a, b)
161assert.Equal(t, "0x2f978c0ab89ebaa576866706b14787f360c4d6c3869efe5a72f7c3651a72ff00", utils.BytesToHex(a[0].Bytes()))
162assert.Equal(t, "0x12e4ba7f0edca8b4fa668fe153aebd908d322dc26ad964d4cd314795844b62b2", utils.BytesToHex(a[1].Bytes()))
163```
164
165- G2 operations
166```go
167bn128, err := NewBn128()
168assert.Nil(t, err)
169
170r1 := big.NewInt(int64(33))
171r2 := big.NewInt(int64(44))
172
173gr1 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r1))
174gr2 := bn128.G2.MulScalar(bn128.G2.G, bn128.Fq1.Copy(r2))
175
176grsum1 := bn128.G2.Add(gr1, gr2)
177r1r2 := bn128.Fq1.Add(r1, r2)
178grsum2 := bn128.G2.MulScalar(bn128.G2.G, r1r2)
179
180a := bn128.G2.Affine(grsum1)
181b := bn128.G2.Affine(grsum2)
182assert.Equal(t, a, b)
183```