circom/src/lcalgebra.js
src/lcalgebra.jsRaw
1/*
2
3 NUMBER: a
4
5 {
6 type: "NUMBER",
7 value: bigInt(a)
8 }
9
10 LINEARCOMBINATION: c1*s1 + c2*s2 + c3*s3
11
12 {
13 type: "LINEARCOMBINATION",
14 values: {
15 s1: bigInt(c1),
16 s2: bigInt(c2),
17 s3: bigInt(c3)
18 }
19 }
20
21
22 QEQ: a*b + c WHERE a,b,c are LINEARCOMBINATION
23 {
24 type: "QEQ"
25 a: { type: LINEARCOMBINATION, values: {...} },
26 b: { type: LINEARCOMBINATION, values: {...} },
27 c: { type: LINEARCOMBINATION, values: {...} }
28 }
29 */
30
31/*
32+ NUM LC QEQ
33NUM NUM LC QEQ
34LC LC LC QEQ
35QEQ QEQ QEQ ERR
36
37* NUM LC QEQ
38NUM NUM LC QEQ
39LC LC QEQ ERR
40QEQ QEQ ERR ERR
41*/
42
43const bigInt = require("big-integer");
44const __P__ = new bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
45
46exports.add = add;
47exports.mul = mul;
48exports.evaluate = evaluate;
49exports.negate = negate;
50exports.sub = sub;
51exports.toQEQ = toQEQ;
52exports.isZero = isZero;
53exports.toString = toString;
54exports.canonize = canonize;
55
56function signal2lc(a) {
57 let lc;
58 if (a.type == "SIGNAL") {
59 lc = {
60 type: "LINEARCOMBINATION",
61 values: {}
62 };
63 lc.values[a.fullName] = bigInt(1);
64 return lc;
65 } else {
66 return a;
67 }
68}
69
70function clone(a) {
71 const res = {};
72 res.type = a.type;
73 if (a.type == "NUMBER") {
74 res.value = bigInt(a.value);
75 } else if (a.type == "LINEARCOMBINATION") {
76 res.values = {};
77 for (let k in a.values) {
78 res.values[k] = bigInt(a.values[k]);
79 }
80 } else if (a.type == "QEQ") {
81 res.a = clone(a.a);
82 res.b = clone(a.b);
83 res.c = clone(a.c);
84 } else if (a.type == "ERROR") {
85 res.errStr = a.errStr;
86 } else {
87 res.type = "ERROR";
88 res.errStr = "Invilid type when clonning: "+a.type;
89 }
90 return res;
91}
92
93function add(_a, _b) {
94 const a = signal2lc(_a);
95 const b = signal2lc(_b);
96 if (a.type == "ERROR") return a;
97 if (b.type == "ERROR") return b;
98 if (a.type == "NUMBER") {
99 if (b.type == "NUMBER") {
100 return addNumNum(a,b);
101 } else if (b.type=="LINEARCOMBINATION") {
102 return addLCNum(b,a);
103 } else if (b.type=="QEQ") {
104 return addQEQNum(b,a);
105 } else {
106 return { type: "ERROR", errStr: "LC Add Invalid Type 2: "+b.type };
107 }
108 } else if (a.type=="LINEARCOMBINATION") {
109 if (b.type == "NUMBER") {
110 return addLCNum(a,b);
111 } else if (b.type=="LINEARCOMBINATION") {
112 return addLCLC(a,b);
113 } else if (b.type=="QEQ") {
114 return addQEQLC(b,a);
115 } else {
116 return { type: "ERROR", errStr: "LC Add Invalid Type 2: "+b.type };
117 }
118 } else if (a.type=="QEQ") {
119 if (b.type == "NUMBER") {
120 return addQEQNum(a,b);
121 } else if (b.type=="LINEARCOMBINATION") {
122 return addQEQLC(a,b);
123 } else if (b.type=="QEQ") {
124 return { type: "ERROR", errStr: "QEQ + QEQ" };
125 } else {
126 return { type: "ERROR", errStr: "LC Add Invalid Type 2: "+b.type };
127 }
128 } else {
129 return { type: "ERROR", errStr: "LC Add Invalid Type 1: "+a.type };
130 }
131}
132
133function addNumNum(a,b) {
134 if (!a.value || !b.value) return { type: "NUMBER" };
135 return {
136 type: "NUMBER",
137 value: a.value.add(b.value).mod(__P__)
138 };
139}
140
141function addLCNum(a,b) {
142 let res = clone(a);
143 if (!b.value) {
144 return { type: "ERROR", errStr: "LinearCombination + undefined" };
145 }
146 if (b.value.isZero()) return res;
147 if (!res.values["one"]) {
148 res.values["one"]=bigInt(b.value);
149 } else {
150 res.values["one"]= res.values["one"].add(b.value).mod(__P__);
151 }
152 return res;
153}
154
155function addLCLC(a,b) {
156 let res = clone(a);
157 for (let k in b.values) {
158 if (!res.values[k]) {
159 res.values[k]=bigInt(b.values[k]);
160 } else {
161 res.values[k]= res.values[k].add(b.values[k]).mod(__P__);
162 }
163 }
164 return res;
165}
166
167function addQEQNum(a,b) {
168 let res = clone(a);
169 res.c = addLCNum(res.c, b);
170 if (res.c.type == "ERROR") return res.c;
171 return res;
172}
173
174function addQEQLC(a,b) {
175 let res = clone(a);
176 res.c = addLCLC(res.c, b);
177 if (res.c.type == "ERROR") return res.c;
178 return res;
179}
180
181function mul(_a, _b) {
182 const a = signal2lc(_a);
183 const b = signal2lc(_b);
184 if (a.type == "ERROR") return a;
185 if (b.type == "ERROR") return b;
186 if (a.type == "NUMBER") {
187 if (b.type == "NUMBER") {
188 return mulNumNum(a,b);
189 } else if (b.type=="LINEARCOMBINATION") {
190 return mulLCNum(b,a);
191 } else if (b.type=="QEQ") {
192 return mulQEQNum(b,a);
193 } else {
194 return { type: "ERROR", errStr: "LC Mul Invalid Type 2: "+b.type };
195 }
196 } else if (a.type=="LINEARCOMBINATION") {
197 if (b.type == "NUMBER") {
198 return mulLCNum(a,b);
199 } else if (b.type=="LINEARCOMBINATION") {
200 return mulLCLC(a,b);
201 } else if (b.type=="QEQ") {
202 return { type: "ERROR", errStr: "LC * QEQ" };
203 } else {
204 return { type: "ERROR", errStr: "LC Mul Invalid Type 2: "+b.type };
205 }
206 } else if (a.type=="QEQ") {
207 if (b.type == "NUMBER") {
208 return mulQEQNum(a,b);
209 } else if (b.type=="LINEARCOMBINATION") {
210 return { type: "ERROR", errStr: "QEC * LC" };
211 } else if (b.type=="QEQ") {
212 return { type: "ERROR", errStr: "QEQ * QEQ" };
213 } else {
214 return { type: "ERROR", errStr: "LC Mul Invalid Type 2: "+b.type };
215 }
216 } else {
217 return { type: "ERROR", errStr: "LC Mul Invalid Type 1: "+a.type };
218 }
219}
220
221
222function mulNumNum(a,b) {
223 if (!a.value || !b.value) return { type: "NUMBER" };
224 return {
225 type: "NUMBER",
226 value: a.value.times(b.value).mod(__P__)
227 };
228}
229
230function mulLCNum(a,b) {
231 let res = clone(a);
232 if (!b.value) {
233 return {type: "ERROR", errStr: "LinearCombination * undefined"};
234 }
235 for (let k in res.values) {
236 res.values[k] = res.values[k].times(b.value).mod(__P__);
237 }
238 return res;
239}
240
241function mulLCLC(a,b) {
242 return {
243 type: "QEQ",
244 a: clone(a),
245 b: clone(b),
246 c: { type: "LINEARCOMBINATION", values: {}}
247 };
248}
249
250function mulQEQNum(a,b) {
251 let res = {
252 type: "QEQ",
253 a: mulLCNum(a.a, b),
254 b: clone(a.b),
255 c: mulLCNum(a.c, b)
256 };
257 if (res.a.type == "ERROR") return res.a;
258 if (res.c.type == "ERROR") return res.a;
259 return res;
260}
261
262function getSignalValue(ctx, signalName) {
263 const s = ctx.signals[signalName];
264 if (s.equivalence != "") {
265 return getSignalValue(ctx, s.equivalence);
266 } else {
267 const res = {
268 type: "NUMBER"
269 };
270 if (s.value) {
271 res.value = s.value;
272 }
273 return res;
274 }
275}
276
277function evaluate(ctx, n) {
278 if (n.type == "NUMBER") {
279 return n;
280 } else if (n.type == "SIGNAL") {
281 return getSignalValue(ctx, n.fullName);
282 } else if (n.type == "LINEARCOMBINATION") {
283 const v= {
284 type: "NUMBER",
285 value: bigInt(0)
286 };
287 for (let k in n.values) {
288 const s = getSignalValue(ctx, k);
289 if (s.type != "NUMBER") return {type: "ERROR", errStr: "Invalid signal in linear Combination: " + k};
290 if (!s.value) return { type: "NUMBER" };
291 v.value = v.value.add( n.values[k].times(s.value)).mod(__P__);
292 }
293 return v;
294 } else if (n.type == "QEQ") {
295 const a = evaluate(ctx, n.a);
296 if (a.type == "ERROR") return a;
297 if (!a.value) return { type: "NUMBER" };
298 const b = evaluate(ctx, n.b);
299 if (b.type == "ERROR") return b;
300 if (!b.value) return { type: "NUMBER" };
301 const c = evaluate(ctx, n.c);
302 if (c.type == "ERROR") return c;
303 if (!c.value) return { type: "NUMBER" };
304
305 return {
306 type: "NUMBER",
307 value: (a.value.times(b.value).add(c.value)).mod(__P__)
308 };
309 } else if (n.type == "ERROR") {
310 return n;
311 } else {
312 return {type: "ERROR", errStr: "Invalid type in evaluate: "+n.type};
313 }
314}
315
316function negate(_a) {
317 const a = signal2lc(_a);
318 let res = clone(a);
319 if (res.type == "NUMBER") {
320 res.value = __P__.minus(a.value).mod(__P__);
321 } else if (res.type == "LINEARCOMBINATION") {
322 for (let k in res.values) {
323 res.values[k] = __P__.minus(res.values[k]).mod(__P__);
324 }
325 } else if (res.type == "QEQ") {
326 res.a = negate(res.a);
327 res.c = negate(res.c);
328 } else if (res.type == "ERROR") {
329 return res;
330 } else {
331 res = {type: "ERROR", errStr: "LC Negate invalid Type: "+res.type};
332 }
333 return res;
334}
335
336function sub(a, b) {
337 return add(a, negate(b));
338}
339
340function toQEQ(a) {
341 if (a.type == "NUMBER") {
342 return {
343 type: "QEQ",
344 a: {type: "LINEARCOMBINATION", values: {}},
345 b: {type: "LINEARCOMBINATION", values: {}},
346 c: {type: "LINEARCOMBINATION", values: {"one": bigInt(a.value)}}
347 };
348 } else if (a.type == "LINEARCOMBINATION") {
349 return {
350 type: "QEQ",
351 a: {type: "LINEARCOMBINATION", values: {}},
352 b: {type: "LINEARCOMBINATION", values: {}},
353 c: clone(a)
354 };
355 } else if (a.type == "QEQ") {
356 return clone(a);
357 } else if (a.type == "ERROR") {
358 return clone(a);
359 } else {
360 return {type: "ERROR", errStr: "toQEQ invalid Type: "+a.type};
361 }
362}
363
364function isZero(a) {
365 if (a.type == "NUMBER") {
366 return a.value.isZero();
367 } else if (a.type == "LINEARCOMBINATION") {
368 for (let k in a.values) {
369 if (!a.values[k].isZero()) return false;
370 }
371 return true;
372 } else if (a.type == "QEQ") {
373 return (isZero(a.a) || isZero(a.b)) && isZero(a.c);
374 } else if (a.type == "ERROR") {
375 return false;
376 } else {
377 return false;
378 }
379}
380
381function toString(a, ctx) {
382 if (a.type == "NUMBER") {
383 return a.value.toString();
384 } else if (a.type == "LINEARCOMBINATION") {
385 let S="";
386 for (let k in a.values) {
387 if (!a.values[k].isZero()) {
388 let c;
389 if (a.values[k].greater(__P__.divide(2))) {
390 S = S + "-";
391 c = __P__.minus(a.values[k]);
392 } else {
393 if (S!="") S=S+" + ";
394 c = a.values[k];
395 }
396 if (!c.equals(1)) {
397 S = S + c.toString() + "*";
398 }
399 let sigName = k;
400 if (ctx) {
401 while (ctx.signals[sigName].equivalence) sigName = ctx.signals[sigName].equivalence;
402 }
403 S = S + sigName;
404 }
405 }
406 if (S=="") return "0"; else return S;
407 } else if (a.type == "QEQ") {
408 return "( "+toString(a.a, ctx)+" ) * ( "+toString(a.b, ctx)+" ) + " + toString(a.c, ctx);
409 } else if (a.type == "ERROR") {
410 return "ERROR: "+a.errStr;
411 } else {
412 return "INVALID";
413 }
414}
415
416function canonize(ctx, a) {
417 if (a.type == "LINEARCOMBINATION") {
418 for (let k in a.values) {
419 let s = k;
420 while (ctx.signals[s].equivalence) s= ctx.signals[s].equivalence;
421 if (typeof(ctx.signals[s].value) != "undefined") {
422 const v = a.values[k].times(ctx.signals[s].value).mod(__P__);
423 if (!a.values["one"]) {
424 a.values["one"]=v;
425 } else {
426 a.values["one"]= a.values["one"].add(v).mod(__P__);
427 }
428 delete a.values[k];
429 } else if (s != k) {
430 if (!a.values[s]) {
431 a.values[s]=bigInt(a.values[k]);
432 } else {
433 a.values[s]= a.values[s].add(a.values[k]).mod(__P__);
434 }
435 delete a.values[k];
436 }
437 }
438 for (let k in a.values) {
439 if (a.values[k].isZero()) delete a.values[k];
440 }
441 return a;
442 } else if (a.type == "QEQ") {
443 a.a = canonize(ctx, a.a);
444 a.b = canonize(ctx, a.b);
445 a.c = canonize(ctx, a.c);
446 }
447 return a;
448}
449