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