The State of the Machine - Part III: The Serialization Trap (RLP)
"The Keccak-256 hash function doesn't know what an Enum is. It doesn't know what a pointer is. It only knows Bytes. This is where the bridge between the Abstract and the Concrete begins."
Series Navigation:
- Introduction
- Part I: The Alphabet (Nibbles)
- Part II: The Four Horsemen (Nodes)
- Part III: The Serialization Trap (RLP) <- You are here
- Part IV: The Surgical Strike (Insertion)
- Part V: The Witness (Merkle Proofs)
PART III: THE SERIALIZATION TRAP
Chapter 7: The Recursive Grammar (RLP)
We have reached the bridge between the Abstract and the Concrete.
In memory, our Node is a beautiful, recursive Rust Enum with smart pointers (Box) and semantic types (Nibbles).
But the Keccak-256 hash function does not know what an Enum is. It does not know what a pointer is. It only knows one thing: Bytes.
To generate the State Root, we must serialize our nodes.
You might ask: "Why not use JSON? Or Protobuf? Or Bincode?"
The answer is Determinism.
- In JSON,
{ "a": 1, "b": 2 }and{ "b": 2, "a": 1 }are semantically identical, but their hashes are completely different. - In Protobuf, field ordering and default values can vary between implementations.
Ethereum needed a format that was:
- Byte-Perfect: One structure has exactly one valid binary representation.
- Type-Agnostic: It doesn't care if it's an integer, a string, or a picture. It only knows "Byte Arrays" and "Lists".
- Space-Efficient: No field names ("key", "value") wasting space.
Hence, they created RLP (Recursive Length Prefix).
1. The Philosophy of RLP
RLP is brutally simple. It only understands two things:
- Item: A string of bytes (e.g., "dog", "100", public key).
- List: A collection of Items or other Lists.
That's it. There are no integers, no booleans, no floats. Everything is a Byte Array.
- The number
100? It is stored as the byte0x64. - The empty string
""? Stored as0x80(we'll see why). - The Null Node? Stored as
0x80.
2. The Rules of Engagement
Implementing RLP from scratch is a rite of passage. Even though we use the rlp crate in Rust, understanding these rules is mandatory because we have to manually intervene during the encoding process later.
There are 4 core rules based on the First Byte (the Prefix):
Rule 1: Single Byte (0x00 - 0x7F)
If the data is a single byte and its value is less than 128 (0x7F), it is its own encoding.
- Input:
0x64('d') - RLP:
0x64 - Overhead: 0 bytes.
Rule 2: Short String (0-55 bytes)
If the string is 0-55 bytes long, we add a prefix of 0x80 + Length.
- Input:
"dog"(3 bytes:64 6f 67) - Prefix:
0x80 + 3 = 0x83 - RLP:
0x83 64 6f 67 - Overhead: 1 byte.
Rule 3: Short List (0-55 bytes payload)
If it's a list, we add a prefix of 0xC0 + Length.
- Input:
["cat", "dog"]- "cat" ->
0x83 63 61 74(4 bytes) - "dog" ->
0x83 64 6f 67(4 bytes) - Total Payload: 8 bytes.
- "cat" ->
- Prefix:
0xC0 + 8 = 0xC8 - RLP:
0xC8 83 63 61 74 83 64 6f 67
Rule 4: Long Data (> 55 bytes)
If the data is huge, we can't fit the length in the prefix byte.
We use the prefix to say "The next N bytes tell you the length."
- This allows RLP to encode massive data structures (like the entire blockchain history) recursively.
3. The Node Encoding (The Spec)
So, how do our Node types map to RLP?
The Yellow Paper is strict.
1. Leaf Node
Encoded as a List of 2 items.
[Path, Value]
- Item 0: The Hex-Prefix encoded path (using the
0x20/0x30flags). - Item 1: The Value (as raw bytes).
2. Extension Node
Encoded as a List of 2 items.
[Path, Child]
- Item 0: The Hex-Prefix encoded path (using the
0x00/0x10flags). - Item 1: The Hash of the child node (usually).
3. Branch Node
Encoded as a List of 17 items.
[Child0, Child1, ..., Child15, Value]
- Items 0-15: The Hashes of the 16 children.
- Item 16: The Value (or empty string if none).
4. Null Node
Encoded as an Empty Byte String.
0x80 (The RLP encoding of length 0).
4. The Rust Implementation Strategy
We are using the rlp crate, which provides a trait Encodable.
Typically, you would just derive it:
#[derive(RlpEncodable)] struct MyStruct;
We cannot do this.
Why?
Because our Node enum is a logical union, but RLP expects specific list structures.
- A
Leafis a list of 2. - A
Branchis a list of 17. - A
Nullis a string.
If we auto-derived it, the library might encode the Enum Variant ID, which breaks Ethereum compatibility. We must implement Encodable manually.
use rlp::{Encodable, RlpStream};
use crate::node::Node;
impl Encodable for Node {
fn rlp_append(&self, s: &mut RlpStream) {
match self {
Node::Null => {
// Null is the empty string (0x80)
// In rlp crate, append_empty_data() does exactly this.
s.append_empty_data();
}
Node::Leaf { key, value } => {
// Leaf is a list of 2
s.begin_list(2);
// 1. Encode Path (Hex-Prefix with Leaf Flag)
let encoded_path = crate::nibbles::encode_compact(key, true);
s.append(&encoded_path);
// 2. Encode Value
s.append(value);
}
Node::Branch { children, value } => {
// Branch is a list of 17
s.begin_list(17);
// 1. Append 16 Children
for child in children {
// PROBLEM: Do we append the child structure? Or its hash?
// This is where things get complicated.
// For now, let's assume we append the child.
s.append(child);
}
// 2. Append Value (Item 17)
match value {
Some(val) => s.append(val),
None => s.append_empty_data(),
};
}
Node::Extension { prefix, next } => {
// Extension is a list of 2
s.begin_list(2);
// 1. Encode Path (Hex-Prefix with Extension Flag)
let encoded_path = crate::nibbles::encode_compact(prefix, false);
s.append(&encoded_path);
// 2. Append Child
s.append(next);
}
}
}
}
5. The Hidden Complexity
The code above looks reasonable. It looks like it should work.
But here's the best part: It's wrong.
If you run the code above, your hashes will not match Ethereum.
Why?
Because of the comment I left in the Branch section:
// PROBLEM: Do we append the child structure? Or its hash?
If we just call s.append(child), the RLP library will recursively encode the entire child node and embed it inside the parent.
If the tree is deep, we end up with one massive RLP blob containing the whole database.
But if we just hash the child, we lose the data.
Ethereum dictates a very specific, conditional rule about when to Hash and when to Embed. Read closely. This is the Inline Node Optimization.
It is the single most common reason why MPT implementations fail.
In the next chapter, we are going to fix our Encodable implementation to handle this edge case. We are going to have to manually inspect the length of the serialized child before we decide how to store it.
It's time to tackle the hardest part of Serialization.
Chapter 8: The Inline Node Optimization (The Final Boss)
In the previous chapter, we wrote a basic implementation of Encodable. We assumed that a parent node simply "appends" its children.
If we strictly followed that logic, we would end up with one of two disasters:
- The Bloated Blob: If we embed children recursively, the Root Node becomes a 100MB byte string containing the entire database state inline.
- The Bloated Hash: If we Hash every child pointer, we waste massive amounts of space on small values.
Ethereum solves this with a conditional rule that is elegant, space-efficient, and absolutely infuriating to debug.
1. The 32-Byte Threshold
A Keccak-256 hash is 32 bytes.
This is our magic number.
Imagine we have a small Leaf Node.
- Key:
0x01 - Value:
0x05 - RLP Encoding:
[0x01, 0x05]->0xC2 01 05. - Total Size: 3 bytes.
If we were to store a pointer to this node using a Hash, we would replace those 3 bytes of data with 32 bytes of hash.
We would increase the storage cost by 1000%.
This is inefficient.
The Rule:
When referencing a child node inside a parent (Branch or Extension):
- If RLP(child).len() < 32: Store the Raw RLP of the child directly inside the parent.
- If RLP(child).len() >= 32: Store the Keccak Hash of the child.
This means the structure of the Trie on disk is variable.
- A Branch node might contain 15 Hashes and 1 Inline Leaf.
- An Extension node might contain an Inline Branch which contains Hashes.
2. The Recursive Dependency
This rule creates a computational dependency chain.
To encode a Parent, we need to know if the Child is < 32 bytes.
To know if the Child is < 32 bytes, we must encoded the Child first.
This forces the serialization to be Bottom-Up.
We cannot stream the encoding from the top. We must recurse down to the leaves, encode them, check their lengths, return that up to the parent, encode the parent, check its length, and so on.
3. The Implementation Strategy
We need a helper function. Let's call it hash_or_raw.
This function will take a node, serialize it, and decide whether to return the Bytes (raw) or the Hash.
But there is a catch: Double Encoding.
- If we embed the Raw RLP, the RLP stream expects raw bytes.
- If we embed the Hash, the RLP stream expects a 32-byte value.
We must use rlp::RlpStream::append_raw carefully.
use tiny_keccak::{Hasher, Keccak};
/// Helper: Decides whether to embed the node raw or hash it.
/// This applies to Branch children and Extension next-pointers.
fn hash_or_raw(node: &Node) -> Vec<u8> {
// 1. Serialize the child strictly to check its size
let encoded = rlp::encode(node);
// 2. The Threshold Check
if encoded.len() < 32 {
// CASE A: Inline
// Return the raw RLP bytes directly
encoded.to_vec()
} else {
// CASE B: Hash
// Hash the full RLP and return the 32-byte result
let mut hasher = Keccak::v256();
let mut output = [0u8; 32];
hasher.update(&encoded);
hasher.finalize(&mut output);
output.to_vec()
}
}
4. The Corrected Encodable Implementation
Now we can rewrite our Encodable implementation from Chapter 7.
We replace the naive s.append(child) with our smart logic.
impl Encodable for Node {
fn rlp_append(&self, s: &mut RlpStream) {
match self {
Node::Null => {
s.append_empty_data();
}
Node::Leaf { key_remainder, value } => {
// Leaf is self-contained. No children to check.
s.begin_list(2);
let encoded_path = encode_compact(key, true);
s.append(&encoded_path);
s.append(value);
}
Node::Branch { children, value } => {
s.begin_list(17);
// Iterate over the 16 children pointers
for child in children.iter() {
let child_data = Node::hash_or_raw(child);
s.append(&child_data);
}
match value {
Some(val) => s.append(val),
None => s.append_empty_data(),
};
}
Node::Extension { prefix, next } => {
s.begin_list(2);
let encoded_path = encode_compact(prefix, false);
s.append(&encoded_path);
// Apply optimization to the 'next' pointer
let next_data = Node::hash_or_raw(next);
s.append(&next_data);
}
}
}
}
5. The "Root" Exception
There is one exception to the Inline Rule.
The State Root itself.
The State Root is stored in the Block Header.
The Block Header is a fixed structure. The "State Root" field is defined as [u8; 32].
It must be a hash.
Even if our entire Trie is just one small Leaf node (size < 32 bytes), the API trie.root_hash() must return a Hash, not the raw node.
If we used hash_or_raw on the very top-level API, and the tree was small, we would return a blob of data instead of a hash, breaking the Block Header structure.
So, in our EthTrie struct, we force the hash:
impl EthTrie {
pub fn root_hash(&self) -> [u8; 32] {
// Always hash the top level, ignoring the inline rule
let encoded = rlp::encode(&*self.root);
let mut hasher = Keccak::v256();
let mut output = [0u8; 32];
hasher.update(&encoded);
hasher.finalize(&mut output);
output
}
}
6. The Psychological Toll
This chapter represents the moment most developers quit.
Why?
Because verifying this is hard.
If you have a bug here, you won't get a compilation error. You won't get a runtime panic.
You will just get a different Hash than Geth.
And because it involves recursion, hashing, and serialization, "debugging" means staring soulessly at hex dumps like 0xf9 01... and trying to manually decode RLP in your head to see where the length prefix went wrong.
But we have done it. We have implemented the logic.
We have a Trie that can Store data (Node), Speak the language (Nibbles), and Serialize itself (RLP) according to the strictest rules of the protocol.
Now, we need to make it dynamic.
A static tree is boring. We want to build the state. We want to insert keys.
This means we have to break the tree apart and rebuild it on the fly.
We will cover all of that, and more in Part IV: The Surgical Strike.
Chapter 9: The Test of Truth (Determinism)
We have spent the last two chapters implementing the laws of Ethereum Serialization.
We handled RLP encoding. We handled the 32-byte Inline Node rule. We handled the Hex-Prefix flags.
Now, we face the Avalanche Effect.
In cryptography, the Avalanche Effect refers to the property where a small change in the input (flipping a single bit) causes a massive, unpredictable change in the output (the hash).
- Input A:
Hello World-> Hash:0xa0bc... - Input B:
Hello world-> Hash:0xf291...
This property is great for security, but it is hell for debugging.
If our merkle-trie-rs implementation is off by one single bit, say we used 0x30 instead of 0x20 for a Leaf flag, or we encoded a length as a u32 instead of a u64, our Root Hash will be completely wrong.
It won't even be "close." It will be random garbage.
And because it's a hash, we can't reverse-engineer it to find the error. We can't look at 0xf291... and say, "Oh, I see, I missed a nibble."
So, how do we verify our work? We start with the constants.
1. The Empty Root (The Constant of the Universe)
There is one number every Ethereum dev knows by heart.
The Hash of the Empty Trie.
If you have a Trie with zero nodes (just Node::Null), what is its Root Hash?
- Root is
Node::Null. - RLP encoding of
Nullis the empty string0x80. - Keccak-256 of
0x80(empty RLP) is...
0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
This is our "Hello World." If our code cannot produce this hash, we are dead in the water.
#[test]
fn test_empty_trie_root_hash() {
let trie = EthTrie::new();
let hash = trie.root_hash();
let expected = hex::decode("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421").unwrap();
assert_eq!(hash.to_vec(), expected);
}
If this test passes, we know two things:
- Our
tiny-keccakintegration is correct. - Our
Node::NullRLP encoding is correct.
2. Manual Construction Tests
Since we haven't implemented insert yet (that'll be in Part IV), we verify our serialization by Manually Constructing complex nodes and checking their hashes against known vectors.
Let's verify the Inline Node Optimization.
Scenario: A Leaf node small enough to be inlined.
- Key:
0x12(Encoded:[0x31, 0x2]) - Value:
0x64("d") - Node:
Leaf { key: [1, 2], value: [0x64] } - RLP:
0xC3 31 02 64(Total 4 bytes).
If we put this Leaf inside a Branch, the Branch RLP should contain the raw bytes 0xC3..., not the hash.
We write a test that manually builds this structure:
#[test]
fn test_inline_leaf_in_branch() {
// 1. Create a small leaf
let leaf = Node::Leaf {
key: vec![0x12],
value: vec![0x64],
};
// 2. Put it in a Branch at index 0
let mut children = std::array::from_fn(|_| Box::new(Node::Null));
children[0] = Box::new(leaf);
let branch = Node::Branch {
children,
value: None,
};
// 3. Serialize the Branch
let encoded = rlp::encode(&branch);
// 4. Verification
// We expect the encoded stream to contain the raw leaf bytes (0xC3...)
// If we see 32 random bytes at the start, we failed the optimization check.
// For debugging, print the hex:
println!("Encoded: {}", hex::encode(&encoded));
}
3. The Debugging Toolkit
When your hashes don't match, you enter what I call the "Pain Cave."
Here is how I survived it:
A. The "Hex Dump" View
Never look at raw bytes. Always convert to Hex.
Use hex::encode(data) everywhere.
Learn to read RLP headers:
0xF8: Start of a long list (likely a Branch).0xC...: Start of a short list (likely a Leaf/Extension).0x8...: Start of a string.
B. The "EthereumJS" Oracle
I didn't guess the correct hashes. I cheated.
I set up a small script using ethereumjs-trie (the reference JavaScript implementation).
I would insert the same keys into the JS trie, print the root hash, and then ensure my Rust implementation matched it.
Rule of Engineering: Don't calculate the expected value yourself. Use a source of truth.
C. Visual Inspection
If hash(A) != hash(B), looking at the hashes is useless.
You must look at rlp(A) and rlp(B).
Often, the difference is trivial:
- Rust:
0x81 0x01(String of length 1, value 1) - JS:
0x01(Single byte 1)
This tells you: "Aha! I treated a small integer as a string, invoking RLP Rule 2 instead of Rule 1."
4. Conclusion of Part III
We have survived the Trap.
We have:
- Defined the Rules (RLP).
- Implemented the Logic (Recursive Encoding).
- Optimized the Storage (Inline Nodes).
- Verified the Truth (Empty Root).
Our Node is now a valid Ethereum citizen. It can be serialized, hashed, and verified by any client on the network.
But a static citizen is boring. We want to Change State.
We want to take an existing tree and inject new truth into it.
We want to implement insert.
This requires us to perform surgery on the immutable. We have to rip apart the Box<Node>, re-wire the pointers, split the Extensions, and stitch it all back together, all while satisfying Rust's strict ownership model.
Time to move to Part IV: The Surgical Strike.
Continue Reading:
Repository:
github.com/bit2swaz/merkle-trie-rs