refactor: Unify upperBound and lowerBound into boundHelper

The two functions were near duplicates: walk to the key, then look for the
nearest leaf on one side. Only the scan direction, the comparison deciding a
leaf qualifies, and whether to take the first or last leaf below the subtree
differed, exactly the distinction `BelowDirection` already draws for
`belowHelper`, so the pair collapse into one parameterised walk. Also drops
the stale `// TODO: what to return here?` above `lowerBound`'s `return end()`:
no predecessor is the correct answer for the smallest key, and the tests pin
it.

Existing coverage only exercised `boundHelper`'s inner-node branch, every test
map had at least three items, so the root was always an inner node and the
leaf branch at the top of the function was never reached with a real answer to
give. Adds coverage for a single-item map, where the leaf branch alone decides
the outcome, and an empty map, where the scan must find nothing on every
branch before falling through to `end()`.

Fixes the single-item test's own comment, which claimed `root_` becomes a
leaf, when in fact `root_` stays the inner node it was constructed with for
any map built via `addItem`; only a single-item map synced from a peer
(`addRootNode`) ever replaces `root_` with a leaf directly.

include/xrpl/shamap/SHAMap.h

@@ -420,7 +420,103 @@ public:
     invariants() const;
 
 private:
-    using SharedPtrNodeStack = std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>>;
+    /**
+     * A path from the root of the map down to some node, pairing each node with the ID naming its
+     * position.
+     *
+     * The two halves of an entry must agree, and the only way to get that wrong is to compute an ID
+     * from the wrong branch. So this type does not accept an ID at all: every push takes the branch
+     * being descended and derives the ID itself, so a node and its ID cannot disagree. Reads are
+     * exposed through the same accessors a std::stack would offer.
+     */
+    class NodePathStack
+    {
+    public:
+        [[nodiscard]] bool
+        empty() const
+        {
+            return stack_.empty();
+        }
+
+        [[nodiscard]] std::size_t
+        size() const
+        {
+            return stack_.size();
+        }
+
+        [[nodiscard]] std::pair<SHAMapTreeNodePtr, SHAMapNodeID> const&
+        top() const
+        {
+            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::top : non-empty stack");
+            return stack_.top();
+        }
+
+        void
+        pop()
+        {
+            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::pop : non-empty stack");
+            stack_.pop();
+        }
+
+        void
+        clear()
+        {
+            stack_ = {};
+        }
+
+        /**
+         * Start a path at the root of the map, whose ID is the zero-depth ID by definition.
+         */
+        void
+        pushRoot(SHAMapTreeNodePtr node)
+        {
+            XRPL_ASSERT(stack_.empty(), "xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
+            stack_.emplace(std::move(node), SHAMapNodeID{});
+        }
+
+        /**
+         * Extend the path to the child of the current node reached by `branch`.
+         *
+         * A node keeps the depth it was reached at, never a normalized kLeafDepth. Only a leaf may
+         * sit at kLeafDepth, since an inner node there would have no branch left to select.
+         */
+        void
+        pushChild(SHAMapTreeNodePtr node, unsigned int branch)
+        {
+            XRPL_ASSERT(node, "xrpl::SHAMap::NodePathStack::pushChild : non-null node input");
+            XRPL_ASSERT(
+                !stack_.empty(), "xrpl::SHAMap::NodePathStack::pushChild : non-empty stack");
+            auto childID = stack_.top().second.getChildNodeID(branch);
+            XRPL_ASSERT_IF(
+                node->isInner(),
+                childID.getDepth() < kLeafDepth,
+                "xrpl::SHAMap::NodePathStack::pushChild : inner node above leaf depth");
+            XRPL_ASSERT_IF(
+                node->isLeaf(),
+                childID.isPrefixOf(leafKey(*node)),
+                "xrpl::SHAMap::NodePathStack::pushChild : leaf key below branch");
+            stack_.emplace(std::move(node), std::move(childID));
+        }
+
+        /**
+         * Extend the path to a node lying on the path to `target`.
+         *
+         * For nodes not reached by descending a known branch: the walk tracks only the key it is
+         * heading for, or the node is newly created. Either way `target` selects the branch.
+         */
+        void
+        pushNode(SHAMapTreeNodePtr node, uint256 const& target)
+        {
+            if (stack_.empty())
+                pushRoot(std::move(node));
+            else
+                pushChild(std::move(node), selectBranch(stack_.top().second, target));
+        }
+
+    private:
+        std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>> stack_;
+    };
+
     using DeltaRef =
         std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
 
@@ -447,7 +543,7 @@ private:
      * Update hashes up to the root
      */
     void
-    dirtyUp(SharedPtrNodeStack& stack, uint256 const& target, SHAMapTreeNodePtr terminal);
+    dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr terminal);
 
     /**
      * Walk towards the specified id, returning the node.  Caller must check
@@ -455,7 +551,7 @@ private:
      * id
      */
     SHAMapLeafNode*
-    walkTowardsKey(uint256 const& id, SharedPtrNodeStack* stack = nullptr) const;
+    walkTowardsKey(uint256 const& id, NodePathStack* stack = nullptr) const;
     /**
      * Return nullptr if key not found
      */
@@ -482,27 +578,19 @@ private:
     SHAMapTreeNodePtr
     writeNode(NodeObjectType t, SHAMapTreeNodePtr node) const;
 
-    // returns the first item at or below this node
-    SHAMapLeafNode*
-    firstBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch = 0u) const;
-
-    // returns the last item at or below this node
-    SHAMapLeafNode*
-    lastBelow(
-        SHAMapTreeNodePtr node,
-        SharedPtrNodeStack& stack,
-        unsigned int branch = kBranchFactor) const;
-
-    // direction in which belowHelper scans an inner node's branches
+    // direction in which a scan walks an inner node's branches
     enum class BelowDirection { First, Last };
 
-    // helper function for firstBelow and lastBelow
+    /**
+     * Returns the first or last item at or below the node already on top of `stack`, extending
+     * `stack` with the path walked to reach it.
+     */
     SHAMapLeafNode*
-    belowHelper(
-        SHAMapTreeNodePtr node,
-        SharedPtrNodeStack& stack,
-        unsigned int branch,
-        BelowDirection direction) const;
+    belowHelper(NodePathStack& stack, BelowDirection direction) const;
+
+    // helper function for upperBound and lowerBound
+    ConstIterator
+    boundHelper(uint256 const& id, BelowDirection direction) const;
 
     // Simple descent
     // Get a child of the specified node
@@ -550,9 +638,9 @@ private:
     hasLeafNode(uint256 const& tag, SHAMapHash const& hash) const;
 
     SHAMapLeafNode const*
-    peekFirstItem(SharedPtrNodeStack& stack) const;
+    peekFirstItem(NodePathStack& stack) const;
     SHAMapLeafNode const*
-    peekNextItem(uint256 const& id, SharedPtrNodeStack& stack) const;
+    peekNextItem(uint256 const& id, NodePathStack& stack) const;
     bool
     walkBranch(
         SHAMapTreeNode* node,
@@ -697,7 +785,7 @@ public:
     using pointer = value_type const*;
 
 private:
-    SharedPtrNodeStack stack_;
+    NodePathStack stack_;
     SHAMap const* map_ = nullptr;
     pointer item_ = nullptr;
 
@@ -723,7 +811,7 @@ public:
 private:
     explicit ConstIterator(SHAMap const* map);
     ConstIterator(SHAMap const* map, std::nullptr_t);
-    ConstIterator(SHAMap const* map, pointer item, SharedPtrNodeStack&& stack);
+    ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack);
 
     friend bool
     operator==(ConstIterator const& x, ConstIterator const& y);
