1 | /// <reference types="node" />
|
2 | import Semaphore from 'semaphore-async-await';
|
3 | import { DB, BatchDBOp } from './db';
|
4 | import { TrieReadStream as ReadStream } from './readStream';
|
5 | import { WalkController } from './util/walkController';
|
6 | import { TrieNode, EmbeddedNode, Nibbles } from './trieNode';
|
7 | import type { LevelUp } from 'levelup';
|
8 | export declare type Proof = Buffer[];
|
9 | interface Path {
|
10 | node: TrieNode | null;
|
11 | remaining: Nibbles;
|
12 | stack: TrieNode[];
|
13 | }
|
14 | export declare type FoundNodeFunction = (nodeRef: Buffer, node: TrieNode | null, key: Nibbles, walkController: WalkController) => void;
|
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 | export declare class Trie {
|
21 | /** The root for an empty trie */
|
22 | EMPTY_TRIE_ROOT: Buffer;
|
23 | protected lock: Semaphore;
|
24 | /** The backend DB */
|
25 | db: DB;
|
26 | private _root;
|
27 | private _deleteFromDB;
|
28 | /**
|
29 | * test
|
30 | * @param db - A [levelup](https://github.com/Level/levelup) instance. By default (if the db is `null` or
|
31 | * left undefined) creates an in-memory [memdown](https://github.com/Level/memdown) instance.
|
32 | * @param root - A `Buffer` for the root of a previously stored trie
|
33 | * @param deleteFromDB - Delete nodes from DB on delete operations (disallows switching to an older state root) (default: `false`)
|
34 | */
|
35 | constructor(db?: LevelUp | null, root?: Buffer, deleteFromDB?: boolean);
|
36 | /**
|
37 | * Sets the current root of the `trie`
|
38 | */
|
39 | set root(value: Buffer);
|
40 | /**
|
41 | * Gets the current root of the `trie`
|
42 | */
|
43 | get root(): Buffer;
|
44 | /**
|
45 | * This method is deprecated.
|
46 | * Please use { Trie.root} instead.
|
47 | *
|
48 | * value
|
49 | *
|
50 | */
|
51 | setRoot(value?: Buffer): void;
|
52 | /**
|
53 | * Checks if a given root exists.
|
54 | */
|
55 | checkRoot(root: Buffer): Promise<boolean>;
|
56 | /**
|
57 | * BaseTrie has no checkpointing so return false
|
58 | */
|
59 | get isCheckpoint(): boolean;
|
60 | /**
|
61 | * Gets a value given a `key`
|
62 | * @param key - the key to search for
|
63 | * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
|
64 | * @returns A Promise that resolves to `Buffer` if a value was found or `null` if no value was found.
|
65 | */
|
66 | get(key: Buffer, throwIfMissing?: boolean): Promise<Buffer | null>;
|
67 | /**
|
68 | * Stores a given `value` at the given `key` or do a delete if `value` is empty
|
69 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
70 | * @param key
|
71 | * @param value
|
72 | * @returns A Promise that resolves once value is stored.
|
73 | */
|
74 | put(key: Buffer, value: Buffer): Promise<void>;
|
75 | /**
|
76 | * Deletes a value given a `key` from the trie
|
77 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
78 | * @param key
|
79 | * @returns A Promise that resolves once value is deleted.
|
80 | */
|
81 | del(key: Buffer): Promise<void>;
|
82 | /**
|
83 | * Tries to find a path to the node for the given key.
|
84 | * It returns a `stack` of nodes to the closest node.
|
85 | * @param key - the search key
|
86 | * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
|
87 | */
|
88 | findPath(key: Buffer, throwIfMissing?: boolean): Promise<Path>;
|
89 | /**
|
90 | * Walks a trie until finished.
|
91 | * @param root
|
92 | * @param onFound - callback to call when a node is found. This schedules new tasks. If no tasks are available, the Promise resolves.
|
93 | * @returns Resolves when finished walking trie.
|
94 | */
|
95 | walkTrie(root: Buffer, onFound: FoundNodeFunction): Promise<void>;
|
96 | /**
|
97 | * @hidden
|
98 | * Backwards compatibility
|
99 | * @param root -
|
100 | * @param onFound -
|
101 | */
|
102 | _walkTrie(root: Buffer, onFound: FoundNodeFunction): Promise<void>;
|
103 | /**
|
104 | * Creates the initial node from an empty tree.
|
105 | * @private
|
106 | */
|
107 | _createInitialNode(key: Buffer, value: Buffer): Promise<void>;
|
108 | /**
|
109 | * Retrieves a node from db by hash.
|
110 | */
|
111 | lookupNode(node: Buffer | Buffer[]): Promise<TrieNode | null>;
|
112 | /**
|
113 | * @hidden
|
114 | * Backwards compatibility
|
115 | * @param node The node hash to lookup from the DB
|
116 | */
|
117 | _lookupNode(node: Buffer | Buffer[]): Promise<TrieNode | null>;
|
118 | /**
|
119 | * Updates a node.
|
120 | * @private
|
121 | * @param key
|
122 | * @param value
|
123 | * @param keyRemainder
|
124 | * @param stack
|
125 | */
|
126 | _updateNode(k: Buffer, value: Buffer, keyRemainder: Nibbles, stack: TrieNode[]): Promise<void>;
|
127 | /**
|
128 | * Deletes a node from the trie.
|
129 | * @private
|
130 | */
|
131 | _deleteNode(k: Buffer, stack: TrieNode[]): Promise<void>;
|
132 | /**
|
133 | * Saves a stack of nodes to the database.
|
134 | * @private
|
135 | * @param key - the key. Should follow the stack
|
136 | * @param stack - a stack of nodes to the value given by the key
|
137 | * @param opStack - a stack of levelup operations to commit at the end of this funciton
|
138 | */
|
139 | _saveStack(key: Nibbles, stack: TrieNode[], opStack: BatchDBOp[]): Promise<void>;
|
140 | /**
|
141 | * Formats node to be saved by `levelup.batch`.
|
142 | * @private
|
143 | * @param node - the node to format.
|
144 | * @param topLevel - if the node is at the top level.
|
145 | * @param opStack - the opStack to push the node's data.
|
146 | * @param remove - whether to remove the node (only used for CheckpointTrie).
|
147 | * @returns The node's hash used as the key or the rawNode.
|
148 | */
|
149 | _formatNode(node: TrieNode, topLevel: boolean, opStack: BatchDBOp[], remove?: boolean): Buffer | (EmbeddedNode | null)[];
|
150 | /**
|
151 | * The given hash of operations (key additions or deletions) are executed on the trie
|
152 | * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
|
153 | * @example
|
154 | * const ops = [
|
155 | * { type: 'del', key: Buffer.from('father') }
|
156 | * , { type: 'put', key: Buffer.from('name'), value: Buffer.from('Yuri Irsenovich Kim') }
|
157 | * , { type: 'put', key: Buffer.from('dob'), value: Buffer.from('16 February 1941') }
|
158 | * , { type: 'put', key: Buffer.from('spouse'), value: Buffer.from('Kim Young-sook') }
|
159 | * , { type: 'put', key: Buffer.from('occupation'), value: Buffer.from('Clown') }
|
160 | * ]
|
161 | * await trie.batch(ops)
|
162 | * @param ops
|
163 | */
|
164 | batch(ops: BatchDBOp[]): Promise<void>;
|
165 | /**
|
166 | * Saves the nodes from a proof into the trie. If no trie is provided a new one wil be instantiated.
|
167 | * @param proof
|
168 | * @param trie
|
169 | */
|
170 | static fromProof(proof: Proof, trie?: Trie): Promise<Trie>;
|
171 | /**
|
172 | * prove has been renamed to {@link Trie.createProof}.
|
173 | * @deprecated
|
174 | * @param trie
|
175 | * @param key
|
176 | */
|
177 | static prove(trie: Trie, key: Buffer): Promise<Proof>;
|
178 | /**
|
179 | * Creates a proof from a trie and key that can be verified using {@link Trie.verifyProof}.
|
180 | * @param trie
|
181 | * @param key
|
182 | */
|
183 | static createProof(trie: Trie, key: Buffer): Promise<Proof>;
|
184 | /**
|
185 | * Verifies a proof.
|
186 | * @param rootHash
|
187 | * @param key
|
188 | * @param proof
|
189 | * @throws If proof is found to be invalid.
|
190 | * @returns The value from the key, or null if valid proof of non-existence.
|
191 | */
|
192 | static verifyProof(rootHash: Buffer, key: Buffer, proof: Proof): Promise<Buffer | null>;
|
193 | /**
|
194 | * {@link verifyRangeProof}
|
195 | */
|
196 | static verifyRangeProof(rootHash: Buffer, firstKey: Buffer | null, lastKey: Buffer | null, keys: Buffer[], values: Buffer[], proof: Buffer[] | null): Promise<boolean>;
|
197 | /**
|
198 | * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.
|
199 | * @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`
|
200 | */
|
201 | createReadStream(): ReadStream;
|
202 | /**
|
203 | * Creates a new trie backed by the same db.
|
204 | */
|
205 | copy(): Trie;
|
206 | /**
|
207 | * Finds all nodes that are stored directly in the db
|
208 | * (some nodes are stored raw inside other nodes)
|
209 | * called by {@link ScratchReadStream}
|
210 | * @private
|
211 | */
|
212 | _findDbNodes(onFound: FoundNodeFunction): Promise<void>;
|
213 | /**
|
214 | * Finds all nodes that store k,v values
|
215 | * called by {@link TrieReadStream}
|
216 | * @private
|
217 | */
|
218 | _findValueNodes(onFound: FoundNodeFunction): Promise<void>;
|
219 | }
|
220 | export {};
|