Posts tagged "trie":

28 Jul 2024

Ethereum Merkle Patricia Trie

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

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

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

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.

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.

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.

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.

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.

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

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.

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

Essentially is a key-value mapping; it provides Get, Put and Del functions.
Ethereum has 3 MPTs: transaction trie; receipt trie and state trie, each trie root hash is included in the block header.
- transactionTrie: all transactions included in the block.
  - The keys are the RLP encodings of an unsigned integer starting from 0.
  - The values are the RLP encodings of the transaction.
- stateTrie: all account states in the network.
- receiptTrie: the outcomes of all transaction executions in the block, e.g., gas used, transaction status.

Allows to verify data integrity with the Hash function to compute the Merkle root hash.
Allows to verify the inclusion of a key-value pair without the access to the entire key-value pairs.
- A full node provide a merkle proof Proof for a key-value pair (e.g., an account and its balance).
- A light node can verify a proof only against the root hash with VerifyProf(rootHash, key, proof); if the proof does not match the hash (e.g., the balance mismatches), an error is thrown.
Why would a light node trust the root hash: it trusts the consensus mechanism, e.g., other benign full nodes verify the hash, act honestly is more profitable.

Proof: the path from the root to the leaf node.
Verification: start from the root, decode the node to match the nibbles until find the node that matches all the remaining nibbles; if not found, the proof is invalid.