Skip to content

Conversation

@glozow
Copy link
Member

@glozow glozow commented Jan 20, 2023

Part of package relay, see #27463.

Note that this still allows packages to bump transactions that are below the dynamic mempool minimum feerate, which means this still solves the "mempool is congested and my presigned 1sat/vB tx is screwed" problem for all transactions.

On master, the package policy (only accessible through regtest-only RPC submitpackage) allows 0-fee (or otherwise below min relay feerate) transactions if they are bumped by a child. However, with default package limits, we don't yet have a DoS-resistant way of ensuring these transactions remain bumped throughout their time in the mempool. Primarily, the fee-bumping child may later be replaced by another transaction that doesn't bump the parent(s). The parent(s) could potentially stay bumped by other transactions, but not enough to ever be selected by the BlockAssembler (due to blockmintxfee).

For example, (tested here):

  • The mempool accepts 24 below-minrelayfeerate transactions ("0-fee parents"), all bumped by a single high-fee transaction ("the fee-bumping child"). The fee-bumping child also spends a confirmed UTXO.
  • Two additional children are added to each 0-fee parent. These children each pay a feerate slightly above the minimum relay feerate (e.g. 1.9sat/vB) such that, for each 0-fee parent, the total fees of its two children divided by the total size of the children and parent is above the minimum relay feerate.
  • If a block template is built now, all transactions would be selected.
  • A transaction replaces the the fee-bumping child, spending only the confirmed UTXO and not any of the outputs from the 0-fee parents.
  • The 0-fee parents now each have 2 children. Their descendant feerates are above minrelayfeerate, which means that they remain in the mempool, even if the mempool evicts all below-minrelayfeerate packages.
  • If a block template is built now, none of the 0-fee parents or their children would be selected.
  • Even more low-feerate descendants can be added to these below-minrelayfeerate packages and they will not be evicted until they expire or the mempool reaches capacity.

Unless we have a DoS-resistant way of ensuring package CPFP-bumped transactions are always bumped, allowing package CPFP to bump below-minrelayfeerate transactions can result in these problematic situations. See #27018 which proposes a partial solution with some limitations, and contains discussion about potential improvements to eviction strategy. While no adequate solution exists, for now, avoid these situations by requiring all transactions to meet min relay feerate.

@glozow glozow added the Mempool label Jan 20, 2023
@DrahtBot
Copy link
Contributor

DrahtBot commented Jan 20, 2023

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

Reviews

See the guideline for information on the review process.

Type Reviewers
ACK instagibbs, ajtowns
Concept ACK naumenkogs, sdaftuar

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

  • #26812 (test: add end-to-end tests for CConnman and PeerManager by vasild)

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.

@glozow
Copy link
Member Author

glozow commented Jan 20, 2023

CC @sdaftuar @ajtowns @instagibbs

@ajtowns
Copy link
Contributor

ajtowns commented Jan 23, 2023

  • We can remove these transactions in TrimToSize(), but 2500 is not within our acceptable limits.

I'm not sure I see why this is a problem? Can't we have the situation where 1000s of txs get evicted anyway, simply by accepting a high fee rate 400kb tx that then causes a large number of small min feerate txs (with no unconfirmed ancestors/descendants) to be evicted due to hitting the mempool limit? (At least evicting ~350 otherwise unrelated txs that way seems possible -- simple 1-in 1-out txs seem to contribute ~1150 bytes to mempool usage each for me, so 350 of them should use about 402kB)

(what if the 0-fee ancestor is bumped by something else?)

We essentially have to do the work to see if the ancestors are bumped by something else anyway, whether they're 0-fee or not (when we evict the conflicted descendant; its ancestors' descendant fee rates get updated). When we get to TrimToSize, we just look at the already calculated descendant score, and evict the low ones. But the logic there doesn't change if the lowest fee rate is 0 or 1 sat/vb?

06:30 < sdaftuar> i think my concern is that the mempool shouldn't have things in it that would never get mined, eg because they're below minrelay fee (which we compare against in the mining code iirc)

