SHAMap architecture & hashing

Introduction

≈90 min · Advanced · builds on State-management foundations

Watch this short video by XRPL Commons first, then dive into the details below.

With the foundations in hand, let's open up the real thing: the SHAMap, the Merkle-Patricia tree that holds all XRPL state. In this module you'll learn its inner and leaf nodes, how a 256-bit key walks the tree nibble by nibble, and how a single change ripples up to a brand-new root hash. This is the structure that makes the whole ledger tamper-evident.

Core Design Principles

In brief: the goals the SHAMap is built to satisfy: verifiable, immutable, and cheap to sync.

The SHAMap architecture achieves three critical properties:

1. Cryptographic Integrity

Every change to data propagates through hashes up to the root:

Modify Account0 data:
  Account0 hash changes
  Parent hash changes (incorporates new Account0 hash)
  Grandparent hash changes
  ... up to root

New root hash is deterministically different from old root hash

This ensures that no data can be modified undetected. Changing even one bit in an account's balance changes the root hash.

2. Efficient Navigation

The Patricia trie structure uses account identifiers as navigation guides:

Account hash: 0x3A7F2E1B4C9D...
Tree navigation:
  Level 0: Extract digit 3 → go to child 3
  Level 1: Extract digit A → go to child A
  Level 2: Extract digit 7 → go to child 7
  ... follow 4-bit chunks down the tree

No binary search needed. The path is directly encoded in the key.

3. Optimized Synchronization

Hash-based comparison eliminates unnecessary data transfer:

Peer A claims: "Root is 0xABCD"
Peer B claims: "Root is 0xXYZW"

If 0xABCD == 0xXYZW:
  Both have identical ledger state
  No synchronization needed

If different:
  Compare children's hashes
  Identify exactly which subtrees differ
  Request only those subtrees

This allows new nodes to synchronize full ledgers from peers in minutes.

The SHAMap Instance

In brief: the class itself: state, transaction and shard maps, and their shared skeleton.

A SHAMap instance represents a complete tree of ledger state:

Core Data:

class SHAMap {
    // The root node (always an inner node)
    std::shared_ptr<SHAMapInnerNode> mRoot;

    // Tree state (Immutable, Mutable, or Synching)
    State mState;

    // For mutable trees: unique identifier
    std::uint32_t mCowID;  // Copy-on-write identifier

    // For navigating to nodes
    std::shared_ptr<Family> mFamily;
};

Key Properties:

• Root Node: Always an inner node, never a leaf (even if only one account, still has inner structure)
• Depth: At most 64 levels (256-bit keys ÷ 4 bits per level), but the trie is truncated: a leaf sits at the first depth where its key prefix is unique, so with millions of entries the typical path is only ~5-6 levels
• Navigation Determinism: Any key uniquely determines its path from root to leaf

Node Hierarchy

In brief: two node kinds, inner nodes (up to 16 children) and leaf nodes that hold the data.

The SHAMap consists of three conceptual layers:

Layer 1: Root

• Always present
• Always an inner node
• Contains the root hash representing entire tree
• Can have up to 16 children (one for each hex digit 0-F)

Layer 2: Internal Structure

• Inner nodes serve as branch points
• Each can have 0-16 children
• Store only hashes of children, not actual data
• No data items in inner nodes

Layer 3: Leaf Nodes

• Terminal nodes containing actual data items
• Types: Account state, Transaction, Transaction+Metadata
• All leaves in a SHAMap tree are homogeneous (same type)

Key idea. A 256-bit key walked four bits at a time gives a tree at most 64 levels deep with a fan-out of 16, which is why lookups and updates stay fast even with millions of entries.

Inner Nodes

In brief: route by one nibble of the key and roll their children's hashes up toward the root.

Inner nodes form the branching structure:

Structure:

class SHAMapInnerNode {
    // Up to 16 child slots (indexed 0-F)
    std::array<Branch, 16> mBranches;

    // Cryptographic hash of this node
    uint256 mHash;

    // Bitset: which children exist
    std::uint16_t mChildBits;

