rbf-improvements.md

Replace by Fee Improvements

This post discusses limitations of current Bitcoin Core RBF policy and attempts to start a conversation about how we can improve it, summarizing some ideas that have been discussed. Please reply if you have any new input on issues to be solved and ideas for improvement!

Background

Please feel free to skip this section if you are already familiar with RBF.

Nodes may receive conflicting unconfirmed transactions, aka "double spends" of the same inputs. Instead of always keeping the first transaction, since v0.12, Bitcoin Core mempool policy has included a set of Replace-by-Fee (RBF) criteria that allows the second transaction to replace the first one and any descendants it may have.

Bitcoin Core RBF policy was previously documented as BIP 125. The current RBF policy is documented here. In summary:

1. The directly conflicting transactions all signal replaceability explicitly.

2. The replacement transaction only includes an unconfirmed input if that input was included in one of the directly conflicting transactions.

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

4. The additional fees pays for the replacement transaction's bandwidth at or above the rate set by the node's incremental relay feerate.

5. The sum of all directly conflicting transactions' descendant counts (number of transactions inclusive of itself and its descendants) does not exceed 100.

We can split these rules into 3 categories/goals:

• Allow Opting Out: Some applications/businesses are unable to handle transactions that are replaceable (e.g. merchants that use zero-confirmation transactions). We (try to) help these businesses by honoring BIP125 signaling; we won't replace transactions that have not opted in.

• Incentive Compatibility: Ensure that our RBF policy would not accept replacement transactions which would decrease fee profits of a miner. In general, if our mempool policy deviates from what is economically rational, it's likely that the transactions in our mempool will not match the ones in miners' mempools, making our fee estimation, compact block relay, and other mempool-dependent functions unreliable. Incentive-incompatible policy may also encourage transaction submission through routes other than the p2p network, harming censorship-resistance and privacy of Bitcoin payments.

• DoS Protection: Limit two types of DoS attacks on the node's mempool: (1) the number of times a transaction can be replaced and (2) the volume of transactions that can be evicted during a replacement.

Even more abstract: our goal is to make a replacement policy that results in a useful interface for users and safe policy for node operators.

Motivation

There are a number of known problems with the current RBF policy. Many of these shortcomings exist due to mempool limitations at the time RBF was implemented or result from new types of Bitcoin usage; they are not criticisms of the original design.

Pinning Attacks

The most pressing concern is that attackers may take advantage of limitations in RBF policy to prevent other users' transactions from being mined or getting accepted as a replacement.

SIGHASH_ANYONECANPAY Pinning

BIP125#2 can be bypassed by creating intermediary transactions to be replaced together. Anyone can simply split a 1-input 1-output transaction off from the replacement transaction, then broadcast the transaction as is. This can always be done, and quite cheaply. More details in this comment.

In general, if a transaction is signed with SIGHASH_ANYONECANPAY, anybody can just attach a low feerate parent to this transaction and lower its ancestor feerate. Even if you require SIGHASH_ALL which prevents an attacker from changing any outputs, the input can be a very low amount (e.g. just above the dust limit) from a low-fee ancestor and still bring down the ancestor feerate of the transaction.

TLDR: if your transaction is signed with SIGHASH_ANYONECANPAY and signals replaceability, regardless of the feerate you broadcast at, an attacker can lower its mining priority by adding an ancestor.

Absolute Fee

The restriction of requiring replacement transactions to increase the absolute fee of the mempool has been described as "bonkers." If the original transaction has a very large descendant that pays a large amount of fees, even if it has a low feerate, the replacement transaction must now pay those fees in order to meet Rule #3.

Package RBF

There are a number of reasons why, in order to enable Package RBF, we cannot use the same criteria.

