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