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