Navigation, Hashing, and Merkle Properties

← Back to SHAMap and NodeStore: Data Persistence and State Management

---

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...

Hash Update Process

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

Scenario: Account0 balance changes

Step 1: Leaf changes
  Old: Account0 leaf hash = 0xOLD1
  New: Account0 leaf hash = 0xNEW1

Step 2: Parent recomputes
  Parent stored hash references to all 16 children
  One changed: [0xAAA][0xNEW1][0xBBB]...
  Old parent hash: 0xOLD2
  New parent hash: 0xNEW2

Step 3: Grandparent recomputes
  Parent hash changed: 0xOLD2 → 0xNEW2
  Grandparent's child references change: [...][0xNEW2][...]
  Old grandparent hash: 0xOLD3
  New grandparent hash: 0xNEW3

... propagates up to root

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

Navigation:

• Keys determine paths through tree

• O(1) expected lookup time

• Fixed depth ensures bounded operations

Hashing:

• Leaves hash their data with type prefixes

• Inner nodes hash their children's hashes

• Changes propagate bottom-up to root

Merkle Properties:

• O(1) tree comparison through root hash

• O(log N) difference detection

• O(log N) proof generation and verification

Performance:

• Single account lookup: microseconds (tree traversal)

• Root hash computation: milliseconds (hash all changed nodes)

• Proof verification: thousands of hashes (proof depth)

These properties make SHAMap practical for blockchain state management: efficient updates, verifiable state, and fast synchronization.