"In a standard database, data is stored in a flat Hash Map. In a Trie, data is stored in the Structure itself. The Key is not just a label; it is a map of the territory."

Series Navigation:

Introduction
Part I: The Alphabet (Nibbles)
Part II: The Four Horsemen (Nodes) <- You are here
Part III: The Serialization Trap (RLP)
Part IV: The Surgical Strike (Insertion)
Part V: The Witness (Merkle Proofs)

PART II: THE FOUR HORSEMEN

Chapter 4: The Architecture of Recursion (The Node Enum)

In Part I, we built the alphabet. We learned how to speak in Nibbles (u4) and how to serialize them using Hex-Prefix encoding.
Now, we must use that alphabet to write words.

In a standard database (like Redis), data is often stored in a flat Hash Map. Key -> Value.
In a Trie, data is stored in the Structure itself. The Key is not just a label; it is a map of the territory. It tells you exactly which turns to take to find the Value.

To represent this in Rust, we need a data structure that can point to itself. We need Recursion.

1. The Rust Memory Model Problem

If you are coming from Python or JavaScript, defining a tree node is trivial:

class Node {
    constructor() {
        this.children = []; // Just put more Nodes in here
    }
}

In those languages, everything is implicitly a reference (a pointer) on the Heap.

In Rust, however, data is stored on the Stack by default. The compiler needs to know exactly how many bytes a type takes up at compile time.
If we try to define a naive recursive Enum:

// This will not compile!
enum Node {
    Branch { children: [Node; 16] }
}

The compiler will scream at you: "Recursive type has infinite size."
If a Branch contains 16 Nodes, and each of those Nodes contains 16 Nodes... how big is the parent? It is infinitely large. You cannot put infinity on the Stack.

To solve this, we must introduce Indirection.
We use Box<Node>.
A Box is a smart pointer. It stays on the Stack, but it points to a memory address on the Heap where the actual data lives. A pointer has a known, fixed size (8 bytes on a 64-bit system).
Now the compiler is happy.

2. The Four Horsemen

The Ethereum Yellow Paper defines exactly four types of nodes. We will map these directly to a Rust Enum.

#[derive(Clone, Debug, Serialize, Deserialize)]
pub enum Node {
    /// 1. The Void
    Null,

    /// 2. The Destination
    Leaf {
        key: Vec<u8>,
        value: Vec<u8>,
    },

    /// 3. The Shortcut (Patricia Optimization)
    Extension {
        prefix: Vec<u8>,
        next: Box<Node>,
    },

    /// 4. The Fork (Radix Structure)
    Branch {
        children: [Box<Node>; 16],
        value: Option<Vec<u8>>,
    },
}

Let's dissect each one. They each serve a specific mechanical purpose in the machine.

3. The Branch Node (The Fork)

This is the heavy lifter. The "Hexary" nature of the Trie lives here.
When a path diverges, for example, we have keys starting with 0xA and 0xB, then we need a Branch node to direct traffic.

It contains an array of 16 pointers (indices 0 through F).
But wait, why does it have a value field?
value: Option<Vec<u8>>

This handles the edge case where a Key is a prefix of another Key.

Key 1: 0xABC -> Value "Dog"
Key 2: 0xABCD -> Value "Cat"

When we traverse A -> B -> C, we land on a Branch node.

At index D, we point to the "Cat" leaf.
But "Dog" stops right here. It doesn't go any further.
So, the Branch node itself needs a slot to hold the value "Dog". In the Yellow Paper, this is often the 17th item.

4. The Leaf Node (The Destination)

Eventually, a path ends.
A Leaf Node tells us: "You have arrived."
It contains:

Key: The remaining nibbles that we haven't traversed yet (stored as Vec<u8>).
Value: The actual RLP-encoded data (e.g., the Account state).

Why store the full key?
Imagine we store the key 0xABCDEF.
We might traverse A -> B -> C (Branch Nodes).
Instead of creating 3 more Branch nodes for D -> E -> F (which is wasteful if no other keys exist there), we just create a Leaf that stores the remaining nibbles [D, E, F] in its key field, along with the value.

5. The Extension Node (The Optimization)

This is the "Patricia" in "Merkle Patricia Trie".
Patricia stands for Practical Algorithm to Retrieve Information Coded in Alphanumeric. (Clearly, computer scientists in the 80s loved acronyms).

The goal is Path Compression.
Suppose we only have one key in the entire database: 0x123456789.
If we used only Branch nodes, we would need 9 layers of empty branches, each one pointing to the next.
Root[1] -> Branch[2] -> Branch[3] -> ...

