Skip to content

Instantly share code, notes, and snippets.

@glozow
Last active March 22, 2024 08:51
Show Gist options
  • Save glozow/25d9662c52453bd08b4b4b1d3783b9ff to your computer and use it in GitHub Desktop.
Save glozow/25d9662c52453bd08b4b4b1d3783b9ff to your computer and use it in GitHub Desktop.

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.

@sdaftuar
Copy link

I think there is another category of policy changes to eliminate RBF pinning that we're overlooking -- namely, signals we can use to not relay low-feerate children in the first place. I believe @gmaxwell was the one who originally suggested an approach like this:

  • Interpret some bit in a transaction that means, when set, that the user creating the transaction plans to RBF it later.
  • If the bit is set, then it becomes incentive compatible for nodes receiving the transaction to not relay child transactions unless doing so would cause the transaction to be confirmed very soon (for some definition of very soon, maybe next block or two).

This would give transaction creators a mechanism to designate their transactions as immune to transaction-pinning. This allows us to leave the RBF rule of absolute-fee-in-the-mempool-going-up in place, so that we don't open the door to free relay attacks.

The downside to this approach is that estimation of what is likely to be confirmed soon is not a precise notion, so it's messy. But I think it's the most incentive-compatible and DoS-resistant design I've heard.

@glozow
Copy link
Author

glozow commented Jan 28, 2022

Interpret some bit in a transaction that means, when set, that the user creating the transaction plans to RBF it later.
If the bit is set, then it becomes incentive compatible for nodes receiving the transaction to not relay child transactions unless doing so would cause the transaction to be confirmed very soon (for some definition of very soon, maybe next block or two).

That's an interesting idea. But are we sure this is incentive-compatible, given that this policy would reject perfectly valid transactions with a decent feerate?

@sdaftuar
Copy link

Well, I believe it's not incentive incompatible, in the same sense as a bunch of other policy rules that we have which might cause a node to not accept a "perfectly valid" transaction that pays a high feerate. For instance, compare this proposed rule with the rules we have around package size or package count limits (arguably the descendant limit is the thorniest rule, as right now we can reject a transaction with just one unconfirmed ancestor, if that ancestor already has 25 descendants -- even if the new transaction has an arbitrarily high feerate).

