circom/src/compiler.js
src/compiler.jsRaw
1/*
2 Copyright 2018 0KIMS association.
3
4 This file is part of circom (Zero Knowledge Circuit Compiler).
5
6 circom 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 circom 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 circom. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const Scalar = require("ffjavascript").Scalar;
21const sONE = 0;
22const build = require("./build");
23const BuilderC = require("../ports/c/builder.js");
24const BuilderWasm = require("../ports/wasm/builder.js");
25const constructionPhase = require("./construction_phase");
26const Ctx = require("./ctx");
27const utils = require("./utils");
28const buildR1cs = require("./r1csfile").buildR1cs;
29const BigArray = require("./bigarray");
30const buildSyms = require("./buildsyms");
31const {performance} = require("perf_hooks");
32
33module.exports = compile;
34const measures = {};
35
36function ms2String(v) {
37 v = Math.floor(v);
38 const ms = v % 1000;
39 v = Math.floor(v/1000);
40 const secs = v % 60;
41 v = Math.floor(v/60);
42 const mins = v % 60;
43 v = Math.floor(v/60);
44 const hours = v % 24;
45 const days = Math.floor(v/24);
46 let S = "";
47 if (days) S = S + days + "D ";
48 if ((S!="")||(hours)) S = S + hours.toString().padStart(2, "0") + ":";
49 if ((S!="")||(mins)) S = S + mins.toString().padStart(2, "0") + ":";
50 if ((S!="")||(secs)) S = S + secs.toString().padStart(2, "0");
51 S+=".";
52 S = S + ms.toString().padStart(3, "0");
53 return S;
54}
55
56async function compile(srcFile, options) {
57 options.prime = options.prime || Scalar.fromString("21888242871839275222246405745257275088548364400416034343698204186575808495617");
58 if (!options) {
59 options = {};
60 }
61 if (typeof options.reduceConstraints === "undefined") {
62 options.reduceConstraints = true;
63 }
64 const ctx = new Ctx(options.prime);
65 ctx.verbose= options.verbose || false;
66 ctx.mainComponent = options.mainComponent || "main";
67 ctx.newThreadTemplates = options.newThreadTemplates;
68
69 measures.constructionPhase = -performance.now();
70 constructionPhase(ctx, srcFile);
71 measures.constructionPhase += performance.now();
72
73 if (ctx.verbose) console.log("NConstraints Before: "+ctx.constraints.length);
74 if (ctx.verbose) console.log("NSignals Before: "+ctx.signals.length);
75
76 if (ctx.error) {
77 throw(ctx.error);
78 }
79
80 if (ctx.getComponentIdx(ctx.mainComponent)<0) {
81 throw new Error("A main component must be defined");
82 }
83
84
85 if (ctx.verbose) console.log("Reduce Constants");
86 measures.reduceConstants = -performance.now();
87 reduceConstants(ctx);
88 measures.reduceConstants += performance.now();
89
90 if (options.reduceConstraints) {
91
92 if (ctx.verbose) console.log("Reduce Constraints");
93 // Repeat while reductions are performed
94/*
95 let oldNConstrains = -1;
96 while (ctx.constraints.length != oldNConstrains) {
97 if (ctx.verbose) console.log("Reducing constraints: "+ctx.constraints.length);
98 oldNConstrains = ctx.constraints.length;
99 reduceConstrains(ctx);
100 }
101*/
102 measures.reduceConstraints = -performance.now();
103 await reduceConstrains(ctx);
104 measures.reduceConstraints += performance.now();
105
106 }
107 if (ctx.verbose) console.log("NConstraints After: "+ctx.constraints.length);
108
109 if (ctx.verbose) console.log("Classify Signals");
110 measures.classifySignals = -performance.now();
111 classifySignals(ctx);
112 measures.classifySignals += performance.now();
113
114 measures.generateWitnessNames = -performance.now();
115 generateWitnessNames(ctx);
116 measures.generateWitnessNames += performance.now();
117
118 if (ctx.error) {
119 throw(ctx.error);
120 }
121
122 if (options.r1csFileName) {
123 measures.generateR1cs = -performance.now();
124 await buildR1cs(ctx, options.r1csFileName);
125 measures.generateR1cs += performance.now();
126 }
127
128 if (ctx.error) throw(ctx.error);
129
130 delete ctx.constraints; // Liberate memory.
131
132 if (options.cSourceFile) {
133 if (ctx.verbose) console.log("Generating c...");
134 measures.generateC = -performance.now();
135 ctx.builder = new BuilderC(options.prime, ctx.verbose);
136 build(ctx);
137 await ctx.builder.build(options.cSourceFile, options.dataFile);
138 measures.generateC += performance.now();
139 }
140
141 if (ctx.error) throw(ctx.error);
142
143 if ((options.wasmFile)||(options.watFile)) {
144 if (ctx.verbose) console.log("Generating wasm...");
145 measures.generateWasm = -performance.now();
146 ctx.builder = new BuilderWasm(options.prime);
147 build(ctx);
148 if (options.wasmFile) {
149 await ctx.builder.build(options.wasmFile, "wasm");
150 }
151 if (options.watFile) {
152 await ctx.builder.build(options.watFile, "wat");
153 }
154 measures.generateWasm += performance.now();
155 }
156
157 // const mainCode = gen(ctx,ast);
158 if (ctx.error) throw(ctx.error);
159
160 if (options.symWriteStream) {
161 measures.generateSyms = -performance.now();
162 const rdStream = buildSyms(ctx);
163 rdStream.pipe(options.symWriteStream);
164 measures.generateSyms += performance.now();
165
166 await new Promise(fulfill => options.symWriteStream.on("finish", fulfill));
167 }
168
169// const def = buildCircuitDef(ctx, mainCode);
170
171 if (ctx.verbose) {
172 for (let [mStr, mValue] of Object.entries(measures)) {
173 console.log(mStr + ": " + ms2String(mValue));
174 }
175 }
176}
177
178
179
180function classifySignals(ctx) {
181
182 const ERROR = 0xFFFF;
183
184 function priorize(t1, t2) {
185 if ((t1 == ERROR) || (t2==ERROR)) return ERROR;
186 if ((t1 == ctx.stONE) || (t2 == ctx.stONE)) return ctx.stONE;
187 if ((t1 == ctx.stOUTPUT) || (t2 == ctx.stOUTPUT)) return ctx.stOUTPUT;
188 if ((t1 == ctx.stPUBINPUT) || (t2 == ctx.stPUBINPUT)) return ctx.stPUBINPUT;
189 if ((t1 == ctx.stPRVINPUT) || (t2 == ctx.stPRVINPUT)) return ctx.stPRVINPUT;
190 if ((t1 == ctx.stINTERNAL) || (t2 == ctx.stINTERNAL)) return ctx.stINTERNAL;
191 if ((t1 == ctx.stCONSTANT) || (t2 == ctx.stCONSTANT)) return ctx.stCONSTANT;
192 if ((t1 == ctx.stDISCARDED) || (t2 == ctx.stDISCARDED)) return ctx.stDISCARDED;
193 if (t1!=t2) return ERROR;
194 return t1;
195 }
196
197 for (let i=0; i<ctx.constraints.length; i++) {
198 if ((ctx.verbose)&&(i%100000 == 0)) console.log(`marking as internal: ${i}/${ctx.constraints.length}`);
199
200 const c = ctx.constraints[i];
201 for (let s in c.a.coefs) ctx.signals[s].c = ctx.stINTERNAL;
202 for (let s in c.b.coefs) ctx.signals[s].c = ctx.stINTERNAL;
203 for (let s in c.c.coefs) ctx.signals[s].c = ctx.stINTERNAL;
204 }
205
206
207 // First classify the signals
208 for (let s=0; s<ctx.signals.length; s++) {
209 if ((ctx.verbose)&&(s%100000 == 0)) console.log(`classify signals: ${s}/${ctx.signals.length}`);
210 const signal = ctx.signals[s];
211 let tAll = ctx.stDISCARDED;
212 let lSignal = signal;
213 let end = false;
214 while (!end) {
215 let t = lSignal.c || ctx.stDISCARDED;
216 if (s == 0) {
217 t = ctx.stONE;
218 } else if (lSignal.o & ctx.MAIN) {
219 if (lSignal.o & ctx.IN) {
220 if (lSignal.o & ctx.PRV) {
221 t = ctx.stPRVINPUT;
222 } else {
223 t = ctx.stPUBINPUT;
224 }
225 } else if (lSignal.o & ctx.OUT) {
226 t = ctx.stOUTPUT;
227 }
228 } else if (utils.isDefined(lSignal.v)) {
229 t = ctx.stCONSTANT;
230 }
231 tAll = priorize(t,tAll);
232 if (lSignal.e>=0) {
233 lSignal = ctx.signals[lSignal.e];
234 } else {
235 end=true;
236 }
237 }
238 if (tAll == ERROR) {
239 throw new Error("Incompatible types in signal: " + s);
240 }
241 lSignal.c = tAll;
242 }
243}
244
245
246function generateWitnessNames(ctx) {
247 const totals = {};
248 totals[ctx.stONE] = 0;
249 totals[ctx.stOUTPUT] = 0;
250 totals[ctx.stPUBINPUT] = 0;
251 totals[ctx.stPRVINPUT] = 0;
252 totals[ctx.stINTERNAL] = 0;
253 totals[ctx.stDISCARDED] = 0;
254 totals[ctx.stCONSTANT] = 0;
255 const ids = {};
256
257 // First classify the signals
258 for (let s=0; s<ctx.signals.length; s++) {
259
260 if ((ctx.verbose)&&(s%10000 == 0)) console.log("generate witness (counting): ", s);
261
262 const signal = ctx.signals[s];
263 let lSignal = signal;
264 while (lSignal.e>=0) lSignal = ctx.signals[lSignal.e];
265
266 if (!( lSignal.o & ctx.COUNTED) ) {
267 lSignal.o |= ctx.COUNTED;
268 totals[lSignal.c] ++;
269 }
270 }
271
272 ids[ctx.stONE] = 0;
273 ids[ctx.stOUTPUT] = 1;
274 ids[ctx.stPUBINPUT] = ids[ctx.stOUTPUT] + totals[ctx.stOUTPUT];
275 ids[ctx.stPRVINPUT] = ids[ctx.stPUBINPUT] + totals[ctx.stPUBINPUT];
276 ids[ctx.stINTERNAL] = ids[ctx.stPRVINPUT] + totals[ctx.stPRVINPUT];
277 ids[ctx.stDISCARDED] = ids[ctx.stINTERNAL] + totals[ctx.stINTERNAL];
278 ids[ctx.stCONSTANT] = ids[ctx.stDISCARDED] + totals[ctx.stDISCARDED];
279 const nSignals = ids[ctx.stCONSTANT] + totals[ctx.stCONSTANT];
280
281 for (let s=0; s<ctx.signals.length; s++) {
282
283 if ((ctx.verbose)&&(s%10000 == 0)) console.log("seting id: ", s);
284
285 const signal = ctx.signals[s];
286 let lSignal = signal;
287 while (lSignal.e>=0) {
288 lSignal = ctx.signals[lSignal.e];
289 }
290 if ( typeof(lSignal.id) === "undefined" ) {
291 lSignal.id = ids[lSignal.c] ++;
292 }
293
294 signal.id = lSignal.id;
295 }
296
297 ctx.totals = totals;
298}
299
300function reduceConstants(ctx) {
301 const newConstraints = new BigArray();
302 for (let i=0; i<ctx.constraints.length; i++) {
303 if ((ctx.verbose)&&(i%10000 == 0)) console.log("reducing constants: ", i);
304 const c = ctx.lc.canonize(ctx, ctx.constraints[i]);
305 if (!ctx.lc.isZero(c)) {
306 newConstraints.push(c);
307 }
308 delete ctx.constraints[i];
309 }
310 ctx.constraints = newConstraints;
311}
312
313async function reduceConstrains(ctx) {
314 const sig2constraint = new BigArray();
315 let removedSignals = new BigArray();
316 let nRemoved;
317 let lIdx;
318
319
320 let possibleConstraints = new BigArray(ctx.constraints.length);
321 let nextPossibleConstraints;
322 for (let i=0; i<ctx.constraints.length; i++) {
323 if ((ctx.verbose)&&(i%100000 == 0)) console.log(`indexing constraints: ${i}/${ctx.constraints.length}`);
324
325 const insertedSig = { 0: true}; // Do not insert one.
326 const c = ctx.constraints[i];
327 for (let s in c.a.coefs) {
328 if (!insertedSig[s]) {
329 if (!sig2constraint[s]) sig2constraint[s] = {};
330 sig2constraint[s][i] = true;
331 insertedSig[s] = true;
332 }
333 }
334 for (let s in c.b.coefs) {
335 if (!insertedSig[s]) {
336 if (!sig2constraint[s]) sig2constraint[s] = {};
337 sig2constraint[s][i] = true;
338 insertedSig[s] = true;
339 }
340 }
341 for (let s in c.c.coefs) {
342 if (!insertedSig[s]) {
343 if (!sig2constraint[s]) sig2constraint[s] = {};
344 sig2constraint[s][i] = true;
345 insertedSig[s] = true;
346 }
347 }
348 possibleConstraints[i] = ctx.constraints.length - i -1;
349 }
350
351 let totalRemoved = 0;
352 while (possibleConstraints.length >0) {
353 if (possibleConstraints.length>1<<20) {
354 nextPossibleConstraints = new BigArray();
355 } else {
356 nextPossibleConstraints = {};
357 }
358 removedSignals = {};
359 nRemoved = 0;
360 lIdx = {};
361 for (let i=0;i<possibleConstraints.length;i++) {
362 if ((ctx.verbose)&&(i%10000 == 0)) {
363 await Promise.resolve();
364 console.log(`reducing constraints: ${i}/${possibleConstraints.length} reduced: ${nRemoved}`);
365 }
366
367 const c = ctx.constraints[possibleConstraints[i]];
368 if (!c) continue;
369
370 // Limit of number of lelements removed per step
371 if (nRemoved>5000000) {
372 nextPossibleConstraints[possibleConstraints[i]] = true;
373 continue;
374 }
375
376 // Swap a and b if b has more variables.
377 if (Object.keys(c.b).length > Object.keys(c.a).length) {
378 const aux = c.a;
379 c.a=c.b;
380 c.b=aux;
381 }
382
383 // Mov to C if possible.
384 if (isConstant(c.a)) {
385 const ct = {t: "N", v: c.a.coefs[sONE]};
386 c.c = ctx.lc.add(ctx.lc.mul(c.b, ct), c.c);
387 c.a = { t: "LC", coefs: {} };
388 c.b = { t: "LC", coefs: {} };
389 }
390 if (isConstant(c.b)) {
391 const ct = {t: "N", v: c.b.coefs[sONE]};
392 c.c = ctx.lc.add(ctx.lc.mul(c.a, ct), c.c);
393 c.a = { t: "LC", coefs: {} };
394 c.b = { t: "LC", coefs: {} };
395 }
396
397 if (ctx.lc.isZero(c.a) || ctx.lc.isZero(c.b)) {
398 const freeC = substituteRemoved(c.c);
399 const isolatedSignal = getFirstInternalSignal(ctx, freeC);
400 if (isolatedSignal) {
401 removedSignals[isolatedSignal] = isolateSignal(freeC, isolatedSignal);
402 if (lIdx[isolatedSignal]) {
403 const sigs = Object.keys(lIdx[isolatedSignal]);
404
405 for (let k=0; k<sigs.length; k++) {
406 const s = sigs[k];
407 const oldLC = removedSignals[s];
408 removedSignals[s] = substitute(removedSignals[s], isolatedSignal, removedSignals[isolatedSignal]);
409 if (oldLC !== removedSignals[s]) addTolIdx(removedSignals[s], s);
410 }
411 }
412
413 addTolIdx(removedSignals[isolatedSignal], isolatedSignal);
414 ctx.constraints[possibleConstraints[i]] = null;
415 nRemoved ++;
416
417 delete lIdx[isolatedSignal];
418
419 const cts = Object.keys(sig2constraint[isolatedSignal]);
420 for (let k=0; k<cts.length; k++) {
421 if (ctx.constraints[cts[k]]) nextPossibleConstraints[cts[k]] = true;
422 }
423 }
424 }
425 }
426
427 if (nextPossibleConstraints.getKeys) {
428 nextPossibleConstraints = nextPossibleConstraints.getKeys();
429 } else {
430 nextPossibleConstraints = Object.keys(nextPossibleConstraints);
431 }
432
433 for (let i=0; i<nextPossibleConstraints.length;i++) {
434 if ((ctx.verbose)&&(i%10000 == 0)) {
435 await Promise.resolve();
436 console.log(`substituting constraints: ${i}/${nextPossibleConstraints.length}`);
437 }
438 const c = ctx.constraints[nextPossibleConstraints[i]];
439 if (c) {
440 const nc = {
441 a: substituteRemoved(c.a, nextPossibleConstraints[i]),
442 b: substituteRemoved(c.b, nextPossibleConstraints[i]),
443 c: substituteRemoved(c.c, nextPossibleConstraints[i])
444 };
445 if (ctx.lc.isZero(nc)) {
446 delete ctx.constraints[nextPossibleConstraints[i]];
447 } else {
448 ctx.constraints[nextPossibleConstraints[i]] = nc;
449 }
450 }
451 }
452
453 const removedSignalsList = Object.keys(removedSignals);
454
455 for (let i=0; i<removedSignalsList.length; i++) {
456 if ((ctx.verbose )&&(i%100000 == 0)) console.log(`removing signals: ${i}/${removedSignalsList.length}`);
457 const s = removedSignalsList[i];
458
459 let lSignal = ctx.signals[s];
460 while (lSignal.e>=0) {
461 lSignal = ctx.signals[lSignal.e];
462 }
463
464 sig2constraint[s] = null;
465 }
466
467/*
468 possibleConstraints = new BigArray();
469 // Reverse
470 for (let i=0; i<nextPossibleConstraints.length; i++) {
471 possibleConstraints[i] = nextPossibleConstraints[nextPossibleConstraints.length -1 -i];
472 }
473*/
474 possibleConstraints = nextPossibleConstraints;
475
476 totalRemoved += nRemoved;
477 if (ctx.verbose) console.log(`Removed: ${totalRemoved} TotalConstraints: ${ctx.constraints.length}` );
478 }
479
480
481 let o=0;
482 for (let i=0; i<ctx.constraints.length;i++) {
483 if ((ctx.verbose)&&(i%100000 == 0)) console.log(`reordering constraints: ${i}/${ctx.constraints.length}`);
484 if (ctx.constraints[i]) {
485 if (!ctx.lc.isZero(ctx.constraints[i])) {
486 ctx.constraints[o] = ctx.constraints[i];
487 o++;
488 }
489 }
490 }
491
492 ctx.constraints.length = o;
493
494 function getFirstInternalSignal(ctx, l) {
495 for (let k in l.coefs) {
496 k = Number(k);
497 const signal = ctx.signals[k];
498 if ( ( ((signal.o & ctx.MAIN) == 0)
499 ||( ((signal.o & ctx.IN) == 0)
500 &&((signal.o & ctx.OUT) == 0)))
501 &&((signal.o & ctx.ONE) ==0)
502 &&(!ctx.F.isZero(l.coefs[k]))
503 &&(!removedSignals[k])) return k;
504 }
505 return null;
506 }
507
508 function isolateSignal(lc, s) {
509 const eq = {
510 t: "LC",
511 coefs: {}
512 };
513 const invCoef = ctx.F.inv(lc.coefs[s]);
514 for (const k in lc.coefs) {
515 if (k != s) {
516 const v = ctx.F.mul( ctx.F.neg(lc.coefs[k]), invCoef);
517 if (!ctx.F.isZero(v)) {
518 eq.coefs[k] = v;
519 }
520 }
521 }
522 return eq;
523 }
524
525 function substituteRemoved(lc, idxConstraint) {
526 const newLc = ctx.lc._clone(lc);
527 for (let k in lc.coefs) {
528 if (removedSignals[k]) {
529 delete newLc.coefs[k];
530 for (let k2 in removedSignals[k].coefs) {
531 const newP = ctx.F.mul(removedSignals[k].coefs[k2], lc.coefs[k]);
532 if (!ctx.F.isZero(newP)) {
533 if (newLc.coefs[k2]) {
534 newLc.coefs[k2] = ctx.F.add(newLc.coefs[k2], newP);
535 if (ctx.F.isZero(newLc.coefs[k2])) delete newLc.coefs[k2];
536 } else {
537 newLc.coefs[k2] = newP;
538 }
539 }
540 if ((typeof idxConstraint != "undefined")&&(k2!=0)) {
541 if (!sig2constraint[k2]) sig2constraint[k2] = {};
542 sig2constraint[k2][idxConstraint] = true;
543 }
544 }
545 }
546 }
547 return newLc;
548 }
549
550 function substitute(lc, s, eq) {
551 if (!lc.coefs[s]) return lc;
552 const newLc = ctx.lc._clone(lc);
553 delete newLc.coefs[s];
554 for (let k2 in eq.coefs) {
555 const newP = ctx.F.mul(eq.coefs[k2], lc.coefs[s]);
556 if (!ctx.F.isZero(newP)) {
557 if (newLc.coefs[k2]) {
558 newLc.coefs[k2] = ctx.F.add(newLc.coefs[k2], newP);
559 if (ctx.F.isZero(newLc.coefs[k2])) delete newLc.coefs[k2];
560 } else {
561 newLc.coefs[k2] = newP;
562 }
563 }
564 }
565 return newLc;
566 }
567
568 function isConstant(l) {
569 for (let k in l.coefs) {
570 if ((k != sONE) && (!ctx.F.isZero(l.coefs[k]))) return false;
571 }
572 if (!l.coefs[sONE] || ctx.F.isZero(l.coefs[sONE])) return false;
573 return true;
574 }
575
576 function addTolIdx(lc, newS) {
577 const sigs = Object.keys(lc.coefs);
578 for (let k=0; k<sigs.length; k++) {
579 const s = sigs[k];
580 if (s) {
581 if (!lIdx[s]) lIdx[s] = {};
582 lIdx[s][newS] = true;
583 }
584 }
585 }
586
587}
588
589