Designing Blockchain #4: Merkle Trees and State Verification

Intro

In the previous article, we secured our Fleming blockchain by implementing cryptographic signatures and wallets, ensuring that only legitimate account owners can authorise transactions. However, if you remember from the second article, we left a critical architectural problem unresolved: storing the full state in every block is extremely wasteful and doesn't scale well.

Let's understand the magnitude of this problem. In our current implementation, each block contains a complete copy of the entire blockchain state — a HashMap<Address, u64> where Address is a String ("0x" prefix + 40 hex characters = 42 bytes) and balance is a u64 (8 bytes). That's 50 bytes per account just for the data itself, not counting HashMap's internal overhead. If our blockchain has 1,000,000 accounts, each block stores at least 50 MB of state data. Now imagine we have 10,000 blocks in our chain. That's 500 GB just for storing redundant state copies! And the problem compounds exponentially as both the number of accounts and blocks grow.

This memory inefficiency makes our blockchain impractical for any real-world application. We need a way to represent the entire state compactly while still being able to verify individual account balances. The solution comes from cryptographic data structures called Merkle Trees.

In this article, we'll explore how Merkle Trees work, discover why a simple binary tree isn't enough for our needs, and implement a data structure that allows us to represent millions of accounts with just a single 32-byte hash. We'll also see how to cryptographically prove that a specific account exists in the state without revealing the entire state data. By the end, instead of storing megabytes of redundant state in each block, we'll store just 32 bytes.

Tree Data Structures

Before diving into Merkle Trees, let's establish what tree data structures are and why they're useful for blockchain.

A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has a root node at the top, and every node can have zero or more child nodes. Nodes without children are called leaf nodes. Trees enable efficient O(log N) operations — with 1,000,000 elements, you might only need to traverse 20 levels instead of checking all million elements linearly.

A trie (pronounced "try", from retrieval) is a specialized type of tree where the path from root to a node represents a key. The key difference from regular trees: in a trie, keys are broken down into individual components (characters, nibbles, or bits), and nodes share common prefixes.

Here's a simple example storing words "cat", "car", and "dog":

    root
   /    \
  c      d
  |      |
  a      o
 / \     |
t   r    g

Notice how "cat" and "car" share the path root→c→a, saving space. This prefix-sharing property makes tries perfect for blockchain addresses.

For blockchain, we use hexadecimal tries where each level of the tree represents one hex character (0-9, a-f). Since our addresses are hex strings like "0x3a7f...", we can naturally traverse the trie by following the hex characters:

Address: 0x3a7f...

     root
    / | \
   3  a  f  ...
   |
   a
   |
   7
   |
   f

Each node can have up to 16 children (one for each hex digit). This structure is perfect for organizing blockchain addresses efficiently.

Merkle Trees

A Merkle Tree (also known as a hash tree) is a tree data structure where every leaf node contains a hash of some data, and every non-leaf node contains a hash of its child nodes. This structure was invented by Ralph Merkle in 1979 and has become fundamental to blockchain technology.

Let's build up the concept step by step. Imagine we have four accounts in our blockchain state:

Account A: balance = 100
Account B: balance = 50
Account C: balance = 75
Account D: balance = 200

Instead of storing this data directly, we create a binary tree of hashes:

             ROOT HASH
            /          \
           /            \
       H(AB)            H(CD)
      /    \           /    \
     /      \         /      \
  H(A)    H(B)     H(C)    H(D)
   |       |        |        |
A:100    B:50     C:75    D:200

At the bottom level (leaf nodes), we hash each account's data. For example, H(A) = SHA256("A" + "100"). Then we move up the tree, combining pairs of hashes: H(AB) = SHA256(H(A) + H(B)). We continue this process until we reach a single hash at the top — the Merkle Root.

The Merkle Root is a single 32-byte hash that uniquely represents all the data in the tree. If any account balance changes — even by a single coin — the root hash changes completely. This is the cryptographic property we need: a compact fingerprint of the entire state.

Now here's the powerful part: we can prove that a specific account exists in the state without revealing all the other accounts. This is called a Merkle Proof.

Merkle Proof

