smtprocessor.js
1 const chai = require("chai"); 2 const path = require("path"); 3 const wasm_tester = require("circom_tester").wasm; 4 const F1Field = require("ffjavascript").F1Field; 5 const Scalar = require("ffjavascript").Scalar; 6 7 const newMemEmptyTrie = require("circomlibjs").newMemEmptyTrie; 8 9 const assert = chai.assert; 10 11 function print(circuit, w, s) { 12 console.log(s + ": " + w[circuit.getSignalIdx(s)]); 13 } 14 15 async 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 41 async 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 64 async 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 89 describe("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 });