Skip to content

Conversation

glozow
Copy link
Member

@glozow glozow commented Aug 10, 2021

This PR does not change behavior. It extracts the BIP125 logic into helper functions (and puts them in the policy/rbf* files). This enables three things - I think each one individually is pretty good:

  • Implementation of package RBF (see Package Mempool Submission with Package Fee-Bumping #22290). I want it to be as close to BIP125 as possible so that it doesn't become a distinct fee-bumping mechanism. Doing these move-only commits first means the diff is mostly mechanical to review, and I just need to create a function that mirrors the single transaction validation.
  • We will be able to isolate and test our RBF logic alone. Recently, there have been some discussions on discrepancies between our code and BIP125, as well as proposals for improving it. Generally, I think making this code more modular and de-bloating validation.cpp is probably a good idea.
  • Witness Replacement (replacing same-txid-different-wtxid when the witness is significantly smaller and therefore higher feerate) in a BIP125-similar way. Hopefully it can just be implemented with calls to the rbf functions (i.e. PaysForRBF) and an edit to the relevant mempool entries.

@0xB10C
Copy link
Contributor

0xB10C commented Aug 10, 2021

Concept ACK

TIL Witness Replacement

@glozow
Copy link
Member Author

glozow commented Aug 10, 2021

A new circular dependency policy/rbf -> txmempool -> validation -> policy/rbf is introduced here, so I've added it to EXPECTED_CIRCULAR_DEPENDENCIES to suppress the issue. I understand this is not ideal. The main problem, I think, is the txmempool -> validation part (which already exists), so I've taken a crack at it in #22677.

@DrahtBot
Copy link
Contributor

DrahtBot commented Aug 10, 2021

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

  • #22539 (Re-include RBF replacement txs in fee estimation by darosior)

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.

@fanquake
Copy link
Member

Concept ACK

Copy link
Contributor

@mjdietzx mjdietzx left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK. Very well done, I think this is a nice improvement

@@ -47,6 +47,29 @@ RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx)
return SignalsOptInRBF(tx) ? RBFTransactionState::REPLACEABLE_BIP125 : RBFTransactionState::UNKNOWN;
}

bool IsRBFOptOut(const CTransaction& txConflicting)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is this necessary? Can't we just use !SignalsOptInRBF from util/rbf.h?

Note: I realize this is a move only PR, but I'm just wondering, maybe it's a minor refactor later

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: I'm sure if util/rbf.h existence is justified in the first place, but if we go with the current convention, IsRBFOptOut would seem to belong there

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hm, I think everything in util/rbf should be moved to policy/rbf actually 🤔 There's no reason to have two places for RBF (I think) and organization-wise, all RBF logic and code is policy.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not sure, it would make all users of policy/rbf depend on txmempool. Eg not sure the standalone binaries wallet-util and friends depend on it although they use util/rbf.

Copy link
Member Author

