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