ethereum.frontier.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 | Transaction | Receipt | Uint | U256 | None

K

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

V

66
V = TypeVar(
67
    "V",
68
    Optional[Account],
69
    Optional[Bytes],
70
    Bytes,
71
    Optional[Transaction],
72
    Optional[Receipt],
73
    Uint,
74
    U256,
75
)

LeafNode

Leaf node in the Merkle Trie

78
@slotted_freezable
79
@dataclass
class LeafNode:

rest_of_key

83
    rest_of_key: Bytes

value

84
    value: Extended

ExtensionNode

Extension node in the Merkle Trie

87
@slotted_freezable
88
@dataclass
class ExtensionNode:

key_segment

92
    key_segment: Bytes

subnode

93
    subnode: Extended

BranchSubnodes

96
BranchSubnodes = Tuple[
97
    Extended,
98
    Extended,
99
    Extended,
100
    Extended,
101
    Extended,
102
    Extended,
103
    Extended,
104
    Extended,
105
    Extended,
106
    Extended,
107
    Extended,
108
    Extended,
109
    Extended,
110
    Extended,
111
    Extended,
112
    Extended,
113
]

BranchNode

Branch node in the Merkle Trie

116
@slotted_freezable
117
@dataclass
class BranchNode:

subnodes

121
    subnodes: BranchSubnodes

value

122
    value: Extended

InternalNode

125
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.RLP The node encoded as RLP.

def encode_internal_node(node: Optional[InternalNode]) -> Extended:
129
    """
130
    Encodes a Merkle Trie node into its RLP form. The RLP will then be
131
    serialized into a `Bytes` and hashed unless it is less that 32 bytes
132
    when serialized.
133
134
    This function also accepts `None`, representing the absence of a node,
135
    which is encoded to `b""`.
136
137
    Parameters
138
    ----------
139
    node : Optional[InternalNode]
140
        The node to encode.
141
142
    Returns
143
    -------
144
    encoded : `rlp.RLP`
145
        The node encoded as RLP.
146
    """
147
    unencoded: Extended
148
    if node is None:
149
        unencoded = b""
150
    elif isinstance(node, LeafNode):
151
        unencoded = (
152
            nibble_list_to_compact(node.rest_of_key, True),
153
            node.value,
154
        )
155
    elif isinstance(node, ExtensionNode):
156
        unencoded = (
157
            nibble_list_to_compact(node.key_segment, False),
158
            node.subnode,
159
        )
160
    elif isinstance(node, BranchNode):
161
        unencoded = list(node.subnodes) + [node.value]
162
    else:
163
        raise AssertionError(f"Invalid internal node type {type(node)}!")
164
165
    encoded = rlp.encode(unencoded)
166
    if len(encoded) < 32:
167
        return unencoded
168
    else:
169
        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:
173
    """
174
    Encode a Node for storage in the Merkle Trie.
175
176
    Currently mostly an unimplemented stub.
177
    """
178
    if isinstance(node, Account):
179
        assert storage_root is not None
180
        return encode_account(node, storage_root)
181
    elif isinstance(node, (Transaction, Receipt, U256)):
182
        return rlp.encode(node)
183
    elif isinstance(node, Bytes):
184
        return node
185
    else:
186
        raise AssertionError(
187
            f"encoding for {type(node)} is not currently implemented"
188
        )

Trie

The Merkle Trie.

191
@dataclass
class Trie:

secured

197
    secured: bool

default

198
    default: V

_data

199
    _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]:
203
    """
204
    Create a copy of `trie`. Since only frozen objects may be stored in tries,
205
    the contents are reused.
206
207
    Parameters
208
    ----------
209
    trie: `Trie`
210
        Trie to copy.
211
212
    Returns
213
    -------
214
    new_trie : `Trie[K, V]`
215
        A copy of the trie.
216
    """
217
    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:
221
    """
222
    Stores an item in a Merkle Trie.
223
224
    This method deletes the key if `value == trie.default`, because the Merkle
225
    Trie represents the default value by omitting it from the trie.
226
227
    Parameters
228
    ----------
229
    trie: `Trie`
230
        Trie to store in.
231
    key : `Bytes`
232
        Key to lookup.
233
    value : `V`
234
        Node to insert at `key`.
235
    """
236
    if value == trie.default:
237
        if key in trie._data:
238
            del trie._data[key]
239
    else:
240
        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:
244
    """
245
    Gets an item from the Merkle Trie.
246
247
    This method returns `trie.default` if the key is missing.
248
249
    Parameters
250
    ----------
251
    trie:
252
        Trie to lookup in.
253
    key :
254
        Key to lookup.
255
256
    Returns
257
    -------
258
    node : `V`
259
        Node at `key` in the trie.
260
    """
261
    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:
265
    """
266
    Find the longest common prefix of two sequences.
267
    """
268
    for i in range(len(a)):
269
        if i >= len(b) or a[i] != b[i]:
270
            return i
271
    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:
275
    """
276
    Compresses nibble-list into a standard byte array with a flag.
277
278
    A nibble-list is a list of byte values no greater than `15`. The flag is
279
    encoded in high nibble of the highest byte. The flag nibble can be broken
280
    down into two two-bit flags.
281
282
    Highest nibble::
283
284
        +---+---+----------+--------+
285
        | _ | _ | is_leaf | parity |
286
        +---+---+----------+--------+
287
          3   2      1         0
288
289
290
    The lowest bit of the nibble encodes the parity of the length of the
291
    remaining nibbles -- `0` when even and `1` when odd. The second lowest bit
292
    is used to distinguish leaf and extension nodes. The other two bits are not
293
    used.
294
295
    Parameters
296
    ----------
297
    x :
298
        Array of nibbles.
299
    is_leaf :
300
        True if this is part of a leaf node, or false if it is an extension
301
        node.
302
303
    Returns
304
    -------
305
    compressed : `bytearray`
306
        Compact byte array.
307
    """
