EEVM.MPT.Trie (eevm v0.1.0)

Ethereum Merkle Patricia Trie (Yellow Paper, Appendix D), as a persistent value that caches each node's hash.

The trie is path-compressed (nibble keys, hex-prefix compact encoding for leaf and extension paths) and content-addressed: each node is RLP-encoded, and a parent refers to a child by its RLP when that is shorter than 32 bytes and by keccak256(RLP(child)) otherwise.

put/3 and delete/2 rebuild only the nodes on the key's path and mark them unhashed; hash/1 hashes exactly those and returns the trie with the hashes filled in. Updating k keys of a hashed trie with n keys therefore costs about k · log₁₆ n Keccak-256 calls instead of a rebuild.

iex> alias EEVM.MPT.Trie
iex> trie = Trie.new() |> Trie.put("doe", "reindeer") |> Trie.put("dog", "puppy")
iex> {root, trie} = trie |> Trie.put("dogglesworth", "cat") |> Trie.hash()
iex> Base.encode16(root, case: :lower)
"8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3"
iex> {^root, _trie} = trie |> Trie.put("do", "verb") |> Trie.delete("do") |> Trie.hash()

Summary

Types

entry()

Raw trie key bytes and value bytes (nil deletes the key).

t()

A trie: nil when empty.

Functions

delete(trie, key)

Removes key. Returns trie itself when key is absent.

empty?(trie)

Returns whether trie has no keys.

hash(trie)

Returns the root hash and the trie with every node's reference computed, hashing only nodes changed since the trie was last hashed.

new()

Returns the empty trie.

put(trie, key, value)

Sets key to value. Returns trie itself when key already holds value.

root_hash(entries)

Computes the root hash of a non-secure trie built from {key, value} pairs, applied in order: a later value for a key replaces an earlier one, and nil deletes the key.

secure_root_hash(entries)

Like root_hash/1, but each key is hashed with Keccak-256 first (a secure trie).