circomlib/src/g2_gencontract.js
src/g2_gencontract.jsRaw
1// Copyright (c) 2018 Jordi Baylina
2// License: LGPL-3.0+
3//
4
5const Contract = require("./evmasm");
6const G2 = require("snarkjs").bn128.G2;
7const bigInt = require("snarkjs").bigInt;
8
9
10function toHex256(a) {
11 let S = a.toString(16);
12 while (S.length < 64) S="0"+S;
13 return "0x" + S;
14}
15
16function createCode(P, w) {
17
18 const C = new Contract();
19
20 const NPOINTS = 1 << (w-1);
21
22 const VAR_POS = C.allocMem(32);
23 const VAR_POINTS = C.allocMem( (NPOINTS)*4*32);
24 const savedP = C.allocMem(32);
25 const savedZ3 = C.allocMem(32);
26
27 // Check selector
28 C.push("0x0100000000000000000000000000000000000000000000000000000000");
29 C.push(0);
30 C.calldataload();
31 C.div();
32 C.push("b65c7c74"); // mulexp(uint256)
33 C.eq();
34 C.jmpi("start");
35 C.invalid();
36
37 C.label("start");
38
39 storeVals();
40
41 C.push( Math.floor(255/w)*w ); // pos := 255
42 C.push(VAR_POS);
43 C.mstore();
44
45 C.push("21888242871839275222246405745257275088696311157297823662689037894645226208583");
46 C.push(0);
47 C.push(0);
48 C.push(0);
49 C.push(0);
50 C.push(0);
51 C.push(0);
52
53 C.label("begin_loop"); // ACC_X ACC_Y ACC_Z q
54
55 C.internalCall("double");
56
57 // g = (e>>pos)&MASK
58 C.push(4);
59 C.calldataload(); // e ACC_X ACC_Y ACC_Z q
60
61 C.push(VAR_POS);
62 C.mload(); // pos e ACC_X ACC_Y ACC_Z q
63 C.shr();
64
65 C.push(NPOINTS-1);
66 C.and(); // g ACC_X ACC_Y ACC_Z q
67
68 C.internalCall("add"); // acc_x acc_y acc_z
69
70 C.push(VAR_POS);
71 C.mload(); // pos acc_x acc_y acc_z
72 C.dup(0); // pos pos acc_x acc_y acc_z
73 C.push(0); // 0 pos pos acc_x acc_y acc_z
74 C.eq(); // eq pos acc_x acc_y acc_z
75 C.jmpi("after_loop"); // pos acc_x acc_y acc_z
76 C.push(w); // 5 pos acc_x acc_y acc_z
77 C.sub(); // pos acc_x acc_y acc_z
78 C.push(VAR_POS);
79 C.mstore(); // acc_x acc_y acc_z
80 C.jmp("begin_loop");
81 C.label("after_loop"); // pos acc_x acc_y acc_z
82 C.pop(); // acc_x acc_y acc_z
83
84 C.internalCall("affine"); // acc_x acc_y
85
86 C.push(0);
87 C.mstore();
88 C.push(20);
89 C.mstore();
90 C.push(40);
91 C.mstore();
92 C.push(60);
93 C.mstore();
94
95 C.push("0x80");
96 C.push("0x00");
97 C.return();
98
99
100 double();
101 addPoint();
102 affine();
103
104 return C.createTxData();
105
106 function add(a,b,q) {
107 C.dup(q);
108 C.dup(a+1 + 1);
109 C.dup(b+1 + 2);
110 C.addmod();
111 C.dup(q + 1);
112 C.dup(a + 2);
113 C.dup(b + 3);
114 C.addmod();
115 }
116
117 function sub(a,b,q) {
118 C.dup(q); // q
119 C.dup(a+1 + 1); // ai q
120 C.dub(q + 2); // q ai q
121 C.dup(b+1 + 3); // bi q ai q
122 C.sub(); // -bi ai q
123 C.addmod(); // ci
124 C.dup(q + 1); // q ci
125 C.dup(a + 2); // ar q ci
126 C.dup(q + 3); // q ar q ci
127 C.dup(b + 4); // br q ar q ci
128 C.sub(); // -br ar q ci
129 C.addmod(); // cr ci
130 }
131
132 function mul(a, b, q) {
133 C.dup(q); // q
134 C.dup(q + 1); // q q
135 C.dup(a + 2); // ar q q
136 C.dup(b+1 + 3); // bi ar q q
137 C.mulmod(); // ci1 q
138 C.dup(q + 2); // q ci1 q
139 C.dup(a+1 + 3); // ai q ci1 q
140 C.dup(b + 4); // ar ai q ci1 q
141 C.mulmod(); // ci2 ci1 q
142 C.addmod(); // ci
143 C.dup(q + 1); // q ci
144 C.dup(q + 2); // q q ci
145 C.dup(q + 3); // q q q ci
146 C.dup(a+1 + 4); // ai q q ci
147 C.dup(b+1 + 5); // bi ai q q ci
148 C.mulmod(); // cr2 q q ci
149 C.sub(); // -cr2 q ci
150 C.dup(q + 3); // q -cr2 q ci
151 C.dup(a + 4); // ar q -cr2 q ci
152 C.dup(b + 5); // br ar q -cr2 q ci
153 C.mulmod(); // cr1 -cr2 q ci
154 C.addmod(); // cr ci
155 }
156
157 function square(a, q) {
158 C.dup(q); // q
159 C.dup(q + 1); // q q
160 C.dup(a + 2); // ar q q
161 C.dup(a+1 + 3); // ai ar q q
162 C.mulmod(); // arai q
163 C.dup(0); // arai arai q
164 C.addmod(); // ci
165 C.dup(q + 1); // q ci
166 C.dup(q + 2); // q q ci
167 C.dup(q + 3); // q q q ci
168 C.dup(a+1 + 4); // ai q q ci
169 C.dup(a+1 + 5); // ai ai q q ci
170 C.mulmod(); // cr2 q q ci
171 C.sub(); // -cr2 q ci
172 C.dup(q + 3); // q -cr2 q ci
173 C.dup(a + 4); // ar q -cr2 q ci
174 C.dup(a + 5); // br ar q -cr2 q ci
175 C.mulmod(); // cr1 -cr2 q ci
176 C.addmod(); // cr ci
177 }
178
179 function add1(a, q) {
180 C.dup(a+1); // im
181 C.dup(1 + q); // q
182 C.dup(2 + a); // re q im
183 C.push(1); // 1 re q im
184 C.addmod();
185 }
186
187 function cmp(a, b) {
188 C.dup(a);
189 C.dup(b);
190 C.eq();
191 C.dup(a+1);
192 C.dup(a+1);
193 C.and();
194 }
195
196 function rm(a) {
197 if (a>0) C.swap(a);
198 C.pop();
199 if (a>0) C.swap(a);
200 C.pop();
201 }
202
203 function double() {
204 C.label("double"); // xR, xI, yR, yI, zR zI, q
205
206 C.dup(4);
207 C.iszero();
208 C.dup(6);
209 C.iszero();
210 C.and();
211 C.jumpi("enddouble"); // X Y Z q
212
213
214 // Z3 = 2*Y*Z // Remove Z
215 mul(2, 4, 6); // yz X Y Z q
216 rm(6); // X Y yz q
217
218 add(4, 4, 6); // 2yz X Y yz q
219 rm(6); // X Y Z3 q
220
221 // A = X^2
222 square(0,6); // A X Y Z3 q
223
224 // B = Y^2 // Remove Y
225 square(4,8); // B A X Y Z3 q
226 rm(6); // A X B Z3 q
227
228 // C = B^2
229 square(4,8); // C A X B Z3 q
230
231 // D = (X+B)^2-A-C // Remove X, Remove B
232 add(4,6, 10); // X+B C A X B Z3 q
233 rm(6); // C A X+B B Z3 q
234 rm(6); // A X+B C Z3 q
235 square(2,8); // (X+B)^2 A X+B C Z3 q
236 rm(4); // A (X+B)^2 C Z3 q
237 sub(2, 0, 8); // (X+B)^2-A A (X+B)^2 C Z3 q
238 rm(4); // A (X+B)^2-A C Z3 q
239 sub(2, 4, 8); // (X+B)^2-A-C A (X+B)^2-A C Z3 q
240 rm(4); // A D C Z3 q
241
242 // D = D+D
243 add(2,2, 8); // D+D A D C Z3 q
244 rm(4); // A D C Z3 q
245
246 // E=A+A+A
247 add(0, 0, 8); // 2A A D C Z3 q
248 add(0, 2, 10); // 3A 2A A D C Z3 q
249 rm(4); // 2A 3A D C Z3 q
250 rm(0); // E D C Z3 q
251
252 // F=E^2
253 square(0, 8); // F E D C Z3 q
254
255 // X3= F - 2*D // Remove F
256 add(4, 4, 10); // 2D F E D C Z3 q
257 sub(2, 0, 12); // F-2D 2D F E D C Z3 q
258 rm(4); // 2D X3 E D C Z3 q
259 rm(0); // X3 E D C Z3 q
260
261 // Y3 = E * (D - X3) - 8 * C // Remove D C E
262
263 sub(4, 0, 10); // D-X3 X3 E D C Z3 q
264 rm(6); // X3 E D-X3 C Z3 q
265 mul(2, 4, 10); // E*(D-X3) X3 E D-X3 C Z3 q
266 rm(6); // X3 E E*(D-X3) C Z3 q
267 rm(2); // X3 E*(D-X3) C Z3 q
268 add(4, 4, 8); // 2C X3 E*(D-X3) C Z3 q
269 rm(6); // X3 E*(D-X3) 2C Z3 q
270 add(4, 4, 8); // 4C X3 E*(D-X3) 2C Z3 q
271 rm(6); // X3 E*(D-X3) 4C Z3 q
272 add(4, 4, 8); // 8C X3 E*(D-X3) 4C Z3 q
273 rm(6); // X3 E*(D-X3) 8C Z3 q
274 sub(2, 4, 8); // E*(D-X3)-8C X3 E*(D-X3) 8C Z3 q
275 rm(6); // X3 E*(D-X3) Y3 Z3 q
276 rm(2); // X3 Y3 Z3 q
277
278 C.label("enddouble");
279 C.returnCall();
280 }
281
282 function addPoint() { // p, xR, xI, yR, yI, zR zI, q
283
284
285 C.dup(0); // p p X2 Y2 Z2 q
286
287 C.push(savedP);
288 C.mstore();
289
290 C.iszero(); // X2 Y2 Z2 q
291 C.jumpi("endpadd");
292
293
294 C.dup(4);
295 C.iszero();
296 C.dup(6);
297 C.iszero();
298 C.and();
299 C.jumpi("returnP"); // X2 Y2 Z2 q
300
301
302
303 // lastZ3 = (Z2+1)^2 - Z2^2
304 add1(4, 6); // Z2+1 X2 Y2 Z2 q
305 square(0, 8); // (Z2+1)^2 Z2+1 X2 Y2 Z2 q
306 rm(2); // (Z2+1)^2 X2 Y2 Z2 q
307 square(6, 8); // Z2^2 (Z2+1)^2 X2 Y2 Z2 q
308
309
310 sub(2, 0, 10); // (Z2+1)^2-Z2^2 Z2^2 (Z2+1)^2 X2 Y2 Z2 q
311
312 saveZ3(); // Z2^2 (Z2+1)^2 X2 Y2 Z2 q
313 rm(2); // Z2^2 X2 Y2 Z2 q
314
315 // U2 = X2
316 // S2 = Y2 // Z2^2 U2 S2 Z2 q
317
318
319 // U1 = X1 * Z2^2
320 loadX(); // X1 Z2^2 U2 S2 Z2 q
321 mul(0, 2, 10); // X1*Z2^2 X1 Z2^2 U2 S2 Z2 q
322 rm(2); // X1*Z2^2 Z2^2 U2 S2 Z2 q
323
324
325 mul(2, 8, 10); // Z2^3 U1 Z2^2 U2 S2 Z2 q
326 rm(4); // U1 Z2^3 U2 S2 Z2 q
327 rm(8); // Z2^3 U2 S2 U1 q
328
329 // S1 = Y1 * Z1^3
330 loadY(); // Y1 Z2^3 U2 S2 U1 q
331 mul(0, 2, 10); // S1 Y1 Z2^3 U2 S2 U1 q
332 rm(4); // Y1 S1 U2 S2 U1 q
333 rm(0); // S1 U2 S2 U1 q
334
335 cmp(0, 4); // c1 S1 U2 S2 U1 q
336 cmp(3, 7); // c2 c1 S1 U2 S2 U1 q
337 C.and(); // c2&c1 S1 U2 S2 U1 q
338 C.jumpi("double1"); // S1 U2 S2 U1 q
339
340
341 // Returns the double
342
343 // H = U2-U1 // Remove U2
344 C.sub(4, 8, 10); // H S1 U2 S2 U1 q
345 rm(4); // S1 H S2 U1 q
346
347 // // r = 2 * (S2-S1) // Remove S2
348 C.sub(4, 4, 8); // S1-S2 S1 H S2 U1 q
349 rm(6); // S1 H S1-S2 U1 q
350 C.add(4, 4, 8); // 2*(S1-S2) S1 H S1-S2 U1 q
351 rm(6); // S1 H r U1 q
352
353 // I = (2 * H)^2
354 C.add(2, 2, 8); // 2*H S1 H r U1 q
355 C.square(0, 10); // (2*H)^2 2*H S1 H r U1 q
356 rm(2); // I S1 H r U1 q
357
358 // V = U1 * I
359 mul(8, 0, 10); // V I S1 H r U1 q
360 rm(10); // I S1 H r V q
361
362 // J = H * I // Remove I
363 mul(4, 0, 10); // J I S1 H r V q
364 rm(2); // J S1 H r V q
365
366 // X3 = r^2 - J - 2 * V
367
368 // S1J2 = (S1*J)*2 // Remove S1
369 mul(2, 0, 10); // S1*J J S1 H r V q
370 rm(4); // J S1*J H r V q
371 add(2,2, 10); // (S1*J)*2 J S1*J H r V q
372 rm(4); // J S1J2 H r V q
373
374 // X3 = r^2 - J - 2 * V
375 square(6, 10); // r^2 J S1J2 H r V q
376 sub(0, 2, 12); // r^2-J r^2 J S1J2 H r V q
377 rm(2); // r^2-J J S1J2 H r V q
378 rm(2); // r^2-J S1J2 H r V q
379 add(8, 8, 10); // 2*V r^2-J S1J2 H r V q
380 sub(2, 0, 12); // r^2-J-2*V 2*V r^2-J S1J2 H r V q
381 rm(4); // 2*V X3 S1J2 H r V q
382 rm(0); // X3 S1J2 H r V q
383
384 // Y3 = r * (V-X3)-S1J2
385
386 sub(8, 0, 10); // V-X3 X3 S1J2 H r V q
387 rm(10); // X3 S1J2 H r V-X3 q
388 mul(6, 8, 10); // r*(V-X3) X3 S1J2 H r V-X3 q
389 rm(8); // X3 S1J2 H r*(V-X3) V-X3 q
390 rm(8); // S1J2 H r*(V-X3) X3 q
391 sub(4, 0, 8); // Y3 S1J2 H r*(V-X3) X3 q
392 rm(6); // S1J2 H Y3 X3 q
393 rm(0); // H Y3 X3 q
394
395 // Z3 = lastZ * H
396 loadZ3(); // lastZ3 H Y3 X3 q
397 mul(0, 2, 8); // Z3 lastZ3 H Y3 X3 q
398 rm(4); // lastZ3 Z3 Y3 X3 q
399 rm(0); // Z3 Y3 X3 q
400
401 C.swap(1);
402 C.swap(5);
403 C.swap(1);
404 C.swap(4); // X3 Y3 Z3 q
405
406 // returns the point in memory
407 C.label("returnP"); // X Y Z q
408 rm(0);
409 rm(0);
410 rm(0);
411 C.push(0);
412 C.push(1);
413 loadX();
414 loadY();
415 C.jump("endpadd");
416
417 C.label("double1"); // S1 U2 S2 U1 q
418 rm(0);
419 rm(0);
420 rm(0);
421 rm(0);
422 C.push(0);
423 C.push(1);
424 loadX();
425 loadY();
426 C.jump("double");
427
428 C.label("endpadd");
429 C.returnCall();
430
431 function loadX() {
432 C.push(savedP);
433 C.mload(); // p
434 C.push(32);
435 C.mul(); // P*32
436 C.push(VAR_POINTS+32);
437 C.add(); // P*32+32
438 C.dup(); // P*32+32 P*32+32
439 C.mload(); // im P*32+32
440 C.swap(1); // P*32+32 im
441 C.push(0x20); // 32 P*32+32 im
442 C.sub(); // P*32 im
443 C.mload(); // re im
444 }
445
446 function loadY() {
447 C.push(savedP);
448 C.mload(); // p
449 C.push(32);
450 C.mul(); // P*32
451 C.push(VAR_POINTS+32*3);
452 C.add(); // P*32+32
453 C.dup(); // P*32+32 P*32+32
454 C.mload(); // im P*32+32
455 C.swap(1); // P*32+32 im
456 C.push(0x20); // 32 P*32+32 im
457 C.sub(); // P*32 im
458 C.mload(); // re im
459 }
460
461 function loadZ3() {
462 C.push(savedZ3+32);
463 C.mload(); // p
464 C.push(savedZ3);
465 C.mload();
466 }
467
468 function saveZ3() {
469 C.push(savedZ3);
470 C.mstore();
471 C.push(savedZ3+32);
472 C.mstore();
473 }
474 }
475
476 function affine() { // X Y Z q
477 // If Z2=0 return 0
478 C.label("affine");
479 C.dup(4);
480 C.dup(5 + 1);
481 C.or();
482 C.jumpi("notZero"); // X Y Z q
483 rm(0);
484 rm(0);
485 C.push(0);
486 C.push(0);
487
488 C.jmp("endAffine");
489 C.label("notZero");
490
491 inverse2(4,6); // Z_inv X Y Z q
492 square(2, 8); // Z2_inv Z_inv X Y Z q
493 mul(0, 2, 10); // Z3_inv Z2_inv Z_inv X Y Z q
494 rm(4); // Z2_inv Z3_inv X Y Z q
495 C.push(1);
496 C.push(0); // 1 Z2_inv Z3_inv X Y Z q
497 rm(10); // Z2_inv Z3_inv X Y 1 q
498 mul(2, 6, 10); // YI Z2_inv Z3_inv X Y 1 q
499 rm(8); // Z2_inv Z3_inv X YI 1 q
500 mul(0, 4, 10); // XI Z2_inv Z3_inv X YI 1 q
501 rm(6); // Z2_inv Z3_inv XI YI 1 q
502 rm(0); // Z3_inv XI YI 1 q
503 rm(0); // XI YI 1 q
504 C.label("endAffine");
505 C.returnCall();
506 }
507
508 function inverse2(a, q) {
509 C.dup(q); // q
510 C.dup(q + 1); // q q
511 C.push(2); // 2 q q
512 C.sub(); // q-2 q
513 C.dup(q + 2); // q q-2 q
514 C.dup(q + 3); // q q q-2 q
515 C.dup(a + 4); // ar q q q-2 q
516 C.dup(a + 5); // ar ar q q q-2 q
517 C.mulmod(); // t0 q q-2 q
518
519 C.dup(q + 4); // q t0 q q-2 q
520 C.dup(a+1 + 5); // ai q t0 q q-2 q
521 C.dup(a+1 + 6); // ai ai q t0 q q-2 q
522 C.mulmod(); // t1 t0 q q-2 q
523
524 C.addmod(); // t2 q-2 q
525 C.expmod(); // t3
526
527 C.dup(q + 1); // q t3
528 C.dup(q + 2); // q q t3
529 C.dup(q + 3); // q q q t3
530 C.dup(1); // t3 q q q t3
531 C.sub(); // -t3 q q t3
532 C.dup(a+1 + 3); // ai -t3 q q t3
533 C.mulmod(); // ii q t3
534 C.swap(2); // t3 q ii
535 C.dup(a + 3); // ar t3 q ii
536 C.mulmod(); // ir ii
537 }
538
539 function storeVals() {
540 C.push(VAR_POINTS); // p
541 for (let i=0; i<NPOINTS; i++) {
542 const MP = G2.affine(G2.mulScalar(P, bigInt(i)));
543 for (let j=0; j<2; j++) {
544 for (let k=0; k<2; k++) {
545 C.push(toHex256(MP[j][k])); // MP[0][0] p
546 C.dup(1); // p MP[0][0] p
547 C.mstore(); // p
548 C.push(32); // 32 p
549 C.add(); // p+32
550 }
551 }
552 }
553 }
554
555}
556
557module.exports.abi = [
558 {
559 "constant": true,
560 "inputs": [
561 {
562 "name": "escalar",
563 "type": "uint256"
564 }
565 ],
566 "name": "mulexp",
567 "outputs": [
568 {
569 "name": "",
570 "type": "uint256"
571 },
572 {
573 "name": "",
574 "type": "uint256"
575 }
576 ],
577 "payable": false,
578 "stateMutability": "pure",
579 "type": "function"
580 }
581];
582
583module.exports.createCode = createCode;