    // For copy-on-write: which SHAMap owns this node
    std::uint32_t mCowID;

    // Synchronization optimization: generation marker
    std::uint32_t mFullBelow;
};

// Each branch slot contains:
struct Branch {
    std::shared_ptr<SHAMapTreeNode> mNode;  // nullptr if empty
    uint256 mHash;  // Hash of child (or empty)
};

Key Characteristics:

1. Do not store data items directly - Only hashing information
2. Maintain cryptographic commitments through child hashes
3. Variable occupancy - Not all 16 children present
4. Support both serialization formats - Compressed and full

Serialization Formats:

Inner nodes support two wire formats:

Compressed Format (used when most slots are empty):

Header: "Inner (compressed)"
Bitmap: Which branches exist
For each existing branch:
  Branch index
  Child hash

Saves space by omitting empty branches.

Full Format (used when most slots are occupied):

Header: "Inner (full)"
For each of 16 branches:
  Child hash (or empty marker)

Simpler structure despite larger size.

Format Selection Algorithm:

XRPL automatically chooses format based on branch count:

Branch count:
  0-8:   Use compressed (saves ~40 bytes)
  9+:    Use full (simpler, fewer bytes overall)

Leaf Nodes

In brief: hold an actual ledger item and its hash at the bottom of the tree.

Leaf nodes store the actual blockchain data:

Base Properties:

class SHAMapLeafNode {
    // The data contained in this leaf
    std::shared_ptr<SHAMapItem> mItem;

    // Cryptographic hash
    uint256 mHash;

    // For copy-on-write
    std::uint32_t mCowID;
};

SHAMapItem Structure:

class SHAMapItem {
    // 256-bit unique identifier (determines tree position)
    uint256 mTag;

    // Variable-length data (transaction, account state, etc.)
    Blob mData;

    // Memory management: intrusive reference counting
};

Leaf Node Specializations:

Three distinct leaf node types exist, each with unique hashing:

1. Account State Leaves (SHAMapNodeType::TnAccountState)

• Store account information
• Include balances, settings, owned objects, trust lines
• Type prefix during hashing prevents collision with other types
• Updated when transactions affect accounts

2. Transaction Leaves (SHAMapNodeType::TnTransactionNm)

• Store transaction data
• Do not include execution metadata
• Immutable once added to ledger
• Enable verification of transaction history

3. Transaction+Metadata Leaves (SHAMapNodeType::TnTransactionMd)

• Store transactions with execution metadata
• Include results (success/failure, ledger entries modified)
• Complete information for replaying or auditing
• Support full transaction reconstruction

Why Multiple Types?

// Type prefix prevents collisions

uint256 hash_account_state = SHA512Half(
    PREFIX_ACCOUNT || key || data);

uint256 hash_transaction = SHA512Half(
    PREFIX_TRANSACTION || key || data);

// Even with identical (key, data), hashes differ
hash_account_state != hash_transaction

Ensures that moving data between leaves would be immediately detected as invalid.

SHAMapNodeID: Node Identification

In brief: how a depth plus a masked key names any node in the tree.

Every node in the tree is uniquely identified by its position:

Components:

class SHAMapNodeID {
    // Distance from root (0 = root)
    std::uint32_t mDepth;

    // Path from root to this node
    // Packed as 4-bit nibbles in a uint256
    uint256 mNodeID;
};

Path Encoding:

The path is encoded as 4-bit chunks (nibbles) in a uint256:

Node at depth 3, path [3, A, 7]:

mNodeID = 0x3A7000...000
          ^^^     (significant nibbles)
            ^^^^^^ (zero padding for remaining levels)

Depth 0 (root):     mNodeID = 0x0000...000
Depth 1:            mNodeID = 0x3000...000
Depth 2:            mNodeID = 0x3A00...000
Depth 3:            mNodeID = 0x3A70...000
...
Depth 64:           mNodeID = complete (all 64 nibbles filled)

Key Operations:

getChildNodeID(branch) - Compute child position:

SHAMapNodeID parent(depth=2, nodeID=0x3A00...);
SHAMapNodeID child = parent.getChildNodeID(7);
// Result: depth=3, nodeID=0x3A70...

