SHAMap synchronization & proofs

Introduction

≈60 min · Advanced · builds on SHAMap architecture & hashing

A tree of hashes isn't just tidy, it's what lets nodes agree cheaply and clients verify without trusting anyone. In this module you'll see how two nodes sync by comparing subtree hashes instead of whole datasets, and how a compact Merkle proof lets a light client confirm a single entry really is in the ledger. It's the SHAMap's superpower, put to work.

Traversal Algorithms

In brief: how to walk two trees in parallel to find exactly where they differ.

SHAMap provides multiple traversal strategies depending on the use case:

Depth-First Traversal: visitNodes

The visitNodes method provides complete tree traversal:

void SHAMap::visitNodes(
    std::function<void(SHAMapTreeNode*)> callback)
{
    std::stack<std::shared_ptr<SHAMapTreeNode>> toVisit;
    toVisit.push(mRoot);

    while (!toVisit.empty()) {
        auto node = toVisit.top();
        toVisit.pop();

        callback(node);

        // Process inner node's children
        if (auto inner = std::dynamic_pointer_cast<SHAMapInnerNode>(node)) {
            for (int i = 15; i >= 0; --i) {  // Reverse order for stack
                if (auto child = inner->getChild(i)) {
                    toVisit.push(child);
                }
            }
        }
    }
}

Use Cases:

• Tree validation (verify all hashes)
• Bulk operations on all nodes
• Custom tree analysis

Leaf-Only Traversal: visitLeaves

void SHAMap::visitLeaves(
    std::function<void(SHAMapItem const&)> callback)
{
    visitNodes([this, &callback](SHAMapTreeNode* node) {
        if (auto leaf = dynamic_cast<SHAMapLeafNode*>(node)) {
            callback(leaf->getItem());
        }
    });
}

Iterator-Based Traversal

for (auto it = shamap.begin(); it != shamap.end(); ++it) {
    // Access SHAMapItem via *it
    // Iteration order matches key ordering
}

Parallel Traversal: walkMapParallel

For performance-critical operations:

void SHAMap::walkMapParallel(
    std::function<void(SHAMapTreeNode*)> callback,
    int numThreads)
{
    // Divide tree into subtrees
    // Process subtrees concurrently
    // Aggregate results
}

Use Cases:

• Missing node detection at scale
• High-throughput synchronization

Missing Node Detection

In brief: how a node discovers which subtrees it still needs from a peer.

The core synchronization primitive identifies nodes needed for complete tree reconstruction:

Algorithm: getMissingNodes

std::vector<std::pair<SHAMapNodeID, uint256>>
SHAMap::getMissingNodes(
    std::function<bool(uint256 const&)> nodeAvailable)
{
    std::vector<std::pair<SHAMapNodeID, uint256>> missing;

    std::stack<SHAMapNodeID> toVisit;
    toVisit.push(SHAMapNodeID(0));  // Root node

    while (!toVisit.empty() && missing.size() < MAX_RESULTS) {
        SHAMapNodeID nodeID = toVisit.top();
        toVisit.pop();

        // Check if we have this node
        auto node = getNode(nodeID);
        if (!node) {
            missing.push_back({nodeID, getExpectedHash(nodeID)});
            continue;
        }

        // For inner nodes, check children
        if (auto inner = dynamic_cast<SHAMapInnerNode*>(node.get())) {
            for (int branch = 0; branch < 16; ++branch) {
                uint256 childHash = inner->getChildHash(branch);
                if (childHash.isValid()) {
                    // Child should exist
                    if (!nodeAvailable(childHash)) {
                        // Child is missing
                        SHAMapNodeID childID = nodeID.getChildNodeID(branch);
                        toVisit.push(childID);
                    }
                }
            }
        }
    }

    return missing;
}

Output:

Returns vector of (NodeID, Hash) pairs representing missing nodes, prioritized for network retrieval.

Full Below Optimization

An optimization preventing redundant traversal:

