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