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 bigInt = require("big-integer");
21const __P__ = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
22const sONE = 0;
23const build = require("./build");
24const BuilderC = require("../ports/c/builder.js");
25const BuilderWasm = require("../ports/wasm/builder.js");
26const constructionPhase = require("./construction_phase");
27const Ctx = require("./ctx");
28const ZqField = require("ffjavascript").ZqField;
29const utils = require("./utils");
30const buildR1cs = require("./r1csfile").buildR1cs;
31const BigArray = require("./bigarray");
32const buildSyms = require("./buildsyms");
33
34module.exports = compile;
35
36async function compile(srcFile, options) {
37 options.p = options.p || __P__;
38 if (!options) {
39 options = {};
40 }
41 if (typeof options.reduceConstraints === "undefined") {
42 options.reduceConstraints = true;
43 }
44 const ctx = new Ctx();
45 ctx.field = new ZqField(options.p);
46 ctx.verbose= options.verbose || false;
47 ctx.mainComponent = options.mainComponent || "main";
48 ctx.newThreadTemplates = options.newThreadTemplates;
49
50 constructionPhase(ctx, srcFile);
51
52 if (ctx.verbose) console.log("NConstraints Before: "+ctx.constraints.length);
53
54 if (ctx.error) {
55 throw(ctx.error);
56 }
57
58 if (ctx.getComponentIdx(ctx.mainComponent)<0) {
59 throw new Error("A main component must be defined");
60 }
61
62 if (ctx.verbose) console.log("Classify Signals");
63 classifySignals(ctx);
64
65 if (ctx.verbose) console.log("Reduce Constants");
66 reduceConstants(ctx);
67 if (options.reduceConstraints) {
68
69 if (ctx.verbose) console.log("Reduce Constraints");
70 // Repeat while reductions are performed
71 let oldNConstrains = -1;
72 while (ctx.constraints.length != oldNConstrains) {
73 if (ctx.verbose) console.log("Reducing constraints: "+ctx.constraints.length);
74 oldNConstrains = ctx.constraints.length;
75 reduceConstrains(ctx);
76 }
77 }
78
79 if (ctx.verbose) console.log("NConstraints After: "+ctx.constraints.length);
80
81 generateWitnessNames(ctx);
82
83 if (ctx.error) {
84 throw(ctx.error);
85 }
86
87 if (options.cSourceWriteStream) {
88 ctx.builder = new BuilderC();
89 build(ctx);
90 const rdStream = ctx.builder.build();
91 rdStream.pipe(options.cSourceWriteStream);
92
93 // await new Promise(fulfill => options.cSourceWriteStream.on("finish", fulfill));
94 }
95
96 if ((options.wasmWriteStream)||(options.watWriteStream)) {
97 ctx.builder = new BuilderWasm();
98 build(ctx);
99 if (options.wasmWriteStream) {
100 const rdStream = ctx.builder.build("wasm");
101 rdStream.pipe(options.wasmWriteStream);
102 }
103 if (options.watWriteStream) {
104 const rdStream = ctx.builder.build("wat");
105 rdStream.pipe(options.watWriteStream);
106 }
107
108 // await new Promise(fulfill => options.wasmWriteStream.on("finish", fulfill));
109 }
110
111 // const mainCode = gen(ctx,ast);
112 if (ctx.error) throw(ctx.error);
113
114 if (options.r1csFileName) {
115 await buildR1cs(ctx, options.r1csFileName);
116 }
117
118 if (options.symWriteStream) {
119 const rdStream = buildSyms(ctx);
120 rdStream.pipe(options.symWriteStream);
121
122 // await new Promise(fulfill => options.symWriteStream.on("finish", fulfill));
123 }
124
125// const def = buildCircuitDef(ctx, mainCode);
126
127}
128
129
130
131function classifySignals(ctx) {
132
133 const ERROR = 0xFFFF;
134
135 function priorize(t1, t2) {
136 if ((t1 == ERROR) || (t2==ERROR)) return ERROR;
137 if (t1 == ctx.stINTERNAL) {
138 return t2;
139 } else if (t2==ctx.stINTERNAL) {
140 return t1;
141 }
142 if ((t1 == ctx.stONE) || (t2 == ctx.stONE)) return ctx.stONE;
143 if ((t1 == ctx.stOUTPUT) || (t2 == ctx.stOUTPUT)) return ctx.stOUTPUT;
144 if ((t1 == ctx.stCONSTANT) || (t2 == ctx.stCONSTANT)) return ctx.stCONSTANT;
145 if ((t1 == ctx.stDISCARDED) || (t2 == ctx.stDISCARDED)) return ctx.stDISCARDED;
146 if (t1!=t2) return ERROR;
147 return t1;
148 }
149
150 // First classify the signals
151 for (let s=0; s<ctx.signals.length; s++) {
152 const signal = ctx.signals[s];
153 let tAll = ctx.stINTERNAL;
154 let lSignal = signal;
155 let end = false;
156 while (!end) {
157 let t = lSignal.c || ctx.stINTERNAL;
158 if (s == 0) {
159 t = ctx.stONE;
160 } else if (lSignal.o & ctx.MAIN) {
161 if (lSignal.o & ctx.IN) {
162 if (lSignal.o & ctx.PRV) {
163 t = ctx.stPRVINPUT;
164 } else {
165 t = ctx.stPUBINPUT;
166 }
167 } else if (lSignal.o & ctx.OUT) {
168 t = ctx.stOUTPUT;
169 }
170 } else if (utils.isDefined(lSignal.v)) {
171 t = ctx.stCONSTANT;
172 }
173 tAll = priorize(t,tAll);
174 if (lSignal.e>=0) {
175 lSignal = ctx.signals[lSignal.e];
176 } else {
177 end=true;
178 }
179 }
180 if (tAll == ERROR) {
181 throw new Error("Incompatible types in signal: " + s);
182 }
183 lSignal.c = tAll;
184 }
185}
186
187
188function generateWitnessNames(ctx) {
189 const totals = {};
190 totals[ctx.stONE] = 0;
191 totals[ctx.stOUTPUT] = 0;
192 totals[ctx.stPUBINPUT] = 0;
193 totals[ctx.stPRVINPUT] = 0;
194 totals[ctx.stINTERNAL] = 0;
195 totals[ctx.stDISCARDED] = 0;
196 totals[ctx.stCONSTANT] = 0;
197 const ids = {};
198
199 // First classify the signals
200 for (let s=0; s<ctx.signals.length; s++) {
201
202 if ((ctx.verbose)&&(s%10000 == 0)) console.log("generate witness (counting): ", s);
203
204 const signal = ctx.signals[s];
205 let lSignal = signal;
206 while (lSignal.e>=0) lSignal = ctx.signals[lSignal.e];
207
208 if (!( lSignal.o & ctx.COUNTED) ) {
209 lSignal.o |= ctx.COUNTED;
210 totals[lSignal.c] ++;
211 }
212 }
213
214 ids[ctx.stONE] = 0;
215 ids[ctx.stOUTPUT] = 1;
216 ids[ctx.stPUBINPUT] = ids[ctx.stOUTPUT] + totals[ctx.stOUTPUT];
217 ids[ctx.stPRVINPUT] = ids[ctx.stPUBINPUT] + totals[ctx.stPUBINPUT];
218 ids[ctx.stINTERNAL] = ids[ctx.stPRVINPUT] + totals[ctx.stPRVINPUT];
219 ids[ctx.stDISCARDED] = ids[ctx.stINTERNAL] + totals[ctx.stINTERNAL];
220 ids[ctx.stCONSTANT] = ids[ctx.stDISCARDED] + totals[ctx.stDISCARDED];
221 const nSignals = ids[ctx.stCONSTANT] + totals[ctx.stCONSTANT];
222
223 for (let s=0; s<ctx.signals.length; s++) {
224
225 if ((ctx.verbose)&&(s%10000 == 0)) console.log("seting id: ", s);
226
227 const signal = ctx.signals[s];
228 let lSignal = signal;
229 while (lSignal.e>=0) {
230 lSignal = ctx.signals[lSignal.e];
231 }
232 if ( typeof(lSignal.id) === "undefined" ) {
233 lSignal.id = ids[lSignal.c] ++;
234 }
235
236 signal.id = lSignal.id;
237 }
238
239 ctx.totals = totals;
240}
241
242function reduceConstants(ctx) {
243 const newConstraints = new BigArray();
244 for (let i=0; i<ctx.constraints.length; i++) {
245 if ((ctx.verbose)&&(i%10000 == 0)) console.log("reducing constants: ", i);
246 const c = ctx.lc.canonize(ctx, ctx.constraints[i]);
247 if (!ctx.lc.isZero(c)) {
248 newConstraints.push(c);
249 }
250 delete ctx.constraints[i];
251 }
252 ctx.constraints = newConstraints;
253}
254
255function reduceConstrains(ctx) {
256 indexVariables();
257 let possibleConstraints = ctx.constraints;
258 let ii=0;
259 while (possibleConstraints.length>0) {
260 let nextPossibleConstraints = new BigArray();
261 for (let i=0; i<possibleConstraints.length; i++) {
262 ii++;
263 if ((ctx.verbose)&&(ii%10000 == 0)) console.log("reducing constraints: ", i);
264 if (!ctx.constraints[i]) continue;
265 const c = ctx.constraints[i];
266
267 // Swap a and b if b has more variables.
268 if (Object.keys(c.b).length > Object.keys(c.a).length) {
269 const aux = c.a;
270 c.a=c.b;
271 c.b=aux;
272 }
273
274 // Mov to C if possible.
275 if (isConstant(c.a)) {
276 const ct = {t: "N", v: c.a.coefs[sONE]};
277 c.c = ctx.lc.add(ctx.lc.mul(c.b, ct), c.c);
278 c.a = { t: "LC", coefs: {} };
279 c.b = { t: "LC", coefs: {} };
280 }
281 if (isConstant(c.b)) {
282 const ct = {t: "N", v: c.b.coefs[sONE]};
283 c.c = ctx.lc.add(ctx.lc.mul(c.a, ct), c.c);
284 c.a = { t: "LC", coefs: {} };
285 c.b = { t: "LC", coefs: {} };
286 }
287
288 if (ctx.lc.isZero(c.a) || ctx.lc.isZero(c.b)) {
289 const isolatedSignal = getFirstInternalSignal(ctx, c.c);
290 if (isolatedSignal) {
291
292 let lSignal = ctx.signals[isolatedSignal];
293 while (lSignal.e>=0) {
294 lSignal = ctx.signals[lSignal.e];
295 }
296
297
298 const isolatedSignalEquivalence = {
299 t: "LC",
300 coefs: {}
301 };
302 const invCoef = c.c.coefs[isolatedSignal].modInv(__P__);
303 for (const s in c.c.coefs) {
304 if (s != isolatedSignal) {
305 const v = __P__.minus(c.c.coefs[s]).times(invCoef).mod(__P__);
306 if (!v.isZero()) {
307 isolatedSignalEquivalence.coefs[s] = v;
308 }
309 }
310 }
311
312 for (let j in lSignal.inConstraints) {
313 if ((j!=i)&&(ctx.constraints[j])) {
314 ctx.constraints[j] = ctx.lc.substitute(ctx.constraints[j], isolatedSignal, isolatedSignalEquivalence);
315 linkSignalsConstraint(j);
316 if (j<i) {
317 nextPossibleConstraints.push(j);
318 }
319 }
320 }
321
322 ctx.constraints[i] = null;
323
324 lSignal.c = ctx.stDISCARDED;
325 } else {
326 if (ctx.lc.isZero(c.c)) ctx.constraints[i] = null;
327 }
328 }
329 }
330 possibleConstraints = nextPossibleConstraints;
331 }
332 unindexVariables();
333
334 // Pack the constraints
335 let o = 0;
336 for (let i=0; i<ctx.constraints.length; i++) {
337 if (ctx.constraints[i]) {
338 if (o != i) {
339 ctx.constraints[o] = ctx.constraints[i];
340 }
341 o++;
342 }
343 }
344 ctx.constraints.length = o;
345
346 function indexVariables() {
347 for (let i=0; i<ctx.constraints.length; i++) linkSignalsConstraint(i);
348 }
349
350 function linkSignalsConstraint(cidx) {
351 const ct = ctx.constraints[cidx];
352 for (let k in ct.a.coefs) linkSignal(k, cidx);
353 for (let k in ct.b.coefs) linkSignal(k, cidx);
354 for (let k in ct.c.coefs) linkSignal(k, cidx);
355 }
356
357 function unindexVariables() {
358 for (let s=0; s<ctx.signals.length; s++) {
359 let lSignal = ctx.signals[s];
360 while (lSignal.e>=0) {
361 lSignal = ctx.signals[lSignal.e];
362 }
363 if (lSignal.inConstraints) delete lSignal.inConstraints;
364 }
365 }
366
367/*
368 function unlinkSignal(signalName, cidx) {
369 let lSignal = ctx.signals[signalName];
370 while (lSignal.e>=0) {
371 lSignal = ctx.signals[lSignal.e];
372 }
373 if ((lSignal.inConstraints)&&(lSignal.inConstraints[cidx])) {
374 delete lSignal.inConstraints[cidx];
375 }
376 }
377*/
378
379 function linkSignal(signalName, cidx) {
380 let lSignal = ctx.signals[signalName];
381 while (lSignal.e>=0) {
382 lSignal = ctx.signals[lSignal.e];
383 }
384 if (!lSignal.inConstraints) lSignal.inConstraints = {};
385 lSignal.inConstraints[cidx] = true;
386 }
387
388 function getFirstInternalSignal(ctx, l) {
389 for (let k in l.coefs) {
390 const signal = ctx.signals[k];
391 if (signal.c == ctx.stINTERNAL) return k;
392 }
393 return null;
394 }
395
396 function isConstant(l) {
397 for (let k in l.coefs) {
398 if ((k != sONE) && (!l.coefs[k].isZero())) return false;
399 }
400 if (!l.coefs[sONE] || l.coefs[sONE].isZero()) return false;
401 return true;
402 }
403
404}
405
406/*
407
408function buildCircuitDef(ctx, mainCode) {
409 const res = {
410 mainCode: mainCode
411 };
412 res.signalName2Idx = ctx.signalName2Idx;
413
414 res.components = [];
415 res.componentName2Idx = {};
416 for (let c in ctx.components) {
417 const idCoponent = res.components.length;
418 res.components.push({
419 name: c,
420 params: ctx.components[c].params,
421 template: ctx.components[c].template,
422 inputSignals: 0
423 });
424 res.componentName2Idx[c] = idCoponent;
425 }
426
427 res.signals = new Array(ctx.signalNames.length);
428 for (let i=0; i<ctx.signalNames.length; i++) {
429 res.signals[i] = {
430 names: ctx.signalNames[i],
431 triggerComponents: []
432 };
433 ctx.signalNames[i].map( (fullName) => {
434 const idComponet = res.componentName2Idx[ctx.signals[fullName].component];
435 if (ctx.signals[fullName].direction == "IN") {
436 res.signals[i].triggerComponents.push(idComponet);
437 res.components[idComponet].inputSignals++;
438 }
439 });
440 }
441
442 res.constraints = buildConstraints(ctx);
443
444 res.templates = ctx.templates;
445
446 res.functions = {};
447 for (let f in ctx.functions) {
448 res.functions[f] = {
449 params: ctx.functionParams[f],
450 func: ctx.functions[f]
451 };
452 }
453
454 res.nPrvInputs = ctx.totals.prvInput;
455 res.nPubInputs = ctx.totals.pubInput;
456 res.nInputs = res.nPrvInputs + res.nPubInputs;
457 res.nOutputs = ctx.totals.output;
458 res.nVars = res.nInputs + res.nOutputs + ctx.totals.one + ctx.totals.internal;
459 res.nConstants = ctx.totals.constant;
460 res.nSignals = res.nVars + res.nConstants;
461
462 return res;
463}
464
465*/
466
467
468/*
469 Build constraints
470
471A constraint like this
472
473 [s1 + 2*s2 + 3*s3] * [ s2 + 5*s4] - [s0 ] = 0
474 [ 5*s2 + 6*s3] * [ s2 + ] - [s0 + 2* s2] = 0
475 [s1 + s3] * [ s2 + 5*s3] - [s4 ] = 0
476
477is converted to
478
479[
480 [{"1":"1","2":"2","3":"3"} , {"2":"1","4":"5"} , {"0":"1" }],
481 [{ "2":"5","3":"6"} , {"2":"1" } , {"0":"1", "2":"2"}],
482 [{"1":"1", "3":"1"} , {"2":"1","3":"5"} , {"4":"1" }]
483]
484 ^ ^ ^
485 | | |
486 A B C
487
488*/
489/*
490function buildConstraints(ctx) {
491 const res = [];
492
493 function fillLC(dst, src) {
494 if (src.t != "LC") throw new Error("Constraint is not a LINEARCOMBINATION");
495 for (let s in src.coefs) {
496 const v = src.coefs[s].toString();
497 const id = ctx.signalName2Idx[s];
498 dst[id] = v;
499 }
500 }
501
502 for (let i=0; i<ctx.constraints.length; i++) {
503 const A = {};
504 const B = {};
505 const C = {};
506
507 fillLC(A, ctx.constraints[i].a);
508 fillLC(B, ctx.constraints[i].b);
509 fillLC(C, ctx.lc.negate(ctx.constraints[i].c));
510
511 res.push([A,B,C]);
512 }
513
514 return res;
515}
516*/
517
518/*
519function buildSyms(ctx, strm) {
520
521 let nSyms;
522
523 addSymbolsComponent(ctx.mainComponent + ".", ctx.getComponentIdx(ctx.mainComponent));
524
525
526 function addSymbolsComponent(prefix, idComponet) {
527 for (let n in ctx.components[idComponet].names.o) {
528 const entrie = ctx.components[idComponet].names.o[n];
529 addSymbolArray(prefix+n, entrie.type, entrie.sizes, entrie.offset);
530 }
531 }
532
533 function addSymbolArray(prefix, type, sizes, offset) {
534 if (sizes.length==0) {
535 if (type == "S") {
536 let s=offset;
537 while (ctx.signals[s].e >= 0) s = ctx.signals[s].e;
538 let wId = ctx.signals[s].id;
539 if (typeof(wId) == "undefined") wId=-1;
540 strm.write(`${offset},${wId},${prefix}\n`);
541 nSyms ++;
542 if ((ctx.verbose)&&(nSyms%10000 == 0)) console.log("Symbols saved: "+nSyms);
543 } else {
544 addSymbolsComponent(prefix+".", offset);
545 }
546 return 1;
547 } else {
548 let acc = 0;
549 for (let i=0; i<sizes[0]; i++) {
550 acc += addSymbolArray(`${prefix}[${i}]`, type, sizes.slice(1), offset + acc );
551 }
552 return acc;
553 }
554 }
555
556}
557
558*/
559