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