class SHAMapInnerNode {
    // Generation counter: when this subtree was marked "complete"
    std::uint32_t mFullBelow = 0;
};

if (node->mFullBelow == currentGeneration) {
    // Entire subtree known complete
    // Skip traversal
    continue;
}

When a subtree is verified complete (all descendants present), skip traversing it again until a new sync starts.

Node Addition and Canonicalization

Adding the Root Node: addRootNode

Initializes or verifies the root node:

SHAMapAddNode SHAMap::addRootNode(
    uint256 const& hash,
    Blob const& nodeData,
    SHANodeFilter* filter = nullptr)
{
    // Check if root already exists with matching hash
    if (mRoot && mRoot->getHash() == hash) {
        return SHAMapAddNode::duplicate();
    }

    // Validate and deserialize
    auto node = deserializeNode(nodeData, SHAMapNodeID(0));
    if (!node) {
        return SHAMapAddNode::invalid();
    }

    // Canonicalize: ensure uniqueness in cache
    canonicalizeNode(node);

    // Set as root
    mRoot = std::dynamic_pointer_cast<SHAMapInnerNode>(node);

    if (filter) {
        filter->foundNode(hash);
    }

    return SHAMapAddNode::useful();
}

Adding Known Nodes: addKnownNode

Adds interior or leaf nodes during synchronization:

SHAMapAddNode SHAMap::addKnownNode(
    SHAMapNodeID const& nodeID,
    Blob const& nodeData,
    SHANodeFilter* filter = nullptr)
{
    // Deserialize node
    auto newNode = deserializeNode(nodeData, nodeID);
    if (!newNode) {
        return SHAMapAddNode::invalid();
    }

    // Canonicalize (prevent duplicate nodes in memory)
    canonicalizeNode(newNode);

    // Navigate from root to parent
    auto parent = getNode(nodeID.getParentNodeID());
    if (!parent || !parent->isInner()) {
        return SHAMapAddNode::invalid();
    }

    // Verify hash matches before insertion
    int branch = nodeID.getBranch();
    if (parent->getChildHash(branch) != newNode->getHash()) {
        return SHAMapAddNode::invalid();
    }

    // Insert into tree
    auto parentInner = std::dynamic_pointer_cast<SHAMapInnerNode>(parent);
    parentInner->setChild(branch, newNode);

    if (filter) {
        filter->foundNode(newNode->getHash());
    }

    return SHAMapAddNode::useful();
}

Canonicalization

Purpose:

Ensure nodes are unique in memory (one NodeObject per hash):

std::shared_ptr<SHAMapTreeNode>
SHAMap::canonicalizeNode(std::shared_ptr<SHAMapTreeNode> node)
{
    uint256 hash = node->getHash();

    // Check cache for existing node
    auto cached = mNodeCache->get(hash);
    if (cached) {
        return cached;  // Use cached instance
    }

    // New node - insert into cache
    mNodeCache->insert(hash, node);
    return node;
}

Benefits:

1. Memory Efficiency: Identical nodes stored once
2. Thread Safety: Cache handles concurrent insertion atomically
3. Fast Equality: Compare pointers instead of content
4. Shared Trees: Multiple SHAMaps can share nodes

Synchronization Scenario

In brief: a worked example of syncing state by comparing hashes, not whole datasets.

The Complete Flow:

Performance Metrics:

Small ledger (100k accounts):
  Nodes in tree: ~20,000
  Network requests: ~20,000 (batch fetch reduces count)
  Time to sync: seconds to minutes

Large ledger (10M accounts):
  Nodes in tree: ~2,000,000
  Network requests: ~100,000 (batching and parallel)
  Time to sync: hours to days

State Reconstruction Guarantee

In brief: why the pieces you fetch can be trusted to rebuild the exact state.

The transaction tree, persisted in NodeStore, ensures unique history:

Problem:

Without transaction history, many sequences could produce same state:

Solution:

The transaction tree proves the exact sequence:

Ledger header contains:
  - Account state tree root (current balances)
  - Transaction tree root (complete history)

Given state tree root + transaction tree root:
  Can verify exact sequence that produced this state
  No ambiguity about what happened

NodeStore's Role:

Both tree nodes are persisted:

• Query state tree to find current values
• Query transaction tree to find history
• Together: complete, verifiable record

Key idea. A Merkle proof lets a client verify that one entry belongs to a state root without downloading the whole ledger, which is what makes light verification possible.

Cryptographic Proofs and State Reconstruction

Introduction

The combination of SHAMap and NodeStore provides more than just efficient storage, they enable cryptographic proofs that transactions were executed correctly and state was computed honestly.

This chapter explores:

• Merkle proof generation and verification
• State reconstruction from transaction history
• Cross-chain or light-client verification
• The guarantee of verifiable ledger history

Merkle Proof Generation

A Merkle proof allows someone to verify that data is in a tree without reconstructing the entire tree.

Algorithm: getProofPath

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

    auto node = std::dynamic_pointer_cast<SHAMapInnerNode>(mRoot);

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

        // Is this the target leaf?
        if (auto leaf = std::dynamic_pointer_cast<SHAMapLeafNode>(node)) {
            if (leaf->getKey() == key) {
                return path;  // Success
            } else {
                return std::nullopt;  // Wrong leaf
            }
        }

        // Navigate to next level
        int branch = key.nthNibble(depth);
        node = std::dynamic_pointer_cast<SHAMapInnerNode>(
            node->getChild(branch));

        if (!node) {
            return std::nullopt;  // Path doesn't exist
        }
    }

    return std::nullopt;  // Shouldn't reach here
}

Example Proof:

For an account with key 0x3A7F2E1B...:

Proof path (from root to leaf):

[0]: Inner node (root)
     Hash: 0x1234... (all state)
     Children: [3 -> 0xABCD..., 5 -> 0x5678..., ...]

[1]: Inner node (depth 1, branch 3)
     Hash: 0xABCD... (state with branch 3)
     Children: [A -> 0xEF12..., B -> 0x3456..., ...]

[2]: Inner node (depth 2, branch A)
     Hash: 0xEF12... (state with branch 3, then A)
     Children: [7 -> 0x7890..., ...]

[3]: Inner node (depth 3, branch 7)
     Hash: 0x7890... (state with branch 3, A, 7)
     Children: [F -> 0x8765..., ...]

[4]: Leaf node
     Content: {Account, Data}
     Hash: 0x8765... (account data)

Total: 5 nodes (including leaf)
Size: ~500 bytes for 5 serialized nodes

Proof Size Properties:

Tree size: 1 million accounts
Tree depth: log_16(1M) ≈ 5 levels

Proof includes:
  5 inner nodes + 1 leaf: ~100 bytes per node
  Total: ~600 bytes

Without proof:
  Send all 1M accounts: gigabytes

Proof is logarithmic in tree size
Verification requires one hash per level: O(log N)

Proof Verification

Verifying a proof requires only the root hash and the proof:

Algorithm: verifyProofPath

