websnark/src/groth16.js
src/groth16.jsRaw
1/*
2 Copyright 2019 0KIMS association.
3
4 This file is part of websnark (Web Assembly zkSnark Prover).
5
6 websnark is a free software: you can redistribute it and/or modify it
7 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 websnark is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with websnark. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20/* globals WebAssembly, Blob, Worker, navigator, Promise, window */
21const bigInt = require("big-integer");
22const groth16_wasm = require("../build/groth16_wasm.js");
23const assert = require("assert");
24
25const inBrowser = (typeof window !== "undefined");
26let NodeWorker;
27let NodeCrypto;
28if (!inBrowser) {
29 NodeWorker = require("worker_threads").Worker;
30 NodeCrypto = require("crypto");
31}
32
33
34class Deferred {
35 constructor() {
36 this.promise = new Promise((resolve, reject)=> {
37 this.reject = reject;
38 this.resolve = resolve;
39 });
40 }
41}
42
43/*
44function delay(ms) {
45 return new Promise(resolve => setTimeout(resolve, ms));
46}
47*/
48
49function thread(self) {
50 let instance;
51 let memory;
52 let i32;
53
54 async function init(data) {
55 const code = new Uint8Array(data.code);
56 const wasmModule = await WebAssembly.compile(code);
57 memory = new WebAssembly.Memory({initial:data.init});
58 i32 = new Uint32Array(memory.buffer);
59
60 instance = await WebAssembly.instantiate(wasmModule, {
61 env: {
62 "memory": memory
63 }
64 });
65 }
66
67 function alloc(length) {
68 while (i32[0] & 3) i32[0]++; // Return always aligned pointers
69 const res = i32[0];
70 i32[0] += length;
71 return res;
72 }
73
74 function putBin(b) {
75 const p = alloc(b.byteLength);
76 const s32 = new Uint32Array(b);
77 i32.set(s32, p/4);
78 return p;
79 }
80
81 function getBin(p, l) {
82 return memory.buffer.slice(p, p+l);
83 }
84
85 self.onmessage = function(e) {
86 let data;
87 if (e.data) {
88 data = e.data;
89 } else {
90 data = e;
91 }
92
93 if (data.command == "INIT") {
94 init(data).then(function() {
95 self.postMessage(data.result);
96 });
97 } else if (data.command == "G1_MULTIEXP") {
98
99 const oldAlloc = i32[0];
100 const pScalars = putBin(data.scalars);
101 const pPoints = putBin(data.points);
102 const pRes = alloc(96);
103 instance.exports.g1_zero(pRes);
104 instance.exports.g1_multiexp(pScalars, pPoints, data.n, 5, pRes);
105
106 data.result = getBin(pRes, 96);
107 i32[0] = oldAlloc;
108 self.postMessage(data.result, [data.result]);
109 } else if (data.command == "G2_MULTIEXP") {
110
111 const oldAlloc = i32[0];
112 const pScalars = putBin(data.scalars);
113 const pPoints = putBin(data.points);
114 const pRes = alloc(192);
115 instance.exports.g2_zero(pRes);
116 instance.exports.g2_multiexp(pScalars, pPoints, data.n, 5, pRes);
117
118 data.result = getBin(pRes, 192);
119 i32[0] = oldAlloc;
120 self.postMessage(data.result, [data.result]);
121 } else if (data.command == "CALC_H") {
122 const oldAlloc = i32[0];
123 const pSignals = putBin(data.signals);
124 const pPolsA = putBin(data.polsA);
125 const pPolsB = putBin(data.polsB);
126 const nSignals = data.nSignals;
127 const domainSize = data.domainSize;
128 const pSignalsM = alloc(nSignals*32);
129 const pPolA = alloc(domainSize*32);
130 const pPolB = alloc(domainSize*32);
131 const pPolA2 = alloc(domainSize*32*2);
132 const pPolB2 = alloc(domainSize*32*2);
133
134 instance.exports.fft_toMontgomeryN(pSignals, pSignalsM, nSignals);
135
136 instance.exports.pol_zero(pPolA, domainSize);
137 instance.exports.pol_zero(pPolB, domainSize);
138
139 instance.exports.pol_constructLC(pPolsA, pSignalsM, nSignals, pPolA);
140 instance.exports.pol_constructLC(pPolsB, pSignalsM, nSignals, pPolB);
141
142 instance.exports.fft_copyNInterleaved(pPolA, pPolA2, domainSize);
143 instance.exports.fft_copyNInterleaved(pPolB, pPolB2, domainSize);
144
145 instance.exports.fft_ifft(pPolA, domainSize, 0);
146 instance.exports.fft_ifft(pPolB, domainSize, 0);
147 instance.exports.fft_fft(pPolA, domainSize, 1);
148 instance.exports.fft_fft(pPolB, domainSize, 1);
149
150 instance.exports.fft_copyNInterleaved(pPolA, pPolA2+32, domainSize);
151 instance.exports.fft_copyNInterleaved(pPolB, pPolB2+32, domainSize);
152
153 instance.exports.fft_mulN(pPolA2, pPolB2, domainSize*2, pPolA2);
154
155 instance.exports.fft_ifft(pPolA2, domainSize*2, 0);
156
157 instance.exports.fft_fromMontgomeryN(pPolA2+domainSize*32, pPolA2+domainSize*32, domainSize);
158
159 data.result = getBin(pPolA2+domainSize*32, domainSize*32);
160 i32[0] = oldAlloc;
161 self.postMessage(data.result, [data.result]);
162 } else if (data.command == "TERMINATE") {
163 process.exit();
164 }
165 };
166}
167
168async function build() {
169
170 const groth16 = new Groth16();
171
172 groth16.q = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208583");
173 groth16.r = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
174 groth16.n64 = Math.floor((groth16.q.minus(1).bitLength() - 1)/64) +1;
175 groth16.n32 = groth16.n64*2;
176 groth16.n8 = groth16.n64*8;
177
178 groth16.memory = new WebAssembly.Memory({initial:1000});
179 groth16.i32 = new Uint32Array(groth16.memory.buffer);
180
181 const wasmModule = await WebAssembly.compile(groth16_wasm.code);
182
183 groth16.instance = await WebAssembly.instantiate(wasmModule, {
184 env: {
185 "memory": groth16.memory
186 }
187 });
188
189 groth16.pq = groth16_wasm.pq;
190 groth16.pr = groth16_wasm.pr;
191
192 groth16.pr0 = groth16.alloc(192);
193 groth16.pr1 = groth16.alloc(192);
194
195 groth16.workers = [];
196 groth16.pendingDeferreds = [];
197 groth16.working = [];
198
199 let concurrency;
200
201 if ((typeof(navigator) === "object") && navigator.hardwareConcurrency) {
202 concurrency = navigator.hardwareConcurrency;
203 } else {
204 concurrency = 8;
205 }
206
207 function getOnMsg(i) {
208 return function(e) {
209 let data;
210 if ((e)&&(e.data)) {
211 data = e.data;
212 } else {
213 data = e;
214 }
215
216 groth16.working[i]=false;
217 groth16.pendingDeferreds[i].resolve(data);
218 groth16.processWorks();
219 };
220 }
221
222 for (let i = 0; i<concurrency; i++) {
223
224 if (inBrowser) {
225 const blob = new Blob(["(", thread.toString(), ")(self);"], { type: "text/javascript" });
226 const url = URL.createObjectURL(blob);
227
228 groth16.workers[i] = new Worker(url);
229
230 groth16.workers[i].onmessage = getOnMsg(i);
231
232 } else {
233 groth16.workers[i] = new NodeWorker("(" + thread.toString()+ ")(require('worker_threads').parentPort);", {eval: true});
234
235 groth16.workers[i].on("message", getOnMsg(i));
236 }
237
238 groth16.working[i]=false;
239 }
240
241 const initPromises = [];
242 for (let i=0; i<groth16.workers.length;i++) {
243 const copyCode = groth16_wasm.code.buffer.slice(0);
244 initPromises.push(groth16.postAction(i, {
245 command: "INIT",
246 init: 1000,
247 code: copyCode
248
249 }, [copyCode]));
250 }
251
252 await Promise.all(initPromises);
253
254 return groth16;
255}
256
257class Groth16 {
258 constructor() {
259 this.actionQueue = [];
260 }
261
262 postAction(workerId, e, transfers, _deferred) {
263 assert(this.working[workerId] == false);
264 this.working[workerId] = true;
265
266 this.pendingDeferreds[workerId] = _deferred ? _deferred : new Deferred();
267 this.workers[workerId].postMessage(e, transfers);
268
269 return this.pendingDeferreds[workerId].promise;
270 }
271
272 processWorks() {
273 for (let i=0; (i<this.workers.length)&&(this.actionQueue.length > 0); i++) {
274 if (this.working[i] == false) {
275 const work = this.actionQueue.shift();
276 this.postAction(i, work.data, work.transfers, work.deferred);
277 }
278 }
279 }
280
281 queueAction(actionData, transfers) {
282 const d = new Deferred();
283 this.actionQueue.push({
284 data: actionData,
285 transfers: transfers,
286 deferred: d
287 });
288 this.processWorks();
289 return d.promise;
290 }
291
292 alloc(length) {
293 while (this.i32[0] & 3) this.i32[0]++; // Return always aligned pointers
294 const res = this.i32[0];
295 this.i32[0] += length;
296 return res;
297 }
298
299
300 putBin(p, b) {
301 const s32 = new Uint32Array(b);
302 this.i32.set(s32, p/4);
303 }
304
305 getBin(p, l) {
306 return this.memory.buffer.slice(p, p+l);
307 }
308
309 bin2int(b) {
310 const i32 = new Uint32Array(b);
311 let acc = bigInt(i32[7]);
312 for (let i=6; i>=0; i--) {
313 acc = acc.shiftLeft(32);
314 acc = acc.add(i32[i]);
315 }
316 return acc.toString();
317 }
318
319 bin2g1(b) {
320 return [
321 this.bin2int(b.slice(0,32)),
322 this.bin2int(b.slice(32,64)),
323 this.bin2int(b.slice(64,96)),
324 ];
325 }
326 bin2g2(b) {
327 return [
328 [
329 this.bin2int(b.slice(0,32)),
330 this.bin2int(b.slice(32,64))
331 ],
332 [
333 this.bin2int(b.slice(64,96)),
334 this.bin2int(b.slice(96,128))
335 ],
336 [
337 this.bin2int(b.slice(128,160)),
338 this.bin2int(b.slice(160,192))
339 ],
340 ];
341 }
342
343 async g1_multiexp(scalars, points) {
344 const nPoints = scalars.byteLength /32;
345 const nPointsPerThread = Math.floor(nPoints / this.workers.length);
346 const opPromises = [];
347 for (let i=0; i<this.workers.length; i++) {
348 const th_nPoints =
349 i < this.workers.length -1 ?
350 nPointsPerThread :
351 nPoints - (nPointsPerThread * (this.workers.length -1));
352 const scalars_th = scalars.slice(i*nPointsPerThread*32, i*nPointsPerThread*32 + th_nPoints*32);
353 const points_th = points.slice(i*nPointsPerThread*64, i*nPointsPerThread*64 + th_nPoints*64);
354 opPromises.push(
355 this.queueAction({
356 command: "G1_MULTIEXP",
357 scalars: scalars_th,
358 points: points_th,
359 n: th_nPoints
360 }, [scalars_th, points_th])
361 );
362 }
363
364 const results = await Promise.all(opPromises);
365
366 this.instance.exports.g1_zero(this.pr0);
367 for (let i=0; i<results.length; i++) {
368 this.putBin(this.pr1, results[i]);
369 this.instance.exports.g1_add(this.pr0, this.pr1, this.pr0);
370 }
371
372 return this.getBin(this.pr0, 96);
373 }
374
375 async g2_multiexp(scalars, points) {
376 const nPoints = scalars.byteLength /32;
377 const nPointsPerThread = Math.floor(nPoints / this.workers.length);
378 const opPromises = [];
379 for (let i=0; i<this.workers.length; i++) {
380 const th_nPoints =
381 i < this.workers.length -1 ?
382 nPointsPerThread :
383 nPoints - (nPointsPerThread * (this.workers.length -1));
384 const scalars_th = scalars.slice(i*nPointsPerThread*32, i*nPointsPerThread*32 + th_nPoints*32);
385 const points_th = points.slice(i*nPointsPerThread*128, i*nPointsPerThread*128 + th_nPoints*128);
386 opPromises.push(
387 this.queueAction({
388 command: "G2_MULTIEXP",
389 scalars: scalars_th,
390 points: points_th,
391 n: th_nPoints
392 }, [scalars_th, points_th])
393 );
394 }
395
396 const results = await Promise.all(opPromises);
397
398 this.instance.exports.g2_zero(this.pr0);
399 for (let i=0; i<results.length; i++) {
400 this.putBin(this.pr1, results[i]);
401 this.instance.exports.g2_add(this.pr0, this.pr1, this.pr0);
402 }
403
404 return this.getBin(this.pr0, 192);
405 }
406
407 g1_affine(p) {
408 this.putBin(this.pr0, p);
409 this.instance.exports.g1_affine(this.pr0, this.pr0);
410 return this.getBin(this.pr0, 96);
411 }
412
413 g2_affine(p) {
414 this.putBin(this.pr0, p);
415 this.instance.exports.g2_affine(this.pr0, this.pr0);
416 return this.getBin(this.pr0, 192);
417 }
418
419 g1_fromMontgomery(p) {
420 this.putBin(this.pr0, p);
421 this.instance.exports.g1_fromMontgomery(this.pr0, this.pr0);
422 return this.getBin(this.pr0, 96);
423 }
424
425 g2_fromMontgomery(p) {
426 this.putBin(this.pr0, p);
427 this.instance.exports.g2_fromMontgomery(this.pr0, this.pr0);
428 return this.getBin(this.pr0, 192);
429 }
430
431 loadPoint1(b) {
432 const p = this.alloc(96);
433 this.putBin(p, b);
434 this.instance.exports.f1m_one(p+64);
435 return p;
436 }
437
438 loadPoint2(b) {
439 const p = this.alloc(192);
440 this.putBin(p, b);
441 this.instance.exports.f2m_one(p+128);
442 return p;
443 }
444
445 terminate() {
446 for (let i=0; i<this.workers.length; i++) {
447 this.workers[i].postMessage({command: "TERMINATE"});
448 }
449 }
450
451
452 async calcH(signals, polsA, polsB, nSignals, domainSize) {
453 return this.queueAction({
454 command: "CALC_H",
455 signals: signals,
456 polsA: polsA,
457 polsB: polsB,
458 nSignals: nSignals,
459 domainSize: domainSize
460 }, [signals, polsA, polsB]);
461 }
462
463 async proof(signals, pkey) {
464 const pkey32 = new Uint32Array(pkey);
465 const nSignals = pkey32[0];
466 const nPublic = pkey32[1];
467 const domainSize = pkey32[2];
468 const pPolsA = pkey32[3];
469 const pPolsB = pkey32[4];
470 const pPointsA = pkey32[5];
471 const pPointsB1 = pkey32[6];
472 const pPointsB2 = pkey32[7];
473 const pPointsC = pkey32[8];
474 const pHExps = pkey32[9];
475 const polsA = pkey.slice(pPolsA, pPolsA + pPolsB);
476 const polsB = pkey.slice(pPolsB, pPolsB + pPointsA);
477 const pointsA = pkey.slice(pPointsA, pPointsA + nSignals*64);
478 const pointsB1 = pkey.slice(pPointsB1, pPointsB1 + nSignals*64);
479 const pointsB2 = pkey.slice(pPointsB2, pPointsB2 + nSignals*128);
480 const pointsC = pkey.slice(pPointsC, pPointsC + (nSignals-nPublic-1)*64);
481 const pointsHExps = pkey.slice(pHExps, pHExps + domainSize*64);
482
483 const alfa1 = pkey.slice(10*4, 10*4 + 64);
484 const beta1 = pkey.slice(10*4 + 64, 10*4 + 128);
485 const delta1 = pkey.slice(10*4 + 128, 10*4 + 192);
486 const beta2 = pkey.slice(10*4 + 192, 10*4 + 320);
487 const delta2 = pkey.slice(10*4 + 320, 10*4 + 448);
488
489
490 const pH = this.calcH(signals.slice(0), polsA, polsB, nSignals, domainSize).then( (h) => {
491/* Debug code to print the result of h
492 for (let i=0; i<domainSize; i++) {
493 const a = this.bin2int(h.slice(i*32, i*32+32));
494 console.log(i + " -> " + a.toString());
495 }
496*/
497 return this.g1_multiexp(h, pointsHExps);
498 });
499
500 const pA = this.g1_multiexp(signals.slice(0), pointsA);
501 const pB1 = this.g1_multiexp(signals.slice(0), pointsB1);
502 const pB2 = this.g2_multiexp(signals.slice(0), pointsB2);
503 const pC = this.g1_multiexp(signals.slice((nPublic+1)*32), pointsC);
504
505 const res = await Promise.all([pA, pB1, pB2, pC, pH]);
506
507 const pi_a = this.alloc(96);
508 const pi_b = this.alloc(192);
509 const pi_c = this.alloc(96);
510 const pib1 = this.alloc(96);
511
512
513 this.putBin(pi_a, res[0]);
514 this.putBin(pib1, res[1]);
515 this.putBin(pi_b, res[2]);
516 this.putBin(pi_c, res[3]);
517
518 const pAlfa1 = this.loadPoint1(alfa1);
519 const pBeta1 = this.loadPoint1(beta1);
520 const pDelta1 = this.loadPoint1(delta1);
521 const pBeta2 = this.loadPoint2(beta2);
522 const pDelta2 = this.loadPoint2(delta2);
523
524
525 let rnd = new Uint32Array(8);
526
527 const aux1 = this.alloc(96);
528 const aux2 = this.alloc(192);
529
530 const pr = this.alloc(32);
531 const ps = this.alloc(32);
532
533 if (inBrowser) {
534 window.crypto.getRandomValues(rnd);
535 this.putBin(pr, rnd);
536
537 window.crypto.getRandomValues(rnd);
538 this.putBin(ps, rnd);
539 } else {
540 const br = NodeCrypto.randomBytes(32);
541 this.putBin(pr, br);
542 const bs = NodeCrypto.randomBytes(32);
543 this.putBin(ps, bs);
544 }
545
546/// Uncoment it to debug and check it works
547// this.instance.exports.f1m_zero(pr);
548// this.instance.exports.f1m_zero(ps);
549
550 // pi_a = pi_a + Alfa1 + r*Delta1
551 this.instance.exports.g1_add(pAlfa1, pi_a, pi_a);
552 this.instance.exports.g1_timesScalar(pDelta1, pr, 32, aux1);
553 this.instance.exports.g1_add(aux1, pi_a, pi_a);
554
555 // pi_b = pi_b + Beta2 + s*Delta2
556 this.instance.exports.g2_add(pBeta2, pi_b, pi_b);
557 this.instance.exports.g2_timesScalar(pDelta2, ps, 32, aux2);
558 this.instance.exports.g2_add(aux2, pi_b, pi_b);
559
560 // pib1 = pib1 + Beta1 + s*Delta1
561 this.instance.exports.g1_add(pBeta1, pib1, pib1);
562 this.instance.exports.g1_timesScalar(pDelta1, ps, 32, aux1);
563 this.instance.exports.g1_add(aux1, pib1, pib1);
564
565
566 // pi_c = pi_c + pH
567 this.putBin(aux1, res[4]);
568 this.instance.exports.g1_add(aux1, pi_c, pi_c);
569
570
571 // pi_c = pi_c + s*pi_a
572 this.instance.exports.g1_timesScalar(pi_a, ps, 32, aux1);
573 this.instance.exports.g1_add(aux1, pi_c, pi_c);
574
575 // pi_c = pi_c + r*pib1
576 this.instance.exports.g1_timesScalar(pib1, pr, 32, aux1);
577 this.instance.exports.g1_add(aux1, pi_c, pi_c);
578
579 // pi_c = pi_c - r*s*delta1
580 const prs = this.alloc(64);
581 this.instance.exports.int_mul(pr, ps, prs);
582 this.instance.exports.g1_timesScalar(pDelta1, prs, 64, aux1);
583 this.instance.exports.g1_neg(aux1, aux1);
584 this.instance.exports.g1_add(aux1, pi_c, pi_c);
585
586 this.instance.exports.g1_affine(pi_a, pi_a);
587 this.instance.exports.g2_affine(pi_b, pi_b);
588 this.instance.exports.g1_affine(pi_c, pi_c);
589
590 this.instance.exports.g1_fromMontgomery(pi_a, pi_a);
591 this.instance.exports.g2_fromMontgomery(pi_b, pi_b);
592 this.instance.exports.g1_fromMontgomery(pi_c, pi_c);
593
594 return {
595 pi_a: this.bin2g1(this.getBin(pi_a, 96)),
596 pi_b: this.bin2g2(this.getBin(pi_b, 192)),
597 pi_c: this.bin2g1(this.getBin(pi_c, 96)),
598 };
599
600 }
601
602}
603
604module.exports = build;