RBF move (1/3): extract BIP125 Rule 5 into policy/rbf

glozow commented at 1:30 pm on August 25, 2021: member

See #22675 for motivation, this is one chunk of it. It extracts some BIP125 logic into policy/rbf:

Defines a constant for specifying the maximum number of mempool entries we’d consider replacing by RBF
Calls the available SignalsOptInRBF function instead of manually iterating through inputs
Moves the logic for getting the list of conflicting mempool entries to a helper function
Also does a bit of preparation for future moves - moving declarations around, etc Also see #22677 for addressing the circular dependency.

MOVEONLY: BIP125 max conflicts limit to policy/rbf.h

A circular dependency is added because policy now depends on txmempool and
txmempool depends on validation. It is natural for [mempool] policy to
rely on mempool; the problem is caused by txmempool depending on
validation. #22677 will resolve this.

b001b9f6de

[validation] default conflicting fees and size to 0

This should have no effect in practice, since we only ever call
PreChecks once per transaction.

e0df41d7d5

call SignalsOptInRBF instead of checking all inputs badb9b11a6

[validation] quit RBF logic earlier and separate loops

No behavior change.
While we're looking through the descendants and calculating how many
transactions we might replace, quit early, as soon as we hit 100.
Since we're failing faster, we can also separate the loops - yes, we
loop through more times, but this helps us detangle the different BIP125
rules later.

8d71796335

MOVEONLY: getting mempool conflicts to policy/rbf f293c68be0

glozow added the label Refactoring on Aug 25, 2021

glozow added the label TX fees and policy on Aug 25, 2021

glozow added the label Validation on Aug 25, 2021

jnewbery commented at 1:47 pm on August 25, 2021: member

Code review ACK f293c68be0469894c988711559f5528020c0ff71

glozow renamed this:
~~RBF move (1/n): extract BIP125 Rule 5 into policy/rbf~~
RBF move (1/3): extract BIP125 Rule 5 into policy/rbf
on Aug 25, 2021

in src/policy/rbf.cpp:9 in f293c68be0

2@@ -3,6 +3,10 @@
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <policy/rbf.h>
6+
7+#include <policy/settings.h>
8+#include <tinyformat.h>
9+#include <util/moneystr.h>

theStack commented at 7:45 pm on August 25, 2021:

nit: I think this include is not needed in this compilation unit (neither FormatMoney nor ParseMoney is used anywhere here)

glozow commented at 9:24 am on August 26, 2021:

ah true, I guess not needed until https://github.com/bitcoin/bitcoin/pull/22675/commits/781e100b6047f110f93e965146d5202ed7032e2c

will update if i need to repush

theStack approved

theStack commented at 7:50 pm on August 25, 2021: member

Thanks for splitting up, this way the changes are easier to digest and should also potentially attract more reviewers.

Code-review ACK f293c68be0469894c988711559f5528020c0ff71 📔

DrahtBot commented at 11:49 pm on August 25, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#22698 (Implement RBF inherited signaling and fix getmempoolentry returned bip125-replaceable status by mjdietzx)
#22677 ([RFC] cut the validation <-> txmempool circular dependency by glozow)
#22665 (policy/rbf: don’t return “incorrect” replaceability status by darosior)
#22539 (Re-include RBF replacement txs in fee estimation by darosior)
#22290 (Package Mempool Submission with Package Fee-Bumping by glozow)
#10443 (Add fee_est tool for debugging fee estimation code by ryanofsky)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Herrytheeagle approved

in src/util/rbf.h:22 in f293c68be0

19+* nSequence > MAX_BIP125_RBF_SEQUENCE (SEQUENCE_FINAL-2) on all inputs.
20+*
21+* SEQUENCE_FINAL-1 is picked to still allow use of nLockTime by
22+* non-replaceable transactions. All inputs rather than just one
23+* is for the sake of multi-party protocols, where we don't
24+* want a single party to be able to disable replacement. */

ariard commented at 9:58 pm on August 27, 2021:

nit: “…by opt-in out its contributed input”

