circom/src/compiler.js
src/compiler.jsRaw
1/*
2 Copyright 2018 0kims association
3
4 This file is part of jaz (Zero Knowlage Circuit compiler).
5
6 jaz is free software: you can redistribute it and/or modify
7 it 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 jaz is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with jaz. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const fs = require("fs");
21const path = require("path");
22const bigInt = require("big-integer");
23const __P__ = new bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
24const __MASK__ = new bigInt(2).pow(253).minus(1);
25const assert = require("assert");
26const gen = require("./gencode");
27const exec = require("./exec");
28const lc = require("./lcalgebra");
29
30module.exports = compile;
31
32const parser = require("../parser/jaz.js").parser;
33
34function compile(srcFile) {
35
36 return new Promise ((resolve, reject) => {
37 const fullFileName = srcFile;
38 const fullFilePath = path.dirname(fullFileName);
39
40 const src = fs.readFileSync(fullFileName, "utf8");
41 const ast = parser.parse(src);
42
43 assert(ast.type == "BLOCK");
44
45 const ctx = {
46 scopes: [{}],
47 signals: {
48 one: {
49 fullName: "one",
50 value: bigInt(1),
51 equivalence: "",
52 direction: ""
53 }
54 },
55 currentComponent: "",
56 constraints: [],
57 components: {},
58 templates: {},
59 functions: {},
60 functionParams: {},
61 filePath: fullFilePath,
62 fileName: fullFileName
63 };
64
65 exec(ctx, ast);
66
67 reduceConstraints(ctx);
68 generateWitnessNames(ctx);
69
70 if (ctx.error) {
71 reject(ctx.error);
72 }
73
74 ctx.scopes = [{}];
75
76 const mainCode = gen(ctx,ast);
77 if (ctx.error) reject(ctx.error);
78
79 const def = buildCircuitDef(ctx, mainCode);
80
81 resolve(def);
82 });
83}
84
85
86function generateWitnessNames(ctx) {
87
88 const totals = {
89 "output": 0,
90 "pubInput": 0,
91 "one": 0,
92 "prvInput": 0,
93 "internal": 0,
94 "constant": 0,
95 };
96 const ids = {};
97
98 function priorize(t1, t2) {
99 if ((t1 == "error") || (t2=="error")) return "error";
100 if (t1 == "internal") {
101 return t2;
102 } else if (t2=="internal") {
103 return t1;
104 }
105 if ((t1 == "one") || (t2 == "one")) return "one";
106 if ((t1 == "constant") || (t2 == "constant")) return "constant";
107 if (t1!=t2) return "error";
108 return t1;
109 }
110
111 // First classify the signals
112 for (let s in ctx.signals) {
113 const signal = ctx.signals[s];
114 let tAll = "internal";
115 let lSignal = signal;
116 let end = false;
117 while (!end) {
118 let t = lSignal.category || "internal";
119 if (s == "one") {
120 t = "one";
121 } else if (lSignal.value) {
122 t = "constant";
123 } else if (lSignal.component=="main") {
124 if (lSignal.direction == "IN") {
125 if (lSignal.private) {
126 t = "prvInput";
127 } else {
128 t = "pubInput";
129 }
130 } else if (lSignal.direction == "OUT") {
131 t = "output";
132 }
133 }
134 tAll = priorize(t,tAll);
135 if (lSignal.equivalence) {
136 lSignal = ctx.signals[lSignal.equivalence];
137 } else {
138 end=true;
139 }
140 }
141 if (tAll == "error") {
142 throw new Error("Incompatible types in signal: " + s);
143 }
144 if (lSignal.category) totals[lSignal.category]--;
145 lSignal.category = tAll;
146 totals[lSignal.category] ++;
147 }
148
149 ids["one"] = 0;
150 ids["output"] = 1;
151 ids["pubInput"] = ids["output"] + totals["output"];
152 ids["prvInput"] = ids["pubInput"] + totals["pubInput"];
153 ids["internal"] = ids["prvInput"] + totals["prvInput"];
154 ids["constant"] = ids["internal"] + totals["internal"];
155 const nSignals = ids["constant"] + totals["constant"];
156
157 ctx.signalNames = new Array(nSignals);
158 for (let i=0; i< nSignals; i++) ctx.signalNames[i] = [];
159 ctx.signalName2Idx = {};
160
161 for (let s in ctx.signals) {
162 const signal = ctx.signals[s];
163 let lSignal = signal;
164 while (lSignal.equivalence) {
165 lSignal = ctx.signals[lSignal.equivalence];
166 }
167 if ( typeof(lSignal.id) === "undefined" ) {
168 lSignal.id = ids[lSignal.category] ++;
169 }
170
171 signal.id = lSignal.id;
172 ctx.signalNames[signal.id].push(signal.fullName);
173 ctx.signalName2Idx[signal.fullName] = signal.id;
174 }
175
176 ctx.totals = totals;
177}
178
179function reduceConstraints(ctx) {
180 const newConstraints = [];
181 for (let i=0; i<ctx.constraints.length; i++) {
182 const c = lc.canonize(ctx, ctx.constraints[i]);
183 if (!lc.isZero(c)) {
184 newConstraints.push(c);
185 }
186 }
187 ctx.constraints = newConstraints;
188}
189
190
191function buildCircuitDef(ctx, mainCode) {
192 const res = {
193 mainCode: mainCode
194 };
195 res.signalName2Idx = ctx.signalName2Idx;
196
197 res.components = [];
198 res.componentName2Idx = {};
199 for (let c in ctx.components) {
200 const idCoponent = res.components.length;
201 res.components.push({
202 name: c,
203 params: ctx.components[c].params,
204 template: ctx.components[c].template,
205 inputSignals: 0
206 });
207 res.componentName2Idx[c] = idCoponent;
208 }
209
210 res.signals = new Array(ctx.signalNames.length);
211 for (let i=0; i<ctx.signalNames.length; i++) {
212 res.signals[i] = {
213 names: ctx.signalNames[i],
214 triggerComponents: []
215 };
216 ctx.signalNames[i].map( (fullName) => {
217 const idComponet = res.componentName2Idx[ctx.signals[fullName].component];
218 if (ctx.signals[fullName].direction == "IN") {
219 res.signals[i].triggerComponents.push(idComponet);
220 res.components[idComponet].inputSignals++;
221 }
222 });
223 }
224
225 res.constraints = buildConstraints(ctx);
226
227 res.templates = ctx.templates;
228
229 res.functions = {};
230 for (let f in ctx.functions) {
231 res.functions[f] = {
232 params: ctx.functionParams[f],
233 func: ctx.functions[f]
234 };
235 }
236
237 res.nPrvInputs = ctx.totals.prvInput;
238 res.nPubInputs = ctx.totals.pubInput;
239 res.nInputs = res.nPrvInputs + res.nPubInputs;
240 res.nOutputs = ctx.totals.output;
241 res.nVars = res.nInputs + res.nOutputs + ctx.totals.one + ctx.totals.internal;
242 res.nConstants = ctx.totals.constant;
243 res.nSignals = res.nVars + res.nConstants;
244
245 return res;
246}
247
248/*
249 Build constraints
250
251A constraint like this
252
253 [s1 + 2*s2 + 3*s3] * [ s2 + 5*s4] - [s0 ] = 0
254 [ 5*s2 + 6*s3] * [ s2 + ] - [s0 + 2* s2] = 0
255 [s1 + s3] * [ s2 + 5*s3] - [s4 ] = 0
256
257is converted to
258
259[
260 [{"1":"1","2":"2","3":"3"} , {"2":"1","4":"5"} , {"0":"1" }],
261 [{ "2":"5","3":"6"} , {"2":"1" } , {"0":"1", "2":"2"}],
262 [{"1":"1", "3":"1"} , {"2":"1","3":"5"} , {"4":"1" }]
263]
264 ^ ^ ^
265 | | |
266 A B C
267
268*/
269
270function buildConstraints(ctx) {
271 const res = [];
272
273 function fillLC(dst, src) {
274 for (let s in src.values) {
275 const v = src.values[s].toString();
276 const id = ctx.signalName2Idx[s];
277 dst[id] = v;
278 }
279 }
280
281 for (let i=0; i<ctx.constraints.length; i++) {
282 const A = {};
283 const B = {};
284 const C = {};
285
286 fillLC(A, ctx.constraints[i].a);
287 fillLC(B, ctx.constraints[i].b);
288 fillLC(C, lc.negate(ctx.constraints[i].c));
289
290 res.push([A,B,C]);
291 }
292
293 return res;
294}
295
296
297