Ethereum Merkle Patricia Trie

This is a personal note of Ethereum Merkle Patricia Trie (MPT), resources are from:

• Simplified Go implementation of Ethereum MPT (2022)
• Blockchain trees Youtube (2022)
• Claude.ai

1. Blockchain fundamentals

1.1. RLP (Recursive Length Prefix)

• A serialization method to encode arbitrarily nested arrays of binary data.
• RLP provides a simple (e.g., no type), space-efficient and deterministic encoding.

1.2. Merkle tree

• Used in Bitcoin to simplify proof of inclusion (PoI) of a transaction.
• If one computes the hash of an array of \(N\):
  • Construction complexity: \(O(n)\) time and space.
  • PoI complexity: \(O(n)\) time and space (needs all other items).

1.2.1. Complexity for \(N\) items.

• Construction: \(O(2n)\) time and space.
• PoI complexity:
  • \(O(logN)\) space: PoI requires one hash from each level from the leaf to the root (the Merkle tree is binary).
  • \(O(logN)\) time: \(O(logN)\) to collect all hashes, and \(O(logN)\) to generate the proof.

1.3. Patricia tree

• Trie: a data structure that stores key-value pair in a key’s prefix tree.
• Patricia tree: compress trie by merging nodes on the same path.
• The structure the Patricia tree is independent of the item insertion order.
• The time complexity for add, query and deletion is \(O(K)\), where \(K\) is the key length.

1.4. Merkle Patricia Tree (MPT)

• MPT is a hex-ary Merkle tree with an additional DB for hash lookup.
• There are 4 types of nodes:
  • Empty node: the null node the root points to when first creating the tree.
  • Leaf node: stores the real data, e.g., account balance.
  • Branch node: stores the pointers to at most 16 other nodes, e.g., they have the common prefix (nibbles) before and differ at the current nibble (4 bit,0-f).
  • Extension node: record the compressed common prefix for a branch node.
• Each pointer in the tree is the hash value of the child node; the real node data is stored in a separate DB that maps from a node hash to its data.
• If the child node is small, the parent node could also directly store the node data rather than the hash pointer.
• In practical implementation, the entire tree is typically stored in a KV DB, and each node is stored with its hash as the key.

1.4.1. Prefix byte

• Identify both the node type and the parity of the stored nibbles.
• Leaf node: 2 if the key-end has even number of nibbles, e.g., the compressed ending of an account; 3X if the number is odd (so the last 4-bit is stored as X in the prefix).
• Extension: 0 if the shared nibbles has even number; 1X if has odd number.

1.4.2. Complexity for \(N\) items and key length \(K\)

• Construction:
  • Time: worst \(O(NK)\); average: \(O(Nlog_{16}N)\).
  • Space: \(O(N)\).
• Indexing (e.g., query an account balance):
  • Time: tree traversal worst \(O(K)\), average \(O(log_{16}N)\); each traversal equals a DB query.
• PoI: \(O(16log_{16}N)\) time and space.
  • Calculating the hash of a branch node requires the hash of all 16 child nodes.

1.5. Rollup state tree

• Rollup has a higher performance requirement for PoI.
• Separate the indexing and PoI with a sorted key-value arrays and a (binary) Merkle tree.
  • MPT: {Addr0: State0, Addr1: State1,...}.
  • Rollup: map: {Addr0: Id0, Addr1: Id1,...} + array: [(Addr0, State0), (Addr1, State1),...].
• When a client wants to query an account, it first gets the key id from the map, then get the state from the array.
• When a node wants to generate PoI, it follows the merkle path and collect hashes (more hashes than MPT).

1.6. PoI for Verkle tree (see MegaETH post for details)

• Stateless light nodes get a witness along with the new block, the witness is a PoI for the state change in the block.
• Light nodes download related state information, e.g., changed account from other full nodes, or from the portal network.

1.7. Polynomial/KZG commitment

• In MPT, PoI for a branch node requires the hash values of all branches.
• KZG commitment reduce the proof size by adding a polynomial formula \(f(x)\) in the branch node, and each branch has a point \((x, y)\) such that \(y = f(x)\).
• In this way, the proof no longer requires hashes of other branches, the proof space complexity \(O(log_{16}N)\) (no 16 coefficient).