Let's say someone asks: "Does account B with balance 50 exist in this state?" Instead of showing them all four accounts, we provide a Merkle Proof — just the minimum set of hashes needed to verify the data.

For account B, the proof would be:

Proof = {
  leaf_hash: H(B),
  siblings: [H(A), H(CD)]
}

The verifier can then:

1. Start with H(B) — the hash of account B's data
2. Combine with H(A) to get H(AB)
3. Combine H(AB) with H(CD) to get the ROOT HASH
4. Compare this computed root with the root stored in the block header

If they match, the proof is valid — account B definitely exists in this state. If the account data was tampered with, or if it doesn't exist in the state, the computed root wouldn't match.

The beauty is that the proof size grows logarithmically with the number of accounts. For 1,000,000 accounts in a binary tree, you only need about 20 hashes (log₂ 1,000,000 ≈ 20) to prove any single account — that's just 640 bytes instead of 50 MB!

Merkle Tree vs Merkle Trie

Before we continue, it's important to clarify the terminology, as these terms are often used interchangeably but refer to different structures:

A Merkle Tree is a general hash tree where the structure can be arbitrary. The classic example is Bitcoin's binary Merkle Tree — transactions are grouped pairwise, hashed together, and combined bottom-up until reaching a single root. The tree structure doesn't encode any information about the data itself; it's just an efficient way to hash a list of items.

A Merkle Trie (or Merkle Patricia Trie) is a specific type of Merkle Tree where the path from root to leaf encodes the key. In a trie, you traverse the tree by following the components of the key (bits, hex characters, etc.) to find the value. This makes it perfect for key-value storage like account balances, where the address itself determines the path through the tree.

The key difference: in a Merkle Tree, the structure is determined by how you group the data. In a Merkle Trie, the structure is determined by the keys themselves.

Why Merkle Trees for Blockchain

Merkle Trees (and Merkle Tries) solve several critical problems for blockchain:

Compact state representation — Instead of storing the full state (50+ MB) in each block, we store just the Merkle Root (32 bytes). This makes blocks dramatically smaller and the blockchain more scalable.

Efficient verification — Anyone can verify that a specific account exists in the state with a small proof, without needing to download and validate the entire state. This enables light clients — nodes that don't store the full blockchain but can still verify data.

Tamper detection — Any change to any account instantly changes the root hash. This makes it cryptographically impossible to modify historical state without detection, as the root hash is included in the block hash.

Deterministic — For the same set of accounts and balances, the Merkle Root is always the same. Different nodes can independently compute the state and verify they're in sync by comparing just 32 bytes.

Merkle Trees in Production Blockchains

Different blockchains use Merkle Trees in different ways, depending on their architecture and requirements:

Bitcoin uses a simple binary Merkle Tree to organize transactions within each block. All transactions in a block are hashed pairwise and combined bottom-up until reaching a single Merkle Root, which is included in the block header. This enables Simplified Payment Verification (SPV) — light clients can verify that a transaction exists in a block by downloading just the block headers and a Merkle Proof, without downloading all transactions. Bitcoin doesn't use Merkle Trees for state because it follows the UTXO model, where state is simply the set of unspent outputs.

Ethereum takes a more sophisticated approach with three separate Patricia Merkle Tries for each block: a State Trie (account balances and contract storage), a Transaction Trie (transactions in the block), and a Receipt Trie (transaction execution results). The Patricia Trie is a modified hexadecimal trie with several optimizations — it uses extension nodes to compress long paths without branching, and branch nodes that can have up to 16 children (one for each hex digit 0-f). These optimizations dramatically reduce tree depth compared to a naive implementation. The structure allows efficient incremental updates: when an account balance changes, only the path from that leaf to the root needs to be recalculated, not the entire tree. The State Trie enables light clients to verify account balances without storing Ethereum's entire state (over 200 million accounts).

Solana uses Merkle Trees for its accounts database. The blockchain maintains a Merkle Tree of all account states, and the root is included in each block. Solana's high-performance architecture processes thousands of transactions per second, and Merkle Trees enable efficient state verification without sacrificing speed. Light clients can query account data and verify it against the Merkle Root without trusting full nodes.