@@ -742,10 +830,7 @@ inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, std::nullptr_t) :
 {
 }
 
-inline SHAMap::ConstIterator::ConstIterator(
-    SHAMap const* map,
-    pointer item,
-    SharedPtrNodeStack&& stack)
+inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack)
     : stack_(std::move(stack)), map_(map), item_(item)
 {
 }

src/libxrpl/shamap/SHAMap.cpp

@@ -97,7 +97,7 @@ SHAMap::snapShot(bool isMutable) const
 }
 
 void
-SHAMap::dirtyUp(SharedPtrNodeStack& stack, uint256 const& target, SHAMapTreeNodePtr child)
+SHAMap::dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr child)
 {
     // walk the tree up from through the inner nodes to the root_
     // update hashes and links
@@ -126,29 +126,34 @@ SHAMap::dirtyUp(SharedPtrNodeStack& stack, uint256 const& target, SHAMapTreeNode
 }
 
 SHAMapLeafNode*
-SHAMap::walkTowardsKey(uint256 const& id, SharedPtrNodeStack* stack) const
+SHAMap::walkTowardsKey(uint256 const& id, NodePathStack* stack) const
 {
     XRPL_ASSERT(
         stack == nullptr || stack->empty(), "xrpl::SHAMap::walkTowardsKey : empty stack input");
     auto inNode = root_;
     SHAMapNodeID nodeID;
 
+    // Every node on this walk lies on the path to `id`, so the stack can derive each ID from the
+    // branch `id` selects at the node above it.
+    auto pushCurrent = [&] {
+        if (stack != nullptr)
+            stack->pushNode(inNode, id);
+    };
+
     while (inNode->isInner())
     {
-        if (stack != nullptr)
-            stack->emplace(inNode, nodeID);
+        pushCurrent();
 
-        auto const inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(inNode);
+        auto& inner = safeDowncast<SHAMapInnerNode&>(*inNode);
         auto const branch = selectBranch(nodeID, id);
-        if (inner->isEmptyBranch(branch))
+        if (inner.isEmptyBranch(branch))
             return nullptr;
 
-        inNode = descendThrow(*inner, branch);
+        inNode = descendThrow(inner, branch);
         nodeID = nodeID.getChildNodeID(branch);
     }
 
-    if (stack != nullptr)
-        stack->emplace(inNode, nodeID);
+    pushCurrent();
     return safeDowncast<SHAMapLeafNode*>(inNode.get());
 }
 
@@ -428,65 +433,40 @@ SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, SHAMapNodeID const& nodeID)
 }
 
 SHAMapLeafNode*
-SHAMap::belowHelper(
-    SHAMapTreeNodePtr node,
-    SharedPtrNodeStack& stack,
-    unsigned int branch,
-    BelowDirection direction) const
+SHAMap::belowHelper(NodePathStack& stack, BelowDirection direction) const
 {
-    if (node->isLeaf())
-    {
-        auto n = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
-        stack.push({node, {kLeafDepth, n->peekItem()->key()}});
-        return n.get();
-    }
-    auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
-    if (stack.empty())
-    {
-        stack.emplace(inner, SHAMapNodeID{});
-    }
-    else
-    {
-        stack.emplace(inner, stack.top().second.getChildNodeID(branch));
-    }
-    // `scanned` counts how many branches of `inner` we have examined; the branch we look at is
-    // derived from it, so no index ever goes out of range.
+    XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack input");
+    if (auto const& top = stack.top().first; top->isLeaf())
+        return safeDowncast<SHAMapLeafNode*>(top.get());
+
+    // The stack owns the node/ID pairing, so descending is only ever "push the branch we took".
+    // `scanned` counts how many branches of the current node we have examined; the branch we look
+    // at is derived from it, so no index ever goes out of range. `inner` tracks the node on top of
+    // the stack, which keeps it alive, so it only needs recomputing after a push.
+    auto* inner = safeDowncast<SHAMapInnerNode*>(stack.top().first.get());
     for (auto scanned = 0u; scanned < kBranchFactor;)
     {
         auto const childBranch =
             (direction == BelowDirection::Last) ? (kBranchFactor - 1u - scanned) : scanned;
 
-        if (!inner->isEmptyBranch(childBranch))
-        {
-            node.adopt(descendThrow(inner.get(), childBranch));
-            XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack");
-            if (node->isLeaf())
-            {
-                auto n = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
-                stack.push({n, {kLeafDepth, n->peekItem()->key()}});
-                return n.get();
-            }
-            inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
-            stack.emplace(inner, stack.top().second.getChildNodeID(branch));
-            scanned = 0u;  // descend and restart the scan on the new node
-        }
-        else
+        if (inner->isEmptyBranch(childBranch))
         {
             ++scanned;  // scan next branch
+            continue;
         }
+
+        stack.pushChild(descendThrow(*inner, childBranch), childBranch);
+
+        auto const& child = stack.top().first;
+        if (child->isLeaf())
+            return safeDowncast<SHAMapLeafNode*>(child.get());
+
+        inner = safeDowncast<SHAMapInnerNode*>(child.get());
+        scanned = 0u;  // descend and restart the scan on the new node
     }
     return nullptr;
 }
-SHAMapLeafNode*
-SHAMap::lastBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch) const
-{
-    return belowHelper(node, stack, branch, BelowDirection::Last);
-}
-SHAMapLeafNode*
-SHAMap::firstBelow(SHAMapTreeNodePtr node, SharedPtrNodeStack& stack, unsigned int branch) const
-{
-    return belowHelper(node, stack, branch, BelowDirection::First);
-}
+
 static boost::intrusive_ptr<SHAMapItem const> const kNoItem;
 
 boost::intrusive_ptr<SHAMapItem const> const&
@@ -529,36 +509,36 @@ SHAMap::onlyBelow(SHAMapTreeNode* node) const
 }
 
 SHAMapLeafNode const*
-SHAMap::peekFirstItem(SharedPtrNodeStack& stack) const
+SHAMap::peekFirstItem(NodePathStack& stack) const
 {
     XRPL_ASSERT(stack.empty(), "xrpl::SHAMap::peekFirstItem : empty stack input");
-    SHAMapLeafNode const* node = firstBelow(root_, stack);
+    stack.pushRoot(root_);
+    SHAMapLeafNode const* node = belowHelper(stack, BelowDirection::First);
     if (node == nullptr)
     {
-        while (!stack.empty())
-            stack.pop();
+        stack.clear();
         return nullptr;
     }
     return node;
 }
 
 SHAMapLeafNode const*
