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
    )