ethereum.frontier.trie

  1"""
  2State Trie
  3^^^^^^^^^^
  4
  5.. contents:: Table of Contents
  6    :backlinks: none
  7    :local:
  8
  9Introduction
 10------------
 11
 12The state trie is the structure responsible for storing
 13`.fork_types.Account` objects.
 14"""
 15
 16import copy
 17from dataclasses import dataclass, field
 18from typing import (
 19    Callable,
 20    Dict,
 21    Generic,
 22    List,
 23    Mapping,
 24    MutableMapping,
 25    Optional,
 26    Sequence,
 27    TypeVar,
 28    Union,
 29    cast,
 30)
 31
 32from ethereum.crypto.hash import keccak256
 33from ethereum.utils.ensure import ensure
 34from ethereum.utils.hexadecimal import hex_to_bytes
 35
 36from .. import rlp
 37from ..base_types import U256, Bytes, Uint, slotted_freezable
 38from .fork_types import (
 39    Account,
 40    Address,
 41    Receipt,
 42    Root,
 43    Transaction,
 44    encode_account,
 45)
 46
 47# note: an empty trie (regardless of whether it is secured) has root:
 48#
 49#   keccak256(RLP(b''))
 50#       ==
 51#   56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421 # noqa: E501,SC10
 52#
 53# also:
 54#
 55#   keccak256(RLP(()))
 56#       ==
 57#   1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347 # noqa: E501,SC10
 58#
 59# which is the sha3Uncles hash in block header with no uncles
 60EMPTY_TRIE_ROOT = Root(
 61    hex_to_bytes(
 62        "56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"
 63    )
 64)
 65
 66Node = Union[Account, Bytes, Transaction, Receipt, Uint, U256, None]
 67K = TypeVar("K", bound=Bytes)
 68V = TypeVar(
 69    "V",
 70    Optional[Account],
 71    Optional[Bytes],
 72    Bytes,
 73    Optional[Transaction],
 74    Optional[Receipt],
 75    Uint,
 76    U256,
 77)
 78
 79
 80@slotted_freezable
 81@dataclass
 82class LeafNode:
 83    """Leaf node in the Merkle Trie"""
 84
 85    rest_of_key: Bytes
 86    value: rlp.RLP
 87
 88
 89@slotted_freezable
 90@dataclass
 91class ExtensionNode:
 92    """Extension node in the Merkle Trie"""
 93
 94    key_segment: Bytes
 95    subnode: rlp.RLP
 96
 97
 98@slotted_freezable
 99@dataclass
