Introduction

≈60 min · Intermediate · builds on Protocols & wire messages

Before you meet XRPL's clever state structures, it's worth understanding the problem they solve. In this module you'll see why a naive database can't work for a trustless network, and build up the ideas (cryptographic hashing, Merkle trees, radix-16 Patricia tries) that make verifiable, efficiently-syncable state possible. Get these foundations and the SHAMap, coming next, will feel inevitable rather than magical.

The Naive Approach: What Fails

In brief: a plain key-value store cannot prove its state is correct to an untrusting network.

Let's consider what happens if you store blockchain state like a simple key-value database:

State Storage:

accounts = {
  "rN7n7otQDd6FczFgLdlqtyMVrn3LNU8B4C": { balance: 100 XRP, ... },
  "rLHzPsX6oXkzU2qL12kHCH8G8cnZv1rBJh": { balance: 50 XRP, ... },
  "r3kmLJN5D28dHuH8vZvVrDjiV5sNSiUQXD": { balance: 75 XRP, ... },
  ...
}

Transaction Processing:

Validator receives transaction: send 10 XRP from Alice to Bob
Validator checks Alice's balance (100 XRP available)
Validator updates Alice's balance to 90 XRP
Validator updates Bob's balance to 60 XRP
State is now modified

The Problem: No Verification

Without a cryptographic commitment to the state, any node can claim any state is correct:

Alice broadcasts: "My balance is 1,000,000 XRP"
Bob broadcasts: "My balance is 1,000,000 XRP"
Charlie broadcasts: "Everyone's balance is 0 XRP"

Which is correct? Without a central authority, there's no way to know.

The Problem: Expensive Synchronization

A new node joining the network needs to learn the current state. With naive storage:

New node requests: "Send me all account state"
Network sends millions of accounts, gigabytes of data
New node has no way to verify this data is correct
Process takes hours or days

The Requirement: Cryptographic Commitment

In brief: you need one hash that commits to the entire state, authentically and completely.

Blockchain state needs a cryptographic commitment: a single value that guarantees:

Authenticity: The value commits to the actual state (not a forgery)
Completeness: All accounts are included (not cherry-picked)
Uniqueness: Only one commitment can represent a given state

This is what cryptographic hashes provide:

uint256 stateHash = hashFunction(serializeAllState());

Now a validator can broadcast: "The current state root is 0xAB12EF..."

Other nodes can verify this is correct by computing the same hash. If someone tries to cheat with different state, the hash will be different.

The Trade-off Problem:

But hashing all state from scratch has a terrible cost:

Every account lookup requires computing the hash of all million accounts
Synchronizing with a peer requires hashing millions of accounts multiple times
A single account change requires rehashing everything
Performance becomes prohibitive

The SHAMap Solution: Merkle Trees

In brief: a tree of hashes makes single-entry changes cheap and lets nodes compare state by root hash.

XRPL solves the cryptographic commitment problem with a Merkle tree:

Instead of hashing all accounts together, organize them in a tree structure:

Key Insight: Each node's hash depends only on its descendants, not the entire tree:

Change Account0 → rehash 4 nodes (path from leaf to root)
Not millions of nodes

Synchronization Benefit:

When syncing with a peer:

Compare root hashes
If they match: entire state is identical (no need to compare anything else)
If they differ: identify which subtree diverges
Only synchronize the different parts
Recursive process: compare child hashes, descend into differences

A tree of 1 million accounts becomes synchronizable in a few thousand comparisons instead of millions.

Key idea. Change one leaf and only the hashes on the path to the root change. That single property is what makes both tamper-evidence and cheap syncing possible.

The Patricia Trie Optimization

In brief: keying the tree by the entry's own hash keeps it balanced and navigable, radix-16.

A simple binary tree has a problem: unbalanced growth. If accounts are added sequentially, the tree becomes a linked list, losing logarithmic properties.

Patricia tries (Radix N tries) solve this:

Use the entry's 256-bit key as a navigation guide
Each level of the tree represents 4 bits (one hex digit) of the key
This produces a balanced, predictable tree structure
Maximum tree depth is 64 levels (256 bits / 4 bits per level); a leaf actually sits at the shallowest level where its key prefix is unique, about 5 levels for a million entries

