Chenyo's org-static-blog

Posts tagged "trie":

28 Jul 2024

Ethereum Merkle Patricia Trie

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

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.
merkle-tree.jpg
Figure 1: Bitcoin Merkle Tree (source)

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.
525px-Patricia_trie.svg.png
Figure 2: Patricia Tree (source)

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.
4_add_4th_tx_kv.png
Figure 3: MPT DB storage (source)

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.
YZGxe.png
Figure 4: Merkle Patricia Tree (source)

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

2. Ethereum MPT data structure

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

3. Ethereum MPT Functionality

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

4. Proof of inclusion

  • 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.
Tags: evm trie
Other posts