mirror of
https://github.com/XRPLF/rippled.git
synced 2026-08-23 23:30:54 +00:00
Compare commits
4 Commits
pratik/ote
...
bthomee/sh
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
2ab143cb9c | ||
|
|
5891da909d | ||
|
|
90ef662bc7 | ||
|
|
d854982fd7 |
@@ -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
|
||||
|
||||
@@ -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();
|
||||
}
|
||||
|
||||
@@ -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
|
||||
|
||||
190
src/tests/libxrpl/shamap/SHAMapNodeID.cpp
Normal file
190
src/tests/libxrpl/shamap/SHAMapNodeID.cpp
Normal 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
|
||||
Reference in New Issue
Block a user