For starters, the absolute fee pinning attack is especially problematic if we apply the same rules (i.e. Rule #3 and #4) in Package RBF. Imagine that Alice (honest) and Bob (adversary) share a LN channel. The mempool is rather full, so their pre-negotiated commitment transactions' feerates would not be considered high priority by miners. Bob broadcasts his commitment transaction and attaches a very large child (100KvB with 100,000sat in fees) to his anchor output. Alice broadcasts her commitment transaction with a fee-bumping child (200vB with 50,000sat fees which is a generous 250sat/vB), but this does not meet the absolute fee requirement. She would need to add another 50,000sat to replace Bob's commitment transaction.

Disallowing new unconfirmed inputs (Rule #2) in Package RBF would be broken for packages containing transactions already in the mempool, explained here.

Note: I originally proposed Package RBF using the same Rule #3 and #4 before I realized how significant this pinning attack is. I'm retracting that proposal, and a new set of Package RBF rules would follow from whatever the new individual RBF rules end up being.

Same Txid Different Witness

Two transactions with the same non-witness data but different witnesses have the same txid but different wtxid, and the same fee but not necessarily the same feerate. Currently, if we see a transaction that has the same txid as one in the mempool, we reject it as a duplicate, even if the feerate is much higher. It's unclear to me if we have a very strong reason to change this, but noting it as a limitation of our current replacement policy. See #24007.

User Interface

Using Unconfirmed UTXOs to Fund Replacements

The restriction of only allowing confirmed UTXOs for funding a fee-bump (Rule #2) can hurt users trying to fee-bump their transactions and complicate wallet implementations. If the original transaction's output value isn't sufficient to fund a fee-bump and/or all of the user's other UTXOs are unconfirmed, they might not be able to fund a replacement transaction. Wallet developers also need to treat self-owned unconfirmed UTXOs as unusable for fee-bumping, which adds complexity to wallet logic. For example, see BDK issues #144 and #414.

Difficult Interface

Currently, a user cannot simply create a replacement transaction targeting a specific feerate or meeting a minimum fee amount and expect to meet the RBF criteria. The fee amount depends on the size of the replacement transaction, and feerate is almost irrelevant.

Bitcoin Core's bumpfee doesn't use the RBF rules when funding the replacement. It estimates a feerate which is "wallet incremental relay fee" (a conservative overestimation of the node's incremental relay fee) higher than the original transaction, selects coins for that feerate, and hopes that it meets the RBF rules. It never fails Rule #3 and #4 because it uses all original inputs and refuses to bump a transaction with mempool descendants.

This is suboptimal, but is designed to work with the coin selection engine: select a feerate first, and then add fees to cover it. Following the exact RBF rules would require working the other way around: based on how much fees we've added to the transaction and its current size, calculate the feerate to see if we meet Rule #4.

While this isn't completely broken, and the user interface is secondary to the safety of the mempool policy, we can do much better. A much more user-friendly interface would depend only on the fee and size of the original transactions.

Updates to Mempool and Mining

Since RBF was first implemented, a number of improvements have been made to mempool and mining logic. For example, we now use ancestor feerates in mining (allowing CPFP), and keep track of ancestor packages in the mempool.

Ideas for Improvements

Goals

To summarize, these seem to be desired changes, in order of priority:

1. Remove Rule #3. The replacement should not be required to pay higher absolute fees.

2. Make it impossible for a replacement transaction to have a lower mining score than the original transaction(s). This would eliminate the SIGHASH\_ANYONECANPAY pinning attack.

3. Remove Rule #2. Adding new unconfirmed inputs should be allowed.

4. Create a more helpful interface that helps wallet fund replacement transactions that aim for a feerate and fee.

A Different Model for Fees

For incentive compatibility, I believe there are different formulations we should consider. Most importantly, if we want to get rid of the absolute fee rule, we can no longer think of it as "the transaction needs to pay for its own bandwidth," since we won't always be getting additional fees. That means we need a new method of rate-limiting replacements that doesn't require additional fees every time.

While it makes sense to think about monetary costs when launching a specific type of attack, given that the fees are paid to the miner and not to the mempool operators, maybe it doesn't make much sense to think about "paying for bandwidth". Maybe we should implement transaction validation rate-limiting differently, e.g. building it into the P2P layer instead of the mempool policy layer.

Recently, Suhas gave a formulation for incentive compatibility that made sense to me: "are the fees expected to be paid in the next (N?) blocks higher or lower if we process this transaction?"

I started by thinking about this where N=1 or 1 + p. Here, a rational miner is looking at what fees they would collect in the next block, and then some proportion p of the rest of the blocks based on their hashrate. We're assuming p isn't so high that they would be okay with lower absolute fees in the next 1 block. We're also assuming p isn't so low that the miner doesn't care about what's left of the mempool after this block.

A tweak to this formulation is "if we process this transaction, would the fees in the next 1 block higher or lower, and is the feerate density of the rest of the mempool higher or lower?" This is pretty similar, where N=1, but we consider the rest of the mempool by feerate rather than fees.

Mining Score of a Mempool Transaction

We are often interested in finding out what the "mining score" of a transaction in the mempool is. That is, when the transaction is considered in block template building, what is the feerate it is considered at?

Obviously, it's not the transaction's individual feerate. Bitcoin Core mining code sorts transactions by their ancestor feerate and includes them packages at a time, keeping track of how this affects the package feerates of remaining transactions in the mempool.

ancestor feerate: Ancestor feerate is easily accessible information, but it's not accurate either, because it doesn't take into account the fact that subsets of a transaction's ancestor set can be included without it. For example, ancestors may have high feerates on their own or we may have high feerate siblings.

TLDR: Looking at the current ancestor feerate of a transaction is insufficient to tell us what feerate it will be considered at when building a block template in the future.

min(individual feerate, ancestor feerate): Another heuristic that is simple to calculate based on current mempool tooling is to use the minimum of a transaction's individual score and its ancestor score as a conservative measure. But this can overestimate as well (see the example below).

min ancestor feerate(tx + possible ancestor subsets) We can also take the minimum of every possible ancestor subset, but this can be computationally expensive since there can be lots and lots of ancestor subsets.

max ancestor feerate(tx + possible descendant subsets): Another idea is to use the maximum ancestor score of the transaction + each of its descendants. This doesn't work either; it has the same blindspot of ancestor subsets being mined on their own.

Mining Score Example

Here's an example illustrating why mining score is tricky to efficiently calculate for mempool transactions:

Let's say you have same-size transactions A (21sat/vB), B (1sat/vB), C(9sat/vB), D(3sat/vB). The layout is: grandparent A, parent B, and two children C and D.

    A
    ^
    B
   ^ ^
   C D

A miner using ancestor packages to build block templates will first include A with a mining score of 21. Next, the miner will include B and C with a mining score of 5. This leaves D, with a mining score of 3.

Note: in this case, mining by ancestor feerate results in the most rational decisions, but a candidate set-based approach which makes ancestor feerate much less relevant could be more advantageous in other situations (e.g. if other transactions with feerates between 5 and 3sat/vB exist in the mempool).

Here is a chart showing the "true" mining score alongside the values calculating using imperfect heuristics described above. All of them can overestimate or underestimate.

				    A	     B       C	     D
mining score			|   21   |   5   |   5   |   3   |
ancestor feerate	  	|   21   |  11   |  10.3 |  8.3  |
min(individual, ancestor)?	|   A    |   B   |   C   |   D   |
min(individual, ancestor)=	|   21   |   1   |   9   |   3   |
min(tx + ancestor subsets)?     |   A    |   B   |  B+C  |  B+D  |
min(tx + ancestor subsets)=     |   21   |   1   |   5   |   2   |
max(tx + descendants subsets)?  |   A    |  A+B  | A+B+C | A+B+D |
max(tx + descendants subsets)=  |   21   |  11   |  10.3 |  8.3  |

(EDITED, thanks Murch)

Possibly the best solution for finding the "mining score" of a transaction is to build a block template, see what feerate each package is included at. Perhaps at some cutoff, remaining mempool transactions can be estimated using some heuristic that leans {overestimating, underestimating} depending on the situation.

Mining score seems to be relevant in multiple places: Murch and I recently found that it would be very important in "ancestor-aware" funding of transactions (the wallet doesn't incorporate ancestor fees when using unconfirmed transactions in coin selection, which is a bug we want to fix).

In general, it would be nice to know the exact mining priority of one's unconfirmed transaction is. I can think of a few block/mempool explorers who might want to display this information for users.

RBF Improvement Proposals

After speaking to quite a few people, here are some suggestions for improvements that I have heard:

• The ancestor score of the replacement must be {5, 10, N}% higher than that of every original transaction.

• The ancestor score of the replacement must be 1sat/vB higher than that of every original transaction.

• If the original transaction is in the top {0.75MvB, 1MvB} of the mempool, apply the current rules (absolute fees must increase and pay for the replacement transaction's new bandwidth). Otherwise, use a feerate-only rule.

• If fees don't increase, the size of the replacement transaction must decrease by at least N%.

• Rate-limit how many replacements we allow per prevout.

• Rate-limit transaction validation in general, per peer.

Perhaps some others on the mailing list can chime in to throw other ideas into the ring and/or combine some of these rules into a sensible policy.

Replace by Feerate Only

I don't think there's going to be a single-line feerate-based rule that can incorporate everything we need. On one hand, a feerate-only approach helps eliminate the issues associated with Rule #3. On the other hand, I believe the main concern with a feerate-only approach is how to rate limit replacements. We don't want to enable an attack such as:

1. Attacker broadcasts large, low-feerate transaction, and attaches a chain of descendants.

2. The attacker replaces the transaction with a smaller but higher feerate transaction, attaching a new chain of descendants.

3. Repeat 1000 times.

Fees in Next Block and Feerate for the Rest of the Mempool

Perhaps we can look at replacements like this:

1. Calculate the directly conflicting transactions and, with their descendants, the original transactions. Check signaling. Limit the total volume (e.g. can't be more than 100 total or 1MvB or something).

2. Find which original transactions would be in the next ~1 block. The replacement must pay at least this amount + X% in absolute fees. This guarantees that the fees of the next block doesn't decrease.

3. Find which transactions would be left in the mempool after that ~1 block. The replacement's feerate must be Y% higher than the maximum mining score of these transactions. This guarantees that you now have only better candidates in your after-this-block mempool than you did before, even if the size and fees the transactions decrease.

4. Now you have two numbers: a minimum absolute fee amount and a minimum feerate. Check to see if the replacement(s) meet these minimums. Also, a wallet would be able to ask the node "What fee and feerate would I need to put on a transaction replacing this?" and use this information to fund a replacement transaction, without needing to guess or overshoot.

Obviously, there are some magic numbers missing here. X and Y are TBD constants to ensure we have some kind of rate limiting for the number of replacements allowed using some set of fees.

What should they be? We can do some arithmetic to see what happens if you start with the biggest/lowest feerate transaction and do a bunch of replacements. Maybe we end up with values that are high enough to prevent abuse and make sense for applications/users that do RBF.

Mempool Changes Need for Implementation

As described in the mining score section above, we may want additional tooling to more accurately assess the economic gain of replacing transactions in our mempool.

A few options have been discussed:

• Calculate block templates on the fly when we need to consider a replacement. However, since replacements are quite common and the information might be useful for other things as well, it may be worth it to cache a block template.

• Keep a persistent block template so that we know what transactions we would put in the next block. We need to remember the feerate at which each transaction was included in the template, because an ancestor package may be included in the same block template in multiple subsets. Transactions included earlier alter the ancestor feerate of the remaining transactions in the package. We also need to keep track of the new feerates of transactions left over.

• Divide the mempool into two layers, "high feerate" and "low feerate." The high feerate layer contains ~1 block of packages with the highest ancestor feerates, and the low feerate layer contains everything else. At the edge of a block, we have a Knapsacky problem where the next highest ancestor feerate package might not fit, so we would probably want the high feerate layer ~2MvB or something to avoid underestimating the fees.

Acknowledgements

Thank you to everyone whose RBF-related suggestions, grievances, criticisms and ideas were incorporated in this document: Andrew Chow, Matt Corallo, Suhas Daftuar, Christian Decker, Mark Erhardt, Lloyd Fournier, Lisa Neigut, John Newbery, Antoine Poinsot, Antoine Riard, Larry Ruane, S3RK and Bastien Teinturier.

Unfortunately, the descendant size limit also includes the size of the transaction itself (it's a transaction's "size_with_descendants" that we compare to that limit) -- we'd have to redefine these terms a bit and rearchitect slightly to achieve the effect that I think you're proposing, where we don't decrease the maximum size of a single transaction but we do limit the size of its descendants.

@sdaftuar thanks a lot for this detailed answer, that's very helpful to understand more of the nuances of mempool design!

I want to raise the possibility that these DOS concerns may be completely unfounded. I want to advocate for simplicity here and to show why we don't need complicated relay rules in order to mitigate risk of DOS.

mempool siphoning attack

I don't believe that wouldn't actually work in practice. A miner shouldn't clear out its mempool with lower-value higher-feerate transactions, regardless of RBF relay rules. Miners should have a much larger mempool than most full nodes. And miner inclusion rules do not have to match relay rules. Its neither necessary nor possible for relay policy to exactly match miner inclusion policy, at very least because its not possible to force all miners to use the same inclusion policy. Its certainly useful for relay policy to be similar to miner inclusion policy in practice in certain ways, for the reasons mentioned under "incentive compatibility" but its by no means imperitive to "ensure that our RBF policy would not accept replacement transactions which would decrease fee profits of a miner." Nodes should be resilient against their mempools differing from their connections. If rule 3 were removed, I don't see any reason to expect that node mempools would be likely to difer enough from miner mempools to cause any significant problems in fee estimation either.

Incentive-incompatible policy may also encourage transaction submission through routes other than the p2p network, harming censorship-resistance and privacy of Bitcoin payments.

I think its important to identify which incentive-incompatible policy might encourage this behavior. Specifically, its anything that prevents transactions getting to miners. In general, any allowed repalcements will not do this. Allowing a transaction to be replaced will not prevent the replaced transaction from having reached miners. What could cause a transaction to not reach miners is any time relay rules decide to reject a replacement transaction. Those are the times that would incentivize someone to use out-of-band transaction submission channels.

We should expect miners will be using a more complex, more optimal way of determining what blocks they're working on. I don't think its reasonable to run with the premise that if a normal full node replaces transaction A with transaction B (and therefore removes transaction A from its mempool) that miners will also remove transaction A. I think we should instead run with the assumption that miners keep all potentially relevant transactions in their mempools, including potentially many conflicting transctions, in order to create the most profitable blocks. And therefore we shouldn't put the constraint on normal non-mining full nodes to do that same more-complex mempool behavior or add any complexity for the purpose of denying transaction replacements.

"are the fees expected to be paid in the next (N?) blocks higher or lower if we process this transaction?"

I think a lot of the complexity in these ideas is because of the attempt to match relay rules with miner inclusion rules. So I want to echo James O'Beirne's opinion on this that this may be the wrong path to go down (a path of more complexity without much gain). He said:

"Special consideration for "what should be in the next block" and/or the caching of block templates seems like an imposing dependency, dragging in a bunch of state and infrastructure to a question that should be solely limited to mempool feerate aggregates and the feerate of the particular txn package a wallet is concerned with."

Remove Rule #3. The replacement should not be required to pay higher absolute fees.

I want to add my support for removal of this rule. Last month I wrote up a thought experiment that showed why removing the absolute fee rule would not introduce a DOS vector. The reason is that, while extra unnecessary data can be propagated through the network in a non-full-block environment, the amount of that extra data + the amount of "non-extra" data would never exceed the amount of data that could already be propagated in a full-block environment. Nodes already need to handle the full-block environment, so a little extra data at a time when much less data is being broadcast in general physically cannot be a DOS vector - there wouldn't be enough data floating around even with intentional spamming to deny anyone service.

this is not just the case if blocks are not full; this is also the case if the transactions being replaced are also much higher feerate than the next best transactions in the mempool, and you're replacing them with smaller transactions that give up more fee than you'd pick up in transactions further down in the mempool.

True, but in that case, the attacker has already paid a higher fee than they needed to pay to get into that block, so in a real sense they already "paid" for the spam that they cause that way in the fee for the original transaction.

If the amount paid by the spammer to the network is equal to or more than the damage they cause the network, then that class of spam basically becomes a non-issue - the amount paid compensates for the damage. If we break down the significant costs incurred on the network by transactions we can get a more quantitative picture of this:

A. Mining PoW (chain security)

B. Ongoing relay cost (bandwidth and validation costs)

C. Initial node spin up costs (IBD bandwidth and validation costs, as well as the time it takes to spin up)

B and C are separated because first of all they don't relay the same amount of data (active nodes relay all data, initially spinning up nodes only receive mined data) but also nodes spinning up incur an additional cost: the time it takes to spin up. The longer this is, the fewer people will feel its worth it to spin up a node at all. 

In any case, what these cost fractions are is certainly up for debate, but a very-rough example estimate might be: A. 70% B. 10% C. 20%

So with these assumptions, if an attacker is creating 1 to 1 spam, where 1 transaction causes 2 transactions worth of data to be relayed, they're causing 10% more cost on the network in total than if they only sent the one transaction. 

Consider the following type of spam. Some malicious actor has a regular need to get a transaction mined quickly, however they also have an interest in spamming the network. With just the fee-rate increase rule, the actor could send a transaction with the minimum fee, then the same transaction with 2x the minimum fee, etc until they get to their target fee rate. There's always going to be some spread between the lowest fee that will be relayed and the highest fee necessary to almost definitely make it into the next block. Again, this is a spread I don't have good information on. But let's say that spread is 50x (meaning the maximum fee necessary is 50x the minimum fee that will be relayed). This means an attacker could send a 50 to 1 spam ratio (by data transmitted) for that transaction. The attacker could produce more spam than 50 to 1, but they would be paying more fees than the need to get into the block to do it, so that spam would obviously be effectively paid for by that extra fee. 

However remember my estimate of the costs incurred on the network above ^. 10% of the costs the network incurrs from a (normal non-replacing) transaction are relay costs. A transaction sent in this way with 50 to 1 spam (by data) costs the network 1*.9+.1*50 = 5.9 times as much as just sending the single transaction, and yet if the spammer really wants to be in the next block and is willing to pay 50x the minimum fee to get in, the spammer is paying over 8 times as much as the costs they're inducing in the network. So that spam is already more than paid for.

Now, this ratio does actually get more economical for the attacker the less they spam. So if a malicious actor were only willing to pay 2x the minimum transaction fee, they'd only be paying 1.8 times the cost they're incurring on the network. But still more.

So whether a spammer is trying to do RBF spam by replacing a transaction with a higher feerate than they need or by replacing minimum-fee transactions with successively higher fee rates up to the maximum fee they're willing to pay, the spam is paid for. And if a spammer is trying to spam a non-full-block network, it will not present any risk of DOS.

So my conclusion from the above lines of thinking are that we should stop worrying so much about prevening spam if rules 3 and 5 are removed. Rule 4 is plenty sufficient to mitigate the problems of spam.

That said, I do like the idea Gloria brought up here about staggering broadcast of replacement transactions. I think this would be a pretty simple way to set a very clear boundary on how much spam could potentially be propgated in the worst case scenario.

making the flushing attack more clear:

1. send 3000 100kb txns (uses 300MB) at feerate top-of-mempool sat/vb2.
2. n times do:
   a. send 3000 non-conflicting 100kb txns (uses 300MB) at feerate top-of-mempool+i sat/vb
3. send 3000 100 byte txns replacing all of the above at feerate top-of-mempool+1 sat/vb
4. mempool on all nodes is now "flushed" at a cost of 300kb block data per 300MB cleared

optimizations: piggyback transaction you want to do (e.g., consolidations, coinjoins, lightning channel opens, mining payouts) with this.

Hi Jeremy, could you clarify this attack a little more? What's the significance of feerate top-of-mempool+i? What might i be? You mention step 3 replaces "all of the above" but from my reading it would only replace 3000 of the above, not all. Is that right?

I have two thoughts:

1. My point from above still holds: the attacker is paying for all that spam already. By sending transactions with top-of-mempool feerate, they're overpaying for those transactions, and that overpayment pays for their future spam (in step 4).
2. You mention that in step 3 the spammer would replace their transactions with "feerate top-of-mempool+1 sat/vb". It makes me wonder if the additional fee required should be calculated a bit differenetly. If nodes require replacement transactions to at minimum pay enough extra fee rate for a non-replaced transaction on its own to be relayed with that (extra) fee. A node with a full mempool isn't going to accept (and therefore relay) any transactions that have less than top-of-mempool feerate. So I wonder if we should consider making that fee the minimum extra fee required for a node to replace transactions in this circumstance. Step 3 would then require the attacker to double their original fee.

The +i / +1 is whatever increment you need to replace the txn.

you repeat the process above n times, which gives you n * 3000*100kb replacement potential. A standard mempool is 300MB. Because we do this attack incrementing the fees as we go, we are able to push the txns out to nodes with larger mempoos as well.

then, when we replace, we replace with things that are tiny paying this same feerate.

this is fixed if we require increasing absolute fee.

generally i dont think we're going to get around 'complex interactions of rules' with 'more complex rules'. The need is probably to solve the problem more wholistically, but i could be wrong on that.

mempool on all nodes is now "flushed" at a cost of 300kb block data per 300MB cleared

That would not the most significant cost incurred by the malicious actor. As I mentioned above, miners shouldn't be discarding valid higher-value block templates with lower-value ones as a replacement. So the spammer would be paying a ton of real money for the opportunity to produce this spam.

To enumerate the damage caused by this attack, they are: increased data flow (spam), and a non-matching mempool between miners and nodes, right? This could be used to effectively max out nodes bandwidth. And when a block hits, it'll propagate much slower because relay needs to retransmit all the transactions in the block. Will this negatively affect fee estimation? Well if nodes have 3000 100kb transactions replaced with 3000 100 byte transactions, it might look like the mempool is empty and a low fee is all that's needed. If you really wanted to have better fee estimation during a situation like this, nodes could act a bit more minery and keep their mempool full (of some of the replaced large transactions) so they can more accurately estimate block templates. But transactions would be effectively blocked anyway because of the spammer paying top dollar (or should I say top sat?) for their 300MB of transactions, so accurate fee estimation is somewhat moot for most people during this window.

So yes this would be a DOS for 300 blocks. But it would be a DOS with or without replacement transactions. Paying a super high fee for 300MB of transactions will deny service to the vast majority of people who want to send an on-chain transaction. The rest seems rather moot considering that, no?

@fresheneesz that's incorrect. If you assume that the miner has a good block template they cache, that contains at most 10 100KB txns at a lower feerate than if it contained all replacements. So if you can replace before mining, good, but using the old block template actually makes (IMO) this attack still compelling. Essentially you can pay for 1 full block and have 299 blocks of sutff you clear.

If you maybe pre-cached a number of block templates this issue would be fixed.

@JeremyRubin

If you maybe pre-cached a number of block templates this issue would be fixed.

I am suggesting something like that. You're right that just keeping a single most-profitable block template isn't sufficient. What do miners do today? I would assume they already have a much more sophisticated model of building blocks and mempool inclusion than normal nodes do. Do they not?

Relay rules, normal node mempool inclusion rules, and miner mempool inclusion rules could theoretically all have different rules. In order to actually maximize miner revenue, this is what we would do I think:

1. Relay rules - Nodes should relay anything that might increase miner revenue. By "might" I mean that nodes would be aware of when they might not have full knowledge and should be permissive whenever they don't know for sure that the replacement wouldn't increase miner revenue.
2. Normal node mempool inclusion rules - Nodes should only include things in their mempool if they think is more likely than not to to increase miner revenue.
3. Miner mempool inclusion rules - Miners should attempt to construct all future blocks from the mempool they have, and if adding a transaction into their mempool requires removing another one, they should only do that if the new set of all future blocks created from that contains more fees (a higher fee-rate per block or by some other appropriate metric), or some approximation of that if its too expensive to do this for every transaction. There should be consideration around when to keep around multiple conflicting transaction packages to compare against eachother. Miner mempool inclusion rules can be substantially more complex and expensive than normal mempool inclusion rules, because miners have a lot more resources to work with and a lot more on the line that makes the expense and complexity worth it.

I think actually doing rule 1 would probably lead to a DOS vector since an attacker could simply send the same transaction over and over again that they know isn't going to be included in a node's mempool but will be relayed. So really we kind of need normal node relay rules and normal node inclusion rules to match (or at least the rule needs to be: "only relay if you also include in your mempool" - theoretically a rule to add to the mempool but not relay is probably ok). But miner mempool inclusion rules can be completely different rather safely I think.

As an example, a rule for miner mempool inclusion that keeps around both the highest fee-rate replacement package and the package with the highest absolute fee would solve the flushing attack you described, even if normal nodes only include and relay higher fee-rate transactions in their mempool. Not sure what the consequences would be of such a simple ruleset for miners, but my point is that building the best blocks from relayed transaction should be left to miners, and while of course its important to consider the consequences of a specific ruleset on what miners are likely to use as inclusion rules, I don't think anything proposed would lead to much significant divergence (in node mempools vs miner mempools) unless an attacker is willing to pay quite a bit to do the kinds of largescale mempool manipulation like the flushing attack you presented.

Hi Gloria, replying to your comment from the dev mailing list since it primarily replies to my comment in the thread above.

First of all, I did a lot of thinking about this and came up with my own imperfect relay/mempool ruleset which more or less fails to achieve the goal I had of a limited (eg 3 to 1) worst case spam ratio with the simplicity I was advocating for. So below is my direct replies to you, which I'll follow by a separate comment with this imperfect ruleset. Hopefully there are some useful ideas in there even if they aren't quite good enough to be actually implemented for bitcoin. My conclusion after all this thinking is that the absolute feerate rule is harder to get rid of safely than I thought, and that perhaps we should keep it and instead implement sponsor transactions as Jeremy Rubin suggested to fix the pinning problem.

 In either case, we would want our mining algorithm to result in block templates that are as close as possible to perfectly incentive compatibile.
The attempt to match policy with miner inclusion rules is deliberate and necessary.
Fundamentally, I believe default mempool policy .. should be as close to the mining code as possible.

I think it would be very helpful to clarify what specifically you mean by "as close as possible to perfectly incentive compatible". Surely you don't mean as close as we can technically get at all costs, right? Certainly I agree, in an ideal world, both miners and nodes would have perfect code and more than enough machine resources to always have the most optimum block templates on hand at all times. But it seems to me that there are trade offs that either must or should be made here, and I'm wondering: what trade offs do you consider worth reducing "perfect" incentive compatibility for?

Miner incentives are such that they work on margins - margins likely to come ever slimmer as time goes on. In the long run, miners will take any advantage they can get in capturing fees. At the same time, the only way to ensure normal nodes have the same mempools as miners is for them to be tuned to capture maximum fees (I believe the terminology you used was "incentive compatible"). Because of these two things, if normal bitcoin nodes aren't maximally optimal, miners will use a different algorithm for their mempools than normal nodes. Do you agree?

At the same time, miners have much greater incentive than normal nodes to optimize how well their mempools can capture fees. Miners would be willing to have much larger mempools, with much larger more complex indecies, and willing to manage it with much more processing power than a normal node would be able to. This makes it inevitable that miner mempools will be divergent from the mempools of normal nodes to some degree. Do you agree that's the case as well?

If one of your goals is to minimize the incentive for out-of-band mechanisms to relay transactions to miners, then rules like "the ancestor score of the replacement must be X% higher", "if the original transaction is top of the mempool, require more constraints", or "abosolute fees must either increase or the transaction must decrease in size" are all contrary to that goal of incentive compatibility. All of those add further incentives for out of band relay.

Otherwise, node A's mempool is not very useful - their fee estimation is flawed

Even if A's mempool operates identically to a miner's, the fact that their mempool is 1/300th the size already makes their fee estimation flawed. I'd argue that the difference in memory allocation in your example is far more significant than eg a mempool protocol that has rule 3 vs one that doesn't. Regardless, a flawed mempool doesn't necessarily mean that node, or a network of such nodes would have significant problems. I'd have to see more analysis to be convinced that fee estimation would be significantly inaccurate, even in this example. 

It would be very suboptimal if the mining code was ancestor package-based (i.e. supports CPFP), but the mempool policy only cared about individual feerate

I agree that such a thing wouldn't be great. I'd have to see some more in depth analysis of this to really be convinced of the magnitude of how suboptimal it is, but I definitely agree that there are good reasons to make node relay/mempool rules more optimal and match mining mempool operations whenever feasible.

Package relay allows us to start thinking about ancestor packages immediately when evaluating transactions for submission to the mempool.

I agree, I'm very much in support of your package relay work.

Rule 3 and 4 are the feerate relay rules.

Rule 4 is the feerate relay rule. Rule 3 is the abosolute fee rule. Am I misunderstanding you?

Removing Rule 3 means allowing recycled fees, so new transactions are not necessarily "paying" anything.

What do you mean "recycled fees"? When I said "the spam is paid for", I was saying that the original (now replaced) transaction paid enough fees to pay for future spam. What do you think the flaw in my logic is in my example which I started with "Consider the following type of spam."?

My next comment will go into a hypothetical relay/mempool ruleset and think through consequences of it.

I'd like to share a modified set of rules to what t-bast proposed above. I think on its own its insufficient, but perhaps there are useful ideas in here. The ruleset:

A: In order for a package to be accepted into the mempool when there is a conflicting package (or subtree), the feerate of the new package must be higher than the feerates of all conflicting packages (or subtrees) by at least the minimum relay feerate.

B: When a package is replaced in the mempool by a conflicting package, that conflicting package replacing it must maintain a descendant-feerate of at least the feerate of the replaced package up to a descendant size of the replaced package plus the minimum relay feerate. Descendant-feerate of a package means the average feerate of the package and any tacked on children/descendants.

C: Conflicting packages will be relayed no closer together than 200 seconds. Eg there is a minimum cooldown between relaying conflicting packages, and only the highest feerate package received during a cooldown period will be relayed.

D: When a package is evicted by a higher feerate package, any subtrees of that package that don't conflict with the package replacing them are separated into smaller packages and evaluated for mempool inclusion on their own separate merit. (Note that this rule is not very important to the discussion, I just thought it would reduce retransmitted data).

E: Nodes can keep multiple conflicting packages in their mempool. Whether to keep lower feerate transactions (rather than dropping them when a higher feerate one comes in) depends on some analysis of the mempool that can determine an expected value of that transaction by predicting the likelihood that lower-feerate package will be profitable to mine and multiplying that by its feerate.

To give an example of rule B, if a 2000 vb package with a 5 sats/vb feerate is in the mempool and there's a 1 sat/vb minimum relay fee, that would mean that a new conflicting package must have 6 sats/vb, and any descendants tacked onto that new package after being added to the mempool (whether replacing the original or not) must have a high enough feerate to maintain a 6 sats/vb feerate.

Rule E is the most potentially complex and expensive, but it need not be perfect. Miners can innovate on this and come up with ways of eking out every last sat of fees, while nodes can keep it much more simple and lightweight. But the idea is that if you can find an accurate probability a transaction/package will be included, you can come up with an accurate expected value for that transaction.

To be more specific about the kind of thing I'm talking about in rule E above, here's some hypothetical pseudo code:

probability_of_being_mined = calculate_probability_of_being_mined(package, mempool)
expected_value = probability_of_being_mined * package.feerate

def calculate_probability_of_being_mined(package, mempool): 
  min_probability = .001
  curHeight = 0, probability = 0, lastDelta = Infinity
  while lastDelta > min_probability:
    lastDelta = probability_mined_in_block(curHeight, package, mempool)
    probability += lastDelta
    curHeight++

# Returns the probability the `package` will be mined at `height` blocks passed the next block. 
def probability_mined_in_block(height, package, mempool):
  next_block_without_package = get_block(mempool, height)
  min_bump_fee_rate = min_fee_rate_for_bytes(next_block_without_package, package.bytes)
  if height == 0 and min_bump_fee_rate > package.fee_rate:
    return 0
  else:
    conflicting_probabilty = calculate_conflicting_probability(mempool, package, height)
    independent_probability = 1 - probability_of_receiving_higher_feerate_transaction_bytes(package.fee_rate, package.bytes, height)
    return independent_probability * (1 - conflicting_probabilty)

# Returns the probability that a higher-feerate conflicting transaction/package will be mined.
def calculate_conflicting_probability(mempool, package, height):
  higher_feerate_packages = mempool.get_higher_feerate_packages(package)
  probability = 0
  for p in higher_feerate_packages:
    probability += calculate_probability_of_being_mined(p, mempool)
  return probability

# Returns the last block created if `height` number of blocks are created from the transactions in the `mempool`.
def get_block(mempool, height):
  ...

# Returns the fee rate that a `bytes` sized package would have to have to bump the bottom `bytes` amount of
# transactions from the `block`.
def min_fee_rate_for_bytes(block, bytes):
  ...

# Returns the probability of receiving at least `bytes` amount of transaction data with a higher average feerate than `fee_rate` in the time it takes to mine `num_blocks` number of blocks.
def probability_of_receiving_feerate_transaction_bytes(fee_rate, bytes, num_blocks):
  ...

The above is pretty rough, and some functions are left unimplemented, but that's the general idea. There's a lot of potential complication and heuristics that could be done in probability_of_receiving_feerate_transaction_bytes. Maybe this could be relatively static by assuming some general set of probabilities for transactions of various sizes, or maybe it would be more sophisticated and actually keep track of recent transactions and build some kind of predictive index that updates to what has been added to the mempool recently (today, this week, this month, etc).

This treats a block at a height H as basically a single block of size avgBlockSize*H and ignores the "knapsacky" complexities miners need to consider when actually building a block template. My gut feeling is that an inaccuracy this would introduce would either be insignificant, or could be made insignificant with some simple correcting tweak. Especially considering that miners may often have a slightly different mempool than normal nodes, the edge cases around packing a block to full capacity seem unlikely to be accurate no matter how you attempt it. But again, that's just a gut feeling.

So how would this handle the RBF spam attack Gloria mentioned? Well, rule C would limit the frequency of spam to on average 3 rounds every block. Rules A and B would mean that any replacement transactions must pay a higher fee than the originals.

It also solves Jeremy's flooding attack.

I must admit that it was harder to come up with rules that seem to plausibly close the loops on spam than I had expected. Even with the above rules, there is the following spam possibility:

Some transactor regularly broadcasts a transaction with a low feerate and then attaches many children. Then that same transactor broadcasts a single transaction with a slightly higher feerate than the original. This replaces a potentially arbitrarily large descendancy tree with a potentially minimally sized transaction. This could mean a spam to transaction ratio of unbounded size (or a size bounded only by nodes' mempool size). There is also the similar spam possibility of: send a large low feerate transaction, replace it with a small slightly-higher feerate transaction. Neither of these are replacement spam exactly, the spam is in the original transaction. But its of course relevant since replacement causes the original to become spam.

How could this be solved without reintroducing the absolute feerate rule (and associated pinning issues)?

One idea would be to gradually increase the feerate requirements for descendant transactions and larger. Ie require a higher minimum feerate for "deeper" bytes. For example, the minimum feerate could be raised by 150% for each byte "depth" multiple of 200 (so a 200 byte or less transaction would have a min 1 sat/vb feerate, an 800 byte tx would need at least 1.5625 sat/vb, a 3200 byte tx would need 3.05 sats/vb etc. This would also apply to attaching any descendants onto a transaction, where its depth at the deepest (from all toplevel unconfirmed transactions it requires) is how the necessary min fee is calculated. This way, you could always attach more children or descendants to transactions, but it would cost more and more if you're attaching a lot. This would also affect a replacing transaction, where that transaction would have to beat the feerate of that whole tree its replacing.

Another idea would be to only do something like that last part, and require a replacement transaction to pay extra for the more bytes its replacing, but not as much extra as the entire absolute fee of what its replacing.

Thinking about all this complication and imperfect solutions makes me think that perhaps it would be best to leave the absolute feerate rule in after all, and rely on Jeremy Rubin's sponsor transactions to solve the issue of pinning.