100class BranchNode:
101    """Branch node in the Merkle Trie"""
102
103    subnodes: List[rlp.RLP]
104    value: rlp.RLP
105
106
107InternalNode = Union[LeafNode, ExtensionNode, BranchNode]
108
109
110def encode_internal_node(node: Optional[InternalNode]) -> rlp.RLP:
111    """
112    Encodes a Merkle Trie node into its RLP form. The RLP will then be
113    serialized into a `Bytes` and hashed unless it is less that 32 bytes
114    when serialized.
115
116    This function also accepts `None`, representing the absence of a node,
117    which is encoded to `b""`.
118
119    Parameters
120    ----------
121    node : Optional[InternalNode]
122        The node to encode.
123
124    Returns
125    -------
126    encoded : `rlp.RLP`
127        The node encoded as RLP.
128    """
129    unencoded: rlp.RLP
130    if node is None:
131        unencoded = b""
132    elif isinstance(node, LeafNode):
133        unencoded = (
134            nibble_list_to_compact(node.rest_of_key, True),
135            node.value,
136        )
137    elif isinstance(node, ExtensionNode):
138        unencoded = (
139            nibble_list_to_compact(node.key_segment, False),
140            node.subnode,
141        )
142    elif isinstance(node, BranchNode):
143        unencoded = node.subnodes + [node.value]
144    else:
145        raise AssertionError(f"Invalid internal node type {type(node)}!")
146
147    encoded = rlp.encode(unencoded)
148    if len(encoded) < 32:
149        return unencoded
150    else:
151        return keccak256(encoded)
152
153
154def encode_node(node: Node, storage_root: Optional[Bytes] = None) -> Bytes:
155    """
156    Encode a Node for storage in the Merkle Trie.
157
158    Currently mostly an unimplemented stub.
159    """
160    if isinstance(node, Account):
161        assert storage_root is not None
162        return encode_account(node, storage_root)
163    elif isinstance(node, (Transaction, Receipt, U256)):
164        return rlp.encode(cast(rlp.RLP, node))
165    elif isinstance(node, Bytes):
166        return node
167    else:
168        raise AssertionError(
169            f"encoding for {type(node)} is not currently implemented"
170        )
171
172
173@dataclass
174class Trie(Generic[K, V]):
175    """
176    The Merkle Trie.
177    """
178
179    secured: bool
180    default: V
181    _data: Dict[K, V] = field(default_factory=dict)
182
183
184def copy_trie(trie: Trie[K, V]) -> Trie[K, V]:
185    """
186    Create a copy of `trie`. Since only frozen objects may be stored in tries,
187    the contents are reused.
188
189    Parameters
190    ----------
191    trie: `Trie`
192        Trie to copy.
193
194    Returns
195    -------
196    new_trie : `Trie[K, V]`
197        A copy of the trie.
198    """
199    return Trie(trie.secured, trie.default, copy.copy(trie._data))
200
201
202def trie_set(trie: Trie[K, V], key: K, value: V) -> None:
203    """
204    Stores an item in a Merkle Trie.
205
206    This method deletes the key if `value == trie.default`, because the Merkle
207    Trie represents the default value by omitting it from the trie.
208
209    Parameters
210    ----------
211    trie: `Trie`
212        Trie to store in.
213    key : `Bytes`
214        Key to lookup.
215    value : `V`
216        Node to insert at `key`.
217    """
218    if value == trie.default:
219        if key in trie._data:
220            del trie._data[key]
221    else:
222        trie._data[key] = value
223
224
225def trie_get(trie: Trie[K, V], key: K) -> V:
226    """
227    Gets an item from the Merkle Trie.
228
229    This method returns `trie.default` if the key is missing.
230
231    Parameters
232    ----------
233    trie:
234        Trie to lookup in.
235    key :
236        Key to lookup.
237
238    Returns
239    -------
240    node : `V`
241        Node at `key` in the trie.
242    """
243    return trie._data.get(key, trie.default)
244
245
246def common_prefix_length(a: Sequence, b: Sequence) -> int:
247    """
248    Find the longest common prefix of two sequences.
249    """
250    for i in range(len(a)):
251        if i >= len(b) or a[i] != b[i]:
252            return i
253    return len(a)
254
255
256def nibble_list_to_compact(x: Bytes, is_leaf: bool) -> Bytes:
257    """
258    Compresses nibble-list into a standard byte array with a flag.
259
260    A nibble-list is a list of byte values no greater than `15`. The flag is
261    encoded in high nibble of the highest byte. The flag nibble can be broken
262    down into two two-bit flags.
263
264    Highest nibble::
265
266        +---+---+----------+--------+
267        | _ | _ | is_leaf | parity |
268        +---+---+----------+--------+
269          3   2      1         0
270
271
272    The lowest bit of the nibble encodes the parity of the length of the
273    remaining nibbles -- `0` when even and `1` when odd. The second lowest bit
274    is used to distinguish leaf and extension nodes. The other two bits are not
275    used.
276
277    Parameters
278    ----------
279    x :
280        Array of nibbles.
281    is_leaf :
282        True if this is part of a leaf node, or false if it is an extension
283        node.
284
285    Returns
286    -------
287    compressed : `bytearray`
288        Compact byte array.
289    """
290    compact = bytearray()
291
292    if len(x) % 2 == 0:  # ie even length
293        compact.append(16 * (2 * is_leaf))
294        for i in range(0, len(x), 2):
295            compact.append(16 * x[i] + x[i + 1])
296    else:
297        compact.append(16 * ((2 * is_leaf) + 1) + x[0])
298        for i in range(1, len(x), 2):
299            compact.append(16 * x[i] + x[i + 1])
300
301    return Bytes(compact)
302
303
304def bytes_to_nibble_list(bytes_: Bytes) -> Bytes:
305    """
306    Converts a `Bytes` into to a sequence of nibbles (bytes with value < 16).
307
308    Parameters
309    ----------
310    bytes_:
311        The `Bytes` to convert.
312
313    Returns
314    -------
315    nibble_list : `Bytes`
316        The `Bytes` in nibble-list format.
317    """
318    nibble_list = bytearray(2 * len(bytes_))
319    for byte_index, byte in enumerate(bytes_):
320        nibble_list[byte_index * 2] = (byte & 0xF0) >> 4
321        nibble_list[byte_index * 2 + 1] = byte & 0x0F
322    return Bytes(nibble_list)
323
324
325def _prepare_trie(
326    trie: Trie[K, V],
327    get_storage_root: Optional[Callable[[Address], Root]] = None,
328) -> Mapping[Bytes, Bytes]:
329    """
330    Prepares the trie for root calculation. Removes values that are empty,
331    hashes the keys (if `secured == True`) and encodes all the nodes.
332
333    Parameters
334    ----------
335    trie :
336        The `Trie` to prepare.
337    get_storage_root :
338        Function to get the storage root of an account. Needed to encode
339        `Account` objects.
340
341    Returns
342    -------
343    out : `Mapping[ethereum.base_types.Bytes, Node]`
344        Object with keys mapped to nibble-byte form.
345    """
346    mapped: MutableMapping[Bytes, Bytes] = {}
347
348    for preimage, value in trie._data.items():
349        if isinstance(value, Account):
350            assert get_storage_root is not None
351            address = Address(preimage)
352            encoded_value = encode_node(value, get_storage_root(address))
353        else:
354            encoded_value = encode_node(value)
355        # Empty values are represented by their absence
356        ensure(encoded_value != b"", AssertionError)
357        key: Bytes
358        if trie.secured:
359            # "secure" tries hash keys once before construction
360            key = keccak256(preimage)
361        else:
362            key = preimage
363        mapped[bytes_to_nibble_list(key)] = encoded_value
364
365    return mapped
366
367
368def root(
369    trie: Trie[K, V],
370    get_storage_root: Optional[Callable[[Address], Root]] = None,
371) -> Root:
372    """
373    Computes the root of a modified merkle patricia trie (MPT).
374
375    Parameters
376    ----------
377    trie :
378        `Trie` to get the root of.
379    get_storage_root :
380        Function to get the storage root of an account. Needed to encode
381        `Account` objects.
382
383
384    Returns
385    -------
386    root : `.fork_types.Root`
387        MPT root of the underlying key-value pairs.
388    """
389    obj = _prepare_trie(trie, get_storage_root)
390
391    root_node = encode_internal_node(patricialize(obj, Uint(0)))
392    if len(rlp.encode(root_node)) < 32:
393        return keccak256(rlp.encode(root_node))
394    else:
395        assert isinstance(root_node, Bytes)
396        return Root(root_node)
397
398
399def patricialize(
400    obj: Mapping[Bytes, Bytes], level: Uint
401) -> Optional[InternalNode]:
402    """
403    Structural composition function.
404
405    Used to recursively patricialize and merkleize a dictionary. Includes
406    memoization of the tree structure and hashes.
407
408    Parameters
409    ----------
410    obj :
411        Underlying trie key-value pairs, with keys in nibble-list format.
412    level :
413        Current trie level.
414
415    Returns
416    -------
417    node : `ethereum.base_types.Bytes`
418        Root node of `obj`.
419    """
420    if len(obj) == 0:
421        return None
422
423    arbitrary_key = next(iter(obj))
424
425    # if leaf node
426    if len(obj) == 1:
427        leaf = LeafNode(arbitrary_key[level:], obj[arbitrary_key])
428        return leaf
429
430    # prepare for extension node check by finding max j such that all keys in
431    # obj have the same key[i:j]
432    substring = arbitrary_key[level:]
433    prefix_length = len(substring)
434    for key in obj:
435        prefix_length = min(
436            prefix_length, common_prefix_length(substring, key[level:])
437        )
438
439        # finished searching, found another key at the current level
440        if prefix_length == 0:
441            break
442
443    # if extension node
444    if prefix_length > 0:
445        prefix = arbitrary_key[level : level + prefix_length]
446        return ExtensionNode(
447            prefix,
448            encode_internal_node(patricialize(obj, level + prefix_length)),
449        )
450
451    branches: List[MutableMapping[Bytes, Bytes]] = []
452    for _ in range(16):
453        branches.append({})
454    value = b""
455    for key in obj:
456        if len(key) == level:
457            # shouldn't ever have an account or receipt in an internal node
458            if isinstance(obj[key], (Account, Receipt, Uint)):
459                raise AssertionError
460            value = obj[key]
461        else:
462            branches[key[level]][key] = obj[key]
463
464    return BranchNode(
465        [
466            encode_internal_node(patricialize(branches[k], level + 1))
467            for k in range(16)
468        ],
469        value,
470    )