# `EEVM.MPT.Trie`
[🔗](https://github.com/mw2000/eevm/blob/v0.1.0/lib/eevm/mpt/trie.ex#L1)

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()

# `entry`

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

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

# `t`

```elixir
@opaque t()
```

A trie: `nil` when empty.

# `delete`

```elixir
@spec delete(t(), binary()) :: t()
```

Removes `key`. Returns `trie` itself when `key` is absent.

# `empty?`

```elixir
@spec empty?(t()) :: boolean()
```

Returns whether `trie` has no keys.

# `hash`

```elixir
@spec hash(t()) :: {<<_::256>>, t()}
```

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

# `new`

```elixir
@spec new() :: t()
```

Returns the empty trie.

# `put`

```elixir
@spec put(t(), binary(), binary()) :: t()
```

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

# `root_hash`

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

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`

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

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

---

*Consult [api-reference.md](api-reference.md) for complete listing*