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