EEVM.MPT.Trie (eevm v0.1.0)

Copy Markdown View Source

Ethereum Merkle Patricia Trie (MPT) root computation.

The trie is path-compressed (nibble-by-nibble keys, hex-prefix compact encoding for leaves and extensions) and content-addressed: each node is RLP-encoded, and a child reference is either the raw RLP payload (when byte_size(RLP(node)) < 32) or keccak256(RLP(node)) otherwise.

Implements the recursive patricialize strategy from Ethereum's execution specs, producing roots compatible with geth/revm for the same inputs.

Summary

Types

entry()

Raw trie key bytes and value bytes (nil means deletion in sequential updates).

nibble()

Nibble values used for trie paths.

node_ref()
trie_node()

Functions

root_hash(entries)

Computes the MPT root hash from {key, value} pairs.

secure_root_hash(entries)

Computes the secure-trie MPT root hash.

Types

entry()

@type entry() :: {binary(), binary() | nil}

Raw trie key bytes and value bytes (nil means deletion in sequential updates).

nibble()

@type nibble() :: 0..15

Nibble values used for trie paths.

node_ref()

@type node_ref() :: {:raw, binary()} | binary()

trie_node()

@type trie_node() ::
  nil
  | {:leaf, [nibble()], binary()}
  | {:extension, [nibble()], trie_node()}
  | {:branch, %{optional(nibble()) => trie_node()}, binary() | nil}

Functions

root_hash(entries)

@spec root_hash([entry()]) :: binary()

Computes the MPT root hash from {key, value} pairs.

Keys are inserted as-is (non-secure trie). Entries are applied sequentially; if a key appears multiple times, later values overwrite earlier ones. A nil value deletes the key.

secure_root_hash(entries)

@spec secure_root_hash([entry()]) :: binary()

Computes the secure-trie MPT root hash.

Secure tries pre-hash each key with Keccak-256 before insertion.