ethereum.forks.paris.trieethereum.forks.shanghai.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

58
EMPTY_TRIE_ROOT = Root(
59
    hex_to_bytes(
60
        "56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"
61
    )
62
)

Node

64
Node = Account | Bytes | LegacyTransaction | Receipt | Uint | U256 | None
64
Node = (
65
    Account
66
    | Bytes
67
    | LegacyTransaction
68
    | Receipt
69
    | Uint
70
    | U256
71
    | Withdrawal
72
    | None
73
)

K

74
K = TypeVar("K", bound=Bytes)

V

75
V = TypeVar(
76
    "V",
77
    Optional[Account],
78
    Optional[Bytes],
79
    Bytes,
80
    Optional[LegacyTransaction | Bytes],
81
    Optional[Receipt | Bytes],
82
    Optional[Withdrawal | Bytes],
83
    Uint,
84
    U256,
85
)

LeafNode

Leaf node in the Merkle Trie.

88
@slotted_freezable
89
@dataclass
class LeafNode:

rest_of_key

93
    rest_of_key: Bytes

value

94
    value: Extended

ExtensionNode

Extension node in the Merkle Trie.

97
@slotted_freezable
98
@dataclass
class ExtensionNode:

key_segment

102
    key_segment: Bytes

subnode

103
    subnode: Extended

BranchSubnodes

106
BranchSubnodes = Tuple[
107
    Extended,
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
]

BranchNode

Branch node in the Merkle Trie.

126
@slotted_freezable
127
@dataclass
class BranchNode:

subnodes

131
    subnodes: BranchSubnodes

value

132
    value: Extended

InternalNode

135
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 : rlp.RLPExtended The node encoded as RLP.

def encode_internal_node(node: Optional[InternalNode]) -> Extended:
139
    """
140
    Encodes a Merkle Trie node into its RLP form. The RLP will then be
141
    serialized into a `Bytes` and hashed unless it is less that 32 bytes
142
    when serialized.
143
144
    This function also accepts `None`, representing the absence of a node,
145
    which is encoded to `b""`.
146
147
    Parameters
148
    ----------
149
    node : Optional[InternalNode]
150
        The node to encode.
151
152
    Returns
153
    -------
144
    encoded : `rlp.RLP`
154
    encoded : `Extended`
155
        The node encoded as RLP.
156
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)
182
    elif isinstance(node, (LegacyTransaction, Receipt, U256)):
192
    elif isinstance(node, (LegacyTransaction, Receipt, Withdrawal, U256)):
193
        return rlp.encode(node)
194
    elif isinstance(node, Bytes):
195
        return node
196
    else:
187
        return previous_trie.encode_node(node, storage_root)
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
    """
227
    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:
231
    """
232
    Stores an item in a Merkle Trie.
233
234
    This method deletes the key if `value == trie.default`, because the Merkle
235
    Trie represents the default value by omitting it from the trie.
236
237
    Parameters
238
    ----------
239
    trie: `Trie`
240
        Trie to store in.
241
    key : `Bytes`
242
        Key to lookup.
243
    value : `V`
244
        Node to insert at `key`.
245
246
    """
247
    if value == trie.default:
248
        if key in trie._data:
249
            del trie._data[key]
250
    else:
251
        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:
255
    """
256
    Gets an item from the Merkle Trie.
257
258
    This method returns `trie.default` if the key is missing.
259
260
    Parameters
261
    ----------
262
    trie:
263
        Trie to lookup in.
264
    key :
265
        Key to lookup.
266
267
    Returns
268
    -------
269
    node : `V`
270
        Node at `key` in the trie.
271
272
    """
273
    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:
277
    """
278
    Find the longest common prefix of two sequences.
279
    """
280
    for i in range(len(a)):
281
        if i >= len(b) or a[i] != b[i]:
282
            return i
283
    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:
287
    """
288
    Compresses nibble-list into a standard byte array with a flag.
289
290
    A nibble-list is a list of byte values no greater than `15`. The flag is
291
    encoded in high nibble of the highest byte. The flag nibble can be broken
292
    down into two two-bit flags.
293
294
    Highest nibble::
295
296
        +---+---+----------+--------+
297
        | _ | _ | is_leaf | parity |
298
        +---+---+----------+--------+
299
          3   2      1         0
300
301
302
    The lowest bit of the nibble encodes the parity of the length of the
303
    remaining nibbles -- `0` when even and `1` when odd. The second lowest bit
304
    is used to distinguish leaf and extension nodes. The other two bits are not
305
    used.
306
307
    Parameters
308
    ----------
309
    x :
310
        Array of nibbles.
311
    is_leaf :
312
        True if this is part of a leaf node, or false if it is an extension
313
        node.
314
315
    Returns
316
    -------
317
    compressed : `bytearray`
318
        Compact byte array.
319
320
    """
321
    compact = bytearray()
322
323
    if len(x) % 2 == 0:  # ie even length
324
        compact.append(16 * (2 * is_leaf))
325
        for i in range(0, len(x), 2):
326
            compact.append(16 * x[i] + x[i + 1])
327
    else:
328
        compact.append(16 * ((2 * is_leaf) + 1) + x[0])
329
        for i in range(1, len(x), 2):
330
            compact.append(16 * x[i] + x[i + 1])
331
332
    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:
336
    """
337
    Converts a `Bytes` into to a sequence of nibbles (bytes with value < 16).
338
339
    Parameters
340
    ----------
341
    bytes_:
342
        The `Bytes` to convert.
343
344
    Returns
345
    -------
346
    nibble_list : `Bytes`
347
        The `Bytes` in nibble-list format.
348
349
    """
350
    nibble_list = bytearray(2 * len(bytes_))
351
    for byte_index, byte in enumerate(bytes_):
352
        nibble_list[byte_index * 2] = (byte & 0xF0) >> 4
353
        nibble_list[byte_index * 2 + 1] = byte & 0x0F
354
    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]:
361
    """
362
    Prepares the trie for root calculation. Removes values that are empty,
363
    hashes the keys (if `secured == True`) and encodes all the nodes.
364
365
    Parameters
366
    ----------
367
    trie :
368
        The `Trie` to prepare.
369
    get_storage_root :
370
        Function to get the storage root of an account. Needed to encode
371
        `Account` objects.
372
373
    Returns
374
    -------
375
    out : `Mapping[ethereum.base_types.Bytes, Node]`
376
        Object with keys mapped to nibble-byte form.
377
378
    """
379
    mapped: MutableMapping[Bytes, Bytes] = {}
380
381
    for preimage, value in trie._data.items():
382
        if isinstance(value, Account):
383
            assert get_storage_root is not None
384
            address = Address(preimage)
385
            encoded_value = encode_node(value, get_storage_root(address))
386
        else:
387
            encoded_value = encode_node(value)
388
        if encoded_value == b"":
389
            raise AssertionError
390
        key: Bytes
391
        if trie.secured:
392
            # "secure" tries hash keys once before construction
393
            key = keccak256(preimage)
394
        else:
395
            key = preimage
396
        mapped[bytes_to_nibble_list(key)] = encoded_value
397
398
    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:
405
    """
406
    Computes the root of a modified merkle patricia trie (MPT).
407
408
    Parameters
409
    ----------
410
    trie :
411
        `Trie` to get the root of.
412
    get_storage_root :
413
        Function to get the storage root of an account. Needed to encode
414
        `Account` objects.
415
416
417
    Returns
418
    -------
419
    root : `.fork_types.Root`
420
        MPT root of the underlying key-value pairs.
421
422
    """
423
    obj = _prepare_trie(trie, get_storage_root)
424
425
    root_node = encode_internal_node(patricialize(obj, Uint(0)))
426
    if len(rlp.encode(root_node)) < 32:
427
        return keccak256(rlp.encode(root_node))
428
    else:
429
        assert isinstance(root_node, Bytes)
430
        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]:
436
    """
437
    Structural composition function.
438
439
    Used to recursively patricialize and merkleize a dictionary. Includes
440
    memoization of the tree structure and hashes.
441
442
    Parameters
443
    ----------
444
    obj :
445
        Underlying trie key-value pairs, with keys in nibble-list format.
446
    level :
447
        Current trie level.
448
449
    Returns
450
    -------
451
    node : `ethereum.base_types.Bytes`
452
        Root node of `obj`.
453
454
    """
455
    if len(obj) == 0:
456
        return None
457
458
    arbitrary_key = next(iter(obj))
459
460
    # if leaf node
461
    if len(obj) == 1:
462
        leaf = LeafNode(arbitrary_key[level:], obj[arbitrary_key])
463
        return leaf
464
465
    # prepare for extension node check by finding max j such that all keys in
466
    # obj have the same key[i:j]
467
    substring = arbitrary_key[level:]
468
    prefix_length = len(substring)
469
    for key in obj:
470
        prefix_length = min(
471
            prefix_length, common_prefix_length(substring, key[level:])
472
        )
473
474
        # finished searching, found another key at the current level
475
        if prefix_length == 0:
476
            break
477
478
    # if extension node
479
    if prefix_length > 0:
480
        prefix = arbitrary_key[int(level) : int(level) + prefix_length]
481
        return ExtensionNode(
482
            prefix,
483
            encode_internal_node(
484
                patricialize(obj, level + Uint(prefix_length))
485
            ),
486
        )
487
488
    branches: List[MutableMapping[Bytes, Bytes]] = []
489
    for _ in range(16):
490
        branches.append({})
491
    value = b""
492
    for key in obj:
493
        if len(key) == level:
494
            # shouldn't ever have an account or receipt in an internal node
495
            if isinstance(obj[key], (Account, Receipt, Uint)):
496
                raise AssertionError
497
            value = obj[key]
498
        else:
499
            branches[key[level]][key] = obj[key]
500
501
    subnodes = tuple(
502
        encode_internal_node(patricialize(branches[k], level + Uint(1)))
503
        for k in range(16)
504
    )
505
    return BranchNode(
506
        cast(BranchSubnodes, assert_type(subnodes, Tuple[Extended, ...])),
507
        value,
508
    )