Wouldn't it make more sense to address that directly, ie by having TrimToSize trim txs whose descendant score is below min relay fee, even if the mempool isn't full? Then txs who lose their CPFP child will get trimmed essentially immediately, no matter how they got in, and no matter why the parent might have been removed?

I don't mind the concept here (which I summarise as "only allow txs below min relay fee via some scheme that deliberately limits the complexity"), but it seems more like a "here's another special case" instead of "here's a simple rule that's easy for everyone to think about".

@glozow
Copy link
Member Author

glozow commented Jan 23, 2023

Slightly out of order:

Wouldn't it make more sense to address that directly, ie by having TrimToSize trim txs whose descendant score is below min relay fee, even if the mempool isn't full?

btw I have this as the next commit (898847e or "[mempool] evict everything below min relay fee in TrimToSize()" commit in #25038). My concern was whether it would be problematic to have many such transactions to trim, hence these changes beforehand. If we instead decide that we're ok with this, I'm happy to drop these.

Somewhat relevant, I'd also wonder if we should add a TrimToSize() at the end of reorgs. Same reason, so we don't add below-minrelayfee from disconnected blocks. And same concern, that it could make the process slower.

I'm not sure I see why this is a problem? Can't we have the situation where 1000s of txs get evicted anyway, simply by accepting a high fee rate 400kb tx that then causes a large number of small min feerate txs (with no unconfirmed ancestors/descendants) to be evicted due to hitting the mempool limit?

Yes, it is definitely not otherwise impossible to be evicting 1000s of transactions in TrimToSize(). But since package cpfp would be a new way of permitting such transactions, I'd rather lean towards being conservative?

@sdaftuar
Copy link
Member

sdaftuar commented Jan 23, 2023

Wouldn't it make more sense to address that directly, ie by having TrimToSize trim txs whose descendant score is below min relay fee, even if the mempool isn't full?

This is insufficient for preventing transactions that will never be mined from staying in the mempool, because TrimToSize would leave transactions in the mempool if a parent and multiple children appear to have enough fee for the combined package size, even though no single child has an ancestor fee rate above the min relay fee (eg a "children-pay-for-parent" scenario).

So I think while having a call to TrimToSize shouldn't hurt (and would be needed in the case of v3), we seem to need an approach like this PR to avoid the problem generally.

@sdaftuar
Copy link
Member

Concept ACK.

@ajtowns
Copy link
Contributor

ajtowns commented Jan 23, 2023

@glozow

My concern was whether it would be problematic to have many such transactions to trim, hence these changes beforehand. If we instead decide that we're ok with this, I'm happy to drop these.

I'm not sure that we shouldn't be concerned about using up too much CPU in such cases; just that if we are, there are other analogous cases we should be concerned about too...

@sdaftuar

This is insufficient for preventing transactions that will never be mined from staying in the mempool, because 'TrimToSize' would leave transactions in the mempool if a parent and multiple children appear to have enough fee for the combined package size, even though no single child has an ancestor fee rate above the min relay fee (eg a "children-pay-for-parents scenario).

Right, but that's a reflection of us using ancestor score for mining, but descendant score for mempool removal... So presumably we'd get similar behaviour even if min relay fee is 0 -- ie, if we have a parent/children relationship like that where the parent has a high descendant score but the children have low ancestor scores, then they'll remain in the mempool while we evict txs with a fee rate in between those values due to the mempool being full, even if it turns out those txs would be mined while the child txs would not. (Though the key value there is what people are using for -blockmintxfee not the min relay fee per se...)

Replacing descendant score is a big, possibly impossible, project though, so Concept ACK on working around it in this way in the meantime. I think it would be better to be much clearer on exactly what this is achieving though.

@naumenkogs
Copy link
Contributor

Concept ACK

@glozow
Copy link
Member Author

glozow commented Jan 30, 2023

Replacing descendant score is a big, possibly impossible, project though, so Concept ACK on working around it in this way in the meantime. I think it would be better to be much clearer on exactly what this is achieving though.

Agreed. I've rewritten the description to focus on the fact that we can end up with descendant packages of transactions that would never be mined but still get to hang out in the mempool. I've also written a test to demonstrate this here, on top of the "evict everything below min relay feerate in TrimToSize()" commit (to show it doesn't fix this issue), and added a description of this test to the OP so it would be in the commit log. I could adapt the test for this PR, but most of it would not be executed when the changes are in place, so I'm not sure how meaningful it would be.

Copy link
Member

@sdaftuar sdaftuar 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. Only lightly reviewed the test changes. Left some non-blocking nits.

@glozow glozow force-pushed the 2023-01-package-mempoolmin-only branch 2 times, most recently from b5bfd50 to fce52c8 Compare February 1, 2023 10:35
@glozow glozow force-pushed the 2023-01-package-mempoolmin-only branch from fce52c8 to f636daf Compare February 1, 2023 13:24
@sdaftuar
Copy link
Member

sdaftuar commented Feb 1, 2023

Gave this more thought... I think I have a better solution to this problem:

Fundamentally the issue with txs below the minrelayfee in the mempool is a problem because (a) the mining code refuses to select ancestor packages below the blockmintxfee, and (b) TrimToSize() necessarily operates on descendant packages and cannot detect when this is the case.

There seems to be basically no good reason anymore for the mining code to not mine whatever makes it in to the mempool. Philosophically, we ought to ensure that whatever gets into the mempool meets the miner's feerate criteria, and then just mine whatever is there. Doing otherwise opens up possibilities for DoS, if it's possible to fill the mempool with transactions that would never be selected.

So instead I think an easier solution to this problem is to (a) drop the blockmintxfee feerate check in the mining code, and (b) modify TrimToSize() to evict descendant packages below the minrelayfee, which should be called whenever there is a reorg or whenever a transaction is added to the mempool (which could be an RBF that leaves a dangling 0-fee transaction lying around). The result of these two changes is that we might pick up a transaction or package in block creation that appears to be below the minrelayfee, but whenever we do so it should open up the door to being able to include transactions that bring the cumulative feerate up to above the minrelayfee, because we're ensuring that every transaction has a total descendant package that is sufficiently high feerate to be mined. I think this should be ok?

Anyway, one reason I like this alternate approach better is that this PR leaves open a possibility of 0-fee transactions being added to the mempool as a result of a reorg, and I was able to sketch out a possible DoS that takes advantage of seeding the mempool with 0-fee transactions and then using those to fill the mempool up with transactions that would both never be mined and be expensive to evict (via TrimToSize()), which basically would cause the relay fees for everyone on the network to be much higher than they should be. I'm not sure this is a very practical attack, but given that it would still exist I think an alternate approach that covers this case (with no downsides I can see) seems better...

@sdaftuar
Copy link
Member

sdaftuar commented Feb 1, 2023

Also, I think it would make sense to drop the blockmintxfee parameter altogether. I think that variable is a holdover from the days when we supported priority transactions, but today it makes no sense to have transactions in your mempool you would never mine (eg if blockmintxfee > minrelayfee), and if you set blockmintxfee to be below minrelayfee, then it mostly has no effect, because how would such low fee transactions make it into your mempool in the first place?

@instagibbs
Copy link
Member

@sdaftuar sorry can you spell out what exactly the proposal is by walking through the "24 below-minrelayfeerate transactions" case, and why that's not a problem?

@sdaftuar
Copy link
Member

sdaftuar commented Feb 1, 2023

@sdaftuar sorry can you spell out what exactly the proposal is by walking through the "24 below-minrelayfeerate transactions" case, and why that's not a problem?

Sure, the proposal is twofold: (1) get rid of any feerate checks in the mining code (ie remove the comparison to blockmintxfee in addPackageTransactions), and (2) modify TrimToSize() so that we evict any descendant package from the mempool if the package is below the minrelayfee. (Technically we need to also invoke this function on the mempool after a reorg, so maybe that's 3 things, but conceptually it's the same idea -- whenever we might have changed the mempool in a way that could have added a 0-fee transaction, run TrimToSize() to evict it so that we limit junk from being relayed on the network.)

I believe the scenario you're asking about is one where we have a zero-fee parent in the mempool, with a bunch of children that are all above the minrelayfee themselves, but each one, when taken with the parent will have an ancestor feerate below the minrelayfee. Originally I put this scenario out there as a DoS vector, because the mining code currently will not select any such transactions. However if we change the mining code to skip the relay fee check, then this whole package will eventually get included in a block instead, which means that there is no free relay (because all those fee-paying transactions will be mined). Moreover, if the descendant package in total has a feerate greater than the minrelayfee, then I think apart from edge cases around which transactions make it in at the end of a block, this is basically achieving the miner's goals anyway of including transactions that in total have a high enough feerate.

If we didn't include the TrimToSize() modification to evict descendant packages below the minrelayfee, then there could be an issue where 0-fee transactions might get included in a block, which ought to be strictly worse for a miner than omitting such transactions (because they take longer to validate than a block without the transaction, and there's no additional benefit to the miner for including them) -- hence that is an important part of the change as well.

@naumenkogs
Copy link
Contributor

I reviewed the code f636daf4c89da7b2b72d05e73de1ca86449a36a6 and it seems correct.
However, I think the other approach #27018 makes more sense. Not just because of the particular reorg issue, but in general it seems to cover more mempool garbage situations.

@glozow I have two questions though.

  1. In mempool / miner: regularly flush <=0-fee entries and mine everything in the mempool #27018 you say

Though they don't need to be mutually exclusive, e.g. we could both require individual transactions to meet minrelayfeerate and also evict below-minrelayfeerate entries in TrimToSize().

What would be a practical benefit of this PR (#26933) if #27018 is already merged? (e.g., better UX, attack mitigated, cleaner code, etc.).

  1. If only mempool / miner: regularly flush <=0-fee entries and mine everything in the mempool #27018 is merged and this one is not, what would change to v3 and ephemeral anchors?

@glozow
Copy link
Member Author

glozow commented Feb 2, 2023

What would be a practical benefit of this PR (#26933) if #27018 is already merged? (e.g., better UX, attack mitigated, cleaner code, etc.).

My reservation with a #27018-only approach is we haven't answered whether we're ok with TrimToSize() (and thus reorgs and RBFs) potentially evicting many entries (I'lll re-post the 2500-tx scenario on that PR).

My original intent was to do this PR + evict everything below minrelayfeerate in TrimToSize(), which I think partially (?) addresses the problem with seeding mempool in a reorg (you can't bump both the reorged tx + a large 0-fee tx with 1-parent-1-child v3, and you can't attach multiple descendants to anything v3).

If only #27018 is merged and this one is not, what would change to v3 and ephemeral anchors?

Nothing is really changing with v3 regardless. If we do this PR, only v3 transactions can be below minrelayfeerate and bumped through package CPFP. If we don't do this PR, v3 still has the same rules, it's just that below-minrelayfeerate is no longer exclusive to v3.

@instagibbs
Copy link
Member

instagibbs commented Feb 2, 2023

Did some naive benchmarking with #27019 and on my basic laptop got 0.72 seconds for evicting 100 packages of size 25 each (2500 txns total).

edit: Using not very scientific methods of repeating the bench with and without eviction steps, it appears to roughly take half that amount of time for the evictions themselves, regardless of topology. ~0.33s

@ajtowns
Copy link
Contributor

ajtowns commented Feb 4, 2023

This is insufficient for preventing transactions that will never be mined from staying in the mempool, because TrimToSize would leave transactions in the mempool if a parent and multiple children appear to have enough fee for the combined package size, even though no single child has an ancestor fee rate above the min relay fee (eg a "children-pay-for-parent" scenario).

Would this be fixable by having TrimToSize remove any tx whose ancestor fee rate is below the minrelay fee if it also has no descendants (m_children.empty()) ? You could probably merge that into the descendant feerate index, just by pretending the descendant fee rate is zero if both those conditions are true.

@ajtowns
Copy link
Contributor

ajtowns commented Apr 17, 2023

I'm not really sure where to draw the line between useful and not useful

I think "submitpackage" would count as obviously useful if it was available on mainnet -- even without package relay, a miner could expose that via a web form to allow people to do cpfp bumps when the (miner's) mempool is full, eg.

I was viewing that RPC more as "here's a way of exposing some code we're working on so we can test it while it's in development", but if you look at it as "here's something that would be useful already, except we don't want to expose it because if someone submits a sub-minrelayfee tx it'll clog up their mempool without ever having any possibility of getting relayed", then this PR fixes that problem.

I think with this PR merged, we could reasonably expose submitpackage outside of regtest, though should keep it debug-only/experimental (after this PR, I think it's never worse than having 500MB in the mempool and submitting a min mempool fee tx, and we already allow that).

@glozow glozow force-pushed the 2023-01-package-mempoolmin-only branch from 6fb01d2 to 9fa3f69 Compare April 17, 2023 08:51
glozow added 3 commits April 17, 2023 09:52
Avoid adding transactions below min relay feerate because, even if they
were bumped through CPFP when entering the mempool, we do not have a
DoS-resistant way of ensuring they always remain bumped.  In the future,
this rule can be relaxed (e.g. to allow packages to bump 0-fee
transactions) if we find a way to do so.
@glozow glozow force-pushed the 2023-01-package-mempoolmin-only branch from 9fa3f69 to 563a2ee Compare April 17, 2023 08:54
@glozow
Copy link
Member Author

glozow commented Apr 17, 2023

Last push fixes + tests the case where package meets mempool min feerate, but hits maxmempool and is evicted immediately (the user-facing effect is that submitpackage now throws a different and more helpful JSONRPCError). Don't know why I hadn't been testing that already, my bad.

I think "submitpackage" would count as obviously useful if it was available on mainnet -- even without package relay, a miner could expose that via a web form to allow people to do cpfp bumps when the (miner's) mempool is full, eg.

That makes sense to me as a useful use case, though I'm unsure if we should encourage miners to accept txns the rest of the network can't see.

I think with this PR merged, we could reasonably expose submitpackage outside of regtest, though should keep it debug-only/experimental (after this PR, I think it's never worse than having 500MB in the mempool and submitting a min mempool fee tx, and we already allow that).

Thought about this for a bit. While there are edge cases where the package won't go in, and submitpackage doesn't have a maxfeerate/maxburn check, I suppose this is not unsafe. Could open the RPC in a followup?

Copy link
Member

@instagibbs instagibbs left a comment

Choose a reason for hiding this comment

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

re-ACK bf77fc9

self.log.info("Check a package that passes mempoolminfee but is evicted immediately after submission")
mempoolmin_feerate = node.getmempoolinfo()["mempoolminfee"]
current_mempool = node.getrawmempool(verbose=False)
worst_feerate_btcvb = Decimal("21000000")
Copy link
Member

Choose a reason for hiding this comment

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

should this just be None and have a check that it's non-None later? or is this value important?

Copy link
Member Author

Choose a reason for hiding this comment

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

no special meaning, just me implementing "find the min" in a very elementary way 😅 will fix if I retouch

@DrahtBot DrahtBot requested a review from ajtowns April 17, 2023 14:27
@instagibbs
Copy link
Member

(the user-facing effect is that submitpackage now throws a different and more helpful JSONRPCError)

For those following at home, the legacy reason it was giving was the first transaction in package's individual submission error, aka missing mempool min fee.

@ajtowns
Copy link
Contributor

ajtowns commented Apr 26, 2023

reACK bf77fc9

@DrahtBot DrahtBot removed the request for review from ajtowns April 26, 2023 09:49
@glozow glozow merged commit bdfe27c into bitcoin:master Apr 26, 2023
sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Apr 28, 2023
achow101 added a commit to bitcoin-core/gui that referenced this pull request Oct 5, 2023
…tside of regtest

5b878be [doc] add release note for submitpackage (glozow)
7a9bb2a [rpc] allow submitpackage to be called outside of regtest (glozow)
5b9087a [rpc] require package to be a tree in submitpackage (glozow)
e32ba15 [txpackages] IsChildWithParentsTree() (glozow)
b4f28cc [doc] parent pay for child in aggregate CheckFeeRate (glozow)

Pull request description:

  Permit (restricted topology) submitpackage RPC outside of regtest. Suggested in bitcoin/bitcoin#26933 (comment)

  This RPC should be safe but still experimental - interface may change, not all features (e.g. package RBF) are implemented, etc. If a miner wants to expose this to people, they can effectively use "package relay" before the p2p changes are implemented. However, please note **this is not package relay**; transactions submitted this way will not relay to other nodes if the feerates are below their mempool min fee. Users should put this behind some kind of rate limit or permissions.

ACKs for top commit:
  instagibbs:
    ACK 5b878be
  achow101:
    ACK 5b878be
  dergoegge:
    Code review ACK 5b878be
  ajtowns:
    ACK 5b878be
  ariard:
    Code Review ACK  5b878be. Though didn’t manually test the PR.

Tree-SHA512: 610365c0b2ffcccd55dedd1151879c82de1027e3319712bcb11d54f2467afaae4d05dca5f4b25f03354c80845fef538d3938b958174dda8b14c10670537a6524
@Sjors
Copy link
Member

Sjors commented Nov 23, 2023

Just ran into this today while testing #27463.

To make testing of package submission easier, should we have an option to allow this on test networks? Or perhaps a way to set a minimum for GetMinFee()?

@sdaftuar does mempool clustering fix this? E.g. is it just a matter of (occasionally) evicting chunks below -minrelaytxfee? From the above discussion I get the impression that the answer is yes, but most of this was discussed before that proposal came out.

@instagibbs
Copy link
Member

@Sjors testing it includes making sure nothing below minrelay can enter the mempool, unfortunately until v3(where 0-fee will be allowed) or cluster mempool is deployed, which makes trimming very fast

@glozow glozow deleted the 2023-01-package-mempoolmin-only branch January 15, 2024 11:59
Fabcien added a commit to Bitcoin-ABC/bitcoin-abc that referenced this pull request Jul 9, 2024
Summary:
```
Note that this still allows packages to bump transactions that are below the dynamic mempool minimum feerate, which means this still solves the "mempool is congested and my presigned 1sat/vB tx is screwed" problem for all transactions.

[...]

Unless we have a DoS-resistant way of ensuring package CPFP-bumped transactions are always bumped, allowing package CPFP to bump below-minrelayfeerate transactions can result in these problematic situations. See #27018 which proposes a partial solution with some limitations, and contains discussion about potential improvements to eviction strategy. While no adequate solution exists, for now, avoid these situations by requiring all transactions to meet min relay feerate.
```

Backport of [[bitcoin/bitcoin#26933 | core#26933]].

Note that the txpackage_tests has to be slightly adjusted to work with our codebase, and the mempool full functional test case has been rewritten to account for the absence of segwit (weight vs size).

Test Plan:
  ninja all check check-functional

Reviewers: #bitcoin_abc, PiRK

Reviewed By: #bitcoin_abc, PiRK

Differential Revision: https://reviews.bitcoinabc.org/D16433
@instagibbs instagibbs mentioned this pull request Jul 19, 2024
roqqit pushed a commit to doged-io/doged that referenced this pull request Aug 1, 2024
Summary:
```
Note that this still allows packages to bump transactions that are below the dynamic mempool minimum feerate, which means this still solves the "mempool is congested and my presigned 1sat/vB tx is screwed" problem for all transactions.

[...]

Unless we have a DoS-resistant way of ensuring package CPFP-bumped transactions are always bumped, allowing package CPFP to bump below-minrelayfeerate transactions can result in these problematic situations. See #27018 which proposes a partial solution with some limitations, and contains discussion about potential improvements to eviction strategy. While no adequate solution exists, for now, avoid these situations by requiring all transactions to meet min relay feerate.
```

Backport of [[bitcoin/bitcoin#26933 | core#26933]].

Note that the txpackage_tests has to be slightly adjusted to work with our codebase, and the mempool full functional test case has been rewritten to account for the absence of segwit (weight vs size).

Test Plan:
  ninja all check check-functional

Reviewers: #bitcoin_abc, PiRK

Reviewed By: #bitcoin_abc, PiRK

Differential Revision: https://reviews.bitcoinabc.org/D16433
@bitcoin bitcoin locked and limited conversation to collaborators Jan 14, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

Projects

Development

Successfully merging this pull request may close these issues.

7 participants