@glozow glozow Aug 11, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ahh good point @darosior. I was wrong. I think it makes sense for policy/* to depend on mempool, but I see how util/rbf is needed now.

@mjdietzx
Copy link
Contributor

crACK 6a0a8ef

@theStack
Copy link
Contributor

Concept ACK

@mjdietzx
Copy link
Contributor

Tested ACK 6a0a8ef

Copy link
Contributor

@theStack theStack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Reviewed up to 474258f (5/9 commits) so far, LGTM, nice cleanups. To be extra-cautious, I also compiled and ran unit tests + the functional test feature_rbf.py on every commit.

Left two minor nits. Planning to review the remaining 4 commits tomorrow.

Copy link
Contributor

@theStack theStack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Left some more suggestions considering const-correctness and passing by reference rather than by value. On the second-to-last commit a30b027 the test feature_rbf.py currently fails, see comment below. In the last commit this is fixed, as the deleted strprintf() argument line is re-introduced in the helper function.

@glozow
Copy link
Member Author

glozow commented Aug 16, 2021

To be extra-cautious, I also compiled and ran unit tests + the functional test feature_rbf.py on every commit.
Left some more suggestions considering const-correctness and passing by reference rather than by value. On the second-to-last commit a30b027 the test feature_rbf.py currently fails, see comment below. In the last commit this is fixed, as the deleted strprintf() argument line is re-introduced in the helper function.

Thanks @theStack and good catch! Fixed. Good idea for reviewers to run git rebase --exec "make check; test/functional/feature_rbf.py" -i HEAD~11 in general

Also added a small scripted diff style cleanup, should be simple to review

Copy link
Contributor

@theStack theStack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Code-review ACK 192193c

Verified via git range-diff 6a0a8ef7...192193c7 that since my last review (#22675 (review) and #22675 (review)) all suggestions have been tackled and that the newly added commits 7d6571f (renames) and 192193c (style cleanups) are okay. Kudos for the new variable names, I think the code is much more comprehensible now 👌

Good idea for reviewers to run git rebase --exec "make check; test/functional/feature_rbf.py" -i HEAD~11 in general

Oh nice, I didn't know about git rebase --exec before (I always did review/compile/run test manually hopping from commit to commit), that is a huge time-saver! 🚀

Copy link

@ariard ariard left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK, I like the direction to drain PreChecks in isolated logical components and adding clearer documentation in the process.

I think the changes proposed by this PR are sizeable enough to be splitted off in different PRs. Especially about the replace-by-fee check rules, beyond the better-feerate-than-directly-replaced transaction present in the code but not in the spec, iirc they're still minor discrepancies worthy to be documented.

One PRs-split-offs could be :

  • IsRBFOptOut() : the replacement signaling, introducing src/policy/rbf.h
  • SpendsAndConflictsDisjoint : the replacement candidate sanitization
  • PaysMoreThanConflicts/... : the replacement check rules

Copy link
Member

@darosior darosior left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK nice cleanup.

I was not sure about the approach at first, since we don't currently need txmempool in policy/rbf for IsRBFOptIn (#22665 removes it). But i agree it's cleaner to rather have txmempool not depend on validation as you do in your followup.
That said, why not proceed the other way around to avoid introducing the circular dependency at all?

@glozow
Copy link
Member Author

glozow commented Aug 20, 2021

That said, why not proceed the other way around to avoid introducing the circular dependency at all?

True, I just did it this way because this PR is a bit further along (other one is still looking for approach feedback), and I have some branches depending on this refactor.

Copy link
Contributor

@jnewbery jnewbery left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good!

The logs for some of the commits could use a little more detail, e.g. e535422 [validation] quit earlier and separate loops could have a better summary (Quit what earlier? Separate which loops? At the very least this should mention ATMP or RBF). The same is true for some of the other commit logs as well.

@jnewbery
Copy link
Contributor

Code review ACK a33fdd0

I'm very happy to review any new PRs if you split this up.

@glozow
Copy link
Member Author

glozow commented Aug 25, 2021

I've split off the first few commits into #22796.

fanquake added a commit that referenced this pull request Aug 31, 2021
f293c68 MOVEONLY: getting mempool conflicts to policy/rbf (glozow)
8d71796 [validation] quit RBF logic earlier and separate loops (glozow)
badb9b1 call SignalsOptInRBF instead of checking all inputs (glozow)
e0df41d [validation] default conflicting fees and size to 0 (glozow)
b001b9f MOVEONLY: BIP125 max conflicts limit to policy/rbf.h (glozow)

Pull request description:

  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.

ACKs for top commit:
  jnewbery:
    Code review ACK f293c68
  theStack:
    Code-review ACK f293c68 📔
  ariard:
    ACK f293c68

Tree-SHA512: a60370994569cfc91d4b2ad5e94542d4855a48927ae8b174880216074e4fa50d4523dd4ee36efdd6edf2bf7adb87a8beff9c3aaaf6dd323b286b287233e63790
@glozow glozow force-pushed the 2021-08-rbf branch 2 times, most recently from 02eecc8 to a15baa5 Compare September 1, 2021 08:45
@glozow glozow changed the title MOVEONLY policy: extract RBF logic into policy/rbf RBF move 2/3: extract RBF logic into policy/rbf Sep 1, 2021
@glozow
Copy link
Member Author

glozow commented Sep 1, 2021

Rebased and split off the documentation changes. Ready for review.
Please note that this is move-only, and I'm happy to add any doc suggestions to #22855.

This checks that a transaction isn't trying to replace something it
supposedly depends on.
"Fee Delta" is already a term used for prioritizing transactions:
modified = base fees + delta

Here, delta also means the difference between original and modified replacement fees:
nDeltaFees = (original_base + original_delta) - (replacement_base + replacement_delta)

This is insanely confusing. Also, since mempool is no longer a member of a
class (MemPoolAccept.m_pool), the "m" prefix is unnecessary. The rest are
clarity/style-focused changes to already-touched lines.

-BEGIN VERIFY SCRIPT-

ren() { sed -i "s/\<$1\>/$2/g" src/policy/rbf* ; }

ren nDeltaFees additional_fees
ren m_pool pool

ren nSize replacement_vsize
ren nModifiedFees replacement_fees
ren nConflictingFees original_fees
ren oldFeeRate original_feerate
ren newFeeRate replacement_feerate

ren setAncestors ancestors
ren setIterConflicting iters_conflicting
ren setConflictsParents parents_of_conflicts
ren setConflicts direct_conflicts
ren allConflicting all_conflicts

sed -i "s/ hash\b/ txid/g" src/policy/rbf*
-END VERIFY SCRIPT-
@glozow
Copy link
Member Author

glozow commented Sep 2, 2021

Changed the functions to return std::optional<std::string> instead of bool in response to #22796 (comment)

@mjdietzx
Copy link
Contributor

mjdietzx commented Sep 3, 2021

ACK 32748da

I tested this again by running some additional test coverage around BIP125 (this PR #22867) on this branch. All good ✅

Copy link
Contributor

@theStack theStack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Code-review ACK 32748da 📐

Built and ran unit tests and functional test ./test/functional/feature_rbf.py at each commit, verified by review that there is no change in behaviour. Here are some naming/documentation improvement nits:

  • to increase clarity, you could explicitely refer to BIP125 when mentioning rules in the comments in MemPoolAccept::PreChecks(), e.g. s/Enforce Rule #2/Enforce BIP125 Rule #2/
  • though I totally understand the motivation behind the new interface, returning std::optional<std::string> seems a bit confusing for functions that previously returned bool. The function name is like a predicate, and the predicate (e.g. PaysForRBF) is now unexpectedly true if nothing (std::nullopt) is returned, leading to an inverted logic for the reader of the if-clause where it is called. Maybe prefix the function names with something like Verify or Check?

Copy link
Member

@maflcko maflcko left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

review ACK 32748da 🦇

Show signature and timestamp

Signature:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

review ACK 32748da0f47f7aa9fba78dfb29aa426b14f15624 🦇
-----BEGIN PGP SIGNATURE-----

iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
pUjoaQwAggcrCYBYlCDfIy4FYpWzVg9dKVuvdwpkRXNo146y0z4w2cNoJa+08akW
UfBbdsu2YlwbPKlgODU6LARsjq5PE8nj+vkj1S3Z9MnvhoXh/UwLlRci2bDDshn1
YyiTdtiFfN1UYFQ4ShhunipzGK6ZNALWZUDFXCIWbtVQUYS0shmWls/Dchah94lf
2hmK9vGXLbtpAuR/9zxYguUL9ixcsBtALCI3GG2DspZIHON3aJBZDP59HJXXINo+
aQoFNw77QfQKa+GMKLvCW8/5eQDVue5xAJyckB+EyJjXE2ztcskn2riA+VP+I0Zu
PfVcqgkfyy5Ci/8BUjvtWAIYGa+WUeJjbtd/DVw80E9CpqILj3TPvrpTeA2q3bHC
PAJQMrmZbEGQgMir9Zj/c9Bh54+9MnEhKwo5JqktBI110ohJsIkFwuT75hXrKRjn
53jrMg7LR9kzA2Hmg625hgxJTNthv1QMZrerkhRjA1ad/s1bE/hGnN2Lk5yYy/8k
FATeV8qZ
=rsJ0
-----END PGP SIGNATURE-----

Timestamp of file with hash 23997a2a7eb742c9c9782006676c24ca77f830db8c1bb6251e751a60a1f59bc5 -

The scripted diff might also modify out-of-tree files. You can fix that by passing the glob through git grep -l:

sed ... $(git grep -l "$1" ./src/policy/rbf*)

Also in the last commit, if you fixup the file so much, might as well go the extra step and fixup the whole file's whitespace:

diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp
index 15527afb8a..d524b95b89 100644
--- a/src/policy/rbf.cpp
+++ b/src/policy/rbf.cpp
@@ -48,9 +48,9 @@ RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx)
 }
 
 std::optional<std::string> GetEntriesForConflicts(const CTransaction& tx,
-                            CTxMemPool& pool,
-                            const CTxMemPool::setEntries& iters_conflicting,
-                            CTxMemPool::setEntries& all_conflicts)
+                                                  CTxMemPool& pool,
+                                                  const CTxMemPool::setEntries& iters_conflicting,
+                                                  CTxMemPool::setEntries& all_conflicts)
 {
     AssertLockHeld(pool.cs);
     const uint256 txid = tx.GetHash();
@@ -81,7 +81,7 @@ std::optional<std::string> HasNoNewUnconfirmed(const CTransaction& tx,
     AssertLockHeld(pool.cs);
     std::set<uint256> parents_of_conflicts;
     for (const auto& mi : iters_conflicting) {
-        for (const CTxIn &txin : mi->GetTx().vin) {
+        for (const CTxIn& txin : mi->GetTx().vin) {
             parents_of_conflicts.insert(txin.prevout.hash);
         }
     }
@@ -111,7 +111,7 @@ std::optional<std::string> EntriesAndTxidsDisjoint(const CTxMemPool::setEntries&
                                                    const uint256& txid)
 {
     for (CTxMemPool::txiter ancestorIt : ancestors) {
-        const uint256 &hashAncestor = ancestorIt->GetTx().GetHash();
+        const uint256& hashAncestor = ancestorIt->GetTx().GetHash();
         if (direct_conflicts.count(hashAncestor)) {
             return strprintf("%s spends conflicting transaction %s",
                              txid.ToString(),
diff --git a/src/policy/rbf.h b/src/policy/rbf.h
index 56468a09b2..3f37bb09bf 100644
--- a/src/policy/rbf.h
+++ b/src/policy/rbf.h
@@ -48,14 +48,14 @@ RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx);
 std::optional<std::string> GetEntriesForConflicts(const CTransaction& tx, CTxMemPool& pool,
                                                   const CTxMemPool::setEntries& iters_conflicting,
                                                   CTxMemPool::setEntries& all_conflicts)
-                                                  EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
+    EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
 
 /** BIP125 Rule #2: "The replacement transaction may only include an unconfirmed input if that input
  * was included in one of the original transactions."
  * @returns error message if Rule #2 is broken, otherwise std::nullopt. */
 std::optional<std::string> HasNoNewUnconfirmed(const CTransaction& tx, const CTxMemPool& pool,
                                                const CTxMemPool::setEntries& iters_conflicting)
