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
22 ///////////////
23 N: a
24
25 {
26 t: "N",
27 v: bigInt(a)
28 }
29
30 // Signal
31 ///////////////
32 {
33 t: "S",
34 sIdx: sIdx
35 }
36
37 // Linear Convination
38 //////////////////
39 LC: c1*s1 + c2*s2 + c3*s3
40 {
41 t: "LC",
42 coefs: {
43 s1: bigInt(c1),
44 s2: bigInt(c2),
45 s3: bigInt(c3)
46 }
47 }
48
49 // Quadratic Expression
50 //////////////////
51 QEX: a*b + c WHERE a,b,c are LC
52 {
53 t: "QEX"
54 a: { t: "LC", coefs: {...} },
55 b: { t: "LC", coefs: {...} },
56 c: { t: "LC", coefs: {...} }
57 }
58
59 NQ: Non quadratic expression
60 {
61 t: "NQ"
62 }
63 */
64
65/*
66+ N LC QEX NQ
67N N LC QEX NQ
68LC LC LC QEX NQ
69QEX QEX QEX NQ NQ
70NQ NQ NQ NQ NQ
71
72* N LC QEX NQ
73N N LC QEX NQ
74LC LC QEX NQ NQ
75QEX QEX NQ NQ NQ
76NQ NQ NQ NQ NQ
77*/
78
79const bigInt = require("big-integer");
80const utils = require("./utils");
81const sONE = 0;
82
83class LCAlgebra {
84 constructor (aField) {
85 const self = this;
86 this.field= aField;
87 [
88 ["lt",2],
89 ["leq",2],
90 ["eq",2],
91 ["neq",2],
92 ["geq",2],
93 ["gt",2],
94 ["idiv",2],
95 ["mod",2],
96 ["band",2],
97 ["bor",2],
98 ["bxor",2],
99 ["bnot",2],
100 ["land",2],
101 ["lor",2],
102 ["lnot",2],
103 ["shl",2],
104 ["shr",2],
105 ].forEach( (op) => {
106 self._genNQOp(op[0], op[1]);
107 });
108 }
109
110 _genNQOp(op, nOps) {
111 const self=this;
112 self[op] = function() {
113 const operands = [];
114 for (let i=0; i<nOps; i++) {
115 if (typeof(arguments[i]) !== "object") throw new Error("Invalid operand type");
116 if (arguments[i].t !== "N") return {t: "NQ"};
117 operands.push(arguments[i].v);
118 }
119 return {
120 t: "N",
121 v: self.field[op](...operands)
122 };
123 };
124 }
125
126 _signal2lc(a) {
127 if (a.t == "S") {
128 const lc = {
129 t: "LC",
130 coefs: {}
131 };
132 lc.coefs[a.sIdx] = bigInt(1);
133 return lc;
134 } else {
135 return a;
136 }
137 }
138
139
140 _clone(a) {
141 const res = {};
142 res.t = a.t;
143 if (a.t == "N") {
144 res.v = a.v;
145 } else if (a.t == "S") {
146 res.sIdx = a.sIdx;
147 } else if (a.t == "LC") {
148 res.coefs = {};
149 for (let k in a.coefs) {
150 res.coefs[k] = a.coefs[k];
151 }
152 } else if (a.t == "QEX") {
153 res.a = this._clone(a.a);
154 res.b = this._clone(a.b);
155 res.c = this._clone(a.c);
156 }
157 return res;
158 }
159
160 add(_a,_b) {
161 const self = this;
162 const a = self._signal2lc(_a);
163 const b = self._signal2lc(_b);
164 if (a.t == "NQ") return a;
165 if (b.t == "NQ") return b;
166 if (a.t == "N") {
167 if (b.t == "N") {
168 return add_N_N(a,b);
169 } else if (b.t=="LC") {
170 return add_LC_N(b,a);
171 } else if (b.t=="QEX") {
172 return add_QEX_N(b,a);
173 } else {
174 return { type: "NQ" };
175 }
176 } else if (a.t=="LC") {
177 if (b.t == "N") {
178 return add_LC_N(a,b);
179 } else if (b.t=="LC") {
180 return add_LC_LC(a,b);
181 } else if (b.t=="QEX") {
182 return add_QEX_LC(b,a);
183 } else {
184 return { t: "NQ" };
185 }
186 } else if (a.t=="QEX") {
187 if (b.t == "N") {
188 return add_QEX_N(a,b);
189 } else if (b.t=="LC") {
190 return add_QEX_LC(a,b);
191 } else if (b.t=="QEX") {
192 return { t: "NQ" };
193 } else {
194 return { t: "NQ" };
195 }
196 } else {
197 return { t: "NQ" };
198 }
199
200 function add_N_N(a,b) {
201 return {
202 t: "N",
203 v: self.field.add(a.v, b.v)
204 };
205 }
206
207 function add_LC_N(a,b) {
208 let res = self._clone(a);
209 if (b.v.isZero()) return res;
210 if (!utils.isDefined(res.coefs[sONE])) {
211 res.coefs[sONE]= b.v;
212 } else {
213 res.coefs[sONE]= self.field.add(res.coefs[sONE], b.v);
214 }
215 return res;
216 }
217
218 function add_LC_LC(a,b) {
219 let res = self._clone(a);
220 for (let k in b.coefs) {
221 if (!utils.isDefined(res.coefs[k])) {
222 res.coefs[k]=b.coefs[k];
223 } else {
224 res.coefs[k]= self.field.add(res.coefs[k], b.coefs[k]);
225 }
226 }
227 return res;
228 }
229
230 function add_QEX_N(a,b) {
231 let res = self._clone(a);
232 res.c = add_LC_N(res.c, b);
233 return res;
234 }
235
236 function add_QEX_LC(a,b) {
237 let res = self._clone(a);
238 res.c = add_LC_LC(res.c, b);
239 return res;
240 }
241 }
242
243 mul(_a,_b) {
244 const self = this;
245 const a = self._signal2lc(_a);
246 const b = self._signal2lc(_b);
247 if (a.t == "NQ") return a;
248 if (b.t == "NQ") return b;
249 if (a.t == "N") {
250 if (b.t == "N") {
251 return mul_N_N(a,b);
252 } else if (b.t=="LC") {
253 return mul_LC_N(b,a);
254 } else if (b.t=="QEX") {
255 return mul_QEX_N(b,a);
256 } else {
257 return { t: "NQ"};
258 }
259 } else if (a.t=="LC") {
260 if (b.t == "N") {
261 return mul_LC_N(a,b);
262 } else if (b.t=="LC") {
263 return mul_LC_LC(a,b);
264 } else if (b.t=="QEX") {
265 return { t: "NQ" };
266 } else {
267 return { t: "NQ" };
268 }
269 } else if (a.t=="QEX") {
270 if (b.t == "N") {
271 return mul_QEX_N(a,b);
272 } else if (b.t=="LC") {
273 return { t: "NQ" };
274 } else if (b.t=="QEX") {
275 return { t: "NQ" };
276 } else {
277 return { t: "NQ" };
278 }
279 } else {
280 return { t: "NQ" };
281 }
282
283 function mul_N_N(a,b) {
284 return {
285 t: "N",
286 v: self.field.mul(a.v, b.v)
287 };
288 }
289
290 function mul_LC_N(a,b) {
291 let res = self._clone(a);
292 for (let k in res.coefs) {
293 res.coefs[k] = self.field.mul(res.coefs[k], b.v);
294 }
295 return res;
296 }
297
298 function mul_LC_LC(a,b) {
299 return {
300 t: "QEX",
301 a: self._clone(a),
302 b: self._clone(b),
303 c: { t: "LC", coefs: {}}
304 };
305 }
306
307 function mul_QEX_N(a,b) {
308 return {
309 t: "QEX",
310 a: mul_LC_N(a.a, b),
311 b: self._clone(a.b),
312 c: mul_LC_N(a.c, b)
313 };
314 }
315 }
316
317 neg(_a) {
318 const a = this._signal2lc(_a);
319 let res = this._clone(a);
320 if (res.t == "N") {
321 res.v = this.field.neg(a.v);
322 } else if (res.t == "LC") {
323 for (let k in res.coefs) {
324 res.coefs[k] = this.field.neg(res.coefs[k]);
325 }
326 } else if (res.t == "QEX") {
327 res.a = this.neg(res.a);
328 res.c = this.neg(res.c);
329 } else {
330 res = {t: "NQ"};
331 }
332 return res;
333 }
334
335 sub(a, b) {
336 return this.add(a, this.neg(b));
337 }
338
339 div(a, b) {
340 if (b.t == "N") {
341 if (b.v.isZero()) throw new Error("Division by zero");
342 const inv = {
343 t: "N",
344 v: this.field.inv(b.v)
345 };
346 return this.mul(a, inv);
347 } else {
348 return {t: "NQ"};
349 }
350 }
351
352 pow(a, b) {
353 if (b.t == "N") {
354 if (b.v.isZero()) {
355 if (this.isZero(a)) {
356 throw new Error("Zero to the Zero");
357 }
358 return {
359 t: "N",
360 v: this.field.one
361 };
362 } else if (b.v.eq(this.field.one)) {
363 return a;
364 } else if (b.v.eq(bigInt(2))) {
365 return this.mul(a,a);
366 } else {
367 if (a.t=="N") {
368 return {
369 t: "N",
370 v: this.field.pow(a.v, b.v)
371 };
372 } else {
373 return {t: "NQ"};
374 }
375 }
376 } else {
377 return {t: "NQ"};
378 }
379 }
380
381 substitute(where, signal, equivalence) {
382 if (equivalence.t != "LC") throw new Error("Equivalence must be a Linear Combination");
383 if (where.t == "LC") {
384 if (!utils.isDefined(where.coefs[signal]) || where.coefs[signal].isZero()) return where;
385 const res=this._clone(where);
386 const coef = res.coefs[signal];
387 for (let k in equivalence.coefs) {
388 if (k != signal) {
389 const v = this.field.mul( coef, equivalence.coefs[k] );
390 if (!utils.isDefined(res.coefs[k])) {
391 res.coefs[k]=v;
392 } else {
393 res.coefs[k]= this.field.add(res.coefs[k],v);
394 }
395 if (res.coefs[k].isZero()) delete res.coefs[k];
396 }
397 }
398 delete res.coefs[signal];
399 return res;
400 } else if (where.t == "QEX") {
401 const res = {
402 t: "QEX",
403 a: this.substitute(where.a, signal, equivalence),
404 b: this.substitute(where.b, signal, equivalence),
405 c: this.substitute(where.c, signal, equivalence)
406 };
407 return res;
408 } else {
409 return where;
410 }
411 }
412
413 toQEX(a) {
414 if (a.t == "N") {
415 const res = {
416 t: "QEX",
417 a: {t: "LC", coefs: {}},
418 b: {t: "LC", coefs: {}},
419 c: {t: "LC", coefs: {}}
420 };
421 res.c[sONE] = a.v;
422 return res;
423 } else if (a.t == "LC") {
424 return {
425 t: "QEX",
426 a: {t: "LC", coefs: {}},
427 b: {t: "LC", coefs: {}},
428 c: this._clone(a)
429 };
430 } else if (a.t == "QEX") {
431 return this._clone(a);
432 } else {
433 throw new Error(`Type ${a.t} can not be converted to QEX`);
434 }
435 }
436
437 isZero(a) {
438 if (a.t == "N") {
439 return a.v.isZero();
440 } else if (a.t == "LC") {
441 for (let k in a.coefs) {
442 if (!a.coefs[k].isZero()) return false;
443 }
444 return true;
445 } else if (a.t == "QEX") {
446 return (this.isZero(a.a) || this.isZero(a.b)) && this.isZero(a.c);
447 } else {
448 return false;
449 }
450 }
451
452 toString(a, ctx) {
453 if (a.t == "N") {
454 return a.v.toString();
455 } else if (a.t == "LC") {
456 let S="";
457 for (let k in a.coefs) {
458 if (!a.coefs[k].isZero()) {
459 let c;
460 if (a.coefs[k].greater(this.field.p.divide(2))) {
461 S = S + "-";
462 c = this.field.p.minus(a.coefs[k]);
463 } else {
464 if (S!="") S=S+" + ";
465 c = a.coefs[k];
466 }
467 if (!c.equals(bigInt.one)) {
468 S = S + c.toString() + "*";
469 }
470 let sIdx = k;
471 if (ctx) {
472 while (ctx.signals[sIdx].e>=0) sIdx = ctx.signals[sIdx].e;
473 }
474 S = S + "[" + sIdx + "]";
475 }
476 }
477 if (S=="") return "0"; else return S;
478 } else if (a.t == "QEX") {
479 return "( "+
480 this.toString(a.a, ctx)+" ) * ( "+
481 this.toString(a.b, ctx)+" ) + " +
482 this.toString(a.c, ctx);
483 } else {
484 return "NQ";
485 }
486 }
487
488 evaluate(ctx, n) {
489 if (n.t == "N") {
490 return n.v;
491 } else if (n.t == "SIGNAL") {
492 return getSignalValue(ctx, n.sIdx);
493 } else if (n.t == "LC") {
494 let v= this.field.zero;
495 for (let k in n.coefs) {
496 const s = getSignalValue(ctx, k);
497 if (s === null) return null;
498 v = this.field.add(v, this.field.mul( n.coefs[k], s));
499 }
500 return v;
501 } else if (n.type == "QEX") {
502 const a = this.evaluate(ctx, n.a);
503 if (a === null) return null;
504 const b = this.evaluate(ctx, n.b);
505 if (b === null) return null;
506 const c = this.evaluate(ctx, n.c);
507 if (c === null) return null;
508
509 return this.field.add(this.field.mul(a,b), c);
510 } else {
511 return null;
512 }
513
514
515 function getSignalValue(ctx, sIdx) {
516 let s = ctx.signals[sIdx];
517 while (s.e>=0) s = ctx.signals[s.e];
518 if (utils.isDefined(s.v)) return s.v;
519 return null;
520 }
521
522 }
523
524
525 canonize(ctx, a) {
526 if (a.t == "LC") {
527 const res = this._clone(a);
528 for (let k in a.coefs) {
529 let s = k;
530 while (ctx.signals[s].e>=0) s= ctx.signals[s].e;
531 if (utils.isDefined(ctx.signals[s].v)&&(k != sONE)) {
532 const v = this.field.mul(res.coefs[k], ctx.signals[s].v);
533 if (!utils.isDefined(res.coefs[sONE])) {
534 res.coefs[sONE]=v;
535 } else {
536 res.coefs[sONE]= this.field.add(res.coefs[sONE], v);
537 }
538 delete res.coefs[k];
539 } else if (s != k) {
540 if (!utils.isDefined(res.coefs[s])) {
541 res.coefs[s]=res.coefs[k];
542 } else {
543 res.coefs[s]= this.field.add(res.coefs[s], res.coefs[k]);
544 }
545 delete res.coefs[k];
546 }
547 }
548 for (let k in res.coefs) {
549 if (res.coefs[k].isZero()) delete res.coefs[k];
550 }
551 return res;
552 } else if (a.t == "QEX") {
553 const res = {
554 t: "QEX",
555 a: this.canonize(ctx, a.a),
556 b: this.canonize(ctx, a.b),
557 c: this.canonize(ctx, a.c)
558 };
559 return res;
560 } else {
561 return a;
562 }
563 }
564}
565
566module.exports = LCAlgebra;
567
568
569
570
571
572