bool verifyProofPath(
    uint256 const& key,
    uint256 const& expectedRootHash,
    std::vector<Blob> const& proof)
{
    if (proof.empty()) {
        return false;
    }

    // Start from leaf (last in proof)
    auto leafNode = deserializeNode(proof.back(), /* leaf */);
    if (!leafNode || leafNode->getKey() != key) {
        return false;
    }

    // Compute leaf hash
    uint256 computedHash = leafNode->computeHash();

    // Walk from leaf toward root
    for (int i = (int)proof.size() - 2; i >= 0; --i) {
        auto innerNode = deserializeNode(proof[i], /* inner */);
        if (!innerNode) {
            return false;
        }

        // Determine which branch we came from
        int depth = i;
        int branch = key.nthNibble(depth);

        // Verify the child hash matches
        if (innerNode->getChildHash(branch) != computedHash) {
            return false;  // Proof is invalid
        }

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

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

Verification Process:

Proof Use Cases

State Reconstruction Guarantee

The transaction tree provides a critical guarantee: verifiable unique history.

The Problem Without Transaction Tree:

The Solution: Transaction Tree

The XRP Ledger maintains both trees in every ledger:

struct LedgerHeader {
    uint256 accountTreeHash;      // Root of account state
    uint256 transactionTreeHash;  // Root of transaction history

    // Both are cryptographically committed
    // Both are signed by validators
    // Both must match
};

State Reconstruction:

Why This Matters:

Without verification: Anyone could claim different history
With verification: Only one possible history is correct

Example:
  Alice claims she sent 100 XRP to Bob
  Bob claims he received only 50 XRP

  Ledger history is immutable and verified
  Proof shows exactly what happened
  No ambiguity

Ledger Verifiability

Every aspect of XRPL state is cryptographically verifiable:

Account Proof

Prove: Account has balance 1000 XRP

Components:
  1. Ledger header with account state root
  2. Merkle proof from root to account leaf
  3. Account data (balance, etc.)

Verification:
  Verify proof leads from root to account
  Account balance is in proof
  Root hash signed by supermajority of validators

Transaction Proof

Prove: Transaction T was executed in ledger L

Components:
  1. Ledger L header with transaction tree root
  2. Merkle proof from root to transaction leaf
  3. Transaction data and execution results

Verification:
  Verify proof leads from root to transaction
  Matches all known transaction identifiers
  Root hash signed by validators

Full Ledger Proof

Prove: Ledger state transitions from L1 to L2

Components:
  1. L1 ledger header (initial state)
  2. All transactions between L1 and L2
  3. L2 ledger header (final state)

Verification:
  1. Verify all transaction proofs against L2
  2. Verify all account proofs against L2
  3. Verify L2 header is valid

Result: Complete proof that L2 is correct result of applying
        all transactions to L1

Practical Verification Workflow

Step 1: Trust the Ledger Header

// Ledger headers are small (~100 bytes)
// Signed by supermajority (>80%) of validators
// Distributed via gossip protocol

LedgerHeader verified_header = getLedgerHeader(ledgerSeq);
// Root hashes are in verified_header

Step 2: Request Proof

Conceptual illustration, not literal rippled APIs: the SHAMap does not expose a MerkleProof type or a requestProof call by these names. The snippet shows the idea, not copy-paste code.

// Client requests proof of account existence (conceptual)
MerkleProof proof = peer.requestProof(
    accountID,
    verified_header.accountStateRoot);

// Proof is small (~500 bytes)

Step 3: Verify Proof

// Client verifies locally (no network needed)
if (verifyProofPath(accountID,
                    verified_header.accountStateRoot,
                    proof)) {
    // Account exists and is proven
    // Can trust all data in proof
    auto account = parseAccountFromProof(proof);
}

Step 4: Use Verified Data

// Application can now use the verified account data
// with absolute confidence it's correct
double balance = account.balance;  // Proven correct

Summary

This module put the SHAMap to work. You saw how two nodes synchronise by comparing subtree hashes and fetching only what differs, instead of exchanging whole datasets, and how a compact Merkle proof lets a light client verify that a single entry belongs to a state root without holding the full ledger. Matching root hashes prove identical state; that is the SHAMap's superpower.

To remember:

• Sync = compare subtree hashes top-down and fetch only what differs
• getMissingNodes walks the tree to list exactly what to request from peers
• Nodes are canonicalized: one in-memory instance per hash
• The full-below optimization skips subtrees already known complete
• A Merkle proof = the leaf plus sibling hashes up to the root; verify by recomputing the root
• Proofs let a light client verify one entry without holding the ledger
• Same root hash = nothing to sync at all
• Watch out: a proof only proves inclusion against THAT root; always check the root belongs to a validated ledger

Next up. Every node you synced from stored those tree nodes somewhere. Where, exactly? Next: the NodeStore, the key-value heart of rippled's persistence.