snarkjs/src/bn128.js
src/bn128.jsRaw
1const bigInt = require("big-integer");
2const assert = require("assert");
3
4const F1Field = require("./f1field.js");
5const F2Field = require("./f2field.js");
6const F3Field = require("./f3field.js");
7const GCurve = require("./gcurve.js");
8
9class BN128 {
10
11 constructor() {
12
13 this.q = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208583");
14 this.r = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
15 this.g1 = [ bigInt(1), bigInt(2) ];
16 this.g2 = [
17 [
18 bigInt("10857046999023057135944570762232829481370756359578518086990519993285655852781"),
19 bigInt("11559732032986387107991004021392285783925812861821192530917403151452391805634")
20 ],
21 [
22 bigInt("8495653923123431417604973247489272438418190587263600148770280649306958101930"),
23 bigInt("4082367875863433681332203403145435568316851327593401208105741076214120093531")
24 ]
25 ];
26
27 this.F1 = new F1Field(this.q);
28 this.F2 = new F2Field(this.F1, bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208582"));
29 this.G1 = new GCurve(this.F1, this.g1);
30 this.G2 = new GCurve(this.F2, this.g2);
31 this.F6 = new F3Field(this.F2, [ bigInt("9"), bigInt("1") ]);
32 this.F12 = new F2Field(this.F6, [ bigInt("9"), bigInt("1") ]);
33 const self = this;
34 this.F12._mulByNonResidue = function(a) {
35 return [self.F2.mul(this.nonResidue, a[2]), a[0], a[1]];
36 };
37
38 this._preparePairing();
39
40 }
41
42 _preparePairing() {
43 this.loopCount = bigInt("29793968203157093288");// CONSTANT
44
45 // Set loopCountNeg
46 if (this.loopCount.isNegative()) {
47 this.loopCount = this.neg();
48 this.loopCountNeg = true;
49 } else {
50 this.loopCountNeg = false;
51 }
52
53 // Set loop_count_bits
54 let lc = this.loopCount;
55 this.loop_count_bits = []; // Constant
56 while (!lc.isZero()) {
57 this.loop_count_bits.push( lc.isOdd() );
58 lc = lc.shiftRight(1);
59 }
60
61 this.two_inv = this.F1.inverse(bigInt(2));
62
63 this.coef_b = bigInt(3);
64 this.twist = [bigInt(9) , bigInt(1)];
65 this.twist_coeff_b = this.F2.mulEscalar( this.F2.inverse(this.twist), this.coef_b );
66
67 this.frobenius_coeffs_c1_1 = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208582");
68 this.twist_mul_by_q_X =
69 [
70 bigInt("21575463638280843010398324269430826099269044274347216827212613867836435027261"),
71 bigInt("10307601595873709700152284273816112264069230130616436755625194854815875713954")
72 ];
73 this.twist_mul_by_q_Y =
74 [
75 bigInt("2821565182194536844548159561693502659359617185244120367078079554186484126554"),
76 bigInt("3505843767911556378687030309984248845540243509899259641013678093033130930403")
77 ];
78
79 this.final_exponent = bigInt("552484233613224096312617126783173147097382103762957654188882734314196910839907541213974502761540629817009608548654680343627701153829446747810907373256841551006201639677726139946029199968412598804882391702273019083653272047566316584365559776493027495458238373902875937659943504873220554161550525926302303331747463515644711876653177129578303191095900909191624817826566688241804408081892785725967931714097716709526092261278071952560171111444072049229123565057483750161460024353346284167282452756217662335528813519139808291170539072125381230815729071544861602750936964829313608137325426383735122175229541155376346436093930287402089517426973178917569713384748081827255472576937471496195752727188261435633271238710131736096299798168852925540549342330775279877006784354801422249722573783561685179618816480037695005515426162362431072245638324744480");
80
81 }
82
83
84 pairing(p1, p2) {
85
86 const pre1 = this.precomputeG1(p1);
87 const pre2 = this.precomputeG2(p2);
88
89 const r1 = this.millerLoop(pre1, pre2);
90
91 const res = this.finalExponentiation(r1);
92
93 return res;
94 }
95
96
97 precomputeG1(p) {
98 const Pcopy = this.G1.affine(p);
99
100 const res = {};
101 res.PX = Pcopy[0];
102 res.PY = Pcopy[1];
103
104 return res;
105 }
106
107 precomputeG2(p) {
108
109 const Qcopy = this.G2.affine(p);
110
111 const res = {
112 QX: Qcopy[0],
113 QY: Qcopy[1],
114 coeffs: []
115 };
116
117 const R = {
118 X: Qcopy[0],
119 Y: Qcopy[1],
120 Z: this.F2.one
121 };
122
123 let c;
124
125 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
126 {
127 const bit = this.loop_count_bits[i];
128
129 c = this._doubleStep(R);
130 res.coeffs.push(c);
131
132 if (bit)
133 {
134 c = this._addStep(Qcopy, R);
135 res.coeffs.push(c);
136 }
137 }
138
139 const Q1 = this.G2.affine(this._g2MulByQ(Qcopy));
140 assert(this.F2.equals(Q1[2], this.F2.one));
141 const Q2 = this.G2.affine(this._g2MulByQ(Q1));
142 assert(this.F2.equals(Q2[2], this.F2.one));
143
144 if (this.loopCountNef)
145 {
146 R.Y = this.F2.neg(R.Y);
147 }
148 Q2[1] = this.F2.neg(Q2[1]);
149
150 c = this._addStep(Q1, R);
151 res.coeffs.push(c);
152
153 c = this._addStep(Q2, R);
154 res.coeffs.push(c);
155
156 return res;
157 }
158
159 millerLoop(pre1, pre2) {
160 let f = this.F12.one;
161
162 let idx = 0;
163
164 let c;
165
166 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
167 {
168 const bit = this.loop_count_bits[i];
169
170 /* code below gets executed for all bits (EXCEPT the MSB itself) of
171 alt_bn128_param_p (skipping leading zeros) in MSB to LSB
172 order */
173
174 c = pre2.coeffs[idx++];
175 f = this.F12.square(f);
176 f = this._mul_by_024(
177 f,
178 c.ell_0,
179 this.F2.mulEscalar(c.ell_VW , pre1.PY),
180 this.F2.mulEscalar(c.ell_VV , pre1.PX, ));
181
182 if (bit)
183 {
184 c = pre2.coeffs[idx++];
185 f = this._mul_by_024(
186 f,
187 c.ell_0,
188 this.F2.mulEscalar(c.ell_VW, pre1.PY, ),
189 this.F2.mulEscalar(c.ell_VV, pre1.PX, ));
190 }
191
192 }
193
194 if (this.loopCountNef)
195 {
196 f = this.F12.inverse(f);
197 }
198
199 c = pre2.coeffs[idx++];
200 f = this._mul_by_024(
201 f,
202 c.ell_0,
203 this.F2.mulEscalar(c.ell_VW, pre1.PY),
204 this.F2.mulEscalar(c.ell_VV, pre1.PX));
205
206 c = pre2.coeffs[idx++];
207 f = this._mul_by_024(
208 f,
209 c.ell_0,
210 this.F2.mulEscalar(c.ell_VW, pre1.PY, ),
211 this.F2.mulEscalar(c.ell_VV, pre1.PX));
212
213 return f;
214 }
215
216 finalExponentiation(elt) {
217 // TODO: There is an optimization in FF
218
219 const res = this.F12.exp(elt,this.final_exponent);
220
221 return res;
222 }
223
224 _doubleStep(current) {
225 const X = current.X;
226 const Y = current.Y;
227 const Z = current.Z;
228
229 const A = this.F2.mulEscalar(this.F2.mul(X,Y), this.two_inv); // A = X1 * Y1 / 2
230 const B = this.F2.square(Y); // B = Y1^2
231 const C = this.F2.square(Z); // C = Z1^2
232 const D = this.F2.add(C, this.F2.add(C,C)); // D = 3 * C
233 const E = this.F2.mul(this.twist_coeff_b, D); // E = twist_b * D
234 const F = this.F2.add(E, this.F2.add(E,E)); // F = 3 * E
235 const G =
236 this.F2.mulEscalar(
237 this.F2.add( B , F ),
238 this.two_inv); // G = (B+F)/2
239 const H =
240 this.F2.sub(
241 this.F2.square( this.F2.add(Y,Z) ),
242 this.F2.add( B , C)); // H = (Y1+Z1)^2-(B+C)
243 const I = this.F2.sub(E, B); // I = E-B
244 const J = this.F2.square(X); // J = X1^2
245 const E_squared = this.F2.square(E); // E_squared = E^2
246
247 current.X = this.F2.mul( A, this.F2.sub(B,F) ); // X3 = A * (B-F)
248 current.Y =
249 this.F2.sub(
250 this.F2.sub( this.F2.square(G) , E_squared ),
251 this.F2.add( E_squared , E_squared )); // Y3 = G^2 - 3*E^2
252 current.Z = this.F2.mul( B, H ); // Z3 = B * H
253 const c = {
254 ell_0 : this.F2.mul( I, this.twist), // ell_0 = xi * I
255 ell_VW: this.F2.neg( H ), // ell_VW = - H (later: * yP)
256 ell_VV: this.F2.add( J , this.F2.add(J,J) ) // ell_VV = 3*J (later: * xP)
257 };
258
259 return c;
260 }
261
262 _addStep(base, current) {
263
264 const X1 = current.X;
265 const Y1 = current.Y;
266 const Z1 = current.Z;
267 const x2 = base[0];
268 const y2 = base[1];
269
270 const D = this.F2.sub( X1, this.F2.mul(x2,Z1) ); // D = X1 - X2*Z1
271 const E = this.F2.sub( Y1, this.F2.mul(y2,Z1) ); // E = Y1 - Y2*Z1
272 const F = this.F2.square(D); // F = D^2
273 const G = this.F2.square(E); // G = E^2
274 const H = this.F2.mul(D,F); // H = D*F
275 const I = this.F2.mul(X1,F); // I = X1 * F
276 const J =
277 this.F2.sub(
278 this.F2.add( H, this.F2.mul(Z1,G) ),
279 this.F2.add( I, I )); // J = H + Z1*G - (I+I)
280
281 current.X = this.F2.mul( D , J ); // X3 = D*J
282 current.Y =
283 this.F2.sub(
284 this.F2.mul( E , this.F2.sub(I,J) ),
285 this.F2.mul( H , Y1)); // Y3 = E*(I-J)-(H*Y1)
286 current.Z = this.F2.mul(Z1,H);
287 const c = {
288 ell_0 :
289 this.F2.mul(
290 this.twist,
291 this.F2.sub(
292 this.F2.mul(E , x2),
293 this.F2.mul(D , y2))), // ell_0 = xi * (E * X2 - D * Y2)
294 ell_VV : this.F2.neg(E), // ell_VV = - E (later: * xP)
295 ell_VW : D // ell_VW = D (later: * yP )
296 };
297
298 return c;
299 }
300
301 _mul_by_024(a, ell_0, ell_VW, ell_VV) {
302
303 const b = [
304 [ell_0, this.F2.zero, ell_VV],
305 [this.F2.zero, ell_VW, this.F2.zero]
306 ];
307
308 return this.F12.mul(a,b);
309
310 // TODO There is a better version on libff. It should be ported.
311 }
312
313 _g2MulByQ(p) {
314 const fmx = [p[0][0], this.F1.mul(p[0][1], this.frobenius_coeffs_c1_1 )];
315 const fmy = [p[1][0], this.F1.mul(p[1][1], this.frobenius_coeffs_c1_1 )];
316 const fmz = [p[2][0], this.F1.mul(p[2][1], this.frobenius_coeffs_c1_1 )];
317 return [
318 this.F2.mul(this.twist_mul_by_q_X , fmx),
319 this.F2.mul(this.twist_mul_by_q_Y , fmy),
320 fmz
321 ];
322 }
323}
324
325module.exports = BN128;