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

86+    {
87+        fee += other.fee;
88+        size += other.size;
89+    }
90+
91+    /** Subtrack size and size of another FeeFrac from this one. */

0@@ -0,0 +1,21 @@
1+// Copyright (c) The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#include <util/feefrac.h>
6+
7+void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram)
8+{
9+    diagram.clear();

15+    for (auto& chunk : chunks) {
16+        FeeFrac& last = diagram.back();
17+        diagram.emplace_back(last.fee+chunk.fee, last.size+chunk.size);
18+    }
19+    return;
20+}

151+        std::swap(a.fee, b.fee);
152+        std::swap(a.size, b.size);
153+    }
154+};
155+
156+void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram);

12+BOOST_AUTO_TEST_CASE(feefrac_operators)
13+{
14+    FeeFrac p1{1000, 100}, p2{500, 300};
15+    FeeFrac sum{1500, 400};
16+    FeeFrac diff{500, -200};
17+    FeeFrac empty{0, 0};

11+
12+BOOST_AUTO_TEST_CASE(feefrac_operators)
13+{
14+    FeeFrac p1{1000, 100}, p2{500, 300};
15+    FeeFrac sum{1500, 400};
16+    FeeFrac diff{500, -200};

1300+
1301+    // new_diagram will have chunks that consist of each ancestor of
1302+    // direct_conflicts that is at its own fee/size, along with the replacement
1303+    // tx/package at its own fee/size
1304+
1305+    // old diagram will consist of each element of direct_conflicts either at

1322+        // Does this transaction have ancestors?
1323+        FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()};
1324+        if (txiter->GetCountWithAncestors() > 1) {
1325+            // We'll add chunks for either the ancestor by itself and this tx
1326+            // by itself, or for a combined package.
1327+            FeeFrac package{txiter->GetModFeesWithAncestors(), int32_t(txiter->GetSizeWithAncestors())};

1360+                new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize());
1361+            }
1362+        }
1363+    }
1364+    // + CNK
1365+    new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize));

301+        return strprintf("unable to compute mining score");
302+    }
303+
304+    if (!CompareFeerateDiagram(old_diagram, new_diagram)) {
305+        return strprintf("insufficient feerate");
306+    }

123+                                                CAmount replacement_fees,
124+                                                int64_t replacement_vsize)
125+                                                EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
126+
127+/** Compares two feerate diagrams. The shorter one is padded with a horizonal line. */
128+std::partial_ordering CompareFeerateDiagram(std::vector<FeeFrac>& dia0, std::vector<FeeFrac>& dia1);

42+    add_fn((a & 0xffffffff) * (b >> 32), 1);
43+    add_fn((a >> 32) * (b >> 32), 2);
44+    return ret;
45+}
46+
47+/* comparison helper for std::vector */

45+}
46+
47+/* comparison helper for std::vector */
48+std::strong_ordering compare_arrays(const std::array<uint32_t, 4>& a, const std::array<uint32_t, 4>& b) {
49+    for (size_t i = 0; i < a.size(); ++i) {
50+        if (a[i] < b[i]) return std::strong_ordering::less;

34+        }
35+        // Make sure no overflow.
36+        assert(carry == 0);
37+    };
38+
39+    // Multiply the 4 individual limbs (schoolbook multiply, with base 2^64).

