test: Cover the two throws a childless inner node reaches

A childless inner node cannot be built in process, since serializing one asserts
it has a branch, but it can be parsed from a blob. `makeFromPrefix` passes
`hashValid = true` and `makeFullInner` then adopts the hash the node was fetched
under rather than recomputing it, so sixteen zero child hashes give a node whose
own hash is whatever its parent claims. Every check on the way in passes: it
carries no key, so `belongsAt` waves it through, and `canonicalize` and
`canonicalizeChild` both compare against the hash it adopted.

The map that results is well formed by every position rule and still cannot be
walked, which is the one case where `belowHelper` returns nullptr for a node it
has just pushed. Two entry points reach it, and both must refuse rather than
report an absence: an iterator increment would otherwise end the walk early and
drop the rest of the map, and `upperBound` would answer `end()`, which is the
positive claim that no greater key exists. Each throws today, and neither
statement had a test.

include/xrpl/basics/IntrusivePointer.h

@@ -86,12 +86,16 @@ public:
         requires std::convertible_to<TT*, T*>
     SharedIntrusive(SharedIntrusive<TT> const& rhs);
 
-    SharedIntrusive(SharedIntrusive&& rhs);
+    // noexcept so that a std::vector of these relocates by moving. Without it, move_if_noexcept
+    // copies each element instead, since this type is also copy constructible, and every copy is an
+    // atomic increment on the pointee's refcount followed by a release on the original. The body is
+    // a std::exchange on a raw pointer, so it provably cannot throw.
+    SharedIntrusive(SharedIntrusive&& rhs) noexcept;
 
     template <class TT>
         requires std::convertible_to<TT*, T*>
-    SharedIntrusive(
-        SharedIntrusive<TT>&& rhs);  // NOLINT(cppcoreguidelines-rvalue-reference-param-not-moved)
+    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
+    SharedIntrusive(SharedIntrusive<TT>&& rhs) noexcept;
 
     SharedIntrusive&
     operator=(SharedIntrusive const& rhs);
@@ -529,11 +533,48 @@ staticPointerCast(TT const& v)
     return SharedPtr<T>(StaticCastTagSharedIntrusive{}, v);
 }
 
+/**
+ * Statically cast an intrusive pointer the caller is giving up, moving out of
+ * it.
+ *
+ * The parameter names the wrapped type rather than taking a bare `TT&&`. A
+ * bare one would be a forwarding reference, so it would also bind to lvalues
+ * in preference to the `const&` overload above and move out of a caller's live
+ * variable on what looks like a copy call.
+ *
+ * @param v the pointer to cast, left empty afterwards.
+ * @return a pointer of the requested type to the same object.
+ */
+template <class T, class TT>
+SharedPtr<T>
+staticPointerCast(SharedIntrusive<TT>&& v)
+{
+    return SharedPtr<T>(StaticCastTagSharedIntrusive{}, std::move(v));
+}
+
 template <class T, class TT>
 SharedPtr<T>
 dynamicPointerCast(TT const& v)
 {
     return SharedPtr<T>(DynamicCastTagSharedIntrusive{}, v);
 }
+
+/**
+ * Dynamically cast an intrusive pointer the caller is giving up, moving out of
+ * it.
+ *
+ * Tied to `SharedIntrusive<TT>&&` for the reason given above.
+ *
+ * @param v the pointer to cast, left empty afterwards if the cast succeeds and
+ *          left owning the object if it does not.
+ * @return a pointer of the requested type, or an empty one if the object is
+ *         not of that type.
+ */
+template <class T, class TT>
+SharedPtr<T>
+dynamicPointerCast(SharedIntrusive<TT>&& v)
+{
+    return SharedPtr<T>(DynamicCastTagSharedIntrusive{}, std::move(v));
+}
 }  // namespace intr_ptr
 }  // namespace xrpl

include/xrpl/basics/IntrusivePointer.ipp

@@ -43,7 +43,7 @@ SharedIntrusive<T>::SharedIntrusive(SharedIntrusive<TT> const& rhs)
 }
 
 template <class T>
-SharedIntrusive<T>::SharedIntrusive(SharedIntrusive&& rhs)
+SharedIntrusive<T>::SharedIntrusive(SharedIntrusive&& rhs) noexcept
     : ptr_{std::move(rhs).unsafeExchange(nullptr)}
 {
 }
@@ -51,7 +51,7 @@ SharedIntrusive<T>::SharedIntrusive(SharedIntrusive&& rhs)
 template <class T>
 template <class TT>
     requires std::convertible_to<TT*, T*>
-SharedIntrusive<T>::SharedIntrusive(SharedIntrusive<TT>&& rhs)
+SharedIntrusive<T>::SharedIntrusive(SharedIntrusive<TT>&& rhs) noexcept
     : ptr_{std::move(rhs).unsafeExchange(nullptr)}
 {
 }

include/xrpl/shamap/SHAMap.h

@@ -71,20 +71,31 @@ enum class SHAMapState {
 };
 
 /**
- * A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
+ * A SHAMap is both a trie with a fan-out of 16 and a Merkle tree.
  *
- * A radix tree is a tree with two properties:
+ * A trie keeps a key in the position of its nodes rather than in the nodes
+ * themselves: the path from the root down to a node spells out the prefix
+ * every key below it shares (the "prefix property"). A SHAMap spends one
+ * nibble of the 256-bit key per level, so each inner node has at most 16
+ * children, which is the fan-out, and a leaf sits at depth 64 at the deepest.
+ * A leaf also carries its own full key, which is what lets a reader check
+ * that it was reached through the branches that key names.
  *
- *   1. The key for a node is represented by the node's position in the tree
- *      (the "prefix property").
- *   2. A node with only one child is merged with that child
- *      (the "merge property")
+ * A radix tree adds a second property: a node with only one child is merged
+ * with that child (the "merge property"), which is what makes it a compressed
+ * trie. A SHAMap does not maintain that, so it is a trie and not a radix
+ * tree. Adding an item creates an inner node at every nibble the two keys
+ * share, however long that run is, and never merges one away. Deleting does
+ * merge: a chain that reduces to a single leaf collapses, pulling that leaf
+ * up to one nibble below the nearest ancestor still holding two branches.
+ * Either way no edge spans more than one nibble, so two keys agreeing on
+ * their first 63 nibbles give 63 single-child inner nodes, an inner node at
+ * depth 63 holding both branches, and the two leaves at depth 64: one entry
+ * per level with no gaps, and 65 entries at the most. Traversal relies on
+ * that, since it is what makes a path's length name each node's depth.
  *
- * These properties result in a significantly smaller memory footprint for
- * a radix tree.
- *
- * A fan-out of 16 means that each node in the tree has at most 16
- * children. See https://en.wikipedia.org/wiki/Radix_tree
+ * See https://en.wikipedia.org/wiki/Trie and
+ * https://en.wikipedia.org/wiki/Radix_tree
  *
  * A Merkle tree is a tree where each non-leaf node is labelled with the hash
  * of the combined labels of its children nodes.
@@ -133,8 +144,7 @@ private:
 
 public:
     /**
-     * Number of children each non-leaf node has (the 'radix tree' part of the
-     * map)
+     * Number of children each non-leaf node has, which is the trie's fan-out
      */
     static constexpr unsigned int kBranchFactor = SHAMapInnerNode::kBranchFactor;
 
@@ -421,104 +431,324 @@ public:
 
 private:
     /**
-     * A path from the root of the map down to some node, pairing each node with the ID naming its
-     * position.
+     * Whether placing `node` one level below `parentDepth` leaves it no room.
      *
-     * 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.
+     * Only a leaf may sit at kLeafDepth, since an inner node there would have
+     * no branch left to select. Both of the places that bound a descent call
+     * this, so a walk with a caller-supplied path and one without cannot drift
+     * apart and refuse at different nodes.
+     *
+     * The depth is tested before the node's type so the virtual call runs only
+     * where the bound can bite, which is the last level of a 65-level walk.
+     *
+     * @param parentDepth the depth of the node being descended from.
+     * @param node the node about to be placed one level below it.
+     * @return whether that placement is past the deepest level this kind of
+     *         node may occupy.
+     */
+    [[nodiscard]] static bool
+    pastLeafDepth(unsigned int parentDepth, SHAMapTreeNode const& node)
+    {
+        return parentDepth + 1u >= kLeafDepth && (node.isInner() || parentDepth >= kLeafDepth);
+    }
+
+    /**
+     * A root-down path of nodes through the map.
+     *
+     * The path itself names each node's position: entry `i` sits at depth
+     * `i`, since a SHAMap does not merge a single-child node away (see the
+     * class docstring above), so every nibble down to a leaf has an inner
+     * node of its own. Nothing is therefore stored per entry but the node.
+     * No consumer needs a whole SHAMapNodeID: every one of them wants a
+     * depth, and reads the nibbles it cares about from the key it already
+     * holds.
+     *
+     * Storing an ID alongside each node would add a second answer to "where
+     * does this node sit", which could then disagree with the first.
+     * Deriving it cannot.
      */
     class NodePathStack
     {
     public:
+        /**
+         * @return whether the path holds no node at all.
+         */
         [[nodiscard]] bool
         empty() const
         {
-            return stack_.empty();
+            return path_.empty();
         }
 
+        /**
+         * @return how many nodes the path holds, which is one more than its
+         *         last node's depth.
+         */
         [[nodiscard]] std::size_t
         size() const
         {
-            return stack_.size();
+            return path_.size();
         }
 
-        [[nodiscard]] std::pair<SHAMapTreeNodePtr, SHAMapNodeID> const&
+        /**
+         * The node at the end of the path.
+         *
+         * Reading an empty path would be undefined, and the assert alone is
+         * stripped in release, so an empty path yields a null node the caller
+         * can test instead.
+         *
+         * @return a reference into the path, which a later push may
+         *         invalidate by reallocating. Callers that push and then want
+         *         the node again ask for it again; the node itself does not
+         *         move, only the slot holding the pointer to it.
+         */
+        [[nodiscard]] SHAMapTreeNodePtr const&
         top() const
         {
-            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::top : non-empty stack");
-            return stack_.top();
+            if (path_.empty())
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::top : empty stack");
+                static SHAMapTreeNodePtr const kEmpty;
+                return kEmpty;
+                // LCOV_EXCL_STOP
+            }
+            return path_.back();
         }
 