Of course, arguing that this is less bad than other stuff we do is not completely satisfying. I think the way I look at this is that (a) transaction chains are inherently risky for propagation (and I don't see any way of making that as reliable as the rules around transactions which have no unconfirmed parents), and (b) users at some level will adapt to reasonable anti-DoS logic that we put in, as long as there is no fundamental reason for users engaging in the behavior we're trying to deter.

In this case, we're trying to deter relaying low-fee children of transactions that we expect will eventually get RBF'ed to appear in a soon-to-happen block. Whatever economic activity is reflected in the child transaction will likely take place anyway, after that occurs (and if not, because the same economic actor is in control of both transactions, then we are exactly deterring the behavior we want to deter, of not allowing someone to replace a bigger size and higher fee transaction with a lower fee but higher feerate transaction later, which is what opens us up to bandwidth DoS).

We would have to pick a threshold for what "soon to confirm" means, and if we pick it too big then the pinning door is still open, and if we pick it too small then we might break legitimate CPFP wallet behaviors. And it's messy to have fee estimation effectively embedded in transaction relay policy; it's also not clear to me what effect this has on network relay behavior as policy rules change over time, which I think could add yet another reason in the future why transaction chains might continue to propagate poorly, at least when users are setting this proposed flag. But the virtue is that this would be a new opt-in policy, so if it's not useful for users presumably people would just not use it.

I also don't know if wallet authors want a behavior like this; honestly I don't know how much transaction pinning still bothers people -- I'm guessing it still does, but if we wanted to pursue a proposal like this I think the right thing to do would be to poll the ecosystem to see if this is a policy that would work for what users are looking for.

@instagibbs
Copy link

instagibbs commented Jan 29, 2022

Interpret some bit in a transaction that means, when set, that the user creating the transaction plans to RBF it later.

Just to be clear this is only applicable to(not) removing rule #3 and #4, yes?

This solution sounds a bit like an ad hoc way to punt the solution to wallet devs, since it will be up to them to figure out when they want to use this bit or not(unlike signaling rbf which pretty much every advanced wallet will do).

honestly I don't know how much transaction pinning still bothers people

This demand for not getting stuck will likely rise and fall with mempool congestion which has been quite low for the last year or so. I'd rather we keep searching for something a bit less ad hoc if possible.

That said, I think the "figure out what is top N blocks of mempool and what is not" will be common infra to work towards?

@sdaftuar
Copy link

Just to be clear this is only applicable to(not) removing rule #3 and #4, yes?

Yeah, this is focused on coming up with a solution for the effect of rule #3 (having to pay for the entire fee of all the replaced transactions).

This solution sounds a bit like an ad hoc way to punt the solution to wallet devs, since it will be up to them to figure out when they want to use this bit or not(unlike signaling rbf which pretty much every advanced wallet will do).

Yeah I guess that's the kind of feedback I'd be interested in hearing. It seems to me like the default for a lot of wallets might be to always use this bit for transactions, because if you think it's your job to put a high enough fee on a transaction that you're creating in order for it to be confirmed (ie your recipient expects that of you), then why do you care if your recipient can't use the output until the transaction is confirmed? The only things that can happen are either (a) they CPFP it so that it confirms (yay) or (b) they chain some low fee junk that makes it harder for you to RBF or CPFP it yourself (eg due to the descendant rule). This proposal allows for outcome (a), while in theory preventing (b).

I think it's kind of natural to have a way to opt-out of transactions being chained in the mempool to yours. By itself, that would likely be too dramatic a policy change to introduce now, because it would prevent legitimate CPFP use cases (and the resulting miner incentives for wanting to accept such child transactions), so this proposal would still allow for those use cases by allowing children that would result in the package being confirmed soon.

(If we had a blank slate, I think a mempol policy rule that would not permit unconfirmed children if some bit in a transaction is set would be a pretty reasonable thing to design in from the beginning. Chains of unconfirmed transactions add complexity and wanting to avoid them by default seems like a good idea to me.)

But maybe there are other problems that wallet authors would have with this that I'm not thinking of. I do think this would satisfy the lightning use cases just fine, as I understand them, at least assuming we are able to reasonably calculate the "soon to confirm" criteria that would be in place.

@achow101
Copy link

achow101 commented Feb 2, 2022

Interpret some bit in a transaction that means, when set, that the user creating the transaction plans to RBF it
If the bit is set, then it becomes incentive compatible for nodes receiving the transaction to not relay child transactions unless doing so would cause the transaction to be confirmed very soon (for some definition of very soon, maybe next block or two).

I feel like in practice this bit would end up either almost never used, or almost always used. It sounds a bit difficult to determine when the right time to set that bit would be, so it would be never. Or it would always be set because we want to be able to RBF every transaction. I think it is not useful in either case.

@glozow
Copy link
Author

glozow commented Feb 7, 2022

This solution sounds a bit like an ad hoc way to punt the solution to wallet devs, since it will be up to them to figure out when they want to use this bit or not(unlike signaling rbf which pretty much every advanced wallet will do).

Yeah I guess that's the kind of feedback I'd be interested in hearing. It seems to me like the default for a lot of wallets might be to always use this bit for transactions, because if you think it's your job to put a high enough fee on a transaction that you're creating in order for it to be confirmed (ie your recipient expects that of you), then why do you care if your recipient can't use the output until the transaction is confirmed? The only things that can happen are either (a) they CPFP it so that it confirms (yay) or (b) they chain some low fee junk that makes it harder for you to RBF or CPFP it yourself (eg due to the descendant rule). This proposal allows for outcome (a), while in theory preventing (b).

I feel like in practice this bit would end up either almost never used, or almost always used. It sounds a bit difficult to determine when the right time to set that bit would be, so it would be never. Or it would always be set because we want to be able to RBF every transaction. I think it is not useful in either case.

I'm not a wallet dev, but I'd look at this bit as "if I use this signal, I promise not to spend any outputs from this transaction unless I want to pay a huge fee." On the receiving side, it also means "if somebody sends me a payment with this signal in it, I should consider it unspendable unless I'm going to use a huge feerate," though this is probably less bad since I'd probably mark unconfirmed external outputs as unsafe anyway.

This might be inconvenient, since it requires extra logic in managing the wallet's UTXO pool. If I make a payment to somebody who wants the signal on, this also means I can't spend the change output unless I use a really high feerate. I imagine that wallets/merchants will require users "please keep this signal off on your payments" for backwards compatibility until they have implemented this logic.

On the other hand, maybe this would be exactly perfect for LN to use as their default: flip a signal on commitment transactions so that the only possible descendants are high feerate, legitimate fee bumps. We might even be able to get rid of the carve out rule in this case, since the descendant limit cannot be wasted.

@instagibbs
Copy link

I'm not a wallet dev, but I'd look at this bit as "if I use this signal, I promise not to spend any outputs from this transaction unless I want to pay a huge fee.

Yes it's clear what the intention is, it's just that myself and achow(both with wallet dev experience on a number of platforms) aren't quite sure when this would should be used or not from a practical engineering perspective.

Perhaps "this gets rid of the careve out rule" is a good enough reason and can be used in those specific cases, and it doesn't hurt anyone else while something better is worked on?

@sdaftuar
Copy link

sdaftuar commented Feb 7, 2022

@achow101 @instagibbs Regarding the more general wallet use cases, do either of you have a proposal that you like for how RBF ought to work? From reading the mailing list thread, it seems to me that some of the things people seem to want (being able to chain a bunch of their own low feerate stuff off their change outputs, only to replace them later with a smaller high feerate replacement) are exactly the thing I think we need to prevent. Fundamentally it doesn't make sense to me that the network would serve as a storage medium for wallets to create transactions, and then re-optimize them later -- or at least, not without non-trivial cost (because the alternative is a DoS-vector on the network's resources).

