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 and transaction maps, and their shared skeleton.

A SHAMap instance represents a complete tree of ledger state:

Core Data (from include/xrpl/shamap/SHAMap.h, trimmed):

class SHAMap
{
private:
    Family& f_;
    beast::Journal journal_;

    /** ID to distinguish this map for all others we're sharing nodes with. */
    std::uint32_t cowid_ = 1;

    /** The sequence of the ledger that this map references, if any. */
    std::uint32_t ledgerSeq_ = 0;

    SHAMapTreeNodePtr root_;
    mutable SHAMapState state_;
    SHAMapType const type_;
    bool backed_ = true;         // Map is backed by the database
    mutable bool full_ = false;  // Map is believed complete in database
};

A few things to note about the real members:

• root_ is a SHAMapTreeNodePtr — an intrusive pointer (intr_ptr::SharedPtr<SHAMapTreeNode>), not a std::shared_ptr. The constructors always install a SHAMapInnerNode there.
• state_ is a SHAMapState with four values: Modifying, Immutable, Synching, and Invalid (a map known to be bad, usually from synching a corrupt ledger).
• type_ is a SHAMapType: TRANSACTION, STATE, or FREE (see include/xrpl/shamap/SHAMapMissingNode.h).
• cowid_ starts at 1 and is never 0; more on this in the copy-on-write section below.

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 (from include/xrpl/shamap/SHAMapInnerNode.h, trimmed):

class SHAMapInnerNode final : public SHAMapTreeNode, public CountedObject<SHAMapInnerNode>
{
public:
    /** Each inner node has 16 children (the 'radix tree' part of the map) */
    static constexpr unsigned int kBranchFactor = 16;

private:
    /** Opaque type that contains the `hashes` array (array of type
       `SHAMapHash`) and the `children` array (array of type
       `intr_ptr::SharedPtr<SHAMapInnerNode>`).
     */
    TaggedPointer hashesAndChildren_;

    std::uint32_t fullBelowGen_ = 0;
    std::uint16_t isBranch_ = 0;
};

There is no per-branch struct: the child hashes and child pointers live in two arrays behind hashesAndChildren_ (a TaggedPointer that can store them sparsely or densely), and the 16-bit occupancy bitset is isBranch_. fullBelowGen_ is the synchronization generation marker. The node's own hash and its copy-on-write owner live in the base class (include/xrpl/shamap/SHAMapTreeNode.h):

class SHAMapTreeNode : public IntrusiveRefCounts
{
protected:
    SHAMapHash hash_;

    /** Determines the owning SHAMap, if any. Used for copy-on-write semantics.

        If this value is 0, the node is not dirty and does not need to be
        flushed. It is eligible for sharing and may be included multiple
        SHAMap instances.
     */
    std::uint32_t cowid_;
};

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. Neither carries a header string or a bitmap — the discriminator is a single wire-type byte at the end of the serialized node (kWireTypeInner = 2, kWireTypeCompressedInner = 3, defined in include/xrpl/shamap/SHAMapTreeNode.h).

Compressed Format (used when the node is sparse):

For each non-empty branch:
  Child hash (32 bytes)
  Branch number (1 byte)
Trailing byte: kWireTypeCompressedInner (3)

Saves space by omitting empty branches.

Full Format (used when most slots are occupied):

For each of 16 branches:
  Child hash (32 bytes; the zero hash for an empty branch)
Trailing byte: kWireTypeInner (2)

Simpler structure despite larger size.

Format Selection Algorithm:

The choice is made on the branch count, in SHAMapInnerNode::serializeForWire (src/libxrpl/shamap/SHAMapInnerNode.cpp):

void
SHAMapInnerNode::serializeForWire(Serializer& s) const
{
    XRPL_ASSERT(!isEmpty(), "xrpl::SHAMapInnerNode::serializeForWire : is non-empty");

    // If the node is sparse, then only send non-empty branches:
    if (getBranchCount() < 12)
    {
        // compressed node
        auto hashes = hashesAndChildren_.getHashes();
        iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
            s.addBitString(hashes[indexNum].asUInt256());
            s.add8(branchNum);
        });
        s.add8(kWireTypeCompressedInner);
    }
    else
    {
        iterChildren([&](SHAMapHash const& hh) { s.addBitString(hh.asUInt256()); });
        s.add8(kWireTypeInner);
    }
}

So compressed covers 1-11 branches and full covers 12-16. An inner node with 0 branches is never wire-serialized at all — the XRPL_ASSERT(!isEmpty(), ...) at the top rules it out.

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 (from include/xrpl/shamap/SHAMapLeafNode.h, trimmed):

class SHAMapLeafNode : public SHAMapTreeNode
{
protected:
    boost::intrusive_ptr<SHAMapItem const> item_;

public:
    boost::intrusive_ptr<SHAMapItem const> const&
    peekItem() const;
};

