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 delete(_key) {
41 const key = bigInt(_key);
42
43 const resFind = await this.find(key);
44 if (!resFind.found) throw new Error("Key does not exists");
45
46 const res = {
47 sibblings: [],
48 delKey: key,
49 delValue: resFind.foundValue
50 };
51
52 const dels = [];
53 const ins = [];
54 let rtOld = smtHash([1, key, resFind.foundValue]);
55 let rtNew;
56 dels.push(rtOld);
57
58
59 let mixed;
60 if (resFind.sibblings.length > 0) {
61 const record = await this.db.get(resFind.sibblings[resFind.sibblings.length - 1]);
62 if ((record.length == 3)&&(record[0].equals(bigInt.one))) {
63 mixed = false;
64 res.oldKey = record[1];
65 res.oldValue = record[2];
66 res.isOld0 = false;
67 rtNew = resFind.sibblings[resFind.sibblings.length - 1];
68 } else if (record.length == 2) {
69 mixed = true;
70 res.oldKey = key;
71 res.oldValue = bigInt(0);
72 res.isOld0 = true;
73 rtNew = bigInt.zero;
74 } else {
75 throw new Error("Invalid node. Database corrupted");
76 }
77 } else {
78 rtNew = bigInt.zero;
79 res.oldKey = key;
80 res.oldValue = bigInt(0);
81 res.isOld0 = true;
82 }
83
84 const keyBits = this._splitBits(key);
85
86 for (let level = resFind.sibblings.length-1; level >=0; level--) {
87 let newSibling = resFind.sibblings[level];
88 if ((level == resFind.sibblings.length-1)&&(!res.isOld0)) {
89 newSibling = bigInt.zero;
90 }
91 const oldSibling = resFind.sibblings[level];
92 if (keyBits[level]) {
93 rtOld = smtHash([oldSibling, rtOld]);
94 } else {
95 rtOld = smtHash([rtOld, oldSibling]);
96 }
97 dels.push(rtOld);
98 if (!newSibling.isZero()) {
99 mixed = true;
100 }
101
102 if (mixed) {
103 res.sibblings.unshift(resFind.sibblings[level]);
104 let newNode;
105 if (keyBits[level]) {
106 newNode = [newSibling, rtNew];
107 } else {
108 newNode = [rtNew, newSibling];
109 }
110 rtNew = smtHash(newNode);
111 ins.push([rtNew, newNode]);
112 }
113 }
114
115 await this.db.multiIns(ins);
116 await this.db.setRoot(rtNew);
117 this.root = rtNew;
118 await this.db.multiDel(dels);
119
120 res.newRoot = rtNew;
121 res.oldRoot = rtOld;
122
123 return res;
124 }
125
126 async insert(_key, _value) {
127 const key = bigInt(_key);
128 const value = bigInt(_value);
129 let addedOne = false;
130 const res = {};
131 res.oldRoot = this.root;
132 const newKeyBits = this._splitBits(key);
133
134 let rtOld;
135
136 const resFind = await this.find(key);
137
138 if (resFind.found) throw new Error("Key already exists");
139
140 res.sibblings = resFind.sibblings;
141 let mixed;
142
143 if (!resFind.isOld0) {
144 const oldKeyits = this._splitBits(resFind.notFoundKey);
145 for (let i= res.sibblings.length; oldKeyits[i] == newKeyBits[i]; i++) {
146 res.sibblings.push(bigInt.zero);
147 }
148 rtOld = smtHash([1, resFind.notFoundKey, resFind.notFoundValue]);
149 res.sibblings.push(rtOld);
150 addedOne = true;
151 mixed = false;
152 } else if (res.sibblings.length >0) {
153 mixed = true;
154 rtOld = bigInt.zero;
155 }
156
157 const inserts = [];
158 const dels = [];
159
160 let rt = smtHash([1, key, value]);
161 inserts.push([rt,[1, key, value]] );
162
163 for (let i=res.sibblings.length-1; i>=0; i--) {
164 if ((i<res.sibblings.length-1)&&(!res.sibblings[i].isZero())) {
165 mixed = true;
166 }
167 if (mixed) {
168 const oldSibling = resFind.sibblings[i];
169 if (newKeyBits[i]) {
170 rtOld = smtHash([oldSibling, rtOld]);
171 } else {
172 rtOld = smtHash([rtOld, oldSibling]);
173 }
174 dels.push(rtOld);
175 }
176
177
178 let newRt;
179 if (newKeyBits[i]) {
180 newRt = smtHash([res.sibblings[i], rt]);
181 inserts.push([newRt,[res.sibblings[i], rt]] );
182 } else {
183 newRt = smtHash([rt, res.sibblings[i]]);
184 inserts.push([newRt,[rt, res.sibblings[i]]] );
185 }
186 rt = newRt;
187 }
188
189 if (addedOne) res.sibblings.pop();
190 while ((res.sibblings.length>0) && (res.sibblings[res.sibblings.length-1].isZero())) {
191 res.sibblings.pop();
192 }
193 res.oldKey = resFind.notFoundKey;
194 res.oldValue = resFind.notFoundValue;
195 res.newRoot = rt;
196 res.isOld0 = resFind.isOld0;
197
198
199 await this.db.multiIns(inserts);
200 await this.db.setRoot(rt);
201 this.root = rt;
202 await this.db.multiDel(dels);
203
204 return res;
205 }
206
207 async find(key) {
208 const keyBits = this._splitBits(key);
209 return await this._find(key, keyBits, this.root, 0);
210 }
211
212 async _find(key, keyBits, root, level) {
213 if (typeof root === "undefined") root = this.root;
214
215 let res;
216 if (root.isZero()) {
217 res = {
218 found: false,
219 sibblings: [],
220 notFoundKey: key,
221 notFoundValue: bigInt.zero,
222 isOld0: true
223 };
224 return res;
225 }
226
227 const record = await this.db.get(root);
228
229 if ((record.length==3)&&(record[0].equals(bigInt.one))) {
230 if (record[1].equals(key)) {
231 res = {
232 found: true,
233 sibblings: [],
234 foundValue: record[2],
235 isOld0: false
236 };
237 } else {
238 res = {
239 found: false,
240 sibblings: [],
241 notFoundKey: record[1],
242 notFoundValue: record[2],
243 isOld0: false
244 };
245 }
246 } else {
247 if (keyBits[level] == 0) {
248 res = await this._find(key, keyBits, record[0], level+1);
249 res.sibblings.unshift(record[1]);
250 } else {
251 res = await this._find(key, keyBits, record[1], level+1);
252 res.sibblings.unshift(record[0]);
253 }
254 }
255 return res;
256 }
257}
258
259async function loadFromFile(fileName) {
260
261}
262
263async function newMemEmptyTrie() {
264 const db = new SMTMemDB();
265 const rt = await db.getRoot();
266 const smt = new SMT(db, rt);
267 return smt;
268}
269
270module.exports.loadFromFile = loadFromFile;
271module.exports.newMemEmptyTrie = newMemEmptyTrie;