-SHAMap::peekNextItem(uint256 const& id, SharedPtrNodeStack& stack) const
+SHAMap::peekNextItem(uint256 const& id, NodePathStack& stack) const
 {
     XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::peekNextItem : non-empty stack input");
     XRPL_ASSERT(stack.top().first->isLeaf(), "xrpl::SHAMap::peekNextItem : stack starts with leaf");
     stack.pop();
     while (!stack.empty())
     {
-        auto [node, nodeID] = stack.top();
+        auto const [node, nodeID] = stack.top();
         XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::peekNextItem : another node is not leaf");
-        auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
+        auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
         for (auto i = selectBranch(nodeID, id) + 1; i < kBranchFactor; ++i)
         {
-            if (!inner->isEmptyBranch(i))
+            if (!inner.isEmptyBranch(i))
             {
-                node = descendThrow(*inner, i);
-                auto leaf = firstBelow(node, stack, i);
+                stack.pushChild(descendThrow(inner, i), i);
+                auto leaf = belowHelper(stack, BelowDirection::First);
                 if (leaf == nullptr)
                     Throw<SHAMapMissingNode>(type_, id);
                 XRPL_ASSERT(leaf->isLeaf(), "xrpl::SHAMap::peekNextItem : leaf is valid");
@@ -595,72 +575,59 @@ SHAMap::peekItem(uint256 const& id, SHAMapHash& hash) const
 }
 
 SHAMap::ConstIterator
-SHAMap::upperBound(uint256 const& id) const
+SHAMap::boundHelper(uint256 const& id, BelowDirection direction) const
 {
-    SharedPtrNodeStack stack;
+    // Walk back up the path to `id` looking for the nearest leaf on the requested side. At each
+    // inner node the branches beyond the one `id` takes hold the candidates; the first non-empty
+    // one is the closest, and the extreme leaf below it is the answer.
+    auto const searchingForward = direction == BelowDirection::First;
+
+    NodePathStack stack;
     walkTowardsKey(id, &stack);
     while (!stack.empty())
     {
-        auto [node, nodeID] = stack.top();
+        auto const [node, nodeID] = stack.top();
         if (node->isLeaf())
         {
-            auto leaf = safeDowncast<SHAMapLeafNode*>(node.get());
-            if (leaf->peekItem()->key() > id)
-                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+            auto const& item = safeDowncast<SHAMapLeafNode const&>(*node).peekItem();
+            if (searchingForward ? (item->key() > id) : (item->key() < id))
+                return ConstIterator(this, item.get(), std::move(stack));
         }
         else
         {
-            auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
-            for (auto branch = selectBranch(nodeID, id) + 1; branch < kBranchFactor; ++branch)
+            auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
+            auto const taken = selectBranch(nodeID, id);
+            auto const remaining = searchingForward ? (kBranchFactor - 1u - taken) : taken;
+
+            for (auto scanned = 0u; scanned < remaining; ++scanned)
             {
-                if (!inner->isEmptyBranch(branch))
-                {
-                    node = descendThrow(*inner, branch);
-                    auto leaf = firstBelow(node, stack, branch);
-                    if (leaf == nullptr)
-                        Throw<SHAMapMissingNode>(type_, id);
-                    return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
-                }
+                auto const branch =
+                    searchingForward ? (taken + 1u + scanned) : (taken - 1u - scanned);
+                if (inner.isEmptyBranch(branch))
+                    continue;
+
+                stack.pushChild(descendThrow(inner, branch), branch);
+                auto const leaf = belowHelper(stack, direction);
+                if (leaf == nullptr)
+                    Throw<SHAMapMissingNode>(type_, id);
+                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
             }
         }
         stack.pop();
     }
     return end();
 }
+
+SHAMap::ConstIterator
+SHAMap::upperBound(uint256 const& id) const
+{
+    return boundHelper(id, BelowDirection::First);
+}
+
 SHAMap::ConstIterator
 SHAMap::lowerBound(uint256 const& id) const
 {
-    SharedPtrNodeStack stack;
-    walkTowardsKey(id, &stack);
-    while (!stack.empty())
-    {
-        auto [node, nodeID] = stack.top();
-        if (node->isLeaf())
-        {
-            auto leaf = safeDowncast<SHAMapLeafNode*>(node.get());
-            if (leaf->peekItem()->key() < id)
-                return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
-        }
-        else
-        {
-            auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
-            for (auto branch = selectBranch(nodeID, id); branch > 0u;)
-            {
-                --branch;
-                if (!inner->isEmptyBranch(branch))
-                {
-                    node = descendThrow(*inner, branch);
-                    auto leaf = lastBelow(node, stack, branch);
-                    if (leaf == nullptr)
-                        Throw<SHAMapMissingNode>(type_, id);
-                    return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
-                }
-            }
-        }
-        stack.pop();
-    }
-    // TODO: what to return here?
-    return end();
+    return boundHelper(id, BelowDirection::Last);
 }
 
 bool
@@ -675,7 +642,7 @@ SHAMap::delItem(uint256 const& id)
     // delete the item with this ID
     XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::delItem : not immutable");
 
-    SharedPtrNodeStack stack;
+    NodePathStack stack;
     walkTowardsKey(id, &stack);
 
     if (stack.empty())
@@ -761,7 +728,7 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
     // add the specified item, does not update
     uint256 const tag = item->key();
 
-    SharedPtrNodeStack stack;
+    NodePathStack stack;
     walkTowardsKey(tag, &stack);
 
     if (stack.empty())
@@ -801,7 +768,7 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
 
         while ((b1 = selectBranch(nodeID, tag)) == (b2 = selectBranch(nodeID, otherItem->key())))
         {
-            stack.emplace(node, nodeID);
+            stack.pushNode(node, tag);
 
             // we need a new inner node, since both go on same branch at this
             // level
@@ -848,7 +815,7 @@ SHAMap::updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem cons
 
     XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::updateGiveItem : not immutable");
 
-    SharedPtrNodeStack stack;
+    NodePathStack stack;
     walkTowardsKey(tag, &stack);
 
     if (stack.empty())
@@ -1170,7 +1137,7 @@ SHAMap::invariants() const
     auto node = root_.get();
     XRPL_ASSERT(node, "xrpl::SHAMap::invariants : non-null root node");
     XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::invariants : root node is not leaf");
-    SharedPtrNodeStack stack;
+    NodePathStack stack;
     for (auto leaf = peekFirstItem(stack); leaf != nullptr;
          leaf = peekNextItem(leaf->peekItem()->key(), stack))
         ;

src/libxrpl/shamap/SHAMapNodeID.cpp

@@ -6,6 +6,7 @@
 #include <xrpl/protocol/Serializer.h>
 #include <xrpl/shamap/SHAMap.h>
 
+#include <algorithm>
 #include <cstddef>
 #include <optional>
 #include <stdexcept>
@@ -40,9 +41,39 @@ depthMask(unsigned int depth)
     return kMasks.entry[depth];
 }
 
+// The prefix of `key` at `depth`: the leading nibbles naming the subtree a node at that depth
+// identifies, with the remainder of the key masked off.
+static uint256
+maskedToDepth(uint256 const& key, unsigned int depth)
+{
+    return key & depthMask(depth);
+}
+
+// Whether `id` at `depth` is what `key` looks like once masked down to that depth, i.e.
+// whether an ID with this depth and id names a subtree that `key` falls under.
+static bool
+isPrefixOfAtDepth(uint256 const& id, unsigned int depth, uint256 const& key)
+{
+    return maskedToDepth(key, depth) == id;
+}
+
 // canonicalize the hash to a node ID for this depth
 SHAMapNodeID::SHAMapNodeID(unsigned int depth, uint256 const& hash) : id_(hash), depth_(depth)
 {
+    // Every SHAMapNodeID's depth is stored here, so this is the one place that can stop an
+    // out-of-range one from being kept: a depth past kLeafDepth would go on to index depthMask
+    // out of bounds, and getRawString would narrow it to a byte, silently renaming the node.
+    // Clamp rather than throw, since node IDs are built from peer-supplied depths on the ledger
+    // data path, where no caller catches an exception before it reaches a thread boundary.
+    if (depth_ > SHAMap::kLeafDepth)
+    {
+        // LCOV_EXCL_START
+        UNREACHABLE("xrpl::SHAMapNodeID::SHAMapNodeID : depth within tree");
+        depth_ = SHAMap::kLeafDepth;
+        id_ = maskedToDepth(id_, depth_);
+        // LCOV_EXCL_STOP
+    }
+
     XRPL_ASSERT(
         depth <= SHAMap::kLeafDepth, "xrpl::SHAMapNodeID::SHAMapNodeID : maximum depth input");
     XRPL_ASSERT(
@@ -89,7 +120,7 @@ SHAMapNodeID::getChildNodeID(unsigned int branch) const
 bool
 SHAMapNodeID::isPrefixOf(uint256 const& key) const
 {
-    return (key & depthMask(depth_)) == id_;
+    return isPrefixOfAtDepth(id_, depth_, key);
 }
 
 [[nodiscard]] std::optional<SHAMapNodeID>
@@ -102,9 +133,9 @@ deserializeSHAMapNodeID(void const* data, std::size_t size)
         unsigned int const depth = *(static_cast<unsigned char const*>(data) + 32);
         if (depth <= SHAMap::kLeafDepth)
         {
-            auto const id = uint256::fromVoid(data);
-
-            if (id == (id & depthMask(depth)))
+            // Reject a serialized ID carrying bits below its own depth. Checked before
+            // constructing, since the constructor asserts that same property.
+            if (auto const id = uint256::fromVoid(data); isPrefixOfAtDepth(id, depth, id))
                 ret.emplace(depth, id);
         }
     }
@@ -115,7 +146,11 @@ deserializeSHAMapNodeID(void const* data, std::size_t size)
 [[nodiscard]] unsigned int
 selectBranch(SHAMapNodeID const& id, uint256 const& hash)
 {
-    auto const depth = id.getDepth();
+    XRPL_ASSERT(id.getDepth() < SHAMap::kLeafDepth, "xrpl::selectBranch : depth below leaf depth");
+
+    // A depth-64 ID has no nibble left to select. Callers must not ask, but clamp anyway to keep
+    // the read below the end of the 32-byte key.
+    auto const depth = std::min(id.getDepth(), SHAMap::kLeafDepth - 1u);
     auto branch = static_cast<unsigned int>(*(hash.begin() + (depth / 2)));
 
     if ((depth & 1) != 0u)
@@ -134,8 +169,18 @@ selectBranch(SHAMapNodeID const& id, uint256 const& hash)
 SHAMapNodeID
 SHAMapNodeID::createID(unsigned int depth, uint256 const& key)
 {
-    XRPL_ASSERT(depth <= SHAMap::kLeafDepth, "xrpl::SHAMapNodeID::createID : valid depth");
-    return SHAMapNodeID(depth, key & depthMask(depth));
+    // The mask is chosen here, before the constructor runs, so the clamp there cannot cover this
+    // call: an out-of-range depth would index depthMask's table while still evaluating this
+    // argument. A public factory has to hold its own bound.
+    if (depth > SHAMap::kLeafDepth)
+    {
+        // LCOV_EXCL_START
+        UNREACHABLE("xrpl::SHAMapNodeID::createID : depth within tree");
+        depth = SHAMap::kLeafDepth;
+        // LCOV_EXCL_STOP
+    }
+
+    return SHAMapNodeID(depth, maskedToDepth(key, depth));
 }
 
 }  // namespace xrpl

src/libxrpl/shamap/SHAMapSync.cpp

@@ -143,6 +143,20 @@ SHAMap::visitDifferences(
         if (!function(*node))
             return;
 
+        // Nibbles run out at kLeafDepth, so only a leaf belongs there. A well-formed map never
+        // holds an inner node at that depth: addKnownNode marks the map invalid rather than hooking
+        // one in, and fetch-pack data is hash-verified against a validated root, so reaching this
+        // means a defect or a corrupt store, not something a peer can provoke. Report the node
+        // anyway - the wire form carries no depth, and the recipient hooks blobs in by hash - but
+        // skip the children rather than letting getChildNodeID throw on them.
+        if (nodeID.getDepth() >= kLeafDepth)
+        {
+            // LCOV_EXCL_START
+            UNREACHABLE("xrpl::SHAMap::visitDifferences : inner node at leaf depth");
+            continue;
+            // LCOV_EXCL_STOP
+        }
+
         // 2) push non-matching child inner nodes
         for (auto i = 0u; i < kBranchFactor; ++i)
         {
@@ -749,11 +763,9 @@ SHAMap::hasLeafNode(uint256 const& tag, SHAMapHash const& targetNodeHash) const
 
     do
     {
-        // An inner node is only reachable here at a depth below kLeafDepth in a well-formed map,
-        // where the loop always finds a leaf first. A malformed map could still have an inner
-        // node claiming kLeafDepth, and getChildNodeID below throws in that case: reject rather
-        // than let the throw escape uncaught. Not reachable through any public entry point,
-        // since addKnownNode already marks such a map invalid, so no test can cover this.
+        // Same kLeafDepth hazard as in visitDifferences above. That guard bounds the caller's own
+        // traversal, not the map queried here, and the loop below descends from this map's root
+        // independently, so this check is what keeps a malformed map from reaching getChildNodeID.
         if (nodeID.getDepth() >= kLeafDepth)
         {
             // LCOV_EXCL_START
@@ -781,7 +793,7 @@ SHAMap::hasLeafNode(uint256 const& tag, SHAMapHash const& targetNodeHash) const
 std::optional<std::vector<Blob>>
 SHAMap::getProofPath(uint256 const& key) const
 {
-    SharedPtrNodeStack stack;
+    NodePathStack stack;
     walkTowardsKey(key, &stack);
 
     if (stack.empty())
@@ -830,15 +842,30 @@ SHAMap::verifyProofPath(uint256 const& rootHash, uint256 const& key, std::vector
             if (node->getHash() != hash)
                 return false;
 
-            auto const depth = std::distance(path.rbegin(), rit);
+            auto const depth = static_cast<unsigned int>(std::distance(path.rbegin(), rit));
             if (node->isInner())
             {
-                auto nodeId = SHAMapNodeID::createID(static_cast<unsigned int>(depth), key);
+                // Nibbles run out at kLeafDepth, so only the leaf terminating the path may sit
+                // there. These nodes come off the wire, so a peer can still claim an inner one;
+                // reject it rather than passing this depth to selectBranch.
+                SOMETIMES(
+                    depth >= kLeafDepth, "xrpl::SHAMap::verifyProofPath : inner at leaf depth");
+                if (depth >= kLeafDepth)
+                    return false;
+
+                auto nodeId = SHAMapNodeID::createID(depth, key);
                 hash = safeDowncast<SHAMapInnerNode*>(node.get())
                            ->getChildHash(selectBranch(nodeId, key));
             }
             else
             {
+                // The hash chain up to rootHash only proves this leaf sits where the path claims,
+                // not that it is the leaf for `key`: a peer could substitute any other leaf whose
+                // subtree hashes to the same value at every level above it. Checking the terminal
+                // leaf's own key is what ties the proof to `key` specifically.
+                if (leafKey(*node) != key)
+                    return false;
+
                 // should exhaust all the blobs now
                 return depth + 1 == path.size();
             }

src/tests/libxrpl/shamap/SHAMap.cpp

@@ -3,19 +3,23 @@
 #include <xrpl/basics/Blob.h>
 #include <xrpl/basics/Buffer.h>
 #include <xrpl/basics/SHAMapHash.h>
+#include <xrpl/basics/Slice.h>
 #include <xrpl/basics/base_uint.h>
 #include <xrpl/beast/utility/Journal.h>
 #include <xrpl/beast/utility/Zero.h>
+#include <xrpl/protocol/Serializer.h>
 #include <xrpl/shamap/SHAMapInnerNode.h>
 #include <xrpl/shamap/SHAMapItem.h>
 #include <xrpl/shamap/SHAMapLeafNode.h>
 #include <xrpl/shamap/SHAMapMissingNode.h>
+#include <xrpl/shamap/SHAMapNodeID.h>
 #include <xrpl/shamap/SHAMapTreeNode.h>
 
 #include <gtest/gtest.h>
 #include <helpers/TestSink.h>
 #include <shamap/common.h>
 
+#include <algorithm>
 #include <array>
 #include <cstddef>
 #include <cstdint>
@@ -268,6 +272,411 @@ INSTANTIATE_TEST_SUITE_P(
     ::testing::Values(kBackedMode, kUnbackedMode),
     shamapBackingModeName);
 
+// Exercises the traversal stacks built by firstBelow/lastBelow. Each stack entry pairs a node with
+// the ID naming its position, and SHAMap asserts that pairing on every push, so these traversals
+// fail loudly in a Debug build if a node ID is ever derived from the wrong branch.
+class SHAMapTraversal : public ::testing::Test
+{
+protected:
+    beast::Journal const j_{TestSink::instance()};
+
+    // Keys that share a long prefix and then fan out across distinct branches, so the deeper inner
+    // nodes have several children and traversal must descend many levels.
+    static std::vector<uint256>
+    deepFanOutKeys()
+    {
+        std::vector<uint256> keys;
+        for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
+        {
+            // Vary the 6th nibble, keeping the first five identical.
+            auto text = std::string("abcde") + "0123456789abcdef"[branch];
+            text.append(64 - text.size(), '7');
+            keys.emplace_back(std::string_view{text});
+        }
+        return keys;
+    }
+
+    // Keys that share all 63 leading nibbles and fan out only at the last one, so the tree is a
+    // chain of single-child inner nodes down to depth 63 with the leaves as siblings at depth 64.
+    // This exercises kLeafDepth directly, unlike deepFanOutKeys() above, whose fan-out at the 6th
+    // nibble keeps the tree only about 6 levels deep.
+    static std::vector<uint256>
+    deepFanOutKeysAtLeafDepth()
+    {
+        std::vector<uint256> keys;
+        for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
+        {
+            auto text = std::string(63, 'a') + "0123456789abcdef"[branch];
+            keys.emplace_back(std::string_view{text});
+        }
+        return keys;
+    }
+
+    static void
+    fillMap(SHAMap& map, std::vector<uint256> const& keys)
+    {
+        map.setUnbacked();
+        for (auto const& k : keys)
+        {
+            Buffer vuc{32};
+            std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
+            map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc)));
+            map.invariants();
+        }
+    }
+};
+
+TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+
+    std::sort(keys.begin(), keys.end());
+    std::vector<uint256> visited;
+    for (auto const& item : map)
+        visited.push_back(item.key());
+
+    EXPECT_EQ(visited, keys);
+}
+
+TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // upperBound from each key must land on its successor, driving firstBelow across every subtree.
+    for (std::size_t k = 0; k + 1 < keys.size(); ++k)
+    {
+        auto it = map.upperBound(keys[k]);
+        ASSERT_NE(it, map.end()) << "no successor for key " << k;
+        EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
+    }
+    EXPECT_EQ(map.upperBound(keys.back()), map.end());
+}
+
+TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // lowerBound is the lastBelow counterpart: it descends to the greatest key below a subtree.
+    for (std::size_t k = 1; k < keys.size(); ++k)
+    {
+        auto it = map.lowerBound(keys[k]);
+        ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
+        EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
+    }
+    EXPECT_EQ(map.lowerBound(keys.front()), map.end());
+}
+
+TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // Probe keys that are not in the map, so the traversal starts mid-tree rather than at a leaf.
+    for (unsigned char c : {0x00, 0x40, 0x80, 0xc0, 0xff})
+    {
+        uint256 probe;
+        std::fill_n(probe.begin(), probe.size(), c);
+
+        auto const expectedUpper = std::upper_bound(keys.begin(), keys.end(), probe);
+        auto const upper = map.upperBound(probe);
+        if (expectedUpper == keys.end())
+        {
+            EXPECT_EQ(upper, map.end()) << "probe " << static_cast<unsigned>(c);
+        }
+        else
+        {
+            ASSERT_NE(upper, map.end()) << "probe " << static_cast<unsigned>(c);
+            EXPECT_EQ(upper->key(), *expectedUpper) << "probe " << static_cast<unsigned>(c);
+        }
+
+        auto const lowerCount = std::lower_bound(keys.begin(), keys.end(), probe) - keys.begin();
+        auto const lower = map.lowerBound(probe);
+        if (lowerCount == 0)
+        {
+            EXPECT_EQ(lower, map.end()) << "probe " << static_cast<unsigned>(c);
+        }
+        else
+        {
+            ASSERT_NE(lower, map.end()) << "probe " << static_cast<unsigned>(c);
+            EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "probe " << static_cast<unsigned>(c);
+        }
+    }
+}
+
+TEST_F(SHAMapTraversal, bounds_on_empty_map_return_end)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+    map.setUnbacked();
+
+    // The root is a childless inner node, so boundHelper's inner-node branch must scan all 16
+    // branches, find every one empty, and fall through to end() rather than dereference a child.
+    EXPECT_EQ(map.upperBound(uint256{}), map.end());
+    EXPECT_EQ(map.lowerBound(uint256{}), map.end());
+
+    uint256 probe;
+    std::fill_n(probe.begin(), probe.size(), std::uint8_t{0xff});
+    EXPECT_EQ(map.upperBound(probe), map.end());
+    EXPECT_EQ(map.lowerBound(probe), map.end());
+}
+
+TEST_F(SHAMapTraversal, bounds_on_single_item_map_use_the_leaf_root)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+
+    auto const key = deepFanOutKeys().front();
+    fillMap(map, {key});
+
+    // root_ can be a leaf, but only after syncing a single-item map from a peer (addRootNode);
+    // fillMap builds this map in-process via addItem, which always leaves root_ as the inner node
+    // it was constructed with, with the single leaf one level below it. So here the stack holds
+    // that inner root plus the leaf, and boundHelper's leaf branch, examined first, decides the
+    // outcome before root_'s own inner-node scan would ever run.
+    uint256 below = key;
+    --below;
+    uint256 above = key;
+    ++above;
+
+    EXPECT_EQ(map.upperBound(below)->key(), key);
+    EXPECT_EQ(map.upperBound(key), map.end());
+    EXPECT_EQ(map.upperBound(above), map.end());
+
+    EXPECT_EQ(map.lowerBound(above)->key(), key);
+    EXPECT_EQ(map.lowerBound(key), map.end());
+    EXPECT_EQ(map.lowerBound(below), map.end());
+}
+
+TEST_F(SHAMapTraversal, iteration_survives_deletions)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // Deleting every other key drops the fan-out node's branch count from 16 to 8, never the 1
+    // that would make delItem collapse it into a leaf. So this pins that iteration survives
+    // deletions that reshape the map without collapsing any inner node; the case that does
+    // collapse one is iteration_survives_a_collapsed_inner_node below.
+    for (std::size_t k = 0; k < keys.size(); k += 2)
+    {
+        ASSERT_TRUE(map.delItem(keys[k]));
+        map.invariants();
+    }
+
+    std::vector<uint256> expected;
+    for (std::size_t k = 1; k < keys.size(); k += 2)
+        expected.push_back(keys[k]);
+
+    std::vector<uint256> visited;
+    for (auto const& item : map)
+        visited.push_back(item.key());
+    EXPECT_EQ(visited, expected);
+
+    for (std::size_t k = 0; k + 1 < expected.size(); ++k)
+    {
+        auto it = map.upperBound(expected[k]);
+        ASSERT_NE(it, map.end());
+        EXPECT_EQ(it->key(), expected[k + 1]);
+    }
+}
+
+TEST_F(SHAMapTraversal, iteration_survives_a_collapsed_inner_node)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+
+    // One key in a separate subtree, diverging from the fan-out group at the very first nibble, so
+    // it survives untouched while the fan-out group below is collapsed.
+    auto const sentinel = uint256{std::string_view{std::string(64, '0')}};
+
+    auto fanOutKeys = deepFanOutKeysAtLeafDepth();
+    fillMap(map, fanOutKeys);
+    Buffer vuc{32};
+    std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
+    ASSERT_TRUE(
+        map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(sentinel, std::move(vuc))));
+    map.invariants();
+
+    std::sort(fanOutKeys.begin(), fanOutKeys.end());
+
+    // Delete all but the last fan-out key. The fan-out node's branch count drops to 1 on the final
+    // delete, which delItem collapses by pulling the sole remaining leaf up in its place; every
+    // ancestor above it has exactly one child by construction, so each of those also drops to
+    // branch count 1 and collapses in turn, all the way up to (but not including) the root. That
+    // final delete replaces the entire 63-level chain with the root pointing straight at the one
+    // remaining leaf, so the surviving traversal stack is rebuilt over a drastically different tree
+    // shape, not just missing one inner node.
+    for (std::size_t k = 0; k + 1 < fanOutKeys.size(); ++k)
+    {
+        ASSERT_TRUE(map.delItem(fanOutKeys[k]));
+        map.invariants();
+    }
+
+    std::vector<uint256> const expected{sentinel, fanOutKeys.back()};
+    std::vector<uint256> visited;
+    for (auto const& item : map)
+        visited.push_back(item.key());
+    EXPECT_EQ(visited, expected);
+
+    auto it = map.upperBound(sentinel);
+    ASSERT_NE(it, map.end());
+    EXPECT_EQ(it->key(), fanOutKeys.back());
+    EXPECT_EQ(map.upperBound(fanOutKeys.back()), map.end());
+}
+
+// The tests below mirror the ones above but use deepFanOutKeysAtLeafDepth(), whose keys share all
+// 63 leading nibbles and fan out only at the last one. That puts the leaves at depth
+// SHAMap::kLeafDepth, so these traversals walk a chain of single-child inner nodes all the way down
+// and exercise the kLeafDepth guards that deepFanOutKeys() alone (fanning out at the 6th nibble)
+// never reaches.
+
+TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order_at_leaf_depth)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeysAtLeafDepth();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+
+    std::sort(keys.begin(), keys.end());
+    std::vector<uint256> visited;
+    for (auto const& item : map)
+        visited.push_back(item.key());
+
+    EXPECT_EQ(visited, keys);
+}
+
+TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map_at_leaf_depth)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeysAtLeafDepth();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // upperBound from each key must land on its successor, driving firstBelow down to depth
+    // kLeafDepth for every subtree.
+    for (std::size_t k = 0; k + 1 < keys.size(); ++k)
+    {
+        auto it = map.upperBound(keys[k]);
+        ASSERT_NE(it, map.end()) << "no successor for key " << k;
+        EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
+    }
+    EXPECT_EQ(map.upperBound(keys.back()), map.end());
+}
+
+TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map_at_leaf_depth)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeysAtLeafDepth();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // lowerBound is the lastBelow counterpart: it descends to depth kLeafDepth to find the greatest
+    // key below a subtree.
+    for (std::size_t k = 1; k < keys.size(); ++k)
+    {
+        auto it = map.lowerBound(keys[k]);
+        ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
+        EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
+    }
+    EXPECT_EQ(map.lowerBound(keys.front()), map.end());
+}
+
+TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys_at_leaf_depth)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeysAtLeafDepth();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // The keys fill all 16 branches of the last nibble, so an absent key must diverge from the
+    // shared 'a' prefix earlier than that. Diverging at increasingly deep nibbles forces
+    // walkTowardsKey to descend through more single-child inner nodes before it finds the empty
+    // branch, right up to the one just above kLeafDepth.
+    for (unsigned int divergeAt : {0u, 31u, 61u, 62u})
+    {
+        auto text = std::string(divergeAt, 'a') + "b";
+        text.append(64 - text.size(), '0');
+        uint256 const probe{std::string_view{text}};
+
+        auto const expectedUpper = std::upper_bound(keys.begin(), keys.end(), probe);
+        auto const upper = map.upperBound(probe);
+        if (expectedUpper == keys.end())
+        {
+            EXPECT_EQ(upper, map.end()) << "divergeAt " << divergeAt;
+        }
+        else
+        {
+            ASSERT_NE(upper, map.end()) << "divergeAt " << divergeAt;
+            EXPECT_EQ(upper->key(), *expectedUpper) << "divergeAt " << divergeAt;
+        }
+
+        auto const lowerCount = std::lower_bound(keys.begin(), keys.end(), probe) - keys.begin();
+        auto const lower = map.lowerBound(probe);
+        if (lowerCount == 0)
+        {
+            EXPECT_EQ(lower, map.end()) << "divergeAt " << divergeAt;
+        }
+        else
+        {
+            ASSERT_NE(lower, map.end()) << "divergeAt " << divergeAt;
+            EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "divergeAt " << divergeAt;
+        }
+    }
+}
+
+TEST_F(SHAMapTraversal, iteration_survives_deletions_at_leaf_depth)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeysAtLeafDepth();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+    std::sort(keys.begin(), keys.end());
+
+    // Deleting every other key drops the fan-out node's branch count from 16 to 8, the same
+    // non-collapsing case as iteration_survives_deletions above, but reached by descending through
+    // a chain of single-child inner nodes down to kLeafDepth instead of a shallow one.
+    for (std::size_t k = 0; k < keys.size(); k += 2)
+    {
+        ASSERT_TRUE(map.delItem(keys[k]));
+        map.invariants();
+    }
+
+    std::vector<uint256> expected;
+    for (std::size_t k = 1; k < keys.size(); k += 2)
+        expected.push_back(keys[k]);
+
+    std::vector<uint256> visited;
+    for (auto const& item : map)
+        visited.push_back(item.key());
+    EXPECT_EQ(visited, expected);
+
+    for (std::size_t k = 0; k + 1 < expected.size(); ++k)
+    {
+        auto it = map.upperBound(expected[k]);
+        ASSERT_NE(it, map.end());
+        EXPECT_EQ(it->key(), expected[k + 1]);
+    }
+}
+
 class SHAMapPathProof : public ::testing::Test
 {
 protected:
@@ -346,4 +755,149 @@ TEST_F(SHAMapPathProof, verify_proof_path)
     EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
 }
 