Cardano also employs Merkle Trees for transaction verification within blocks, similar to Bitcoin. This allows light wallets to verify transactions efficiently without downloading the entire blockchain.

For our Fleming blockchain, we'll implement a hexadecimal Merkle Trie similar to Ethereum's approach — using hex characters from our addresses to traverse the trie. Since the path through the tree is determined by the address itself (each hex character decides which of the 16 children to follow), this is a trie structure, not a simple tree. This gives us a good balance between implementation simplicity and real-world applicability.

Sparse Merkle Trie

Now that we understand Merkle Trees and Merkle Tries, let's address a critical challenge: how do we handle dynamic state updates efficiently?

Imagine we implement a naive hexadecimal Merkle Trie for our blockchain state. Our addresses are 40 hex characters long, which means a full trie would have a depth of 40 levels. Here's the problem: if we only have 3 accounts in our blockchain, we'd still need to maintain the entire tree structure with potentially millions of empty branches. Even worse, every time we add a new account, we'd need to traverse up to 40 levels to insert it and recalculate hashes along the path.

This is where the Sparse Merkle Trie comes in. The key insight is that most of the trie is empty — with millions of possible addresses but only thousands or millions actually in use, the vast majority of the tree nodes don't exist. A Sparse Merkle Trie takes advantage of this sparseness.

How Sparse Merkle Tries Work

A Sparse Merkle Trie has a fixed depth determined by the key length. For our 40-character hex addresses, the tree has exactly 40 levels. However, instead of actually creating all possible nodes, we only store the nodes that exist along paths to actual data.

Here's the clever part: we use a default hash for empty branches. If a subtree contains no data, we don't store it at all — we just use a pre-computed empty hash. When we need to compute a node's hash and one or more of its children are empty, we use the default hash for those children.

Let's visualize this with a simple example. Suppose we have only two accounts with addresses starting with "0x3..." and "0xf...":

           root
          /    \
         /      \
      [3]       [f]
       |         |
     actual    actual
      data      data

All other children (0,1,2,4,5,6,7,8,9,a,b,c,d,e) use default empty hash

Why Sparse Merkle Tries Solve Our Problem

Efficient storage — We only store nodes that lead to actual accounts. If we have 1,000 accounts in a tree with 40 levels, we store roughly 1,000 × 40 = 40,000 nodes maximum, not the theoretical 16^40 nodes of a full trie.

Incremental updates — When we add a new account or update a balance, we only need to update the nodes along one path from the leaf to the root (40 nodes). We don't need to rebuild the entire tree. This is O(depth) = O(40) for our addresses — a constant-time operation regardless of how many accounts exist.

Deterministic root — For any given set of accounts and balances, the root hash is always the same. Empty parts of the tree always hash to the default value, so two nodes with identical state will compute identical roots.

Efficient proofs — To prove an account exists, we provide the hashes along the path from leaf to root (40 hashes). To prove an account doesn't exist, we can show that a path leads to an empty node (default hash).

Our Implementation Approach

For our Fleming blockchain, we'll implement a hexadecimal Sparse Merkle Trie with these characteristics:

• Fixed depth of 40 levels (one per hex character in our addresses)
• 16 children per node (one for each hex digit 0-f)
• Default hash for empty nodes (pre-computed to avoid redundant calculations)
• HashMap-based storage (only storing non-empty nodes)

This approach gives us a good balance: simple enough to understand and implement, but efficient enough to handle millions of accounts with incremental updates.

Let's implement it.

Implementation

Before implementing the Sparse Merkle Trie, we need to refactor our hash types. Currently, we have BlockHash as a wrapper, but we'll be using 32-byte hashes in multiple places: blocks, Merkle Tree nodes, and state roots. Instead of having different hash types for different purposes, let's introduce a single consistent hash type.

Since we're using SHA-256 everywhere (which produces 256-bit = 32-byte hashes), let's rename BlockHash to Hash256:

// core/hash256.rs
use std::fmt::{Debug, Formatter};

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Hash256(pub [u8; 32]);

