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