-                                               EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
+    EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
 
 /** Check the intersection between two sets of transactions (a set of mempool entries and a set of
  * txids) to make sure they are disjoint.
diff --git a/src/util/rbf.h b/src/util/rbf.h
index 6d44a2cb83..db9549e3ed 100644
--- a/src/util/rbf.h
+++ b/src/util/rbf.h
@@ -18,6 +18,6 @@ static const uint32_t MAX_BIP125_RBF_SEQUENCE = 0xfffffffd;
 * SEQUENCE_FINAL-1 is picked to still allow use of nLockTime by non-replaceable transactions. All
 * inputs rather than just one is for the sake of multi-party protocols, where we don't want a single
 * party to be able to disable replacement. */
-bool SignalsOptInRBF(const CTransaction &tx);
+bool SignalsOptInRBF(const CTransaction& tx);
 
 #endif // BITCOIN_UTIL_RBF_H

@fanquake fanquake merged commit b8336b2 into bitcoin:master Sep 10, 2021
@glozow glozow deleted the 2021-08-rbf branch September 10, 2021 09:25
Copy link

@ariard ariard left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Post-merge Code Review ACK 32748da

/** Enforce BIP125 Rule #3 "The replacement transaction pays an absolute fee of at least the sum
* paid by the original transactions." Enforce BIP125 Rule #4 "The replacement transaction must also
* pay for its own bandwidth at or above the rate set by the node's minimum relay fee setting."
* @param[in] original_fees Total modified fees of original transaction(s).
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note, as previously mentioned, I think this is where we do have additional divergences w.r.t to bip125.

Rule 3 says "The replacement transaction pays an absolute fee of at least the sum paid by the original transactions".

I think original transactions as to be interpreted as the set of directly conflicted transactions, i.e sharing inputs with the replacement transaction. At least Rule 5 explicitly dissociates "original transactions to be replaced and their descendant transactions".

However our RBF implementation computes the original_fees from iterating on allConflicting which is built from CalculateDescendants. So to-be-replaced descendants fees are also added to the sum paid checked.

This means our implementation is more conservative than BIP125, as the replacement threshold is higher. I think this is preferable, at least without deeper thinking.

AFAIK, this is mental model shared by most developers when they reason about our RBF logic (e.g in pinning discussions). Though it might create surprises if a user submits replacement transactions to Core and other full-node like bcoin, btcd (I don't know their behaviors), they might be refused by Core but accepted in other implems.

If I'm correct, good to make this point more known.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You are correct with regard to the implementation. However BIP125 says:

The replacement transaction pays an absolute fee of at least the sum paid by the original transactions

Which is plural, so i think the implementation is in line with this rule.
Of course, i agree that it would be a nice place to look for bugs in re-implementations :)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

At least wrt fees, it wouldn't make much sense to not consider the descendants of direct conflicts. You can very easily end up replacing higher-fee packages with lower-fee ones. As such, I don't expect that other implementations are interpreting the BIP wording as excluding descendants. Good shout, though, since that would be a pretty juicy bug! 🐛

wrt wording used in these comments, I have been trying to use "direct conflicts" as the mempool transactions that a transaction conflicts with, and "original transactions" as all of the mempool transactions that would need to be evicted, i.e. direct conflicts and their descendants. I hope that's clear enough - welcome any feedback on that

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Which is plural, so i think the implementation is in line with this rule.

Yes "original transactions" is plural though Rule 5 explicitly dissociates "original transactions to be replaced and their descendant transactions". Like the directly-replaced transactions and their descendants as two different things :) ?

I still think this is confusing and our implementation is not in line with this rule. Though I think this is the best behavior for the reason underscored by Gloria.

I'll let someone else checking other full-node implementations if they have bugs around that!

// Ideally we'd keep track of the ancestor feerates and make the decision based on that, but
// for now requiring all new inputs to be confirmed works.
//
// Note that if you relax this to make RBF a little more useful, this may break the
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In case of code relocation like this one, I think it could ease understanding if a reference to PreChecks is added, where the calls to CalculateMempoolAncestors happen.

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Sep 11, 2021
Copy link
Member

@darosior darosior left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

late-to-the-party ACK 32748da

/** Enforce BIP125 Rule #3 "The replacement transaction pays an absolute fee of at least the sum
* paid by the original transactions." Enforce BIP125 Rule #4 "The replacement transaction must also
* pay for its own bandwidth at or above the rate set by the node's minimum relay fee setting."
* @param[in] original_fees Total modified fees of original transaction(s).
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You are correct with regard to the implementation. However BIP125 says:

The replacement transaction pays an absolute fee of at least the sum paid by the original transactions

Which is plural, so i think the implementation is in line with this rule.
Of course, i agree that it would be a nice place to look for bugs in re-implementations :)

fanquake added a commit that referenced this pull request Sep 23, 2021
0ef08f8 add missing includes in policy/rbf (glozow)
c6abeb7 make MAX_BIP125_RBF_SEQUENCE constexpr (glozow)
3cf46f6 [doc] improve RBF documentation (glozow)
c78eb86 [policy/refactor] pass in relay fee instead of using global (glozow)

Pull request description:

  Followups to #22675 and documentation-only changes intended to clarify the code/logic concerning mempool Replace-by-Fee.

ACKs for top commit:
  jnewbery:
    utACK 0ef08f8
  fanquake:
    ACK 0ef08f8

Tree-SHA512: 6797ae758beca0c9673cb00ce85da48e9a4ac5cb5100074ca93e004cdb31d24d91a1a7721b57fc2f619addfeb4950d8caf45fee0f5b7528defbbd121eb4d271f
@bitcoin bitcoin locked and limited conversation to collaborators Oct 30, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
Development

Successfully merging this pull request may close these issues.