XRPL's Choice: Patricia trie with radix 16 (hex digits):

Level 0 (root): Evaluate first hex digit of the key (0-F)
  → Child 0, 1, 2, ... or F

Level 1: Evaluate second hex digit
  → One of 16 children

... and so on

This gives a balanced tree with:

Depth: at most 64 levels (one hex digit of the 256-bit key per level), typically ~5 for a million entries
Branching: Up to 16 children per node
Keys: 256-bit indexes computed with sha512Half over a LedgerNameSpace value and the entry's identifying data — for an account, the 160-bit AccountID (keylet::account in src/libxrpl/protocol/Indexes.cpp)

NodeStore: From Memory to Disk

Now we have SHAMap: an elegant in-memory data structure for cryptographically-committed state.

But there's a problem: When the validator crashes, all in-memory state vanishes.

The next startup:

The node must acquire the current validated ledger's state tree from its peers
Without a local copy of the tree's nodes, every node has to be downloaded again
For mainnet: that is gigabytes of data re-fetched over the network

NodeStore solves this by making SHAMap persistent:

Every node in the SHAMap is serialized to storage
Identified by its cryptographic hash
Retrievable by any peer that needs it
On restart, ledger acquisition reuses the nodes already on disk, so sync completes in minutes

The Storage Challenge:

But persistence introduces new challenges:

Database Size: A mature XRPL ledger creates millions of nodes. Storage can be terabytes.
Lookup Performance: Database queries are 1000x slower than memory access
Write Efficiency: Persisting every state change is I/O intensive
Backend Flexibility: Different operators need different storage engines (RocksDB, NuDB; plus in-memory backends for testing — see src/libxrpl/nodestore/backend/)

NodeStore addresses each:

Caching: Keep hot data in memory, query disk only when needed
Abstraction: Support multiple database backends with identical logic
Batch Operations: Write multiple nodes atomically
Online Deletion: Rotate databases to manage disk space without downtime

The Complete Picture

SHAMap's Role:

Maintains blockchain state in a Merkle tree structure
Provides cryptographic commitment through root hash
Enables efficient synchronization through hash comparison
Supports proof generation for trustless verification

NodeStore's Role:

Persists SHAMap nodes to durable storage
Provides on-demand node retrieval
Implements intelligent caching to minimize I/O
Abstracts database implementation details

Together:

They solve the complete blockchain state management problem:

A validator can:

Process transactions at microsecond latencies (SHAMap is in-memory)
Know state is persisted safely (NodeStore writes atomically)
Sync new peers in minutes (hash-based comparison finds differences)
Recover from crashes quickly (ledger acquisition from peers reuses nodes already in the local NodeStore)
Switch database backends without changing application logic

Why This Matters

In brief: these ideas are exactly what the SHAMap, coming next, is built from.

Understanding SHAMap and NodeStore is essential because:

Consensus Correctness: The root hash is what validators vote on. You cannot understand consensus without understanding how that hash is computed.
Synchronization Performance: Why can a new node catch up to the network in minutes? Because hash-based tree comparison eliminates redundant data transfer.
API Performance: Why do account lookups return in milliseconds? Because careful caching keeps hot nodes in memory.
Operational Reliability: Why can validators safely delete old data? Because the rotating database enables online deletion without service interruption.
Scalability Limits: Why does XRPL have practical limits on transaction volume? Because synchronizing and storing the ever-growing tree hits physical limits of disk I/O and memory.

These aren't just implementation details, they're fundamental to what XRPL is and how it works.

Looking Ahead

In the next chapter, we'll explore the mathematical foundations: Merkle trees, Patricia tries, and cryptographic hashing. Then we'll dive deep into the SHAMap implementation, followed by the NodeStore persistence layer.

By the end of this module, you'll understand not just what SHAMap and NodeStore do, but why they're architected the way they are, and how to reason about their correctness, performance, and limitations.

Trees, Hashing, and Cryptographic Commitments

Introduction

Before diving into the implementation of SHAMap and NodeStore, we need to understand the mathematical foundations they're built on. This chapter covers:

Cryptographic hashing and why it creates mathematical guarantees
Tree structures and why they matter for efficiency
How Merkle trees combine both to create verifiable commitments to data
Patricia tries and why they're optimal for key-value storage

Don't skip this chapter thinking it's just theory. Every design decision in SHAMap flows directly from the properties of these data structures. Understanding the foundations will make the implementation clear.

Cryptographic Hash Functions

A cryptographic hash function H has three critical properties:

1. Determinism

H(x) always returns the same result
H("hello") = 0x2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
H("hello") = 0x2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

(The example hashes in this section are SHA-256; XRPL's own hash function is SHA-512Half, covered below.)

Same input, always same output. This enables verification: others can compute the same hash and confirm correctness.

2. Collision Resistance

Finding two different inputs with the same hash output is computationally infeasible:

H(x) = H(y) where x ≠ y  → "collision"

For SHA-256: Finding a collision requires ~2^128 operations
Current computers: ~10^18 operations/second
Time required: ~3.4 × 10^20 seconds ≈ 10 trillion years

Cryptographic security: "practical impossibility"

3. Avalanche Effect

Tiny changes produce completely different outputs:

H("hello") = 0x2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
H("hallo") = 0xd3751d33f9cd5049c4af2b462735457e4d3baf130bcbb87f389e349fbaeb20b9

Change one character → hash completely changes

Implication for XRPL:

Hash output acts as a "fingerprint" of data:

Two accounts with identical state have identical hashes
Even one byte difference produces completely different hashes
Anyone can verify a claimed hash by recomputing it
Cannot forge a hash without recomputing it (collision-resistant)

XRPL uses SHA-512Half: First 256 bits of SHA-512. This gives:

256-bit output (32 bytes, fits in a uint256)
Security level of ~128 bits (same as AES-128)
Good performance for cryptographic verification

Tree Structures

Trees are recursive data structures: a root node with zero or more children, each of which is a tree.

Key Tree Property: Logarithmic Depth

For a balanced tree with branching factor B and N items:

Depth = log_B(N)
Binary tree (B=2): 1M items → depth 20
Radix-16 tree (B=16): 1M items → depth 5
Radix-256 tree (B=256): 1M items → depth 3

Why Depth Matters:

Access time: proportional to depth
Update time: change leaf → rehash path from leaf to root (depth operations)
Synchronization: identify differences by comparing hashes (depth comparisons)

Higher branching factor = shallower tree = faster operations.

The Balance Problem:

But trees can become unbalanced:

For blockchain state, accounts are inserted in unpredictable order. Without careful tree structure, you get unbalanced trees and logarithmic operations degrade.

Patricia Tries (Radix Tries)

Patricia tries solve the balance problem by using the key itself as navigation.

Basic Idea:

For a 256-bit key (like a ledger entry's index), use the bits to guide traversal:

Radix-2 (binary): Each bit (0 or 1) determines left or right child
Radix-4: Each 2-bit pair determines one of 4 children
Radix-16 (hex): Each 4-bit nibble determines one of 16 children
Radix-256: Each 8-bit byte determines one of 256 children

Example: Radix-16 Patricia Trie

Balance Guarantee:

Since navigation is determined by the key:

A leaf is stored at the shallowest depth where its key prefix differs from every other key's — no insertion order can degrade the tree into a list
Maximum depth is bounded by key length (256 bits / 4 bits = 64 levels; SHAMap::kLeafDepth in include/xrpl/shamap/SHAMap.h)
With uniformly distributed hash keys, actual leaf depth stays near log_16(N) — about 5 levels for a million entries

Space Trade-off:

Inner nodes have up to 16 pointers (for radix-16), but most sparse:

Many branches are empty (no accounts in that range)
Compressed representation avoids wasting space
Net result: similar space as binary tree despite higher branching

XRPL's Choice: Radix-16

// include/xrpl/shamap/SHAMapInnerNode.h
/** Each inner node has 16 children (the 'radix tree' part of the map) */
static constexpr unsigned int kBranchFactor = 16;

And the navigation itself — one nibble of the key per level, high nibble at even depths, low nibble at odd depths:

// src/libxrpl/shamap/SHAMapNodeID.cpp
[[nodiscard]] unsigned int
selectBranch(SHAMapNodeID const& id, uint256 const& hash)
{
    auto const depth = id.getDepth();
    auto branch = static_cast<unsigned int>(*(hash.begin() + (depth / 2)));

    if ((depth & 1) != 0u)
    {
        branch &= 0xf;
    }
    else
    {
        branch >>= 4;
    }

    XRPL_ASSERT(branch < SHAMap::kBranchFactor, "xrpl::selectBranch : maximum result");
    return branch;
}

Why radix-16?

Shallow trees: leaf depth tracks log_16 of ledger size (~5 levels for a million entries), with a hard cap of 64
Manageable fanout: 16 children per node (balanced tree complexity)
Natural alignment: hex notation matches code
Proven in Ethereum: its Merkle-Patricia trie is also radix-16. (Bitcoin is not a precedent here: it builds a plain binary Merkle tree over each block's transactions and does not merkleize state at all.)

Merkle Trees

A Merkle tree combines tree structure with cryptographic hashing:

Definition:

Leaf nodes: Contain data (accounts, transactions)
Inner nodes: Contain hashes of their children
Root hash: Represents the entire tree

Key Property: Hash Propagation

When a leaf changes, its hash changes. This affects its parent:

Benefit: O(1) Subtree Comparison

Compare two trees:

Without Merkle trees:

Compare all N leaves directly: O(N) time

With Merkle trees:

Compare root hashes: O(1) time
If different, compare child hashes to find divergence: O(log N) comparisons

Benefit: Logarithmic Proofs

Prove that a specific item is in the tree:

Merkle Proof for "Alice: 90 XRP":

Show:  H("Alice: 90 XRP") = 0x1234...
       H(Sibling1) = 0x5678...
       H(Sibling2) = 0x9ABC...

Verifier computes:
  Combine with siblings working up to root
  Verify final hash matches claimed root

Only need to show O(log N) nodes, not entire tree

XRPL's Merkle-Patricia Trie

XRPL's SHAMap combines both approaches:

Patricia Trie Structure:

Navigation determined by the entry's key (256-bit hash)
Radix-16 branching (hex digit at each level)
Perfect balance regardless of account insertion order

Merkle Properties:

Each node contains hash of its content
Inner node hash computed from children's hashes
Root hash represents entire ledger state
Changes propagate up to root

The Result:

Properties:

Leaf depth: approximately log_16(number of accounts) ≈ 5 levels for 1M accounts
Hash changes: only O(log N) nodes affected by any modification
Verification: O(1) root hash comparison, O(log N) proof verification
Synchronization: O(log N) hash comparisons to find differences

Hashing Algorithms in XRPL

XRPL uses SHA-512Half for all protocol object hashing: SHAMap node hashes, ledger entry indexes, transaction IDs, and signing hashes. (One notable exception outside that scope: the 160-bit AccountID is RIPEMD-160 of SHA-256 of the public key — include/xrpl/protocol/digest.h.) The workhorse is the free function sha512Half:

// include/xrpl/protocol/digest.h
/** Returns the SHA512-Half of a series of objects. */
template <class... Args>
sha512_half_hasher::result_type
sha512Half(Args const&... args)
{
    sha512_half_hasher h;
    using beast::hash_append;
    hash_append(h, args...);
    return static_cast<typename sha512_half_hasher::result_type>(h);
}

Why SHA-512Half instead of SHA-256?

SHA-512 has better performance on 64-bit CPUs
Taking first 256 bits gives same security as SHA-256
But faster on modern hardware
256-bit output fits uint256 perfectly

Hash Computation in SHAMap:

An inner node's hash covers HashPrefix::InnerNode followed by all 16 branch hashes — iterChildren visits every branch, and an empty branch contributes a zero hash. A node with no branches at all hashes to zero:

// src/libxrpl/shamap/SHAMapInnerNode.cpp
void
SHAMapInnerNode::updateHash()
{
    uint256 nh;
    if (isBranch_ != 0)
    {
        sha512_half_hasher h;
        using beast::hash_append;
        hash_append(h, HashPrefix::InnerNode);
        iterChildren([&](SHAMapHash const& hh) { hash_append(h, hh); });
        nh = static_cast<typename sha512_half_hasher::result_type>(h);
    }
    hash_ = SHAMapHash{nh};
}

Including all 16 positions (empty ones as zero) matters: skipping empties would make two nodes whose only child sits at different branch positions hash identically.

Leaf nodes hash a HashPrefix constant, then the item's data, then the item's key last. Each leaf type has its own updateHash:

// include/xrpl/shamap/SHAMapAccountStateLeafNode.h
void
updateHash() final
{
    hash_ = SHAMapHash{sha512Half(HashPrefix::LeafNode, item_->slice(), item_->key())};
}

// include/xrpl/shamap/SHAMapTxPlusMetaLeafNode.h
void
updateHash() final
{
    hash_ = SHAMapHash{sha512Half(HashPrefix::TxNode, item_->slice(), item_->key())};
}

// include/xrpl/shamap/SHAMapTxLeafNode.h
void
updateHash() final
{
    hash_ = SHAMapHash{sha512Half(HashPrefix::TransactionId, item_->slice())};
}

Note the plain transaction leaf hashes no key at all: its hash of the transaction data is the item's key.

Why Hash Prefixes?

Each prefix is a 4-byte constant from include/xrpl/protocol/HashPrefix.h — three ASCII characters plus a zero byte: HashPrefix::LeafNode ('M','L','N', account state), HashPrefix::TxNode ('S','N','D', transaction plus metadata), HashPrefix::TransactionId ('T','X','N'), HashPrefix::InnerNode ('M','I','N'). They prevent collisions between different types of data:

Same bytes, different meaning:

Account-state leaf:  sha512Half("MLN\0" || data || key)
Tx-with-meta leaf:   sha512Half("SND\0" || data || key)

Identical data and key can never produce the same hash in both
maps, because the prefixes differ.

Immutability and Copy-on-Write

Once a Merkle tree root hash is committed to (published in a ledger), that entire tree must be immutable:

Changing any leaf would change the root hash
Root hash commitment would become invalid
Trust in the ledger is broken

Solution: Snapshots

For each ledger version, create a snapshot:

Copy-on-Write:

When a mutable SHAMap modifies a shared node:

Both ledgers are verified by their root hashes, but they share most of the tree (unchanged nodes).

Summary

This module built up the ideas behind XRPL's state storage. It showed why a naive key-value store fails for a trustless network, then introduced cryptographic hashing, Merkle trees, and radix-16 Patricia tries, the pieces that make state verifiable and cheap to sync. The key insight is that a tree of hashes lets a single change touch only the path to the root, and lets nodes compare state by comparing one root hash. These foundations are exactly what the SHAMap is built from.

To remember:

Naive key-value state fails trustless networks: no cryptographic commitment, no cheap verification
One root hash commits to the whole state: authenticity, completeness, uniqueness
Merkle tree: changing one leaf rehashes only the path to the root, O(depth) not O(state)
Radix-16 Patricia trie: the key itself routes, one nibble (4 bits) per level; leaves sit at the shallowest unique-prefix depth (max 64)
Copy-on-write: snapshots share unchanged subtrees, so per-ledger immutability is cheap
Equal root hashes mean identical state; a difference tells you exactly which subtree to descend
The workhorse hash is SHA-512Half: SHA-512, keep the first 256 bits
Watch out: these are the load-bearing ideas behind the SHAMap; if syncing or proofs ever feel magic, come back here

Next up. You know why the state tree exists. Now go inside it: how the SHAMap actually stores a million accounts and fingerprints them all in one 32-byte hash.

State-management foundations

Introduction

The Naive Approach: What Fails

The Requirement: Cryptographic Commitment

The SHAMap Solution: Merkle Trees

The Patricia Trie Optimization

NodeStore: From Memory to Disk

The Complete Picture

Why This Matters

Looking Ahead

Trees, Hashing, and Cryptographic Commitments

Introduction

Cryptographic Hash Functions

Tree Structures

Patricia Tries (Radix Tries)

Merkle Trees

XRPL's Merkle-Patricia Trie

Hashing Algorithms in XRPL

Immutability and Copy-on-Write

Summary