go-snark/bn128/bn128.go
bn128/bn128.goRaw
1package bn128
2
3import (
4 "bytes"
5 "errors"
6 "math/big"
7)
8
9type Bn128 struct {
10 Q *big.Int
11 Gg1 [2]*big.Int
12 Gg2 [2][2]*big.Int
13 NonResidueFq2 *big.Int
14 NonResidueFq6 [2]*big.Int
15 Fq1 Fq
16 Fq2 Fq2
17 Fq6 Fq6
18 Fq12 Fq12
19 G1 G1
20 G2 G2
21 LoopCount *big.Int
22 LoopCountNeg bool
23
24 TwoInv *big.Int
25 CoefB *big.Int
26 TwistCoefB [2]*big.Int
27 Twist [2]*big.Int
28 FrobeniusCoeffsC11 *big.Int
29 TwistMulByQX [2]*big.Int
30 TwistMulByQY [2]*big.Int
31 FinalExp *big.Int
32}
33
34func NewBn128() (Bn128, error) {
35 var b Bn128
36 q, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208583", 10) // i
37 if !ok {
38 return b, errors.New("err with q")
39 }
40 b.Q = q
41
42 b.Gg1 = [2]*big.Int{
43 big.NewInt(int64(1)),
44 big.NewInt(int64(2)),
45 }
46
47 g2_00, ok := new(big.Int).SetString("10857046999023057135944570762232829481370756359578518086990519993285655852781", 10)
48 if !ok {
49 return b, errors.New("err with g2_00")
50 }
51 g2_01, ok := new(big.Int).SetString("11559732032986387107991004021392285783925812861821192530917403151452391805634", 10)
52 if !ok {
53 return b, errors.New("err with g2_00")
54 }
55 g2_10, ok := new(big.Int).SetString("8495653923123431417604973247489272438418190587263600148770280649306958101930", 10)
56 if !ok {
57 return b, errors.New("err with g2_00")
58 }
59 g2_11, ok := new(big.Int).SetString("4082367875863433681332203403145435568316851327593401208105741076214120093531", 10)
60 if !ok {
61 return b, errors.New("err with g2_00")
62 }
63
64 b.Gg2 = [2][2]*big.Int{
65 [2]*big.Int{
66 g2_00,
67 g2_01,
68 },
69 [2]*big.Int{
70 g2_10,
71 g2_11,
72 },
73 }
74
75 b.Fq1 = NewFq(q)
76 b.NonResidueFq2, ok = new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208582", 10) // i
77 if !ok {
78 return b, errors.New("err with nonResidueFq2")
79 }
80 b.NonResidueFq6 = [2]*big.Int{
81 big.NewInt(int64(9)),
82 big.NewInt(int64(1)),
83 }
84
85 b.Fq2 = NewFq2(b.Fq1, b.NonResidueFq2)
86 b.Fq6 = NewFq6(b.Fq2, b.NonResidueFq6)
87 b.Fq12 = NewFq12(b.Fq6, b.Fq2, b.NonResidueFq6)
88
89 b.G1 = NewG1(b.Fq1, b.Gg1)
90 b.G2 = NewG2(b.Fq2, b.Gg2)
91
92 err := b.preparePairing()
93 if err != nil {
94 return b, err
95 }
96
97 return b, nil
98}
99
100func BigIsOdd(n *big.Int) bool {
101 one := big.NewInt(int64(1))
102 and := new(big.Int).And(n, one)
103 return bytes.Equal(and.Bytes(), big.NewInt(int64(1)).Bytes())
104}
105
106func (bn128 *Bn128) preparePairing() error {
107 var ok bool
108 bn128.LoopCount, ok = new(big.Int).SetString("29793968203157093288", 10)
109 if !ok {
110 return errors.New("err with LoopCount from string")
111 }
112
113 bn128.LoopCountNeg = false
114
115 bn128.TwoInv = bn128.Fq1.Inverse(big.NewInt(int64(2)))
116
117 bn128.CoefB = big.NewInt(int64(3))
118 bn128.Twist = [2]*big.Int{
119 big.NewInt(int64(9)),
120 big.NewInt(int64(1)),
121 }
122 bn128.TwistCoefB = bn128.Fq2.MulScalar(bn128.Fq2.Inverse(bn128.Twist), bn128.CoefB)
123
124 bn128.FrobeniusCoeffsC11, ok = new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208582", 10)
125 if !ok {
126 return errors.New("error parsing frobeniusCoeffsC11")
127 }
128
129 a, ok := new(big.Int).SetString("21575463638280843010398324269430826099269044274347216827212613867836435027261", 10)
130 if !ok {
131 return errors.New("error parsing a")
132 }
133 b, ok := new(big.Int).SetString("10307601595873709700152284273816112264069230130616436755625194854815875713954", 10)
134 if !ok {
135 return errors.New("error parsing b")
136 }
137 bn128.TwistMulByQX = [2]*big.Int{
138 a,
139 b,
140 }
141
142 a, ok = new(big.Int).SetString("2821565182194536844548159561693502659359617185244120367078079554186484126554", 10)
143 if !ok {
144 return errors.New("error parsing a")
145 }
146 b, ok = new(big.Int).SetString("3505843767911556378687030309984248845540243509899259641013678093033130930403", 10)
147 if !ok {
148 return errors.New("error parsing b")
149 }
150 bn128.TwistMulByQY = [2]*big.Int{
151 a,
152 b,
153 }
154
155 bn128.FinalExp, ok = new(big.Int).SetString("552484233613224096312617126783173147097382103762957654188882734314196910839907541213974502761540629817009608548654680343627701153829446747810907373256841551006201639677726139946029199968412598804882391702273019083653272047566316584365559776493027495458238373902875937659943504873220554161550525926302303331747463515644711876653177129578303191095900909191624817826566688241804408081892785725967931714097716709526092261278071952560171111444072049229123565057483750161460024353346284167282452756217662335528813519139808291170539072125381230815729071544861602750936964829313608137325426383735122175229541155376346436093930287402089517426973178917569713384748081827255472576937471496195752727188261435633271238710131736096299798168852925540549342330775279877006784354801422249722573783561685179618816480037695005515426162362431072245638324744480", 10)
156 if !ok {
157 return errors.New("error parsing finalExp")
158 }
159
160 return nil
161
162}
163
164func (bn128 Bn128) Pairing(p1 [3]*big.Int, p2 [3][2]*big.Int) ([2][3][2]*big.Int, error) {
165 pre1 := bn128.PreComputeG1(p1)
166 pre2, err := bn128.PreComputeG2(p2)
167 if err != nil {
168 return [2][3][2]*big.Int{}, err
169 }
170
171 r1 := bn128.MillerLoop(pre1, pre2)
172 res := bn128.FinalExponentiation(r1)
173 return res, nil
174}
175
176type AteG1Precomp struct {
177 Px *big.Int
178 Py *big.Int
179}
180
181func (bn128 Bn128) PreComputeG1(p [3]*big.Int) AteG1Precomp {
182 pCopy := bn128.G1.Affine(p)
183 res := AteG1Precomp{
184 Px: pCopy[0],
185 Py: pCopy[1],
186 }
187 return res
188}
189
190type EllCoeffs struct {
191 Ell0 [2]*big.Int
192 EllVW [2]*big.Int
193 EllVV [2]*big.Int
194}
195type AteG2Precomp struct {
196 Qx [2]*big.Int
197 Qy [2]*big.Int
198 Coeffs []EllCoeffs
199}
200
201func (bn128 Bn128) PreComputeG2(p [3][2]*big.Int) (AteG2Precomp, error) {
202 qCopy := bn128.G2.Affine(p)
203 res := AteG2Precomp{
204 qCopy[0],
205 qCopy[1],
206 []EllCoeffs{},
207 }
208 r := [3][2]*big.Int{
209 bn128.Fq2.Copy(qCopy[0]),
210 bn128.Fq2.Copy(qCopy[1]),
211 bn128.Fq2.One(),
212 }
213 var c EllCoeffs
214 for i := bn128.LoopCount.BitLen() - 2; i >= 0; i-- {
215 bit := bn128.LoopCount.Bit(i)
216
217 c, r = bn128.DoublingStep(r)
218 res.Coeffs = append(res.Coeffs, c)
219 if bit == 1 {
220 c, r = bn128.MixedAdditionStep(qCopy, r)
221 res.Coeffs = append(res.Coeffs, c)
222 }
223 }
224
225 q1 := bn128.G2.Affine(bn128.G2MulByQ(qCopy))
226 if !bn128.Fq2.Equal(q1[2], bn128.Fq2.One()) {
227 return res, errors.New("q1[2] != Fq2.One")
228 }
229 q2 := bn128.G2.Affine(bn128.G2MulByQ(q1))
230 if !bn128.Fq2.Equal(q2[2], bn128.Fq2.One()) {
231 return res, errors.New("q2[2] != Fq2.One")
232 }
233
234 if bn128.LoopCountNeg {
235 r[1] = bn128.Fq2.Neg(r[1])
236 }
237 q2[1] = bn128.Fq2.Neg(q2[1])
238
239 c, r = bn128.MixedAdditionStep(q1, r)
240 res.Coeffs = append(res.Coeffs, c)
241
242 c, r = bn128.MixedAdditionStep(q2, r)
243 res.Coeffs = append(res.Coeffs, c)
244
245 return res, nil
246}
247
248func (bn128 Bn128) DoublingStep(current [3][2]*big.Int) (EllCoeffs, [3][2]*big.Int) {
249 x := current[0]
250 y := current[1]
251 z := current[2]
252
253 a := bn128.Fq2.MulScalar(bn128.Fq2.Mul(x, y), bn128.TwoInv)
254 b := bn128.Fq2.Square(y)
255 c := bn128.Fq2.Square(z)
256 d := bn128.Fq2.Add(c, bn128.Fq2.Add(c, c))
257 e := bn128.Fq2.Mul(bn128.TwistCoefB, d)
258 f := bn128.Fq2.Add(e, bn128.Fq2.Add(e, e))
259 g := bn128.Fq2.MulScalar(bn128.Fq2.Add(b, f), bn128.TwoInv)
260 h := bn128.Fq2.Sub(
261 bn128.Fq2.Square(bn128.Fq2.Add(y, z)),
262 bn128.Fq2.Add(b, c))
263 i := bn128.Fq2.Sub(e, b)
264 j := bn128.Fq2.Square(x)
265 eSqr := bn128.Fq2.Square(e)
266 current[0] = bn128.Fq2.Mul(a, bn128.Fq2.Sub(b, f))
267 current[1] = bn128.Fq2.Sub(bn128.Fq2.Sub(bn128.Fq2.Square(g), eSqr),
268 bn128.Fq2.Add(eSqr, eSqr))
269 current[2] = bn128.Fq2.Mul(b, h)
270 res := EllCoeffs{
271 Ell0: bn128.Fq2.Mul(i, bn128.Twist),
272 EllVW: bn128.Fq2.Neg(h),
273 EllVV: bn128.Fq2.Add(j, bn128.Fq2.Add(j, j)),
274 }
275
276 return res, current
277}
278
279func (bn128 Bn128) MixedAdditionStep(base, current [3][2]*big.Int) (EllCoeffs, [3][2]*big.Int) {
280 x1 := current[0]
281 y1 := current[1]
282 z1 := current[2]
283 x2 := base[0]
284 y2 := base[1]
285
286 d := bn128.Fq2.Sub(x1, bn128.Fq2.Mul(x2, z1))
287 e := bn128.Fq2.Sub(y1, bn128.Fq2.Mul(y2, z1))
288 f := bn128.Fq2.Square(d)
289 g := bn128.Fq2.Square(e)
290 h := bn128.Fq2.Mul(d, f)
291 i := bn128.Fq2.Mul(x1, f)
292 j := bn128.Fq2.Sub(
293 bn128.Fq2.Add(h, bn128.Fq2.Mul(z1, g)),
294 bn128.Fq2.Add(i, i))
295
296 current[0] = bn128.Fq2.Mul(d, j)
297 current[1] = bn128.Fq2.Sub(
298 bn128.Fq2.Mul(e, bn128.Fq2.Sub(i, j)),
299 bn128.Fq2.Mul(h, y1))
300 current[2] = bn128.Fq2.Mul(z1, h)
301
302 coef := EllCoeffs{
303 Ell0: bn128.Fq2.Mul(
304 bn128.Twist,
305 bn128.Fq2.Sub(
306 bn128.Fq2.Mul(e, x2),
307 bn128.Fq2.Mul(d, y2))),
308 EllVW: d,
309 EllVV: bn128.Fq2.Neg(e),
310 }
311 return coef, current
312}
313func (bn128 Bn128) G2MulByQ(p [3][2]*big.Int) [3][2]*big.Int {
314 fmx := [2]*big.Int{
315 p[0][0],
316 bn128.Fq1.Mul(p[0][1], bn128.Fq1.Copy(bn128.FrobeniusCoeffsC11)),
317 }
318 fmy := [2]*big.Int{
319 p[1][0],
320 bn128.Fq1.Mul(p[1][1], bn128.Fq1.Copy(bn128.FrobeniusCoeffsC11)),
321 }
322 fmz := [2]*big.Int{
323 p[2][0],
324 bn128.Fq1.Mul(p[2][1], bn128.Fq1.Copy(bn128.FrobeniusCoeffsC11)),
325 }
326
327 return [3][2]*big.Int{
328 bn128.Fq2.Mul(bn128.TwistMulByQX, fmx),
329 bn128.Fq2.Mul(bn128.TwistMulByQY, fmy),
330 fmz,
331 }
332}
333
334func (bn128 Bn128) MillerLoop(pre1 AteG1Precomp, pre2 AteG2Precomp) [2][3][2]*big.Int {
335 // https://cryptojedi.org/papers/dclxvi-20100714.pdf
336 // https://eprint.iacr.org/2008/096.pdf
337
338 idx := 0
339 var c EllCoeffs
340 f := bn128.Fq12.One()
341
342 for i := bn128.LoopCount.BitLen() - 2; i >= 0; i-- {
343 bit := bn128.LoopCount.Bit(i)
344
345 c = pre2.Coeffs[idx]
346 idx++
347 f = bn128.Fq12.Square(f)
348
349 f = bn128.MulBy024(f,
350 c.Ell0,
351 bn128.Fq2.MulScalar(c.EllVW, pre1.Py),
352 bn128.Fq2.MulScalar(c.EllVV, pre1.Px))
353
354 if bit == 1 {
355 c = pre2.Coeffs[idx]
356 idx++
357 f = bn128.MulBy024(
358 f,
359 c.Ell0,
360 bn128.Fq2.MulScalar(c.EllVW, pre1.Py),
361 bn128.Fq2.MulScalar(c.EllVV, pre1.Px))
362 }
363 }
364 if bn128.LoopCountNeg {
365 f = bn128.Fq12.Inverse(f)
366 }
367
368 c = pre2.Coeffs[idx]
369 idx++
370 f = bn128.MulBy024(
371 f,
372 c.Ell0,
373 bn128.Fq2.MulScalar(c.EllVW, pre1.Py),
374 bn128.Fq2.MulScalar(c.EllVV, pre1.Px))
375
376 c = pre2.Coeffs[idx]
377 idx++
378
379 f = bn128.MulBy024(
380 f,
381 c.Ell0,
382 bn128.Fq2.MulScalar(c.EllVW, pre1.Py),
383 bn128.Fq2.MulScalar(c.EllVV, pre1.Px))
384
385 return f
386}
387
388func (bn128 Bn128) MulBy024(a [2][3][2]*big.Int, ell0, ellVW, ellVV [2]*big.Int) [2][3][2]*big.Int {
389 b := [2][3][2]*big.Int{
390 [3][2]*big.Int{
391 ell0,
392 bn128.Fq2.Zero(),
393 ellVV,
394 },
395 [3][2]*big.Int{
396 bn128.Fq2.Zero(),
397 ellVW,
398 bn128.Fq2.Zero(),
399 },
400 }
401 return bn128.Fq12.Mul(a, b)
402}
403
404func (bn128 Bn128) FinalExponentiation(r [2][3][2]*big.Int) [2][3][2]*big.Int {
405 res := bn128.Fq12.Exp(r, bn128.FinalExp)
406 return res
407}