+        /**
+         * The depth of the node at the end of the path.
+         *
+         * @return the depth, which is the entry's own index; zero on an empty
+         *         path, which a caller must not read but which must not be an
+         *         out-of-range subtraction either.
+         */
+        [[nodiscard]] unsigned int
+        topDepth() const
+        {
+            if (path_.empty())
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::topDepth : empty stack");
+                return 0;
+                // LCOV_EXCL_STOP
+            }
+            return static_cast<unsigned int>(path_.size() - 1);
+        }
+
+        /**
+         * Shorten the path by one node.
+         *
+         * Popping an empty path would be undefined, and the assert alone is
+         * stripped in release, so an empty path is left alone instead.
+         */
         void
         pop()
         {
-            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::pop : non-empty stack");
-            stack_.pop();
+            if (path_.empty())
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::pop : empty stack");
+                return;
+                // LCOV_EXCL_STOP
+            }
+            path_.pop_back();
         }
 
+        /**
+         * Discard the whole path.
+         *
+         * For a walk that pushed a node it then found unusable: the node never
+         * became a meaningful path entry, so it must not be mistaken for one
+         * by whatever the caller does next with an empty-vs-nonempty check.
+         */
         void
         clear()
         {
-            stack_ = {};
+            path_.clear();
+            pathKey_ = uint256{};
         }
 
         /**
-         * Start a path at the root of the map, whose ID is the zero-depth ID by definition.
+         * Shorten the path by one node and hand that node to the caller.
+         *
+         * Reading a node out and then popping copies it, which costs an atomic
+         * increment on its refcount. Moving it out does not.
+         *
+         * @return the node that was at the end of the path, or an empty
+         *         pointer if there was none.
          */
-        void
+        [[nodiscard]] SHAMapTreeNodePtr
+        releaseNode()
+        {
+            if (path_.empty())
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::releaseNode : empty stack");
+                return {};
+                // LCOV_EXCL_STOP
+            }
+            auto node = std::move(path_.back());
+            path_.pop_back();
+            return node;
+        }
+
+        /**
+         * Start a path at the root of the map, which sits at depth zero by
+         * definition.
+         *
+         * @return false, leaving the path unchanged, if a path was already
+         *         started. A malformed call must not abort a release build,
+         *         so callers stop rather than overwrite it.
+         */
+        [[nodiscard]] bool
         pushRoot(SHAMapTreeNodePtr node)
         {
-            XRPL_ASSERT(stack_.empty(), "xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
-            stack_.emplace(std::move(node), SHAMapNodeID{});
+            if (!path_.empty())
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::pushRoot : non-empty stack");
+                return false;
+                // LCOV_EXCL_STOP
+            }
+            path_.push_back(std::move(node));
+            return true;
         }
 
         /**
-         * Extend the path to the child of the current node reached by `branch`.
+         * Extend the path to the child of the node at its end 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.
+         * The branch is not stored. It is only used to judge the node offered,
+         * since the child's position is this path one level longer whichever
+         * branch reached it.
+         *
+         * Only a leaf may sit at kLeafDepth, since an inner node there would
+         * have no branch left to select.
+         *
+         * @param node the child to append.
+         * @param branch the branch of the current node that `node` was
+         *               reached through.
+         * @return false if there is no node to descend from, no node to push,
+         *         no branch of that number, no room left below for the kind
+         *         of node offered, or a leaf whose own key does not select
+         *         `branch`. A malformed call or a malformed map must not abort
+         *         a release build, so callers stop walking instead. The path
+         *         keeps its nodes, though the recorded branch chain may
+         *         already name `branch`, which no later read reaches.
          */
-        void
+        [[nodiscard]] bool
         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));
+            if (path_.empty() || !node || branch >= kBranchFactor)
+            {
+                // LCOV_EXCL_START
+                UNREACHABLE("xrpl::SHAMap::NodePathStack::pushChild : no child to push");
+                return false;
+                // LCOV_EXCL_STOP
+            }
+
+            // Only a leaf may sit at kLeafDepth, so an inner child must land one level short of
+            // it, tighter than the plain depth bound a leaf child needs.
+            //
+            // Reachable, for the same reason the misplaced-leaf case below is: a node resolved from
+            // the local store has had neither its position nor its type judged. The two-argument
+            // SHAMap::descend fetches by the parent's recorded child hash and hooks what comes
+            // back, and a parsed node adopts that hash rather than recomputing it, so an inner node
+            // can arrive one level too deep. So this refuses rather than aborting a build.
+            //
+            auto const parentDepth = topDepth();
+            bool const tooDeep = pastLeafDepth(parentDepth, *node);
+            SOMETIMES(tooDeep, "xrpl::SHAMap::NodePathStack::pushChild : child past leaf depth");
+            if (tooDeep)
+            {
+                return false;
+            }
+
+            // Record the branch, then judge a leaf against every branch recorded so far. Testing
+            // only this step's nibble would accept a whole subtree hung under the wrong branch:
+            // one wrong child pointer in one inner node leaves every leaf below it agreeing at its
+            // own final nibble, because the subtree is internally well formed, and disagreeing only
+            // at the level where the pointer is wrong.
+            //
+            // This is the one thing a path cannot derive. Its length gives every depth, but whether
+            // the caller descended the branches it says it did is only visible against a real key.
+            //
+            // Reachable for the same reason, and by a wider route: a node arriving through a sync
+            // filter is judged by hash, and a hash says nothing about position. The paths that hook
+            // a node reject a misplaced one first (see SHAMap::descend and gmnProcessNodes), but a
+            // map read lazily from the local store never passes through them.
+            setNibble(parentDepth, branch);
+
+            bool const misplaced = node->isLeaf() &&
+                !SHAMapNodeID::createID(parentDepth + 1u, pathKey_).isPrefixOf(leafKey(*node));
+            SOMETIMES(
+                misplaced, "xrpl::SHAMap::NodePathStack::pushChild : leaf key outside branch");
+            if (misplaced)
+            {
+                return false;
+            }
+
+            path_.push_back(std::move(node));
+            return true;
         }
 
         /**
-         * Extend the path to a node lying on the path to `target`.
+         * Extend the path by one node lying on the way to `target`, starting
+         * it if it is empty.
          *
-         * 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.
+         * 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` names the branch.
+         *
+         * @param node the node to append.
+         * @param target the key the walk is heading for.
+         * @return whatever pushRoot or pushChild returned.
          */
-        void
+        [[nodiscard]] bool
         pushNode(SHAMapTreeNodePtr node, uint256 const& target)
         {
-            if (stack_.empty())
+            if (path_.empty())
             {
-                pushRoot(std::move(node));
-            }
-            else
-            {
-                pushChild(std::move(node), selectBranch(stack_.top().second, target));
+                return pushRoot(std::move(node));
             }
+            return pushChild(std::move(node), selectBranch(topDepth(), target));
         }
 
     private:
-        std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>> stack_;
+        /**
+         * Write `branch` as the nibble at `depth` of the recorded branch chain.
+         *
+         * @param depth the nibble index to write, which is the depth the
+         *              branch was taken from.
+         * @param branch the branch taken, which the caller has already bounded.
+         */
+        void
+        setNibble(unsigned int depth, unsigned int branch)
+        {
+            auto& byte = *(pathKey_.begin() + (depth / 2));
+            if ((depth & 1) != 0u)
+            {
+                byte = static_cast<unsigned char>((byte & 0xF0u) | branch);
+            }
+            else
+            {
+                byte = static_cast<unsigned char>((byte & 0x0Fu) | (branch << 4));
+            }
+        }
+
+        // path_[i] holds the node at depth i, by construction: pushRoot starts at depth 0 and
+        // pushChild only ever appends one level.
+        std::vector<SHAMapTreeNodePtr> path_;
+
+        // The branches descended, one nibble per level: nibble i is the branch taken from depth i.
+        // One record for the whole path rather than an ID per entry, so path_.size() stays the only
+        // answer to where a node sits and this is only the claim being checked against it.
+        //
+        // A pop leaves the nibbles above the path's end as they were, because no read can reach
+        // them: createID masks this at parentDepth + 1, so a check reads nibbles 0 through
+        // parentDepth only, and those are always the current path's. Level j + 1 exists only if a
+        // push at depth j wrote nibble j, and re-descending at j overwrites it.
+        uint256 pathKey_;
     };
 
     using DeltaRef =
@@ -550,9 +780,15 @@ private:
     dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr terminal);
 
     /**
-     * Walk towards the specified id, returning the node.  Caller must check
-     *  if the return is nullptr, and if not, if the node->peekItem()->key() ==
-     * id
+     * Walk towards the specified id, returning the node.
+     *
+     * @param id the key to walk towards, which need not be in the map.
+     * @param stack records the path walked, or nullptr to skip recording it.
+     *              Lookups that only want the leaf (see findKey) omit it to
+     *              avoid building a path they would immediately discard.
+     * @return the leaf the walk ended on, or nullptr if it ended on an inner
+     *         node or was refused. A returned leaf need not hold `id`, so
+     *         callers compare its key themselves.
      */
     SHAMapLeafNode*
     walkTowardsKey(uint256 const& id, NodePathStack* stack = nullptr) const;
@@ -564,10 +800,17 @@ private:
 
     /**
      * Unshare the node, allowing it to be modified
+     *
+     * @param node the node to unshare.
+     * @param depth the depth the node sits at, which says whether it is the
+     *        root. A clone of the root has to be adopted as the new root; a
+     *        clone of any other node is hooked up by the caller walking back
+     *        up the path.
+     * @return the node, cloned if it was shared.
      */
     template <class Node>
     intr_ptr::SharedPtr<Node>
-    unshareNode(intr_ptr::SharedPtr<Node>, SHAMapNodeID const& nodeID);
+    unshareNode(intr_ptr::SharedPtr<Node> node, unsigned int depth);
 
     /**
      * prepare a node to be modified before flushing
@@ -588,10 +831,28 @@ private:
     /**
      * 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.
+     *
+     * @param stack the path to extend, whose last node the search starts from.
+     * @param direction whether to take the lowest or the highest branch at
+     *                  each level.
+     * @return the leaf found, or nullptr if no leaf lies below that node.
      */
     SHAMapLeafNode*
     belowHelper(NodePathStack& stack, BelowDirection direction) const;
 
+    /**
+     * The nearest item on one side of `id`, which upperBound and lowerBound
+     * both answer.
+     *
+     * @param id the key to search around, which need not be in the map.
+     * @param direction First for the nearest key greater than `id`, Last for
+     *                  the nearest lesser.
+     * @return an iterator at that item, or end() if the map holds no key on
+     *         that side.
+     */
+    [[nodiscard]] ConstIterator
+    boundHelper(uint256 const& id, BelowDirection direction) const;
+
     // Simple descent
     // Get a child of the specified node
     SHAMapTreeNode*
@@ -714,10 +975,30 @@ private:
     };
 
     // getMissingNodes helper functions
+
+    /**
+     * Examine the remaining branches of one inner node, recording or
+     * requesting what is missing.
+     *
+     * @param mn the walk's shared state, which collects the missing nodes.
+     * @param node the walk's current position, updated to the node to process
+     *             next.
+     */
     void
