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

instagibbs · 2024-01-12T18:07:44Z

This is a smaller piece of #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:

Limited Package RBF(Cluster size 2 package rbf #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.
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.

DrahtBot · 2024-01-12T18:07:47Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	sipa, glozow, murchandamus, ismaelsadeeq, willcl-ark, sdaftuar
Concept ACK	hebasto

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

No conflicts as of last run.

DrahtBot · 2024-01-12T18:29:27Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/20435922692}

instagibbs · 2024-01-12T21:38:22Z

ready for review

cc @glozow @ismaelsadeeq @achow101

src/util/feefrac.h

src/util/feefrac.cpp

ismaelsadeeq · 2024-01-16T14:14:22Z

src/util/feefrac.h

+    }
+};
+
+void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram);


Maybe add a docstring on what BuildDiagramFromUnsortedChunks does in and out params description that are doxygen compatible?

added comment

The correctness of the result of BuildDiagramFromUnsortedChunks very much depends on the assumption that the chunks can be reordered w.r.t. one another, which seems to be the case in the current PR, but will very much not be the case going forward in a general cluster mempool world.

I would suggest either:

Removing the sorting step in this function (moving it to the caller). The function can then take Span<const FeeFrac> as input too, and perhaps in a further iteration (in a later PR) this function could then be turned into one that actually performs chunking too.

Adding a big comment on the function definition that it needs independent chunks.

The correctness of the result of BuildDiagramFromUnsortedChunks very much depends on the assumption that the chunks can be reordered w.r.t. one another, which seems to be the case in the current PR, but will very much not be the case going forward in a general cluster mempool world.

No objection to your suggested change here, but I don't follow this comment -- in a general cluster mempool world, unless we were to bound chunk sizes to something smaller than a cluster size (resulting in the possibility of chunk feerates not being monotonically decreasing), I think for the purposes of a feerate diagram it is fine to sort by chunk feerate and permit equal-feerate-chunks to be reordered? From the perspective of a feerate diagram, two such diagrams are equivalent.

If you're suggesting that we want to preserve the ability in the future to impose a chunk size limit, then yes I agree that we should rewrite this... Is there another case that I'm overlooking?

@sdaftuar that matches my understanding.

Removing the sorting step in this function (moving it to the caller). The function can then take Span as input too, and perhaps in a further iteration (in a later PR) this function could then be turned into one that actually performs chunking too.

Took this suggestion

src/test/feefrac_tests.cpp

ismaelsadeeq · 2024-01-16T15:36:53Z

src/txmempool.cpp

+    // 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 direct_conflicts either at


I think you mean all_conflicts here

Suggested change

// old diagram will consist of each element of direct_conflicts either at

// old diagram will consist of each element of all_conflicts either at

src/txmempool.cpp

src/policy/rbf.cpp

DrahtBot · 2024-01-18T20:29:48Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/20632055548}

src/policy/rbf.h

src/test/feefrac_tests.cpp

src/test/fuzz/feefrac.cpp

src/util/feefrac.h

DrahtBot · 2024-01-19T20:32:35Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/20672153966}

instagibbs · 2024-01-19T21:42:00Z

test failure appears to be spurious wallet failure, ready for review

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com> Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com>

This new function takes the populated sets of direct and all conflicts computed in the current mempool, assuming the replacements are a single chunk, and computes a diagram check. The diagram check only works against cluster sizes of 2 or less, and fails if it encounters a different topology. Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com>

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com>

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com> Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

sipa

utACK 7295986

Some non-blocking nits:

sipa · 2024-03-18T14:59:51Z

src/util/feefrac.h

+ * 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


In commit "Add FeeFrac utils":

Self-nit: CompareFeeFrac -> FeeRateCompare

opened in follow-up

sipa · 2024-03-18T15:04:32Z

src/policy/rbf.cpp

+                                                CAmount replacement_fees,
+                                                int64_t replacement_vsize)
+{
+    // Require that the replacement strictly improve the mempool's feerate diagram.


In commit "Implement ImprovesFeerateDiagram"

Nit: improves

opened in follow-up

glozow

code review ACK 7295986

Various non-blocking comments about the tests, can be saved for a followup.

glozow · 2024-03-19T12:00:32Z

src/test/rbf_tests.cpp

+    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)));
+


e9c5aeb could do the reciprocal checks everywhere i.e.

BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram))); BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram))); ... BOOST_CHECK(std::is_eq(CompareFeerateDiagram(old_diagram, new_diagram))); BOOST_CHECK(std::is_eq(CompareFeerateDiagram(new_diagram, old_diagram)));