glozow commented at 9:10 am on August 31, 2021:

Noted, will add this to a33fdd0b981965982754b39586eedb7ae456ba57!

glozow commented at 9:09 am on September 1, 2021:

Taken in #22855

in src/validation.cpp:479 in f293c68be0

474@@ -474,8 +475,10 @@ class MemPoolAccept
475         bool m_replacement_transaction;
476         CAmount m_base_fees;
477         CAmount m_modified_fees;
478-        CAmount m_conflicting_fees;
479-        size_t m_conflicting_size;
480+        /** Total modified fees of all transactions being replaced. */
481+        CAmount m_conflicting_fees{0};

ariard commented at 10:13 pm on August 27, 2021:

I think what we called “modified fees” in before-this-PR PreChecks() are currently the base_fee of the mempool candidate plus the delta from PrioritiseTransaction (L698 in src/validation.cpp). Maybe the “modified” adjective can be dropped ?

glozow commented at 9:13 am on August 31, 2021:

Correct, modified is base + delta from prioritise. But why should we drop the “modified” adjective? It’s still very widely used in the mempool and MemPoolAccept code. In my view, just saying “fees” is less clear, as I would assume that to mean base fees.

in src/validation.cpp:846 in 8d71796335 outdated

841+            nConflictingFees += it->GetModifiedFee();
842+            nConflictingSize += it->GetTxSize();
843+        }
844 
845+        std::set<uint256> setConflictsParents;
846+        for (const auto& mi : setIterConflicting) {

ariard commented at 11:06 pm on August 27, 2021:

Note, I think this commit is changing a bit the processing, Previously, the 3 operations a) checking candidate feerate is better than any replaced transaction b) fulfilling the set of parents inputs and c) accounting replaced transactions with descendants in the same loop.

After this commit, setIterConflicting is iterated 3 times. Overall I think it’s okay, though it might add a bit of work in case of well-sized set of replaced transactions. From a DoS viewpoint no changes. An upper bound is still enforced with nConflictingCount against MAX_BIP_125_REPLACEMENT_CANDIDATES (that would be great to have a set of QA assets with a wide range of mempool candidates payloads to confirm or infirm that kind of intuitions, not sure that’s an information you can currently get from qa-assets/fuzz_seed_corpus/validation_load_mempool)

glozow commented at 9:18 am on August 31, 2021:

Right, I was hoping to make this clear in the commit messages. Because of the changes in the preceding commit, we now quit immediately when we see more than MAX_BIP_125_REPLACEMENT_CANDIDATES. Previously, we’d grab all potential candidates and only check the total number afterward. So this PR has, overall, reduced the complexity from O(n) to O(1) where n is the number of conflicts, which is why I think it’s okay to iterate 3 times.

The only observable “behavior” change is that we might return too many potential replacements instead of insufficient fee when a transaction violates both.

in src/policy/rbf.h:46 in f293c68be0

41+ * more than MAX_BIP125_REPLACEMENT_CANDIDATES potential entries.
42+ * @param[in]   setIterConflicting  The set of iterators to mempool entries.
43+ * @param[out]  err_string          Used to return errors, if any.
44+ * @param[out]  allConflicting      Populated with all the mempool entries that would be replaced,
45+ *                                  which includes descendants of setIterConflicting. Not cleared at
46+ *                                  the start; any existing mempool entries will remain in the set.

ariard commented at 11:31 pm on August 27, 2021:

What do you mean by “Not cleared at the start; any existing mempool entries will remain in the set” ?

If the replacement is successful, allConflicting are going to be removed in Finalize. For package support, I think this operation we’ll remove the per-package tx allConflicting set all at once. If PreChecks or any new other package policy checks as failed, don’t modify mempool state.

glozow commented at 9:08 am on August 31, 2021:

It’s similar to other mempool functions where you can pass in a setEntries and it will insert entries, but not expect it to be empty beforehand, so you can call it multiple times and end up with an aggregated set. I’m expecting to use this in package RBF. It has nothing to do with what’s going to end up in the mempool; this is just a helper function.

