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