opened in follow-up

src/test/rbf_tests.cpp

glozow · 2024-03-19T12:11:14Z

src/test/rbf_tests.cpp

+    // Tests for CheckConflictTopology
+
+    // Tx4 has 23 descendants
+    BOOST_CHECK(pool.CheckConflictTopology(set_34_cpfp).has_value());


Check the value of the string as well, i.e. "%s has 23 descendants, max 1 allowed"

opened in follow-up

glozow · 2024-03-19T12:17:04Z

src/txmempool.cpp

+        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());
+            }
+        }


I see you've added coverage for the "not the only parent" case, but I don't see a test for "not the only child" case. Also nothing failed when I commented it out.

glozow · 2024-03-19T12:25:37Z

src/test/rbf_tests.cpp

+    const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(tx1));


b767e6b This is perhaps the place to add coverage for the fact that modified feerate is used, e.g. PrioritiseTransaction here and check that using a replacement_fee between modified and base makes a difference in the result.

opened in follow-up

glozow · 2024-03-19T12:27:08Z

src/test/fuzz/rbf.cpp

+        parent->vin[0].prevout = g_outpoints[iter++];
+
+        mempool_txs.emplace_back(*parent);
+        pool.addUnchecked(ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()));


Similar to previous comment, could do a random PrioritiseTransaction here

if (fuzzed_data_provider.ConsumeBool()) { pool.PrioritiseTransaction(mempool_txs.back().GetHash().ToUint256(), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(-100000, 100000)); }

opened in follow-up

glozow · 2024-03-19T12:53:05Z

src/test/rbf_tests.cpp

+    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));


7295986
Nit, but this old_diagram, new_diagram assignment setup is

making a copies of everything

brittle / easy for the tests to bleed into each other, e.g. if you forgot to reset the variables (and, previously, if you forgot to clear them between tests)

repetitive

checking size + each element of a vector when you could just compare it to an expected vector

Something cleaner might e.g. look like:

{ const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})}; BOOST_CHECK(replace_one.has_value()); std::vector<FeeFrac> expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee, low_size)}; BOOST_CHECK(replace_one->first == expected_old_diagram); std::vector<FeeFrac> expected_new_diagram{FeeFrac(0, 0), FeeFrac(0, 1)}; BOOST_CHECK(replace_one->second == expected_new_diagram); }

opened in follow-up

glozow · 2024-03-19T14:12:59Z

src/test/rbf_tests.cpp

+
+    // With one more satoshi it does
+    BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size) == std::nullopt);
+


Suggested change

// With one less vB it does

BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size - 1) == std::nullopt);

opened in follow-up

glozow · 2024-03-19T14:40:49Z

src/test/fuzz/rbf.cpp

+
+    // 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());


I think we can be a bit more specific than this, i.e. if !calc_results.has_value() then err_tuple.value().first == DiagramCheckError::UNCALCULABLE

opened in follow-up

glozow · 2024-03-19T14:50:00Z

src/test/fuzz/rbf.cpp

+        // 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);


This test for ImprovesFeerateDiagram doesn't seem very strict beyond checking NEW = OLD - CON + replacement and that internal errors = wrapper errors. For example, if I swap !is_gt for a !is_eq in ImprovesFeerateDiagram, this fuzzer is still happy with everything. There is coverage for that in other places, but it seems like we could be writing stronger assertions?

Can we perhaps add a check that the result is consistent with what CompareFeerateDiagram says when comparing the diagrams returned in calc_results? Or some kind of sanity check that when the new diagram ends with lower fees, we should be getting DiagramCheckError::FAILURE?

I added a couple more checks where I could clearly add them in followup

instagibbs · 2024-03-19T15:36:23Z

Thanks for the review!

As long as it's nits only, I will compile a list of 👍 I will accomplish on a follow-up PR.

murchandamus

utACK 7295986

I also only have non-blocking nits

murchandamus · 2024-03-14T19:19:17Z

src/txmempool.cpp

+    // Step 1: build the old diagram.
+
+    // The above clusters are all trivially linearized;
+    // they have a strict topology of 1 or two connected transactions.


Nit:

Suggested change

// they have a strict topology of 1 or two connected transactions.

// they have a strict topology of one or two connected transactions.

or

Suggested change

// they have a strict topology of 1 or two connected transactions.

// they have a strict topology of 1 or 2 connected transactions.

opened in follow-up

src/util/feefrac.h

murchandamus · 2024-03-19T18:51:27Z

src/txmempool.cpp

+        }
+    }
+
+    // No topology restrictions post-chunking; sort


In "Implement ImprovesFeerateDiagram" (2079b80):

I’m not sure I understand why there are "No topology restrictions post-chunking". I am guessing that this is alluding to all affected clusters at most having two transactions and therefore each having only two possible configurations: child has higher feerate and the cluster is one chunk, or child has lower feerate and the cluster has two chunks, but the chunk with the child naturally sorts after the chunk with the parent. If that’s what is being alluded to here, perhaps you could elaborate in the comment if you touch this again.

Also, I have one open question here. It is my understanding that we do not combine two transactions into one chunk if they tie in feerate. If we have a parent and a child that have the same feerate, and the child is smaller, would that not mean that the chunk with the child could be sorted in front of the chunk with the parent incorrectly?

Thinking more about this, I think this does not matter here, because even if the child were sorted in front of the parent, given them having the same feerate, it would result in the same feerate diagram.

Also, it seems to me that this problem could be sidestepped by chunking together a parent and a child on equal feerate for the purpose of the diagram, if you used if (individual >= package) { in line 1320 instead of if (individual > package) {.

It'd need to be if (!(individual << package)) {, because >= and > use size as tie breaker when comparing FeeFracs. I think that's generally an improvement, actually, because size shouldn't matter here.

If that’s what is being alluded to here, perhaps you could elaborate in the comment if you touch this again.

Will elaborate a bit on the chunk construction comments in a follow-up.

I think that's generally an improvement, actually, because size shouldn't matter here.

Agreed, at a minimum I'd change to individual >> package to get rid of the tie-breaking behavior which is confusing to have here. Will take on a chosen change in follow-up.

opened in follow-up with >> as noted

src/util/feefrac.h

murchandamus · 2024-03-19T19:15:55Z

src/test/fuzz/feeratediagram.cpp

+    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};


In "fuzz: fuzz diagram creation and comparison" (4d6528a):

Nit: The use of vsize throughout would help differentiate the mixed occurrences of diagram.size() and diagram[i].size

leaving as is

murchandamus · 2024-03-19T19:26:26Z

src/test/rbf_tests.cpp

+    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


Nit: In "Unit tests for CalculateFeerateDiagramsForRBF" (7295986):

Suggested change

// You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less

// You can have more than two direct conflicts if the there are multiple affected clusters, all of size 2 or less

opened in follow-up

murchandamus · 2024-03-19T19:40:51Z

src/test/rbf_tests.cpp

+    const CAmount normal_fee{CENT/10};
+    const CAmount high_fee{CENT};
+
+    // low -> high -> medium fee transactions that would result in two chunks together


In "Unit tests for CalculateFeerateDiagramsForRBF" (7295986):

Nit: this comment appears to make the unstated assumption that the three transactions are of similar vsize

opened in follow-up

ismaelsadeeq

Re-ACK 7295986

willcl-ark

crACK 7295986

This looks good on a first pass of the code, and was a good introduction (to me) for how we are approaching implementation of the Diagrammatic fee rate checks, which matches my current understanding of the proposed concept.

Left only two small non-blocking nits.

In addition, while checking each commit I did notice that clang-format could be run on most (all?) of them too if wanted (but I'd guess it's not wanted at this stage of review 😄 ).

src/util/feefrac.cpp

willcl-ark · 2024-03-20T11:33:14Z

src/policy/rbf.cpp

+                                                int64_t replacement_vsize)
+{
+    // Require that the replacement strictly improve the mempool's feerate diagram.
+    std::vector<FeeFrac> old_diagram, new_diagram;


In "Implement ImprovesFeerateDiagram": 2079b80

std::vector<FeeFrac> old_diagram, new_diagram;

These vectors at src/policy/rbf.cpp:L194 appear to be unused and the diagrams are built inside of CalculateFeerateDiagramsForRBF.

leftovers, will remove on touchup/followup

opened in follow-up

instagibbs · 2024-03-25T16:14:28Z

I see you've added coverage for the "not the only parent" case, but I don't see a test for "not the only child" case. Also nothing failed when I commented it out.

@glozow can't figure out github interface, I added a test in followup

sdaftuar

ACK 7295986

Left some nits that can be addressed (or not) in a followup.

sdaftuar · 2024-03-25T19:24:14Z

src/util/feefrac.cpp

+        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);


Just noticed that I think we could change this to short circuit in the case where we've detected that both diagrams are "better somewhere" and hence incomparable, eg:

} while (!(better_somewhere[0] && better_somewhere[1]));

I think slightly better is to pull the check a few lines below into the loop, just after updating the better_somewhere array:

