circomlib/test/smt.js
test/smt.jsRaw
1const chai = require("chai");
2const path = require("path");
3const snarkjs = require("snarkjs");
4const compiler = require("circom");
5
6const smt = require("../src/smt.js");
7
8const assert = chai.assert;
9
10const bigInt = snarkjs.bigInt;
11
12function print(circuit, w, s) {
13 console.log(s + ": " + w[circuit.getSignalIdx(s)]);
14}
15
16async function testInsert(tree, key, value, circuit, log ) {
17
18 const res = await tree.insert(key,value);
19 let siblings = res.siblings;
20 while (siblings.length<10) siblings.push(bigInt(0));
21
22 const w = circuit.calculateWitness({
23 fnc: [1,0],
24 oldRoot: res.oldRoot,
25 newRoot: res.newRoot,
26 siblings: siblings,
27 oldKey: res.oldKey,
28 oldValue: res.oldValue,
29 isOld0: res.isOld0 ? 1 : 0,
30 newKey: key,
31 newValue: value
32 }, log);
33
34 const root1 = w[circuit.getSignalIdx("main.topSwitcher.outR")];
35 assert(circuit.checkWitness(w));
36 assert(root1.equals(res.newRoot));
37}
38
39async function testDelete(tree, key, circuit) {
40 const res = await tree.delete(key);
41 let siblings = res.siblings;
42 while (siblings.length<10) siblings.push(bigInt(0));
43
44 const w = circuit.calculateWitness({
45 fnc: [1,1],
46 oldRoot: res.oldRoot,
47 newRoot: res.newRoot,
48 siblings: siblings,
49 oldKey: res.oldKey,
50 oldValue: res.oldValue,
51 isOld0: res.isOld0 ? 1 : 0,
52 newKey: res.delKey,
53 newValue: res.delValue
54 });
55
56 const root1 = w[circuit.getSignalIdx("main.topSwitcher.outR")];
57
58 assert(circuit.checkWitness(w));
59 assert(root1.equals(res.newRoot));
60}
61
62async function testUpdate(tree, key, newValue, circuit) {
63 const res = await tree.update(key, newValue);
64 let siblings = res.siblings;
65 while (siblings.length<10) siblings.push(bigInt(0));
66
67 const w = circuit.calculateWitness({
68 fnc: [0,1],
69 oldRoot: res.oldRoot,
70 newRoot: res.newRoot,
71 siblings: siblings,
72 oldKey: res.oldKey,
73 oldValue: res.oldValue,
74 isOld0: 0,
75 newKey: res.newKey,
76 newValue: res.newValue
77 });
78
79 const root1 = w[circuit.getSignalIdx("main.topSwitcher.outR")];
80
81 assert(circuit.checkWitness(w));
82 assert(root1.equals(res.newRoot));
83}
84
85
86describe("SMT test", function () {
87 let circuit;
88 let tree;
89
90 this.timeout(100000);
91
92 before( async () => {
93 const cirDef = await compiler(path.join(__dirname, "circuits", "smtprocessor10_test.circom"));
94
95 circuit = new snarkjs.Circuit(cirDef);
96
97 console.log("NConstrains SMTProcessor: " + circuit.nConstraints);
98
99 tree = await smt.newMemEmptyTrie();
100 });
101
102 it("Should verify an insert to an empty tree", async () => {
103 const key = bigInt(111);
104 const value = bigInt(222);
105
106 await testInsert(tree, key, value, circuit);
107 });
108
109 it("It should add another element", async () => {
110 const key = bigInt(333);
111 const value = bigInt(444);
112
113 await testInsert(tree, key, value, circuit);
114 });
115
116
117
118 it("Should remove an element", async () => {
119 await testDelete(tree, 111, circuit);
120 await testDelete(tree, 333, circuit);
121 });
122
123 it("Should test convination of adding and removing 3 elements", async () => {
124 const keys = [bigInt(8), bigInt(9), bigInt(32)];
125 const values = [bigInt(88), bigInt(99), bigInt(3232)];
126 const tree1 = await smt.newMemEmptyTrie();
127 const tree2 = await smt.newMemEmptyTrie();
128 const tree3 = await smt.newMemEmptyTrie();
129 const tree4 = await smt.newMemEmptyTrie();
130 const tree5 = await smt.newMemEmptyTrie();
131 const tree6 = await smt.newMemEmptyTrie();
132
133 await testInsert(tree1,keys[0],values[0], circuit);
134 await testInsert(tree1,keys[1],values[1], circuit);
135 await testInsert(tree1,keys[2],values[2], circuit);
136
137 await testInsert(tree2,keys[0],values[0], circuit);
138 await testInsert(tree2,keys[2],values[2], circuit);
139 await testInsert(tree2,keys[1],values[1], circuit);
140
141 await testInsert(tree3,keys[1],values[1], circuit);
142 await testInsert(tree3,keys[0],values[0], circuit);
143 await testInsert(tree3,keys[2],values[2], circuit);
144
145 await testInsert(tree4,keys[1],values[1], circuit);
146 await testInsert(tree4,keys[2],values[2], circuit);
147 await testInsert(tree4,keys[0],values[0], circuit);
148
149 await testInsert(tree5,keys[2],values[2], circuit);
150 await testInsert(tree5,keys[0],values[0], circuit);
151 await testInsert(tree5,keys[1],values[1], circuit);
152
153 await testInsert(tree6,keys[2],values[2], circuit);
154 await testInsert(tree6,keys[1],values[1], circuit);
155 await testInsert(tree6,keys[0],values[0], circuit);
156
157
158 await testDelete(tree1, keys[0], circuit);
159 await testDelete(tree1, keys[1], circuit);
160 await testDelete(tree2, keys[1], circuit);
161 await testDelete(tree2, keys[0], circuit);
162
163 await testDelete(tree3, keys[0], circuit);
164 await testDelete(tree3, keys[2], circuit);
165 await testDelete(tree4, keys[2], circuit);
166 await testDelete(tree4, keys[0], circuit);
167
168
169 await testDelete(tree5, keys[1], circuit);
170 await testDelete(tree5, keys[2], circuit);
171 await testDelete(tree6, keys[2], circuit);
172 await testDelete(tree6, keys[1], circuit);
173
174 await testDelete(tree1, keys[2], circuit);
175 await testDelete(tree2, keys[2], circuit);
176 await testDelete(tree3, keys[1], circuit);
177 await testDelete(tree4, keys[1], circuit);
178 await testDelete(tree5, keys[0], circuit);
179 await testDelete(tree6, keys[0], circuit);
180 });
181
182 it("Should match a NOp with random vals", async () => {
183 let siblings = [];
184 while (siblings.length<10) siblings.push(bigInt(88));
185 const w = circuit.calculateWitness({
186 fnc: [0,0],
187 oldRoot: 11,
188 newRoot: 22,
189 siblings: siblings,
190 oldKey: 33,
191 oldValue: 44,
192 isOld0: 55,
193 newKey: 66,
194 newValue: 77
195 });
196
197 assert(circuit.checkWitness(w));
198
199 });
200 it("Should update an element", async () => {
201 const tree1 = await smt.newMemEmptyTrie();
202 const tree2 = await smt.newMemEmptyTrie();
203
204 await testInsert(tree1,8,88, circuit);
205 await testInsert(tree1,9,99, circuit);
206 await testInsert(tree1,32,3232, circuit);
207
208 await testInsert(tree2,8,888, circuit);
209 await testInsert(tree2,9,999, circuit);
210 await testInsert(tree2,32,323232, circuit);
211
212 await testUpdate(tree1, 8, 888, circuit);
213 await testUpdate(tree1, 9, 999, circuit);
214 await testUpdate(tree1, 32, 323232, circuit);
215 });
216
217 it("Should verify existance of an element", async () => {
218
219 });
220
221 it("Should verify non existance of an element", async () => {
222
223 });
224
225});