1 | ;
|
2 | var __importDefault = (this && this.__importDefault) || function (mod) {
|
3 | return (mod && mod.__esModule) ? mod : { "default": mod };
|
4 | };
|
5 | Object.defineProperty(exports, "__esModule", { value: true });
|
6 | exports.Trie = void 0;
|
7 | const semaphore_async_await_1 = __importDefault(require("semaphore-async-await"));
|
8 | const ethereumjs_util_1 = require("ethereumjs-util");
|
9 | const db_1 = require("./db");
|
10 | const readStream_1 = require("./readStream");
|
11 | const nibbles_1 = require("./util/nibbles");
|
12 | const walkController_1 = require("./util/walkController");
|
13 | const trieNode_1 = require("./trieNode");
|
14 | const assert = require('assert');
|
15 | /**
|
16 | * The basic trie interface, use with `import { BaseTrie as Trie } from 'merkle-patricia-tree'`.
|
17 | * In Ethereum applications stick with the {@link SecureTrie} overlay.
|
18 | * The API for the base and the secure interface are about the same.
|
19 | */
|
20 | class Trie {
|
21 | /**
|
22 | * test
|
23 | * @param db - A [levelup](https://github.com/Level/levelup) instance. By default (if the db is `null` or
|
24 | * left undefined) creates an in-memory [memdown](https://github.com/Level/memdown) instance.
|
25 | * @param root - A `Buffer` for the root of a previously stored trie
|
26 | * @param deleteFromDB - Delete nodes from DB on delete operations (disallows switching to an older state root) (default: `false`)
|
27 | */
|
28 | constructor(db, root, deleteFromDB = false) {
|
29 | this.EMPTY_TRIE_ROOT = ethereumjs_util_1.KECCAK256_RLP;
|
30 | this.lock = new semaphore_async_await_1.default(1);
|
31 | this.db = db ? new db_1.DB(db) : new db_1.DB();
|
32 | this._root = this.EMPTY_TRIE_ROOT;
|
33 | this._deleteFromDB = deleteFromDB;
|
34 | if (root) {
|
35 | this.root = root;
|
36 | }
|
37 | }
|
38 | /**
|
39 | * Sets the current root of the `trie`
|
40 | */
|
41 | set root(value) {
|
42 | if (!value) {
|
43 | value = this.EMPTY_TRIE_ROOT;
|
44 | }
|
45 | assert(value.length === 32, 'Invalid root length. Roots are 32 bytes');
|
46 | this._root = value;
|
47 | }
|
48 | /**
|
49 | * Gets the current root of the `trie`
|
50 | */
|
51 | get root() {
|
52 | return this._root;
|
53 | }
|
54 | /**
|
55 | * This method is deprecated.
|
56 | * Please use {@link Trie.root} instead.
|
57 | *
|
58 | * @param value
|
59 | * @deprecated
|
60 | */
|
61 | setRoot(value) {
|
62 | this.root = value !== null && value !== void 0 ? value : this.EMPTY_TRIE_ROOT;
|
63 | }
|
64 | /**
|
65 | * Checks if a given root exists.
|
66 | */
|
67 | async checkRoot(root) {
|
68 | try {
|
69 | const value = await this._lookupNode(root);
|
70 | return value !== null;
|
71 | }
|
72 | catch (error) {
|
73 | if (error.message == 'Missing node in DB') {
|
74 | return false;
|
75 | }
|
76 | else {
|
77 | throw error;
|
78 | }
|
79 | }
|
80 | }
|
81 | /**
|
82 | * BaseTrie has no checkpointing so return false
|
83 | */
|
84 | get isCheckpoint() {
|
85 | return false;
|
86 | }
|
87 | /**
|
88 | * Gets a value given a `key`
|
89 | * @param key - the key to search for
|
90 | * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
|
91 | * @returns A Promise that resolves to `Buffer` if a value was found or `null` if no value was found.
|
92 | */
|
93 | async get(key, throwIfMissing = false) {
|
94 | const { node, remaining } = await this.findPath(key, throwIfMissing);
|
95 | let value = null;
|
96 | if (node && remaining.length === 0) {
|
97 | value = node.value;
|
98 | }
|
99 | return value;
|
100 | }
|
101 | /**
|
102 | * Stores a given `value` at the given `key` or do a delete if `value` is empty
|
103 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
104 | * @param key
|
105 | * @param value
|
106 | * @returns A Promise that resolves once value is stored.
|
107 | */
|
108 | async put(key, value) {
|
109 | // If value is empty, delete
|
110 | if (!value || value.toString() === '') {
|
111 | return await this.del(key);
|
112 | }
|
113 | await this.lock.wait();
|
114 | if (this.root.equals(ethereumjs_util_1.KECCAK256_RLP)) {
|
115 | // If no root, initialize this trie
|
116 | await this._createInitialNode(key, value);
|
117 | }
|
118 | else {
|
119 | // First try to find the given key or its nearest node
|
120 | const { remaining, stack } = await this.findPath(key);
|
121 | // then update
|
122 | await this._updateNode(key, value, remaining, stack);
|
123 | }
|
124 | this.lock.signal();
|
125 | }
|
126 | /**
|
127 | * Deletes a value given a `key` from the trie
|
128 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
129 | * @param key
|
130 | * @returns A Promise that resolves once value is deleted.
|
131 | */
|
132 | async del(key) {
|
133 | await this.lock.wait();
|
134 | const { node, stack } = await this.findPath(key);
|
135 | if (node) {
|
136 | await this._deleteNode(key, stack);
|
137 | }
|
138 | this.lock.signal();
|
139 | }
|
140 | /**
|
141 | * Tries to find a path to the node for the given key.
|
142 | * It returns a `stack` of nodes to the closest node.
|
143 | * @param key - the search key
|
144 | * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
|
145 | */
|
146 | async findPath(key, throwIfMissing = false) {
|
147 | // eslint-disable-next-line no-async-promise-executor
|
148 | return new Promise(async (resolve, reject) => {
|
149 | const stack = [];
|
150 | const targetKey = (0, nibbles_1.bufferToNibbles)(key);
|
151 | const onFound = async (nodeRef, node, keyProgress, walkController) => {
|
152 | if (node === null) {
|
153 | return reject(new Error('Path not found'));
|
154 | }
|
155 | const keyRemainder = targetKey.slice((0, nibbles_1.matchingNibbleLength)(keyProgress, targetKey));
|
156 | stack.push(node);
|
157 | if (node instanceof trieNode_1.BranchNode) {
|
158 | if (keyRemainder.length === 0) {
|
159 | // we exhausted the key without finding a node
|
160 | resolve({ node, remaining: [], stack });
|
161 | }
|
162 | else {
|
163 | const branchIndex = keyRemainder[0];
|
164 | const branchNode = node.getBranch(branchIndex);
|
165 | if (!branchNode) {
|
166 | // there are no more nodes to find and we didn't find the key
|
167 | resolve({ node: null, remaining: keyRemainder, stack });
|
168 | }
|
169 | else {
|
170 | // node found, continuing search
|
171 | // this can be optimized as this calls getBranch again.
|
172 | walkController.onlyBranchIndex(node, keyProgress, branchIndex);
|
173 | }
|
174 | }
|
175 | }
|
176 | else if (node instanceof trieNode_1.LeafNode) {
|
177 | if ((0, nibbles_1.doKeysMatch)(keyRemainder, node.key)) {
|
178 | // keys match, return node with empty key
|
179 | resolve({ node, remaining: [], stack });
|
180 | }
|
181 | else {
|
182 | // reached leaf but keys dont match
|
183 | resolve({ node: null, remaining: keyRemainder, stack });
|
184 | }
|
185 | }
|
186 | else if (node instanceof trieNode_1.ExtensionNode) {
|
187 | const matchingLen = (0, nibbles_1.matchingNibbleLength)(keyRemainder, node.key);
|
188 | if (matchingLen !== node.key.length) {
|
189 | // keys don't match, fail
|
190 | resolve({ node: null, remaining: keyRemainder, stack });
|
191 | }
|
192 | else {
|
193 | // keys match, continue search
|
194 | walkController.allChildren(node, keyProgress);
|
195 | }
|
196 | }
|
197 | };
|
198 | // walk trie and process nodes
|
199 | try {
|
200 | await this.walkTrie(this.root, onFound);
|
201 | }
|
202 | catch (error) {
|
203 | if (error.message == 'Missing node in DB' && !throwIfMissing) {
|
204 | // pass
|
205 | }
|
206 | else {
|
207 | reject(error);
|
208 | }
|
209 | }
|
210 | // Resolve if _walkTrie finishes without finding any nodes
|
211 | resolve({ node: null, remaining: [], stack });
|
212 | });
|
213 | }
|
214 | /**
|
215 | * Walks a trie until finished.
|
216 | * @param root
|
217 | * @param onFound - callback to call when a node is found. This schedules new tasks. If no tasks are available, the Promise resolves.
|
218 | * @returns Resolves when finished walking trie.
|
219 | */
|
220 | async walkTrie(root, onFound) {
|
221 | await walkController_1.WalkController.newWalk(onFound, this, root);
|
222 | }
|
223 | /**
|
224 | * @hidden
|
225 | * Backwards compatibility
|
226 | * @param root -
|
227 | * @param onFound -
|
228 | */
|
229 | async _walkTrie(root, onFound) {
|
230 | await this.walkTrie(root, onFound);
|
231 | }
|
232 | /**
|
233 | * Creates the initial node from an empty tree.
|
234 | * @private
|
235 | */
|
236 | async _createInitialNode(key, value) {
|
237 | const newNode = new trieNode_1.LeafNode((0, nibbles_1.bufferToNibbles)(key), value);
|
238 | this.root = newNode.hash();
|
239 | await this.db.put(this.root, newNode.serialize());
|
240 | }
|
241 | /**
|
242 | * Retrieves a node from db by hash.
|
243 | */
|
244 | async lookupNode(node) {
|
245 | if ((0, trieNode_1.isRawNode)(node)) {
|
246 | return (0, trieNode_1.decodeRawNode)(node);
|
247 | }
|
248 | let value = null;
|
249 | let foundNode = null;
|
250 | value = await this.db.get(node);
|
251 | if (value) {
|
252 | foundNode = (0, trieNode_1.decodeNode)(value);
|
253 | }
|
254 | else {
|
255 | // Dev note: this error message text is used for error checking in `checkRoot`, `verifyProof`, and `findPath`
|
256 | throw new Error('Missing node in DB');
|
257 | }
|
258 | return foundNode;
|
259 | }
|
260 | /**
|
261 | * @hidden
|
262 | * Backwards compatibility
|
263 | * @param node The node hash to lookup from the DB
|
264 | */
|
265 | async _lookupNode(node) {
|
266 | return this.lookupNode(node);
|
267 | }
|
268 | /**
|
269 | * Updates a node.
|
270 | * @private
|
271 | * @param key
|
272 | * @param value
|
273 | * @param keyRemainder
|
274 | * @param stack
|
275 | */
|
276 | async _updateNode(k, value, keyRemainder, stack) {
|
277 | const toSave = [];
|
278 | const lastNode = stack.pop();
|
279 | if (!lastNode) {
|
280 | throw new Error('Stack underflow');
|
281 | }
|
282 | // add the new nodes
|
283 | const key = (0, nibbles_1.bufferToNibbles)(k);
|
284 | // Check if the last node is a leaf and the key matches to this
|
285 | let matchLeaf = false;
|
286 | if (lastNode instanceof trieNode_1.LeafNode) {
|
287 | let l = 0;
|
288 | for (let i = 0; i < stack.length; i++) {
|
289 | const n = stack[i];
|
290 | if (n instanceof trieNode_1.BranchNode) {
|
291 | l++;
|
292 | }
|
293 | else {
|
294 | l += n.key.length;
|
295 | }
|
296 | }
|
297 | if ((0, nibbles_1.matchingNibbleLength)(lastNode.key, key.slice(l)) === lastNode.key.length &&
|
298 | keyRemainder.length === 0) {
|
299 | matchLeaf = true;
|
300 | }
|
301 | }
|
302 | if (matchLeaf) {
|
303 | // just updating a found value
|
304 | lastNode.value = value;
|
305 | stack.push(lastNode);
|
306 | }
|
307 | else if (lastNode instanceof trieNode_1.BranchNode) {
|
308 | stack.push(lastNode);
|
309 | if (keyRemainder.length !== 0) {
|
310 | // add an extension to a branch node
|
311 | keyRemainder.shift();
|
312 | // create a new leaf
|
313 | const newLeaf = new trieNode_1.LeafNode(keyRemainder, value);
|
314 | stack.push(newLeaf);
|
315 | }
|
316 | else {
|
317 | lastNode.value = value;
|
318 | }
|
319 | }
|
320 | else {
|
321 | // create a branch node
|
322 | const lastKey = lastNode.key;
|
323 | const matchingLength = (0, nibbles_1.matchingNibbleLength)(lastKey, keyRemainder);
|
324 | const newBranchNode = new trieNode_1.BranchNode();
|
325 | // create a new extension node
|
326 | if (matchingLength !== 0) {
|
327 | const newKey = lastNode.key.slice(0, matchingLength);
|
328 | const newExtNode = new trieNode_1.ExtensionNode(newKey, value);
|
329 | stack.push(newExtNode);
|
330 | lastKey.splice(0, matchingLength);
|
331 | keyRemainder.splice(0, matchingLength);
|
332 | }
|
333 | stack.push(newBranchNode);
|
334 | if (lastKey.length !== 0) {
|
335 | const branchKey = lastKey.shift();
|
336 | if (lastKey.length !== 0 || lastNode instanceof trieNode_1.LeafNode) {
|
337 | // shrinking extension or leaf
|
338 | lastNode.key = lastKey;
|
339 | const formattedNode = this._formatNode(lastNode, false, toSave);
|
340 | newBranchNode.setBranch(branchKey, formattedNode);
|
341 | }
|
342 | else {
|
343 | // remove extension or attaching
|
344 | this._formatNode(lastNode, false, toSave, true);
|
345 | newBranchNode.setBranch(branchKey, lastNode.value);
|
346 | }
|
347 | }
|
348 | else {
|
349 | newBranchNode.value = lastNode.value;
|
350 | }
|
351 | if (keyRemainder.length !== 0) {
|
352 | keyRemainder.shift();
|
353 | // add a leaf node to the new branch node
|
354 | const newLeafNode = new trieNode_1.LeafNode(keyRemainder, value);
|
355 | stack.push(newLeafNode);
|
356 | }
|
357 | else {
|
358 | newBranchNode.value = value;
|
359 | }
|
360 | }
|
361 | await this._saveStack(key, stack, toSave);
|
362 | }
|
363 | /**
|
364 | * Deletes a node from the trie.
|
365 | * @private
|
366 | */
|
367 | async _deleteNode(k, stack) {
|
368 | const processBranchNode = (key, branchKey, branchNode, parentNode, stack) => {
|
369 | // branchNode is the node ON the branch node not THE branch node
|
370 | if (!parentNode || parentNode instanceof trieNode_1.BranchNode) {
|
371 | // branch->?
|
372 | if (parentNode) {
|
373 | stack.push(parentNode);
|
374 | }
|
375 | if (branchNode instanceof trieNode_1.BranchNode) {
|
376 | // create an extension node
|
377 | // branch->extension->branch
|
378 | // @ts-ignore
|
379 | const extensionNode = new trieNode_1.ExtensionNode([branchKey], null);
|
380 | stack.push(extensionNode);
|
381 | key.push(branchKey);
|
382 | }
|
383 | else {
|
384 | const branchNodeKey = branchNode.key;
|
385 | // branch key is an extension or a leaf
|
386 | // branch->(leaf or extension)
|
387 | branchNodeKey.unshift(branchKey);
|
388 | branchNode.key = branchNodeKey.slice(0);
|
389 | key = key.concat(branchNodeKey);
|
390 | }
|
391 | stack.push(branchNode);
|
392 | }
|
393 | else {
|
394 | // parent is an extension
|
395 | let parentKey = parentNode.key;
|
396 | if (branchNode instanceof trieNode_1.BranchNode) {
|
397 | // ext->branch
|
398 | parentKey.push(branchKey);
|
399 | key.push(branchKey);
|
400 | parentNode.key = parentKey;
|
401 | stack.push(parentNode);
|
402 | }
|
403 | else {
|
404 | const branchNodeKey = branchNode.key;
|
405 | // branch node is an leaf or extension and parent node is an exstention
|
406 | // add two keys together
|
407 | // dont push the parent node
|
408 | branchNodeKey.unshift(branchKey);
|
409 | key = key.concat(branchNodeKey);
|
410 | parentKey = parentKey.concat(branchNodeKey);
|
411 | branchNode.key = parentKey;
|
412 | }
|
413 | stack.push(branchNode);
|
414 | }
|
415 | return key;
|
416 | };
|
417 | let lastNode = stack.pop();
|
418 | assert(lastNode);
|
419 | let parentNode = stack.pop();
|
420 | const opStack = [];
|
421 | let key = (0, nibbles_1.bufferToNibbles)(k);
|
422 | if (!parentNode) {
|
423 | // the root here has to be a leaf.
|
424 | this.root = this.EMPTY_TRIE_ROOT;
|
425 | return;
|
426 | }
|
427 | if (lastNode instanceof trieNode_1.BranchNode) {
|
428 | lastNode.value = null;
|
429 | }
|
430 | else {
|
431 | // the lastNode has to be a leaf if it's not a branch.
|
432 | // And a leaf's parent, if it has one, must be a branch.
|
433 | if (!(parentNode instanceof trieNode_1.BranchNode)) {
|
434 | throw new Error('Expected branch node');
|
435 | }
|
436 | const lastNodeKey = lastNode.key;
|
437 | key.splice(key.length - lastNodeKey.length);
|
438 | // delete the value
|
439 | this._formatNode(lastNode, false, opStack, true);
|
440 | parentNode.setBranch(key.pop(), null);
|
441 | lastNode = parentNode;
|
442 | parentNode = stack.pop();
|
443 | }
|
444 | // nodes on the branch
|
445 | // count the number of nodes on the branch
|
446 | const branchNodes = lastNode.getChildren();
|
447 | // if there is only one branch node left, collapse the branch node
|
448 | if (branchNodes.length === 1) {
|
449 | // add the one remaing branch node to node above it
|
450 | const branchNode = branchNodes[0][1];
|
451 | const branchNodeKey = branchNodes[0][0];
|
452 | // look up node
|
453 | const foundNode = await this._lookupNode(branchNode);
|
454 | if (foundNode) {
|
455 | key = processBranchNode(key, branchNodeKey, foundNode, parentNode, stack);
|
456 | await this._saveStack(key, stack, opStack);
|
457 | }
|
458 | }
|
459 | else {
|
460 | // simple removing a leaf and recaluclation the stack
|
461 | if (parentNode) {
|
462 | stack.push(parentNode);
|
463 | }
|
464 | stack.push(lastNode);
|
465 | await this._saveStack(key, stack, opStack);
|
466 | }
|
467 | }
|
468 | /**
|
469 | * Saves a stack of nodes to the database.
|
470 | * @private
|
471 | * @param key - the key. Should follow the stack
|
472 | * @param stack - a stack of nodes to the value given by the key
|
473 | * @param opStack - a stack of levelup operations to commit at the end of this funciton
|
474 | */
|
475 | async _saveStack(key, stack, opStack) {
|
476 | let lastRoot;
|
477 | // update nodes
|
478 | while (stack.length) {
|
479 | const node = stack.pop();
|
480 | if (node instanceof trieNode_1.LeafNode) {
|
481 | key.splice(key.length - node.key.length);
|
482 | }
|
483 | else if (node instanceof trieNode_1.ExtensionNode) {
|
484 | key.splice(key.length - node.key.length);
|
485 | if (lastRoot) {
|
486 | node.value = lastRoot;
|
487 | }
|
488 | }
|
489 | else if (node instanceof trieNode_1.BranchNode) {
|
490 | if (lastRoot) {
|
491 | const branchKey = key.pop();
|
492 | node.setBranch(branchKey, lastRoot);
|
493 | }
|
494 | }
|
495 | lastRoot = this._formatNode(node, stack.length === 0, opStack);
|
496 | }
|
497 | if (lastRoot) {
|
498 | this.root = lastRoot;
|
499 | }
|
500 | await this.db.batch(opStack);
|
501 | }
|
502 | /**
|
503 | * Formats node to be saved by `levelup.batch`.
|
504 | * @private
|
505 | * @param node - the node to format.
|
506 | * @param topLevel - if the node is at the top level.
|
507 | * @param opStack - the opStack to push the node's data.
|
508 | * @param remove - whether to remove the node (only used for CheckpointTrie).
|
509 | * @returns The node's hash used as the key or the rawNode.
|
510 | */
|
511 | _formatNode(node, topLevel, opStack, remove = false) {
|
512 | const rlpNode = node.serialize();
|
513 | if (rlpNode.length >= 32 || topLevel) {
|
514 | // Do not use TrieNode.hash() here otherwise serialize()
|
515 | // is applied twice (performance)
|
516 | const hashRoot = (0, ethereumjs_util_1.keccak)(rlpNode);
|
517 | if (remove) {
|
518 | if (this._deleteFromDB) {
|
519 | opStack.push({
|
520 | type: 'del',
|
521 | key: hashRoot,
|
522 | });
|
523 | }
|
524 | }
|
525 | else {
|
526 | opStack.push({
|
527 | type: 'put',
|
528 | key: hashRoot,
|
529 | value: rlpNode,
|
530 | });
|
531 | }
|
532 | return hashRoot;
|
533 | }
|
534 | return node.raw();
|
535 | }
|
536 | /**
|
537 | * The given hash of operations (key additions or deletions) are executed on the trie
|
538 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
539 | * @example
|
540 | * const ops = [
|
541 | * { type: 'del', key: Buffer.from('father') }
|
542 | * , { type: 'put', key: Buffer.from('name'), value: Buffer.from('Yuri Irsenovich Kim') }
|
543 | * , { type: 'put', key: Buffer.from('dob'), value: Buffer.from('16 February 1941') }
|
544 | * , { type: 'put', key: Buffer.from('spouse'), value: Buffer.from('Kim Young-sook') }
|
545 | * , { type: 'put', key: Buffer.from('occupation'), value: Buffer.from('Clown') }
|
546 | * ]
|
547 | * await trie.batch(ops)
|
548 | * @param ops
|
549 | */
|
550 | async batch(ops) {
|
551 | for (const op of ops) {
|
552 | if (op.type === 'put') {
|
553 | if (!op.value) {
|
554 | throw new Error('Invalid batch db operation');
|
555 | }
|
556 | await this.put(op.key, op.value);
|
557 | }
|
558 | else if (op.type === 'del') {
|
559 | await this.del(op.key);
|
560 | }
|
561 | }
|
562 | }
|
563 | /**
|
564 | * Saves the nodes from a proof into the trie. If no trie is provided a new one wil be instantiated.
|
565 | * @param proof
|
566 | * @param trie
|
567 | */
|
568 | static async fromProof(proof, trie) {
|
569 | const opStack = proof.map((nodeValue) => {
|
570 | return {
|
571 | type: 'put',
|
572 | key: (0, ethereumjs_util_1.keccak)(nodeValue),
|
573 | value: nodeValue,
|
574 | };
|
575 | });
|
576 | if (!trie) {
|
577 | trie = new Trie();
|
578 | if (opStack[0]) {
|
579 | trie.root = opStack[0].key;
|
580 | }
|
581 | }
|
582 | await trie.db.batch(opStack);
|
583 | return trie;
|
584 | }
|
585 | /**
|
586 | * prove has been renamed to {@link Trie.createProof}.
|
587 | * @deprecated
|
588 | * @param trie
|
589 | * @param key
|
590 | */
|
591 | static async prove(trie, key) {
|
592 | return this.createProof(trie, key);
|
593 | }
|
594 | /**
|
595 | * Creates a proof from a trie and key that can be verified using {@link Trie.verifyProof}.
|
596 | * @param trie
|
597 | * @param key
|
598 | */
|
599 | static async createProof(trie, key) {
|
600 | const { stack } = await trie.findPath(key);
|
601 | const p = stack.map((stackElem) => {
|
602 | return stackElem.serialize();
|
603 | });
|
604 | return p;
|
605 | }
|
606 | /**
|
607 | * Verifies a proof.
|
608 | * @param rootHash
|
609 | * @param key
|
610 | * @param proof
|
611 | * @throws If proof is found to be invalid.
|
612 | * @returns The value from the key, or null if valid proof of non-existence.
|
613 | */
|
614 | static async verifyProof(rootHash, key, proof) {
|
615 | let proofTrie = new Trie(null, rootHash);
|
616 | try {
|
617 | proofTrie = await Trie.fromProof(proof, proofTrie);
|
618 | }
|
619 | catch (e) {
|
620 | throw new Error('Invalid proof nodes given');
|
621 | }
|
622 | try {
|
623 | const value = await proofTrie.get(key, true);
|
624 | return value;
|
625 | }
|
626 | catch (err) {
|
627 | if (err.message == 'Missing node in DB') {
|
628 | throw new Error('Invalid proof provided');
|
629 | }
|
630 | else {
|
631 | throw err;
|
632 | }
|
633 | }
|
634 | }
|
635 | /**
|
636 | * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.
|
637 | * @return Returns a [stream](https://nodejs.org/dist/latest-v12.x/docs/api/stream.html#stream_class_stream_readable) of the contents of the `trie`
|
638 | */
|
639 | createReadStream() {
|
640 | return new readStream_1.TrieReadStream(this);
|
641 | }
|
642 | /**
|
643 | * Creates a new trie backed by the same db.
|
644 | */
|
645 | copy() {
|
646 | const db = this.db.copy();
|
647 | return new Trie(db._leveldb, this.root);
|
648 | }
|
649 | /**
|
650 | * Finds all nodes that are stored directly in the db
|
651 | * (some nodes are stored raw inside other nodes)
|
652 | * called by {@link ScratchReadStream}
|
653 | * @private
|
654 | */
|
655 | async _findDbNodes(onFound) {
|
656 | const outerOnFound = async (nodeRef, node, key, walkController) => {
|
657 | if ((0, trieNode_1.isRawNode)(nodeRef)) {
|
658 | if (node !== null) {
|
659 | walkController.allChildren(node, key);
|
660 | }
|
661 | }
|
662 | else {
|
663 | onFound(nodeRef, node, key, walkController);
|
664 | }
|
665 | };
|
666 | await this.walkTrie(this.root, outerOnFound);
|
667 | }
|
668 | /**
|
669 | * Finds all nodes that store k,v values
|
670 | * called by {@link TrieReadStream}
|
671 | * @private
|
672 | */
|
673 | async _findValueNodes(onFound) {
|
674 | const outerOnFound = async (nodeRef, node, key, walkController) => {
|
675 | let fullKey = key;
|
676 | if (node instanceof trieNode_1.LeafNode) {
|
677 | fullKey = key.concat(node.key);
|
678 | // found leaf node!
|
679 | onFound(nodeRef, node, fullKey, walkController);
|
680 | }
|
681 | else if (node instanceof trieNode_1.BranchNode && node.value) {
|
682 | // found branch with value
|
683 | onFound(nodeRef, node, fullKey, walkController);
|
684 | }
|
685 | else {
|
686 | // keep looking for value nodes
|
687 | if (node !== null) {
|
688 | walkController.allChildren(node, key);
|
689 | }
|
690 | }
|
691 | };
|
692 | await this.walkTrie(this.root, outerOnFound);
|
693 | }
|
694 | }
|
695 | exports.Trie = Trie;
|
696 | //# sourceMappingURL=baseTrie.js.map |
\ | No newline at end of file |