snarkjs/src/pairing.js
src/pairing.jsRaw
1/*
2This module calculate the pairing of p1 and p2 where p1 in G1 and p2 in G2
3 */
4
5const assert = require("assert");
6const bigInt = require("big-integer");
7const F1Field = require("f1field");
8const F2Field = require("f2field");
9const F12Field = require("f12field");
10const G1Curve = require("g1curve");
11const G2Curve = require("g2curve");
12const constants = require("constants");
13
14module.exports = new Pairing();
15
16
17class Pairing {
18
19 constructor() {
20 this.loopCount = bigInt(11);// CONSTANT
21
22 // Set loopCountNeg
23 if (this.loopCount.isNegative()) {
24 this.loopCount = this.neg();
25 this.loopCountNeg = true;
26 } else {
27 this.loopCountNeg = false;
28 }
29
30 // Set loop_count_bits
31 let lc = this.loopCount;
32 this.loop_count_bits = []; // Constant
33 while (lc) {
34 this.loop_count_bits.push( lc.isOdd() );
35 lc = lc.shiftRight(1);
36 }
37
38 this.F12 = new F12Field(constants.q);
39 this.F2 = new F2Field(constants.q);
40 this.F1 = new F1Field(constants.q);
41 this.G1 = new GCurve(F1, constants.g1);
42 this.G2 = new GCurve(F2, constants.g2);
43
44 this.twoInv = this.F1.inverse(bigInt(2));
45 }
46
47 pairing(p1, p2) {
48
49 const pre1 = this._precomputeG1(p1);
50 const pre2 = this._precomputeG2(p2);
51
52 const res = this._millerLoop(pre1, pre2);
53
54 return res;
55 }
56
57
58 _precomputeG1(p) {
59 const Pcopy = this.G1.affine(p);
60
61 const res = {};
62 res.PX = Pcopy[0];
63 res.PY = Pcopy[1];
64
65 return res;
66 }
67
68 _precomputeG2(p) {
69
70 const Qcopy = this.G2.affine(p);
71
72 const res = {
73 QX: Qcopy[0],
74 QY: Qcopy[1],
75 coeffs: []
76 };
77
78 const R = {
79 X: Qcopy[0],
80 Y: Qcopy[1],
81 Z: this.F2.one
82 };
83
84 let c;
85
86 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
87 {
88 const bit = this.loop_count_bits[i];
89
90 c = this._doubleStep(R);
91 res.coeffs.push(c);
92
93 if (bit)
94 {
95 c = this._addStep(Qcopy, R);
96 res.coeffs.push(c);
97 }
98 }
99
100 const Q1 = this.G2.mul_by_q(Qcopy); // TODO mul_by_q
101 assert(this.F2.equal(Q1[2], this.F2.one));
102 const Q2 = this.G2.mul_by_q(Q1);
103 assert(this.F2.equal(Q2[2], this.F2.one));
104
105 if (this.loopCountNef)
106 {
107 R.Y = this.F2.neg(R.Y);
108 }
109 Q2.Y = this.F2.neg(Q2.Y);
110
111 c = this._addStep(Q1, R);
112 res.coeffs.push(c);
113
114 c = this._addStep(Q2, R);
115 res.coeffs.push(c);
116
117 return res;
118 }
119
120 _millerLoop(pre1, pre2) {
121 let f = this.F12.one;
122
123 let idx = 0;
124
125 let c;
126
127 for (let i = this.loop_count_bits.length-2; i >= 0; --i)
128 {
129 const bit = this.loop_count_bits[i];
130
131 /* code below gets executed for all bits (EXCEPT the MSB itself) of
132 alt_bn128_param_p (skipping leading zeros) in MSB to LSB
133 order */
134
135 c = pre2.coeffs[idx++];
136 f = this.F12.square(f);
137 f = this.F12.mul_by_024(
138 f,
139 c.ell_0,
140 this.F2.mul(pre1.PY, c.ell_VW),
141 this.F2.mul(pre1.PX, c.ell_VV));
142
143 if (bit)
144 {
145 c = pre2.coeffs[idx++];
146 f = this.F12.mul_by_024(
147 f,
148 c.ell_0,
149 this.F2.mul(pre1.PY, c.ell_VW),
150 this.F2.mul(pre1.PX, c.ell_VV));
151 }
152
153 }
154
155 if (this.loopCountNef)
156 {
157 f = this.F12.inverse(f);
158 }
159
160 c = pre2.coeffs[idx++];
161 f = this.F12.mul_by_024(
162 f,
163 c.ell_0,
164 this.F2.mul(pre1.PY, c.ell_VW),
165 this.F2.mul(pre1.PX, c.ell_VV));
166
167 c = pre2.coeffs[idx++];
168 f = this.F12.mul_by_024(
169 f,
170 c.ell_0,
171 this.F2.mul(pre1.PY, c.ell_VW),
172 this.F2.mul(pre1.PX, c.ell_VV));
173
174 return f;
175 }
176
177 _doubleStep(current) {
178 const X = current.X;
179 const Y = current.Y;
180 const Z = current.Z;
181
182 const A = this.F2.mulEscalar(this.F1.mul(X,Y), constants.two_inv); // A = X1 * Y1 / 2
183 const B = this.F2.square(Y); // B = Y1^2
184 const C = this.F2.square(Z); // C = Z1^2
185 const D = this.F2.add(C, this.F1.add(C,C)); // D = 3 * C
186 const E = this.F2.mul(constants.twist_coeff_b, D); // E = twist_b * D
187 const F = this.F2.add(E, this.F2.add(E,E)); // F = 3 * E
188 const G =
189 this.F2.mulEscalar(
190 this.F2.sum( B , F ),
191 constants.two_inv); // G = (B+F)/2
192 const H =
193 this.F2.sub(
194 this.F2.square( this.F2.add(Y,Z) ),
195 this.F2.add( B , C)); // H = (Y1+Z1)^2-(B+C)
196 const I = this.F2.sub(E, B); // I = E-B
197 const J = this.F2.square(X); // J = X1^2
198 const E_squared = this.F2.square(E); // E_squared = E^2
199
200 current.X = this.F2.mul( A, this.F2.sub(B,F) ); // X3 = A * (B-F)
201 current.Y =
202 this.F2.sub(
203 this.F2.sub( this.F2.square(G) , E_squared ),
204 this.F2.add( E_squared , E_squared )); // Y3 = G^2 - 3*E^2
205 current.Z = this.F2.mul( B, H ); // Z3 = B * H
206 const c = {
207 ell_0 : this.F2.mul( I, constants.twist), // ell_0 = xi * I
208 ell_VW: this.F2.neg( H ), // ell_VW = - H (later: * yP)
209 ell_VV: this.F2.add( J , this.F2.add(J,J) ) // ell_VV = 3*J (later: * xP)
210 };
211
212 return c;
213 }
214
215 _addStep(base, current) {
216
217 const X1 = current.X;
218 const Y1 = current.Y;
219 const Z1 = current.Z;
220 const x2 = base.X;
221 const y2 = base.Y;
222
223 const D = this.F2.sub( X1, this.F2.mul(x2,Z1) ); // D = X1 - X2*Z1
224 const E = this.F2.sub( Y1, this.F2.mul(y2,Z1) ); // E = Y1 - Y2*Z1
225 const F = this.F2.square(D); // F = D^2
226 const G = this.F2.square(E); // G = E^2
227 const H = this.F2.mul(D,F); // H = D*F
228 const I = this.F2.mul(X1,F); // I = X1 * F
229 const J =
230 this.F2.sub(
231 this.F2.add( H, this.F2.mul(Z1,G) ),
232 this.F2.add( I, I )); // J = H + Z1*G - (I+I)
233
234 current.X = this.F2.mul( D , J ); // X3 = D*J
235 current.Y =
236 this.F2.sub(
237 this.F2.mul( E , this.F2.sub(I,J) ),
238 this.F2.mul( H , Y1)); // Y3 = E*(I-J)-(H*Y1)
239 current.Z = this.F2.mul(Z1,H);
240 const c = {
241 ell_0 :
242 this.F2.mul(
243 constants.twist,
244 this.F2.sub(
245 this.F2.mul(E , x2),
246 this.F2.mul(D , y2))), // ell_0 = xi * (E * X2 - D * Y2)
247 ell_VV : this.F2.neg(E), // ell_VV = - E (later: * xP)
248 ell_VW : D // ell_VW = D (later: * yP )
249 };
250
251 return c;
252 }
253}