17+std::array<uint32_t, 4> Mul128(uint64_t a, uint64_t b)
18+{
19+    std::array<uint32_t, 4> ret{0, 0, 0, 0};
20+
21+    /** Perform ret += v << (32 * pos), at 128-bit precision. */
22+    auto add_fn = [&](uint64_t v, int pos) {

58+    // Compute and compare signs.
59+    int sign_a = (a1 == 0 ? 0 : a1 < 0 ? -1 : 1) * (a2 == 0 ? 0 : a2 < 0 ? -1 : 1);
60+    int sign_b = (b1 == 0 ? 0 : b1 < 0 ? -1 : 1) * (b2 == 0 ? 0 : b2 < 0 ? -1 : 1);
61+    if (sign_a != sign_b) return sign_a <=> sign_b;
62+
63+    // Compute absolute values.

 8+#include <stdint.h>
 9+#include <compare>
10+#include <vector>
11+#include <util/check.h>
12+
13+namespace {

120+    {
121+        return a.fee == b.fee && a.size == b.size;
122+    }
123+
124+    /** Check if two FeeFrac objects are different (either fee or size differs). */
125+    friend inline bool operator!=(const FeeFrac& a, const FeeFrac& b) noexcept

155+        if (cross_a == cross_b) return b.size <=> a.size;
156+        return cross_a <=> cross_b;
157+    }
158+
159+    /** Check if a FeeFrac object is worse than another. */
160+    friend inline bool operator<(const FeeFrac& a, const FeeFrac& b) noexcept

18@@ -19,6 +19,8 @@
19 #include <limits>
20 #include <vector>
21 
22+#include <compare>

1270+        } else if (has_ancestor && has_descendant) {
1271+            return strprintf("%s has both ancestor and descendant", txid_string);
1272+        }
1273+        // Additionally enforce that:
1274+        // If we have a parent, we are its only child.
1275+        // If we have a child,  we are its only parent.

1266+        if (ancestor_count > 2) {
1267+            return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1);
1268+        } else if (descendant_count > 2) {
1269+            return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1);
1270+        } else if (has_ancestor && has_descendant) {
1271+            return strprintf("%s has both ancestor and descendant", txid_string);

114@@ -106,4 +115,20 @@ std::optional<std::string> PaysForRBF(CAmount original_fees,
115                                       CFeeRate relay_fee,
116                                       const uint256& txid);
117 
118+/**
119+ * The replacement transaction must improve the feerate diagram of the mempool.
120+ * @param[in]   pool                The mempool.
121+ * @param[in]   direct_conflicts    Set of txids corresponding to the direct conflicts
122+ * @param[in]   all_conflicts       Set of mempool entries corresponding to all conflicts

1330+                // therefore higher than the parent's fee. Chunk these
1331+                // together.
1332+                old_chunks.emplace_back(package);
1333+            } else {
1334+                // Add two points, one for the parent and one for this child.
1335+                old_chunks.emplace_back(package-individual);

739+     * Calculate the old and new mempool feerate diagrams relating to the
740+     * clusters that would be affected by a potential replacement transaction.
741+     *
742+     * @param[in] replacement_fees    Package fees
743+     * @param[in] replacement_vsize   Package size
744+     * @param[in] direct_conflicts    All transactions that would be removed directly (not via descendants)

294+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
295+    new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 300}};
296+
297+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
298+
299+    // Feerate of first chunk is sufficiently better, but second chunk is worse.

302+
303+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
304+
305+    // Feerate of first chunk is better, but second chunk is worse
306+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
307+    new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{999, 350}, FeeFrac{1150, 500}};

326+
327+    // No change in evaluation when tail check needed.
328+    BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram)));
329+
330+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
331+

740+     * clusters that would be affected by a potential replacement transaction.
741+     *
742+     * @param[in] replacement_fees    Package fees
743+     * @param[in] replacement_vsize   Package size
744+     * @param[in] direct_conflicts    All transactions that would be removed directly by
745+     *                                having a conflicting input wih a proposed transaction

326+
327+    BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
328+
329+    // Incomparable diagrams
330+    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
331+    new_diagram = {FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1000, 400}};

61+#endif
62+
63+    /** Fee. */
64+    int64_t fee;
65+    /** Size. */
66+    int32_t size;

25+ * - fee=2 size=2 (feerate 1)
26+ * - fee=1 size=1 (feerate 1)
27+ * - fee=3 size=2 (feerate 1.5)
28+ * - fee=2 size=1 (feerate 2)
29+ * - fee=0 size=0 (undefined feerate)
30+ *

1275+        }
1276+    }
1277+    return std::nullopt;
1278+}
1279+
1280+std::optional<std::string> CTxMemPool::CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts, std::vector<FeeFrac>& old_diagram, std::vector<FeeFrac>& new_diagram)

93+    FeeFrac fr1(f1, s1);
94+    assert(fr1.IsEmpty() == (s1 == 0));
95+
96+    int64_t f2 = provider.ConsumeIntegral<int64_t>();
97+    //int64_t f2 = provider.ConsumeIntegralInRange(std::numeric_limits<int64_t>::min() + 1,
98+    //                            std::numeric_limits<int64_t>::max() - 1);

349+    BOOST_CHECK(old_diagram.size() == 2);
350+    BOOST_CHECK(new_diagram.size() == 2);
351+    BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
352+    BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size));
353+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
354+    BOOST_CHECK(new_diagram[1] == FeeFrac(0, 0));

321+    const CAmount low_fee{CENT/100};
322+    const CAmount normal_fee{CENT/10};
323+    const CAmount high_fee{CENT};
324+
325+    // low -> high -> medium fee transactions that would result in two chunks together
326+    const auto low_tx= make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});

429+    BOOST_CHECK(old_diagram[2] == FeeFrac(low_fee + high_fee, low_size_2 + high_size_2));
430+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
431+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2));
432+    old_diagram.clear();
433+    new_diagram.clear();
434 }

0@@ -0,0 +1,93 @@
1+// Copyright (c) The Bitcoin Core developers

46+        const int unproc_side = next_point(0).size > next_point(1).size;
47+
48+        // let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
49+        // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
50+        // compute the direction coefficients of line AB and of line AP, and compare them. These
51+        // direction coefficients are fee per size, and can thus be expressed as FeeFracs.

154+
155+/** Takes the pre-computed chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
156+void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram);
157+
158+/** Compares two feerate diagrams (which must both start at size=0). The shorter one is implicitly
159+ * extended with a horizontal straight line. */

188+                                                const CTxMemPool::setEntries& direct_conflicts,
189+                                                const CTxMemPool::setEntries& all_conflicts,
190+                                                CAmount replacement_fees,
191+                                                int64_t replacement_vsize)
192+{
193+    // Require that the replacement strictly improve the mempool's fee vs. size diagram.

745+     * @param[in] all_conflicts       All transactions that would be removed
746+     * @param[out] old_diagram        The feerate diagram of the relevant clusters before accepting the new tx
747+     * @param[out] new_diagram        The feerate diagram of the relevant clusters after accepting the new tx
748+     * @return An optional error string if the conflicts don't match a calculable topology
749+     */
750+    std::optional<std::string> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts, std::vector<FeeFrac>& old_diagram, std::vector<FeeFrac>& new_diagram) EXCLUSIVE_LOCKS_REQUIRED(cs);

68+        if (point_b.size == point_p.size) ++next_index[!unproc_side];
69+    }
70+
71+    // Tail check at 0 feerate: Compare the remaining area. Use similar logic as in the loop above,
72+    // except we use a horizontal line instead of AB, as no point B exists anymore.
73+    const int long_side = next_index[1] != dias[1].size();

748+     * @return An optional error string if the conflicts don't match a calculable topology
749+     */
750+    std::optional<std::string> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts, std::vector<FeeFrac>& old_diagram, std::vector<FeeFrac>& new_diagram) EXCLUSIVE_LOCKS_REQUIRED(cs);
751+
752+    /* Check that all direct conflicts are in a cluster size of two or less. */
753+    std::optional<std::string> CheckConflictTopology(const setEntries& direct_conflicts);

 97+    chunks.push_back(empty);
 98+    chunks.push_back(oversized_1);
 99+    chunks.push_back(oversized_2);
100+
101+    FastRandomContext rng{/*fDeterministic=*/true};
102+    std::shuffle(chunks.begin(), chunks.end(), rng);

16+
17+    // And now build the diagram for these chunks.
18+    diagram.emplace_back(0, 0);
19+    for (auto& chunk : chunks) {
20+        FeeFrac& last = diagram.back();
21+        diagram.emplace_back(last.fee+chunk.fee, last.size+chunk.size);

54+        // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
55+        // and can thus be expressed as FeeFracs.
56+        const FeeFrac& point_p = next_point(unproc_side);
57+        const FeeFrac& point_a = prev_point(!unproc_side);
58+
59+        // Slope of AP can be negative, unlike AB

418+    BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
419+    BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2));
420+    old_diagram.clear();
421+    new_diagram.clear();
422+
423+    // You can have more than two direct conflicts if the therea re multiple effected clusters, all of size 2 or less

19+
20+    BOOST_CHECK(empty == FeeFrac{}); // same as no-args
21+
22+    BOOST_CHECK(p1 == p1);
23+    BOOST_CHECK(p1+p2 == sum);
24+    BOOST_CHECK(p1-p2 == diff);

66+    BOOST_CHECK(oversized_1 <= oversized_2);
67+    BOOST_CHECK(oversized_1 << oversized_2);
68+    BOOST_CHECK(oversized_1 != oversized_2);
69+
70+    // Tests paths that use double arithmetic
71+    FeeFrac busted{((int64_t) INT32_MAX) + 1, INT32_MAX};

0@@ -0,0 +1,124 @@
1+// Copyright (c) 2016-2021 The Bitcoin Core developers

294+    // Now test ImprovesFeerateDiagram with various levels of "package rbf" feerates
295+
296+    // It doesn't improve itself
297+    const auto res1 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size);
298+    BOOST_CHECK(res1.has_value());
299+    BOOST_CHECK(res1.value().first == DiagramCheckError::FAILURE);

342+    BOOST_CHECK(new_diagram[1] == FeeFrac(0, 1));
343+    old_diagram.clear();
344+    new_diagram.clear();
345+
346+    // Non-zero replacement fee/size
347+    const auto err_string3{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low}, old_diagram, new_diagram)};

754+     * @param[out] new_diagram        The feerate diagram of the relevant clusters after accepting the new tx
755+     * @return An optional error string if the conflicts don't match a calculable topology
756+     */
757+    std::optional<std::string> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts, std::vector<FeeFrac>& old_diagram, std::vector<FeeFrac>& new_diagram) EXCLUSIVE_LOCKS_REQUIRED(cs);
758+
759+    /* Check that all direct conflicts are in a cluster size of two or less. */

752+     * @param[in] all_conflicts       All transactions that would be removed
753+     * @param[out] old_diagram        The feerate diagram of the relevant clusters before accepting the new tx
754+     * @param[out] new_diagram        The feerate diagram of the relevant clusters after accepting the new tx
755+     * @return An optional error string if the conflicts don't match a calculable topology
756+     */
757+    std::optional<std::string> CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts, std::vector<FeeFrac>& old_diagram, std::vector<FeeFrac>& new_diagram) EXCLUSIVE_LOCKS_REQUIRED(cs);

145+        std::swap(a.size, b.size);
146+    }
147+};
148+
149+/** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
150+std::vector<FeeFrac> BuildDiagramFromChunks(const Span<const FeeFrac> chunks);

1273+            const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin();
1274+            if (our_parent->get().GetCountWithDescendants() > 2) {
1275+                return strprintf("%s is not the only child of parent %s",
1276+                                 txid_string, our_parent->get().GetSharedTx()->GetHash().ToString());
1277+            }
1278+        }

276+    TestMemPoolEntryHelper entry;
277+
278+    const CAmount low_fee{CENT/100};
279+    const CAmount normal_fee{CENT/10};
280+
281+    // One low feerate txn followed be normal feerate