ethereum.cancun.trie
State Trie ^^^^^^^^^^
.. contents:: Table of Contents :backlinks: none :local:
Introduction
The state trie is the structure responsible for storing
.fork_types.Account
objects.
EMPTY_TRIE_ROOT
59 | EMPTY_TRIE_ROOT = Root( |
---|---|
60 | hex_to_bytes( |
61 | "56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421" |
62 | ) |
63 | ) |
Node
65 | Node = ( |
---|---|
66 | Account |
67 | | Bytes |
68 | | LegacyTransaction |
69 | | Receipt |
70 | | Uint |
71 | | U256 |
72 | | Withdrawal |
73 | | None |
74 | ) |
K
75 | K = TypeVar("K", bound=Bytes) |
---|
V
76 | V = TypeVar( |
---|---|
77 | "V", |
78 | Optional[Account], |
79 | Optional[Bytes], |
80 | Bytes, |
81 | Optional[LegacyTransaction | Bytes], |
82 | Optional[Receipt | Bytes], |
83 | Optional[Withdrawal | Bytes], |
84 | Uint, |
85 | U256, |
86 | ) |
LeafNode
Leaf node in the Merkle Trie
89 | @slotted_freezable |
---|
90 | @dataclass |
---|
class LeafNode:
rest_of_key
94 | rest_of_key: Bytes |
---|
value
95 | value: Extended |
---|
ExtensionNode
Extension node in the Merkle Trie
98 | @slotted_freezable |
---|
99 | @dataclass |
---|
class ExtensionNode:
key_segment
103 | key_segment: Bytes |
---|
subnode
104 | subnode: Extended |
---|
BranchSubnodes
107 | BranchSubnodes = Tuple[ |
---|---|
108 | Extended, |
109 | Extended, |
110 | Extended, |
111 | Extended, |
112 | Extended, |
113 | Extended, |
114 | Extended, |
115 | Extended, |
116 | Extended, |
117 | Extended, |
118 | Extended, |
119 | Extended, |
120 | Extended, |
121 | Extended, |
122 | Extended, |
123 | Extended, |
124 | ] |
BranchNode
Branch node in the Merkle Trie
127 | @slotted_freezable |
---|
128 | @dataclass |
---|
class BranchNode:
subnodes
132 | subnodes: BranchSubnodes |
---|
value
133 | value: Extended |
---|
InternalNode
136 | InternalNode = LeafNode | ExtensionNode | BranchNode |
---|
encode_internal_node
Encodes a Merkle Trie node into its RLP form. The RLP will then be
serialized into a Bytes
and hashed unless it is less that 32 bytes
when serialized.
This function also accepts None
, representing the absence of a node,
which is encoded to b""
.
Parameters
node : Optional[InternalNode] The node to encode.
Returns
encoded : Extended
The node encoded as RLP.
def encode_internal_node(node: Optional[InternalNode]) -> Extended:
140 | """ |
---|---|
141 | Encodes a Merkle Trie node into its RLP form. The RLP will then be |
142 | serialized into a `Bytes` and hashed unless it is less that 32 bytes |
143 | when serialized. |
144 |
|
145 | This function also accepts `None`, representing the absence of a node, |
146 | which is encoded to `b""`. |
147 |
|
148 | Parameters |
149 | ---------- |
150 | node : Optional[InternalNode] |
151 | The node to encode. |
152 |
|
153 | Returns |
154 | ------- |
155 | encoded : `Extended` |
156 | The node encoded as RLP. |
157 | """ |
158 | unencoded: Extended |
159 | if node is None: |
160 | unencoded = b"" |
161 | elif isinstance(node, LeafNode): |
162 | unencoded = ( |
163 | nibble_list_to_compact(node.rest_of_key, True), |
164 | node.value, |
165 | ) |
166 | elif isinstance(node, ExtensionNode): |
167 | unencoded = ( |
168 | nibble_list_to_compact(node.key_segment, False), |
169 | node.subnode, |
170 | ) |
171 | elif isinstance(node, BranchNode): |
172 | unencoded = list(node.subnodes) + [node.value] |
173 | else: |
174 | raise AssertionError(f"Invalid internal node type {type(node)}!") |
175 | |
176 | encoded = rlp.encode(unencoded) |
177 | if len(encoded) < 32: |
178 | return unencoded |
179 | else: |
180 | return keccak256(encoded) |
encode_node
Encode a Node for storage in the Merkle Trie.
Currently mostly an unimplemented stub.
def encode_node(node: Node, storage_root: Optional[Bytes]) -> Bytes:
184 | """ |
---|---|
185 | Encode a Node for storage in the Merkle Trie. |
186 |
|
187 | Currently mostly an unimplemented stub. |
188 | """ |
189 | if isinstance(node, Account): |
190 | assert storage_root is not None |
191 | return encode_account(node, storage_root) |
192 | elif isinstance(node, (LegacyTransaction, Receipt, Withdrawal, U256)): |
193 | return rlp.encode(node) |
194 | elif isinstance(node, Bytes): |
195 | return node |
196 | else: |
197 | return previous_trie.encode_node(node, storage_root) |
Trie
The Merkle Trie.
200 | @dataclass |
---|
class Trie:
secured
206 | secured: bool |
---|
default
207 | default: V |
---|
_data
208 | _data: Dict[K, V] = field(default_factory=dict) |
---|
copy_trie
Create a copy of trie
. Since only frozen objects may be stored in tries,
the contents are reused.
Parameters
trie: Trie
Trie to copy.
Returns
new_trie : Trie[K, V]
A copy of the trie.
def copy_trie(trie: Trie[K, V]) -> Trie[K, V]:
212 | """ |
---|---|
213 | Create a copy of `trie`. Since only frozen objects may be stored in tries, |
214 | the contents are reused. |
215 |
|
216 | Parameters |
217 | ---------- |
218 | trie: `Trie` |
219 | Trie to copy. |
220 |
|
221 | Returns |
222 | ------- |
223 | new_trie : `Trie[K, V]` |
224 | A copy of the trie. |
225 | """ |
226 | return Trie(trie.secured, trie.default, copy.copy(trie._data)) |
trie_set
Stores an item in a Merkle Trie.
This method deletes the key if value == trie.default
, because the Merkle
Trie represents the default value by omitting it from the trie.
Parameters
trie: Trie
Trie to store in.
key : Bytes
Key to lookup.
value : V
Node to insert at key
.
def trie_set(trie: Trie[K, V], key: K, value: V) -> None:
230 | """ |
---|---|
231 | Stores an item in a Merkle Trie. |
232 |
|
233 | This method deletes the key if `value == trie.default`, because the Merkle |
234 | Trie represents the default value by omitting it from the trie. |
235 |
|
236 | Parameters |
237 | ---------- |
238 | trie: `Trie` |
239 | Trie to store in. |
240 | key : `Bytes` |
241 | Key to lookup. |
242 | value : `V` |
243 | Node to insert at `key`. |
244 | """ |
245 | if value == trie.default: |
246 | if key in trie._data: |
247 | del trie._data[key] |
248 | else: |
249 | trie._data[key] = value |
trie_get
Gets an item from the Merkle Trie.
This method returns trie.default
if the key is missing.
Parameters
trie: Trie to lookup in. key : Key to lookup.
Returns
node : V
Node at key
in the trie.
def trie_get(trie: Trie[K, V], key: K) -> V:
253 | """ |
---|---|
254 | Gets an item from the Merkle Trie. |
255 |
|
256 | This method returns `trie.default` if the key is missing. |
257 |
|
258 | Parameters |
259 | ---------- |
260 | trie: |
261 | Trie to lookup in. |
262 | key : |
263 | Key to lookup. |
264 |
|
265 | Returns |
266 | ------- |
267 | node : `V` |
268 | Node at `key` in the trie. |
269 | """ |
270 | return trie._data.get(key, trie.default) |
common_prefix_length
Find the longest common prefix of two sequences.
def common_prefix_length(a: Sequence, b: Sequence) -> int:
274 | """ |
---|---|
275 | Find the longest common prefix of two sequences. |
276 | """ |
277 | for i in range(len(a)): |
278 | if i >= len(b) or a[i] != b[i]: |
279 | return i |
280 | return len(a) |
nibble_list_to_compact
Compresses nibble-list into a standard byte array with a flag.
A nibble-list is a list of byte values no greater than 15
. The flag is
encoded in high nibble of the highest byte. The flag nibble can be broken
down into two two-bit flags.
Highest nibble::
+---+---+----------+--------+
| _ | _ | is_leaf | parity |
+---+---+----------+--------+
3 2 1 0
The lowest bit of the nibble encodes the parity of the length of the
remaining nibbles -- 0
when even and 1
when odd. The second lowest bit
is used to distinguish leaf and extension nodes. The other two bits are not
used.
Parameters
x : Array of nibbles. is_leaf : True if this is part of a leaf node, or false if it is an extension node.
Returns
compressed : bytearray
Compact byte array.
def nibble_list_to_compact(x: Bytes, is_leaf: bool) -> Bytes:
284 | """ |
---|---|
285 | Compresses nibble-list into a standard byte array with a flag. |
286 |
|
287 | A nibble-list is a list of byte values no greater than `15`. The flag is |
288 | encoded in high nibble of the highest byte. The flag nibble can be broken |
289 | down into two two-bit flags. |
290 |
|
291 | Highest nibble:: |
292 |
|
293 | +---+---+----------+--------+ |
294 | | _ | _ | is_leaf | parity | |
295 | +---+---+----------+--------+ |
296 | 3 2 1 0 |
297 |
|
298 |
|
299 | The lowest bit of the nibble encodes the parity of the length of the |
300 | remaining nibbles -- `0` when even and `1` when odd. The second lowest bit |
301 | is used to distinguish leaf and extension nodes. The other two bits are not |
302 | used. |
303 |
|
304 | Parameters |
305 | ---------- |
306 | x : |
307 | Array of nibbles. |
308 | is_leaf : |
309 | True if this is part of a leaf node, or false if it is an extension |
310 | node. |
311 |
|
312 | Returns |
313 | ------- |
314 | compressed : `bytearray` |
315 | Compact byte array. |
316 | """ |
317 | compact = bytearray() |
318 | |
319 | if len(x) % 2 == 0: # ie even length |
320 | compact.append(16 * (2 * is_leaf)) |
321 | for i in range(0, len(x), 2): |
322 | compact.append(16 * x[i] + x[i + 1]) |
323 | else: |
324 | compact.append(16 * ((2 * is_leaf) + 1) + x[0]) |
325 | for i in range(1, len(x), 2): |
326 | compact.append(16 * x[i] + x[i + 1]) |
327 | |
328 | return Bytes(compact) |
bytes_to_nibble_list
Converts a Bytes
into to a sequence of nibbles (bytes with value < 16).
Parameters
bytes_:
The Bytes
to convert.
Returns
nibble_list : Bytes
The Bytes
in nibble-list format.
def bytes_to_nibble_list(bytes_: Bytes) -> Bytes:
332 | """ |
---|---|
333 | Converts a `Bytes` into to a sequence of nibbles (bytes with value < 16). |
334 |
|
335 | Parameters |
336 | ---------- |
337 | bytes_: |
338 | The `Bytes` to convert. |
339 |
|
340 | Returns |
341 | ------- |
342 | nibble_list : `Bytes` |
343 | The `Bytes` in nibble-list format. |
344 | """ |
345 | nibble_list = bytearray(2 * len(bytes_)) |
346 | for byte_index, byte in enumerate(bytes_): |
347 | nibble_list[byte_index * 2] = (byte & 0xF0) >> 4 |
348 | nibble_list[byte_index * 2 + 1] = byte & 0x0F |
349 | return Bytes(nibble_list) |
_prepare_trie
Prepares the trie for root calculation. Removes values that are empty,
hashes the keys (if secured == True
) and encodes all the nodes.
Parameters
trie :
The Trie
to prepare.
get_storage_root :
Function to get the storage root of an account. Needed to encode
Account
objects.
Returns
out : Mapping[ethereum.base_types.Bytes, Node]
Object with keys mapped to nibble-byte form.
def _prepare_trie(trie: Trie[K, V], get_storage_root: Optional[Callable[[Address], Root]]) -> Mapping[Bytes, Bytes]:
356 | """ |
---|---|
357 | Prepares the trie for root calculation. Removes values that are empty, |
358 | hashes the keys (if `secured == True`) and encodes all the nodes. |
359 |
|
360 | Parameters |
361 | ---------- |
362 | trie : |
363 | The `Trie` to prepare. |
364 | get_storage_root : |
365 | Function to get the storage root of an account. Needed to encode |
366 | `Account` objects. |
367 |
|
368 | Returns |
369 | ------- |
370 | out : `Mapping[ethereum.base_types.Bytes, Node]` |
371 | Object with keys mapped to nibble-byte form. |
372 | """ |
373 | mapped: MutableMapping[Bytes, Bytes] = {} |
374 | |
375 | for preimage, value in trie._data.items(): |
376 | if isinstance(value, Account): |
377 | assert get_storage_root is not None |
378 | address = Address(preimage) |
379 | encoded_value = encode_node(value, get_storage_root(address)) |
380 | else: |
381 | encoded_value = encode_node(value) |
382 | if encoded_value == b"": |
383 | raise AssertionError |
384 | key: Bytes |
385 | if trie.secured: |
386 | # "secure" tries hash keys once before construction |
387 | key = keccak256(preimage) |
388 | else: |
389 | key = preimage |
390 | mapped[bytes_to_nibble_list(key)] = encoded_value |
391 | |
392 | return mapped |
root
Computes the root of a modified merkle patricia trie (MPT).
Parameters
trie :
Trie
to get the root of.
get_storage_root :
Function to get the storage root of an account. Needed to encode
Account
objects.
Returns
root : .fork_types.Root
MPT root of the underlying key-value pairs.
def root(trie: Trie[K, V], get_storage_root: Optional[Callable[[Address], Root]]) -> Root:
399 | """ |
---|---|
400 | Computes the root of a modified merkle patricia trie (MPT). |
401 |
|
402 | Parameters |
403 | ---------- |
404 | trie : |
405 | `Trie` to get the root of. |
406 | get_storage_root : |
407 | Function to get the storage root of an account. Needed to encode |
408 | `Account` objects. |
409 |
|
410 |
|
411 | Returns |
412 | ------- |
413 | root : `.fork_types.Root` |
414 | MPT root of the underlying key-value pairs. |
415 | """ |
416 | obj = _prepare_trie(trie, get_storage_root) |
417 | |
418 | root_node = encode_internal_node(patricialize(obj, Uint(0))) |
419 | if len(rlp.encode(root_node)) < 32: |
420 | return keccak256(rlp.encode(root_node)) |
421 | else: |
422 | assert isinstance(root_node, Bytes) |
423 | return Root(root_node) |
patricialize
Structural composition function.
Used to recursively patricialize and merkleize a dictionary. Includes memoization of the tree structure and hashes.
Parameters
obj : Underlying trie key-value pairs, with keys in nibble-list format. level : Current trie level.
Returns
node : ethereum.base_types.Bytes
Root node of obj
.
def patricialize(obj: Mapping[Bytes, Bytes], level: Uint) -> Optional[InternalNode]:
429 | """ |
---|---|
430 | Structural composition function. |
431 |
|
432 | Used to recursively patricialize and merkleize a dictionary. Includes |
433 | memoization of the tree structure and hashes. |
434 |
|
435 | Parameters |
436 | ---------- |
437 | obj : |
438 | Underlying trie key-value pairs, with keys in nibble-list format. |
439 | level : |
440 | Current trie level. |
441 |
|
442 | Returns |
443 | ------- |
444 | node : `ethereum.base_types.Bytes` |
445 | Root node of `obj`. |
446 | """ |
447 | if len(obj) == 0: |
448 | return None |
449 | |
450 | arbitrary_key = next(iter(obj)) |
451 | |
452 | # if leaf node |
453 | if len(obj) == 1: |
454 | leaf = LeafNode(arbitrary_key[level:], obj[arbitrary_key]) |
455 | return leaf |
456 | |
457 | # prepare for extension node check by finding max j such that all keys in |
458 | # obj have the same key[i:j] |
459 | substring = arbitrary_key[level:] |
460 | prefix_length = len(substring) |
461 | for key in obj: |
462 | prefix_length = min( |
463 | prefix_length, common_prefix_length(substring, key[level:]) |
464 | ) |
465 |
|
466 | # finished searching, found another key at the current level |
467 | if prefix_length == 0: |
468 | break |
469 | |
470 | # if extension node |
471 | if prefix_length > 0: |
472 | prefix = arbitrary_key[int(level) : int(level) + prefix_length] |
473 | return ExtensionNode( |
474 | prefix, |
475 | encode_internal_node( |
476 | patricialize(obj, level + Uint(prefix_length)) |
477 | ), |
478 | ) |
479 | |
480 | branches: List[MutableMapping[Bytes, Bytes]] = [] |
481 | for _ in range(16): |
482 | branches.append({}) |
483 | value = b"" |
484 | for key in obj: |
485 | if len(key) == level: |
486 | # shouldn't ever have an account or receipt in an internal node |
487 | if isinstance(obj[key], (Account, Receipt, Uint)): |
488 | raise AssertionError |
489 | value = obj[key] |
490 | else: |
491 | branches[key[level]][key] = obj[key] |
492 | |
493 | subnodes = tuple( |
494 | encode_internal_node(patricialize(branches[k], level + Uint(1))) |
495 | for k in range(16) |
496 | ) |
497 | return BranchNode( |
498 | cast(BranchSubnodes, assert_type(subnodes, Tuple[Extended, ...])), |
499 | value, |
500 | ) |