308
    compact = bytearray()
309
310
    if len(x) % 2 == 0:  # ie even length
311
        compact.append(16 * (2 * is_leaf))
312
        for i in range(0, len(x), 2):
313
            compact.append(16 * x[i] + x[i + 1])
314
    else:
315
        compact.append(16 * ((2 * is_leaf) + 1) + x[0])
316
        for i in range(1, len(x), 2):
317
            compact.append(16 * x[i] + x[i + 1])
318
319
    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:
323
    """
324
    Converts a `Bytes` into to a sequence of nibbles (bytes with value < 16).
325
326
    Parameters
327
    ----------
328
    bytes_:
329
        The `Bytes` to convert.
330
331
    Returns
332
    -------
333
    nibble_list : `Bytes`
334
        The `Bytes` in nibble-list format.
335
    """
336
    nibble_list = bytearray(2 * len(bytes_))
337
    for byte_index, byte in enumerate(bytes_):
338
        nibble_list[byte_index * 2] = (byte & 0xF0) >> 4
339
        nibble_list[byte_index * 2 + 1] = byte & 0x0F
340
    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]:
347
    """
348
    Prepares the trie for root calculation. Removes values that are empty,
349
    hashes the keys (if `secured == True`) and encodes all the nodes.
350
351
    Parameters
352
    ----------
353
    trie :
354
        The `Trie` to prepare.
355
    get_storage_root :
356
        Function to get the storage root of an account. Needed to encode
357
        `Account` objects.
358
359
    Returns
360
    -------
361
    out : `Mapping[ethereum.base_types.Bytes, Node]`
362
        Object with keys mapped to nibble-byte form.
363
    """
364
    mapped: MutableMapping[Bytes, Bytes] = {}
365
366
    for preimage, value in trie._data.items():
367
        if isinstance(value, Account):
368
            assert get_storage_root is not None
369
            address = Address(preimage)
370
            encoded_value = encode_node(value, get_storage_root(address))
371
        else:
372
            encoded_value = encode_node(value)
373
        if encoded_value == b"":
374
            raise AssertionError
375
        key: Bytes
376
        if trie.secured:
377
            # "secure" tries hash keys once before construction
378
            key = keccak256(preimage)
379
        else:
380
            key = preimage
381
        mapped[bytes_to_nibble_list(key)] = encoded_value
382
383
    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:
390
    """
391
    Computes the root of a modified merkle patricia trie (MPT).
392
393
    Parameters
394
    ----------
395
    trie :
396
        `Trie` to get the root of.
397
    get_storage_root :
398
        Function to get the storage root of an account. Needed to encode
399
        `Account` objects.
400
401
402
    Returns
403
    -------
404
    root : `.fork_types.Root`
405
        MPT root of the underlying key-value pairs.
406
    """
407
    obj = _prepare_trie(trie, get_storage_root)
408
409
    root_node = encode_internal_node(patricialize(obj, Uint(0)))
410
    if len(rlp.encode(root_node)) < 32:
411
        return keccak256(rlp.encode(root_node))
412
    else:
413
        assert isinstance(root_node, Bytes)
414
        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]:
420
    """
421
    Structural composition function.
422
423
    Used to recursively patricialize and merkleize a dictionary. Includes
424
    memoization of the tree structure and hashes.
425
426
    Parameters
427
    ----------
428
    obj :
429
        Underlying trie key-value pairs, with keys in nibble-list format.
430
    level :
431
        Current trie level.
432
433
    Returns
434
    -------
435
    node : `ethereum.base_types.Bytes`
436
        Root node of `obj`.
437
    """
438
    if len(obj) == 0:
439
        return None
440
441
    arbitrary_key = next(iter(obj))
442
443
    # if leaf node
444
    if len(obj) == 1:
445
        leaf = LeafNode(arbitrary_key[level:], obj[arbitrary_key])
446
        return leaf
447
448
    # prepare for extension node check by finding max j such that all keys in
449
    # obj have the same key[i:j]
450
    substring = arbitrary_key[level:]
451
    prefix_length = len(substring)
452
    for key in obj:
453
        prefix_length = min(
454
            prefix_length, common_prefix_length(substring, key[level:])
455
        )
456
457
        # finished searching, found another key at the current level
458
        if prefix_length == 0:
459
            break
460
461
    # if extension node
462
    if prefix_length > 0:
463
        prefix = arbitrary_key[int(level) : int(level) + prefix_length]
464
        return ExtensionNode(
465
            prefix,
466
            encode_internal_node(
467
                patricialize(obj, level + Uint(prefix_length))
468
            ),
469
        )
470
471
    branches: List[MutableMapping[Bytes, Bytes]] = []
472
    for _ in range(16):
473
        branches.append({})
474
    value = b""
475
    for key in obj:
476
        if len(key) == level:
477
            # shouldn't ever have an account or receipt in an internal node
478
            if isinstance(obj[key], (Account, Receipt, Uint)):
479
                raise AssertionError
480
            value = obj[key]
481
        else:
482
            branches[key[level]][key] = obj[key]
483
484
    subnodes = tuple(
485
        encode_internal_node(patricialize(branches[k], level + Uint(1)))
486
        for k in range(16)
487
    )
488
    return BranchNode(
489
        cast(BranchSubnodes, assert_type(subnodes, Tuple[Extended, ...])),
490
        value,
491
    )