selectBranch(nodeID, key) - Determine which branch to follow:

uint256 key = 0x3A7F2E1B4C9D...;
int branch = key.nthNibble(depth);  // Extract nth 4-bit chunk
// For depth=2: branch = 7 (extract bits 8-11)

This deterministic navigation ensures every key has exactly one path through the tree.

State Management

In brief: immutable snapshots, copy-on-write, and why sharing subtrees is safe.

SHAMaps exist in different states reflecting their role in the system:

Immutable State

mState == State::Immutable;
mCowID == 0;

• Represents a finalized, historical ledger
• Nodes cannot be modified
• Multiple readers can access simultaneously
• Critical limitation: cannot be trimmed (nodes loaded stay in memory)
• Used for consensus history

Mutable State

mState == State::Modifying;
mCowID != 0;  // Unique identifier for this tree

• Represents work-in-progress ledger state
• Nodes can be modified through copy-on-write
• Safe mutations without affecting other SHAMap instances
• Single writer (typically), multiple readers possible
• Used for constructing new ledger

Synching State

mState == State::Synching;

• Transitional state during network synchronization
• Allows incremental tree construction
• Transitions to Immutable or Modifying when complete
• Used when receiving missing nodes from peers

State Transitions:

Copy-on-Write Mechanism

In brief: new versions share unchanged nodes with the old, giving cheap immutable snapshots.

The copy-on-write system enables safe node sharing and snapshots:

Principle:

Nodes are shared between SHAMaps using shared pointers. When a mutable SHAMap needs to modify a shared node, it creates a copy:

// Check if node is owned by this SHAMap
if (node->getCowID() != mCowID) {
    // Node is shared or immutable
    // Create a copy
    auto newNode = node->clone();
    newNode->setCowID(mCowID);  // Mark as owned by this tree
    return newNode;
} else {
    // Node already owned by this tree
    // Safe to modify in place
    return node;
}

Node Sharing Rules:

cowID == 0:           Immutable (shared by all)
cowID == tree.mCowID: Owned by this tree (safe to modify)
cowID != tree.mCowID: Owned by another tree (must copy before modifying)

Benefits:

1. Efficient Snapshots: New SHAMap instances share unmodified subtrees

   Create snapshot before ledger close:
     New immutable SHAMap shares root and all unchanged nodes
     No deep copy required
   

2. Safe Concurrent Access: Modifications don't affect other instances

   SHAMap A modifies Account1:
     Clones nodes along path to Account1
     Leaves rest of tree shared
   SHAMap B (different ledger) unaffected
   

3. Memory Efficiency: Identical subtrees stored once

   100 ledgers share 99% of tree structure
   Only 1% of data duplicated for different accounts
   

Integration with NodeStore

In brief: how tree nodes become database records and come back.

SHAMap is designed for in-memory operation, but nodes can be persisted:

Persistent Nodes:

Some nodes are marked as "backed" - they exist in NodeStore:

// Node came from persistent storage
mNode->setBacked();

// When synchronizing, try to retrieve from storage
std::shared_ptr<SHAMapTreeNode> node = nodestore.fetch(hash);
if (node) {
    // Add to tree
    canonicalizeNode(node);  // Ensure uniqueness
}

Canonicalization:

Ensures nodes are unique in memory:

// Check cache for existing node with same hash
std::shared_ptr<SHAMapTreeNode> cached = cache.get(hash);
if (cached) {
    return cached;  // Use existing node
} else {
    cache.insert(hash, newNode);  // Cache new node
    return newNode;
}

This enables:

• Safe node sharing across multiple SHAMap instances
• Fast equality checking (compare pointers, not content)
• Memory efficiency (identical nodes stored once)

Appendix: Codebase Navigation Guide

In brief: where everything SHAMap lives in the repository.

Introduction

This appendix helps you navigate the rippled codebase to find SHAMap and NodeStore implementations.

Directory Structure

SHAMap Source Files

NodeStore Source Files

Integration Points

Key Classes and Their Locations

SHAMap Classes

