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