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