ethereum.homestead.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 = Account | Bytes | Transaction | Receipt | Uint | U256 | None

K

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

V

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

LeafNode

Leaf node in the Merkle Trie

79
@slotted_freezable
80
@dataclass
class LeafNode:

rest_of_key

84
    rest_of_key: Bytes

value

85
    value: Extended

ExtensionNode

Extension node in the Merkle Trie

88
@slotted_freezable
89
@dataclass
class ExtensionNode:

key_segment

93
    key_segment: Bytes

subnode

94
    subnode: Extended

BranchSubnodes

97
BranchSubnodes = Tuple[
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
    Extended,
114
]

BranchNode

Branch node in the Merkle Trie

117
@slotted_freezable
118
@dataclass
class BranchNode:

subnodes

122
    subnodes: BranchSubnodes

value

123
    value: Extended

InternalNode

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

Trie

The Merkle Trie.

190
@dataclass
class Trie:

secured

196
    secured: bool

default

197
    default: V

_data

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