The reason I document it here is I think it’s a relevant detail in the interface. It’s the caller’s responsibility to clear the set beforehand if it needs that.

in src/policy/rbf.cpp:61 in f293c68be0

56+    AssertLockHeld(m_pool.cs);
57+    const uint256 hash = tx.GetHash();
58+    uint64_t nConflictingCount = 0;
59+    for (const auto& mi : setIterConflicting) {
60+        nConflictingCount += mi->GetCountWithDescendants();
61+        // This potentially overestimates the number of actual descendants

ariard commented at 11:41 pm on August 27, 2021:

nit: “as replaced parents might have intersecting descendants”

glozow commented at 9:10 am on August 31, 2021:

I elaborate on this comment in a33fdd0b981965982754b39586eedb7ae456ba57 - these commits are MOVEONLY

ariard commented at 11:44 pm on August 27, 2021: member

ACK f293c68b

I verified that test_too_many_replacements in test/functional/feature_rbf.py still cover correctly the refactored bip 125 rule 5 check.

I think any comments if worthy can be addressed in a follow-up or be taken on another PR of this serie of works.

fanquake commented at 2:34 pm on August 31, 2021: member

Please comment here when you’re addressing followup comments / nits via the next PRs in the series.

fanquake merged this on Aug 31, 2021

fanquake closed this on Aug 31, 2021

sidhujag referenced this in commit 74f46397e2 on Aug 31, 2021

in src/validation.cpp:843 in 8d71796335 outdated

838+        // Check if it's economically rational to mine this transaction rather
839+        // than the ones it replaces.
840+        for (CTxMemPool::txiter it : allConflicting) {
841+            nConflictingFees += it->GetModifiedFee();
842+            nConflictingSize += it->GetTxSize();
843+        }

darosior commented at 7:13 am on September 1, 2021:

In the same spirit of exiting early, i think we could check if (nModifiedFees < nConflictingFees) here directly. We could probably also check the delta fee.

glozow commented at 9:17 am on September 1, 2021:

I’m not sure if that would be much of an improvement? There would be <=100 entries to aggregate fees for, so this is pretty tightly bounded already.

darosior commented at 7:28 am on September 1, 2021: member

Post-merge ACK f293c68be0469894c988711559f5528020c0ff71

glozow deleted the branch on Sep 1, 2021

glozow commented at 9:11 am on September 1, 2021: member

Next PR is #22675! Addressing documentation-related comments in #22855

in src/validation.cpp:821 in f293c68be0

814@@ -835,33 +815,26 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
815                             newFeeRate.ToString(),
816                             oldFeeRate.ToString()));
817             }
818+        }
819+
820+        // Calculate all conflicting entries and enforce Rule #5.
821+        if (!GetEntriesForConflicts(tx, m_pool, setIterConflicting, allConflicting, err_string)) {

MarcoFalke commented at 10:11 am on September 2, 2021:

f293c68be0469894c988711559f5528020c0ff71: I think for new code we should avoid leaking mutable return args into a greater scope than needed. Especially when the goal is to re-use (https://github.com/bitcoin/bitcoin/pull/22675/files) the symbol (err_string), when it shouldn’t be re-used. With C++17 this is trivial to fix.

One example:

0         if (const auto err_string{GetEntriesForConflicts(tx, m_pool, setIterConflicting, allConflicting)}) {
1            return ..., *err_string;

and make the util function return an error string or nullopt if no error is hit.

Re-using symbols has bitten us in ATMP in the past, so I don’t think there is need to repeat that. See commit 116419e58dddef8fe3ff9806a1d8ceebe64ae3e6

glozow commented at 3:40 pm on September 2, 2021:

Good point, I’ve added a followup commit for GetEntriesForConflicts and edited the rest of the functions to return a std::optional<std::string> in #22675

MarcoFalke commented at 10:11 am on September 2, 2021: member

cr ACK f293c68

but I don’t like the symbol re-use

DrahtBot locked this on Sep 2, 2022

RBF move (1/3): extract BIP125 Rule 5 into policy/rbf #22796

Conflicts