impl Debug for Hash256 {
    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
        write!(f, "\"0x{}\"", hex::encode(self.0))
    }
}

Now we can update our Block structure to use Hash256 instead of BlockHash:

// core/block.rs
use crate::core::Hash256;

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,
    transactions: Vec<Transaction>,
    state: State,
    previous_hash: Hash256,  // was BlockHash
    hash: Hash256,           // was BlockHash
    timestamp: u64,
}

This refactoring gives us:

• Consistency — all 32-byte hashes use the same type across the codebase
• Type safety — Hash256 is a distinct type, not just an alias
• Reusability — we can now use Hash256 for Merkle Trie hashes without creating yet another hash type

With this foundation in place, we're ready to implement the Sparse Merkle Trie.

Let's extend our existing core/state.rs module with the Sparse Merkle Trie implementation. First, add the new data structures:

use crate::core::Hash256;
use crate::core::address::Address;
use std::collections::HashMap;

const TREE_DEPTH: usize = 40;
const HEX_RADIX: usize = 16;

pub type State = HashMap<Address, u64>;

struct TrieNode {
    hash: Hash256,
    value: Option<u64>, // just for leafs
}

pub struct SparseMerkleTrie {
    nodes: HashMap<String, TrieNode>, // path -> node
}

The TrieNode stores the hash of a node and optionally a balance value (only for leaf nodes). The SparseMerkleTrie uses a HashMap to store nodes indexed by their path — for example, "3a7f" represents the node at depth 4 reached by following hex characters 3, a, 7, and f from the root. We use a HashMap-based approach rather than recursive node structures to avoid Rust's ownership complexities with Box<T> and self-referential types.

Now let's implement the helper functions for hashing:

impl SparseMerkleTrie {
    fn hash_leaf(balance: Option<u64>) -> Hash256 {
        let mut hasher = Sha256::new();
        if let Some(balance) = balance {
            hasher.update(balance.to_le_bytes());
        }
        Hash256(hasher.finalize().into())
    }

    fn hash_internal_node(children: &[Hash256; HEX_RADIX]) -> Hash256 {
        let mut hasher = Sha256::new();
        for child_hash in children {
            hasher.update(child_hash.0);
        }
        Hash256(hasher.finalize().into())
    }

    fn address_to_path(address: &Address) -> &str {
        address
            .as_str()
            .strip_prefix("0x")
            .unwrap_or(address.as_str())
    }
}

The hash_leaf function hashes a balance value (or an empty value for non-existent accounts). The hash_internal_node concatenates the hashes of all 16 children and hashes the result. The address_to_path function strips the "0x" prefix from addresses to get the path through the trie.

Next, implement the constructor and basic operations:

pub fn new() -> Self {
    SparseMerkleTrie {
        nodes: HashMap::new(),
    }
}

pub fn get(&self, address: &Address) -> Option<u64> {
    let path = Self::address_to_path(address);
    self.nodes.get(path).and_then(|node| node.value)
}

pub fn insert(&mut self, address: &Address, balance: u64) {
    let path = Self::address_to_path(address);

    // Create leaf node with balance
    let leaf_hash = Self::hash_leaf(Some(balance));
    self.nodes.insert(
        path.to_string(),
        TrieNode {
            hash: leaf_hash,
            value: Some(balance),
        },
    );

    // Update hashes of all parent nodes up to root
    self.update_path(path);
}

The get method simply looks up the node in the HashMap and returns its balance. The insert method creates or updates a leaf node with the account balance, then updates all ancestor hashes up to the root.

Now implement the core logic for updating hashes along a path:

fn update_path(&mut self, path: &str) {
    // Update hashes from leaf to root
    // Walk backwards: parent_of_leaf -> parent_of_parent -> ... -> root
    for i in (0..path.len()).rev() {
        let parent_path = &path[..i]; // trim last character
        let parent_hash = self.compute_node_hash(parent_path);

        // Create/update parent node
        self.nodes.insert(
            parent_path.to_string(),
            TrieNode {
                hash: parent_hash,
                value: None, // only leaves have values
            },
        );
    }
}

