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