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