For wallets that are typically online (perhaps Bitcoin Core's wallet might be an example), might it make sense to have the wallet do the job of doing more active management of when to try to relay a transaction, so that we don't relay low feerate transactions whenever they are created, but instead wait until feerates on the network may have dropped to the point that they are likely to confirm soon? This strategy would allow a wallet user to continuously re-optimize its own low feerate transactions, and have total freedom to replace them, chain things, replace the chain, etc since nothing has been broadcast yet. And once the user either wants to RBF some transaction or CPFP it to the point that it might get mined, or once feerates come down on the network, the wallet could then relay it to everyone with the expectation that it would get confirmed soon (and so no further RBF optimizations should be necessary).

The downside is needing to be online to broadcast opportunistically, and any UX confusion from not having a txid to show someone if they want to see it in their own mempools (though, of course, users should be able to give each other transactions without broadcasting to everyone on the network!).

@instagibbs
Copy link

instagibbs commented Feb 7, 2022

If we restrict unconfirmed spends to only things that explicitly look like CPFP, then I'd expect a wallet to do something like:

  1. Make transaction from confirmed outputs at given feerate to pay
  2. RBF (1) as required if it isn't being confirmed
  3. If we can't RBF for whatever reason, CPFP change with a one input one output transaction to self
  4. RBF the CPFP as needed, since it my not have entered mempools of relayers/miners nodes due to new rule

The main UX drawback to me would be the requirement to have a very nice UTXO pool and/or coin selection research(?) to make more than one payment in a short sequence, which could be solved by sneaking spends of unconfirmed at high feerate(CPFP), or a much larger UI overhaul, or RBF'ing payout transactions, with all the associated complexity to avoid duplicate payouts.

I think all of these design discussions are quite well trodden, the blocker is actual engineering of these more complex wallet setups that haven't actually arrived due to implementation complexity?

@sdaftuar
Copy link

sdaftuar commented Feb 8, 2022

An alternative idea, from talking to @TheBlueMatt today: we could set a bit in a transaction that means "do not accept more than X vbytes worth of descendants into the mempool that depend on this one, because this may be RBF'ed in the future".

Values of X could be something like twice the original transaction's vsize (maybe with a floor -- 1000 vbytes? 5000? ), or some other smallish value.

The point of this would be to bound the RBF cost to the original transactor, as the issue with RBF pinning is that a package's size can be 1000 times bigger than a typical transaction, so if we can bound that to 2x the size of the original transaction (or something similarly small), the RBF cost when you're paying for descendants seems much more reasonable.

This approach would not require making any feerate predictions (which is nice), but also may suffer from the problem of wallets not knowing when to use it... But if this at least makes it easier for some use cases, maybe it's still forward progress?

@glozow
Copy link
Author

glozow commented Feb 14, 2022

An alternative idea, from talking to @TheBlueMatt today: we could set a bit in a transaction that means "do not accept more than X vbytes worth of descendants into the mempool that depend on this one, because this may be RBF'ed in the future".

How would you imagine this working with anchor outputs (or other transactions where counterparties each have 1 output)? If one counterparty tacks on an X-vbyte child, then the other counterparty can no longer CPFP - is this a problem? Though I guess in the LN scenario they could just RBF when there's package relay.

@TheBlueMatt
Copy link

If one counterparty tacks on an X-vbyte child, then the other counterparty can no longer CPFP - is this a problem?

In today's lightning (with asymmetric commitments) you generally never actually care about being able to tack on additional fee to a transaction already in the mempool - in order to do so you'd need to know the state of "the" mempool and know that your counterparty's commitment transaction is there, and which one, and then go tack on the extra fee. If you just broadcast your own latest state, however, you don't need to go look at the mempool, so you'll basically always do that, package-replacing the whole alternate state.

That said, there are other protocols where the commitments are symmetric so you'd want to be able to do this (eg eltoo). In that context, we'd probably want something like the carve-out to apply here.

Though I guess in the LN scenario they could just RBF when there's package relay.

Yea, that.

@glozow
Copy link
Author

glozow commented Feb 14, 2022

In today's lightning (with asymmetric commitments) you generally never actually care about being able to tack on additional fee to a transaction already in the mempool - in order to do so you'd need to know the state of "the" mempool and know that your counterparty's commitment transaction is there, and which one, and then go tack on the extra fee. If you just broadcast your own latest state, however, you don't need to go look at the mempool, so you'll basically always do that, package-replacing the whole alternate state.

Makes sense. So the proposal is: we interpret some nth bit of nSequence that means "this transaction won't have more than X vbytes of descendants" where X = max(1000, vsizeof(tx)) or something. We also add package RBF with the current rules + package relay. You flip the descendant-limit bit on all commitment transactions. You broadcast your channel closes with the knowledge that any conflicting commitment transactions won't have more than X vbytes of descendants to replace.

That said, there are other protocols where the commitments are symmetric so you'd want to be able to do this (eg eltoo). In that context, we'd probably want something like the carve-out to apply here.

Would it make sense to have the limit per-output? Like, any descendant chain from some output needs to be <= the size of this transaction.

@TheBlueMatt
Copy link

Makes sense. So the proposal is: ...

Yes.

Would it make sense to have the limit per-output? Like, any descendant chain from some output needs to be <= the size of this transaction.

Yea, that's one option. We could also keep the current carve-out logic explicitly and say "you can violate the descendent limits by exactly X as long as...$EXISTING_CARVE_OUT_RULE".

@glozow
Copy link
Author

glozow commented Feb 15, 2022

@TheBlueMatt @sdaftuar I've implemented this proposal (I called it "user-elected descendant limits") here. It's extremely simple in terms of code. I'd be interested to hear if other LN developers find this sufficient for their needs? If so, we have something that works well enough to unblock package RBF and can continue moving forward.

Also: I arbitrarily allocated the 30th bit of nSequence, though I'm not entirely sure if this is the right way to go. Our functional tests, for example, set this bit by default since they use the maximum RBF-signaling value - I imagine there could be some wallets out there doing the same, or applications applying some other meaning to this bit.

@instagibbs
Copy link

instagibbs commented Feb 16, 2022

fwiw I think the latest proposal is a lot less hacky and possibly usable as a feature by more "normal" wallets. Will think more about the usage and scenarios that still wouldn't be covered with this rule + carveout + package RBF

@TheBlueMatt
Copy link

Ah, thinking about it more you may be right, this could work for eltoo even without the carve-out, because the commitment transaction is signed by both counterparties with the flag set.

@t-bast
Copy link

t-bast commented Feb 28, 2022

While I think being able to opt-in to say "I won't add a lot of descendants" is a good thing, I'm afraid it won't be a completely satisfying short-term solution because it prevents you from spending your own change output. If you're producing a big change output, that's some wasted capital allocation (if you're not targeting a confirmation the next few blocks).

To work around that you would have to interleave another transaction to first split your big utxo before using it with the nSequence set, which waste on-chain space...

@TheBlueMatt
Copy link

Yes, its definitely limiting, and far from ideal, but I'm not really sure that there is another workable solution currently on the table at all.

@t-bast
Copy link

t-bast commented Mar 1, 2022

Here is the outcome of the brainstorming session we had yesterday with a few people. Mistakes are 100% my own if that doesn't correctly depict what was proposed.

What do you think about the following proposed set of rules? I'm curious to learn what I'm still missing if you believe this isn't an acceptable set of rules.

#1: The ancestor feerate of the replacement transaction must be N% higher than the feerate of the replaced transactions
#2: Miners keep mining the most profitable block template, regardless of replacements
#3: Mempool replacements are delayed and rate-limited to once every M seconds or minutes.

More details on #3: if you receive txB that conflicts with txA and passes rule #1 quickly after adding txA to your mempool, you don't apply txB yet. You keep it in a "replacement queue" and will apply it and relay it after some time. If you receive another transaction txC that is a better replacement than txB (again, according to rule #1), you simply drop txB and will instead apply txC once the timer has elapsed. I believe this addresses pinning concerns while limiting network DoS. This "replacement queue" may in the worst case use as much RAM as your mempool, but not more since you only keep the best replacement candidate (please verify that statement, I believe it is correct but needs more scrutiny).

More details on #2: this is needed because rule #1 doesn't always maximize miners revenue. When blocks aren't full, a higher feerate package with lower absolute fee would pass rule #1 but would reduce miners revenue. However, miners easily detect this because the new block template gives them less fees than the previous one, so they simply continue mining the previous block template. Since blocks aren't full, all transactions will be included in the next block, which guarantees that there's no risk of pinning either (the transaction that will confirm will be the old version, not the replacement, but that is perfectly fine as long as something confirms).

This would provide a very simple interface to wallets and applications: just choose a feerate based on your feerate estimator, and if your replacement works, then your transaction has reached that desired feerate. If your replacement is rejected, that means the mempool already contains a package that has that feerate (probably thanks to high-feerate descendants) so it's as likely to be included in a block.

The combination of rule #3 and the fact that a % increase creates an exponential blow-up should address DoS concerns, and makes it quickly very costly for an attacker to try to pin your transactions.

There is a trade-off regarding miner revenue because we only consider the next block in #2, whereas a feerate increase may entail an absolute fee decrease in block 1 + p. However, I believe that this is a case of trying to predict an unpredictable future: such a replacement will likely be followed by new descendant transactions which will ensure that there is no absolute fee decrease. However, we can't know for sure because we can't predict the future.

@t-bast
Copy link

t-bast commented Mar 1, 2022

Actually @JeremyRubin explained to me that replacement strategies based on feerate only are subject to the following mempool siphoning attack:

  • the attacker sends a lot of large, high feerate transactions to fill the top of the mempool and get transactions from other people to be evicted
  • then they replace those transactions with higher feerate but much smaller transactions

Everyone's mempool is now almost empty, with transactions that pay a low absolute fee, which isn't miner incentive compatible at all.
I'm not sure how to address that issue without reintroducing pinning, but at least I learned something about designing mempool policies!

@JeremyRubin
Copy link

I dont think you can use an nSequence bit without a new transaction version & the patches to lock down the nSequence values currently allowed under standardness rules.

@sdaftuar
Copy link

sdaftuar commented Mar 1, 2022

FYI I think your proposed rules 2 and 3 are also problematic, independently of the problems with rule 1:

#2: Miners keep mining the most profitable block template, regardless of replacements
More details on #2: this is needed because rule #1 doesn't always maximize miners revenue. When blocks aren't full, a higher feerate package with lower absolute fee would pass rule #1 but would reduce miners revenue. However, miners easily detect this because the new block template gives them less fees than the previous one, so they simply continue mining the previous block template. Since blocks aren't full, all transactions will be included in the next block, which guarantees that there's no risk of pinning either (the transaction that will confirm will be the old version, not the replacement, but that is perfectly fine as long as something confirms).

First, 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.

More fundamentally though the mempool's most important function is to serve as a data structure to support mining, by providing a consistent set of transactions to construct blocks from. If you propose changing the mempool in a way that no longer supports that function, then I think there's a lot more to flesh out around exactly how mining would work. For example, in your proposed algorithm, suppose we're in a situation where a replacement has lowered the next-block-fee, and so we fallback on the mining algorithm somehow returning the last template it produced, instead of the next one it would produce from the mempool. What happens when some unrelated high fee transaction arrives in the mempool, bringing up the fee in the next block template produced from the mempool to be above the cached template? It's possible that using the cached template's transactions + the new unrelated high fee transaction would produce the highest total fee, but without a mempool-like datastructure to track that, that would go undetected.

#3: Mempool replacements are delayed and rate-limited to once every M seconds or minutes.
More details on #3: if you receive txB that conflicts with txA and passes rule #1 quickly after adding txA to your mempool, you don't apply txB yet. You keep it in a "replacement queue" and will apply it and relay it after some time. If you receive another transaction txC that is a better replacement than txB (again, according to rule #1), you simply drop txB and will instead apply txC once the timer has elapsed. I believe this addresses pinning concerns while limiting network DoS. This "replacement queue" may in the worst case use as much RAM as your mempool, but not more since you only keep the best replacement candidate (please verify that statement, I believe it is correct but needs more scrutiny).

Here are some issues I see with this strategy:

  1. While txB is queued for acceptance, any other transaction that is added and chained on txA is basically going to get free relay, because eventually txB will get added and evict txA and all its descendants. (To be fair, this is mostly a problem with rule #1, which permits free relay too! But I think queued acceptance introduces its own unique design challenges.)

  2. If txB would replace multiple in-mempool transactions, then how do you keep track of things to even compare txB and txC? For example, it's possible that txB and txC could both cause txA to be replaced, yet txB and txC are both compatible with each other (consider the case where txA has two inputs, and txB conflicts with one and txC conflicts with the other; alternately, it's also possible that txB and txC could conflict with each other in ways that are not obvious from just looking at the two transactions directly -- for instance, suppose txB conflicts with an input of txC that is in the mempool now, but wasn't in the mempool when txB was added to the queue!). Keeping track of the bookkeeping for making determinations like this is exactly the job of the mempool, so relegating transactions like these to some other data structure requires implementing solutions for all the DoS issues that the mempool has... So in my view, we might as well just solve it in the mempool itself.

  3. What would you do with transactions that depend on txB that arrive while txB is in the queue? (I think that if your answer is anything other than "throw them away" you're basically saying we need two mempools; but throwing them away seems bad to me as well, because needing to download transactions more than once in order to get transactions to propagate successfully, in seemingly normal situations involving RBF, seems like a poor design as it wastes bandwidth and adds latency to getting the best transactions across the network.)

@glozow
Copy link
Author

glozow commented Mar 1, 2022

Have we considered just lowering the default descendant size limit to something like 50KvB or 20KvB? We could keep the ancestor limit the same (i.e. to allow batched fee-bumping).

@sdaftuar
Copy link

sdaftuar commented Mar 1, 2022

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.

@t-bast
Copy link

t-bast commented Mar 1, 2022

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

@fresheneesz
Copy link

fresheneesz commented Mar 10, 2022

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.

@JeremyRubin
Copy link

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.

@fresheneesz
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment