Compare commits

...

4 Commits

Author SHA1 Message Date
Bart
2ab143cb9c fix: Clamp the depth used to index selectBranch's key byte
`selectBranch` reads the key byte at `depth / 2`, which is out of bounds for a
32-byte key once the depth reaches 64. Every branch selection in the map
funnels through here, so this is the one place a stray depth can turn into a
bad read. Assert the precondition for callers, then clamp anyway: a wrong
answer for an input that should never occur is better than reading past the
buffer. Verified under ASan that the unclamped form reads one byte past a
32-byte allocation while the clamped form does not.

`depthMask`'s own 65-entry table had the same exposure one level up, reachable
through the public `createID` factory rather than only from inside the map. A
depth past `kLeafDepth` indexed that table out of bounds, confirmed under ASan
as a 4-byte `global-buffer-overflow` immediately after `kMasks`. Both places
that can set a depth now clamp it: the constructor, which is the single point
every `SHAMapNodeID`'s `depth_` passes through, and `createID`, which needs its
own bound because it picks the mask while evaluating the constructor's
argument, before the constructor body could correct anything.

Clamping rather than throwing, which is what `getChildNodeID` does for the
analogous case: `createID` is reached from `getSHAMapNodeID` with a
peer-supplied depth, and two of that function's three callers
(`InboundTransactions::gotData`, `PeerImp::onMessage`) sit on paths with no
handler between them and a thread boundary, so a throw there would end the
process rather than the message. Clamping also has to fix up `id_` alongside
`depth_`, since a node ID whose id and depth disagree fails the invariant every
read of `id_` relies on. Leaving the depth unclamped would additionally let
`getRawString` narrow it to a byte, turning depth 256 into a node claiming to
be the root.

`deserializeSHAMapNodeID` gets the same mask check `isPrefixOf` already
performs, pulled into a shared `isPrefixOfAtDepth` helper, and the masking both
it and `createID` perform is now a named `maskedToDepth` rather than a repeated
bitwise-and.

Tests cover the depth-sensitivity of `isPrefixOf`, the guards that must hold
with asserts stripped, that `deserializeSHAMapNodeID` rejects an out-of-range
depth, and the clamp itself under both build configurations (`EXPECT_DEATH`
in a forked process when the assert is live, and the clamped result compared
against depth 63 when it is not). The clamp test also gates on
`ENABLE_VOIDSTAR`, not just `NDEBUG`: under Antithesis instrumentation
`XRPL_ASSERT` routes to a handler that records the hit but never aborts, so a
Debug build with voidstar enabled has `NDEBUG` undefined yet still hits the
same non-fatal assert as a release build, and without this gate would send
that configuration into the `EXPECT_DEATH` arm, where the forked child never
dies and the test fails, breaking the CI job that runs this suite under
`-Dvoidstar=ON`.
2026-08-21 17:35:39 -04:00
Bart
5891da909d docs: Correct the reachability claims on the leaf depth guards
The `visitDifferences` guard said an inner node at leaf depth could be seeded by a peer through an
earlier fetch-pack exchange, while the code marks the branch `UNREACHABLE`, which is documented as a
line that must not be reached in normal use or under fuzzing. Both cannot hold: a peer-reachable
assert is a peer-triggered abort. The code is the correct half. `addKnownNode` marks the map invalid
instead of hooking such a node in, fetch-pack blobs are checked against their content hash in
`LedgerMaster::getFetchPack`, and the parent child-hash slots they attach to chain up to a validated
root, so provoking this needs a preimage rather than a crafted message.

The comment now attributes the branch to a defect or a corrupt store, and records why the node is
still reported into the pack before its children are skipped: the wire form of an inner node carries
only child hashes, so the bad depth is never transmitted, and the recipient hooks blobs in by hash at
positions its own traversal picks. Withholding it would instead surface as a peer that cannot
complete a ledger, with nothing to diagnose locally.

The `hasLeafNode` comment credited its caller with a bound that does not apply. That guard limits the
depth of the caller's own traversal, whereas `hasLeafNode` runs on the map passed in and descends
from that map's root, so the check here is the only thing between a malformed map and the throw in
`getChildNodeID`, not a second line of defense. `hasInnerNode` is the one bounded by its caller.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
2026-08-21 17:35:11 -04:00
Bart
90ef662bc7 test: Cover the leaf key check in verifyProofPath
The check that the terminal leaf of a proof path actually holds the key being proved had no test
covering it, because the substitution it guards against cannot be built by swapping a leaf under a
genuine root: the hash comparison one level up rejects that first.

This test forges the root instead. It puts a genuine leaf from elsewhere in the map at the bottom of
a two-element path and wraps it in an inner node whose branch for the proved key carries that leaf's
hash, so the chain up to the root hash validates even though the leaf belongs to another key. A
control case runs the same forged root over the proved key's own leaf and expects acceptance, which
pins the leaf key comparison as the only reason the substituted path is rejected.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
2026-08-21 17:04:43 -04:00
Bart
d854982fd7 fix: Reject an inner node claimed at leaf depth in verifyProofPath
A SHAMap has 65 levels, and nibbles run out at level 64: `selectBranch` indexes
the key byte at `depth / 2`, so at depth 64 it reads byte 32 of a 32-byte key.
Only the leaf terminating a path may sit at that depth, but proof path nodes
come off the wire, so a peer could send 65 hash-chained inner nodes and drive
that read past the end of the buffer.

The existing length bound cannot be tightened to catch this: a path for two
keys sharing all 63 leading nibbles legitimately holds 64 inner nodes plus a
leaf, so 65 elements is valid. The claimed node type at the final depth is the
thing to reject, using `>=` rather than `==` to match the convention every
other `kLeafDepth` comparison in this codebase already follows.

Reachable from `TMProofPathResponse` via `LedgerReplayMsgHandler`; confirmed
under ASan with asserts compiled out that the unguarded read lands one byte
past a 32-byte heap allocation. Also closes a second gap: nothing checked the
terminal leaf's own key against `key`, so the hash chain alone let a peer
substitute any leaf whose subtree hashes matched at every level above it.
Pinned by tests: the 65-element path that must verify for both keys sharing
the deep prefix, and the forged all-inner path that must not.

Also guards `visitDifferences` against an inner node claimed at leaf depth:
`hasLeafNode` only checked the comparison map, not the map being walked, so a
corrupt node in the map under `visitDifferences` itself could still throw
uncaught. Skip such a node's children instead.
2026-08-18 10:17:53 -04:00
4 changed files with 425 additions and 14 deletions

View File

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

View File

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

View File

