snarkjs/src/bn128.js
src/bn128.jsRaw
1/*
2 Copyright 2018 0kims association.
3
4 This file is part of snarkjs.
5
6 snarkjs is a free software: you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as published by the
8 Free Software Foundation, either version 3 of the License, or (at your option)
9 any later version.
10
11 snarkjs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
15
16 You should have received a copy of the GNU General Public License along with
17 snarkjs. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const bigInt = require("./bigint.js");
21const assert = require("assert");
22
23const F1Field = require("./zqfield.js");
24const F2Field = require("./f2field.js");
25const F3Field = require("./f3field.js");
26const GCurve = require("./gcurve.js");
27
28class BN128 {
29
30 constructor() {
31
32 this.q = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208583");
33 this.r = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
34 this.g1 = [ bigInt(1), bigInt(2) ];
35 this.g2 = [
36 [
37 bigInt("10857046999023057135944570762232829481370756359578518086990519993285655852781"),
38 bigInt("11559732032986387107991004021392285783925812861821192530917403151452391805634")
39 ],
40 [
41 bigInt("8495653923123431417604973247489272438418190587263600148770280649306958101930"),
42 bigInt("4082367875863433681332203403145435568316851327593401208105741076214120093531")
43 ]
44 ];
45
46 this.nonResidueF2 = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208582");
47 this.nonResidueF6 = [ bigInt("9"), bigInt("1") ];
48
49 this.F1 = new F1Field(this.q);
50 this.F2 = new F2Field(this.F1, this.nonResidueF2);
51 this.G1 = new GCurve(this.F1, this.g1);
52 this.G2 = new GCurve(this.F2, this.g2);
53 this.F6 = new F3Field(this.F2, this.nonResidueF6);
54 this.F12 = new F2Field(this.F6, this.nonResidueF6);
55 const self = this;
56 this.F12._mulByNonResidue = function(a) {
57 return [self.F2.mul(this.nonResidue, a[2]), a[0], a[1]];
58 };
59
60 this._preparePairing();
61
62 }
63
64 _preparePairing() {
65 this.loopCount = bigInt("29793968203157093288");// CONSTANT
66
67 // Set loopCountNeg
68 if (this.loopCount.isNegative()) {
69 this.loopCount = this.loopCount.neg();
70 this.loopCountNeg = true;
71 } else {
72 this.loopCountNeg = false;
73 }
74
75 // Set loop_count_bits
76 let lc = this.loopCount;
77 this.loop_count_bits = []; // Constant
78 while (!lc.isZero()) {
79 this.loop_count_bits.push( lc.isOdd() );
80 lc = lc.shr(1);
81 }
82
83 this.two_inv = this.F1.inverse(bigInt(2));
84
85 this.coef_b = bigInt(3);
86 this.twist = [bigInt(9) , bigInt(1)];
87 this.twist_coeff_b = this.F2.mulScalar( this.F2.inverse(this.twist), this.coef_b );
88
89 this.frobenius_coeffs_c1_1 = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208582");
90 this.twist_mul_by_q_X =
91 [
92 bigInt("21575463638280843010398324269430826099269044274347216827212613867836435027261"),
93 bigInt("10307601595873709700152284273816112264069230130616436755625194854815875713954")
94 ];
95 this.twist_mul_by_q_Y =
96 [
97 bigInt("2821565182194536844548159561693502659359617185244120367078079554186484126554"),
98 bigInt("3505843767911556378687030309984248845540243509899259641013678093033130930403")
99 ];
100
101 this.final_exponent = bigInt("552484233613224096312617126783173147097382103762957654188882734314196910839907541213974502761540629817009608548654680343627701153829446747810907373256841551006201639677726139946029199968412598804882391702273019083653272047566316584365559776493027495458238373902875937659943504873220554161550525926302303331747463515644711876653177129578303191095900909191624817826566688241804408081892785725967931714097716709526092261278071952560171111444072049229123565057483750161460024353346284167282452756217662335528813519139808291170539072125381230815729071544861602750936964829313608137325426383735122175229541155376346436093930287402089517426973178917569713384748081827255472576937471496195752727188261435633271238710131736096299798168852925540549342330775279877006784354801422249722573783561685179618816480037695005515426162362431072245638324744480");
102
103 }
104
105
106 pairing(p1, p2) {
107
108 const pre1 = this.precomputeG1(p1);
109 const pre2 = this.precomputeG2(p2);
110
111 const r1 = this.millerLoop(pre1, pre2);
112
113 const res = this.finalExponentiation(r1);
114
115 return res;
116 }
117
118
119 precomputeG1(p) {
120 const Pcopy = this.G1.affine(p);
121
122 const res = {};
123 res.PX = Pcopy[0];
124 res.PY = Pcopy[1];
125
126 return res;
127 }
128
129 precomputeG2(p) {
130
131 const Qcopy = this.G2.affine(p);
132
133 const res = {
134 QX: Qcopy[0],
135 QY: Qcopy[1],
136 coeffs: []
137 };
138
139 const R = {
140 X: Qcopy[0],
141 Y: Qcopy[1],
142 Z: this.F2.one
143 };
144
145 let c;
146
147 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
148 {
149 const bit = this.loop_count_bits[i];
150
151 c = this._doubleStep(R);
152 res.coeffs.push(c);
153
154 if (bit)
155 {
156 c = this._addStep(Qcopy, R);
157 res.coeffs.push(c);
158 }
159 }
160
161 const Q1 = this.G2.affine(this._g2MulByQ(Qcopy));
162 assert(this.F2.equals(Q1[2], this.F2.one));
163 const Q2 = this.G2.affine(this._g2MulByQ(Q1));
164 assert(this.F2.equals(Q2[2], this.F2.one));
165
166 if (this.loopCountNef)
167 {
168 R.Y = this.F2.neg(R.Y);
169 }
170 Q2[1] = this.F2.neg(Q2[1]);
171
172 c = this._addStep(Q1, R);
173 res.coeffs.push(c);
174
175 c = this._addStep(Q2, R);
176 res.coeffs.push(c);
177
178 return res;
179 }
180
181 millerLoop(pre1, pre2) {
182 let f = this.F12.one;
183
184 let idx = 0;
185
186 let c;
187
188 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
189 {
190 const bit = this.loop_count_bits[i];
191
192 /* code below gets executed for all bits (EXCEPT the MSB itself) of
193 alt_bn128_param_p (skipping leading zeros) in MSB to LSB
194 order */
195
196 c = pre2.coeffs[idx++];
197 f = this.F12.square(f);
198 f = this._mul_by_024(
199 f,
200 c.ell_0,
201 this.F2.mulScalar(c.ell_VW , pre1.PY),
202 this.F2.mulScalar(c.ell_VV , pre1.PX, ));
203
204 if (bit)
205 {
206 c = pre2.coeffs[idx++];
207 f = this._mul_by_024(
208 f,
209 c.ell_0,
210 this.F2.mulScalar(c.ell_VW, pre1.PY, ),
211 this.F2.mulScalar(c.ell_VV, pre1.PX, ));
212 }
213
214 }
215
216 if (this.loopCountNef)
217 {
218 f = this.F12.inverse(f);
219 }
220
221 c = pre2.coeffs[idx++];
222 f = this._mul_by_024(
223 f,
224 c.ell_0,
225 this.F2.mulScalar(c.ell_VW, pre1.PY),
226 this.F2.mulScalar(c.ell_VV, pre1.PX));
227
228 c = pre2.coeffs[idx++];
229 f = this._mul_by_024(
230 f,
231 c.ell_0,
232 this.F2.mulScalar(c.ell_VW, pre1.PY, ),
233 this.F2.mulScalar(c.ell_VV, pre1.PX));
234
235 return f;
236 }
237
238 finalExponentiation(elt) {
239 // TODO: There is an optimization in FF
240
241 const res = this.F12.exp(elt,this.final_exponent);
242
243 return res;
244 }
245
246 _doubleStep(current) {
247 const X = current.X;
248 const Y = current.Y;
249 const Z = current.Z;
250
251 const A = this.F2.mulScalar(this.F2.mul(X,Y), this.two_inv); // A = X1 * Y1 / 2
252 const B = this.F2.square(Y); // B = Y1^2
253 const C = this.F2.square(Z); // C = Z1^2
254 const D = this.F2.add(C, this.F2.add(C,C)); // D = 3 * C
255 const E = this.F2.mul(this.twist_coeff_b, D); // E = twist_b * D
256 const F = this.F2.add(E, this.F2.add(E,E)); // F = 3 * E
257 const G =
258 this.F2.mulScalar(
259 this.F2.add( B , F ),
260 this.two_inv); // G = (B+F)/2
261 const H =
262 this.F2.sub(
263 this.F2.square( this.F2.add(Y,Z) ),
264 this.F2.add( B , C)); // H = (Y1+Z1)^2-(B+C)
265 const I = this.F2.sub(E, B); // I = E-B
266 const J = this.F2.square(X); // J = X1^2
267 const E_squared = this.F2.square(E); // E_squared = E^2
268
269 current.X = this.F2.mul( A, this.F2.sub(B,F) ); // X3 = A * (B-F)
270 current.Y =
271 this.F2.sub(
272 this.F2.sub( this.F2.square(G) , E_squared ),
273 this.F2.add( E_squared , E_squared )); // Y3 = G^2 - 3*E^2
274 current.Z = this.F2.mul( B, H ); // Z3 = B * H
275 const c = {
276 ell_0 : this.F2.mul( I, this.twist), // ell_0 = xi * I
277 ell_VW: this.F2.neg( H ), // ell_VW = - H (later: * yP)
278 ell_VV: this.F2.add( J , this.F2.add(J,J) ) // ell_VV = 3*J (later: * xP)
279 };
280
281 return c;
282 }
283
284 _addStep(base, current) {
285
286 const X1 = current.X;
287 const Y1 = current.Y;
288 const Z1 = current.Z;
289 const x2 = base[0];
290 const y2 = base[1];
291
292 const D = this.F2.sub( X1, this.F2.mul(x2,Z1) ); // D = X1 - X2*Z1
293 const E = this.F2.sub( Y1, this.F2.mul(y2,Z1) ); // E = Y1 - Y2*Z1
294 const F = this.F2.square(D); // F = D^2
295 const G = this.F2.square(E); // G = E^2
296 const H = this.F2.mul(D,F); // H = D*F
297 const I = this.F2.mul(X1,F); // I = X1 * F
298 const J =
299 this.F2.sub(
300 this.F2.add( H, this.F2.mul(Z1,G) ),
301 this.F2.add( I, I )); // J = H + Z1*G - (I+I)
302
303 current.X = this.F2.mul( D , J ); // X3 = D*J
304 current.Y =
305 this.F2.sub(
306 this.F2.mul( E , this.F2.sub(I,J) ),
307 this.F2.mul( H , Y1)); // Y3 = E*(I-J)-(H*Y1)
308 current.Z = this.F2.mul(Z1,H);
309 const c = {
310 ell_0 :
311 this.F2.mul(
312 this.twist,
313 this.F2.sub(
314 this.F2.mul(E , x2),
315 this.F2.mul(D , y2))), // ell_0 = xi * (E * X2 - D * Y2)
316 ell_VV : this.F2.neg(E), // ell_VV = - E (later: * xP)
317 ell_VW : D // ell_VW = D (later: * yP )
318 };
319
320 return c;
321 }
322
323 _mul_by_024(a, ell_0, ell_VW, ell_VV) {
324
325 // Old implementation
326
327 const b = [
328 [ell_0, this.F2.zero, ell_VV],
329 [this.F2.zero, ell_VW, this.F2.zero]
330 ];
331
332 return this.F12.mul(a,b);
333
334 /*
335 // This is a new implementation,
336 // But it does not look worthy
337 // at least in javascript.
338
339 let z0 = a[0][0];
340 let z1 = a[0][1];
341 let z2 = a[0][2];
342 let z3 = a[1][0];
343 let z4 = a[1][1];
344 let z5 = a[1][2];
345
346 const x0 = ell_0;
347 const x2 = ell_VV;
348 const x4 = ell_VW;
349
350 const D0 = this.F2.mul(z0, x0);
351 const D2 = this.F2.mul(z2, x2);
352 const D4 = this.F2.mul(z4, x4);
353 const t2 = this.F2.add(z0, z4);
354 let t1 = this.F2.add(z0, z2);
355 const s0 = this.F2.add(this.F2.add(z1,z3),z5);
356
357 // For z.a_.a_ = z0.
358 let S1 = this.F2.mul(z1, x2);
359 let T3 = this.F2.add(S1, D4);
360 let T4 = this.F2.add( this.F2.mul(this.nonResidueF6, T3),D0);
361 z0 = T4;
362
363 // For z.a_.b_ = z1
364 T3 = this.F2.mul(z5, x4);
365 S1 = this.F2.add(S1, T3);
366 T3 = this.F2.add(T3, D2);
367 T4 = this.F2.mul(this.nonResidueF6, T3);
368 T3 = this.F2.mul(z1, x0);
369 S1 = this.F2.add(S1, T3);
370 T4 = this.F2.add(T4, T3);
371 z1 = T4;
372
373 // For z.a_.c_ = z2
374 let t0 = this.F2.add(x0, x2);
375 T3 = this.F2.sub(
376 this.F2.mul(t1, t0),
377 this.F2.add(D0, D2));
378 T4 = this.F2.mul(z3, x4);
379 S1 = this.F2.add(S1, T4);
380 T3 = this.F2.add(T3, T4);
381
382 // For z.b_.a_ = z3 (z3 needs z2)
383 t0 = this.F2.add(z2, z4);
384 z2 = T3;
385 t1 = this.F2.add(x2, x4);
386 T3 = this.F2.sub(
387 this.F2.mul(t0,t1),
388 this.F2.add(D2, D4));
389
390 T4 = this.F2.mul(this.nonResidueF6, T3);
391 T3 = this.F2.mul(z3, x0);
392 S1 = this.F2.add(S1, T3);
393 T4 = this.F2.add(T4, T3);
394 z3 = T4;
395
396 // For z.b_.b_ = z4
397 T3 = this.F2.mul(z5, x2);
398 S1 = this.F2.add(S1, T3);
399 T4 = this.F2.mul(this.nonResidueF6, T3);
400 t0 = this.F2.add(x0, x4);
401 T3 = this.F2.sub(
402 this.F2.mul(t2,t0),
403 this.F2.add(D0, D4));
404 T4 = this.F2.add(T4, T3);
405 z4 = T4;
406
407 // For z.b_.c_ = z5.
408 t0 = this.F2.add(this.F2.add(x0, x2), x4);
409 T3 = this.F2.sub(this.F2.mul(s0, t0), S1);
410 z5 = T3;
411
412 return [
413 [z0, z1, z2],
414 [z3, z4, z5]
415 ];
416
417 */
418
419 }
420
421 _g2MulByQ(p) {
422 const fmx = [p[0][0], this.F1.mul(p[0][1], this.frobenius_coeffs_c1_1 )];
423 const fmy = [p[1][0], this.F1.mul(p[1][1], this.frobenius_coeffs_c1_1 )];
424 const fmz = [p[2][0], this.F1.mul(p[2][1], this.frobenius_coeffs_c1_1 )];
425 return [
426 this.F2.mul(this.twist_mul_by_q_X , fmx),
427 this.F2.mul(this.twist_mul_by_q_Y , fmy),
428 fmz
429 ];
430 }
431}
432
433module.exports = BN128;