The hash (hash_) and copy-on-write owner (cowid_) again come from the SHAMapTreeNode base class.

SHAMapItem Structure (from include/xrpl/shamap/SHAMapItem.h, trimmed):

// an item stored in a SHAMap
class SHAMapItem : public CountedObject<SHAMapItem>
{
private:
    uint256 const tag_;

    // We use std::uint32_t to minimize the size; there's no SHAMapItem whose
    // size exceeds 4GB and there won't ever be (famous last words?), so this
    // is safe.
    std::uint32_t const size_;

    // This is the reference count used to support boost::intrusive_ptr
    mutable std::atomic<std::uint32_t> refcount_ = 1;

public:
    uint256 const&
    key() const;

    Slice
    slice() const;
};

There is no Blob member: the payload bytes are slab-allocated immediately after the object itself, and slice() returns a view over them. tag_ (returned by key()) is the 256-bit identifier that determines the item's position in the tree, and reference counting is intrusive (boost::intrusive_ptr).

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 (HashPrefix::LeafNode) 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?

Each leaf type hashes its content under a different HashPrefix — a 4-byte value, three ASCII characters plus a zero byte (include/xrpl/protocol/HashPrefix.h). These are the three real updateHash implementations:

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

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

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

Even with identical bytes, the differing prefixes ('MLN\0', 'SND\0', 'TXN\0') produce different hashes, so moving data between leaf types would be immediately detected as invalid. Note the field order: prefix, then the item's data, then the key — and the plain transaction leaf hashes no key at all, because its hash is the transaction ID.

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 (from include/xrpl/shamap/SHAMapNodeID.h, trimmed):

/** Identifies a node inside a SHAMap */
class SHAMapNodeID : public CountedObject<SHAMapNodeID>
{
private:
    uint256 id_;
    unsigned int depth_ = 0;
};

Path Encoding:

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

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

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

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

Key Operations:

getChildNodeID(branch) - Compute child position:

// SHAMapNodeID getChildNodeID(unsigned int m) const;
SHAMapNodeID child = parent.getChildNodeID(7);
// For a parent at depth_=2, id_=0x3A00...:
// Result: depth_=3, id_=0x3A70...

selectBranch(id, hash) - Determine which branch to follow. This is a free function, not a member:

/** Returns the branch that would contain the given hash */
[[nodiscard]] unsigned int
selectBranch(SHAMapNodeID const& id, uint256 const& hash);

// For a node at depth 2 and key 0x3A7F2E1B4C9D...:
// selectBranch extracts the third nibble → branch 7

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

state_ == SHAMapState::Immutable;

• 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

Note: an immutable map still has a nonzero cowid_. The map's cowid_ is initialized to 1 and every snapshot gets a strictly larger one (cowid_(other.cowid_ + 1) in the snapshot constructor, src/libxrpl/shamap/SHAMap.cpp). A cowid of 0 is a property of individual nodes, marking a node as shareable — see the copy-on-write section below.

Mutable State

state_ == SHAMapState::Modifying;

• 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

state_ == SHAMapState::Synching;

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

There is also a fourth value, SHAMapState::Invalid, for a map that is known to not be valid (usually from synching a corrupt ledger).

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. When a mutable SHAMap needs to modify a node it does not own, it clones the node first. This is the real implementation, SHAMap::unshareNode (src/libxrpl/shamap/SHAMap.cpp):

template <class Node>
intr_ptr::SharedPtr<Node>
SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, SHAMapNodeID const& nodeID)
{
    // make sure the node is suitable for the intended operation (copy on write)
    XRPL_ASSERT(node->cowid() <= cowid_, "xrpl::SHAMap::unshareNode : node valid for cowid");
    if (node->cowid() != cowid_)
    {
        // have a CoW
        XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::unshareNode : not immutable");
        node = intr_ptr::staticPointerCast<Node>(node->clone(cowid_));
        if (nodeID.isRoot())
            root_ = node;
    }
    return node;
}

Node Sharing Rules:

node->cowid() == 0:      node is shared; it may appear in multiple SHAMap
                         instances and must not be modified