This is terrible for disk space and lookup speed.
Instead, we compress the shared path into a single node.
We create an Extension Node:

prefix: 0x12345678
next: Pointer to Leaf 9.

We have collapsed 8 levels of depth into 1.
This optimization is why Ethereum is able to be efficient despite having 160-bit keys.

6. The Null Node (The Void)

Finally, we need to represent Nothing.
In Rust, we often use Option<Node>. But explicit is better than implicit.
The Null variant represents an empty branch slot. When we hash a Null node, it serializes to an empty byte string (or the hash of an empty string), which is mathematically distinct from "Zero".

7. The Implementation Detail: Fixed Arrays

Take a closer look at the Branch definition:
children: [Box<Node>; 16]

Initializing this in Rust requires careful handling because Box<Node> doesn't implement Copy. In the actual implementation, branch nodes are created inline where needed:

let mut children: [Box<Node>; 16] = [
    Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null),
    Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null),
    Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null),
    Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null), Box::new(Node::Null),
];

This explicit initialization ensures each box is a distinct allocation.

8. Summary

We have defined the anatomy of our state machine.

Branch: Handles divergence.
Extension: Handles path compression.
Leaf: Handles data storage.
Null: Handles emptiness.

But this structure is still just a Rust Enum in memory. It is ephemeral. If we turn off the computer, it vanishes.
To make it persistent (and to make it verifiable), we need to turn this Enum into a stream of Bytes. We need to serialize it.

[change this]
All of this will be covered in Part III: The Serialization Trap, where will encounter RLP, and the single most frustrating rule in the entire Ethereum specification: The Inline Node Optimization.

Chapter 5: The Logic of Lookup (Reading the Mind)

In the previous chapter, we defined the State. We built the Node Enum, the skeleton that holds the Ethereum universe.
But a database is useless if it is just a static statue. We need to interact with it. We need to query it.

The most fundamental operation in any Key-Value store is GET.
GET(key) -> value.

In a Hash Map (like std::collections::HashMap), this is a mathematical operation:

Hash the Key -> 0x123...
Modulo bucket size -> Index 5.
Jump to Index 5.

It is O(1). Constant time. It feels like teleportation.

In a Trie, GET is not teleportation. It is a Journey.
We do not jump to the destination. We must walk the path, step by step, node by node. If the key is 0xABC, we must visit node A, then node B, then node C.

This sounds slower (and theoretically it is O(k) where k is key length), but it gives us something a Hash Map cannot: Proof of Absence.
If I walk the path 0xAB and find that the pointer to C is Null, I know with cryptographic certainty that the key does not exist. In a Hash Map, I just know I didn't find it. In a Merkle Trie, I can prove it isn't there.

1. The Cursor Concept

To implement get in Rust, we need to think about Nibble Consumption.
We start with the full key (e.g., [0xA, 0xB, 0xC, 0xD]).
As we descend the tree, we "consume" nibbles.

Root (Branch): We look at the first nibble (0xA). We follow index 10.
Step 2: We are now looking for [0xB, 0xC, 0xD].
Step 3: We consume 0xB. We follow index 11.
Step 4: We are now looking for [0xC, 0xD].

We need a recursive helper function that takes the Current Node and the Remaining Path.

fn get_at(node: &Node, path: &Nibbles) -> Option<Vec<u8>>

Let's break down the logic for each of our Four Horsemen.

2. The Branch Traversal (The Switchboard)

The Branch node is the easiest to understand but the most powerful. It is a 16-way switch.

Scenario:

Current Node: Branch
Remaining Path: [0xA, 0xB, 0xC]

Logic:

Is the path empty?

Yes: This means we have arrived at the destination, but the destination is a Branch node (this happens when one key is a prefix of another). Return node.value.
No: Look at the first nibble (0xA).

Use 0xA (10) as an index into the children array.
Recurse: get_at(children[10], path[1..]).

The Rust Implementation:

match node {
    Node::Branch { children, value } => {
        if nibbles.is_empty() {
            // We matched the full key, and it ended on a branch.
            // Return the value stored in the branch (if any).
            return value.clone();
        }

        // Extract the first nibble to decide which child to visit
        let idx = nibbles[0] as usize;
        
        // Recurse into the child, slicing the path (consuming 1 nibble)
        Self::get_at(&children[idx], &nibbles[1..])
    }
}

3. The Extension Traversal (The Gatekeeper)

This is where it gets tricky.
An Extension node claims to cover a chunk of the path.

Extension Prefix: [0xA, 0xB]
Target Path: [0xA, 0xB, 0xC, 0xD]

