circomlib/src/smt.js
src/smt.jsRaw
1const bigInt = require("snarkjs").bigInt;
2
3const SMTMemDB = require("./smt_memdb");
4const mimc7 = require("./mimc7").hash;
5
6function smtHash(arr) {
7 let r = bigInt(0);
8 for (let i=0; i<arr.length; i++) {
9 r = mimc7(r, bigInt(arr[i]));
10 }
11 return r;
12}
13
14class SMT {
15
16 constructor(db, root) {
17 this.db = db;
18 this.root = root;
19 }
20
21 _splitBits(_key) {
22
23 let k = bigInt(_key);
24 const res = [];
25
26 while (!k.isZero()) {
27 if (k.isOdd()) {
28 res.push(true);
29 } else {
30 res.push(false);
31 }
32 k = k.shr(1);
33 }
34
35 while (res.length<256) res.push(false);
36
37 return res;
38 }
39
40 async update(_key, _newValue) {
41 const key = bigInt(_key);
42 const newValue = bigInt(_newValue);
43
44
45 const resFind = await this.find(key);
46 const res = {};
47 res.oldRoot = this.root;
48 res.oldKey = key;
49 res.oldValue = resFind.foundValue;
50 res.newKey = key;
51 res.newValue = newValue;
52 res.siblings = resFind.siblings;
53
54 const ins = [];
55 const dels = [];
56
57 let rtOld = smtHash([1, key, resFind.foundValue]);
58 let rtNew = smtHash([1, key, newValue]);
59 ins.push([rtNew, [1, key, newValue ]]);
60 dels.push(rtOld);
61
62 const keyBits = this._splitBits(key);
63 for (let level = resFind.siblings.length-1; level >=0; level--) {
64 let oldNode, newNode;
65 const sibling = resFind.siblings[level];
66 if (keyBits[level]) {
67 oldNode = [sibling, rtOld];
68 newNode = [sibling, rtNew];
69 } else {
70 oldNode = [rtOld, sibling, ];
71 newNode = [rtNew, sibling, ];
72 }
73 rtOld = smtHash(oldNode);
74 rtNew = smtHash(newNode);
75 dels.push(rtOld);
76 ins.push([rtNew, newNode]);
77 }
78
79 res.newRoot = rtNew;
80
81 await this.db.multiIns(ins);
82 await this.db.setRoot(rtNew);
83 this.root = rtNew;
84 await this.db.multiDel(dels);
85
86 return res;
87 }
88
89 async delete(_key) {
90 const key = bigInt(_key);
91
92 const resFind = await this.find(key);
93 if (!resFind.found) throw new Error("Key does not exists");
94
95 const res = {
96 siblings: [],
97 delKey: key,
98 delValue: resFind.foundValue
99 };
100
101 const dels = [];
102 const ins = [];
103 let rtOld = smtHash([1, key, resFind.foundValue]);
104 let rtNew;
105 dels.push(rtOld);
106
107 let mixed;
108 if (resFind.siblings.length > 0) {
109 const record = await this.db.get(resFind.siblings[resFind.siblings.length - 1]);
110 if ((record.length == 3)&&(record[0].equals(bigInt.one))) {
111 mixed = false;
112 res.oldKey = record[1];
113 res.oldValue = record[2];
114 res.isOld0 = false;
115 rtNew = resFind.siblings[resFind.siblings.length - 1];
116 } else if (record.length == 2) {
117 mixed = true;
118 res.oldKey = key;
119 res.oldValue = bigInt(0);
120 res.isOld0 = true;
121 rtNew = bigInt.zero;
122 } else {
123 throw new Error("Invalid node. Database corrupted");
124 }
125 } else {
126 rtNew = bigInt.zero;
127 res.oldKey = key;
128 res.oldValue = bigInt(0);
129 res.isOld0 = true;
130 }
131
132 const keyBits = this._splitBits(key);
133
134 for (let level = resFind.siblings.length-1; level >=0; level--) {
135 let newSibling = resFind.siblings[level];
136 if ((level == resFind.siblings.length-1)&&(!res.isOld0)) {
137 newSibling = bigInt.zero;
138 }
139 const oldSibling = resFind.siblings[level];
140 if (keyBits[level]) {
141 rtOld = smtHash([oldSibling, rtOld]);
142 } else {
143 rtOld = smtHash([rtOld, oldSibling]);
144 }
145 dels.push(rtOld);
146 if (!newSibling.isZero()) {
147 mixed = true;
148 }
149
150 if (mixed) {
151 res.siblings.unshift(resFind.siblings[level]);
152 let newNode;
153 if (keyBits[level]) {
154 newNode = [newSibling, rtNew];
155 } else {
156 newNode = [rtNew, newSibling];
157 }
158 rtNew = smtHash(newNode);
159 ins.push([rtNew, newNode]);
160 }
161 }
162
163 await this.db.multiIns(ins);
164 await this.db.setRoot(rtNew);
165 this.root = rtNew;
166 await this.db.multiDel(dels);
167
168 res.newRoot = rtNew;
169 res.oldRoot = rtOld;
170
171 return res;
172 }
173
174 async insert(_key, _value) {
175 const key = bigInt(_key);
176 const value = bigInt(_value);
177 let addedOne = false;
178 const res = {};
179 res.oldRoot = this.root;
180 const newKeyBits = this._splitBits(key);
181
182 let rtOld;
183
184 const resFind = await this.find(key);
185
186 if (resFind.found) throw new Error("Key already exists");
187
188 res.siblings = resFind.siblings;
189 let mixed;
190
191 if (!resFind.isOld0) {
192 const oldKeyits = this._splitBits(resFind.notFoundKey);
193 for (let i= res.siblings.length; oldKeyits[i] == newKeyBits[i]; i++) {
194 res.siblings.push(bigInt.zero);
195 }
196 rtOld = smtHash([1, resFind.notFoundKey, resFind.notFoundValue]);
197 res.siblings.push(rtOld);
198 addedOne = true;
199 mixed = false;
200 } else if (res.siblings.length >0) {
201 mixed = true;
202 rtOld = bigInt.zero;
203 }
204
205 const inserts = [];
206 const dels = [];
207
208 let rt = smtHash([1, key, value]);
209 inserts.push([rt,[1, key, value]] );
210
211 for (let i=res.siblings.length-1; i>=0; i--) {
212 if ((i<res.siblings.length-1)&&(!res.siblings[i].isZero())) {
213 mixed = true;
214 }
215 if (mixed) {
216 const oldSibling = resFind.siblings[i];
217 if (newKeyBits[i]) {
218 rtOld = smtHash([oldSibling, rtOld]);
219 } else {
220 rtOld = smtHash([rtOld, oldSibling]);
221 }
222 dels.push(rtOld);
223 }
224
225
226 let newRt;
227 if (newKeyBits[i]) {
228 newRt = smtHash([res.siblings[i], rt]);
229 inserts.push([newRt,[res.siblings[i], rt]] );
230 } else {
231 newRt = smtHash([rt, res.siblings[i]]);
232 inserts.push([newRt,[rt, res.siblings[i]]] );
233 }
234 rt = newRt;
235 }
236
237 if (addedOne) res.siblings.pop();
238 while ((res.siblings.length>0) && (res.siblings[res.siblings.length-1].isZero())) {
239 res.siblings.pop();
240 }
241 res.oldKey = resFind.notFoundKey;
242 res.oldValue = resFind.notFoundValue;
243 res.newRoot = rt;
244 res.isOld0 = resFind.isOld0;
245
246
247 await this.db.multiIns(inserts);
248 await this.db.setRoot(rt);
249 this.root = rt;
250 await this.db.multiDel(dels);
251
252 return res;
253 }
254
255 async find(key) {
256 const keyBits = this._splitBits(key);
257 return await this._find(key, keyBits, this.root, 0);
258 }
259
260 async _find(key, keyBits, root, level) {
261 if (typeof root === "undefined") root = this.root;
262
263 let res;
264 if (root.isZero()) {
265 res = {
266 found: false,
267 siblings: [],
268 notFoundKey: key,
269 notFoundValue: bigInt.zero,
270 isOld0: true
271 };
272 return res;
273 }
274
275 const record = await this.db.get(root);
276
277 if ((record.length==3)&&(record[0].equals(bigInt.one))) {
278 if (record[1].equals(key)) {
279 res = {
280 found: true,
281 siblings: [],
282 foundValue: record[2],
283 isOld0: false
284 };
285 } else {
286 res = {
287 found: false,
288 siblings: [],
289 notFoundKey: record[1],
290 notFoundValue: record[2],
291 isOld0: false
292 };
293 }
294 } else {
295 if (keyBits[level] == 0) {
296 res = await this._find(key, keyBits, record[0], level+1);
297 res.siblings.unshift(record[1]);
298 } else {
299 res = await this._find(key, keyBits, record[1], level+1);
300 res.siblings.unshift(record[0]);
301 }
302 }
303 return res;
304 }
305}
306
307async function loadFromFile(fileName) {
308
309}
310
311async function newMemEmptyTrie() {
312 const db = new SMTMemDB();
313 const rt = await db.getRoot();
314 const smt = new SMT(db, rt);
315 return smt;
316}
317
318module.exports.loadFromFile = loadFromFile;
319module.exports.newMemEmptyTrie = newMemEmptyTrie;