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