-    gmnProcessNodes(MissingNodes&, MissingNodes::StackEntry& node);
-    static void
-    gmnProcessDeferredReads(MissingNodes&);
+    gmnProcessNodes(MissingNodes& mn, MissingNodes::StackEntry& node);
+
+    /**
+     * Wait for every read this pass posted, then hook up or record what each
+     * one resolved.
+     *
+     * Drains all of them even after judging the map, since an outstanding
+     * read holds a pointer to `mn` and this is the only thing that waits for
+     * it.
+     *
+     * @param mn the walk's shared state, holding the posted reads.
+     */
+    void
+    gmnProcessDeferredReads(MissingNodes& mn);
 
     // fetch from DB helper function
     SHAMapTreeNodePtr

include/xrpl/shamap/SHAMapInnerNode.h

@@ -19,7 +19,8 @@ class SHAMapInnerNode final : public SHAMapTreeNode, public CountedObject<SHAMap
 {
 public:
     /**
-     * Each inner node has 16 children (the 'radix tree' part of the map)
+     * Each inner node has 16 children, which is the fan-out of the trie: one
+     * branch per value of the key nibble that level selects on.
      */
     static constexpr unsigned int kBranchFactor = 16;
 

include/xrpl/shamap/SHAMapLeafNode.h

@@ -75,4 +75,22 @@ leafKey(SHAMapTreeNode const& node)
     return safeDowncast<SHAMapLeafNode const&>(node).peekItem()->key();
 }
 
+/**
+ * Whether a node may occupy a position in a SHAMap.
+ *
+ * A leaf's own key names its position, so an ID that is not a prefix of that
+ * key names a different subtree than the one the leaf belongs to. An inner
+ * node carries no key, so every position is consistent with it and the
+ * caller's own depth rules are what bound it.
+ *
+ * @param nodeID the position the node is claimed to occupy.
+ * @param node the node to judge.
+ * @return whether the node's own key agrees with that position.
+ */
+[[nodiscard]] inline bool
+belongsAt(SHAMapNodeID const& nodeID, SHAMapTreeNode const& node)
+{
+    return !node.isLeaf() || nodeID.isPrefixOf(leafKey(node));
+}
+
 }  // namespace xrpl

include/xrpl/shamap/SHAMapNodeID.h

@@ -144,9 +144,31 @@ deserializeSHAMapNodeID(std::string_view s)
 /** @} */
 
 /**
- * Returns the branch that would contain the given hash
+ * Returns the branch at the given depth that would contain the given hash
+ *
+ * Only the depth of a position matters here, since the nibble selected is read
+ * from `hash`. Callers holding a depth rather than a whole ID use this one.
+ *
+ * @param depth the depth of the node whose branch to select.
+ * @param hash the key whose nibble at that depth names the branch.
+ * @return the branch containing the hash.
  */
 [[nodiscard]] unsigned int
-selectBranch(SHAMapNodeID const& id, uint256 const& hash);
+selectBranch(unsigned int depth, uint256 const& hash);
+
+/**
+ * Returns the branch that would contain the given hash
+ *
+ * Reads only the depth of `id`, never its own key bits.
+ *
+ * @param id the node whose depth to read.
+ * @param hash the key whose nibble at that depth names the branch.
+ * @return the branch containing the hash.
+ */
+[[nodiscard]] inline unsigned int
+selectBranch(SHAMapNodeID const& id, uint256 const& hash)
+{
+    return selectBranch(id.getDepth(), hash);
+}
 
 }  // namespace xrpl

src/libxrpl/shamap/SHAMap.cpp

@@ -111,14 +111,20 @@ SHAMap::dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr c
 
     while (!stack.empty())
     {
-        auto node = intr_ptr::dynamicPointerCast<SHAMapInnerNode>(stack.top().first);
-        SHAMapNodeID const nodeID = stack.top().second;
-        stack.pop();
-        XRPL_ASSERT(node, "xrpl::SHAMap::dirtyUp : non-null node");
+        auto const depth = stack.topDepth();
+        auto top = stack.releaseNode();
+        if (!top->isInner())
+        {
+            // LCOV_EXCL_START
+            UNREACHABLE("xrpl::SHAMap::dirtyUp : node is not inner");
+            Throw<SHAMapMissingNode>(type_, target);
+            // LCOV_EXCL_STOP
+        }
+        auto node = intr_ptr::staticPointerCast<SHAMapInnerNode>(std::move(top));
 
-        auto const branch = selectBranch(nodeID, target);
+        auto const branch = selectBranch(depth, target);
 
-        node = unshareNode(std::move(node), nodeID);
+        node = unshareNode(std::move(node), depth);
         node->setChild(branch, std::move(child));
 
         child = std::move(node);
@@ -128,32 +134,69 @@ SHAMap::dirtyUp(NodePathStack& stack, uint256 const& target, SHAMapTreeNodePtr c
 SHAMapLeafNode*
 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;
+    if (stack != nullptr && !stack->empty())
+    {
+        // A plain XRPL_ASSERT here is a no-op under NDEBUG; without this guard a non-empty stack
+        // would be appended to below, leaving the caller with a path that starts mid-walk instead
+        // of at the root.
+        // LCOV_EXCL_START
+        UNREACHABLE("xrpl::SHAMap::walkTowardsKey : non-empty stack input");
+        stack->clear();
+        return nullptr;
+        // LCOV_EXCL_STOP
+    }
 
-    // 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);
+    auto inNode = root_;
+    unsigned int noStackDepth = 0;
+
+    // Without a caller-supplied stack, `noStackDepth` is the only record of position, so it is
+    // counted directly here instead of read back from a push. A push fails when the map is
+    // malformed, by holding a leaf outside the branch it was reached through or a node with no room
+    // left below it, not because `id` is merely absent; the stack is cleared rather than left
+    // holding a node that never became a real path entry. Callers tell the two apart by the path,
+    // which is empty only in the first case.
+    auto pushCurrent = [&]() -> bool {
+        if (stack == nullptr || stack->pushNode(inNode, id))
+        {
+            return true;
+        }
+        stack->clear();
+        return false;
     };
 
     while (inNode->isInner())
     {
-        pushCurrent();
+        if (!pushCurrent())
+        {
+            return nullptr;
+        }
 
         auto& inner = safeDowncast<SHAMapInnerNode&>(*inNode);
-        auto const branch = selectBranch(nodeID, id);
+        auto const depth = stack != nullptr ? stack->topDepth() : noStackDepth;
+        auto const branch = selectBranch(depth, id);
         if (inner.isEmptyBranch(branch))
             return nullptr;
 
         inNode = descendThrow(inner, branch);
-        nodeID = nodeID.getChildNodeID(branch);
+        if (stack == nullptr)
+        {
+            // Shares pastLeafDepth with pushChild, so this mode and the one with a
+            // caller-supplied path refuse at the same node. Reachable for the reason that helper
+            // gives, so it refuses rather than aborts.
+            bool const tooDeep = pastLeafDepth(depth, *inNode);
+            SOMETIMES(tooDeep, "xrpl::SHAMap::walkTowardsKey : child too deep");
+            if (tooDeep)
+            {
+                return nullptr;
+            }
+            ++noStackDepth;
+        }
     }
 
-    pushCurrent();
+    if (!pushCurrent())
+    {
+        return nullptr;
+    }
     return safeDowncast<SHAMapLeafNode*>(inNode.get());
 }
 
@@ -357,12 +400,29 @@ SHAMap::descend(
         !parent->isEmptyBranch(branch), "xrpl::SHAMap::descend : parent branch is non-empty");
 
     SHAMapTreeNode* child = parent->getChildPointer(branch);  // NOLINT(misc-const-correctness)
+    auto childID = parentID.getChildNodeID(branch);
 
     if (child == nullptr)
     {
         auto const& childHash = parent->getChildHash(branch);
         SHAMapTreeNodePtr childNode = fetchNodeNT(childHash, filter);
 
+        if (childNode && !belongsAt(childID, *childNode))
+        {
+            // A node arriving through the filter is judged by hash, and a hash covers a node's
+            // contents rather than its position, so this is where a leaf that belongs elsewhere
+            // enters the map. Judged before canonicalizeChild, after which every later walk would
+            // see it as part of the tree.
+            //
+            // The map is the verdict rather than the node, because refusing one node would only
+            // make the walk fetch the same thing again: the filter answers from a local cache, so
+            // the next attempt resolves the same blob to the same place.
+            JLOG(journal_.warn()) << "Leaf " << childHash << " does not belong at " << childID
+                                  << ", map is invalid";
+            state_ = SHAMapState::Invalid;
+            return std::make_pair(nullptr, std::move(childID));
+        }
+
         if (childNode)
         {
             childNode = parent->canonicalizeChild(branch, std::move(childNode));
@@ -370,7 +430,7 @@ SHAMap::descend(
         }
     }
 
-    return std::make_pair(child, parentID.getChildNodeID(branch));
+    return std::make_pair(child, std::move(childID));
 }
 
 SHAMapTreeNode*
@@ -417,7 +477,7 @@ SHAMap::descendAsync(
 
 template <class Node>
 intr_ptr::SharedPtr<Node>
-SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, SHAMapNodeID const& nodeID)
+SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, unsigned int depth)
 {
     // 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");
@@ -426,7 +486,7 @@ SHAMap::unshareNode(intr_ptr::SharedPtr<Node> node, SHAMapNodeID const& nodeID)
         // have a CoW
         XRPL_ASSERT(state_ != SHAMapState::Immutable, "xrpl::SHAMap::unshareNode : not immutable");
         node = intr_ptr::staticPointerCast<Node>(node->clone(cowid_));
-        if (nodeID.isRoot())
+        if (depth == 0)
             root_ = node;
     }
     return node;
