Merge bitcoin/bitcoin#29242: Mempool util: Add RBF diagram checks for single chunks against clusters of size 2

72959867784098137a50c34f86deca8235eef4f8 Unit tests for CalculateFeerateDiagramsForRBF (Greg Sanders)
b767e6bd47cb0fb8f7aea3fb10c597e59a35bf74 test: unit test for ImprovesFeerateDiagram (Greg Sanders)
7e89b659e1ddd0c04fa2bddba9706b5d1a1daec3 Add fuzz test for FeeFrac (Greg Sanders)
4d6528a3d6bf3821c216c68f99170e2faab5d63c fuzz: fuzz diagram creation and comparison (Greg Sanders)
e9c5aeb11d641b8cae373452339760809625021d test: Add tests for CompareFeerateDiagram and CheckConflictTopology (Greg Sanders)
588a98dccc5dbb6e331f28d83a4a10a13d70eb31 fuzz: Add fuzz target for ImprovesFeerateDiagram (Greg Sanders)
2079b80854e2595f6f696e7c13a56c7f2a7da9f4 Implement ImprovesFeerateDiagram (Greg Sanders)
66d966dcfaad3638f84654e710f403cb0a0a2ac7 Add FeeFrac unit tests (Greg Sanders)
ce8e22542ed0b4fa5794d3203207146418d59473 Add FeeFrac utils (Greg Sanders)

Pull request description:

  This is a smaller piece of https://github.com/bitcoin/bitcoin/pull/28984 broken off for easier review.

  Up to date explanation of diagram checks are here: https://delvingbitcoin.org/t/mempool-incentive-compatibility/553

  This infrastructure has two near term applications prior to cluster mempool:
  1) Limited Package RBF(https://github.com/bitcoin/bitcoin/pull/28984): We want to allow package RBF only when we know it improves the mempool. This narrowly scoped functionality allows use with v3-like topologies, and will be expanded at some point post-cluster mempool when diagram checks can be done efficiently against bounded cluster sizes.
  2) Replacement for single tx RBF(in a cluster size of up to two) against conflicts of up to cluster size two. `ImprovesFeerateDiagram` interface will have to change for this use-case, which is a future direction to solve certain pins and improve mempool incentive compatibility: https://delvingbitcoin.org/t/ephemeral-anchors-and-mev/383#diagram-checks-fix-this-3

  And longer-term, this would be the proposed way we would compute incentive compatibility for all conflicts, post-cluster mempool.

ACKs for top commit:
  sipa:
    utACK 72959867784098137a50c34f86deca8235eef4f8
  glozow:
    code review ACK 72959867784098137a50c34f86deca8235eef4f8
  murchandamus:
    utACK 72959867784098137a50c34f86deca8235eef4f8
  ismaelsadeeq:
    Re-ACK https://github.com/bitcoin/bitcoin/commit/72959867784098137a50c34f86deca8235eef4f8
  willcl-ark:
    crACK 72959867784098137a50c34f86deca8235eef4f8
  sdaftuar:
    ACK 72959867784098137a50c34f86deca8235eef4f8

Tree-SHA512: 79593e5a087801c06f06cc8b73aa3e7b96ab938d3b90f5d229c4e4bfca887a77b447605c49aa5eb7ddcead85706c534ac5eb6146ae2396af678f4beaaa5bea8e

13 files changed, 1310 insertions, 41 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 1f55bfbafd..0328dfc2cd 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -302,6 +302,7 @@ BITCOIN_CORE_H = \
   util/error.h \
   util/exception.h \
   util/fastrange.h \
+  util/feefrac.h \
   util/fees.h \
   util/fs.h \
   util/fs_helpers.h \
@@ -741,6 +742,7 @@ libbitcoin_util_a_SOURCES = \
   util/check.cpp \
   util/error.cpp \
   util/exception.cpp \
+  util/feefrac.cpp \
   util/fees.cpp \
   util/fs.cpp \
   util/fs_helpers.cpp \
@@ -983,6 +985,7 @@ libbitcoinkernel_la_SOURCES = \
   util/batchpriority.cpp \
   util/chaintype.cpp \
   util/check.cpp \
+  util/feefrac.cpp \
   util/fs.cpp \
   util/fs_helpers.cpp \
   util/hasher.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 9f9bdbbd0c..d345b41a0a 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -93,6 +93,7 @@ BITCOIN_TESTS =\
   test/denialofservice_tests.cpp \
   test/descriptor_tests.cpp \
   test/disconnected_transactions.cpp \
+  test/feefrac_tests.cpp \
   test/flatfile_tests.cpp \
   test/fs_tests.cpp \
   test/getarg_tests.cpp \
@@ -313,7 +314,9 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/descriptor_parse.cpp \
  test/fuzz/deserialize.cpp \
  test/fuzz/eval_script.cpp \
+ test/fuzz/feefrac.cpp \
  test/fuzz/fee_rate.cpp \
+ test/fuzz/feeratediagram.cpp \
  test/fuzz/fees.cpp \
  test/fuzz/flatfile.cpp \
  test/fuzz/float.cpp \
diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp
index f0830d8f22..a2c6990657 100644
--- a/src/policy/rbf.cpp
+++ b/src/policy/rbf.cpp
@@ -19,6 +19,8 @@
 #include <limits>
 #include <vector>
 
+#include <compare>
+
 RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool)
 {
     AssertLockHeld(pool.cs);
@@ -181,3 +183,24 @@ std::optional<std::string> PaysForRBF(CAmount original_fees,
     }
     return std::nullopt;
 }
+
+std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool& pool,
+                                                const CTxMemPool::setEntries& direct_conflicts,
+                                                const CTxMemPool::setEntries& all_conflicts,
+                                                CAmount replacement_fees,
+                                                int64_t replacement_vsize)
+{
+    // Require that the replacement strictly improve the mempool's feerate diagram.
+    std::vector<FeeFrac> old_diagram, new_diagram;
+
+    const auto diagram_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
+
+    if (!diagram_results.has_value()) {
+        return std::make_pair(DiagramCheckError::UNCALCULABLE, util::ErrorString(diagram_results).original);
+    }
+
+    if (!std::is_gt(CompareFeerateDiagram(diagram_results.value().second, diagram_results.value().first))) {
+        return std::make_pair(DiagramCheckError::FAILURE, "insufficient feerate: does not improve feerate diagram");
+    }
+    return std::nullopt;
+}
diff --git a/src/policy/rbf.h b/src/policy/rbf.h
index 5a33ed64a3..252fbec8e3 100644
--- a/src/policy/rbf.h
+++ b/src/policy/rbf.h
@@ -9,7 +9,9 @@
 #include <primitives/transaction.h>
 #include <threadsafety.h>
 #include <txmempool.h>
+#include <util/feefrac.h>
 
+#include <compare>
 #include <cstddef>
 #include <cstdint>
 #include <optional>
@@ -33,6 +35,13 @@ enum class RBFTransactionState {
     FINAL,
 };
 
+enum class DiagramCheckError {
+    /** Unable to calculate due to topology or other reason */
+    UNCALCULABLE,
+    /** New diagram wasn't strictly superior  */
+    FAILURE,
+};
+
 /**
  * Determine whether an unconfirmed transaction is signaling opt-in to RBF
  * according to BIP 125
@@ -106,4 +115,21 @@ std::optional<std::string> PaysForRBF(CAmount original_fees,
                                       CFeeRate relay_fee,
                                       const uint256& txid);
 
+/**
+ * The replacement transaction must improve the feerate diagram of the mempool.
+ * @param[in]   pool                The mempool.
+ * @param[in]   direct_conflicts    Set of in-mempool txids corresponding to the direct conflicts i.e.
+ *                                  input double-spends with the proposed transaction
+ * @param[in]   all_conflicts       Set of mempool entries corresponding to all transactions to be evicted
+ * @param[in]   replacement_fees    Fees of proposed replacement package
+ * @param[in]   replacement_vsize   Size of proposed replacement package
+ * @returns error type and string if mempool diagram doesn't improve, otherwise std::nullopt.
+ */
+std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool& pool,
+                                                const CTxMemPool::setEntries& direct_conflicts,
+                                                const CTxMemPool::setEntries& all_conflicts,
+                                                CAmount replacement_fees,
+                                                int64_t replacement_vsize)
+                                                EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
+
 #endif // BITCOIN_POLICY_RBF_H
diff --git a/src/test/feefrac_tests.cpp b/src/test/feefrac_tests.cpp
new file mode 100644
index 0000000000..2e015b382e
--- /dev/null
+++ b/src/test/feefrac_tests.cpp
@@ -0,0 +1,124 @@
+// Copyright (c) 2024-present The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <util/feefrac.h>
+#include <random.h>
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_AUTO_TEST_SUITE(feefrac_tests)
+
+BOOST_AUTO_TEST_CASE(feefrac_operators)
+{
+    FeeFrac p1{1000, 100}, p2{500, 300};
+    FeeFrac sum{1500, 400};
+    FeeFrac diff{500, -200};
+    FeeFrac empty{0, 0};
+    FeeFrac zero_fee{0, 1}; // zero-fee allowed
+
+    BOOST_CHECK(empty == FeeFrac{}); // same as no-args
+
+    BOOST_CHECK(p1 == p1);
+    BOOST_CHECK(p1 + p2 == sum);
+    BOOST_CHECK(p1 - p2 == diff);
+
+    FeeFrac p3{2000, 200};
+    BOOST_CHECK(p1 != p3); // feefracs only equal if both fee and size are same
+    BOOST_CHECK(p2 != p3);
+
+    FeeFrac p4{3000, 300};
+    BOOST_CHECK(p1 == p4-p3);
+    BOOST_CHECK(p1 + p3 == p4);
+
+    // Fee-rate comparison
+    BOOST_CHECK(p1 > p2);
+    BOOST_CHECK(p1 >= p2);
+    BOOST_CHECK(p1 >= p4-p3);
+    BOOST_CHECK(!(p1 >> p3)); // not strictly better
+    BOOST_CHECK(p1 >> p2); // strictly greater feerate
+
+    BOOST_CHECK(p2 < p1);
+    BOOST_CHECK(p2 <= p1);
+    BOOST_CHECK(p1 <= p4-p3);
+    BOOST_CHECK(!(p3 << p1)); // not strictly worse
+    BOOST_CHECK(p2 << p1); // strictly lower feerate
+
+    // "empty" comparisons
+    BOOST_CHECK(!(p1 >> empty)); // << will always result in false
+    BOOST_CHECK(!(p1 << empty));
+    BOOST_CHECK(!(empty >> empty));
+    BOOST_CHECK(!(empty << empty));
+
+    // empty is always bigger than everything else
+    BOOST_CHECK(empty > p1);
+    BOOST_CHECK(empty > p2);
+    BOOST_CHECK(empty > p3);
+    BOOST_CHECK(empty >= p1);
+    BOOST_CHECK(empty >= p2);
+    BOOST_CHECK(empty >= p3);
+
+    // check "max" values for comparison
+    FeeFrac oversized_1{4611686000000, 4000000};
+    FeeFrac oversized_2{184467440000000, 100000};
+
+    BOOST_CHECK(oversized_1 < oversized_2);
+    BOOST_CHECK(oversized_1 <= oversized_2);
+    BOOST_CHECK(oversized_1 << oversized_2);
+    BOOST_CHECK(oversized_1 != oversized_2);
+
+    // Tests paths that use double arithmetic
+    FeeFrac busted{(static_cast<int64_t>(INT32_MAX)) + 1, INT32_MAX};
+    BOOST_CHECK(!(busted < busted));
+
+    FeeFrac max_fee{2100000000000000, INT32_MAX};
+    BOOST_CHECK(!(max_fee < max_fee));
+    BOOST_CHECK(!(max_fee > max_fee));
+    BOOST_CHECK(max_fee <= max_fee);
+    BOOST_CHECK(max_fee >= max_fee);
+
+    FeeFrac max_fee2{1, 1};
+    BOOST_CHECK(max_fee >= max_fee2);
+
+}
+
+BOOST_AUTO_TEST_CASE(build_diagram_test)
+{
+    FeeFrac p1{1000, 100};
+    FeeFrac empty{0, 0};
+    FeeFrac zero_fee{0, 1};
+    FeeFrac oversized_1{4611686000000, 4000000};
+    FeeFrac oversized_2{184467440000000, 100000};
+
+    // Diagram-building will reorder chunks
+    std::vector<FeeFrac> chunks;
+    chunks.push_back(p1);
+    chunks.push_back(zero_fee);
+    chunks.push_back(empty);
+    chunks.push_back(oversized_1);
+    chunks.push_back(oversized_2);
+
+    // Caller in charge of sorting chunks in case chunk size limit
+    // differs from cluster size limit
+    std::sort(chunks.begin(), chunks.end(), [](const FeeFrac& a, const FeeFrac& b) { return a > b; });
+
+    // Chunks are now sorted in reverse order (largest first)
+    BOOST_CHECK(chunks[0] == empty); // empty is considered "highest" fee
+    BOOST_CHECK(chunks[1] == oversized_2);
+    BOOST_CHECK(chunks[2] == oversized_1);
+    BOOST_CHECK(chunks[3] == p1);
+    BOOST_CHECK(chunks[4] == zero_fee);
+
+    std::vector<FeeFrac> generated_diagram{BuildDiagramFromChunks(chunks)};
+    BOOST_CHECK(generated_diagram.size() == 1 + chunks.size());
+
+    // Prepended with an empty, then the chunks summed in order as above
+    BOOST_CHECK(generated_diagram[0] == empty);
+    BOOST_CHECK(generated_diagram[1] == empty);
+    BOOST_CHECK(generated_diagram[2] == oversized_2);
+    BOOST_CHECK(generated_diagram[3] == oversized_2 + oversized_1);
+    BOOST_CHECK(generated_diagram[4] == oversized_2 + oversized_1 + p1);
+    BOOST_CHECK(generated_diagram[5] == oversized_2 + oversized_1 + p1 + zero_fee);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/fuzz/feefrac.cpp b/src/test/fuzz/feefrac.cpp
new file mode 100644
index 0000000000..2c7553360e
--- /dev/null
+++ b/src/test/fuzz/feefrac.cpp
@@ -0,0 +1,123 @@
+// Copyright (c) 2024 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <util/feefrac.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <compare>
+#include <cstdint>
+#include <iostream>
+
+namespace {
+
+/** Compute a * b, represented in 4x32 bits, highest limb first. */
+std::array<uint32_t, 4> Mul128(uint64_t a, uint64_t b)
+{
+    std::array<uint32_t, 4> ret{0, 0, 0, 0};
+
+    /** Perform ret += v << (32 * pos), at 128-bit precision. */
+    auto add_fn = [&](uint64_t v, int pos) {
+        uint64_t accum{0};
+        for (int i = 0; i + pos < 4; ++i) {
+            // Add current value at limb pos in ret.
+            accum += ret[3 - pos - i];
+            // Add low or high half of v.
+            if (i == 0) accum += v & 0xffffffff;
+            if (i == 1) accum += v >> 32;
+            // Store lower half of result in limb pos in ret.
+            ret[3 - pos - i] = accum & 0xffffffff;
+            // Leave carry in accum.
+            accum >>= 32;
+        }
+        // Make sure no overflow.
+        assert(accum == 0);
+    };
+
+    // Multiply the 4 individual limbs (schoolbook multiply, with base 2^32).
+    add_fn((a & 0xffffffff) * (b & 0xffffffff), 0);
+    add_fn((a >> 32) * (b & 0xffffffff), 1);
+    add_fn((a & 0xffffffff) * (b >> 32), 1);
+    add_fn((a >> 32) * (b >> 32), 2);
+    return ret;
+}
+
+/* comparison helper for std::array */
+std::strong_ordering compare_arrays(const std::array<uint32_t, 4>& a, const std::array<uint32_t, 4>& b) {
+    for (size_t i = 0; i < a.size(); ++i) {
+        if (a[i] != b[i]) return a[i] <=> b[i];
+    }
+    return std::strong_ordering::equal;
+}
+
+std::strong_ordering MulCompare(int64_t a1, int64_t a2, int64_t b1, int64_t b2)
+{
+    // Compute and compare signs.
+    int sign_a = (a1 == 0 ? 0 : a1 < 0 ? -1 : 1) * (a2 == 0 ? 0 : a2 < 0 ? -1 : 1);
+    int sign_b = (b1 == 0 ? 0 : b1 < 0 ? -1 : 1) * (b2 == 0 ? 0 : b2 < 0 ? -1 : 1);
+    if (sign_a != sign_b) return sign_a <=> sign_b;
+
+    // Compute absolute values.
+    uint64_t abs_a1 = static_cast<uint64_t>(a1), abs_a2 = static_cast<uint64_t>(a2);
+    uint64_t abs_b1 = static_cast<uint64_t>(b1), abs_b2 = static_cast<uint64_t>(b2);
+    // Use (~x + 1) instead of the equivalent (-x) to silence the linter; mod 2^64 behavior is
+    // intentional here.
+    if (a1 < 0) abs_a1 = ~abs_a1 + 1;
+    if (a2 < 0) abs_a2 = ~abs_a2 + 1;
+    if (b1 < 0) abs_b1 = ~abs_b1 + 1;
+    if (b2 < 0) abs_b2 = ~abs_b2 + 1;
+
+    // Compute products of absolute values.
+    auto mul_abs_a = Mul128(abs_a1, abs_a2);
+    auto mul_abs_b = Mul128(abs_b1, abs_b2);
+    if (sign_a < 0) {
+        return compare_arrays(mul_abs_b, mul_abs_a);
+    } else {
+        return compare_arrays(mul_abs_a, mul_abs_b);
+    }
+}
+
+} // namespace
+
+FUZZ_TARGET(feefrac)
+{
+    FuzzedDataProvider provider(buffer.data(), buffer.size());
+
+    int64_t f1 = provider.ConsumeIntegral<int64_t>();
+    int32_t s1 = provider.ConsumeIntegral<int32_t>();
+    if (s1 == 0) f1 = 0;
+    FeeFrac fr1(f1, s1);
+    assert(fr1.IsEmpty() == (s1 == 0));
+
+    int64_t f2 = provider.ConsumeIntegral<int64_t>();
+    int32_t s2 = provider.ConsumeIntegral<int32_t>();
+    if (s2 == 0) f2 = 0;
+    FeeFrac fr2(f2, s2);
+    assert(fr2.IsEmpty() == (s2 == 0));
+
+    // Feerate comparisons
+    auto cmp_feerate = MulCompare(f1, s2, f2, s1);
+    assert(FeeRateCompare(fr1, fr2) == cmp_feerate);
+    assert((fr1 << fr2) == std::is_lt(cmp_feerate));
+    assert((fr1 >> fr2) == std::is_gt(cmp_feerate));
+
+    // Compare with manual invocation of FeeFrac::Mul.
+    auto cmp_mul = FeeFrac::Mul(f1, s2) <=> FeeFrac::Mul(f2, s1);
+    assert(cmp_mul == cmp_feerate);
+
+    // Same, but using FeeFrac::MulFallback.
+    auto cmp_fallback = FeeFrac::MulFallback(f1, s2) <=> FeeFrac::MulFallback(f2, s1);
+    assert(cmp_fallback == cmp_feerate);
+
+    // Total order comparisons
+    auto cmp_total = std::is_eq(cmp_feerate) ? (s2 <=> s1) : cmp_feerate;
+    assert((fr1 <=> fr2) == cmp_total);
+    assert((fr1 < fr2) == std::is_lt(cmp_total));
+    assert((fr1 > fr2) == std::is_gt(cmp_total));
+    assert((fr1 <= fr2) == std::is_lteq(cmp_total));
+    assert((fr1 >= fr2) == std::is_gteq(cmp_total));
+    assert((fr1 == fr2) == std::is_eq(cmp_total));
+    assert((fr1 != fr2) == std::is_neq(cmp_total));
+}
diff --git a/src/test/fuzz/feeratediagram.cpp b/src/test/fuzz/feeratediagram.cpp
new file mode 100644
index 0000000000..6d710093cb
--- /dev/null
+++ b/src/test/fuzz/feeratediagram.cpp
@@ -0,0 +1,119 @@
+// Copyright (c) 2023 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <stdint.h>
+
+#include <vector>
+
+#include <util/feefrac.h>
+#include <policy/rbf.h>
+
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <assert.h>
+
+namespace {
+
+/** Evaluate a diagram at a specific size, returning the fee as a fraction.
+ *
+ * Fees in diagram cannot exceed 2^32, as the returned evaluation could overflow
+ * the FeeFrac::fee field in the result. */
+FeeFrac EvaluateDiagram(int32_t size, Span<const FeeFrac> diagram)
+{
+    assert(diagram.size() > 0);
+    unsigned not_above = 0;
+    unsigned not_below = diagram.size() - 1;
+    // If outside the range of diagram, extend begin/end.
+    if (size < diagram[not_above].size) return {diagram[not_above].fee, 1};
+    if (size > diagram[not_below].size) return {diagram[not_below].fee, 1};
+    // Perform bisection search to locate the diagram segment that size is in.
+    while (not_below > not_above + 1) {
+        unsigned mid = (not_below + not_above) / 2;
+        if (diagram[mid].size <= size) not_above = mid;
+        if (diagram[mid].size >= size) not_below = mid;
+    }
+    // If the size matches a transition point between segments, return its fee.
+    if (not_below == not_above) return {diagram[not_below].fee, 1};
+    // Otherwise, interpolate.
+    auto dir_coef = diagram[not_below] - diagram[not_above];
+    assert(dir_coef.size > 0);
+    // Let A = diagram[not_above] and B = diagram[not_below]
+    const auto& point_a = diagram[not_above];
+    // We want to return:
+    //     A.fee + (B.fee - A.fee) / (B.size - A.size) * (size - A.size)
+    //   = A.fee + dir_coef.fee / dir_coef.size * (size - A.size)
+    //   = (A.fee * dir_coef.size + dir_coef.fee * (size - A.size)) / dir_coef.size
+    assert(size >= point_a.size);
+    return {point_a.fee * dir_coef.size + dir_coef.fee * (size - point_a.size), dir_coef.size};
+}
+
+std::weak_ordering CompareFeeFracWithDiagram(const FeeFrac& ff, Span<const FeeFrac> diagram)
+{
+    return FeeRateCompare(FeeFrac{ff.fee, 1}, EvaluateDiagram(ff.size, diagram));
+}
+
+std::partial_ordering CompareDiagrams(Span<const FeeFrac> dia1, Span<const FeeFrac> dia2)
+{
+    bool all_ge = true;
+    bool all_le = true;
+    for (const auto p1 : dia1) {
+        auto cmp = CompareFeeFracWithDiagram(p1, dia2);
+        if (std::is_lt(cmp)) all_ge = false;
+        if (std::is_gt(cmp)) all_le = false;
+    }
+    for (const auto p2 : dia2) {
+        auto cmp = CompareFeeFracWithDiagram(p2, dia1);
+        if (std::is_lt(cmp)) all_le = false;
+        if (std::is_gt(cmp)) all_ge = false;
+    }
+    if (all_ge && all_le) return std::partial_ordering::equivalent;
+    if (all_ge && !all_le) return std::partial_ordering::greater;
+    if (!all_ge && all_le) return std::partial_ordering::less;
+    return std::partial_ordering::unordered;
+}
+
+void PopulateChunks(FuzzedDataProvider& fuzzed_data_provider, std::vector<FeeFrac>& chunks)
+{
+    chunks.clear();
+
+    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 50)
+    {
+        chunks.emplace_back(fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(INT32_MIN>>1, INT32_MAX>>1), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(1, 1000000));
+    }
+    return;
+}
+
+} // namespace
+
+FUZZ_TARGET(build_and_compare_feerate_diagram)
+{
+    // Generate a random set of chunks
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    std::vector<FeeFrac> chunks1, chunks2;
+    FeeFrac empty{0, 0};
+
+    PopulateChunks(fuzzed_data_provider, chunks1);
+    PopulateChunks(fuzzed_data_provider, chunks2);
+
+    std::vector<FeeFrac> diagram1{BuildDiagramFromChunks(chunks1)};
+    std::vector<FeeFrac> diagram2{BuildDiagramFromChunks(chunks2)};
+
+    assert(diagram1.front() == empty);
+    assert(diagram2.front() == empty);
+
+    auto real = CompareFeerateDiagram(diagram1, diagram2);
+    auto sim = CompareDiagrams(diagram1, diagram2);
+    assert(real == sim);
+
+    // Do explicit evaluation at up to 1000 points, and verify consistency with the result.
+    LIMITED_WHILE(fuzzed_data_provider.remaining_bytes(), 1000) {
+        int32_t size = fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(0, diagram2.back().size);
+        auto eval1 = EvaluateDiagram(size, diagram1);
+        auto eval2 = EvaluateDiagram(size, diagram2);
+        auto cmp = FeeRateCompare(eval1, eval2);
+        if (std::is_lt(cmp)) assert(!std::is_gt(real));
+        if (std::is_gt(cmp)) assert(!std::is_lt(real));
+    }
+}
diff --git a/src/test/fuzz/rbf.cpp b/src/test/fuzz/rbf.cpp
index aa6385d12d..42008c6ad9 100644
--- a/src/test/fuzz/rbf.cpp
+++ b/src/test/fuzz/rbf.cpp
@@ -23,12 +23,30 @@ namespace {
 const BasicTestingSetup* g_setup;
 } // namespace
 
+const int NUM_ITERS = 10000;
+
+std::vector<COutPoint> g_outpoints;
+
 void initialize_rbf()
 {
     static const auto testing_setup = MakeNoLogFileContext<>();
     g_setup = testing_setup.get();
 }
 
+void initialize_package_rbf()
+{
+    static const auto testing_setup = MakeNoLogFileContext<>();
+    g_setup = testing_setup.get();
+
+    // Create a fixed set of unique "UTXOs" to source parents from
+    // to avoid fuzzer giving circular references
+    for (int i = 0; i < NUM_ITERS; ++i) {
+        g_outpoints.emplace_back();
+        g_outpoints.back().n = i;
+    }
+
+}
+
 FUZZ_TARGET(rbf, .init = initialize_rbf)
 {
     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
@@ -40,7 +58,7 @@ FUZZ_TARGET(rbf, .init = initialize_rbf)
 
     CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node)};
 
-    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
+    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), NUM_ITERS)
     {
         const std::optional<CMutableTransaction> another_mtx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
         if (!another_mtx) {
@@ -63,3 +81,98 @@ FUZZ_TARGET(rbf, .init = initialize_rbf)
         (void)IsRBFOptIn(tx, pool);
     }
 }
+
+void CheckDiagramConcave(std::vector<FeeFrac>& diagram)
+{
+    // Diagrams are in monotonically-decreasing feerate order.
+    FeeFrac last_chunk = diagram.front();
+    for (size_t i = 1; i<diagram.size(); ++i) {
+        FeeFrac next_chunk = diagram[i] - diagram[i-1];
+        assert(next_chunk <= last_chunk);
+        last_chunk = next_chunk;
+    }
+}
+
+FUZZ_TARGET(package_rbf, .init = initialize_package_rbf)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    SetMockTime(ConsumeTime(fuzzed_data_provider));
+
+    std::optional<CMutableTransaction> child = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
+    if (!child) return;
+
+    CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node)};
+
+    // Add a bunch of parent-child pairs to the mempool, and remember them.
+    std::vector<CTransaction> mempool_txs;
+    size_t iter{0};
+
+    LOCK2(cs_main, pool.cs);
+
+    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), NUM_ITERS)
+    {
+        // Make sure txns only have one input, and that a unique input is given to avoid circular references
+        std::optional<CMutableTransaction> parent = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
+        if (!parent) {
+            continue;
+        }
+        assert(iter <= g_outpoints.size());
+        parent->vin.resize(1);
+        parent->vin[0].prevout = g_outpoints[iter++];
+
+        mempool_txs.emplace_back(*parent);
+        pool.addUnchecked(ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()));
+        if (fuzzed_data_provider.ConsumeBool() && !child->vin.empty()) {
+            child->vin[0].prevout = COutPoint{mempool_txs.back().GetHash(), 0};
+        }
+        mempool_txs.emplace_back(*child);
+        pool.addUnchecked(ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()));
+    }
+
+    // Pick some transactions at random to be the direct conflicts
+    CTxMemPool::setEntries direct_conflicts;
+    for (auto& tx : mempool_txs) {
+        if (fuzzed_data_provider.ConsumeBool()) {
+            direct_conflicts.insert(*pool.GetIter(tx.GetHash()));
+        }
+    }
+
+    // Calculate all conflicts:
+    CTxMemPool::setEntries all_conflicts;
+    for (auto& txiter : direct_conflicts) {
+        pool.CalculateDescendants(txiter, all_conflicts);
+    }
+
+    // Calculate the feerate diagrams for a replacement.
+    CAmount replacement_fees = ConsumeMoney(fuzzed_data_provider);
+    int64_t replacement_vsize = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(1, 1000000);
+    auto calc_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
+
+    if (calc_results.has_value()) {
+        // Sanity checks on the diagrams.
+
+        // Diagrams start at 0.
+        assert(calc_results->first.front().size == 0);
+        assert(calc_results->first.front().fee == 0);
+        assert(calc_results->second.front().size == 0);
+        assert(calc_results->second.front().fee == 0);
+
+        CheckDiagramConcave(calc_results->first);
+        CheckDiagramConcave(calc_results->second);
+
+        CAmount replaced_fee{0};
+        int64_t replaced_size{0};
+        for (auto txiter : all_conflicts) {
+            replaced_fee += txiter->GetModifiedFee();
+            replaced_size += txiter->GetTxSize();
+        }
+        // The total fee of the new diagram should be the total fee of the old
+        // diagram - replaced_fee + replacement_fees
+        assert(calc_results->first.back().fee - replaced_fee + replacement_fees == calc_results->second.back().fee);
+        assert(calc_results->first.back().size - replaced_size + replacement_vsize == calc_results->second.back().size);
+    }
+
+    // If internals report error, wrapper should too
+    auto err_tuple{ImprovesFeerateDiagram(pool, direct_conflicts, all_conflicts, replacement_fees, replacement_vsize)};
+    if (!calc_results.has_value()) assert(err_tuple.has_value());
+}
diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp
index e6c135eed9..961fd62fe4 100644
--- a/src/test/rbf_tests.cpp
+++ b/src/test/rbf_tests.cpp
@@ -37,7 +37,7 @@ static inline CTransactionRef make_tx(const std::vector<CTransactionRef>& inputs
     return MakeTransactionRef(tx);
 }
 
-static void add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool)
+static CTransactionRef add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool)
     EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs)
 {
     AssertLockHeld(::cs_main);
@@ -50,6 +50,21 @@ static void add_descendants(const CTransactionRef& tx, int32_t num_descendants,
         pool.addUnchecked(entry.FromTx(next_tx));
         tx_to_spend = next_tx;
     }
+    // Return last created tx
+    return tx_to_spend;
+}
+
+static CTransactionRef add_descendant_to_parents(const std::vector<CTransactionRef>& parents, CTxMemPool& pool)
+    EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs)
+{
+    AssertLockHeld(::cs_main);
+    AssertLockHeld(pool.cs);
+    TestMemPoolEntryHelper entry;
+    // Assumes this isn't already spent in mempool
+    auto child_tx = make_tx(/*inputs=*/parents, /*output_values=*/{50 * CENT});
+    pool.addUnchecked(entry.FromTx(child_tx));
+    // Return last created tx
+    return child_tx;
 }
 
 BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
@@ -89,28 +104,46 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
     const auto tx8 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {999 * CENT});
     pool.addUnchecked(entry.Fee(high_fee).FromTx(tx8));
 
-    const auto entry1 = pool.GetIter(tx1->GetHash()).value();
-    const auto entry2 = pool.GetIter(tx2->GetHash()).value();
-    const auto entry3 = pool.GetIter(tx3->GetHash()).value();
-    const auto entry4 = pool.GetIter(tx4->GetHash()).value();
-    const auto entry5 = pool.GetIter(tx5->GetHash()).value();
-    const auto entry6 = pool.GetIter(tx6->GetHash()).value();
-    const auto entry7 = pool.GetIter(tx7->GetHash()).value();
-    const auto entry8 = pool.GetIter(tx8->GetHash()).value();
-
-    BOOST_CHECK_EQUAL(entry1->GetFee(), normal_fee);
-    BOOST_CHECK_EQUAL(entry2->GetFee(), normal_fee);
-    BOOST_CHECK_EQUAL(entry3->GetFee(), low_fee);
-    BOOST_CHECK_EQUAL(entry4->GetFee(), high_fee);
-    BOOST_CHECK_EQUAL(entry5->GetFee(), low_fee);
-    BOOST_CHECK_EQUAL(entry6->GetFee(), low_fee);
-    BOOST_CHECK_EQUAL(entry7->GetFee(), high_fee);
-    BOOST_CHECK_EQUAL(entry8->GetFee(), high_fee);
-
-    CTxMemPool::setEntries set_12_normal{entry1, entry2};
-    CTxMemPool::setEntries set_34_cpfp{entry3, entry4};
-    CTxMemPool::setEntries set_56_low{entry5, entry6};
-    CTxMemPool::setEntries all_entries{entry1, entry2, entry3, entry4, entry5, entry6, entry7, entry8};
+    // Normal txs, will chain txns right before CheckConflictTopology test
+    const auto tx9 = make_tx(/*inputs=*/ {m_coinbase_txns[5]}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx9));
+    const auto tx10 = make_tx(/*inputs=*/ {m_coinbase_txns[6]}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx10));
+
+    // Will make these two parents of single child
+    const auto tx11 = make_tx(/*inputs=*/ {m_coinbase_txns[7]}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx11));
+    const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx12));
+
+    const auto entry1_normal = pool.GetIter(tx1->GetHash()).value();
+    const auto entry2_normal = pool.GetIter(tx2->GetHash()).value();
+    const auto entry3_low = pool.GetIter(tx3->GetHash()).value();
+    const auto entry4_high = pool.GetIter(tx4->GetHash()).value();
+    const auto entry5_low = pool.GetIter(tx5->GetHash()).value();
+    const auto entry6_low_prioritised = pool.GetIter(tx6->GetHash()).value();
+    const auto entry7_high = pool.GetIter(tx7->GetHash()).value();
+    const auto entry8_high = pool.GetIter(tx8->GetHash()).value();
+    const auto entry9_unchained = pool.GetIter(tx9->GetHash()).value();
+    const auto entry10_unchained = pool.GetIter(tx10->GetHash()).value();
+    const auto entry11_unchained = pool.GetIter(tx11->GetHash()).value();
+    const auto entry12_unchained = pool.GetIter(tx12->GetHash()).value();
+
+    BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee);
+    BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee);
+    BOOST_CHECK_EQUAL(entry3_low->GetFee(), low_fee);
+    BOOST_CHECK_EQUAL(entry4_high->GetFee(), high_fee);
+    BOOST_CHECK_EQUAL(entry5_low->GetFee(), low_fee);
+    BOOST_CHECK_EQUAL(entry6_low_prioritised->GetFee(), low_fee);
+    BOOST_CHECK_EQUAL(entry7_high->GetFee(), high_fee);
+    BOOST_CHECK_EQUAL(entry8_high->GetFee(), high_fee);
+
+    CTxMemPool::setEntries set_12_normal{entry1_normal, entry2_normal};
+    CTxMemPool::setEntries set_34_cpfp{entry3_low, entry4_high};
+    CTxMemPool::setEntries set_56_low{entry5_low, entry6_low_prioritised};
+    CTxMemPool::setEntries set_78_high{entry7_high, entry8_high};
+    CTxMemPool::setEntries all_entries{entry1_normal, entry2_normal, entry3_low, entry4_high,
+                                       entry5_low, entry6_low_prioritised, entry7_high, entry8_high};
     CTxMemPool::setEntries empty_set;
 
     const auto unused_txid{GetRandHash()};
@@ -118,29 +151,29 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
     // Tests for PaysMoreThanConflicts
     // These tests use feerate, not absolute fee.
     BOOST_CHECK(PaysMoreThanConflicts(/*iters_conflicting=*/set_12_normal,
-                                      /*replacement_feerate=*/CFeeRate(entry1->GetModifiedFee() + 1, entry1->GetTxSize() + 2),
+                                      /*replacement_feerate=*/CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize() + 2),
                                       /*txid=*/unused_txid).has_value());
     // Replacement must be strictly greater than the originals.
-    BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1->GetModifiedFee(), entry1->GetTxSize()), unused_txid).has_value());
-    BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1->GetModifiedFee() + 1, entry1->GetTxSize()), unused_txid) == std::nullopt);
+    BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee(), entry1_normal->GetTxSize()), unused_txid).has_value());
+    BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize()), unused_txid) == std::nullopt);
     // These tests use modified fees (including prioritisation), not base fees.
-    BOOST_CHECK(PaysMoreThanConflicts({entry5}, CFeeRate(entry5->GetModifiedFee() + 1, entry5->GetTxSize()), unused_txid) == std::nullopt);
-    BOOST_CHECK(PaysMoreThanConflicts({entry6}, CFeeRate(entry6->GetFee() + 1, entry6->GetTxSize()), unused_txid).has_value());
-    BOOST_CHECK(PaysMoreThanConflicts({entry6}, CFeeRate(entry6->GetModifiedFee() + 1, entry6->GetTxSize()), unused_txid) == std::nullopt);
+    BOOST_CHECK(PaysMoreThanConflicts({entry5_low}, CFeeRate(entry5_low->GetModifiedFee() + 1, entry5_low->GetTxSize()), unused_txid) == std::nullopt);
+    BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid).has_value());
+    BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetModifiedFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid) == std::nullopt);
     // PaysMoreThanConflicts checks individual feerate, not ancestor feerate. This test compares
-    // replacement_feerate and entry4's feerate, which are the same. The replacement_feerate is
-    // considered too low even though entry4 has a low ancestor feerate.
-    BOOST_CHECK(PaysMoreThanConflicts(set_34_cpfp, CFeeRate(entry4->GetModifiedFee(), entry4->GetTxSize()), unused_txid).has_value());
+    // replacement_feerate and entry4_high's feerate, which are the same. The replacement_feerate is
+    // considered too low even though entry4_high has a low ancestor feerate.
+    BOOST_CHECK(PaysMoreThanConflicts(set_34_cpfp, CFeeRate(entry4_high->GetModifiedFee(), entry4_high->GetTxSize()), unused_txid).has_value());
 
     // Tests for EntriesAndTxidsDisjoint
     BOOST_CHECK(EntriesAndTxidsDisjoint(empty_set, {tx1->GetHash()}, unused_txid) == std::nullopt);
     BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx3->GetHash()}, unused_txid) == std::nullopt);
-    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2}, {tx2->GetHash()}, unused_txid).has_value());
+    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx2->GetHash()}, unused_txid).has_value());
     BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx1->GetHash()}, unused_txid).has_value());
     BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx2->GetHash()}, unused_txid).has_value());
     // EntriesAndTxidsDisjoint does not calculate descendants of iters_conflicting; it uses whatever
-    // the caller passed in. As such, no error is returned even though entry2 is a descendant of tx1.
-    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2}, {tx1->GetHash()}, unused_txid) == std::nullopt);
+    // the caller passed in. As such, no error is returned even though entry2_normal is a descendant of tx1.
+    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx1->GetHash()}, unused_txid) == std::nullopt);
 
     // Tests for PaysForRBF
     const CFeeRate incremental_relay_feerate{DEFAULT_INCREMENTAL_RELAY_FEE};
@@ -163,8 +196,8 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
     BOOST_CHECK(PaysForRBF(low_fee, high_fee + 99999999, 99999999, incremental_relay_feerate, unused_txid) == std::nullopt);
 
     // Tests for GetEntriesForConflicts
-    CTxMemPool::setEntries all_parents{entry1, entry3, entry5, entry7, entry8};
-    CTxMemPool::setEntries all_children{entry2, entry4, entry6};
+    CTxMemPool::setEntries all_parents{entry1_normal, entry3_low, entry5_low, entry7_high, entry8_high};
+    CTxMemPool::setEntries all_children{entry2_normal, entry4_high, entry6_low_prioritised};
     const std::vector<CTransactionRef> parent_inputs({m_coinbase_txns[0], m_coinbase_txns[1], m_coinbase_txns[2],
                                                 m_coinbase_txns[3], m_coinbase_txns[4]});
     const auto conflicts_with_parents = make_tx(parent_inputs, {50 * CENT});
@@ -215,15 +248,319 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
     BOOST_CHECK(HasNoNewUnconfirmed(/*tx=*/ *spends_unconfirmed.get(),
                                     /*pool=*/ pool,
                                     /*iters_conflicting=*/ all_entries) == std::nullopt);
-    BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, {entry2}) == std::nullopt);
+    BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, {entry2_normal}) == std::nullopt);
     BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, empty_set).has_value());
 
     const auto spends_new_unconfirmed = make_tx({tx1, tx8}, {36 * CENT});
-    BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, {entry2}).has_value());
+    BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, {entry2_normal}).has_value());
     BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, all_entries).has_value());
 
     const auto spends_conflicting_confirmed = make_tx({m_coinbase_txns[0], m_coinbase_txns[1]}, {45 * CENT});
-    BOOST_CHECK(HasNoNewUnconfirmed(*spends_conflicting_confirmed.get(), pool, {entry1, entry3}) == std::nullopt);
+    BOOST_CHECK(HasNoNewUnconfirmed(*spends_conflicting_confirmed.get(), pool, {entry1_normal, entry3_low}) == std::nullopt);
+
+    // Tests for CheckConflictTopology
+
+    // Tx4 has 23 descendants
+    BOOST_CHECK(pool.CheckConflictTopology(set_34_cpfp).has_value());
+
+    // No descendants yet
+    BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt);
+
+    // Add 1 descendant, still ok
+    add_descendants(tx9, 1, pool);
+    BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt);
+
+    // N direct conflicts; ok
+    BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt);
+
+    // Add 1 descendant, still ok, even if it's considered a direct conflict as well
+    const auto child_tx = add_descendants(tx10, 1, pool);
+    const auto entry10_child = pool.GetIter(child_tx->GetHash()).value();
+    BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt);
+    BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained, entry10_child}) == std::nullopt);
+
+    // One more, size 3 cluster too much
+    const auto grand_child_tx = add_descendants(child_tx, 1, pool);
+    const auto entry10_grand_child = pool.GetIter(grand_child_tx->GetHash()).value();
+    BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}).value(), strprintf("%s has 2 descendants, max 1 allowed", entry10_unchained->GetSharedTx()->GetHash().ToString()));
+    // even if direct conflict is descendent itself
+    BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry9_unchained, entry10_grand_child, entry11_unchained}).value(), strprintf("%s has 2 ancestors, max 1 allowed", entry10_grand_child->GetSharedTx()->GetHash().ToString()));
+
+    // Make a single child from two singleton parents
+    const auto two_parent_child_tx = add_descendant_to_parents({tx11, tx12}, pool);
+    const auto entry_two_parent_child = pool.GetIter(two_parent_child_tx->GetHash()).value();
+    BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry11_unchained}).value(), strprintf("%s is not the only parent of child %s", entry11_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString()));
+    BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry12_unchained}).value(), strprintf("%s is not the only parent of child %s", entry12_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString()));
+    BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_two_parent_child}).value(), strprintf("%s has 2 ancestors, max 1 allowed", entry_two_parent_child->GetSharedTx()->GetHash().ToString()));
+}
+
+BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup)
+{
+    CTxMemPool& pool = *Assert(m_node.mempool);
+    LOCK2(::cs_main, pool.cs);
+    TestMemPoolEntryHelper entry;
+
+    const CAmount low_fee{CENT/100};
+    const CAmount normal_fee{CENT/10};
+
+    // low feerate parent with normal feerate child
+    const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(tx1));
+    const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx2));
+
+    const auto entry1 = pool.GetIter(tx1->GetHash()).value();
+    const auto tx1_fee = entry1->GetModifiedFee();
+    const auto tx1_size = entry1->GetTxSize();
+    const auto entry2 = pool.GetIter(tx2->GetHash()).value();
+    const auto tx2_fee = entry2->GetModifiedFee();
+    const auto tx2_size = entry2->GetTxSize();
+
+    // Now test ImprovesFeerateDiagram with various levels of "package rbf" feerates
+
+    // It doesn't improve itself
+    const auto res1 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size);
+    BOOST_CHECK(res1.has_value());
+    BOOST_CHECK(res1.value().first == DiagramCheckError::FAILURE);
+    BOOST_CHECK(res1.value().second == "insufficient feerate: does not improve feerate diagram");
+
+    // With one more satoshi it does
+    BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size) == std::nullopt);
+
+    // Adding a grandchild makes the cluster size 3, which is uncalculable
+    const auto tx3 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx3));
+    const auto res3 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size);
+    BOOST_CHECK(res3.has_value());
+    BOOST_CHECK(res3.value().first == DiagramCheckError::UNCALCULABLE);
+    BOOST_CHECK(res3.value().second == strprintf("%s has 2 descendants, max 1 allowed", tx1->GetHash().GetHex()));
+
+}
+
+BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup)
+{
+    CTxMemPool& pool = *Assert(m_node.mempool);
+    LOCK2(::cs_main, pool.cs);
+    TestMemPoolEntryHelper entry;
+
+    const CAmount low_fee{CENT/100};
+    const CAmount normal_fee{CENT/10};
+    const CAmount high_fee{CENT};
+
+    // low -> high -> medium fee transactions that would result in two chunks together
+    const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(low_tx));
+
+    const auto entry_low = pool.GetIter(low_tx->GetHash()).value();
+    const auto low_size = entry_low->GetTxSize();
+
+    std::vector<FeeFrac> old_diagram, new_diagram;
+
+    // Replacement of size 1
+    const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})};
+    BOOST_CHECK(replace_one.has_value());
+    old_diagram = replace_one->first;
+    new_diagram = replace_one->second;
+    BOOST_CHECK(old_diagram.size() == 2);
+    BOOST_CHECK(new_diagram.size() == 2);
+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size));
+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(new_diagram[1] == FeeFrac(0, 1));
+
+    // Non-zero replacement fee/size
+    const auto replace_one_fee{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low})};
+    BOOST_CHECK(replace_one_fee.has_value());
+    old_diagram = replace_one_fee->first;
+    new_diagram = replace_one_fee->second;
+    BOOST_CHECK(old_diagram.size() == 2);
+    BOOST_CHECK(new_diagram.size() == 2);
+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size));
+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
+
+    // Add a second transaction to the cluster that will make a single chunk, to be evicted in the RBF
+    const auto high_tx = make_tx(/*inputs=*/ {low_tx}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(high_fee).FromTx(high_tx));
+    const auto entry_high = pool.GetIter(high_tx->GetHash()).value();
+    const auto high_size = entry_high->GetTxSize();
+
+    const auto replace_single_chunk{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low, entry_high})};
+    BOOST_CHECK(replace_single_chunk.has_value());
+    old_diagram = replace_single_chunk->first;
+    new_diagram = replace_single_chunk->second;
+    BOOST_CHECK(old_diagram.size() == 2);
+    BOOST_CHECK(new_diagram.size() == 2);
+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size));
+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
+
+    // Conflict with the 2nd tx, resulting in new diagram with three entries
+    const auto replace_cpfp_child{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high}, {entry_high})};
+    BOOST_CHECK(replace_cpfp_child.has_value());
+    old_diagram = replace_cpfp_child->first;
+    new_diagram = replace_cpfp_child->second;
+    BOOST_CHECK(old_diagram.size() == 2);
+    BOOST_CHECK(new_diagram.size() == 3);
+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size));
+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
+    BOOST_CHECK(new_diagram[2] == FeeFrac(low_fee + high_fee, low_size + low_size));
+
+    // third transaction causes the topology check to fail
+    const auto normal_tx = make_tx(/*inputs=*/ {high_tx}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(normal_fee).FromTx(normal_tx));
+    const auto entry_normal = pool.GetIter(normal_tx->GetHash()).value();
+    const auto normal_size = entry_normal->GetTxSize();
+
+    const auto replace_too_large{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/normal_fee, /*replacement_vsize=*/normal_size, {entry_low}, {entry_low, entry_high, entry_normal})};
+    BOOST_CHECK(!replace_too_large.has_value());
+    BOOST_CHECK_EQUAL(util::ErrorString(replace_too_large).original, strprintf("%s has 2 descendants, max 1 allowed", low_tx->GetHash().GetHex()));
+    old_diagram.clear();
+    new_diagram.clear();
+
+    // Make a size 2 cluster that is itself two chunks; evict both txns
+    const auto high_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(high_fee).FromTx(high_tx_2));
+    const auto entry_high_2 = pool.GetIter(high_tx_2->GetHash()).value();
+    const auto high_size_2 = entry_high_2->GetTxSize();
+
+    const auto low_tx_2 = make_tx(/*inputs=*/ {high_tx_2}, /*output_values=*/ {9 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(low_tx_2));
+    const auto entry_low_2 = pool.GetIter(low_tx_2->GetHash()).value();
+    const auto low_size_2 = entry_low_2->GetTxSize();
+
+    const auto replace_two_chunks_single_cluster{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high_2}, {entry_high_2, entry_low_2})};
+    BOOST_CHECK(replace_two_chunks_single_cluster.has_value());
+    old_diagram = replace_two_chunks_single_cluster->first;
+    new_diagram = replace_two_chunks_single_cluster->second;
+    BOOST_CHECK(old_diagram.size() == 3);
+    BOOST_CHECK(new_diagram.size() == 2);
+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(old_diagram[1] == FeeFrac(high_fee, high_size_2));
+    BOOST_CHECK(old_diagram[2] == FeeFrac(low_fee + high_fee, low_size_2 + high_size_2));
+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2));
+
+    // You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less
+    const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1));
+    const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value();
+
+    const auto conflict_2 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_2));
+    const auto conflict_2_entry = pool.GetIter(conflict_2->GetHash()).value();
+
+    const auto conflict_3 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_3));
+    const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value();
+
+    const auto replace_multiple_clusters{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry})};
+
+    BOOST_CHECK(replace_multiple_clusters.has_value());
+    old_diagram = replace_multiple_clusters->first;
+    new_diagram = replace_multiple_clusters->second;
+    BOOST_CHECK(old_diagram.size() == 4);
+    BOOST_CHECK(new_diagram.size() == 2);
+
+    // Add a child transaction to conflict_1 and make it cluster size 2, still one chunk due to same feerate
+    const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1_child));
+    const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
+
+    const auto replace_multiple_clusters_2{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry})};
+
+    BOOST_CHECK(replace_multiple_clusters_2.has_value());
+    old_diagram = replace_multiple_clusters_2->first;
+    new_diagram = replace_multiple_clusters_2->second;
+    BOOST_CHECK(old_diagram.size() == 4);
+    BOOST_CHECK(new_diagram.size() == 2);
+    old_diagram.clear();
+    new_diagram.clear();
+
+    // Add another descendant to conflict_1, making the cluster size > 2 should fail at this point.
+    const auto conflict_1_grand_child = make_tx(/*inputs=*/{conflict_1_child}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(high_fee).FromTx(conflict_1_grand_child));
+    const auto conflict_1_grand_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
+
+    const auto replace_cluster_size_3{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry, conflict_1_grand_child_entry})};
+
+    BOOST_CHECK(!replace_cluster_size_3.has_value());
+    BOOST_CHECK_EQUAL(util::ErrorString(replace_cluster_size_3).original, strprintf("%s has 2 descendants, max 1 allowed", conflict_1->GetHash().GetHex()));
+    BOOST_CHECK(old_diagram.empty());
+    BOOST_CHECK(new_diagram.empty());
+}
+
+BOOST_AUTO_TEST_CASE(feerate_diagram_utilities)
+{
+    // Sanity check the correctness of the feerate diagram comparison.
+
+    // A strictly better case.
+    std::vector<FeeFrac> old_diagram{{FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}};
+    std::vector<FeeFrac> new_diagram{{FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1050, 400}}};
+
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // Incomparable diagrams
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1000, 400}};
+
+    BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
+
+    // Strictly better but smaller size.
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 300}};
+
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // New diagram is strictly better due to the first chunk, even though
+    // second chunk contributes no fees
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 100}, FeeFrac{1100, 200}};
+
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // Feerate of first new chunk is better with, but second chunk is worse
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{999, 350}, FeeFrac{1150, 1000}};
+
+    BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
+
+    // If we make the second chunk slightly better, the new diagram now wins.
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{1000, 350}, FeeFrac{1150, 500}};
+
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // Identical diagrams, cannot be strictly better
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+
+    BOOST_CHECK(std::is_eq(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // Same aggregate fee, but different total size (trigger single tail fee check step)
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
+
+    // No change in evaluation when tail check needed.
+    BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram)));
+
+    // Padding works on either argument
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(new_diagram, old_diagram)));
+
+    // Trigger multiple tail fee check steps
+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}, FeeFrac{1050, 401}, FeeFrac{1050, 402}};
+
+    BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram)));
+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(new_diagram, old_diagram)));
+
+    // Multiple tail fee check steps, unordered result
+    new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}, FeeFrac{1050, 401}, FeeFrac{1050, 402}, FeeFrac{1051, 403}};
+    BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 0bee27c2b2..4047ceda3c 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -17,6 +17,7 @@
 #include <random.h>
 #include <reverse_iterator.h>
 #include <util/check.h>
