1 | import Semaphore from 'semaphore-async-await'
|
2 | import { keccak, KECCAK256_RLP } from 'ethereumjs-util'
|
3 | import { DB, BatchDBOp, PutBatch } from './db'
|
4 | import { TrieReadStream as ReadStream } from './readStream'
|
5 | import { bufferToNibbles, matchingNibbleLength, doKeysMatch } from './util/nibbles'
|
6 | import { WalkController } from './util/walkController'
|
7 | import {
|
8 | TrieNode,
|
9 | decodeNode,
|
10 | decodeRawNode,
|
11 | isRawNode,
|
12 | BranchNode,
|
13 | ExtensionNode,
|
14 | LeafNode,
|
15 | EmbeddedNode,
|
16 | Nibbles,
|
17 | } from './trieNode'
|
18 |
|
19 | import type { LevelUp } from 'levelup'
|
20 | const assert = require('assert')
|
21 |
|
22 | export type Proof = Buffer[]
|
23 |
|
24 | interface Path {
|
25 | node: TrieNode | null
|
26 | remaining: Nibbles
|
27 | stack: TrieNode[]
|
28 | }
|
29 |
|
30 | export type FoundNodeFunction = (
|
31 | nodeRef: Buffer,
|
32 | node: TrieNode | null,
|
33 | key: Nibbles,
|
34 | walkController: WalkController
|
35 | ) => void
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 | export class Trie {
|
43 |
|
44 | EMPTY_TRIE_ROOT: Buffer
|
45 | protected lock: Semaphore
|
46 |
|
47 |
|
48 | db: DB
|
49 | private _root: Buffer
|
50 | private _deleteFromDB: boolean
|
51 |
|
52 | |
53 |
|
54 |
|
55 |
|
56 |
|
57 |
|
58 |
|
59 | constructor(db?: LevelUp | null, root?: Buffer, deleteFromDB: boolean = false) {
|
60 | this.EMPTY_TRIE_ROOT = KECCAK256_RLP
|
61 | this.lock = new Semaphore(1)
|
62 |
|
63 | this.db = db ? new DB(db) : new DB()
|
64 | this._root = this.EMPTY_TRIE_ROOT
|
65 | this._deleteFromDB = deleteFromDB
|
66 |
|
67 | if (root) {
|
68 | this.root = root
|
69 | }
|
70 | }
|
71 |
|
72 | |
73 |
|
74 |
|
75 | set root(value: Buffer) {
|
76 | if (!value) {
|
77 | value = this.EMPTY_TRIE_ROOT
|
78 | }
|
79 | assert(value.length === 32, 'Invalid root length. Roots are 32 bytes')
|
80 | this._root = value
|
81 | }
|
82 |
|
83 | |
84 |
|
85 |
|
86 | get root(): Buffer {
|
87 | return this._root
|
88 | }
|
89 |
|
90 | |
91 |
|
92 |
|
93 |
|
94 |
|
95 |
|
96 |
|
97 | setRoot(value?: Buffer) {
|
98 | this.root = value ?? this.EMPTY_TRIE_ROOT
|
99 | }
|
100 |
|
101 | |
102 |
|
103 |
|
104 | async checkRoot(root: Buffer): Promise<boolean> {
|
105 | try {
|
106 | const value = await this._lookupNode(root)
|
107 | return value !== null
|
108 | } catch (error: any) {
|
109 | if (error.message == 'Missing node in DB') {
|
110 | return false
|
111 | } else {
|
112 | throw error
|
113 | }
|
114 | }
|
115 | }
|
116 |
|
117 | |
118 |
|
119 |
|
120 | get isCheckpoint() {
|
121 | return false
|
122 | }
|
123 |
|
124 | |
125 |
|
126 |
|
127 |
|
128 |
|
129 |
|
130 | async get(key: Buffer, throwIfMissing = false): Promise<Buffer | null> {
|
131 | const { node, remaining } = await this.findPath(key, throwIfMissing)
|
132 | let value = null
|
133 | if (node && remaining.length === 0) {
|
134 | value = node.value
|
135 | }
|
136 | return value
|
137 | }
|
138 |
|
139 | |
140 |
|
141 |
|
142 |
|
143 |
|
144 |
|
145 |
|
146 | async put(key: Buffer, value: Buffer): Promise<void> {
|
147 |
|
148 | if (!value || value.toString() === '') {
|
149 | return await this.del(key)
|
150 | }
|
151 |
|
152 | await this.lock.wait()
|
153 | if (this.root.equals(KECCAK256_RLP)) {
|
154 |
|
155 | await this._createInitialNode(key, value)
|
156 | } else {
|
157 |
|
158 | const { remaining, stack } = await this.findPath(key)
|
159 |
|
160 | await this._updateNode(key, value, remaining, stack)
|
161 | }
|
162 | this.lock.signal()
|
163 | }
|
164 |
|
165 | |
166 |
|
167 |
|
168 |
|
169 |
|
170 |
|
171 | async del(key: Buffer): Promise<void> {
|
172 | await this.lock.wait()
|
173 | const { node, stack } = await this.findPath(key)
|
174 | if (node) {
|
175 | await this._deleteNode(key, stack)
|
176 | }
|
177 | this.lock.signal()
|
178 | }
|
179 |
|
180 | |
181 |
|
182 |
|
183 |
|
184 |
|
185 |
|
186 | async findPath(key: Buffer, throwIfMissing = false): Promise<Path> {
|
187 |
|
188 | return new Promise(async (resolve, reject) => {
|
189 | const stack: TrieNode[] = []
|
190 | const targetKey = bufferToNibbles(key)
|
191 |
|
192 | const onFound: FoundNodeFunction = async (nodeRef, node, keyProgress, walkController) => {
|
193 | if (node === null) {
|
194 | return reject(new Error('Path not found'))
|
195 | }
|
196 | const keyRemainder = targetKey.slice(matchingNibbleLength(keyProgress, targetKey))
|
197 | stack.push(node)
|
198 |
|
199 | if (node instanceof BranchNode) {
|
200 | if (keyRemainder.length === 0) {
|
201 |
|
202 | resolve({ node, remaining: [], stack })
|
203 | } else {
|
204 | const branchIndex = keyRemainder[0]
|
205 | const branchNode = node.getBranch(branchIndex)
|
206 | if (!branchNode) {
|
207 |
|
208 | resolve({ node: null, remaining: keyRemainder, stack })
|
209 | } else {
|
210 |
|
211 |
|
212 | walkController.onlyBranchIndex(node, keyProgress, branchIndex)
|
213 | }
|
214 | }
|
215 | } else if (node instanceof LeafNode) {
|
216 | if (doKeysMatch(keyRemainder, node.key)) {
|
217 |
|
218 | resolve({ node, remaining: [], stack })
|
219 | } else {
|
220 |
|
221 | resolve({ node: null, remaining: keyRemainder, stack })
|
222 | }
|
223 | } else if (node instanceof ExtensionNode) {
|
224 | const matchingLen = matchingNibbleLength(keyRemainder, node.key)
|
225 | if (matchingLen !== node.key.length) {
|
226 |
|
227 | resolve({ node: null, remaining: keyRemainder, stack })
|
228 | } else {
|
229 |
|
230 | walkController.allChildren(node, keyProgress)
|
231 | }
|
232 | }
|
233 | }
|
234 |
|
235 |
|
236 | try {
|
237 | await this.walkTrie(this.root, onFound)
|
238 | } catch (error: any) {
|
239 | if (error.message == 'Missing node in DB' && !throwIfMissing) {
|
240 |
|
241 | } else {
|
242 | reject(error)
|
243 | }
|
244 | }
|
245 |
|
246 |
|
247 | resolve({ node: null, remaining: [], stack })
|
248 | })
|
249 | }
|
250 |
|
251 | |
252 |
|
253 |
|
254 |
|
255 |
|
256 |
|
257 | async walkTrie(root: Buffer, onFound: FoundNodeFunction): Promise<void> {
|
258 | await WalkController.newWalk(onFound, this, root)
|
259 | }
|
260 |
|
261 | |
262 |
|
263 |
|
264 |
|
265 |
|
266 |
|
267 | async _walkTrie(root: Buffer, onFound: FoundNodeFunction): Promise<void> {
|
268 | await this.walkTrie(root, onFound)
|
269 | }
|
270 |
|
271 | |
272 |
|
273 |
|
274 |
|
275 | async _createInitialNode(key: Buffer, value: Buffer): Promise<void> {
|
276 | const newNode = new LeafNode(bufferToNibbles(key), value)
|
277 | this.root = newNode.hash()
|
278 | await this.db.put(this.root, newNode.serialize())
|
279 | }
|
280 |
|
281 | |
282 |
|
283 |
|
284 | async lookupNode(node: Buffer | Buffer[]): Promise<TrieNode | null> {
|
285 | if (isRawNode(node)) {
|
286 | return decodeRawNode(node as Buffer[])
|
287 | }
|
288 | let value = null
|
289 | let foundNode = null
|
290 | value = await this.db.get(node as Buffer)
|
291 | if (value) {
|
292 | foundNode = decodeNode(value)
|
293 | } else {
|
294 |
|
295 | throw new Error('Missing node in DB')
|
296 | }
|
297 | return foundNode
|
298 | }
|
299 |
|
300 | |
301 |
|
302 |
|
303 |
|
304 |
|
305 | async _lookupNode(node: Buffer | Buffer[]): Promise<TrieNode | null> {
|
306 | return this.lookupNode(node)
|
307 | }
|
308 |
|
309 | |
310 |
|
311 |
|
312 |
|
313 |
|
314 |
|
315 |
|
316 |
|
317 | async _updateNode(
|
318 | k: Buffer,
|
319 | value: Buffer,
|
320 | keyRemainder: Nibbles,
|
321 | stack: TrieNode[]
|
322 | ): Promise<void> {
|
323 | const toSave: BatchDBOp[] = []
|
324 | const lastNode = stack.pop()
|
325 | if (!lastNode) {
|
326 | throw new Error('Stack underflow')
|
327 | }
|
328 |
|
329 |
|
330 | const key = bufferToNibbles(k)
|
331 |
|
332 |
|
333 | let matchLeaf = false
|
334 |
|
335 | if (lastNode instanceof LeafNode) {
|
336 | let l = 0
|
337 | for (let i = 0; i < stack.length; i++) {
|
338 | const n = stack[i]
|
339 | if (n instanceof BranchNode) {
|
340 | l++
|
341 | } else {
|
342 | l += n.key.length
|
343 | }
|
344 | }
|
345 |
|
346 | if (
|
347 | matchingNibbleLength(lastNode.key, key.slice(l)) === lastNode.key.length &&
|
348 | keyRemainder.length === 0
|
349 | ) {
|
350 | matchLeaf = true
|
351 | }
|
352 | }
|
353 |
|
354 | if (matchLeaf) {
|
355 |
|
356 | lastNode.value = value
|
357 | stack.push(lastNode as TrieNode)
|
358 | } else if (lastNode instanceof BranchNode) {
|
359 | stack.push(lastNode)
|
360 | if (keyRemainder.length !== 0) {
|
361 |
|
362 | keyRemainder.shift()
|
363 |
|
364 | const newLeaf = new LeafNode(keyRemainder, value)
|
365 | stack.push(newLeaf)
|
366 | } else {
|
367 | lastNode.value = value
|
368 | }
|
369 | } else {
|
370 |
|
371 | const lastKey = lastNode.key
|
372 | const matchingLength = matchingNibbleLength(lastKey, keyRemainder)
|
373 | const newBranchNode = new BranchNode()
|
374 |
|
375 |
|
376 | if (matchingLength !== 0) {
|
377 | const newKey = lastNode.key.slice(0, matchingLength)
|
378 | const newExtNode = new ExtensionNode(newKey, value)
|
379 | stack.push(newExtNode)
|
380 | lastKey.splice(0, matchingLength)
|
381 | keyRemainder.splice(0, matchingLength)
|
382 | }
|
383 |
|
384 | stack.push(newBranchNode)
|
385 |
|
386 | if (lastKey.length !== 0) {
|
387 | const branchKey = lastKey.shift() as number
|
388 |
|
389 | if (lastKey.length !== 0 || lastNode instanceof LeafNode) {
|
390 |
|
391 | lastNode.key = lastKey
|
392 | const formattedNode = this._formatNode(lastNode, false, toSave)
|
393 | newBranchNode.setBranch(branchKey, formattedNode as EmbeddedNode)
|
394 | } else {
|
395 |
|
396 | this._formatNode(lastNode, false, toSave, true)
|
397 | newBranchNode.setBranch(branchKey, lastNode.value)
|
398 | }
|
399 | } else {
|
400 | newBranchNode.value = lastNode.value
|
401 | }
|
402 |
|
403 | if (keyRemainder.length !== 0) {
|
404 | keyRemainder.shift()
|
405 |
|
406 | const newLeafNode = new LeafNode(keyRemainder, value)
|
407 | stack.push(newLeafNode)
|
408 | } else {
|
409 | newBranchNode.value = value
|
410 | }
|
411 | }
|
412 |
|
413 | await this._saveStack(key, stack, toSave)
|
414 | }
|
415 |
|
416 | |
417 |
|
418 |
|
419 |
|
420 | async _deleteNode(k: Buffer, stack: TrieNode[]): Promise<void> {
|
421 | const processBranchNode = (
|
422 | key: Nibbles,
|
423 | branchKey: number,
|
424 | branchNode: TrieNode,
|
425 | parentNode: TrieNode,
|
426 | stack: TrieNode[]
|
427 | ) => {
|
428 |
|
429 | if (!parentNode || parentNode instanceof BranchNode) {
|
430 |
|
431 | if (parentNode) {
|
432 | stack.push(parentNode)
|
433 | }
|
434 |
|
435 | if (branchNode instanceof BranchNode) {
|
436 |
|
437 |
|
438 |
|
439 | const extensionNode = new ExtensionNode([branchKey], null)
|
440 | stack.push(extensionNode)
|
441 | key.push(branchKey)
|
442 | } else {
|
443 | const branchNodeKey = branchNode.key
|
444 |
|
445 |
|
446 | branchNodeKey.unshift(branchKey)
|
447 | branchNode.key = branchNodeKey.slice(0)
|
448 | key = key.concat(branchNodeKey)
|
449 | }
|
450 | stack.push(branchNode)
|
451 | } else {
|
452 |
|
453 | let parentKey = parentNode.key
|
454 |
|
455 | if (branchNode instanceof BranchNode) {
|
456 |
|
457 | parentKey.push(branchKey)
|
458 | key.push(branchKey)
|
459 | parentNode.key = parentKey
|
460 | stack.push(parentNode)
|
461 | } else {
|
462 | const branchNodeKey = branchNode.key
|
463 |
|
464 |
|
465 |
|
466 | branchNodeKey.unshift(branchKey)
|
467 | key = key.concat(branchNodeKey)
|
468 | parentKey = parentKey.concat(branchNodeKey)
|
469 | branchNode.key = parentKey
|
470 | }
|
471 |
|
472 | stack.push(branchNode)
|
473 | }
|
474 |
|
475 | return key
|
476 | }
|
477 |
|
478 | let lastNode = stack.pop() as TrieNode
|
479 | assert(lastNode)
|
480 | let parentNode = stack.pop()
|
481 | const opStack: BatchDBOp[] = []
|
482 |
|
483 | let key = bufferToNibbles(k)
|
484 |
|
485 | if (!parentNode) {
|
486 |
|
487 | this.root = this.EMPTY_TRIE_ROOT
|
488 | return
|
489 | }
|
490 |
|
491 | if (lastNode instanceof BranchNode) {
|
492 | lastNode.value = null
|
493 | } else {
|
494 |
|
495 |
|
496 | if (!(parentNode instanceof BranchNode)) {
|
497 | throw new Error('Expected branch node')
|
498 | }
|
499 | const lastNodeKey = lastNode.key
|
500 | key.splice(key.length - lastNodeKey.length)
|
501 |
|
502 | this._formatNode(lastNode, false, opStack, true)
|
503 | parentNode.setBranch(key.pop() as number, null)
|
504 | lastNode = parentNode
|
505 | parentNode = stack.pop()
|
506 | }
|
507 |
|
508 |
|
509 |
|
510 | const branchNodes: [number, EmbeddedNode][] = lastNode.getChildren()
|
511 |
|
512 |
|
513 | if (branchNodes.length === 1) {
|
514 |
|
515 | const branchNode = branchNodes[0][1]
|
516 | const branchNodeKey = branchNodes[0][0]
|
517 |
|
518 |
|
519 | const foundNode = await this._lookupNode(branchNode)
|
520 | if (foundNode) {
|
521 | key = processBranchNode(
|
522 | key,
|
523 | branchNodeKey,
|
524 | foundNode as TrieNode,
|
525 | parentNode as TrieNode,
|
526 | stack
|
527 | )
|
528 | await this._saveStack(key, stack, opStack)
|
529 | }
|
530 | } else {
|
531 |
|
532 | if (parentNode) {
|
533 | stack.push(parentNode)
|
534 | }
|
535 |
|
536 | stack.push(lastNode)
|
537 | await this._saveStack(key, stack, opStack)
|
538 | }
|
539 | }
|
540 |
|
541 | |
542 |
|
543 |
|
544 |
|
545 |
|
546 |
|
547 |
|
548 | async _saveStack(key: Nibbles, stack: TrieNode[], opStack: BatchDBOp[]): Promise<void> {
|
549 | let lastRoot
|
550 |
|
551 |
|
552 | while (stack.length) {
|
553 | const node = stack.pop() as TrieNode
|
554 | if (node instanceof LeafNode) {
|
555 | key.splice(key.length - node.key.length)
|
556 | } else if (node instanceof ExtensionNode) {
|
557 | key.splice(key.length - node.key.length)
|
558 | if (lastRoot) {
|
559 | node.value = lastRoot
|
560 | }
|
561 | } else if (node instanceof BranchNode) {
|
562 | if (lastRoot) {
|
563 | const branchKey = key.pop()
|
564 | node.setBranch(branchKey!, lastRoot)
|
565 | }
|
566 | }
|
567 | lastRoot = this._formatNode(node, stack.length === 0, opStack) as Buffer
|
568 | }
|
569 |
|
570 | if (lastRoot) {
|
571 | this.root = lastRoot
|
572 | }
|
573 |
|
574 | await this.db.batch(opStack)
|
575 | }
|
576 |
|
577 | |
578 |
|
579 |
|
580 |
|
581 |
|
582 |
|
583 |
|
584 |
|
585 |
|
586 | _formatNode(
|
587 | node: TrieNode,
|
588 | topLevel: boolean,
|
589 | opStack: BatchDBOp[],
|
590 | remove: boolean = false
|
591 | ): Buffer | (EmbeddedNode | null)[] {
|
592 | const rlpNode = node.serialize()
|
593 |
|
594 | if (rlpNode.length >= 32 || topLevel) {
|
595 |
|
596 |
|
597 | const hashRoot = keccak(rlpNode)
|
598 |
|
599 | if (remove) {
|
600 | if (this._deleteFromDB) {
|
601 | opStack.push({
|
602 | type: 'del',
|
603 | key: hashRoot,
|
604 | })
|
605 | }
|
606 | } else {
|
607 | opStack.push({
|
608 | type: 'put',
|
609 | key: hashRoot,
|
610 | value: rlpNode,
|
611 | })
|
612 | }
|
613 |
|
614 | return hashRoot
|
615 | }
|
616 |
|
617 | return node.raw()
|
618 | }
|
619 |
|
620 | |
621 |
|
622 |
|
623 |
|
624 |
|
625 |
|
626 |
|
627 |
|
628 |
|
629 |
|
630 |
|
631 |
|
632 |
|
633 |
|
634 | async batch(ops: BatchDBOp[]): Promise<void> {
|
635 | for (const op of ops) {
|
636 | if (op.type === 'put') {
|
637 | if (!op.value) {
|
638 | throw new Error('Invalid batch db operation')
|
639 | }
|
640 | await this.put(op.key, op.value)
|
641 | } else if (op.type === 'del') {
|
642 | await this.del(op.key)
|
643 | }
|
644 | }
|
645 | }
|
646 |
|
647 | |
648 |
|
649 |
|
650 |
|
651 |
|
652 | static async fromProof(proof: Proof, trie?: Trie): Promise<Trie> {
|
653 | const opStack = proof.map((nodeValue) => {
|
654 | return {
|
655 | type: 'put',
|
656 | key: keccak(nodeValue),
|
657 | value: nodeValue,
|
658 | } as PutBatch
|
659 | })
|
660 |
|
661 | if (!trie) {
|
662 | trie = new Trie()
|
663 | if (opStack[0]) {
|
664 | trie.root = opStack[0].key
|
665 | }
|
666 | }
|
667 |
|
668 | await trie.db.batch(opStack)
|
669 | return trie
|
670 | }
|
671 |
|
672 | |
673 |
|
674 |
|
675 |
|
676 |
|
677 |
|
678 | static async prove(trie: Trie, key: Buffer): Promise<Proof> {
|
679 | return this.createProof(trie, key)
|
680 | }
|
681 |
|
682 | |
683 |
|
684 |
|
685 |
|
686 |
|
687 | static async createProof(trie: Trie, key: Buffer): Promise<Proof> {
|
688 | const { stack } = await trie.findPath(key)
|
689 | const p = stack.map((stackElem) => {
|
690 | return stackElem.serialize()
|
691 | })
|
692 | return p
|
693 | }
|
694 |
|
695 | |
696 |
|
697 |
|
698 |
|
699 |
|
700 |
|
701 |
|
702 |
|
703 | static async verifyProof(rootHash: Buffer, key: Buffer, proof: Proof): Promise<Buffer | null> {
|
704 | let proofTrie = new Trie(null, rootHash)
|
705 | try {
|
706 | proofTrie = await Trie.fromProof(proof, proofTrie)
|
707 | } catch (e: any) {
|
708 | throw new Error('Invalid proof nodes given')
|
709 | }
|
710 | try {
|
711 | const value = await proofTrie.get(key, true)
|
712 | return value
|
713 | } catch (err: any) {
|
714 | if (err.message == 'Missing node in DB') {
|
715 | throw new Error('Invalid proof provided')
|
716 | } else {
|
717 | throw err
|
718 | }
|
719 | }
|
720 | }
|
721 |
|
722 | |
723 |
|
724 |
|
725 |
|
726 | createReadStream(): ReadStream {
|
727 | return new ReadStream(this)
|
728 | }
|
729 |
|
730 | |
731 |
|
732 |
|
733 | copy(): Trie {
|
734 | const db = this.db.copy()
|
735 | return new Trie(db._leveldb, this.root)
|
736 | }
|
737 |
|
738 | |
739 |
|
740 |
|
741 |
|
742 |
|
743 |
|
744 | async _findDbNodes(onFound: FoundNodeFunction): Promise<void> {
|
745 | const outerOnFound: FoundNodeFunction = async (nodeRef, node, key, walkController) => {
|
746 | if (isRawNode(nodeRef)) {
|
747 | if (node !== null) {
|
748 | walkController.allChildren(node, key)
|
749 | }
|
750 | } else {
|
751 | onFound(nodeRef, node, key, walkController)
|
752 | }
|
753 | }
|
754 | await this.walkTrie(this.root, outerOnFound)
|
755 | }
|
756 |
|
757 | |
758 |
|
759 |
|
760 |
|
761 |
|
762 | async _findValueNodes(onFound: FoundNodeFunction): Promise<void> {
|
763 | const outerOnFound: FoundNodeFunction = async (nodeRef, node, key, walkController) => {
|
764 | let fullKey = key
|
765 |
|
766 | if (node instanceof LeafNode) {
|
767 | fullKey = key.concat(node.key)
|
768 |
|
769 | onFound(nodeRef, node, fullKey, walkController)
|
770 | } else if (node instanceof BranchNode && node.value) {
|
771 |
|
772 | onFound(nodeRef, node, fullKey, walkController)
|
773 | } else {
|
774 |
|
775 | if (node !== null) {
|
776 | walkController.allChildren(node, key)
|
777 | }
|
778 | }
|
779 | }
|
780 | await this.walkTrie(this.root, outerOnFound)
|
781 | }
|
782 | }
|