if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;

?

e.g., a9d42b9

sdaftuar · 2024-03-25T19:48:49Z

src/txmempool.cpp

+
+    // 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.


I think this comment is wrong -- it should say something like:

// old diagram will consist of the ancestors and descendants of each element of // all_conflicts. every such transaction will either be at its own feerate (followed // by any descendant at its own feerate), or as a single chunk at the descendant's // ancestor feerate.

taken, indeed my definition missed the ancestors

ee1b9b2 CalculateFeerateDiagramsForRBF: update misleading description of old diagram contents (Greg Sanders) a9d42b9 CompareFeerateDiagram: short-circuit comparison when detected as incomparable (Greg Sanders) cebcced remove erroneous CompareFeerateDiagram comment about slope (Greg Sanders) a0376e1 unit test: clarify unstated assumption for calc_feerate_diagram_rbf chunking (Greg Sanders) 890cb01 s/effected/affected/ (Greg Sanders) d9391ec CalculateFeerateDiagramsForRBF: remove size tie-breaking from chunking conflicts (Greg Sanders) b684d82 fuzz: Add more invariant checks for package_rbf (Greg Sanders) 2a3ada8 fuzz: finer grained ImprovesFeerateDiagram check on error result (Greg Sanders) c377ae9 unit test: improve ImprovesFeerateDiagram coverage with one less vb case (Greg Sanders) d2bf923 unit test: make calc_feerate_diagram_rbf less brittle (Greg Sanders) defe023 fuzz: add PrioritiseTransaction coverage in diagram checks (Greg Sanders) 216d5ff unit test: add coverage showing priority affects diagram check results (Greg Sanders) a80d809 unit test: add CheckConflictTopology case for not the only child (Greg Sanders) 69bd18c unit test: check tx4 conflict error message (Greg Sanders) c0c37f0 unit test: have CompareFeerateDiagram tested with diagrams both ways (Greg Sanders) b62e2c0 ImprovesFeerateDiagram: Spelling fix and removal of unused diagram vectors (Greg Sanders) bb42402 doc: fix comment about non-existing CompareFeeFrac (Greg Sanders) Pull request description: Follow-ups to #29242 ACKs for top commit: glozow: ACK ee1b9b2, reviewed the changes and package_rbf fuzzer seems to run fine murchandamus: crACK ee1b9b2 ismaelsadeeq: Code review ACK ee1b9b2 willcl-ark: ACK ee1b9b2 Tree-SHA512: 8399fe12064fb49b0e4c73258968b57be1d9c2e35701b2d3b0bb67e2e4052e44216358238f92508e4697d0fb6176518d5b885474054d3deda242f669e99262a7

…sed on chunks b22901d Avoid explicitly computing diagram; compare based on chunks (Pieter Wuille) Pull request description: This merges the `BuildDiagramFromChunks` and `CompareFeeRateDiagram` introduced in #29242 into a single `CompareChunks` function, which operates on sorted chunk data rather than diagrams, instead computing the diagram on the fly. This avoids the need for the construction of an intermediary diagram object, and removes the slightly arbitrary "all diagrams must start at (0, 0)" requirement. Not a big deal, but I think the result is a bit cleaner and not really more complicated. ACKs for top commit: glozow: reACK b22901d instagibbs: reACK b22901d Tree-SHA512: ca37bdf61d9a9cb5435f4da73e97ead33bf65828ad9af49b87336b1ece70db8ced1c21f517fc6eb6d616311c91f3da75ecae6b9bd42547133e3a3c5320b7816d

instagibbs mentioned this pull request Jan 12, 2024

Cluster size 2 package rbf #28984

Open

instagibbs force-pushed the 2024-01-diagram-checks branch from 0e89dc2 to aa49f82 Compare January 12, 2024 18:29

DrahtBot added the CI failed label Jan 12, 2024

instagibbs force-pushed the 2024-01-diagram-checks branch 2 times, most recently from 71c7870 to 5da41e6 Compare January 12, 2024 20:25

DrahtBot removed the CI failed label Jan 12, 2024

This was referenced Jan 13, 2024

kernel: Streamline util library #29015

Open

kernel: Remove dependency on CScheduler #28960

Merged

v3 transaction policy for anti-pinning #28948

Merged

refactor: Replace sets of txiter with CTxMemPoolEntryRefs #28886

Closed

ismaelsadeeq reviewed Jan 16, 2024

View reviewed changes

DrahtBot mentioned this pull request Jan 17, 2024

Improve new LogDebug/Trace/Info/Warning/Error Macros #29256

