ethereum.trie¶
State Trie¶
Table of Contents
Introduction¶
The state trie is the structure responsible for storing eth1spec.eth_types.Account objects.
Module Contents¶
Functions¶
Compresses nibble-list into a standard byte array with a flag. |
|
Maps all compact keys to nibble-list format. Optionally hashes the keys. |
|
RLP encode leaf nodes of the Trie. |
|
Computes the root of a modified merkle patricia trie (MPT). |
|
Internal nodes less than 32 bytes in length are represented by themselves |
|
Structural composition function. |
Attributes¶
Module Details¶
debug¶
- ethereum.trie.debug = False¶
verbose¶
- ethereum.trie.verbose = False¶
Node¶
- ethereum.trie.Node¶
nibble_list_to_compact¶
- ethereum.trie.nibble_list_to_compact(x: ethereum.base_types.Bytes, terminal: bool) → bytearray¶
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:
+---+---+----------+--------+ | _ | _ | terminal | 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 encodes whether the key maps to a terminal node. The other two bits are not used.
- Parameters
x – Array of nibbles.
terminal – Flag denoting if the key points to a terminal (leaf) node.
- Returns
compressed – Compact byte array.
- Return type
bytearray
def nibble_list_to_compact(x: Bytes, terminal: bool) -> bytearray:
compact = bytearray()
if len(x) % 2 == 0: # ie even length
compact.append(16 * (2 * terminal))
for i in range(0, len(x), 2):
compact.append(16 * x[i] + x[i + 1])
else:
compact.append(16 * ((2 * terminal) + 1) + x[0])
for i in range(1, len(x), 2):
compact.append(16 * x[i] + x[i + 1])
return compact
map_keys¶
- ethereum.trie.map_keys(obj: Mapping[ethereum.base_types.Bytes, Node], secured: bool = True) → Mapping[ethereum.base_types.Bytes, Node]¶
Maps all compact keys to nibble-list format. Optionally hashes the keys.
- Parameters
obj – Underlying trie key-value pairs.
secured – Denotes whether the keys should be hashed. Defaults to true.
- Returns
out – Object with keys mapped to nibble-byte form.
- Return type
Mapping[eth1spec.base_types.Bytes, Node]
def map_keys(
obj: Mapping[Bytes, Node], secured: bool = True
) -> Mapping[Bytes, Node]:
mapped: MutableMapping[Bytes, Node] = {}
# skip empty values, these are defined to be omitted from the trie
skip: Set[Bytes] = set()
for (k, v) in obj.items():
if v == b"":
skip.add(k)
for (preimage, value) in obj.items():
if preimage in skip:
continue
# "secure" tries hash keys once before construction
key = crypto.keccak256(preimage) if secured else preimage
nibble_list = bytearray(2 * len(key))
for i in range(2 * len(key)):
byte_idx = i // 2
if i % 2 == 0:
# get upper nibble
nibble_list[i] = (key[byte_idx] & 0xF0) >> 4
else:
# get lower nibble
nibble_list[i] = key[byte_idx] & 0x0F
mapped[Bytes(nibble_list)] = value
return mapped
encode_leaf¶
- ethereum.trie.encode_leaf(leaf: Node) → ethereum.rlp.RLP¶
RLP encode leaf nodes of the Trie. Currently leaf nodes can be Account, Transaction, Receipt dataclasses.
def encode_leaf(leaf: Node) -> rlp.RLP:
if isinstance(leaf, (Account, Transaction, Receipt)):
return rlp.encode(cast(rlp.RLP, leaf))
return leaf
root¶
- ethereum.trie.root(obj: Mapping[ethereum.base_types.Bytes, Node]) → ethereum.eth_types.Root¶
Computes the root of a modified merkle patricia trie (MPT).
- Parameters
obj – Underlying trie key-value pairs.
- Returns
root – MPT root of the underlying key-value pairs.
- Return type
eth1spec.eth_types.Root
def root(obj: Mapping[Bytes, Node]) -> Root:
root_node = patricialize(obj, Uint(0))
return crypto.keccak256(rlp.encode(root_node))
node_cap¶
- ethereum.trie.node_cap(obj: Mapping[ethereum.base_types.Bytes, Node], i: ethereum.base_types.Uint) → ethereum.rlp.RLP¶
Internal nodes less than 32 bytes in length are represented by themselves directly. Larger nodes are hashed once to cap their size to 32 bytes.
- Parameters
obj – Underlying trie key-value pairs.
i – Current trie level.
- Returns
hash – Internal node commitment.
- Return type
eth1spec.eth_types.Hash32
def node_cap(obj: Mapping[Bytes, Node], i: Uint) -> rlp.RLP:
if len(obj) == 0:
return b""
node = patricialize(obj, i)
encoded = rlp.encode(node)
if len(encoded) < 32:
return node
return crypto.keccak256(encoded)
patricialize¶
- ethereum.trie.patricialize(obj: Mapping[ethereum.base_types.Bytes, Node], i: ethereum.base_types.Uint) → ethereum.rlp.RLP¶
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.
i – Current trie level.
- Returns
node – Root node of obj.
- Return type
eth1spec.base_types.Bytes
def patricialize(obj: Mapping[Bytes, Node], i: Uint) -> rlp.RLP:
if len(obj) == 0:
# note: empty storage tree has merkle root:
#
# crypto.keccak256(RLP(b''))
# ==
# 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421 # noqa: E501,SC100
#
# also:
#
# crypto.keccak256(RLP(()))
# ==
# 1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347 # noqa: E501,SC100
#
# which is the sha3Uncles hash in block header for no uncles
return b""
key = next(iter(obj)) # get first key, will reuse below
# if leaf node
if len(obj) == 1:
leaf = obj[key]
node: rlp.RLP = encode_leaf(leaf)
return (nibble_list_to_compact(key[i:], True), node)
# prepare for extension node check by finding max j such that all keys in
# obj have the same key[i:j]
substring = copy(key)
j = Uint(len(substring))
for key in obj:
j = min(j, Uint(len(key)))
substring = substring[:j]
for x in range(i, j):
# mismatch -- reduce j to best previous value
if key[x] != substring[x]:
j = Uint(x)
substring = substring[:j]
break
# finished searching, found another key at the current level
if i == j:
break
# if extension node
if i != j:
child = node_cap(obj, j)
return (nibble_list_to_compact(key[i:j], False), child)
# otherwise branch node
def build_branch(j: int) -> rlp.RLP:
branch = {}
skip = {}
for (k, v) in obj.items():
if len(k) <= i:
skip[k] = True
if k in skip:
continue
if k[i] == j:
branch[k] = v
return node_cap(branch, i + 1)
value: Bytes = b""
for key in obj:
if len(key) == i:
# shouldn't ever have an account or receipt in an internal node
if isinstance(obj[key], (Account, Receipt, Uint)):
raise TypeError()
value = cast(Bytes, obj[key])
break
return [build_branch(k) for k in range(16)] + [value]