+#include <util/feefrac.h>
 #include <util/moneystr.h>
 #include <util/overflow.h>
 #include <util/result.h>
@@ -1238,3 +1239,131 @@ std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uin
     }
     return clustered_txs;
 }
+
+std::optional<std::string> CTxMemPool::CheckConflictTopology(const setEntries& direct_conflicts)
+{
+    for (const auto& direct_conflict : direct_conflicts) {
+        // Ancestor and descendant counts are inclusive of the tx itself.
+        const auto ancestor_count{direct_conflict->GetCountWithAncestors()};
+        const auto descendant_count{direct_conflict->GetCountWithDescendants()};
+        const bool has_ancestor{ancestor_count > 1};
+        const bool has_descendant{descendant_count > 1};
+        const auto& txid_string{direct_conflict->GetSharedTx()->GetHash().ToString()};
+        // The only allowed configurations are:
+        // 1 ancestor and 0 descendant
+        // 0 ancestor and 1 descendant
+        // 0 ancestor and 0 descendant
+        if (ancestor_count > 2) {
+            return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1);
+        } else if (descendant_count > 2) {
+            return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1);
+        } else if (has_ancestor && has_descendant) {
+            return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string);
+        }
+        // Additionally enforce that:
+        // If we have a child,  we are its only parent.
+        // If we have a parent, we are its only child.
+        if (has_descendant) {
+            const auto& our_child = direct_conflict->GetMemPoolChildrenConst().begin();
+            if (our_child->get().GetCountWithAncestors() > 2) {
+                return strprintf("%s is not the only parent of child %s",
+                                 txid_string, our_child->get().GetSharedTx()->GetHash().ToString());
+            }
+        } else if (has_ancestor) {
+            const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin();
+            if (our_parent->get().GetCountWithDescendants() > 2) {
+                return strprintf("%s is not the only child of parent %s",
+                                 txid_string, our_parent->get().GetSharedTx()->GetHash().ToString());
+            }
+        }
+    }
+    return std::nullopt;
+}
+
+util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts)
+{
+    Assume(replacement_vsize > 0);
+
+    auto err_string{CheckConflictTopology(direct_conflicts)};
+    if (err_string.has_value()) {
+        // Unsupported topology for calculating a feerate diagram
+        return util::Error{Untranslated(err_string.value())};
+    }
+
+    // new diagram will have chunks that consist of each ancestor of
+    // direct_conflicts that is at its own fee/size, along with the replacement
+    // tx/package at its own fee/size
+
+    // old diagram will consist of each element of all_conflicts either at
+    // its own feerate (followed by any descendant at its own feerate) or as a
+    // single chunk at its descendant's ancestor feerate.
+
+    std::vector<FeeFrac> old_chunks;
+    // Step 1: build the old diagram.
+
+    // The above clusters are all trivially linearized;
+    // they have a strict topology of 1 or two connected transactions.
+
+    // OLD: Compute existing chunks from all affected clusters
+    for (auto txiter : all_conflicts) {
+        // Does this transaction have descendants?
+        if (txiter->GetCountWithDescendants() > 1) {
+            // Consider this tx when we consider the descendant.
+            continue;
+        }
+        // Does this transaction have ancestors?
+        FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()};
+        if (txiter->GetCountWithAncestors() > 1) {
+            // We'll add chunks for either the ancestor by itself and this tx
+            // by itself, or for a combined package.
+            FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())};
+            if (individual > package) {
+                // The individual feerate is higher than the package, and
+                // therefore higher than the parent's fee. Chunk these
+                // together.
+                old_chunks.emplace_back(package);
+            } else {
+                // Add two points, one for the parent and one for this child.
+                old_chunks.emplace_back(package - individual);
+                old_chunks.emplace_back(individual);
+            }
+        } else {
+            old_chunks.emplace_back(individual);
+        }
+    }
+
+    // No topology restrictions post-chunking; sort
+    std::sort(old_chunks.begin(), old_chunks.end(), std::greater());
+    std::vector<FeeFrac> old_diagram = BuildDiagramFromChunks(old_chunks);
+
+    std::vector<FeeFrac> new_chunks;
+
+    /* Step 2: build the NEW diagram
+     * CON = Conflicts of proposed chunk
+     * CNK = Proposed chunk
+     * NEW = OLD - CON + CNK: New diagram includes all chunks in OLD, minus
+     * the conflicts, plus the proposed chunk
+     */
+
+    // OLD - CON: Add any parents of direct conflicts that are not conflicted themselves
+    for (auto direct_conflict : direct_conflicts) {
+        // If a direct conflict has an ancestor that is not in all_conflicts,
+        // it can be affected by the replacement of the child.
+        if (direct_conflict->GetMemPoolParentsConst().size() > 0) {
+            // Grab the parent.
+            const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get();
+            if (!all_conflicts.count(mapTx.iterator_to(parent))) {
+                // This transaction would be left over, so add to the NEW
+                // diagram.
+                new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize());
+            }
+        }
+    }
+    // + CNK: Add the proposed chunk itself
+    new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize));
+
+    // No topology restrictions post-chunking; sort
+    std::sort(new_chunks.begin(), new_chunks.end(), std::greater());
+    std::vector<FeeFrac> new_diagram = BuildDiagramFromChunks(new_chunks);
+    return std::make_pair(old_diagram, new_diagram);
+}
diff --git a/src/txmempool.h b/src/txmempool.h
index 32f2c024f7..9dd4d56da7 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -21,6 +21,7 @@
 #include <util/epochguard.h>
 #include <util/hasher.h>
 #include <util/result.h>
+#include <util/feefrac.h>
 
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/identity.hpp>
@@ -736,6 +737,28 @@ public:
         return m_sequence_number;
     }
 
+    /**
+     * Calculate the old and new mempool feerate diagrams relating to the
+     * clusters that would be affected by a potential replacement transaction.
+     * (replacement_fees, replacement_vsize) values are gathered from a
+     * proposed set of replacement transactions that are considered as a single
+     * chunk, and represent their complete cluster. In other words, they have no
+     * in-mempool ancestors.
+     *
+     * @param[in] replacement_fees    Package fees
+     * @param[in] replacement_vsize   Package size (must be greater than 0)
+     * @param[in] direct_conflicts    All transactions that would be removed directly by
+     *                                having a conflicting input with a proposed transaction
+     * @param[in] all_conflicts       All transactions that would be removed
+     * @return old and new diagram pair respectively, or an error string if the conflicts don't match a calculable topology
+     */
+    util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts) EXCLUSIVE_LOCKS_REQUIRED(cs);
+
+    /* Check that all direct conflicts are in a cluster size of two or less. Each
+     * direct conflict may be in a separate cluster.
+     */
+    std::optional<std::string> CheckConflictTopology(const setEntries& direct_conflicts);
+
 private:
     /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
      *  the descendants for a single transaction that has been added to the
diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp
new file mode 100644
index 0000000000..a271fe585e
--- /dev/null
+++ b/src/util/feefrac.cpp
@@ -0,0 +1,86 @@
+// Copyright (c) The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <util/feefrac.h>
+#include <algorithm>
+#include <array>
+#include <vector>
+
+std::vector<FeeFrac> BuildDiagramFromChunks(const Span<const FeeFrac> chunks)
+{
+    std::vector<FeeFrac> diagram;
+    diagram.reserve(chunks.size() + 1);
+
+    diagram.emplace_back(0, 0);
+    for (auto& chunk : chunks) {
+        diagram.emplace_back(diagram.back() + chunk);
+    }
+    return diagram;
+}
+
+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1)
+{
+    /** Array to allow indexed access to input diagrams. */
+    const std::array<Span<const FeeFrac>, 2> dias = {dia0, dia1};
+    /** How many elements we have processed in each input. */
+    size_t next_index[2] = {1, 1};
+    /** Whether the corresponding input is strictly better than the other at least in one place. */
+    bool better_somewhere[2] = {false, false};
+    /** Get the first unprocessed point in diagram number dia. */
+    const auto next_point = [&](int dia) { return dias[dia][next_index[dia]]; };
+    /** Get the last processed point in diagram number dia. */
+    const auto prev_point = [&](int dia) { return dias[dia][next_index[dia] - 1]; };
+
+    // Diagrams should be non-empty, and first elements zero in size and fee
+    Assert(!dia0.empty() && !dia1.empty());
+    Assert(prev_point(0).IsEmpty());
+    Assert(prev_point(1).IsEmpty());
+
+    do {
+        bool done_0 = next_index[0] == dias[0].size();
+        bool done_1 = next_index[1] == dias[1].size();
+        if (done_0 && done_1) break;
+
+        // Determine which diagram has the first unprocessed point. If a single side is finished, use the
+        // other one. Only up to one can be done due to check above.
+        const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
+
+        // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
+        // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
+        // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
+        // and can thus be expressed as FeeFracs.
+        const FeeFrac& point_p = next_point(unproc_side);
+        const FeeFrac& point_a = prev_point(!unproc_side);
+
+        // Slope of AP can be negative, unlike AB
+        const auto slope_ap = point_p - point_a;
+        Assume(slope_ap.size > 0);
+        std::weak_ordering cmp = std::weak_ordering::equivalent;
+        if (done_0 || done_1) {
+            // If a single side has no points left, act as if AB has slope tail_feerate(of 0).
+            Assume(!(done_0 && done_1));
+            cmp = FeeRateCompare(slope_ap, FeeFrac(0, 1));
+        } else {
+            // If both sides have points left, compute B, and the slope of AB explicitly.
+            const FeeFrac& point_b = next_point(!unproc_side);
+            const auto slope_ab = point_b - point_a;
+            Assume(slope_ab.size >= slope_ap.size);
+            cmp = FeeRateCompare(slope_ap, slope_ab);
+
+            // If B and P have the same size, B can be marked as processed (in addition to P, see
+            // below), as we've already performed a comparison at this size.
+            if (point_b.size == point_p.size) ++next_index[!unproc_side];
+        }
+        // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
+        // better in P.
+        if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
+        if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
+        ++next_index[unproc_side];
+    } while(true);
+
+    // If both diagrams are better somewhere, they are incomparable.
+    if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
+    // Otherwise compare the better_somewhere values.
+    return better_somewhere[0] <=> better_somewhere[1];
+}
diff --git a/src/util/feefrac.h b/src/util/feefrac.h
new file mode 100644
index 0000000000..48bd287c7c
--- /dev/null
+++ b/src/util/feefrac.h
@@ -0,0 +1,160 @@
+// Copyright (c) The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_UTIL_FEEFRAC_H
+#define BITCOIN_UTIL_FEEFRAC_H
+
+#include <stdint.h>
+#include <compare>
+#include <vector>
+#include <span.h>
+#include <util/check.h>
+
+/** Data structure storing a fee and size, ordered by increasing fee/size.
+ *
+ * The size of a FeeFrac cannot be zero unless the fee is also zero.
+ *
+ * FeeFracs have a total ordering, first by increasing feerate (ratio of fee over size), and then
+ * by decreasing size. The empty FeeFrac (fee and size both 0) sorts last. So for example, the
+ * following FeeFracs are in sorted order:
+ *
+ * - fee=0 size=1 (feerate 0)
+ * - fee=1 size=2 (feerate 0.5)
+ * - fee=2 size=3 (feerate 0.667...)
+ * - fee=2 size=2 (feerate 1)
+ * - fee=1 size=1 (feerate 1)
+ * - fee=3 size=2 (feerate 1.5)
+ * - fee=2 size=1 (feerate 2)
+ * - fee=0 size=0 (undefined feerate)
+ *
+ * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard
+ * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering.
+ *
+ * The CompareFeeFrac, and >> and << operators only compare feerate and treat equal feerate but
+ * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any
+ * other.
+ */
+struct FeeFrac
+{
+    /** Fallback version for Mul (see below).
+     *
+     * Separate to permit testing on platforms where it isn't actually needed.
+     */
+    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
+    {
+        // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies.
+        int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
+        int64_t high = (a >> 32) * b;
+        return {high + (low >> 32), static_cast<uint32_t>(low)};
+    }
+
+    // Compute a * b, returning an unspecified but totally ordered type.
+#ifdef __SIZEOF_INT128__
+    static inline __int128 Mul(int64_t a, int32_t b) noexcept
+    {
+        // If __int128 is available, use 128-bit wide multiply.
+        return __int128{a} * b;
+    }
+#else
+    static constexpr auto Mul = MulFallback;
+#endif
+
+    int64_t fee;
+    int32_t size;
+
+    /** Construct an IsEmpty() FeeFrac. */
+    inline FeeFrac() noexcept : fee{0}, size{0} {}
+
+    /** Construct a FeeFrac with specified fee and size. */
+    inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
+
+    inline FeeFrac(const FeeFrac&) noexcept = default;
+    inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
+
+    /** Check if this is empty (size and fee are 0). */
+    bool inline IsEmpty() const noexcept {
+        return size == 0;
+    }
+
+    /** Add fee and size of another FeeFrac to this one. */
+    void inline operator+=(const FeeFrac& other) noexcept
+    {
+        fee += other.fee;
+        size += other.size;
+    }
+
+    /** Subtract fee and size of another FeeFrac from this one. */
+    void inline operator-=(const FeeFrac& other) noexcept
+    {
+        fee -= other.fee;
+        size -= other.size;
+    }
+
+    /** Sum fee and size. */
+    friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        return {a.fee + b.fee, a.size + b.size};
+    }
+
+    /** Subtract both fee and size. */
+    friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        return {a.fee - b.fee, a.size - b.size};
+    }
+
+    /** Check if two FeeFrac objects are equal (both same fee and same size). */
+    friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        return a.fee == b.fee && a.size == b.size;
+    }
+
+    /** Compare two FeeFracs just by feerate. */
+    friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
+        return cross_a <=> cross_b;
+    }
+
+    /** Check if a FeeFrac object has strictly lower feerate than another. */
+    friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
+        return cross_a < cross_b;
+    }
+
+    /** Check if a FeeFrac object has strictly higher feerate than another. */
+    friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
+        return cross_a > cross_b;
+    }
+
+    /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
+    friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
+    {
+        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
+        if (cross_a == cross_b) return b.size <=> a.size;
+        return cross_a <=> cross_b;
+    }
+
+    /** Swap two FeeFracs. */
+    friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
+    {
+        std::swap(a.fee, b.fee);
+        std::swap(a.size, b.size);
+    }
+};
+
+/** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
+std::vector<FeeFrac> BuildDiagramFromChunks(Span<const FeeFrac> chunks);
+
+/** Compares two feerate diagrams. The shorter one is implicitly
+ * extended with a horizontal straight line.
+ *
+ * A feerate diagram consists of a list of (fee, size) points with the property that size
+ * is strictly increasing and that the first entry is (0, 0).
+ */
+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
+
+#endif // BITCOIN_UTIL_FEEFRAC_H