node->cowid() == cowid_: node is owned by this map (safe to modify in place)
node->cowid() != cowid_: node belongs to another map (clone 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
   

   Copy

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
   

   Copy

3. Memory Efficiency: Identical subtrees stored once

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

   Copy

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:

Whether a map is backed by the database is a property of the map, not of individual nodes:

// include/xrpl/shamap/SHAMap.h
bool backed_ = true;         // Map is backed by the database

When a backed map needs a node that is not in memory, it fetches the record from the NodeStore by hash (src/libxrpl/shamap/SHAMap.cpp):

SHAMapTreeNodePtr
SHAMap::fetchNodeFromDB(SHAMapHash const& hash) const
{
    XRPL_ASSERT(backed_, "xrpl::SHAMap::fetchNodeFromDB : is backed");
    auto obj = f_.db().fetchNodeObject(hash.asUInt256(), ledgerSeq_);
    return finishFetch(hash, obj);
}

finishFetch deserializes the record into a tree node and calls canonicalize(hash, node) before returning it.

Canonicalization:

Ensures nodes are unique in memory (illustrative sketch of what the family's tree-node cache does):

// Check cache for existing node with same hash
auto 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 libxrpl/shamap/SHAMap.cpp — descend one level from an inner node:
SHAMapTreeNode* child = descendThrow(inner, branch);

// Or look up a leaf item directly by key (public API in SHAMap.h):
boost::intrusive_ptr<SHAMapItem const> const& item = map.peekItem(key);

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)

• src/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
• src/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->getType() << 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 = 16384      # Cache for database records, in records (default 16384)
cache_age = 5           # Minutes to keep records cached (default 5)

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

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

Note: cache_size is a record count, not a byte size, and cache_age is in minutes. If online_delete is set, this cache is not created at all (the rotating NodeStore does not use it). See the comments in cfg/xrpld-example.cfg.

Common Configuration Patterns

# Small validator (less memory available)
[node_db]
cache_size = 8192
cache_age = 2

# Large validator (plenty of resources)
[node_db]
cache_size = 65536
cache_age = 15

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 (this is a simplified sketch; the real implementation is SHAMap::walkTowardsKey in src/libxrpl/shamap/SHAMap.cpp):

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. All node hashes use sha512Half (SHA-512 truncated to 256 bits, include/xrpl/protocol/digest.h) over a 4-byte HashPrefix plus the node's content, and are stored wrapped in SHAMapHash.

Leaf Node Hashing

Each leaf type computes its hash from a type-specific prefix and its item. These are the real updateHash implementations:

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

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

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

Note the order: prefix, then data (item_->slice()), then key (item_->key()) — and the plain transaction leaf omits the key entirely, because its hash is the transaction ID.

Example:

Account-state leaf: key=0x123ABC..., data=<serialized AccountRoot, 100 XRP>
Prefix: HashPrefix::LeafNode — 4 bytes: 'M','L','N',0x00

Hash input: ['M']['L']['N'][0x00][<data bytes>][123ABC...]
Hash output: 0x47FA... (256 bits)

Changed: balance to 99 XRP
Hash input: ['M']['L']['N'][0x00][<new data bytes>][123ABC...]
Hash output: 0xB8EF... (completely different)

Inner Node Hashing

Inner nodes hash HashPrefix::InnerNode followed by all 16 child hash slots — an empty branch contributes the zero hash. This is the real implementation, SHAMapInnerNode::updateHash (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<sha512_half_hasher::result_type>(h);
    }
    hash_ = SHAMapHash{nh};
}

iterChildren calls its callback "for all 16 (branchFactor) branches - even if the branch is empty" (include/xrpl/shamap/SHAMapInnerNode.h). Including the empty slots matters: if only the non-empty hashes were hashed, two nodes with the same children in different branch positions would collide. Also note the isBranch_ != 0 guard — an inner node with no children at all hashes to zero.

Example:

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

branch 0  → child hash 0xAA11...
branch 3  → child hash 0xBB22...
branch 7  → child hash 0xCC33...
branch 15 → child hash 0xDD44...
all other branches → zero hash (32 zero bytes each)

Compute hash:
  input = 'MIN\0' || hash(branch 0) || hash(branch 1) || ... || hash(branch 15)
          (all 16 slots, empty ones as the zero hash)
  hash  = sha512Half(input)
  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, 256-bit keys (64 nibbles, 4 bits per level)
Radix-2 (binary) tree depth to separate 1M items = log2(1M) = 20
Radix-16 Merkle depth = log16(1M) ≈ 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. The real API is SHAMap::getProofPath and SHAMap::verifyProofPath (include/xrpl/shamap/SHAMap.h); the sketches below show the idea:

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

// Real declaration:
// std::optional<std::vector<Blob>> getProofPath(uint256 const& key) const;

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:

// Real declaration:
// static bool verifyProofPath(
//     uint256 const& rootHash, uint256 const& key, std::vector<Blob> const& path);

bool verifyProofPath(
    uint256 rootHash,
    uint256 key,
    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 == rootHash);
}

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: an inner node hashes HashPrefix::InnerNode plus all 16 child hash slots (empties as the zero hash), up to a single root
• Copy-on-write gives an immutable snapshot per ledger version; a node with cowid 0 is shared, and a map's cowid_ is always nonzero
• Code: include/xrpl/shamap, src/libxrpl/shamap
• Watch out: node hashes include 4-byte domain prefixes; a leaf's hash is not just the item's hash (and a plain transaction leaf's hash is the transaction ID)

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.