Logic:
We must verify that the Extension Prefix matches the Start of our Target Path exactly.
If the Extension says "I handle 0xAB", but we are looking for 0xAC..., then this is a dead end. The key does not exist.

Compare prefix vs path.
Partial Match: If they don't match fully, return None (Key not found).
Full Match: If they match, we have successfully skipped 2 steps!
Recurse: get_at(next_node, path[prefix_len..]).

The Rust Implementation:

    Node::Extension { prefix, next } => {
        // Essential: Check if we have enough nibbles
        if nibbles.len() < prefix.len() {
            return None;
        }
        
        // Check if the prefix matches the start of our path
        if &nibbles[..prefix.len()] == prefix.as_slice() {
            // Match successful. We "fast travel" over the prefix.
            // Consume the matching nibbles and recurse.
            Self::get_at(next, &nibbles[prefix.len()..])
        } else {
            None
        }
    }

4. The Leaf Traversal (The Final Exam)

We have reached a Leaf. This is the end of the line.
But we aren't done yet. We have to verify the Key Remainder.

Scenario:

Leaf Key Remainder: [0xC, 0xD]
Target Path: [0xC, 0xD]

Logic:
Does the Leaf's remainder match our target exactly?

Yes: Return Some(value).
No: Return None.

Wait, why would it "No"?
Imagine the Trie contains dog (64 6f 67).
We search for do (64 6f).
We arrive at the Leaf.

Leaf says: "I handle 67 (g)".
We say: "I have nothing left."
Mismatch. do is not in the database (only dog is).

The Rust Implementation:

    Node::Leaf { key, value } => {
        // We must match the key exactly.
        if key == nibbles {
            return Some(value.clone());
        }
        None
    }

5. The Null Traversal (The Void)

This is the easiest one.
If we hit a Null node, it means the branch is empty. The key doesn't exist.

    Node::Null => None,

6. Putting It All Together

Here is the complete, recursive get logic. Notice how clean it is. The complexity of the Trie is hidden behind the recursive dispatch.

impl EthTrie {
    /// Public API: Get a value by raw key (bytes)
    pub fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
        // 1. Convert Bytes -> Nibbles (The Translation Layer)
        let nibbles = Nibbles::from_raw(key, false);
        let nibbles_vec = nibbles.as_slice().to_vec();
        
        // 2. Start Recursion from Root
        Self::get_at(&self.root, &nibbles_vec)
    }

    /// Internal Recursive Helper
    fn get_at(node: &Node, nibbles: &[u8]) -> Option<Vec<u8>> {
        match node {
            Node::Null => None,
            
            Node::Leaf { key, value } => {
                // Exact match check
                if key == nibbles {
                    Some(value.clone())
                } else {
                    None
                }
            }
            
            Node::Branch { children, value } => {
                if nibbles.is_empty() {
                    return value.clone();
                }
                
                let idx = nibbles[0] as usize;
                // Recurse into child[idx], consuming 1 nibble
                Self::get_at(&children[idx], &nibbles[1..])
            }
            
            Node::Extension { prefix, next } => {
                // Prefix match check
                if nibbles.len() >= prefix.len() 
                    && &nibbles[..prefix.len()] == prefix.as_slice() 
                {
                    // Recurse into next, consuming prefix.len() nibbles
                    Self::get_at(next, &nibbles[prefix.len()..])
                } else {
                    None
                }
            }
        }
    }
}

7. The Complexity Analysis

Why did we do all this?
Let's look at the performance characteristics.

In a Binary Trie, for a 32-byte key (64 nibbles), we perform 64 recursions.
In our Hexary Trie with Extension Nodes, the average case is significantly better.

If we look up a key that shares a long prefix with neighbors (common in Ethereum, as addresses are random hashes but storage keys often share prefixes), we might traverse:

Extension Node (consumes 10 nibbles).
Branch Node (consumes 1 nibble).
Leaf Node (consumes 53 nibbles).

Total steps: 3.
We found a 256-bit key in 3 hops.
This is the power of the Patricia Optimization. We compress the empty space between the forks.

However, reading is the easy part. The Trie is static.
The real nightmare begins when we want to Write.
When we insert a key, we break these Extension nodes. We have to shatter them, inject branches, and rewire the pointers. And we have to do it without invalidating the cryptographic hashes of the siblings.

But before we can insert, we must solve one final problem.
To hash a node, we must serialize it.
And to serialize it, we must face the RLP Beast.

In Part III, we will enter the Serialization Trap.

Chapter 6: The Cryptographic Link (The Merkle Property)

