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