fn compute_node_hash(&self, path: &str) -> Hash256 {
    let mut children_hashes = [Hash256([0u8; 32]); HEX_RADIX];

    // Check all 16 possible children (0-f)
    for (i, hex_char) in "0123456789abcdef".chars().enumerate() {
        let child_path = format!("{}{}", path, hex_char);

        // If a child exists, use its hash; otherwise use zero hash
        children_hashes[i] = if let Some(child_node) = self.nodes.get(&child_path) {
            child_node.hash
        } else {
            Hash256([0u8; 32]) // empty branch
        };
    }

    // Hash all 16 children hashes together
    Self::hash_internal_node(&children_hashes)
}

pub fn get_root_hash(&self) -> Hash256 {
    // Root has empty path
    self.compute_node_hash("")
}

The update_path method walks from the leaf up to the root, recalculating hashes for each ancestor node. The compute_node_hash method computes a node's hash by gathering the hashes of all 16 possible children — using the stored hash if the child exists, or a zero hash if it doesn't. The get_root_hash method returns the Merkle Root by computing the hash of the root node (empty path).

Finally, let's update the Block structure to use the Merkle Root instead of storing the full state:

// core/block.rs

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,                    // just a serial number of block
    transactions: Vec<Transaction>, // array of transactions
    state_root: Hash256,            // Merkle root of the state trie (32 bytes)
    previous_hash: Hash256,         // SHA-256 of previous block
    hash: Hash256,                  // SHA-256 of current block
    timestamp: u64,                 // block creation timestamp
}

Now update the block hash calculation to include the state root:

fn calculate_hash(&self) -> Hash256 {
    let mut hasher = Sha256::new();
    hasher.update(self.number.to_le_bytes());
    hasher.update(&self.previous_hash.0);
    hasher.update(self.timestamp.to_le_bytes());

    for tx in &self.transactions {
        hasher.update(tx.as_bytes());
    }

    hasher.update(&self.state_root.0);

    Hash256(hasher.finalize().into())
}

And update the blockchain to maintain the trie and compute state roots:

// core/blockchain.rs

pub struct Blockchain {
    chain: Vec<Block>, // chain of blocks
    state: SparseMerkleTrie, // global state trie
}

pub fn append_block(&mut self, transactions: Vec<Transaction>) {
    let previous_block = self.chain.last().unwrap();
    let previous_hash = previous_block.hash().clone();
    let block_number = previous_block.number() + 1;

    // apply all transactions to the state
    for tx in &transactions {
        // check transaction
        if !tx.is_valid() {
            panic!("Invalid transaction");
        }

        // check balances
        let from_balance = self.state.get(&tx.from).unwrap_or(0);
        if from_balance < tx.amount {
            // will handle correctly later
            panic!("Insufficient balance!");
        }

        let to_balance = self.state.get(&tx.to).unwrap_or(0);

        self.state.insert(&tx.from, from_balance - tx.amount);
        self.state.insert(&tx.to, to_balance + tx.amount);
    }

    let state_root = self.state.get_root_hash();
    let new_block = Block::new(block_number, transactions, state_root, previous_hash);
    println!("Appending block: {:#?}", new_block);
    self.chain.push(new_block);
}

Instead of storing the full state in each block (which was 50+ MB for 1,000,000 accounts), we now store only the 32-byte Merkle Root. The blockchain maintains a single SparseMerkleTrie that gets updated with each block, and only the root hash is included in the block. This dramatically reduces storage requirements while maintaining cryptographic verifiability of the entire state.

Now let's implement Merkle Proofs to verify account balances without storing the full state. We'll need this later when we add peer-to-peer connections — a light client can request a proof from a full node and verify it against the state root in the block header.

First, define the proof structure:

// core/state.rs

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct MerkleProof {
    pub siblings: Vec<Hash256>,
}

