1const chai = require("chai");
  2const path = require("path");
  3const wasm_tester = require("circom_tester").wasm;
  4const F1Field = require("ffjavascript").F1Field;
  5const Scalar = require("ffjavascript").Scalar;
  6
  7const newMemEmptyTrie = require("circomlibjs").newMemEmptyTrie;
  8
  9const assert = chai.assert;
 10
 11function print(circuit, w, s) {
 12    console.log(s + ": " + w[circuit.getSignalIdx(s)]);
 13}
 14
 15async function testInsert(tree, _key, _value, circuit ) {
 16    const key = tree.F.e(_key);
 17    const value = tree.F.e(_value)
 18
 19    const res = await tree.insert(key,value);
 20    let siblings = res.siblings;
 21    for (let i=0; i<siblings.length; i++) siblings[i] = tree.F.toObject(siblings[i]);
 22    while (siblings.length<10) siblings.push(0);
 23
 24    const w = await circuit.calculateWitness({
 25        fnc: [1,0],
 26        oldRoot: tree.F.toObject(res.oldRoot),
 27        siblings: siblings,
 28        oldKey: res.isOld0 ? 0 : tree.F.toObject(res.oldKey),
 29        oldValue: res.isOld0 ? 0 : tree.F.toObject(res.oldValue),
 30        isOld0: res.isOld0 ? 1 : 0,
 31        newKey: tree.F.toObject(key),
 32        newValue: tree.F.toObject(value)
 33    }, true);
 34
 35    await circuit.checkConstraints(w);
 36
 37    await circuit.assertOut(w, {newRoot: tree.F.toObject(res.newRoot)});
 38
 39}
 40
 41async function testDelete(tree, _key, circuit) {
 42    const key = tree.F.e(_key);
 43    const res = await tree.delete(key);
 44    let siblings = res.siblings;
 45    for (let i=0; i<siblings.length; i++) siblings[i] = tree.F.toObject(siblings[i]);
 46    while (siblings.length<10) siblings.push(0);
 47
 48    const w = await circuit.calculateWitness({
 49        fnc: [1,1],
 50        oldRoot: tree.F.toObject(res.oldRoot),
 51        siblings: siblings,
 52        oldKey: res.isOld0 ? 0 : tree.F.toObject(res.oldKey),
 53        oldValue: res.isOld0 ? 0 : tree.F.toObject(res.oldValue),
 54        isOld0: res.isOld0 ? 1 : 0,
 55        newKey: tree.F.toObject(res.delKey),
 56        newValue: tree.F.toObject(res.delValue)
 57    }, true);
 58
 59    await circuit.checkConstraints(w);
 60
 61    await circuit.assertOut(w, {newRoot: tree.F.toObject(res.newRoot)});
 62}
 63
 64async function testUpdate(tree, _key, _newValue, circuit) {
 65    const key = tree.F.e(_key);
 66    const newValue = tree.F.e(_newValue);
 67    const res = await tree.update(key, newValue);
 68    let siblings = res.siblings;
 69    for (let i=0; i<siblings.length; i++) siblings[i] = tree.F.toObject(siblings[i]);
 70    while (siblings.length<10) siblings.push(0);
 71
 72    const w = await circuit.calculateWitness({
 73        fnc: [0,1],
 74        oldRoot: tree.F.toObject(res.oldRoot),
 75        siblings: siblings,
 76        oldKey: tree.F.toObject(res.oldKey),
 77        oldValue: tree.F.toObject(res.oldValue),
 78        isOld0: 0,
 79        newKey: tree.F.toObject(res.newKey),
 80        newValue: tree.F.toObject(res.newValue)
 81    });
 82
 83    await circuit.checkConstraints(w);
 84
 85    await circuit.assertOut(w, {newRoot: tree.F.toObject(res.newRoot)});
 86}
 87
 88
 89describe("SMT Processor test", function () {
 90    let circuit;
 91    let tree;
 92    let Fr;
 93
 94    this.timeout(1000000000);
 95
 96    before( async () => {
 97        circuit = await wasm_tester(path.join(__dirname, "circuits", "smtprocessor10_test.circom"));
 98        await circuit.loadSymbols();
 99
100        tree = await newMemEmptyTrie();
101        Fr = tree.F;
102    });
103
104    it("Should verify an insert to an empty tree", async () => {
105        const key = Fr.e(111);
106        const value = Fr.e(222);
107
108        await testInsert(tree, key, value, circuit);
109    });
110
111    it("It should add another element", async () => {
112        const key = Fr.e(333);
113        const value = Fr.e(444);
114
115        await testInsert(tree, key, value, circuit);
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 = [Fr.e(8), Fr.e(9), Fr.e(32)];
125        const values = [Fr.e(88), Fr.e(99), Fr.e(3232)];
126        const tree1 = await newMemEmptyTrie();
127        const tree2 = await newMemEmptyTrie();
128        const tree3 = await newMemEmptyTrie();
129        const tree4 = await newMemEmptyTrie();
130        const tree5 = await newMemEmptyTrie();
131        const tree6 = await 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(88);
185        const w = await circuit.calculateWitness({
186            fnc: [0,0],
187            oldRoot: 11,
188            siblings: siblings,
189            oldKey: 33,
190            oldValue: 44,
191            isOld0: 55,
192            newKey: 66,
193            newValue: 77
194        });
195
196        const root1 = Fr.e(w[circuit.symbols["main.oldRoot"].varIdx]);
197        const root2 = Fr.e(w[circuit.symbols["main.newRoot"].varIdx]);
198
199        await circuit.checkConstraints(w);
200
201        assert(Fr.eq(root1, root2));
202    });
203    it("Should update an element", async () => {
204        const tree1 = await newMemEmptyTrie();
205        const tree2 = await newMemEmptyTrie();
206
207        await testInsert(tree1,8,88, circuit);
208        await testInsert(tree1,9,99, circuit);
209        await testInsert(tree1,32,3232, circuit);
210
211        await testInsert(tree2,8,888, circuit);
212        await testInsert(tree2,9,999, circuit);
213        await testInsert(tree2,32,323232, circuit);
214
215        await testUpdate(tree1, 8, 888, circuit);
216        await testUpdate(tree1, 9, 999, circuit);
217        await testUpdate(tree1, 32, 323232, circuit);
218    });
219});