NodeStore Classes

Navigation by Task

Understanding SHAMap Structure

1. Start: SHAMap.h - Overview of the class
2. Read: SHAMapTreeNode.h - Base class and type system
3. Explore: SHAMapInnerNode.h - Branch structure
4. Explore: SHAMapLeafNode.h - Data storage
5. Study: libxrpl/shamap/SHAMap.cpp - Implementation details

Understanding Node Synchronization

1. Start: shamap/SHAMapMissingNode.h - Missing node representation
2. Study: libxrpl/shamap/SHAMapSync.cpp - Synchronization algorithm
3. Cross-reference: nodestore/Database.h - Fetch operations called during sync
4. Understand: shamap/SHAMapNodeID.h - How nodes are identified

Understanding NodeStore Architecture

1. Start: nodestore/Database.h - Public interface
2. Understand: nodestore/Backend.h - Storage abstraction
3. Explore: nodestore/NodeObject.h - Storage unit
4. Study: nodestore/detail/DatabaseNodeImp.h - Standard implementation
5. Study: nodestore/detail/DatabaseRotatingImp.h - Rotation implementation

Understanding Database Rotation

1. Read: nodestore/detail/DatabaseRotatingImp.h - Architecture
2. Study: libxrpl/nodestore/DatabaseRotatingImp.cpp - Implementation
3. Understand: Synchronization with app/misc/SHAMapStoreImp.h

Understanding Cache Layer

1. Explore: basics/TaggedCache.h - Cache implementation
2. Study usage in: libxrpl/nodestore/DatabaseNodeImp.cpp
3. Understand metrics in: Database metrics methods

Common Code Patterns

Accessing a Node in SHAMap

// In shamap/SHAMap.h or libxrpl/shamap/SHAMap.cpp
std::shared_ptr<SHAMapTreeNode> node = getNodePointer(nodeID);

Storing a Node in NodeStore

// In app/misc/SHAMapStoreImp.cpp
auto obj = NodeObject::createObject(type, data, hash);
mNodeStore->store(obj);

Retrieving a Node

// In libxrpl/nodestore/DatabaseNodeImp.cpp
auto obj = mDatabase->fetchNodeObject(hash);

Cache Hit Path

// In libxrpl/nodestore/DatabaseNodeImp.cpp
auto cached = mCache.get(hash);  // L1 cache
if (!cached) {
    cached = mBackend->fetch(hash);  // L2 backend
    if (cached) mCache.insert(hash, cached);
}

Important Files to Read

Essential (Required Reading)

• shamap/SHAMap.h - Core API
• shamap/SHAMapNodeID.h - Navigation understanding
• nodestore/Database.h - NodeStore API
• nodestore/Backend.h - Abstraction principle

Important (Strongly Recommended)

• shamap/libxrpl/shamap/SHAMap.cpp - Implementation
• nodestore/detail/DatabaseNodeImp.h - Cache logic
• app/misc/SHAMapStoreImp.h - Integration

Reference (For Deep Understanding)

• shamap/SHAMapInnerNode.h - Branch structure details
• shamap/SHAMapLeafNode.h - Leaf implementations
• nodestore/libxrpl/shamap/SHAMapSync.cpp - Sync algorithm
• nodestore/detail/DatabaseRotatingImp.h - Rotation details

Building and Exploring

Compile rippled

cd rippled
mkdir build && cd build
cmake ..
make -j4

Navigate with IDE

Using VS Code or similar:

1. Open rippled repository
2. Go to Definition (Ctrl+Click) to jump to class definitions
3. Find All References (Shift+Ctrl+F) to see usage patterns
4. Use search to navigate between related classes

Debug and Trace

// Add to your code to trace execution
#include <iostream>

std::cout << "Node hash: " << node->getHash() << std::endl;
std::cout << "Node type: " << (int)node->getNodeType() << std::endl;

Test Files

Locate tests in:

rippled/src/test/*/shamap* and */nodestore*

Study how these are tested to understand expected usage patterns.

Configuration Reference

Configuration Files

NodeStore configuration in xrpld.cfg:

[node_db]
type = RocksDB          # Backend choice
path = /data/node.db    # Location
cache_size = 256        # Cache size in MB
cache_age = 60          # Max age in seconds

# For NuDB
# type = NuDB
# path = /data/nudb

# For Rotating
# online_delete = 256   # Keep last N ledgers

Common Configuration Patterns

# Small validator (less memory available)
[node_db]
cache_size = 64
cache_age = 30

# Large validator (plenty of resources)
[node_db]
cache_size = 512
cache_age = 120

Going Deeper

When you want to go from concept to implementation mastery, read the source in this order: SHAMap.h (node types), then src/libxrpl/shamap/SHAMap.cpp (the implementation), then nodestore/Database.h and nodestore/detail/DatabaseNodeImp.h (storage and caching, covered by the next modules), and finally trace a single transaction end to end and experiment with the tests.

Navigation, Hashing, and Merkle Properties

In brief: walking by nibbles, hashing bottom-up, and what the root hash proves.

Introduction

Now that you understand SHAMap's architecture and node types, let's explore how navigation actually works and how hashes propagate through the tree.

These operations are at the heart of what makes SHAMap efficient:

• Navigation: Finding the correct path to any account
• Hashing: Computing cryptographic commitments at each level
• Verification: Ensuring data integrity through hash chains

Navigation Algorithm

Finding a leaf in a SHAMap is straightforward because the account's key determines the exact path:

Algorithm: findLeaf

std::shared_ptr<SHAMapLeafNode> findLeaf(uint256 key) {
    std::shared_ptr<SHAMapTreeNode> node = mRoot;

    for (int depth = 0; depth < 64; ++depth) {
        // Is this a leaf?
        if (auto leaf = std::dynamic_pointer_cast<SHAMapLeafNode>(node)) {
            return leaf;
        }

        // Must be inner node
        auto inner = std::dynamic_pointer_cast<SHAMapInnerNode>(node);

        // Extract 4-bit chunk (nibble) at position 'depth'
        int branch = key.nthNibble(depth);

        // Get child node at that branch
        node = inner->getChild(branch);

        if (!node) {
            // Child doesn't exist - key not in tree
            return nullptr;
        }
    }

    return nullptr;  // Key not found
}

Step-by-Step Example:

Key: 0x3A7F2E1B4C9D... (account hash)

Depth 0: Root
  Extract nibble 0 (first 4 bits): 3
  Navigate to child 3

Depth 1:
  Extract nibble 1 (next 4 bits): A
  Navigate to child A in the child-3 subtree

Depth 2:
  Extract nibble 2: 7
  Navigate to child 7

... continue until reaching leaf

Time Complexity:

• Worst case: O(64) inner node traversals (fixed depth)
• Each traversal: O(1) array access to branch pointer
• Total: O(1) expected time (with high probability leaf found before depth 64)

Space Requirement:

• Path from root to leaf: ~64 pointers maximum
• Working memory: O(1) per operation

Hash Computation

Hashing is fundamental to SHAMap's integrity guarantees:

Leaf Node Hashing

Leaves compute their hash from their data with a type prefix:

uint256 SHAMapLeafNode::computeHash() {
    Blob data;

    // Type prefix (1 byte) - prevents collisions
    data.push_back(mLeafType);  // ACCOUNT, TX, or TX_WITH_META

    // Account key (32 bytes)
    data.append(mItem->getTag());

    // Account data (variable)
    data.append(mItem->getData());

    // Hash the complete structure
    return SHA512Half(data);
}

Example:

Account0 data: mTag=0x123ABC..., mData=<100 XRP, flags>
Type prefix: ACCOUNT_LEAF (1 byte)

Hash input: [0x01][123ABC...][100 XRP, flags]
Hash output: 0x47FA... (256 bits)

Changed: mData to "99 XRP"
Hash input: [0x01][123ABC...][99 XRP, flags]
Hash output: 0xB8EF... (completely different)

Inner Node Hashing

Inner nodes compute their hash from their children's hashes:

uint256 SHAMapInnerNode::computeHash() {
    Blob data;

    // For each of 16 possible children
    for (int i = 0; i < 16; ++i) {
        if (hasChild(i)) {
            // Get child's hash (whether child exists in memory or disk)
            uint256 childHash = getChildHash(i);
            data.append(childHash);  // Append 32 bytes
        }
    }

    // Hash all non-empty child hashes
    return SHA512Half(data);
}

Example:

Inner node has children 0, 3, 7, 15:

mBranches[0] → child hash: 0xAA11...
mBranches[3] → child hash: 0xBB22...
mBranches[7] → child hash: 0xCC33...
mBranches[15] → child hash: 0xDD44...

Compute hash:
  data = [0xAA11...][0xBB22...][0xCC33...][0xDD44...]
  hash = SHA512Half(data)
  result: 0x5678...   (all values illustrative, not real hashes)

Hash Update Process

When tree is modified, hashes must be recomputed bottom-up:

Critical Property: All Hashes Change

Change 1 account → 1 leaf hash changes
                 → parent hash changes
                 → grandparent hash changes
                 → ... all ancestors up to root change

Root hash changes with certainty

This is why root hash is used as the ledger's cryptographic commitment. Change anything in the ledger → root hash changes.

Merkle Tree Properties

Property 1: O(1) Subtree Comparison

Two complete SHAMaps can be compared by comparing single 256-bit values:

bool sameLedgerState = (treeA.getRootHash() == treeB.getRootHash());

if (sameLedgerState) {
    // Entire trees identical
    // Verified cryptographically
} else {
    // At least one difference
    // Must investigate child hashes to find it
}

Implication:

Peers can quickly determine if their ledgers match:

Peer A: "My ledger root is 0xABCD..."
Peer B: "My ledger root is 0xABCD..."

Comparison: 1 operation
Result: "Ledgers identical" (proven cryptographically)

No need to compare millions of accounts

Property 2: Efficient Difference Detection

If root hashes differ, child hashes pinpoint the differences:

Root hash differs: 0xABCD != 0xXYZW

Compare children:
  Child 0: 0xAA == 0xAA (same)
  Child 1: 0xBB == 0xBB (same)
  Child 2: 0xCC != 0xXX (different!)
  Child 3: 0xDD == 0xDD (same)
  ...

Recursively descend into Child 2 and its siblings

Eventually reach specific accounts that differ

Search Complexity:

Complete recount:      O(N) comparisons (N = number of accounts)
Merkle tree method:    O(log N) comparisons (log_16 of N)

Example: 1M accounts = 64 bits / 4 bits per level
Binary search depth = 20
Radix-16 Merkle depth = 5

Merkle method: 5 hash comparisons to find differences
vs. 1,000,000 account comparisons

Property 3: Cryptographic Proofs

Prove that a specific item is in the tree:

// Prove Account A exists in tree with root hash R

MerkleProof proof;  // Vector of serialized nodes

std::optional<std::vector<Blob>> getProofPath(uint256 key) {
    std::vector<Blob> path;

    std::shared_ptr<SHAMapTreeNode> node = mRoot;

    for (int depth = 0; depth < 64; ++depth) {
        // Serialize current node
        Blob serialized = node->serialize();
        path.push_back(serialized);

        if (auto leaf = std::dynamic_pointer_cast<SHAMapLeafNode>(node)) {
            // Reached target leaf
            return path;
        }

        // Descend to next node following key
        auto inner = std::dynamic_pointer_cast<SHAMapInnerNode>(node);
        int branch = key.nthNibble(depth);
        node = inner->getChild(branch);

        if (!node) {
            return std::nullopt;  // Key not found
        }
    }

    return std::nullopt;
}

Proof Verification:

bool verifyProofPath(
    uint256 key,
    uint256 expectedRootHash,
    std::vector<Blob> proof)
{
    // Start from leaf end of proof
    auto leafNode = deserialize(proof.back());

    // Verify leaf contains the key
    if (leafNode->getKey() != key) {
        return false;
    }

    uint256 computedHash = leafNode->computeHash();

    // Move from leaf toward root
    for (int i = proof.size() - 2; i >= 0; --i) {
        auto innerNode = deserialize(proof[i]);

        // Verify the branch we came from
        int depth = i;  // Depth in tree
        int branch = key.nthNibble(depth);

        // Child hash must match computed hash
        if (innerNode->getChildHash(branch) != computedHash) {
            return false;
        }

        // Compute this node's hash
        computedHash = innerNode->computeHash();
    }

    // Verify final hash matches expected root
    return (computedHash == expectedRootHash);
}

Proof Size:

Tree with 1M accounts:
  Depth: log_16(1M) ≈ 5

Proof includes:
  1 leaf node: ~50-100 bytes
  5 inner nodes: ~100 bytes each
  Total: ~600 bytes

Compare to:
  Sending all accounts: millions of bytes
  Merkle proof: <1 KB

Verification requires hashing ~5 nodes
vs. hashing millions of accounts

Use Cases:

1. Light Clients: Verify account state without full ledger
2. Cross-Chain Bridges: Prove XRPL state to other chains
3. Auditing: Prove specific transactions were executed

Mutable Tree Operations

When constructing a new ledger, trees must support modifications:

Adding a New Leaf

void addLeaf(uint256 key, SHAMapItem item) {
    auto leaf = std::make_shared<SHAMapLeafNode>(key, item);
    leaf->setCowID(mCowID);  // Mark as owned by this tree

    std::shared_ptr<SHAMapTreeNode> node = mRoot;

    // Navigate to position
    for (int depth = 0; depth < 64; ++depth) {
        if (auto inner = std::dynamic_pointer_cast<SHAMapInnerNode>(node)) {
            int branch = key.nthNibble(depth);
            auto child = inner->getChild(branch);

            if (!child) {
                // Empty slot - insert leaf here
                inner = unshareNode(inner);  // Copy-on-write
                inner->setChild(branch, leaf);
                updateHashes(inner);  // Recompute hashes up to root
                return;
            } else if (auto childLeaf =
                      std::dynamic_pointer_cast<SHAMapLeafNode>(child)) {
                // Slot occupied by another leaf
                // Need to split into inner node
                // ... (complex branch splitting logic)
            }

            node = child;
        }
    }
}

Hash Updates

After modification, hashes propagate up:

void updateHashes(std::shared_ptr<SHAMapInnerNode> node) {
    uint256 oldHash = node->getHash();
    uint256 newHash = node->computeHash();

    if (oldHash == newHash) {
        return;  // Nothing changed
    }

    // Find parent
    auto parent = node->getParent();
    if (parent) {
        // Update parent's reference to this node
        int branch = node->getNodeID().getNibbleAtDepth(
            node->getDepth() - 1);
        parent->setChildHash(branch, newHash);

        // Recursively update parent
        updateHashes(parent);
    } else {
        // This is root - update root hash
        mRootHash = newHash;
    }
}

Summary

This module opened up the SHAMap, the Merkle-Patricia tree that holds all XRPL state. You learned its two node types (inner and leaf), how a 256-bit key walks the tree four bits at a time (up to 64 levels deep, fan-out 16), how hashes roll up to a single root, and how copy-on-write gives cheap immutable snapshots. This is the structure that makes the whole ledger tamper-evident.

To remember:

• SHAMap = Merkle tree + radix-16 Patricia trie holding all ledger state
• Two node kinds: SHAMapInnerNode (up to 16 children) and SHAMapLeafNode (holds the item)
• 256-bit key walked one nibble per level: fan-out 16, max depth 64
• SHAMapNodeID encodes a node's position (depth + path)
• Hashes roll up: child hashes feed the inner-node hash, up to a single root
• Copy-on-write gives an immutable snapshot per ledger version
• Code: include/xrpl/shamap, src/libxrpl/shamap
• Watch out: node hashes include domain prefixes; a leaf's hash is not just the item's hash

Next up. One hash fingerprints the whole tree; that is exactly what makes trees comparable across the network. Next: how two nodes synchronize SHAMaps by exchanging only what differs, and how a tiny proof convinces anyone of anything.