Open

instagibbs force-pushed the 2024-01-diagram-checks branch from 5da41e6 to 5e48ade Compare January 18, 2024 20:11

DrahtBot added the CI failed label Jan 18, 2024

instagibbs force-pushed the 2024-01-diagram-checks branch 3 times, most recently from e757568 to a4b92cf Compare January 19, 2024 16:01

sipa reviewed Jan 19, 2024

View reviewed changes

DrahtBot removed the CI failed label Jan 19, 2024

instagibbs force-pushed the 2024-01-diagram-checks branch 3 times, most recently from d0eaea2 to c914968 Compare January 19, 2024 20:32

DrahtBot added the CI failed label Jan 19, 2024

DrahtBot removed the CI failed label Jan 19, 2024

instagibbs and others added 9 commits March 18, 2024 10:32

Add FeeFrac utils

ce8e225

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com> Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

Add FeeFrac unit tests

66d966d

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com>

fuzz: Add fuzz target for ImprovesFeerateDiagram

588a98d

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com>

test: Add tests for CompareFeerateDiagram and CheckConflictTopology

e9c5aeb

fuzz: fuzz diagram creation and comparison

4d6528a

Co-authored-by: Suhas Daftuar <sdaftuar@chaincode.com> Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

Add fuzz test for FeeFrac

7e89b65

test: unit test for ImprovesFeerateDiagram

b767e6b

Unit tests for CalculateFeerateDiagramsForRBF

7295986

instagibbs force-pushed the 2024-01-diagram-checks branch from dc8195c to 7295986 Compare March 18, 2024 14:35

ismaelsadeeq mentioned this pull request Mar 18, 2024

Wallet: Add max_tx_weight to transaction funding options (take 2) #29523

Open

sipa reviewed Mar 18, 2024

View reviewed changes

DrahtBot requested a review from ismaelsadeeq March 18, 2024 16:34

glozow reviewed Mar 19, 2024

View reviewed changes

murchandamus reviewed Mar 19, 2024

View reviewed changes

ismaelsadeeq reviewed Mar 20, 2024

View reviewed changes

willcl-ark approved these changes Mar 20, 2024

View reviewed changes

achow101 assigned glozow Mar 20, 2024

instagibbs mentioned this pull request Mar 25, 2024

29242 Diagram check followups #29724

Merged

sdaftuar approved these changes Mar 25, 2024

View reviewed changes

glozow merged commit c2dbbc3 into bitcoin:master Mar 26, 2024
16 checks passed

glozow removed their assignment Mar 26, 2024

This was referenced Mar 28, 2024

feefrac: avoid explicitly computing diagram; compare based on chunks #29757

Merged

feefrac: 128-bit multiply support in MSVC #29758

Open

hebasto mentioned this pull request Apr 3, 2024

cmake: Regular rebasing of the cmake-staging branch hebasto/bitcoin#138

Closed

hebasto mentioned this pull request Apr 19, 2024

Apple Clang 14.0 lacks support for std::is_eq #29918

Closed

	// old diagram will consist of each element of direct_conflicts either at
	// old diagram will consist of each element of all_conflicts either at

		const auto tx1 = make_tx(/inputs=/ {m_coinbase_txns[0]}, /output_values=/ {10 * COIN});
		pool.addUnchecked(entry.Fee(low_fee).FromTx(tx1));


		// With one more satoshi it does
		BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size) == std::nullopt);


	// With one less vB it does
	BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size - 1) == std::nullopt);

	// they have a strict topology of 1 or two connected transactions.
	// they have a strict topology of one or two connected transactions.

	// they have a strict topology of 1 or two connected transactions.
	// they have a strict topology of 1 or 2 connected transactions.

	// You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less
	// You can have more than two direct conflicts if the there are multiple affected clusters, all of size 2 or less

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

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

Conversation

instagibbs commented Jan 12, 2024 • edited

DrahtBot commented Jan 12, 2024 • edited

Code Coverage

Reviews

Conflicts

DrahtBot commented Jan 12, 2024

instagibbs commented Jan 12, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

DrahtBot commented Jan 18, 2024

DrahtBot commented Jan 19, 2024

instagibbs commented Jan 19, 2024

sipa left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

glozow left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

instagibbs commented Mar 19, 2024

murchandamus left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ismaelsadeeq left a comment

Choose a reason for hiding this comment

willcl-ark left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

instagibbs commented Mar 25, 2024

sdaftuar left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

instagibbs commented Jan 12, 2024 •

edited

DrahtBot commented Jan 12, 2024 •

edited