> For the complete documentation index, see [llms.txt](https://docs.xrpl-commons.org/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.xrpl-commons.org/core-dev-bootcamp/module03/shamap-architecture.md). # SHAMap Architecture and Node Hierarchy [← Back to SHAMap and NodeStore: Data Persistence and State Management](/core-dev-bootcamp/module03.md) *** ### Introduction Now that you understand the mathematical foundations of Merkle-Patricia tries, let's explore how XRPL actually implements them in the SHAMap data structure. The SHAMap is responsible for: * Maintaining account and transaction state in a cryptographically-verified Merkle tree * Computing root hashes that represent entire ledger state * Enabling efficient navigation through key-based lookups * Supporting snapshots and immutability for historical ledgers * Providing proof generation for trustless state verification This chapter covers the architectural overview and node types. Later chapters dive into specific algorithms for navigation, hashing, and synchronization. {% embed url="" %} ### Core Design Principles 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 A SHAMap instance represents a complete tree of ledger state: **Core Data:** ```cpp class SHAMap { // The root node (always an inner node) std::shared_ptr 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 mFamily; }; ``` **Key Properties:** * **Root Node**: Always an inner node, never a leaf (even if only one account, still has inner structure) * **Depth**: Exactly 64 levels (256-bit keys ÷ 4 bits per level) * **Navigation Determinism**: Any key uniquely determines its path from root to leaf ### Node Hierarchy The SHAMap consists of three conceptual layers: **Layer 1: Root** ``` [Inner Node - Root] (hashes all state) ``` * 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 Node - Root] / | \ ... \ [Inner] [Inner] [Inner] ... [Inner] / | \ / | \ [Inner][Inner][Inner] ``` * 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** ``` [Inner Node] / | \ ... \ [Leaf][Leaf][Leaf] | | | Account Account Account State State State ``` * Terminal nodes containing actual data items * Types: Account state, Transaction, Transaction+Metadata * All leaves in a SHAMap tree are homogeneous (same type) ### Inner Nodes Inner nodes form the branching structure: **Structure:** ```cpp class SHAMapInnerNode { // Up to 16 child slots (indexed 0-F) std::array 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 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 Leaf nodes store the actual blockchain data: **Base Properties:** ```cpp class SHAMapLeafNode { // The data contained in this leaf std::shared_ptr mItem; // Cryptographic hash uint256 mHash; // For copy-on-write std::uint32_t mCowID; }; ``` **SHAMapItem Structure:** ```cpp 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** (hotACCOUNT\_NODE) * 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** (hotTRANSACTION\_NODE) * Store transaction data * Do not include execution metadata * Immutable once added to ledger * Enable verification of transaction history **3. Transaction+Metadata Leaves** (hotTRANSACTION\_LEDGER\_ENTRY) * 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?** ```cpp // 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 Every node in the tree is uniquely identified by its position: **Components:** ```cpp 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: ```cpp SHAMapNodeID parent(depth=2, nodeID=0x3A00...); SHAMapNodeID child = parent.getChildNodeID(7); // Result: depth=3, nodeID=0x3A70... ``` **selectBranch(nodeID, key)** - Determine which branch to follow: ```cpp 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 SHAMaps exist in different states reflecting their role in the system: **Immutable State** ```cpp 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** ```cpp 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** ```cpp 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:** ``` New Tree | v [Synching] <-- Receiving nodes from peers | +--> [Immutable] <-- Finalized ledger | +--> [Modifying] <-- New transactions incoming ``` ### Copy-on-Write Mechanism 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: ```cpp // 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 SHAMap is designed for in-memory operation, but nodes can be persisted: **Persistent Nodes:** Some nodes are marked as "backed" - they exist in NodeStore: ```cpp // Node came from persistent storage mNode->setBacked(); // When synchronizing, try to retrieve from storage std::shared_ptr node = nodestore.fetch(hash); if (node) { // Add to tree canonicalizeNode(node); // Ensure uniqueness } ``` **Canonicalization:** Ensures nodes are unique in memory: ```cpp // Check cache for existing node with same hash std::shared_ptr 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) ### Summary **Key Architectural Elements:** 1. **SHAMap Instance**: Complete tree representing one ledger version 2. **Inner Nodes**: Branching structure with 0-16 children, storing hashes 3. **Leaf Nodes**: Terminal nodes containing account or transaction data 4. **SHAMapNodeID**: Identifies node position through depth and path 5. **State Management**: Immutable (historical), Mutable (work-in-progress), Synching (incomplete) 6. **Copy-on-Write**: Enables snapshots and safe sharing 7. **NodeStore Integration**: Persistent layer for large datasets **Design Properties:** * Perfect balance: All leaves at approximately same depth (log\_16 of account count) * Deterministic navigation: Key uniquely determines path * Immutable persistence: Historical ledgers safe from modification * Efficient sharing: Snapshots require minimal additional memory * Scalable: Handles millions of accounts with logarithmic operations In the next chapter, we'll explore how nodes are navigated, hashes are computed, and the tree structure is maintained.