+// A legitimate proof path for two keys sharing all 63 leading nibbles is 65 elements: inner nodes
+// at depths 0..63 plus the leaf at depth 64. This pins that the 65 bound is real, so the fix for
+// the forged-path case below must not simply tighten the length limit.
+TEST_F(SHAMapPathProof, legitimate_deep_path_is_sixty_five_elements)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+    map.setUnbacked();
+
+    auto const kA = uint256{std::string_view{std::string(63, 'a') + "1"}};
+    auto const kB = uint256{std::string_view{std::string(63, 'a') + "2"}};
+
+    for (auto const& k : {kA, kB})
+    {
+        Buffer vuc{32};
+        std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
+        ASSERT_TRUE(map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc))));
+    }
+    map.invariants();
+
+    auto const pathA = map.getProofPath(kA);
+    ASSERT_TRUE(pathA.has_value());
+    // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
+    EXPECT_EQ(pathA->size(), 65u);
+    EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kA, *pathA));
+    // NOLINTEND(bugprone-unchecked-optional-access)
+
+    auto const pathB = map.getProofPath(kB);
+    ASSERT_TRUE(pathB.has_value());
+    // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
+    EXPECT_EQ(pathB->size(), 65u);
+    EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kB, *pathB));
+    // NOLINTEND(bugprone-unchecked-optional-access)
+}
+
+// A forged path of 65 hash-chained inner nodes reaches depth kLeafDepth, where only the leaf
+// terminating the path may sit. Such a path must be rejected.
+TEST_F(SHAMapPathProof, all_inner_path_at_leaf_depth_is_rejected)
+{
+    // An arbitrary well-formed key; the test does not care about its specific value.
+    constexpr uint256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
+
+    // Build upwards from the deepest node so each parent's selected branch carries its child's hash
+    // and the hash chain validates at every level.
+    std::vector<Blob> path;
+    SHAMapHash childHash{uint256{1}};
+
+    for (auto depth = SHAMap::kLeafDepth + 1u; depth-- > 0;)
+    {
+        auto const id = SHAMapNodeID::createID(std::min(depth, SHAMap::kLeafDepth - 1u), kTestKey);
+        auto const branch = selectBranch(id, kTestKey);
+
+        Serializer s;
+        for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+            s.addBitString(i == branch ? childHash.asUInt256() : uint256{});
+        s.add8(kWireTypeInner);
+        path.push_back(s.getData());
+
+        auto node = SHAMapTreeNode::makeFromWire(makeSlice(path.back()));
+        ASSERT_TRUE(node);
+        node->updateHash();
+        childHash = node->getHash();
+    }
+
+    ASSERT_EQ(path.size(), 65u);
+    EXPECT_FALSE(SHAMap::verifyProofPath(childHash.asUInt256(), kTestKey, path));
+}
+
+/**
+ * Wrap a leaf blob in a forged root inner node whose branch for `key` carries that leaf's hash.
+ *
+ * The resulting two-element path hash-chains for `key` no matter which leaf sits at the bottom,
+ * which is exactly the substitution a peer could attempt.
+ *
+ * @param leafBlob the wire form of the leaf to place at the bottom of the path.
+ * @param key the key the forged path claims to prove.
+ * @return the path (deepest element first) and the forged root hash, or an empty path if the leaf
+ *         blob does not parse.
+ */
+static std::pair<std::vector<Blob>, uint256>
+forgeRootOverLeaf(Blob const& leafBlob, uint256 const& key)
+{
+    auto leaf = SHAMapTreeNode::makeFromWire(makeSlice(leafBlob));
+    if (!leaf || !leaf->isLeaf())
+        return {};
+    leaf->updateHash();
+
+    auto const branch = selectBranch(SHAMapNodeID::createID(0, key), key);
+    Serializer s;
+    for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+        s.addBitString(i == branch ? leaf->getHash().asUInt256() : uint256{});
+    s.add8(kWireTypeInner);
+
+    auto root = SHAMapTreeNode::makeFromWire(makeSlice(s.peekData()));
+    if (!root)
+        return {};
+    root->updateHash();
+
+    return {std::vector<Blob>{leafBlob, s.getData()}, root->getHash().asUInt256()};
+}
+
+// The hash chain above a leaf proves nothing about which key that leaf holds, so a peer can graft a
+// genuine leaf from elsewhere in the map onto a path forged for another key. Comparing the terminal
+// leaf's own key against the key being proved is what rejects it.
+TEST_F(SHAMapPathProof, substituted_leaf_for_other_key_is_rejected)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+    map.setUnbacked();
+
+    // Two arbitrary keys differing in their first nibble, so each leaf hangs off the root directly.
+    constexpr uint256 kKey("1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93");
+    constexpr uint256 kOtherKey("e3f1a7d5b9c2e8f406a1d3b5c7e9f2a4d6b8c0e2f4a6d8b0c2e4f6a8d0b2c4e6");
+
+    for (auto const& k : {kKey, kOtherKey})
+    {
+        ASSERT_TRUE(map.addItem(
+            SHAMapNodeType::TnAccountState, makeShamapitem(k, Slice{k.data(), k.size()})));
+    }
+    map.invariants();
+
+    auto const ownPath = map.getProofPath(kKey);
+    auto const otherPath = map.getProofPath(kOtherKey);
+    ASSERT_TRUE(ownPath.has_value());
+    ASSERT_TRUE(otherPath.has_value());
+
+    // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
+    // The genuine leaf blobs, deepest element first.
+    auto const& ownLeaf = ownPath->front();
+    auto const& otherLeaf = otherPath->front();
+    // NOLINTEND(bugprone-unchecked-optional-access)
+
+    // Control: the forged root is accepted when the leaf below it really is kKey's leaf, so the
+    // rejection below can only come from the leaf key comparison.
+    auto const [goodPath, goodRoot] = forgeRootOverLeaf(ownLeaf, kKey);
+    ASSERT_EQ(goodPath.size(), 2u);
+    EXPECT_TRUE(SHAMap::verifyProofPath(goodRoot, kKey, goodPath));
+
+    // Same forged root, but kOtherKey's leaf substituted at the bottom: the hash chain still
+    // validates, yet the path does not prove anything about kKey.
+    auto const [badPath, badRoot] = forgeRootOverLeaf(otherLeaf, kKey);
+    ASSERT_EQ(badPath.size(), 2u);
+    EXPECT_FALSE(SHAMap::verifyProofPath(badRoot, kKey, badPath));
+}
+
 }  // namespace xrpl::tests