impl SparseMerkleTrie {
    pub fn get_proof(&self, address: &Address) -> Option<MerkleProof> {
        let path = Self::address_to_path(address);

        // Check if account exists
        if !self.nodes.contains_key(path) {
            return None;
        }

        let mut siblings = Vec::new();

        // Collect sibling hashes along the path
        for i in (0..path.len()).rev() {
            let parent_path = &path[..i];
            let current_char = path.chars().nth(i).unwrap();

            // For each level, we need the hashes of all 15 siblings
            // (all children except the one we're traversing)
            for (j, hex_char) in "0123456789abcdef".chars().enumerate() {
                if hex_char != current_char {
                    let sibling_path = format!("{}{}", parent_path, hex_char);
                    let sibling_hash = if let Some(node) = self.nodes.get(&sibling_path) {
                        node.hash
                    } else {
                        Hash256([0u8; 32])
                    };
                    siblings.push(sibling_hash);
                }
            }
        }

        Some(MerkleProof { siblings })
    }

    pub fn verify_proof(
        address: &Address,
        balance: u64,
        proof: &MerkleProof,
        expected_root: &Hash256,
    ) -> bool {
        let path = Self::address_to_path(address);
        let mut current_hash = Self::hash_leaf(Some(balance));
        let mut sibling_idx = 0;

        // Rebuild the path from leaf to root using the proof
        for i in (0..path.len()).rev() {
            let current_char = path.chars().nth(i).unwrap();
            let char_idx = "0123456789abcdef".find(current_char).unwrap();

            let mut children_hashes = [Hash256([0u8; 32]); HEX_RADIX];

            // Place current hash at correct position
            children_hashes[char_idx] = current_hash;

            // Fill in siblings from proof
            for (j, _) in "0123456789abcdef".chars().enumerate() {
                if j != char_idx {
                    children_hashes[j] = proof.siblings[sibling_idx];
                    sibling_idx += 1;
                }
            }

            current_hash = Self::hash_internal_node(&children_hashes);
        }

        // Compare computed root with expected root
        current_hash.0 == expected_root.0
    }
}

The get_proof method collects all sibling hashes along the path from the leaf to the root. For our hexadecimal trie, each level contributes 15 sibling hashes (all 16 children except the one we traverse). The verify_proof method reconstructs the root hash using only the address, balance, and proof — if the computed root matches the expected root, the proof is valid. This allows light clients to verify account balances with just ~19 KB of data instead of downloading the entire state.

We've now transformed our blockchain to use Merkle Trie for state management. However, this refactoring requires updating all existing tests — changing assertions from checking HashMap state to using the get() method, updating genesis block initialization, and adjusting validation logic. Rather than showing dozens of test updates in this article, you can find the complete test suite in the GitHub. The tests verify trie operations, proof generation and verification, and ensure backward compatibility with previous functionality.

Conclusion

In this article, we've solved the memory inefficiency problem by implementing a Sparse Merkle Trie for state management in our Fleming blockchain. We explored how Merkle Trees work, understood the difference between Merkle Trees and Merkle Tries, and implemented a hexadecimal Sparse Merkle Trie that efficiently handles millions of accounts.

We successfully implemented:

• Hash type refactoring with Hash256 for consistency across the codebase
• Sparse Merkle Trie with HashMap-based storage for efficient sparse data handling
• Hashing functions for leaf nodes and internal nodes
• Incremental hash updates from leaf to root
• Merkle Proof generation and verification for light client support
• Block structure update to store only the 32-byte Merkle Root instead of the full state

The impact is dramatic: instead of storing 50+ MB of state data in each block for 1,000,000 accounts, we now store just 32 bytes. The Merkle Root provides cryptographic verification of the entire state — any change to any account balance instantly changes the root hash, making tampering detectable. With Merkle Proofs, light clients can verify account balances using only ~19 KB of data instead of downloading the entire blockchain state, enabling efficient verification without trusting full nodes.

However, our blockchain still stores everything in memory, which means we lose all data when the program stops. For a real-world blockchain, we need persistent storage that survives restarts and can handle massive amounts of data efficiently.

In the next article, we'll tackle persistent storage by integrating Rocks DB — a high-performance embedded database used by production blockchains. We'll explore how to store blocks and state on disk, implement efficient queries, and ensure data integrity across restarts. This will transform our blockchain from a learning prototype into something that could actually handle real-world workloads.

As usual, all the source code from the article can be found here.

Stay tuned!