Package Mempool Submission with Package Fee-Bumping #22290

glozow · 2021-06-20T15:49:10Z

This implements mempool validation logic for fee-bumping transactions using CPFP and RBFing mempool transactions within a package, and the combination of both (i.e. a child in a package can pay to RBF its parents' conflicts). This does not implement package relay; there are no P2P changes.

For more info, see full proposal gist.

Package Mempool Accept Progress:

Note that, until package relay exists, fee-bumped package transactions that are otherwise too-low-fee won't go any further than the user's mempool. This PR doesn't expose the package validation codepath to users because it would be misleading.

DrahtBot · 2021-06-20T17:19:13Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#22981 (doc: Fix incorrect C++ named args by MarcoFalke)
#22976 (scripted-diff: Rename overloaded int GetArg to GetIntArg by ryanofsky)
#22901 (Improve mempool_package_limits.py by naiza2000)
#22674 (validation: mempool validation and submission for packages of 1 child + parents by glozow)
#22539 (Re-include RBF replacement txs in fee estimation by darosior)
#22097 (validation: Move package acceptance size limit from KvB to WU by ariard)
#21515 (Erlay: bandwidth-efficient transaction relay protocol by naumenkogs)

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.

sdaftuar · 2021-06-21T17:17:59Z

I have some concerns around what semantics are desired for bypassing the fee rate checks for a single transaction and using a notion of package fee rate instead.

I think the logic here — of using the descendant fee rate as an alternate to the transaction’s fee rate — is insufficient for preventing free relay. Consider a 3 transaction package where one child transaction C has two parents, A and B, all of equal size. Suppose A and B are zero-fee transactions and C has a fee rate of 2. Then each of A and B would evaluate to having a fee rate of 1 (with C), but as a package the fee rate would be just 2/3. If the mempool min fee or min relay fee is 1, then this package would make it in despite being below the required fee rate.

I think this type of issue may be somewhat difficult to avoid if we don’t tailor our semantics to the use case(s) we are trying to support. Right now, if I understand correctly, we don’t enforce any particular topology on the packages we accept — in fact I think the package acceptance logic would even accept unrelated transactions as well? One idea I had was to require the whole package’s fee rate to be above the min relay and mempool min fee as well, but that doesn’t work very well if we allow someone to bundle in an unrelated high fee transaction to “pay” for some low fee rate package.

We could check that a package is connected (from a graph theory perspective) as a condition for acceptance, but that is also not quite sufficient for achieving the semantics that I think we want. For instance, if we are processing some package that has a sub graph of transactions which would not make it in on its own, we probably wouldn’t want to admit that whole graph? I’m not quite sure. It seems like if there is a detachable sub graph that would get evicted shortly after acceptance because it’s below the mempool min fee, that might still admit some kind of free relay problem, similar to the issue with unrelated transactions.

My previous approach to the package relay problem was to define packages in a future p2p protocol extension as being the set of unconfirmed ancestors of a single target transaction. If that is sufficient for the use cases we are currently trying to support, then I think that simplifies the concerns a great deal — in this simple case I believe we could just look at two things: (a) check the target transaction’s own fee rate is sufficient to get in, and (b) check that the entire ancestor package for that target transaction also has a total fee rate sufficient to get in. (Of course we’d have to add a check that validates a package only contains ancestor transactions of the target, too.)

The other benefit of using a target transaction’s ancestors as how we define a package is that it lines up better with how the mining algorithm currently works.

If multiple children paying for multiple parents is some desired use case, I’m not sure the mempool and mining code are set up well enough to support that, so it would be helpful to analyze those use cases better to make sure our implementation will work okay.

Rspigler · 2021-06-21T21:37:34Z

in this simple case I believe we could just look at two things: (a) check the target transaction’s own fee rate is sufficient to get in, and (b) check that the entire ancestor package for that target transaction also has a total fee rate sufficient to get in.

This seems reasonable.

glozow · 2021-06-22T11:05:30Z

Thank you for the thoughtful review @sdaftuar!

I think the logic here — of using the descendant fee rate as an alternate to the transaction’s fee rate — is insufficient for preventing free relay. Consider a 3 transaction package where one child transaction C has two parents, A and B, all of equal size. Suppose A and B are zero-fee transactions and C has a fee rate of 2. Then each of A and B would evaluate to having a fee rate of 1 (with C), but as a package the fee rate would be just 2/3. If the mempool min fee or min relay fee is 1, then this package would make it in despite being below the required fee rate.

Great point. I had been thinking of descendant feerate as a good marker since that's how we evict from mempool, but it is imperfect: I think we already have the case where a transaction's ancestor score is too low to be mined, but descendant score too high to be evicted. And it's additionally problematic with package relay.

A proposal: if the mempool is intended to store the best candidates for mining, then we should evict in the opposite order we include in blocks, which is ancestor score.
So a transaction's minerscore = max([ancestorfeerate(tx) for tx in {itself, all its descendants}]). (This is with the current mining code - I suppose the definition of minerscore would be updated if/when block template creation changes).

If we replaced descendant feerate with minerscore, would that solve this problem? We go through the package, calculate everyone's ancestor feerate (including in-package and in-mempool ancestors), then we calculate everyone's minerscore based on that? Everyone's minerscore must surpass the min mempool/relay feerate. I think, then, it might not be necessary to specify/figure out which transactions are sponsees and which ones are sponsors?

(Very far down the line, but just throwing a thought out there: considering feefilters with package relay, I think we would also want to use [unmodified] minerscore for feefiltering as well).

sdaftuar · 2021-06-22T21:29:26Z

A proposal: if the mempool is intended to store the best candidates for mining, then we should evict in the opposite order we include in blocks, which is ancestor score.
So a transaction's minerscore = max([ancestorfeerate(tx) for tx in {itself, all its descendants}]). (This is with the current mining code - I suppose the definition of minerscore would be updated if/when block template creation changes).

If we replaced descendant feerate with minerscore, would that solve this problem?

I think we should consider these two things separately: (1) whether to change the eviction algorithm used by the mempool, and (2) whether to change the fee rate heuristic used to evaluate transaction / package acceptance.

Regarding the use of the miner score based on maximum-ancestor-feerate-of-descendants, I think that heuristic doesn't work very well for eviction. Imagine this scenario: the mempool has a very large, very low fee rate transaction A, with children B and C. C also is a child of another low feerate parent D.

It is possible then that B has such a high feerate that A and B would be selected for the next block, and then that C and D would be selected as well (once A is paid for by B, C's ancestor feerate score would go up). However, if A is in fact very large, then C's own ancestor fee rate could be quite low, so that D's minerscore could be very small. This might mean that D and C could be evicted if the mempool were full, even if they would be selected for the next block!

(As an aside I think the worst-case computation required to maintain this score would be worse than the status quo, too -- going from O(n) to O(n^2) to update statistics in the mempool when transactions are added/removed, where n = ancestor/descendant count.)

However regarding the heuristic we use for admitting a package to the mempool, I think using this max-ancestor-feerate-of-descendants as an additional check that we compare to the min-relay-fee and mempool-min-fee probably does work. It might mean that packages which include a transaction that would be relying on some in-mempool-sibling to pay for a low fee parent might not make it in, but if that's not a use case we're worried about then probably this is fine (if conservative)?

That seems to be a generalization of what I had proposed; I had suggested requiring a single ancestor-package that passes the fee rate check in total, while you're saying we can just require that every transaction in the package be part of some ancestor package that would pass the fee rate check. I'll give that more thought but it seems like a plausible solution.

EDIT: One additional thought, assuming this idea works at all I think it ought to be sufficient to restrict the calculation of the score to the package transactions alone. That is, for each transaction, calculate its fee rate for mempool acceptance as max([in-package-ancestor-fee-rate(tx) for tx in {itself, descendants}], where the in-package-ancestor-fee-rate(tx) is defined to be the min(tx fee rate, tx's fee rate including in-package ancestors). And then for each transaction in the package, evaluate that fee rate against the mempool min fee and the min relay fee. The idea is that we only need to ensure that we're paying enough to justify relay of the transactions -- when the network gets busier, the mempool min fee goes up so as long as the new transaction packages being relayed are continuing to have their fee rates go up too, that should be good enough to prevent free relay. There shouldn't be any need to look at the fee rates of the transactions that are already in the mempool.

glozow · 2021-06-23T15:58:10Z

Right, I agree with the separation between mempool eviction policy and evaluation of package transactions. Won't pursue the former much further here...

My plan of attack after the IRC discussion last night is going to be 1 parent + 1 child packages (perhaps these can also be thought of as 1 sponsee + 1 sponsor) and I think checking everyone's max-ancestor-feerate-of-descendants or descendant feerate of sponsee & ancestor feerate of sponsor would all work.

Edit: I'm going for 1 child + multiple parents instead, so package feerate is what I'll use.

One additional thought, assuming this idea works at all I think it ought to be sufficient to restrict the calculation of the score to the package transactions alone. That is, for each transaction, calculate its fee rate for mempool acceptance as max([in-package-ancestor-fee-rate(tx) for tx in {itself, descendants}], where the in-package-ancestor-fee-rate(tx) is defined to be the min(tx fee rate, tx's fee rate including in-package ancestors). And then for each transaction in the package, evaluate that fee rate against the mempool min fee and the min relay fee. The idea is that we only need to ensure that we're paying enough to justify relay of the transactions -- when the network gets busier, the mempool min fee goes up so as long as the new transaction packages being relayed are continuing to have their fee rates go up too, that should be good enough to prevent free relay. There shouldn't be any need to look at the fee rates of the transactions that are already in the mempool.

Good point!!!

This allows CPFP within a package prior to submission to mempool.

Update the existing unit test to have 0 fees in parent, 1BTC fees in child. This makes the parent too-low-fee by itself, but enough with its child.

No change in behavior. For single transaction acceptance, this is a simple refactor: Workspace::m_all_conflicting -> MemPoolAccept::m_all_conflicts Workspace::m_replacement_transaction -> MemPoolAccept::m_rbf Workspace::m_conflicting_fees -> MemPoolAccept::m_conflicting_fees Workspace::m_conflicting_size -> MemPoolAccept::m_conflicting_size Workspace::m_replaced_transactions -> MemPoolAccept::m_replaced_transactions For package acceptance, we don't enable RBF yet, but we want these to be package-wide variables because: - Transactions will never have the same conflict by prevout in the package, but they could have the same conflict by tx, and their conflicts could share descendants. - We want to compare conflicts with the package fee rather than individual transaction fee.

Created a new file because rpc_packages.py is for testing that the RPCs are returning the results we want. feature_package_relay is for testing the special policies and behaviors like CPFP and RBF.

Gated on an ATMPARgs value until later, so there are no behavior changes in this commit.

As node operators are free to set their mempool policies however they please, it's possible for package transaction(s) to already be in the mempool. We definitely don't want to reject the entire package in that case (as that could be a censorship vector). We still need to return the successful result to the caller, so add another result type to MempoolAcceptResult.

DrahtBot · 2021-12-13T23:18:22Z

🐙 This pull request conflicts with the target branch and needs rebase.

_{Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft".}

…ges of 1 child + parents 046e8ff [unit test] package submission (glozow) e12fafd [validation] de-duplicate package transactions already in mempool (glozow) 8310d94 [packages] add sanity checks for package vs mempool limits (glozow) be3ff15 [validation] full package accept + mempool submission (glozow) 144a290 [policy] require submitted packages to be child-with-unconfirmed-parents (glozow) d59ddc5 [packages/doc] define and document package rules (glozow) ba26169 [unit test] context-free package checks (glozow) 9b2fdca [packages] add static IsChildWithParents function (glozow) Pull request description: This is 1 chunk of [Package Mempool Accept](https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a); it restricts packages to 1 child with its parents, doesn't allow conflicts, and doesn't have CPFP (yet). Future PRs (see #22290) will add RBF and CPFP within packages. ACKs for top commit: laanwj: Code review ACK 046e8ff Tree-SHA512: 37dbba37d527712f8efef71ee05c90a8308992615af35f5e0cfeafc60d859cc792737d125aac526e37742fe7683ac8c155ac24af562426213904333c01260c95

glozow · 2022-01-25T14:38:19Z

Next PR ready for review is #24152.

LarryRuane · 2022-03-29T17:38:46Z

Hi @sdaftuar, regarding your comment:

Consider a 3 transaction package where one child transaction C has two parents, A and B, all of equal size. Suppose A and B are zero-fee transactions and C has a fee rate of 2. Then each of A and B would evaluate to having a fee rate of 1 (with C), but as a package the fee rate would be just 2/3. If the mempool min fee or min relay fee is 1, then this package would make it in despite being below the required fee rate.

This is an interesting problem, after some thought I wrote a little demo to better understand these concepts, and I think it addresses some of these questions. I thought you and @glozow might find this helpful:

https://github.com/LarryRuane/bitcoin_package_accept_demo

9bebf35 [validation] don't package validate if not policy or missing inputs (glozow) 51edcff [unit test] package feerate and package cpfp (glozow) 1b93748 [validation] try individual validation before package validation (glozow) 17a8ffd [packages/policy] use package feerate in package validation (glozow) 09f32cf [docs] package feerate (glozow) Pull request description: Part of #22290, aka [Package Mempool Accept](https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a). This enables CPFP fee bumping in child-with-unconfirmed-parents packages by introducing [package feerate](https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a#fee-related-checks-use-package-feerate) (total modified fees divided by total virtual size) and using it in place of individual feerate. We also always [validate individual transactions first](https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a#always-try-individual-submission-first) to avoid incentive-incompatible policies like "parents pay for children" or "siblings pay for siblings" behavior. ACKs for top commit: instagibbs: reACK 9bebf35 mzumsande: Code review ACK 9bebf35 t-bast: ACK 9bebf35 Tree-SHA512: 5117cfcc3ce55c00384d9e8003a0589ceac1e6f738b1c299007d9cd9cdd2d7c530d31cfd23658b041a6604d39073bcc6e81f0639a300082a92097682a6ea8c8f

DrahtBot · 2022-12-22T00:44:01Z

There hasn't been much activity lately and the patch still needs rebase. What is the status here?

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

glozow · 2022-12-22T12:14:04Z

Actually that's a good point @DrahtBot - this PR was made to track progress on package relay / package mempool stuff but it's not great at it since there are now multiple branches, v3 is separated, and there are things in multiple repos.
Possibly more helpful, here's a board to track everything package relay-related: Package Relay + V3 Project Tracking (view)

flack · 2022-12-22T20:01:32Z

@glozow that link gives a 404 for me. Also the board you mention isn't listed in https://github.com/orgs/bitcoin/projects?query=is%3Aopen. Or is it only accessible to members?

glozow · 2023-01-04T11:08:32Z

@flack apologies I didn't realize! It should be public now.

DrahtBot added Mempool RPC/REST/ZMQ Validation labels Jun 20, 2021

This was referenced Jun 20, 2021

policy: Trim Packages when transaction with same txid exists in mempool #22252

Closed

mempool/validation: mempool ancestor/descendant limits for packages #21800

Merged

glozow force-pushed the package-mempool-accept branch from 7ebf83a to 1bc51d4 Compare June 21, 2021 09:21

This was referenced Jul 28, 2021

refactor: Move mutable globals cleared in ::UnloadBlockIndex to BlockManager #22564

Merged

test: a test to check descendant limits #22582

Merged

glozow force-pushed the package-mempool-accept branch from 1bc51d4 to 9d08189 Compare August 10, 2021 09:58

This was referenced Aug 10, 2021

validation: mempool validation and submission for packages of 1 child + parents #22674

Merged

RBF move 2/3: extract RBF logic into policy/rbf #22675

Merged

glozow force-pushed the package-mempool-accept branch from 9d08189 to 4fa69ab Compare August 13, 2021 14:55

This was referenced Aug 14, 2021

Implement RBF inherited signaling and fix getmempoolentry returned bip125-replaceable status #22698

Closed

cut the validation <-> txmempool circular dependency 2/2 #22677

Merged

glozow force-pushed the package-mempool-accept branch from 4fa69ab to 12876ac Compare September 2, 2021 13:30

glozow added 12 commits October 20, 2021 11:27

[functional test] submitrawpackage RPC

ffbfb71

[packages/policy] use package feerate in package validation

edeb074

This allows CPFP within a package prior to submission to mempool.

[test] package submission with CPFP'd zero-fee parent

f37e126

Update the existing unit test to have 0 fees in parent, 1BTC fees in child. This makes the parent too-low-fee by itself, but enough with its child.

[packages/policy] implement package RBF

1a0b766

[functional test] package RBF

98238e7

Created a new file because rpc_packages.py is for testing that the RPCs are returning the results we want. feature_package_relay is for testing the special policies and behaviors like CPFP and RBF.

[functional test] cpfp and rbf together

4768198

[validation] implement ancestor comparison for RBF

634f950

Gated on an ATMPARgs value until later, so there are no behavior changes in this commit.

[policy] allow new unconfirmed if higher ancestor score in package RBF

042790a

[functional test] package RBF with ancestor scores

10f20ea

[functional test] partially submitted packages

535f311

glozow force-pushed the package-mempool-accept branch from 6591eb3 to 535f311 Compare October 20, 2021 10:29

jnewbery mentioned this pull request Oct 29, 2021

validation/refactor: refactoring for package submission #23381

Merged

DrahtBot added the Needs rebase label Dec 13, 2021

glozow mentioned this pull request Dec 21, 2021

Newsletters: add 180 (2021-12-22) bitcoinops/bitcoinops.github.io#702

Merged

glozow mentioned this pull request Jan 25, 2022

policy / validation: CPFP fee bumping within packages #24152

Merged

glozow mentioned this pull request Apr 30, 2022

policy: nVersion=3 and Package RBF #25038

Closed

glozow closed this Dec 22, 2022

glozow mentioned this pull request Apr 14, 2023

Package Relay Project Tracking #27463

Open

55 tasks

bitcoin locked and limited conversation to collaborators Jan 4, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Package Mempool Submission with Package Fee-Bumping #22290

Package Mempool Submission with Package Fee-Bumping #22290

Uh oh!

glozow commented Jun 20, 2021 •

edited

Loading

Uh oh!

DrahtBot commented Jun 20, 2021 •

edited

Loading

Uh oh!

sdaftuar commented Jun 21, 2021

Uh oh!

Rspigler commented Jun 21, 2021

Uh oh!

glozow commented Jun 22, 2021

Uh oh!

sdaftuar commented Jun 22, 2021 •

edited

Loading

Uh oh!

glozow commented Jun 23, 2021 •

edited

Loading

Uh oh!

DrahtBot commented Dec 13, 2021

Uh oh!

glozow commented Jan 25, 2022

Uh oh!

LarryRuane commented Mar 29, 2022 •

edited

Loading

Uh oh!

DrahtBot commented Dec 22, 2022

Uh oh!

glozow commented Dec 22, 2022

Uh oh!

flack commented Dec 22, 2022

Uh oh!

glozow commented Jan 4, 2023

Uh oh!

Uh oh!

Package Mempool Submission with Package Fee-Bumping #22290

Package Mempool Submission with Package Fee-Bumping #22290

Uh oh!

Conversation

glozow commented Jun 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Jun 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

sdaftuar commented Jun 21, 2021

Uh oh!

Rspigler commented Jun 21, 2021

Uh oh!

glozow commented Jun 22, 2021

Uh oh!

sdaftuar commented Jun 22, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

glozow commented Jun 23, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Dec 13, 2021

Uh oh!

glozow commented Jan 25, 2022

Uh oh!

LarryRuane commented Mar 29, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Dec 22, 2022

Uh oh!

glozow commented Dec 22, 2022

Uh oh!

flack commented Dec 22, 2022

Uh oh!

glozow commented Jan 4, 2023

Uh oh!

Uh oh!

glozow commented Jun 20, 2021 •

edited

Loading

DrahtBot commented Jun 20, 2021 •

edited

Loading

sdaftuar commented Jun 22, 2021 •

edited

Loading

glozow commented Jun 23, 2021 •

edited

Loading

LarryRuane commented Mar 29, 2022 •

edited

Loading