src/tests/libxrpl/shamap/SHAMapNodeID.cpp

@@ -0,0 +1,190 @@
+#include <xrpl/shamap/SHAMapNodeID.h>
+
+#include <xrpl/basics/base_uint.h>
+#include <xrpl/protocol/Serializer.h>
+#include <xrpl/shamap/SHAMap.h>
+
+#include <gtest/gtest.h>
+
+#include <stdexcept>
+
+namespace xrpl::tests {
+
+// An arbitrary 32-byte key reused across tests below that don't care about its specific value,
+// only that it is a well-formed key.
+constexpr uint256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
+
+TEST(SHAMapNodeIDTest, root_is_prefix_of_every_key)
+{
+    SHAMapNodeID const root;
+    EXPECT_EQ(root.getDepth(), 0u);
+    EXPECT_TRUE(root.isPrefixOf(uint256{}));
+    EXPECT_TRUE(root.isPrefixOf(kTestKey));
+}
+
+TEST(SHAMapNodeIDTest, child_id_is_prefix_of_keys_in_that_branch)
+{
+    // Walking the branches spelled by the key's own nibbles must keep every
+    // intermediate ID a prefix of that key.
+    SHAMapNodeID id;
+    for (auto depth = 0u; depth < SHAMap::kLeafDepth; ++depth)
+    {
+        id = id.getChildNodeID(selectBranch(id, kTestKey));
+        EXPECT_EQ(id.getDepth(), depth + 1);
+        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << id.getDepth();
+    }
+}
+
+TEST(SHAMapNodeIDTest, wrong_branch_is_not_prefix_of_key)
+{
+    SHAMapNodeID const root;
+    auto const correct = selectBranch(root, kTestKey);
+    ASSERT_EQ(correct, 0xbu);
+
+    // An ID built from the wrong branch still has a valid depth and a self-consistent mask, so
+    // isPrefixOf(kTestKey) below is what actually distinguishes the correct branch from the rest.
+    for (auto branch = 0u; branch < SHAMap::kBranchFactor; ++branch)
+    {
+        auto const child = root.getChildNodeID(branch);
+        EXPECT_EQ(child.getDepth(), 1u);
+        EXPECT_EQ(child.isPrefixOf(kTestKey), branch == correct) << "branch " << branch;
+    }
+}
+
+TEST(SHAMapNodeIDTest, prefix_check_is_depth_sensitive)
+{
+    // kTestKey and kOther agree on the first two nibbles ("b9") and then diverge.
+    constexpr uint256 kOther("b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
+
+    auto id = SHAMapNodeID{}.getChildNodeID(selectBranch(SHAMapNodeID{}, kTestKey));
+    EXPECT_TRUE(id.isPrefixOf(kTestKey));
+    EXPECT_TRUE(id.isPrefixOf(kOther)) << "shared first nibble";
+
+    id = id.getChildNodeID(selectBranch(id, kTestKey));
+    EXPECT_TRUE(id.isPrefixOf(kTestKey));
+    EXPECT_TRUE(id.isPrefixOf(kOther)) << "shared second nibble";
+
+    // Third nibble differs, so the deeper ID no longer covers kOther.
+    id = id.getChildNodeID(selectBranch(id, kTestKey));
+    EXPECT_TRUE(id.isPrefixOf(kTestKey));
+    EXPECT_FALSE(id.isPrefixOf(kOther));
+}
+
+TEST(SHAMapNodeIDTest, leaf_id_from_key_is_prefix_of_that_key)
+{
+    SHAMapNodeID const leaf{SHAMap::kLeafDepth, kTestKey};
+    EXPECT_TRUE(leaf.isPrefixOf(kTestKey));
+
+    // At full depth the prefix is the whole key, so nothing else matches.
+    constexpr uint256 kOther("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca9");
+    EXPECT_FALSE(leaf.isPrefixOf(kOther));
+}
+
+TEST(SHAMapNodeIDTest, create_id_masks_key_to_depth)
+{
+    for (auto depth = 0u; depth <= SHAMap::kLeafDepth; ++depth)
+    {
+        auto const id = SHAMapNodeID::createID(depth, kTestKey);
+        EXPECT_EQ(id.getDepth(), depth);
+        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << depth;
+    }
+}
+
+// The guards below must hold with XRPL_ASSERT compiled out (NDEBUG), so each one
+// has to be a real runtime check rather than an assert.
+
+TEST(SHAMapNodeIDTest, child_of_leaf_depth_id_throws)
+{
+    auto const leafDepthID = SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey);
+    ASSERT_EQ(leafDepthID.getDepth(), SHAMap::kLeafDepth);
+    EXPECT_THROW((void)leafDepthID.getChildNodeID(0), std::logic_error);
+}
+
+TEST(SHAMapNodeIDTest, out_of_range_depth_is_clamped)
+{
+    // A depth past kLeafDepth has no mask in depthMask's 65-entry table, so both the constructor
+    // and createID clamp it. createID needs its own clamp: it picks the mask while evaluating the
+    // constructor's argument, so the constructor's clamp cannot cover that read.
+    //
+    // Both clamps are marked UNREACHABLE, which is an assert and therefore fatal wherever asserts
+    // are live. Only a build with them compiled out (or routed to Antithesis's non-fatal handler)
+    // reaches the clamp itself, so that is the only configuration that can assert on the result.
+#if defined(NDEBUG) || defined(ENABLE_VOIDSTAR)
+    for (auto const depth : {SHAMap::kLeafDepth + 1u, 100u, 255u, 256u, 320u})
+    {
+        auto const id = SHAMapNodeID::createID(depth, kTestKey);
+
+        // Clamped to a real depth, not the depth asked for, and not a byte-narrowed version of it:
+        // 256 would otherwise become 0 and name the root, 320 would become 64.
+        EXPECT_EQ(id.getDepth(), SHAMap::kLeafDepth) << "depth " << depth;
+
+        // id_ and depth_ still agree, so the object is usable rather than merely non-crashing.
+        EXPECT_TRUE(id.isPrefixOf(kTestKey)) << "depth " << depth;
+        EXPECT_EQ(id, SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey)) << "depth " << depth;
+
+        // The clamp holds through the wire format too, which encodes the depth in one byte.
+        auto const roundTripped = deserializeSHAMapNodeID(id.getRawString());
+        ASSERT_TRUE(roundTripped.has_value()) << "depth " << depth;
+        EXPECT_EQ(roundTripped->getDepth(), SHAMap::kLeafDepth) << "depth " << depth;
+    }
+
+    // The constructor clamps on its own, for the paths that do not go through createID.
+    SHAMapNodeID const direct{SHAMap::kLeafDepth + 1u, uint256{}};
+    EXPECT_EQ(direct.getDepth(), SHAMap::kLeafDepth);
+#else
+    EXPECT_DEATH(
+        (void)SHAMapNodeID::createID(SHAMap::kLeafDepth + 1u, kTestKey), "depth within tree");
+#endif
+}
+
+TEST(SHAMapNodeIDTest, select_branch_clamps_leaf_depth)
+{
+    // selectBranch's own precondition is depth < kLeafDepth: a depth-64 ID has no nibble left
+    // to select. That makes it unlike the guards above, which have a throw/return reachable
+    // even with XRPL_ASSERT compiled out; selectBranch has no such path, so the two build
+    // configurations have to be tested differently.
+    //
+    // Under ENABLE_VOIDSTAR, XRPL_ASSERT routes to Antithesis's assert_impl, which only records
+    // the hit and returns rather than aborting, even though NDEBUG is undefined there (voidstar
+    // requires a Debug build). So the assert is live in name but never fatal, the same as the
+    // NDEBUG case below.
+    auto const leafDepthID = SHAMapNodeID::createID(SHAMap::kLeafDepth, kTestKey);
+
+#if defined(NDEBUG) || defined(ENABLE_VOIDSTAR)
+    // With the assert compiled out or routed to a non-fatal handler, the clamp is what stands
+    // between this call and reading past the end of the 32-byte key. Clamping means it reads the
+    // same byte, and returns the same branch, as the deepest ID that still has one: depth 63.
+    auto const deepestWithBranchID = SHAMapNodeID::createID(SHAMap::kLeafDepth - 1u, kTestKey);
+    auto const branch = selectBranch(leafDepthID, kTestKey);
+    EXPECT_LT(branch, SHAMap::kBranchFactor);
+    EXPECT_EQ(branch, selectBranch(deepestWithBranchID, kTestKey));
+#else
+    // In a debug build the assert is live and must reject this call outright, in a forked
+    // process so a failure here cannot take down the rest of the suite.
+    EXPECT_DEATH((void)selectBranch(leafDepthID, kTestKey), "depth below leaf depth");
+#endif
+}
+
+TEST(SHAMapNodeIDTest, deserialize_rejects_out_of_range_depth)
+{
+    // getRawString() only serializes a depth already accepted by the constructor's own
+    // assertion, so an out-of-range depth here is built by hand instead.
+    auto serializeWithRawDepth = [](unsigned int depth) {
+        Serializer s;
+        s.addBitString(uint256{});
+        s.add8(static_cast<unsigned char>(depth));
+        return s.getString();
+    };
+
+    for (auto const depth : {65u, 100u, 255u})
+        EXPECT_FALSE(deserializeSHAMapNodeID(serializeWithRawDepth(depth)).has_value())
+            << "depth " << depth;
+
+    // A depth-64 ID is legal, since leaves live there, but it has no children.
+    auto const id =
+        deserializeSHAMapNodeID(SHAMapNodeID{SHAMap::kLeafDepth, uint256{}}.getRawString());
+    ASSERT_TRUE(id.has_value());
+    EXPECT_THROW((void)id->getChildNodeID(0), std::logic_error);
+}
+
+}  // namespace xrpl::tests