We have built a tree. We have branches, extensions, and leaves. We can walk down the path from Root to Leaf.
But right now, this is just a Radix Trie. It is efficient, but it is not secure.

If I am a malicious actor running a node, and you ask me for the balance of Account X, I could just change the value in my Leaf node from 100 to 0.
In a standard tree, there is no way for you to know I tampered with it.

To fix this, we need to turn this Radix Trie into a Merkle Trie.
We need to make the data Self-Verifying.

1. The Pointer Problem

In C++ or Rust, a "Pointer" is a memory address. 0x7ffee4....
It points to a physical location in RAM.
If I change the data at that location, the pointer remains valid, but the data is different.

In Ethereum, we do not use memory addresses as pointers.
We use Hashes.

Parent: BranchNode
Child Index 0: Hash(ChildNode)

The "Pointer" to the child is the Keccak-256 Hash of the child's serialized data.

This creates a cryptographic dependency chain:

If I change the Leaf Value from 100 to 0...
The Leaf's Hash changes.
The Parent Branch stores the Leaf's Hash. Since the Leaf's Hash changed, the Parent's Data has changed.
The Parent's Hash changes.
This ripples all the way up to the Root.

The State Root is simply the hash of the top-most node.
This single 32-byte string (0x5f2a...) is a unique fingerprint of the entire 180-million-account database.
If a single byte changes anywhere in the petabytes of history, the Root Hash changes.

2. The Hash Function (Keccak-256)

Ethereum uses Keccak-256.
Note: This is NOT standard SHA-3.
SHA-3 was finalized by NIST in 2015. Keccak was the original submission. NIST changed the padding parameters slightly for the final standard.
Ethereum was built before the standard was final, so it uses the original Keccak.

If you use a standard sha3 library in Rust, you will get the wrong hashes.
We must use the tiny-keccak crate with the keccak feature (not sha3).

use tiny_keccak::{Hasher, Keccak};

pub fn keccak256(data: &[u8]) -> [u8; 32] {
    let mut hasher = Keccak::v256();
    let mut output = [0u8; 32];
    hasher.update(data);
    hasher.finalize(&mut output);
    output
}

3. The Recursive Hash Calculation

This brings us to the most computationally expensive part of the EVM.
To calculate the Root Hash, we cannot just hash the top node.
We need the hash of its children.
To get the hash of the children, we need the hash of their children.

We must calculate the hashes Bottom-Up.

But wait. We defined our Node enum using Box<Node>.

enum Node {
    Branch { children: [Box<Node>; 16], ... }
}

Our Rust structure uses memory pointers, not hash pointers.
This is strictly for Performance.
If we recalculated the hash every time we touched a node, the database would be incredibly slow.
We keep the tree in memory using Box (RAM pointers) for fast traversal.

We only calculate the Hashes when we need to:

Commit the state to disk.
Generate the State Root for a block header.
Produce a Merkle Proof.

4. The Trie Wrapper

This completes our data structure definition. We wrap the Root Node in a struct that acts as the API boundary.

use tiny_keccak::{Hasher, Keccak};

#[derive(Serialize, Deserialize)]
pub struct EthTrie {
    root: Box<Node>,
}

impl EthTrie {
    pub fn new() -> Self {
        EthTrie {
            root: Box::new(Node::Null),
        }
    }
    
    /// Calculates the Root Hash of the entire state.
    /// This triggers a recursive serialization of the entire tree.
    pub fn root_hash(&self) -> [u8; 32] {
        let encoded = rlp::encode(&*self.root);
        let mut hasher = Keccak::v256();
        let mut output = [0u8; 32];
        hasher.update(&encoded);
        hasher.finalize(&mut output);
        output
    }
}

5. The "Chicken and Egg" Problem

We have a problem.
I said "The pointer to the child is the Hash of the child."
But to hash the child, we must Serialize it (turn it into bytes).

How do we serialize a Branch?
Well, it's a list of 16 children.
Do we serialize the full children recursively? Or do we serialize their Hashes?

The Rule:
When serializing a node to calculate its hash:

We generally replace its children with their Hashes.
We do not verify the children's internal structure; we just trust their Hash.

This turns the serialization process into a weird hybrid operation where we are mixing Raw Data (the value) with Cryptographic Links (the child hashes).

And this leads us directly into the most complex, error-prone, and frustrating part of the entire project.
The Serialization Standard. RLP.

If you thought bit-twiddling nibbles was annoying, wait until you see the Inline Node Optimization.

It is finally time for Part III.

Continue Reading:

Part III: The Serialization Trap (RLP) →

Repository:
github.com/bit2swaz/merkle-trie-rs