websnark/test/f1.js
test/f1.jsRaw
1const assert = require("assert");
2const bigInt = require("big-integer");
3
4const buildF1 = require("../index.js").buildF1;
5
6describe("Basic tests for Zq", () => {
7 it("It should do a basic addition", async () => {
8 const f1 = await buildF1(101);
9
10 const pA = f1.allocInt(3);
11 const pB = f1.allocInt(4);
12 const pC = f1.allocInt();
13 f1.f1_add(pA, pB, pC);
14
15 const c = f1.getInt(pC);
16 assert.equal(c, 7);
17 });
18 it("Should add with 2 chunks", async () => {
19 const f1 = await buildF1(bigInt("100000000000000000001", 16));
20
21 const pA = f1.allocInt(bigInt("FFFFFFFFFFFFFFFF", 16));
22 const pB = f1.allocInt(1);
23 const pC = f1.allocInt();
24
25 f1.f1_add(pA, pB, pC);
26 const c = f1.getInt(pC);
27
28 assert(c.equals(bigInt("10000000000000000", 16)));
29 });
30 it("Should add with 2 chunks overflow", async () => {
31 const q = bigInt("10000000000000001", 16);
32 const f1 = await buildF1(q);
33
34 const pA = f1.allocInt(bigInt("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16).mod(q));
35 const pB = f1.allocInt(1);
36 const pC = f1.allocInt();
37
38 f1.f1_add(pA, pB, pC);
39 const c = f1.getInt(pC);
40
41 assert(c.equals(1));
42 });
43 it("Should add with double overflow", async () => {
44 const q = bigInt(1).shiftLeft(255).add(1);
45 const a = bigInt(1).shiftLeft(256).minus(1).mod(q);
46 const f1 = await buildF1(q);
47
48 const pA = f1.allocInt(a);
49 const pC = f1.allocInt();
50
51 f1.f1_add(pA, pA, pC);
52
53 const c = f1.getInt(pC);
54 assert(c.equals(a.add(a).mod(q)));
55 });
56 it("It should do a basic substraction", async () => {
57 const f1 = await buildF1(101);
58
59 const pA = f1.allocInt(5);
60 const pB = f1.allocInt(3);
61 const pC = f1.allocInt();
62
63 f1.f1_sub(pA, pB, pC);
64 const c = f1.getInt(pC);
65
66 assert.equal(c, 2);
67 });
68 it("It should do a basic substraction with negative result", async () => {
69 const f1 = await buildF1(101);
70
71 const pA = f1.allocInt(3);
72 const pB = f1.allocInt(5);
73 const pC = f1.allocInt();
74
75 f1.f1_sub(pA, pB, pC);
76 const c = f1.getInt(pC);
77
78 assert.equal(c.mod(101), 99);
79 });
80 it("Should substract with 2 chunks overflow", async () => {
81 const q = bigInt("10000000000000001", 16);
82 const a = bigInt("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16).mod(q);
83 const f1 = await buildF1(q);
84
85 const pA = f1.allocInt(1);
86 const pB = f1.allocInt(a);
87 const pC = f1.allocInt();
88
89 f1.f1_sub(pA, pB, pC);
90 const c = f1.getInt(pC);
91
92 let d = bigInt.one.minus(a).mod(q);
93 if (d.isNegative()) d = d.add(q);
94
95 assert(c.equals(d));
96 });
97 it("It should Substract a big number", async () => {
98 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
99 const f1 = await buildF1(q);
100
101 const a = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808495617");
102 const b = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808234523");
103
104 const pA = f1.allocInt(a);
105 const pB = f1.allocInt(b);
106 const pC = f1.allocInt();
107
108 f1.f1_sub(pA, pB, pC);
109 const c = f1.getInt(pC);
110
111 let cc = a.minus(b).mod(q);
112 if (cc.isNegative()) cc = cc.add(q);
113 assert(cc.equals(c.mod(q)));
114
115
116 const pAA = f1.allocInt(b);
117 const pBB = f1.allocInt(a);
118 const pCC = f1.allocInt();
119
120 f1.f1_sub(pAA, pBB, pCC);
121 const d = f1.getInt(pCC);
122
123 let dd = b.minus(a).mod(q);
124 if (dd.isNegative()) dd = dd.add(q);
125 assert(dd.equals(d.mod(q)));
126 });
127
128 it("It should do a basic multiplication", async () => {
129 const f1 = await buildF1(101);
130
131 const pA = f1.allocInt(3);
132 const pB = f1.allocInt(4);
133 const pC = f1.allocInt2();
134
135 f1.int_mul(pA, pB, pC);
136 const c = f1.getInt2(pC);
137
138 assert.equal(c, 12);
139 });
140
141 it("It should do a basic division", async () => {
142 const f1 = await buildF1(101);
143
144 const pA = f1.allocInt(12);
145 const pB = f1.allocInt(6);
146 const pC = f1.allocInt();
147 f1.int_div(pA, pB, pC);
148
149 const c = f1.getInt(pC);
150 assert.equal(c, 2);
151 });
152 it("It should do a more complex division", async () => {
153 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
154 const f1 = await buildF1(q);
155
156 const pA = f1.allocInt(bigInt("FFFF00000000", 16));
157 const pB = f1.allocInt(bigInt("100000000", 16));
158 const pC = f1.allocInt();
159 f1.int_div(pA, pB, pC);
160
161 const c = f1.getInt(pC);
162 assert(c.equals(bigInt("FFFF", 16)));
163 });
164 it("It should do a division by zero", async () => {
165 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
166 const f1 = await buildF1(q);
167
168 const pA = f1.allocInt(bigInt("FFFF00000000", 16));
169 const pB = f1.allocInt(0);
170 const pC = f1.allocInt();
171 try {
172 f1.int_div(pA, pB, pC);
173 assert(false, "Didn't throw...");
174 } catch (err) {
175 assert.equal(err.toString(), "RuntimeError: divide by zero");
176 }
177 });
178
179 it("It should do a various division", async () => {
180 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
181 const f1 = await buildF1(q);
182
183
184 const v= [
185 bigInt.zero,
186 q.minus(1),
187 q.minus(2),
188 q.minus(1).shiftRight(1),
189 q.minus(1).shiftRight(1).add(1),
190 q.minus(1).shiftRight(1).add(2),
191 q.minus(1).shiftRight(1).minus(1),
192 q.minus(1).shiftRight(1).minus(2),
193 bigInt(bigInt("F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0", 16)),
194 bigInt(bigInt("10101010101010101010101010101010", 16)),
195 bigInt(bigInt("FF00FF00FF00FF00FF00FF00FF00FF00", 16)),
196 bigInt(bigInt("11001100110011001100110011001100", 16)),
197 bigInt(bigInt("F0F0F0F0F0F0F0F0", 16)),
198 bigInt(bigInt("1010101010101010", 16)),
199 bigInt(bigInt("FF00FF00FF00FF00", 16)),
200 bigInt(bigInt("1100110011001100", 16)),
201 bigInt(2),
202 bigInt.one,
203 ];
204
205 const pA = f1.allocInt();
206 const pB = f1.allocInt();
207 const pC = f1.allocInt();
208 const pR = f1.allocInt();
209 for (let i=0; i<v.length; i++) {
210 for (let j=1; j<v.length; j++) {
211 const expected_c = v[i].divide(v[j]);
212 const expected_r = v[i].mod(v[j]);
213
214 f1.putInt(pA, v[i]);
215 f1.putInt(pB, v[j]);
216
217 f1.int_div(pA, pB, pC, pR);
218
219 const c = f1.getInt(pC);
220 const r = f1.getInt(pR);
221
222 assert(expected_r.equals(r));
223 assert(expected_c.equals(c));
224 }
225 }
226
227 });
228
229 it("It should do a basic reduction 1", async () => {
230 const f1 = await buildF1(bigInt("FFFFFFFFFFFFFFFF",16));
231
232 const pA = f1.allocInt2(bigInt(0x10000000000000000));
233 const pC = f1.allocInt();
234
235 f1.f1m_mReduct(pA, pC);
236
237 const c = f1.getInt(pC);
238
239 assert.equal(c, 1);
240 });
241 it("It should do a basic reduction 2", async () => {
242 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
243 const f1 = await buildF1(q);
244
245 const a = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808495617");
246 const b = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808234523");
247
248 const pA = f1.allocInt(a);
249 const pB = f1.allocInt(b);
250 const pC = f1.allocInt2();
251 const pD = f1.allocInt();
252
253 f1.int_mul(pA, pB, pC);
254 const c = f1.getInt2(pC);
255
256 f1.f1m_mReduct(pC, pD);
257 const d = f1.getInt(pD);
258
259 const r = bigInt.one.shiftLeft(256).mod(q);
260 const r2 = r.times(r).mod(q);
261
262 const pR2 = f1.allocInt(r2);
263
264
265 const pE = f1.allocInt2();
266 f1.int_mul(pD, pR2, pE);
267
268 const pF = f1.allocInt();
269 f1.f1m_mReduct(pE, pF);
270
271 const f = f1.getInt2(pF);
272
273 assert(a.times(b).mod(q).equals(f.mod(q)));
274 });
275 it("It should do a basic reduction 3", async () => {
276 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
277 const f1 = await buildF1(q);
278
279 const a = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808495617");
280 const b = bigInt("10000242871839275222246405745257275088548364400416034343698204186575808234523");
281
282 const pA = f1.allocInt(a);
283 const pB = f1.allocInt(b);
284 const pC = f1.allocInt();
285
286 f1.f1_mul(pA, pB, pC);
287
288 const c = f1.getInt2(pC);
289 assert(a.times(b).mod(q).equals(c.mod(q)));
290 });
291 it("It should do various test in zq Snarks modules", async () => {
292 const q = bigInt("21888242871839275222246405745257275088696311157297823662689037894645226208583");
293 const f1 = await buildF1(q);
294 const v= [
295 q.minus(1),
296 q.minus(2),
297 q.minus(1).shiftRight(1),
298 q.minus(1).shiftRight(1).add(1),
299 q.minus(1).shiftRight(1).add(2),
300 q.minus(1).shiftRight(1).minus(1),
301 q.minus(1).shiftRight(1).minus(2),
302 bigInt(2),
303 bigInt.one,
304 bigInt.zero
305 ];
306
307 const pA = f1.allocInt();
308 const pB = f1.allocInt();
309 const pC = f1.allocInt();
310 let c;
311
312 for (let i=0; i<v.length; i++) {
313 for (let j=0; j<5; j++) {
314
315 f1.putInt(pA, v[i]);
316 f1.putInt(pB, v[j]);
317
318 // eq
319 assert.equal( f1.int_eq(pA,pB), (i==j));
320
321 // add
322 f1.f1_add(pA, pB, pC);
323 c = f1.getInt2(pC);
324 assert(c.equals(v[i].add(v[j]).mod(q)));
325
326 // sub
327 f1.f1_sub(pA, pB, pC);
328 c = f1.getInt2(pC);
329
330 let s = v[i].minus(v[j]).mod(q);
331 if (s.isNegative()) s=s.add(q);
332 assert(c.equals(s));
333
334 // mul
335 f1.f1_mul(pA, pB, pC);
336 c = f1.getInt2(pC);
337 assert(c.equals(v[i].times(v[j]).mod(q)));
338 }
339 }
340 });
341 it("It should do a test", async () => {
342 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
343 const f1 = await buildF1(q);
344
345 const t = f1.test_F1(1000000);
346
347 console.log(t);
348
349 }).timeout(10000000);
350 it("Should test to montgomery", async () => {
351 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
352 const f1 = await buildF1(q);
353
354 const r = bigInt(11);
355
356 const pR = f1.allocInt(r);
357 const pRes = f1.allocInt();
358 const pRes2 = f1.allocInt();
359
360 f1.f1m_toMontgomery(pR, pRes);
361 const res = f1.getInt(pRes);
362
363 f1.f1m_fromMontgomery(pRes, pRes2);
364 const res2 = f1.getInt(pRes2);
365
366 assert(res.equals(r.times( bigInt.one.shiftLeft(256)).mod(q)));
367 assert(res2.equals(r));
368 });
369 it("Should convert back and forth montgomery", async () => {
370 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
371 const v= [
372 q.minus(1),
373 q.minus(2),
374 q.minus(1).shiftRight(1),
375 q.minus(1).shiftRight(1).add(1),
376 q.minus(1).shiftRight(1).add(2),
377 q.minus(1).shiftRight(1).minus(1),
378 q.minus(1).shiftRight(1).minus(2),
379 bigInt(2),
380 bigInt.one,
381 bigInt.zero
382 ];
383 const f1 = await buildF1(q);
384
385 const pA = f1.allocInt();
386
387 for (let i=0; i<v.length; i++) {
388 f1.putInt(pA, v[i]);
389
390 f1.f1m_toMontgomery(pA, pA);
391 f1.f1m_fromMontgomery(pA, pA);
392
393 const a = f1.getInt(pA);
394 assert(v[i].equals(a));
395 }
396 });
397 it("Should do inverse", async () => {
398 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
399 const v= [
400 bigInt.one,
401 q.minus(1),
402 q.minus(2),
403 q.minus(1).shiftRight(1),
404 q.minus(1).shiftRight(1).add(1),
405 q.minus(1).shiftRight(1).add(2),
406 q.minus(1).shiftRight(1).minus(1),
407 q.minus(1).shiftRight(1).minus(2),
408 bigInt(2),
409 ];
410 const f1 = await buildF1(q);
411
412 const pA = f1.allocInt();
413 const pB = f1.allocInt();
414 const pQ = f1.allocInt();
415
416 f1.putInt(pQ, q);
417
418 for (let i=0; i<v.length; i++) {
419 f1.putInt(pA, v[i]);
420
421 f1.int_inverseMod(pA, pQ, pB);
422
423 const b = f1.getInt(pB);
424 assert(b.equals(v[i].modInv(q)));
425 }
426 });
427 it("Should do inverse in montgomery", async () => {
428 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
429 const v= [
430 bigInt.one,
431 q.minus(1),
432 q.minus(2),
433 q.minus(1).shiftRight(1),
434 q.minus(1).shiftRight(1).add(1),
435 q.minus(1).shiftRight(1).add(2),
436 q.minus(1).shiftRight(1).minus(1),
437 q.minus(1).shiftRight(1).minus(2),
438 bigInt(2),
439 ];
440 const f1 = await buildF1(q);
441
442 const pA = f1.allocInt();
443 const pB = f1.allocInt();
444 const pC = f1.allocInt();
445
446 for (let i=0; i<v.length; i++) {
447 f1.putInt(pA, v[i]);
448
449 f1.f1m_toMontgomery(pA, pA);
450 f1.f1m_inverse(pA, pB);
451 f1.f1m_mul(pA, pB, pC);
452 f1.f1m_fromMontgomery(pC, pC);
453
454 const c = f1.getInt(pC);
455 assert(c.equals(1));
456 }
457 });
458 it("Test Neg", async () => {
459 const q = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
460 const v= [
461 bigInt.one,
462 q.minus(1),
463 q.minus(2),
464 q.minus(1).shiftRight(1),
465 q.minus(1).shiftRight(1).add(1),
466 q.minus(1).shiftRight(1).add(2),
467 q.minus(1).shiftRight(1).minus(1),
468 q.minus(1).shiftRight(1).minus(2),
469 bigInt(2),
470 ];
471 const f1 = await buildF1(q);
472
473 const pA = f1.allocInt();
474
475 for (let i=0; i<v.length; i++) {
476 f1.putInt(pA, v[i]);
477
478 f1.f1m_neg(pA);
479 f1.f1m_neg(pA);
480
481 const a = f1.getInt(pA);
482 assert(a.equals(v[i]));
483 }
484 });
485});