@@ -436,14 +496,20 @@ SHAMapLeafNode*
 SHAMap::belowHelper(NodePathStack& stack, BelowDirection direction) const
 {
     XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack input");
-    if (auto const& top = stack.top().first; top->isLeaf())
+    if (stack.empty())
+    {
+        // LCOV_EXCL_START
+        return nullptr;
+        // LCOV_EXCL_STOP
+    }
+    if (auto const& top = stack.top(); top->isLeaf())
         return safeDowncast<SHAMapLeafNode*>(top.get());
 
-    // The stack owns the node/ID pairing, so descending is only ever "push the branch we took".
+    // The path names each node's position, so descending is only ever "push the node we reached".
     // `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());
+    auto* inner = safeDowncast<SHAMapInnerNode*>(stack.top().get());
     for (auto scanned = 0u; scanned < kBranchFactor;)
     {
         auto const childBranch =
@@ -455,9 +521,28 @@ SHAMap::belowHelper(NodePathStack& stack, BelowDirection direction) const
             continue;
         }
 
-        stack.pushChild(descendThrow(*inner, childBranch), childBranch);
+        auto const parentDepth = stack.topDepth();
+        auto descended = descendThrow(*inner, childBranch);
+        if (!stack.pushChild(std::move(descended), childBranch))
+        {
+            // A refused push means the map holds a node that cannot be walked, which is not the
+            // same as a subtree with no leaf below it. Throwing keeps nullptr meaning only the
+            // latter, so begin() cannot report such a map as empty while an iterator increment
+            // throws on the same condition. SHAMapMissingNode describes a resident node poorly,
+            // but descendThrow above throws it too, so every caller already handles it.
+            //
+            // The map is deliberately NOT condemned here. Every caller of belowHelper is a const
+            // read on an immutable snapshot, called from several RPC threads at once, and no
+            // reader checks isValid(); the callers that do are on the acquisition path. So the
+            // write would buy nothing, would race those readers, and would make a later compare()
+            // trip its own isValid() assertion. A map from peer data is judged where it is
+            // assembled (see SHAMap::descend and gmnProcessNodes).
+            JLOG(journal_.warn()) << "Cannot walk below depth " << parentDepth << " at branch "
+                                  << childBranch;
+            Throw<SHAMapMissingNode>(type_, inner->getChildHash(childBranch));
+        }
 
-        auto const& child = stack.top().first;
+        auto const& child = stack.top();
         if (child->isLeaf())
             return safeDowncast<SHAMapLeafNode*>(child.get());
 
@@ -512,10 +597,17 @@ SHAMapLeafNode const*
 SHAMap::peekFirstItem(NodePathStack& stack) const
 {
     XRPL_ASSERT(stack.empty(), "xrpl::SHAMap::peekFirstItem : empty stack input");
-    stack.pushRoot(root_);
+    if (!stack.pushRoot(root_))
+    {
+        // LCOV_EXCL_START
+        return nullptr;
+        // LCOV_EXCL_STOP
+    }
     SHAMapLeafNode const* node = belowHelper(stack, BelowDirection::First);
     if (node == nullptr)
     {
+        // Whether the map was empty or belowHelper's walk otherwise failed to find a leaf, the
+        // stack is cleared rather than left holding a partial path the caller cannot use.
         stack.clear();
         return nullptr;
     }
@@ -526,18 +618,28 @@ SHAMapLeafNode 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");
+    if (stack.empty())
+    {
+        // LCOV_EXCL_START
+        return nullptr;
+        // LCOV_EXCL_STOP
+    }
+    XRPL_ASSERT(stack.top()->isLeaf(), "xrpl::SHAMap::peekNextItem : stack starts with leaf");
     stack.pop();
     while (!stack.empty())
     {
-        auto const [node, nodeID] = stack.top();
+        auto const& node = stack.top();
         XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::peekNextItem : another node is not leaf");
         auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
-        for (auto i = selectBranch(nodeID, id) + 1; i < kBranchFactor; ++i)
+        for (auto i = selectBranch(stack.topDepth(), id) + 1; i < kBranchFactor; ++i)
         {
             if (!inner.isEmptyBranch(i))
             {
-                stack.pushChild(descendThrow(inner, i), i);
+                auto child = descendThrow(inner, i);
+                if (!stack.pushChild(std::move(child), i))
+                {
+                    Throw<SHAMapMissingNode>(type_, id);
+                }
                 auto leaf = belowHelper(stack, BelowDirection::First);
                 if (leaf == nullptr)
                     Throw<SHAMapMissingNode>(type_, id);
@@ -575,72 +677,72 @@ SHAMap::peekItem(uint256 const& id, SHAMapHash& hash) const
 }
 
 SHAMap::ConstIterator
-SHAMap::upperBound(uint256 const& id) const
+SHAMap::boundHelper(uint256 const& id, BelowDirection direction) const
 {
+    // Walk back up the path to `id` looking for the nearest leaf on the requested side. At each
+    // inner node the candidates are the branches on that side of the one `id` takes: the higher
+    // ones searching forward, the lower ones searching back. The nearest non-empty candidate holds
+    // the answer, which is its lowest leaf searching forward and its highest searching back.
+    auto const searchingForward = direction == BelowDirection::First;
+
     NodePathStack stack;
     walkTowardsKey(id, &stack);
+
+    // An empty path means the walk refused a node, not that the map is empty: an empty map still
+    // leaves its root on the path. end() is the positive claim that no key lies on the requested
+    // side of `id`, so it must not stand in for "cannot answer", which is what every other entry
+    // point reports by throwing.
+    if (stack.empty())
+        Throw<SHAMapMissingNode>(type_, id);
+
     while (!stack.empty())
     {
-        auto const [node, nodeID] = stack.top();
+        auto const& node = 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 = safeDowncast<SHAMapInnerNode&>(*node);
-            for (auto branch = selectBranch(nodeID, id) + 1; branch < kBranchFactor; ++branch)
+            auto const taken = selectBranch(stack.topDepth(), id);
+            auto const remaining = searchingForward ? (kBranchFactor - 1u - taken) : taken;
+
+            for (auto scanned = 0u; scanned < remaining; ++scanned)
             {
-                if (!inner.isEmptyBranch(branch))
+                auto const branch =
+                    searchingForward ? (taken + 1u + scanned) : (taken - 1u - scanned);
+                if (inner.isEmptyBranch(branch))
+                    continue;
+
+                auto child = descendThrow(inner, branch);
+                if (!stack.pushChild(std::move(child), branch))
                 {
-                    stack.pushChild(descendThrow(inner, branch), branch);
-                    auto leaf = belowHelper(stack, BelowDirection::First);
-                    if (leaf == nullptr)
-                        Throw<SHAMapMissingNode>(type_, id);
-                    return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
+                    Throw<SHAMapMissingNode>(type_, id);
                 }
+                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
 {
-    NodePathStack stack;
-    walkTowardsKey(id, &stack);
-    while (!stack.empty())
-    {
-        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));
-        }
-        else
-        {
-            auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
-            for (auto branch = selectBranch(nodeID, id); branch > 0u;)
-            {
-                --branch;
-                if (!inner.isEmptyBranch(branch))
-                {
-                    stack.pushChild(descendThrow(inner, branch), branch);
-                    auto leaf = belowHelper(stack, BelowDirection::Last);
-                    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
@@ -661,10 +763,15 @@ SHAMap::delItem(uint256 const& id)
     if (stack.empty())
         Throw<SHAMapMissingNode>(type_, id);
 
-    auto leaf = intr_ptr::dynamicPointerCast<SHAMapLeafNode>(stack.top().first);
-    stack.pop();
+    // An absent id leaves an inner node on top rather than a leaf, which is a "not found" answer
+    // and not a fault, so it is tested rather than cast through. Matches the three sibling sites in
+    // this commit, so no traversal path is left paying for a dynamic_cast.
+    auto top = stack.releaseNode();
+    if (!top->isLeaf())
+        return false;
+    auto leaf = intr_ptr::staticPointerCast<SHAMapLeafNode>(std::move(top));
 
-    if (!leaf || (leaf->peekItem()->key() != id))
+    if (leaf->peekItem()->key() != id)
         return false;
 
     SHAMapNodeType const type = leaf->getType();
@@ -674,19 +781,26 @@ SHAMap::delItem(uint256 const& id)
 
     while (!stack.empty())
     {
-        auto node = intr_ptr::staticPointerCast<SHAMapInnerNode>(stack.top().first);
-        SHAMapNodeID const nodeID = stack.top().second;
-        stack.pop();
+        auto const depth = stack.topDepth();
+        auto top = stack.releaseNode();
+        if (!top->isInner())
+        {
+            // LCOV_EXCL_START
+            UNREACHABLE("xrpl::SHAMap::delItem : node is not inner");
+            Throw<SHAMapMissingNode>(type_, id);
+            // LCOV_EXCL_STOP
+        }
+        auto node = intr_ptr::staticPointerCast<SHAMapInnerNode>(std::move(top));
 
-        node = unshareNode(std::move(node), nodeID);
+        node = unshareNode(std::move(node), depth);
         node->setChild(
-            selectBranch(nodeID, id), std::move(prevNode));  // NOLINT(bugprone-use-after-move)
+            selectBranch(depth, id), std::move(prevNode));  // NOLINT(bugprone-use-after-move)
 
         XRPL_ASSERT(
             not prevNode,  // NOLINT(bugprone-use-after-move)
             "xrpl::SHAMap::delItem : prevNode should be nullptr after std::move");
 
-        if (!nodeID.isRoot())
+        if (depth != 0)
         {
             // we may have made this a node with 1 or 0 children
             // And, if so, we need to remove this branch
@@ -747,8 +861,8 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
     if (stack.empty())
         Throw<SHAMapMissingNode>(type_, tag);
 
-    auto [node, nodeID] = stack.top();
-    stack.pop();
+    auto depth = stack.topDepth();
+    auto node = stack.releaseNode();
 
     if (node->isLeaf())
     {
@@ -756,12 +870,12 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
         if (leaf->peekItem()->key() == tag)
             return false;
     }
-    node = unshareNode(std::move(node), nodeID);
+    node = unshareNode(std::move(node), depth);
     if (node->isInner())
     {
         // easy case, we end on an inner node
         auto inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
-        auto const branch = selectBranch(nodeID, tag);
+        auto const branch = selectBranch(depth, tag);
         XRPL_ASSERT(
             inner->isEmptyBranch(branch), "xrpl::SHAMap::addGiveItem : inner branch is empty");
         inner->setChild(branch, makeTypedLeaf(type, std::move(item), cowid_));
@@ -779,13 +893,22 @@ SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const>
 
         auto b1 = 0u, b2 = 0u;
 
-        while ((b1 = selectBranch(nodeID, tag)) == (b2 = selectBranch(nodeID, otherItem->key())))
+        while ((b1 = selectBranch(depth, tag)) == (b2 = selectBranch(depth, otherItem->key())))
         {
-            stack.pushNode(node, tag);
+            if (!stack.pushNode(node, tag))
+            {
+                // The node pushed here is freshly made and inner, so only the depth bound could
+                // refuse it, and the loop cannot reach that bound: it advances only while the two
+                // keys agree at the current nibble, and keys agreeing at all 64 nibbles are equal,
+                // which the caller already returned false for.
+                // LCOV_EXCL_START
+                Throw<SHAMapMissingNode>(type_, tag);
+                // LCOV_EXCL_STOP
+            }
 
             // we need a new inner node, since both go on same branch at this
             // level
-            nodeID = nodeID.getChildNodeID(b1);
+            ++depth;
             node = intr_ptr::makeShared<SHAMapInnerNode>(cowid_);
         }
 
@@ -834,16 +957,26 @@ SHAMap::updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem cons
     if (stack.empty())
         Throw<SHAMapMissingNode>(type_, tag);
 
-    auto node = intr_ptr::dynamicPointerCast<SHAMapLeafNode>(stack.top().first);
-    auto nodeID = stack.top().second;
-    stack.pop();
+    auto const depth = stack.topDepth();
+    auto top = stack.releaseNode();
 
-    if (!node || (node->peekItem()->key() != tag))
+    // walkTowardsKey pushes an inner node's own entry before testing whether the branch it needs
+    // is empty, so a tag absent from the map leaves that inner node on top rather than a leaf.
+    // No in-tree caller reaches this, since each checks the item exists first, but the API is
+    // public and permits the call, which is why it returns false rather than reporting UNREACHABLE.
+    // The static cast below is also safe only once this is confirmed.
+    if (!top->isLeaf())
+    {
+        return false;
+    }
+    auto node = intr_ptr::staticPointerCast<SHAMapLeafNode>(std::move(top));
+
+    // The other shape an absent tag takes: the walk ends on the leaf it reached, whose key need not
+    // be `tag`, which is why findKey discards such a leaf. Both shapes mean the same thing to a
+    // caller, so both answer false rather than reporting UNREACHABLE.
+    if (node->peekItem()->key() != tag)
     {
-        // LCOV_EXCL_START
-        UNREACHABLE("xrpl::SHAMap::updateGiveItem : invalid node");
         return false;
-        // LCOV_EXCL_STOP
     }
 
     if (node->getType() != type)
@@ -852,7 +985,7 @@ SHAMap::updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem cons
         return false;
     }
 
-    node = unshareNode(std::move(node), nodeID);
+    node = unshareNode(std::move(node), depth);
 
     if (node->setItem(item))
         dirtyUp(stack, tag, node);

src/libxrpl/shamap/SHAMapNodeID.cpp

@@ -144,16 +144,18 @@ deserializeSHAMapNodeID(void const* data, std::size_t size)
 }
 
 [[nodiscard]] unsigned int
-selectBranch(SHAMapNodeID const& id, uint256 const& hash)
+selectBranch(unsigned int depth, uint256 const& hash)
 {
-    XRPL_ASSERT(id.getDepth() < SHAMap::kLeafDepth, "xrpl::selectBranch : depth below leaf depth");
+    XRPL_ASSERT(depth < 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)));
+    // A depth-64 position 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 clamped = std::min(depth, SHAMap::kLeafDepth - 1u);
+    auto branch = static_cast<unsigned int>(*(hash.begin() + (clamped / 2)));
 
-    if ((depth & 1) != 0u)
+    // Both reads take the clamped depth. Taking the byte from one and the nibble from the other
+    // would select the high nibble at depth 64 where depth 63 selects the low one.
+    if ((clamped & 1) != 0u)
     {
         branch &= 0xf;
     }

src/libxrpl/shamap/SHAMapSync.cpp

@@ -238,6 +238,28 @@ SHAMap::gmnProcessNodes(MissingNodes& mn, MissingNodes::StackEntry& se)
                 if (--mn.max <= 0)
                     return;
             }
+            // Only a leaf has a position of its own to judge, so the type is tested first: that
+            // also keeps getChildNodeID, which builds a SHAMapNodeID, off every inner child on the
+            // walk. The depth is tested next so the ID is only asked for a child that can exist.
+            else if (
+                d->isLeaf() && nodeID.getDepth() < kLeafDepth &&
+                !belongsAt(nodeID.getChildNodeID(branch), *d))
+            {
+                // The same judgment SHAMap::descend makes, for the path that consults the filter
+                // through descendAsync instead. descendAsync hooks what it resolves, so the node is
+                // already part of the tree and refusing it here would not remove it.
+                //
+                // `fullBelow` is cleared first, as on the missing-node path above. It is a
+                // reference into the caller's stack entry, and this node is left on that stack, so
+                // a later pass over its remaining branches would otherwise reach the full-below
+                // test with it still set and record this subtree's hash as complete in the
+                // family-wide cache, where another map would trust it.
+                JLOG(journal_.warn()) << "Leaf " << childHash << " does not belong below " << nodeID
+                                      << " at branch " << branch << ", map is invalid";
+                fullBelow = false;
+                state_ = SHAMapState::Invalid;
+                return;
+            }
             else if (d->isInner() && !safeDowncast<SHAMapInnerNode*>(d)->isFullBelow(mn.generation))
             {
                 mn.stack.push(se);
@@ -291,6 +313,29 @@ SHAMap::gmnProcessDeferredReads(MissingNodes& mn)
         auto nodePtr = std::get<3>(deferredNode);
         auto const& nodeHash = parent->getChildHash(branch);
 
+        // Guarded on depth for the same reason as the sibling test in gmnProcessNodes: a deferred
+        // entry carries the position the walk held when it posted the read, and the `pending`
+        // branch there records that position without building a child ID from it. So a child ID is
+        // asked for here only where the tree has room for one, which is the bound getChildNodeID
+        // keeps for itself.
+        if (nodePtr && nodePtr->isLeaf() && parentID.getDepth() < kLeafDepth &&
+            !belongsAt(parentID.getChildNodeID(branch), *nodePtr))
+        {
+            // The same judgment the two synchronous paths make (see SHAMap::descend and the
+            // descendAsync case in gmnProcessNodes), for a node an async read resolved. Every site
+            // that knows the position a node is about to take judges it here, which is what lets
+            // the traversal treat a misplaced leaf as a rarity rather than a routine case.
+            //
+            // Skips this node rather than returning: the reads still outstanding hold a pointer to
+            // `mn`, which lives in getMissingNodes' frame, and this loop is the only thing that
+            // waits for them. Returning early would let that frame go while a read was still due
+            // to write through it.
+            JLOG(journal_.warn()) << "Leaf " << nodeHash << " does not belong below " << parentID
+                                  << " at branch " << branch << ", map is invalid";
+            state_ = SHAMapState::Invalid;
+            continue;
+        }
+
         if (nodePtr)
         {  // Got the node
             nodePtr = parent->canonicalizeChild(branch, std::move(nodePtr));
@@ -328,10 +373,15 @@ SHAMap::getMissingNodes(int max, SHAMapSyncFilter const* filter)
         512,  // number of async reads per pass
         f_.getFullBelowCache()->getGeneration());
 
+    // Guarded with isValid() for the same reason the late return below is: clearSynching() moves
+    // the state to Modifying, which would erase a verdict an earlier walk already reached. No path
+    // to that was found, since every site that condemns the map also clears the fullBelow flag this
+    // return reads, but the rule holds either way and one conjunct is what it costs.
     if (!root_->isInner() ||
         intr_ptr::staticPointerCast<SHAMapInnerNode>(root_)->isFullBelow(mn.generation))
     {
-        clearSynching();
+        if (isValid())
+            clearSynching();
         return std::move(mn.missingNodes);
     }
 
@@ -416,7 +466,11 @@ SHAMap::getMissingNodes(int max, SHAMapSyncFilter const* filter)
 
     } while (node != nullptr);
 
-    if (mn.missingNodes.empty())
+    // An empty result does not mean the map is complete when the walk judged it impossible on the
+    // way down: clearSynching() moves the state to Modifying, which would erase that verdict and
+    // report the map as satisfied. Asking nothing is the only part this has to get right, since
+    // clearSynching() is what a later walk would read.
+    if (mn.missingNodes.empty() && isValid())
         clearSynching();
 
     return std::move(mn.missingNodes);
@@ -569,10 +623,6 @@ SHAMap::addKnownNode(
 {
     XRPL_ASSERT(!nodeID.isRoot(), "xrpl::SHAMap::addKnownNode : valid node");
     XRPL_ASSERT(treeNode, "xrpl::SHAMap::addKnownNode : non-null tree node");
-    XRPL_ASSERT_IF(
-        treeNode->isLeaf(),
-        nodeID.isPrefixOf(leafKey(*treeNode)),
-        "xrpl::SHAMap::addKnownNode : leaf position consistent with node ID");
 
     if (!isSynching())
     {
@@ -606,6 +656,17 @@ SHAMap::addKnownNode(
         auto prevNode = inner;
         std::tie(currNode, currNodeID) = descend(inner, currNodeID, branch, filter);
 
+        if (!isValid())
+        {
+            // descend judged a node on the way down and condemned the map. Stops here rather than
+            // falling through, for two reasons: `childHash` was read before that descent, so the
+            // hash comparison below would report a corrupt node against a sender that sent nothing
+            // wrong, and if the node descend refused is the one offered here, that comparison would
+            // instead succeed and hook it after all.
+            JLOG(journal_.warn()) << "Node " << nodeID << " cannot be hooked into an invalid map";
+            return SHAMapAddNode::invalid();
+        }
+
         if (currNode != nullptr)
             continue;
 
@@ -637,6 +698,19 @@ SHAMap::addKnownNode(
             return SHAMapAddNode::useful();
         }
 
+        // A leaf's own key names its position, so a leaf offered for this slot has to agree with
+        // the ID it was offered under. The hash test above already proves the parent records this
+        // exact leaf here, so a disagreement is a property of the map rather than of the sender.
+        // This was an entry assertion, which is stripped under NDEBUG, and the node is hooked
+        // immediately below.
+        if (!belongsAt(nodeID, *treeNode))
+        {
+            JLOG(journal_.warn()) << "Leaf " << treeNode->getHash() << " does not belong at "
+                                  << nodeID << ", map is invalid";
+            state_ = SHAMapState::Invalid;
+            return SHAMapAddNode::invalid();
+        }
+
         if (backed_)
             canonicalize(childHash, treeNode);
 
@@ -802,7 +876,7 @@ SHAMap::getProofPath(uint256 const& key) const
         return {};
     }
 
-    if (auto const& node = stack.top().first; !node || node->isInner() ||
+    if (auto const& node = stack.top(); !node || node->isInner() ||
         intr_ptr::staticPointerCast<SHAMapLeafNode>(node)->peekItem()->key() != key)
     {
         JLOG(journal_.debug()) << "no path to " << key;
@@ -814,7 +888,7 @@ SHAMap::getProofPath(uint256 const& key) const
     while (!stack.empty())
     {
         Serializer s;
-        stack.top().first->serializeForWire(s);
+        stack.top()->serializeForWire(s);
         path.emplace_back(std::move(s.modData()));
         stack.pop();
     }

src/tests/libxrpl/shamap/SHAMap.cpp

@@ -7,12 +7,15 @@
 #include <xrpl/basics/base_uint.h>
 #include <xrpl/beast/utility/Journal.h>
 #include <xrpl/beast/utility/Zero.h>
+#include <xrpl/protocol/HashPrefix.h>
 #include <xrpl/protocol/Serializer.h>
+#include <xrpl/shamap/Family.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/SHAMapSyncFilter.h>
 #include <xrpl/shamap/SHAMapTreeNode.h>
 
 #include <gtest/gtest.h>
@@ -23,7 +26,9 @@
 #include <array>
 #include <cstddef>
 #include <cstdint>
+#include <map>
 #include <memory>
+#include <optional>
 #include <string>
 #include <string_view>
 #include <type_traits>
@@ -272,9 +277,9 @@ INSTANTIATE_TEST_SUITE_P(
     ::testing::Values(kBackedMode, kUnbackedMode),
     shamapBackingModeName);
 
-// Exercises the traversal stacks built by belowHelper. 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.
+// Exercises the traversal paths built by belowHelper. A path names each node's position by its own
+// length, and every push refuses a leaf whose key does not lie under the branch it was reached
+// through, in Release builds as well as Debug ones.
 class SHAMapTraversal : public ::testing::Test
 {
 protected:
@@ -455,6 +460,82 @@ TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys)
     }
 }
 
+TEST_F(SHAMapTraversal, update_give_item_on_absent_key_returns_false)
+{
+    tests::TestNodeFamily f{j_};
+    auto keys = deepFanOutKeys();
+    SHAMap map{SHAMapType::FREE, f};
+    fillMap(map, keys);
+
+    // Absent key: walkTowardsKey stops on an inner node with an empty branch, not a leaf, so
+    // updateGiveItem has to answer for a top of the wrong type. The public API permits the call,
+    // so it returns false rather than reporting UNREACHABLE and aborting an instrumented build.
+    auto const absentKey = uint256{std::string_view{std::string(64, '0')}};
+    Buffer vuc{32};
+    std::fill_n(vuc.data(), vuc.size(), std::uint8_t{2});
+    EXPECT_FALSE(map.updateGiveItem(
+        SHAMapNodeType::TnAccountState, makeShamapitem(absentKey, std::move(vuc))));
+
+    // The other shape an absent key takes: a single-item map queried with a key that selects the
+    // same root branch. The walk ends on the leaf it reached, whose key is not the one asked for,
+    // so the top is a leaf that does not hold the tag. Both shapes answer false. The difference
+    // only shows in an instrumented build, where reporting UNREACHABLE would abort.
+    SHAMap single{SHAMapType::FREE, f};
+    fillMap(single, {keys.front()});
+
+    auto probe = keys.front();
+    std::fill_n(probe.begin() + 1, probe.size() - 1, std::uint8_t{0});
+    ASSERT_NE(probe, keys.front());
+
+    Buffer other{32};
+    std::fill_n(other.data(), other.size(), std::uint8_t{3});
+    EXPECT_FALSE(single.updateGiveItem(
+        SHAMapNodeType::TnAccountState, makeShamapitem(probe, std::move(other))));
+}
+
+TEST_F(SHAMapTraversal, bounds_on_empty_map_return_end)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+    map.setUnbacked();
+
+    // An empty map still leaves its root on the path, so end() here is an answer rather than a
+    // refusal. This is what stops boundHelper from reading an empty path as an empty map.
+    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_below_the_root)
+{
+    tests::TestNodeFamily f{j_};
+    SHAMap map{SHAMapType::FREE, f};
+
+    auto const key = deepFanOutKeys().front();
+    fillMap(map, {key});
+
+    // fillMap uses addItem, which leaves root_ the inner node the map was constructed with and the
+    // single leaf one level below it. So the path holds both, and boundHelper judges the leaf
+    // first; for a probe the leaf does not qualify against it pops back to the root, whose scan
+    // finds nothing on the requested side.
+    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_};
@@ -901,4 +982,519 @@ TEST_F(SHAMapPathProof, substituted_leaf_for_other_key_is_rejected)
     EXPECT_FALSE(SHAMap::verifyProofPath(badRoot, kKey, badPath));
 }
 
+/**
+ * A filter that resolves exactly one node, by hash.
+ *
+ * Stands in for the real sync filters, which serve a node from a local cache
+ * keyed on its hash and so say nothing about where in a tree it belongs.
+ */
+class OneNodeFilter : public SHAMapSyncFilter
+{
+    std::map<SHAMapHash, Blob> nodes_;
+
+public:
+    OneNodeFilter(SHAMapHash const& hash, Blob blob)
+    {
+        nodes_.emplace(hash, std::move(blob));
+    }
+
+    explicit OneNodeFilter(std::vector<std::pair<SHAMapHash, Blob>> nodes)
+    {
+        for (auto& [hash, blob] : nodes)
+            nodes_.emplace(hash, std::move(blob));
+    }
+
+    void
+    gotNode(
+        bool,
+        SHAMapHash const&,
+        std::uint32_t,
+        Blob&&,  // NOLINT(cppcoreguidelines-rvalue-reference-param-not-moved)
+        SHAMapNodeType) const override
+    {
+    }
+
+    [[nodiscard]] std::optional<Blob>
+    getNode(SHAMapHash const& hash) const override
+    {
+        if (auto const it = nodes_.find(hash); it != nodes_.end())
+            return it->second;
+        return std::nullopt;
+    }
+};
+
+// A tree whose hashes all agree can still put a leaf where its key does not belong, because a hash
+// covers a node's contents rather than its position. Such a tree is what a proposer builds, and it
+// is accepted node by node, so the paths that hook a node are where the position has to be judged.
+class SHAMapMisplacedLeaf : public ::testing::Test
+{
+protected:
+    beast::Journal const j_{TestSink::instance()};
+
+    // An arbitrary key whose first nibble is 1, so its leaf belongs under branch 1 of the root.
+    static constexpr uint256 kKey{
+        "1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93"};
+
+    // Any branch other than the one kKey selects at depth 0.
+    static constexpr unsigned int kWrongBranch = 5;
+
+    /**
+     * A genuine leaf holding kKey, in the form a sync filter serves, with its
+     * hash.
+     *
+     * Taken from a map that placed the leaf correctly, so only its position is
+     * ever wrong below. Serialized with its prefix rather than in wire form,
+     * since that is what checkFilter parses.
+     *
+     * @param f the family the throwaway source map belongs to.
+     * @return the leaf's prefixed form and its hash, or an empty blob if the
+     *         map rejected the item.
+     */
+    static std::pair<Blob, SHAMapHash>
+    genuineLeaf(Family& f)
+    {
+        SHAMap source{SHAMapType::FREE, f};
+        source.setUnbacked();
+        if (!source.addItem(
+                SHAMapNodeType::TnAccountState,
+                makeShamapitem(kKey, Slice{kKey.data(), kKey.size()})))
+        {
+            return {};
+        }
+
+        auto const path = source.getProofPath(kKey);
+        if (!path.has_value() || path->empty())
+            return {};
+
+        auto leaf = SHAMapTreeNode::makeFromWire(makeSlice(path->front()));
+        if (!leaf || !leaf->isLeaf())
+            return {};
+        leaf->updateHash();
+
+        Serializer s;
+        leaf->serializeWithPrefix(s);
+        return {s.getData(), leaf->getHash()};
+    }
+
+    /**
+     * Assemble `map` as a root inner node holding a leaf's hash under the
+     * wrong branch.
+     *
+     * The root is installed directly, as a peer's would be, so the leaf itself
+     * stays unresolved until a walk consults the filter for it.
+     *
+     * @param map the map to assemble, which must be synching and empty.
+     * @param leafHash the hash the forged root records under kWrongBranch.
+     * @return whether the root was accepted.
+     */
+    static bool
+    forgeRoot(SHAMap& map, SHAMapHash const& leafHash)
+    {
+        Serializer s;
+        for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+            s.addBitString(i == kWrongBranch ? leafHash.asUInt256() : uint256{});
+        s.add8(kWireTypeInner);
+
+        auto root = SHAMapTreeNode::makeFromWire(makeSlice(s.peekData()));
+        if (!root)
+            return false;
+        root->updateHash();
+
+        auto const rootHash = root->getHash();
+        return map.addRootNode(rootHash, std::move(root), nullptr).isGood();
+    }
+};
+
+// getMissingNodes reaches a filter through descendAsync, which hooks whatever it resolves. The
+// verdict lands on the map, since every node from the root down hash-verified to get here.
+TEST_F(SHAMapMisplacedLeaf, walking_for_missing_nodes_invalidates_the_map)
+{
+    tests::TestNodeFamily sourceFamily{j_};
+    auto const [leafBlob, leafHash] = genuineLeaf(sourceFamily);
+    ASSERT_FALSE(leafBlob.empty());
+
+    // Its own family, so the leaf is reachable only through the filter rather than from a cache the
+    // source map warmed.
+    tests::TestNodeFamily targetFamily{j_};
+    SHAMap map{SHAMapType::FREE, uint256{}, targetFamily};
+    map.setUnbacked();
+    ASSERT_TRUE(forgeRoot(map, leafHash));
+    ASSERT_TRUE(map.isValid());
+
+    OneNodeFilter const filter{leafHash, leafBlob};
+    map.getMissingNodes(1, &filter);
+
+    EXPECT_FALSE(map.isValid());
+}
+
+// addKnownNode reaches a filter through the synchronous descend on its way to the position it was
+// given, which is the other route a node takes into a tree during acquisition.
+TEST_F(SHAMapMisplacedLeaf, hooking_a_known_node_invalidates_the_map)
+{
+    tests::TestNodeFamily sourceFamily{j_};
+    auto const [leafBlob, leafHash] = genuineLeaf(sourceFamily);
+    ASSERT_FALSE(leafBlob.empty());
+
+    tests::TestNodeFamily targetFamily{j_};
+    SHAMap map{SHAMapType::FREE, uint256{}, targetFamily};
+    map.setUnbacked();
+    ASSERT_TRUE(forgeRoot(map, leafHash));
+    ASSERT_TRUE(map.isValid());
+
+    // A key whose first nibble is kWrongBranch, so the walk descends the branch holding the leaf.
+    // An inner node is offered rather than a leaf, since a leaf would have to agree with this
+    // position and the point here is to reach the descent, not to hook what is offered.
+    auto const target = SHAMapNodeID::createID(
+        2, uint256{"5000000000000000000000000000000000000000000000000000000000000000"});
+
+    Serializer s;
+    for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+        s.addBitString(i == 0u ? uint256{1} : uint256{});
+    s.add8(kWireTypeInner);
+    auto offered = SHAMapTreeNode::makeFromWire(makeSlice(s.peekData()));
+    ASSERT_TRUE(offered);
+    offered->updateHash();
+
+    OneNodeFilter const filter{leafHash, leafBlob};
+    auto const result = map.addKnownNode(target, std::move(offered), &filter);
+
+    EXPECT_FALSE(map.isValid());
+
+    // The verdict matters as much as the state: it is what the acquisition paths charge a peer on,
+    // so a later change to it should fail here rather than pass quietly.
+    EXPECT_TRUE(result.isInvalid());
+    EXPECT_FALSE(result.isGood());
+}
+
+// addKnownNode also hooks the very node it was handed, on the path where the local store has
+// nothing to resolve for that slot. Such a node's position is known only from the ID the caller
+// supplied, so it is judged against the leaf's own key before it is hooked.
+TEST_F(SHAMapMisplacedLeaf, hooking_an_offered_misplaced_leaf_invalidates_the_map)
+{
+    tests::TestNodeFamily sourceFamily{j_};
+    auto const [leafBlob, leafHash] = genuineLeaf(sourceFamily);
+    ASSERT_FALSE(leafBlob.empty());
+
+    tests::TestNodeFamily targetFamily{j_};
+    SHAMap map{SHAMapType::FREE, uint256{}, targetFamily};
+    map.setUnbacked();
+    ASSERT_TRUE(forgeRoot(map, leafHash));
+    ASSERT_TRUE(map.isValid());
+
+    // The branch the forged root files the leaf under, which is not the one kKey selects.
+    uint256 wrongPrefix;
+    wrongPrefix.begin()[0] = static_cast<std::uint8_t>(kWrongBranch << 4);
+    auto const target = SHAMapNodeID::createID(1, wrongPrefix);
+
+    auto offered = SHAMapTreeNode::makeFromPrefix(makeSlice(leafBlob), leafHash);
+    ASSERT_TRUE(offered);
+    ASSERT_TRUE(offered->isLeaf());
+
+    // No filter, so the walk resolves nothing locally and the node offered here is the one that
+    // would be hooked.
+    auto const result = map.addKnownNode(target, std::move(offered), nullptr);
+
+    EXPECT_FALSE(map.isValid());
+    EXPECT_TRUE(result.isInvalid());
+    EXPECT_FALSE(result.isGood());
+}
+
+// A whole subtree can sit under the wrong branch through a single wrong child pointer, and that is
+// cheaper to produce than one misplaced leaf. Every leaf below such a subtree agrees with its own
+// final branch, because the subtree is internally well formed, and disagrees only at the level the
+// pointer is wrong. So judging a leaf against the last branch alone accepts all of them, and only
+// judging it against every branch above it refuses them.
+TEST_F(SHAMapMisplacedLeaf, iterating_a_misplaced_subtree_throws)
+{
+    // Two keys sharing their first nibble, so they hang off one inner node at depth 1.
+    constexpr uint256 kFirst{"a100000000000000000000000000000000000000000000000000000000000000"};
+    constexpr uint256 kSecond{"a200000000000000000000000000000000000000000000000000000000000000"};
+
+    tests::TestNodeFamily sourceFamily{j_};
+    SHAMap source{SHAMapType::FREE, sourceFamily};
+    source.setUnbacked();
+    for (auto const& k : {kFirst, kSecond})
+    {
+        ASSERT_TRUE(source.addItem(
+            SHAMapNodeType::TnAccountState, makeShamapitem(k, Slice{k.data(), k.size()})));
+    }
+    source.invariants();
+
+    // The inner node holding both leaves, as the filter will serve it. It belongs under branch 10,
+    // the nibble the two keys share, and the forged root below files it under kWrongBranch instead.
+    auto const subtree = source.getProofPath(kFirst);
+    ASSERT_TRUE(subtree.has_value());
+    // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
+    ASSERT_GE(subtree->size(), 2u);
+
+    // getProofPath returns the path deepest element first, so the element above the leaf is the
+    // inner node the two keys share.
+    auto inner = SHAMapTreeNode::makeFromWire(makeSlice((*subtree)[1]));
+    // NOLINTEND(bugprone-unchecked-optional-access)
+    ASSERT_TRUE(inner);
+    ASSERT_TRUE(inner->isInner());
+    inner->updateHash();
+
+    Serializer innerPrefixed;
+    inner->serializeWithPrefix(innerPrefixed);
+
+    // Both leaves are served as well. Without them the walk would stop on a node it genuinely does
+    // not have, and the throw below would say nothing about position.
+    std::vector<std::pair<SHAMapHash, Blob>> served;
+    served.emplace_back(inner->getHash(), innerPrefixed.getData());
+    for (auto const& k : {kFirst, kSecond})
+    {
+        auto const leafPath = source.getProofPath(k);
+        ASSERT_TRUE(leafPath.has_value());
+        // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
+        ASSERT_FALSE(leafPath->empty());
+        auto leaf = SHAMapTreeNode::makeFromWire(makeSlice(leafPath->front()));
+        // NOLINTEND(bugprone-unchecked-optional-access)
+        ASSERT_TRUE(leaf);
+        ASSERT_TRUE(leaf->isLeaf());
+        leaf->updateHash();
+
+        Serializer leafPrefixed;
+        leaf->serializeWithPrefix(leafPrefixed);
+        served.emplace_back(leaf->getHash(), leafPrefixed.getData());
+    }
+
+    tests::TestNodeFamily targetFamily{j_};
+    SHAMap map{SHAMapType::FREE, uint256{}, targetFamily};
+    map.setUnbacked();
+    ASSERT_TRUE(forgeRoot(map, inner->getHash()));
+
+    // The inner node itself carries no key, so nothing about it is out of place. Only a leaf below
+    // it can show that the branch it was reached through disagrees with the keys underneath.
+    OneNodeFilter const filter{std::move(served)};
+    map.getMissingNodes(4, &filter);
+
+    EXPECT_THROW(map.begin(), SHAMapMissingNode);
+
+    // The bounds have to refuse the same map, and refusing is not the same as answering end().
+    // This probe selects kWrongBranch at depth 0 and then the branch holding kFirst, so the walk
+    // reaches the misplaced leaf and clears the path. Both keys in the map are greater than the
+    // probe, so end() here would be the positive and wrong claim that no greater key exists.
+    uint256 probe;
+    probe.begin()[0] = static_cast<std::uint8_t>((kWrongBranch << 4) | 0x1u);
+    ASSERT_GT(kFirst, probe);
+    ASSERT_GT(kSecond, probe);
+
+    EXPECT_THROW(map.upperBound(probe), SHAMapMissingNode);
+    EXPECT_THROW(map.lowerBound(probe), SHAMapMissingNode);
+}
+
+// The descendAsync walk leaves the leaf hooked, since it resolved the node before the position
+// could be judged. Iterating it must not abort an instrumented build, and must not report the map
+// as empty either, which is what a plain nullptr from belowHelper would have meant.
+TEST_F(SHAMapMisplacedLeaf, iterating_a_hooked_misplaced_leaf_throws)
+{
+    tests::TestNodeFamily sourceFamily{j_};
+    auto const [leafBlob, leafHash] = genuineLeaf(sourceFamily);
+    ASSERT_FALSE(leafBlob.empty());
+
+    tests::TestNodeFamily targetFamily{j_};
+    SHAMap map{SHAMapType::FREE, uint256{}, targetFamily};
+    map.setUnbacked();
+    ASSERT_TRUE(forgeRoot(map, leafHash));
+
+    OneNodeFilter const filter{leafHash, leafBlob};
+    map.getMissingNodes(1, &filter);
+    ASSERT_FALSE(map.isValid());
+
+    EXPECT_THROW(map.begin(), SHAMapMissingNode);
+}
+
+// A childless inner node cannot be built by this process, since serializing one asserts it has a
+// branch, but it can be parsed from a blob. makeFromPrefix passes hashValid = true and
+// makeFullInner then adopts the hash it was fetched under rather than recomputing it, so sixteen
+// zero child hashes give a node whose own hash is whatever the parent claims for it. Every check
+// on the way in passes: it carries no key, so belongsAt waves it through, and canonicalize and
+// canonicalizeChild both compare against the hash it adopted.
+//
+// The map that results is well formed by every position rule and still cannot be walked, which is
+// the one case where belowHelper returns nullptr on a node it has just pushed. Both entry points
+// that can reach it must refuse rather than report an empty subtree.
+class SHAMapChildlessInner : public ::testing::Test
+{
+protected:
+    beast::Journal const j_{TestSink::instance()};
+
+    // An arbitrary key whose first nibble is 1, so its leaf belongs under branch 1 of the root.
+    static constexpr uint256 kKey{
+        "1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93"};
+
+    // A branch above the one kKey selects, so a scan reaches the leaf first and this second.
+    static constexpr unsigned int kEmptyInnerBranch = 5;
+
+    // The hash the forged root claims for the childless inner node. Arbitrary and non-zero: the
+    // node adopts whatever it is fetched under, so this is the one the parent has to record.
+    static constexpr uint256 kEmptyInnerHash{
+        "00000000000000000000000000000000000000000000000000000000000000ff"};
+
+    /**
+     * A leaf holding kKey in the form a sync filter serves, with its hash.
+     *
+     * @param f the family the throwaway source map belongs to.
+     * @return the leaf's prefixed form and its hash, or an empty blob if the
+     *         map rejected the item.
+     */
+    static std::pair<Blob, SHAMapHash>
+    genuineLeaf(Family& f)
+    {
+        SHAMap source{SHAMapType::FREE, f};
+        source.setUnbacked();
+        if (!source.addItem(
+                SHAMapNodeType::TnAccountState,
+                makeShamapitem(kKey, Slice{kKey.data(), kKey.size()})))
+        {
+            return {};
+        }
+
+        auto const path = source.getProofPath(kKey);
+        if (!path.has_value() || path->empty())
+            return {};
+
+        auto leaf = SHAMapTreeNode::makeFromWire(makeSlice(path->front()));
+        if (!leaf || !leaf->isLeaf())
+            return {};
+        leaf->updateHash();
+
+        Serializer s;
+        leaf->serializeWithPrefix(s);
+        return {s.getData(), leaf->getHash()};
+    }
+
+    /**
+     * The prefixed form of an inner node with no children at all.
+     *
+     * Assembled by hand rather than through serializeWithPrefix, which asserts
+     * the node has a branch, and that is exactly the shape being forged.
+     *
+     * @return four prefix bytes followed by sixteen zero child hashes.
+     */
+    static Blob
+    childlessInnerBlob()
+    {
+        Serializer s;
+        s.add32(HashPrefix::InnerNode);
+        for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+            s.addBitString(uint256{});
+        return s.getData();
+    }
+
+    /**
+     * Assemble `map` as a root holding the leaf where it belongs and the
+     * childless inner above it.
+     *
+     * @param map the map to assemble, which must be synching and empty.
+     * @param leafHash the hash of the leaf, recorded under the branch kKey
+     *                 selects.
+     * @return whether the root was accepted.
+     */
+    static bool
+    forgeRoot(SHAMap& map, SHAMapHash const& leafHash)
+    {
+        auto const leafBranch = selectBranch(0u, kKey);
+
+        Serializer s;
+        for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
+        {
+            if (i == leafBranch)
+            {
+                s.addBitString(leafHash.asUInt256());
+            }
+            else if (i == kEmptyInnerBranch)
+            {
+                s.addBitString(kEmptyInnerHash);
+            }
+            else
+            {
+                s.addBitString(uint256{});
+            }
+        }
+        s.add8(kWireTypeInner);
+
+        auto root = SHAMapTreeNode::makeFromWire(makeSlice(s.peekData()));
+        if (!root)
+            return false;
+        root->updateHash();
+
+        auto const rootHash = root->getHash();
+        return map.addRootNode(rootHash, std::move(root), nullptr).isGood();
+    }
+
+    /**
+     * Build a map holding both nodes, hooked in through a getMissingNodes walk.
+     *
+     * @param f the family the map belongs to.
+     * @return the map, or nullptr if any step was refused.
+     */
+    std::shared_ptr<SHAMap>
+    buildMap(Family& f) const
+    {
+        tests::TestNodeFamily sourceFamily{j_};
+        auto const [leafBlob, leafHash] = genuineLeaf(sourceFamily);
+        if (leafBlob.empty())
+            return nullptr;
+
+        auto map = std::make_shared<SHAMap>(SHAMapType::FREE, uint256{}, f);
+        map->setUnbacked();
+        if (!forgeRoot(*map, leafHash))
+            return nullptr;
+
+        std::vector<std::pair<SHAMapHash, Blob>> served;
+        served.emplace_back(leafHash, leafBlob);
+        served.emplace_back(SHAMapHash{kEmptyInnerHash}, childlessInnerBlob());
+
+        OneNodeFilter const filter{std::move(served)};
+
+        // The list has to come back empty. The filter serves both nodes, so anything still missing
+        // means a blob did not resolve, and a throw in the tests below would then come from
+        // descendThrow meeting an absent node rather than from the walk reaching the childless
+        // inner node. isValid() alone does not rule that out, since an unresolved child leaves the
+        // map valid.
+        if (!map->getMissingNodes(4, &filter).empty())
+            return nullptr;
+
+        // Nothing here is out of place, so no position check has anything to say about it.
+        if (!map->isValid())
+            return nullptr;
+        return map;
+    }
+};
+
+// An iterator increment reaches the childless inner node through peekNextItem, which pushes it and
+// then asks belowHelper for a leaf below it. Reporting "no leaf" would end the iteration early and
+// silently drop the rest of the map, so it throws instead.
+TEST_F(SHAMapChildlessInner, incrementing_past_a_childless_inner_node_throws)
+{
+    tests::TestNodeFamily f{j_};
+    auto const map = buildMap(f);
+    ASSERT_NE(map, nullptr);
+
+    auto it = map->begin();
+    ASSERT_NE(it, map->end());
+    EXPECT_EQ(it->key(), kKey);
+
+    EXPECT_THROW(++it, SHAMapMissingNode);
+}
+
+// upperBound reaches it through its own scan past the branch the probe takes. end() there would be
+// the positive claim that no greater key exists, so it throws for the same reason.
+TEST_F(SHAMapChildlessInner, bounding_across_a_childless_inner_node_throws)
+{
+    tests::TestNodeFamily f{j_};
+    auto const map = buildMap(f);
+    ASSERT_NE(map, nullptr);
+
+    // Shares kKey's first nibble, so the walk ends on the leaf, but compares greater, so the leaf
+    // does not qualify and the scan moves up to the root and on to kEmptyInnerBranch.
+    uint256 probe;
+    probe.begin()[0] = static_cast<std::uint8_t>(selectBranch(0u, kKey) << 4 | 0x0fu);
+    ASSERT_GT(probe, kKey);
+
+    EXPECT_THROW(map->upperBound(probe), SHAMapMissingNode);
+}
+
 }  // namespace xrpl::tests

src/tests/libxrpl/shamap/SHAMapSync.cpp

@@ -7,6 +7,7 @@
 #include <xrpl/protocol/Serializer.h>
 #include <xrpl/shamap/SHAMap.h>
 #include <xrpl/shamap/SHAMapItem.h>
+#include <xrpl/shamap/SHAMapLeafNode.h>
 #include <xrpl/shamap/SHAMapMissingNode.h>
 #include <xrpl/shamap/SHAMapTreeNode.h>
 
@@ -180,4 +181,165 @@ TEST_F(SHAMapSyncTest, sync)
     destination.invariants();
 }
 
+// `visitDifferences` walks this map and reports only the nodes the other map does not already
+// have, which is how a fetch pack is assembled (see LedgerMaster's populateFetchPack). It decides
+// what to skip by asking `hasInnerNode` and `hasLeafNode`, which are private, so it is the only
+// route a test has to them.
+//
+// Both answers matter to a peer waiting on the pack. Reporting a node it already has wastes space
+// in a size-limited message; skipping one it does not have leaves it unable to complete the
+// ledger. The tests below therefore check exactly which nodes come back, not just how many.
+
+// `visitDifferences` returns early while the root hash is still zero, so a map built here has to be
+// sealed before it can be compared against another. `setImmutable` only moves the state; `getHash`
+// is what unshares the tree and so makes the hashes real, and the expectation below is what forces
+// that call rather than merely documenting it.
+//
+// The ASSERT_ aborts only this helper, not the calling test, so every call site wraps it in
+// ASSERT_NO_FATAL_FAILURE. Without that the test would carry on with an unhashed map and fail again
+// further down, burying the real cause.
+static void
+finalize(SHAMap& map)
+{
+    map.setImmutable();
+    ASSERT_FALSE(map.getHash().isZero());
+}
+
+TEST_F(SHAMapSyncTest, visit_differences_reports_only_what_is_missing)
+{
+    TestNodeFamily f{j_};
+
+    // Enough shared items that they build inner nodes of their own: the walk then has whole
+    // matching subtrees to skip, which is what hasInnerNode decides. With only a couple of shared
+    // leaves the tree is too shallow for that path to be taken at all.
+    std::vector<boost::intrusive_ptr<SHAMapItem>> shared;
+    shared.reserve(64);
+    for (int i = 0; i < 64; ++i)
+    {
+        shared.push_back(makeRandomAS());
+    }
+
+    auto const extra = makeRandomAS();
+
+    SHAMap have{SHAMapType::FREE, f};
+    for (auto const& item : shared)
+    {
+        ASSERT_TRUE(have.addItem(SHAMapNodeType::TnAccountState, item));
+    }
+    ASSERT_NO_FATAL_FAILURE(finalize(have));
+
+    SHAMap want{SHAMapType::FREE, f};
+    for (auto const& item : shared)
+    {
+        ASSERT_TRUE(want.addItem(SHAMapNodeType::TnAccountState, item));
+    }
+    ASSERT_TRUE(want.addItem(SHAMapNodeType::TnAccountState, extra));
+    ASSERT_NO_FATAL_FAILURE(finalize(want));
+
+    std::vector<uint256> leaves;
+    std::size_t inners = 0;
+    want.visitDifferences(&have, [&leaves, &inners](SHAMapTreeNode const& node) {
+        if (node.isLeaf())
+        {
+            leaves.push_back(leafKey(node));
+        }
+        else
+        {
+            ++inners;
+        }
+        return true;
+    });
+
+    // Every shared leaf is already on the far side, so only `extra` is worth sending.
+    EXPECT_EQ(leaves, std::vector<uint256>{extra->key()});
+
+    // The inner nodes on `extra`'s path are reported, but the matching subtrees are skipped, so
+    // the walk must not have visited every inner node in the tree.
+    std::size_t allInners = 0;
+    want.visitNodes([&allInners](SHAMapTreeNode& node) {
+        if (!node.isLeaf())
+        {
+            ++allInners;
+        }
+        return true;
+    });
+    EXPECT_GT(inners, 0u);
+    EXPECT_LT(inners, allInners);
+}
+
+TEST_F(SHAMapSyncTest, visit_differences_against_identical_map_reports_nothing)
+{
+    TestNodeFamily f{j_};
+
+    auto const item = makeRandomAS();
+
+    SHAMap have{SHAMapType::FREE, f};
+    ASSERT_TRUE(have.addItem(SHAMapNodeType::TnAccountState, item));
+    ASSERT_NO_FATAL_FAILURE(finalize(have));
+
+    SHAMap want{SHAMapType::FREE, f};
+    ASSERT_TRUE(want.addItem(SHAMapNodeType::TnAccountState, item));
+    ASSERT_NO_FATAL_FAILURE(finalize(want));
+    ASSERT_EQ(want.getHash(), have.getHash());
+
+    std::size_t visited = 0;
+    want.visitDifferences(&have, [&visited]([[maybe_unused]] SHAMapTreeNode const& node) {
+        ++visited;
+        return true;
+    });
+
+    EXPECT_EQ(visited, 0u);
+}
+
+TEST_F(SHAMapSyncTest, visit_differences_against_no_map_reports_every_node)
+{
+    TestNodeFamily f{j_};
+
+    SHAMap want{SHAMapType::FREE, f};
+    for (int i = 0; i < 32; ++i)
+    {
+        ASSERT_TRUE(want.addItem(SHAMapNodeType::TnAccountState, makeRandomAS()));
+    }
+    ASSERT_NO_FATAL_FAILURE(finalize(want));
+
+    // A null `have` means the far side holds nothing, so every node counts as missing. Compared
+    // against visitNodes, which walks the same tree with no such filtering.
+    std::size_t differences = 0;
+    want.visitDifferences(nullptr, [&differences]([[maybe_unused]] SHAMapTreeNode const& node) {
+        ++differences;
+        return true;
+    });
+
+    std::size_t all = 0;
+    want.visitNodes([&all]([[maybe_unused]] SHAMapTreeNode& node) {
+        ++all;
+        return true;
+    });
+
+    EXPECT_GT(differences, 0u);
+    EXPECT_EQ(differences, all);
+}
+
+TEST_F(SHAMapSyncTest, visit_differences_stops_when_callback_returns_false)
+{
+    TestNodeFamily f{j_};
+
+    SHAMap want{SHAMapType::FREE, f};
+    for (int i = 0; i < 32; ++i)
+    {
+        ASSERT_TRUE(want.addItem(SHAMapNodeType::TnAccountState, makeRandomAS()));
+    }
+    ASSERT_NO_FATAL_FAILURE(finalize(want));
+
+    // Returning false is how populateFetchPack stops once the pack is full, so the walk must
+    // honor it rather than visiting the rest of the tree.
+    std::size_t visited = 0;
+    want.visitDifferences(nullptr, [&visited]([[maybe_unused]] SHAMapTreeNode const& node) {
+        ++visited;
+        return visited < 3;
+    });
+
+    EXPECT_EQ(visited, 3u);
+}
+
 }  // namespace xrpl::tests