Merkle Patricia Trees: Ethereum State Trie

Understanding and implementing Merkle Patricia Trees used in Ethereum for efficient state storage.

Advanced⏱️ 55 min📚 Prerequisites: 2

Merkle Patricia Trees: Ethereum State Trie

Merkle Patricia Trees (MPT) combine Merkle trees with Patricia (trie) structures for efficient state storage.

Why MPT?

Ethereum uses MPT for:

State Trie: Account balances, nonces, storage
Transaction Trie: Transactions in a block
Receipt Trie: Transaction receipts

Key Features

Trie Structure

A trie (prefix tree) stores keys by their prefixes:

        Root
       /    \
    0x0    0x1
   /  \    /  \
 0x00 0x01 0x10 0x11

Node Types

Extension Node: Shared prefix
Branch Node: 16 children (hex digits)
Leaf Node: Final value

Implementation


RUST
enum MPTNode {
    Extension { shared_nibbles: Vec<u8>, next: Box<MPTNode> },
    Branch { children: [Option<Box<MPTNode>>; 16], value: Option<Vec<u8>> },
    Leaf { remaining_nibbles: Vec<u8>, value: Vec<u8> },
}

struct MerklePatriciaTree {
    root: Option<Box<MPTNode>>,
}

impl MerklePatriciaTree {
    fn new() -> Self {
        MerklePatriciaTree { root: None }
    }
    
    fn insert(&mut self, key: &[u8], value: Vec<u8>) {
        // Insert key-value pair
        // Navigate trie, create nodes as needed
    }
    
    fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
        // Retrieve value by key
        // Navigate trie following key path
    }
    
    fn root_hash(&self) -> Vec<u8> {
        // Calculate Merkle root hash
    }
}

Ethereum State

Ethereum stores:

Account State: Balance, nonce, code hash, storage root
Storage: Contract storage (key-value pairs)
Code: Smart contract bytecode

Benefits

Efficient Lookups: O(log n) for state queries
Merkle Proofs: Prove state without full data
Incremental Updates: Only update changed paths
Compact Storage: Shared prefixes reduce size

Real-World Usage

Ethereum: State, transactions, receipts
Light Clients: Verify state with proofs
State Sync: Sync only changed state

Optimization

Caching: Cache frequently accessed nodes
Pruning: Remove old state
Compression: Compress node data

Code Examples

Simple Trie Structure

Basic trie implementation

RUST

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<u8, Box<TrieNode>>,
    value: Option<Vec<u8>>,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            value: None,
        }
    }
    
    fn insert(&mut self, key: &[u8], value: Vec<u8>) {
        if key.is_empty() {
            self.value = Some(value);
            return;
        }
        
        let first = key[0];
        let child = self.children
            .entry(first)
            .or_insert_with(|| Box::new(TrieNode::new()));
        
        child.insert(&key[1..], value);
    }
    
    fn get(&self, key: &[u8]) -> Option<&Vec<u8>> {
        if key.is_empty() {
            return self.value.as_ref();
        }
        
        let first = key[0];
        if let Some(child) = self.children.get(&first) {
            child.get(&key[1..])
        } else {
            None
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie { root: TrieNode::new() }
    }
    
    fn insert(&mut self, key: &[u8], value: Vec<u8>) {
        self.root.insert(key, value);
    }
    
    fn get(&self, key: &[u8]) -> Option<&Vec<u8>> {
        self.root.get(key)
    }
}

fn main() {
    let mut trie = Trie::new();
    
    // Insert key-value pairs
    trie.insert(b"0x1234", b"value1".to_vec());
    trie.insert(b"0x5678", b"value2".to_vec());
    
    // Retrieve values
    if let Some(value) = trie.get(b"0x1234") {
        println!("Found: {:?}", value);
    }
}

Explanation:

A trie (prefix tree) stores keys by their prefixes. Each node can have multiple children. This enables efficient lookups and shared prefixes reduce storage. Ethereum uses a more complex version (MPT) with Merkle hashing.

Ethereum State Concept

Conceptual Ethereum state storage

RUST

use std::collections::HashMap;

struct AccountState {
    balance: u64,
    nonce: u64,
    code_hash: Vec<u8>,
    storage_root: Vec<u8>, // Root of storage trie
}

struct EthereumState {
    accounts: HashMap<Vec<u8>, AccountState>, // Address -> State
    state_root: Vec<u8>, // Root of state trie
}

impl EthereumState {
    fn new() -> Self {
        EthereumState {
            accounts: HashMap::new(),
            state_root: vec![0; 32],
        }
    }
    
    fn set_balance(&mut self, address: &[u8], balance: u64) {
        let account = self.accounts
            .entry(address.to_vec())
            .or_insert_with(|| AccountState {
                balance: 0,
                nonce: 0,
                code_hash: vec![],
                storage_root: vec![],
            });
        
        account.balance = balance;
        // In real implementation: update state root
    }
    
    fn get_balance(&self, address: &[u8]) -> u64 {
        self.accounts
            .get(address)
            .map(|acc| acc.balance)
            .unwrap_or(0)
    }
    
    fn increment_nonce(&mut self, address: &[u8]) {
        let account = self.accounts
            .entry(address.to_vec())
            .or_insert_with(|| AccountState {
                balance: 0,
                nonce: 0,
                code_hash: vec![],
                storage_root: vec![],
            });
        
        account.nonce += 1;
    }
}

fn main() {
    let mut state = EthereumState::new();
    
    let address = b"0xAlice";
    
    // Set balance
    state.set_balance(address, 1000);
    println!("Balance: {}", state.get_balance(address));
    
    // Increment nonce (transaction)
    state.increment_nonce(address);
    
    println!("State root represents all account states");
    println!("Can prove any account state with Merkle proof!");
}

Explanation:

Ethereum stores all account states in a Merkle Patricia Tree. The state root is a single hash representing all accounts. You can prove any account's state with a Merkle proof without downloading the entire state.

Exercises

Simple Trie

Create a simple trie that stores key-value pairs!

Hard

Starter Code:

RUST

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<u8, Box<TrieNode>>,
    value: Option<String>,
}

fn main() {
    // Create trie
    // Insert values
    // Retrieve values
}

Previous Lesson

← 32 merkle trees

Next Lesson

33 cryptographic hashes →