@@ -3,19 +3,23 @@
#include <xrpl/basics/Blob.h>
#include <xrpl/basics/Buffer.h>
#include <xrpl/basics/SHAMapHash.h>
#include <xrpl/basics/Slice.h>
#include <xrpl/basics/base_uint.h>
#include <xrpl/beast/utility/Journal.h>
#include <xrpl/beast/utility/Zero.h>
#include <xrpl/protocol/Serializer.h>
#include <xrpl/shamap/SHAMapInnerNode.h>
#include <xrpl/shamap/SHAMapItem.h>
#include <xrpl/shamap/SHAMapLeafNode.h>
#include <xrpl/shamap/SHAMapMissingNode.h>
#include <xrpl/shamap/SHAMapNodeID.h>
#include <xrpl/shamap/SHAMapTreeNode.h>
#include <gtest/gtest.h>
#include <helpers/TestSink.h>
#include <shamap/common.h>
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
@@ -346,4 +350,149 @@ TEST_F(SHAMapPathProof, verify_proof_path)
EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
}
// A legitimate proof path for two keys sharing all 63 leading nibbles is 65 elements: inner nodes
// at depths 0..63 plus the leaf at depth 64. This pins that the 65 bound is real, so the fix for
// the forged-path case below must not simply tighten the length limit.
TEST_F(SHAMapPathProof, legitimate_deep_path_is_sixty_five_elements)
{
tests::TestNodeFamily f{j_};
SHAMap map{SHAMapType::FREE, f};
map.setUnbacked();
auto const kA = uint256{std::string_view{std::string(63, 'a') + "1"}};
auto const kB = uint256{std::string_view{std::string(63, 'a') + "2"}};
for (auto const& k : {kA, kB})
{
Buffer vuc{32};
std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
ASSERT_TRUE(map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc))));
}
map.invariants();
auto const pathA = map.getProofPath(kA);
ASSERT_TRUE(pathA.has_value());
// NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
EXPECT_EQ(pathA->size(), 65u);
EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kA, *pathA));
// NOLINTEND(bugprone-unchecked-optional-access)
auto const pathB = map.getProofPath(kB);
ASSERT_TRUE(pathB.has_value());
// NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
EXPECT_EQ(pathB->size(), 65u);
EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kB, *pathB));
// NOLINTEND(bugprone-unchecked-optional-access)
}
// A forged path of 65 hash-chained inner nodes reaches depth kLeafDepth, where only the leaf
// terminating the path may sit. Such a path must be rejected.
TEST_F(SHAMapPathProof, all_inner_path_at_leaf_depth_is_rejected)
{
// An arbitrary well-formed key; the test does not care about its specific value.
constexpr uint256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
// Build upwards from the deepest node so each parent's selected branch carries its child's hash
// and the hash chain validates at every level.
std::vector<Blob> path;
SHAMapHash childHash{uint256{1}};
for (auto depth = SHAMap::kLeafDepth + 1u; depth-- > 0;)
{
auto const id = SHAMapNodeID::createID(std::min(depth, SHAMap::kLeafDepth - 1u), kTestKey);
auto const branch = selectBranch(id, kTestKey);
Serializer s;
for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
s.addBitString(i == branch ? childHash.asUInt256() : uint256{});
s.add8(kWireTypeInner);
path.push_back(s.getData());
auto node = SHAMapTreeNode::makeFromWire(makeSlice(path.back()));
ASSERT_TRUE(node);
node->updateHash();
childHash = node->getHash();
}
ASSERT_EQ(path.size(), 65u);
EXPECT_FALSE(SHAMap::verifyProofPath(childHash.asUInt256(), kTestKey, path));
}
/**
* Wrap a leaf blob in a forged root inner node whose branch for `key` carries that leaf's hash.
*
* The resulting two-element path hash-chains for `key` no matter which leaf sits at the bottom,
* which is exactly the substitution a peer could attempt.
*
* @param leafBlob the wire form of the leaf to place at the bottom of the path.
* @param key the key the forged path claims to prove.
* @return the path (deepest element first) and the forged root hash, or an empty path if the leaf
* blob does not parse.
*/
static std::pair<std::vector<Blob>, uint256>
forgeRootOverLeaf(Blob const& leafBlob, uint256 const& key)
{
auto leaf = SHAMapTreeNode::makeFromWire(makeSlice(leafBlob));
if (!leaf || !leaf->isLeaf())
return {};
leaf->updateHash();
auto const branch = selectBranch(SHAMapNodeID::createID(0, key), key);
Serializer s;
for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
s.addBitString(i == branch ? leaf->getHash().asUInt256() : uint256{});
s.add8(kWireTypeInner);
auto root = SHAMapTreeNode::makeFromWire(makeSlice(s.peekData()));
if (!root)
return {};
root->updateHash();
return {std::vector<Blob>{leafBlob, s.getData()}, root->getHash().asUInt256()};
}
// The hash chain above a leaf proves nothing about which key that leaf holds, so a peer can graft a
// genuine leaf from elsewhere in the map onto a path forged for another key. Comparing the terminal
// leaf's own key against the key being proved is what rejects it.
TEST_F(SHAMapPathProof, substituted_leaf_for_other_key_is_rejected)
{
tests::TestNodeFamily f{j_};
SHAMap map{SHAMapType::FREE, f};
map.setUnbacked();
// Two arbitrary keys differing in their first nibble, so each leaf hangs off the root directly.
constexpr uint256 kKey("1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93");
constexpr uint256 kOtherKey("e3f1a7d5b9c2e8f406a1d3b5c7e9f2a4d6b8c0e2f4a6d8b0c2e4f6a8d0b2c4e6");
for (auto const& k : {kKey, kOtherKey})
{
ASSERT_TRUE(map.addItem(
SHAMapNodeType::TnAccountState, makeShamapitem(k, Slice{k.data(), k.size()})));
}
map.invariants();
auto const ownPath = map.getProofPath(kKey);
auto const otherPath = map.getProofPath(kOtherKey);
ASSERT_TRUE(ownPath.has_value());
ASSERT_TRUE(otherPath.has_value());
// NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
// The genuine leaf blobs, deepest element first.
auto const& ownLeaf = ownPath->front();
auto const& otherLeaf = otherPath->front();
// NOLINTEND(bugprone-unchecked-optional-access)
// Control: the forged root is accepted when the leaf below it really is kKey's leaf, so the
// rejection below can only come from the leaf key comparison.
auto const [goodPath, goodRoot] = forgeRootOverLeaf(ownLeaf, kKey);
ASSERT_EQ(goodPath.size(), 2u);
EXPECT_TRUE(SHAMap::verifyProofPath(goodRoot, kKey, goodPath));
// Same forged root, but kOtherKey's leaf substituted at the bottom: the hash chain still
// validates, yet the path does not prove anything about kKey.
auto const [badPath, badRoot] = forgeRootOverLeaf(otherLeaf, kKey);
ASSERT_EQ(badPath.size(), 2u);
EXPECT_FALSE(SHAMap::verifyProofPath(badRoot, kKey, badPath));
}
} // namespace xrpl::tests

View File

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