ethereum.byzantium.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

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

Node

63
Node = Union[Account, Bytes, Transaction, Receipt, Uint, U256, None]

K

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

V

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

LeafNode

Leaf node in the Merkle Trie

77
@slotted_freezable
78
@dataclass
class LeafNode:

rest_of_key

82
    rest_of_key: Bytes

value

83
    value: rlp.Extended

ExtensionNode

Extension node in the Merkle Trie

86
@slotted_freezable
87
@dataclass
class ExtensionNode:

key_segment

91
    key_segment: Bytes

subnode

92
    subnode: rlp.Extended

BranchNode

Branch node in the Merkle Trie

95
@slotted_freezable
96
@dataclass
class BranchNode:

subnodes

100
    subnodes: List[rlp.Extended]

value

101
    value: rlp.Extended

InternalNode

104
InternalNode = Union[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]) -> ethereum.rlp.Extended:
108
    """
109
    Encodes a Merkle Trie node into its RLP form. The RLP will then be
110
    serialized into a `Bytes` and hashed unless it is less that 32 bytes
111
    when serialized.
112
113
    This function also accepts `None`, representing the absence of a node,
114
    which is encoded to `b""`.
115
116
    Parameters
117
    ----------
118
    node : Optional[InternalNode]
119
        The node to encode.
120
121
    Returns
122
    -------
123
    encoded : `rlp.RLP`
124
        The node encoded as RLP.
125
    """
126
    unencoded: rlp.Extended
127
    if node is None:
128
        unencoded = b""
129
    elif isinstance(node, LeafNode):
130
        unencoded = (
131
            nibble_list_to_compact(node.rest_of_key, True),
132
            node.value,
133
        )
134
    elif isinstance(node, ExtensionNode):
135
        unencoded = (
136
            nibble_list_to_compact(node.key_segment, False),
137
            node.subnode,
138
        )
139
    elif isinstance(node, BranchNode):
140
        unencoded = node.subnodes + [node.value]
141
    else:
142
        raise AssertionError(f"Invalid internal node type {type(node)}!")
143
144
    encoded = rlp.encode(unencoded)
145
    if len(encoded) < 32:
146
        return unencoded
147
    else:
148
        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:
152
    """
153
    Encode a Node for storage in the Merkle Trie.
154
155
    Currently mostly an unimplemented stub.
156
    """
157
    if isinstance(node, Account):
158
        assert storage_root is not None
159
        return encode_account(node, storage_root)
160
    elif isinstance(node, (Transaction, Receipt, U256)):
161
        return rlp.encode(node)
162
    elif isinstance(node, Bytes):
163
        return node
164
    else:
165
        return previous_trie.encode_node(node, storage_root)

Trie

The Merkle Trie.

168
@dataclass
class Trie:

secured

174
    secured: bool

default

175
    default: V

_data

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