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