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