Further motivation:

(1) The restriction of only allowing confirmed UTXOs for funding a fee-bump doesn't necessarily help our mempool validation logic, but hurts users trying to fee-bump their transactions. 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 fee bump. Wallet developers also need to treat self-owned unconfirmed UTXOs as unusable for fee-bumping, which is an unnecessary complication.

(2) BIP125#2 can also be bypassed: @jnewbery recently pointed out to me that an attacker 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.

To illustrate, Example L shows how BIP125#2 can be bypassed in all cases where the replacement transaction has enough fees to be split into multiple transactions. Example L1 is blocked by BIP125#2 because C is not allowed to spend an output of B. The owner of transaction C can bypass BIP125#2 as shown in example L2. Simply create a 1-input 1-output transaction, C*, that spends the output from B, and replace it with C.

This might be a good hack for people who need to RBF transactions and only have unconfirmed UTXOs available, like scenario M, where we want to replace A (a 100vB transaction paying 1000sats), but our only UTXOs are in unconfirmed transactions B and C. We can simply create D*, an intermediary transaction spending the outputs we want from B and C, and then replace that with D. This just means that D needs to pay some additional fees for replacing D* (which can be at the mempool minimum feerate).

However, Example N shows how this strategy can cause us to accept an replacement transaction that is actually less economical to mine than the original. Assume all transactions have a vsize of 100vB. A user wants to replace A, which has an ancestor score of 10sat/vB, with transaction C. Suppose they want to spend an unconfirmed output from transaction B, which has an ancestor score of 1sat/vB (maybe their wallet doesn't have enough funds to provide a higher fee using only confirmed inputs). BIP125#2 prevents scenario N1, where the inclusion of another unconfirmed input means C has an ancestor score of 8sat/vB and thus less economical to mine than A. However, it does not prevent scenario M2, where the user splits off a 1-input 1-output transaction, C*, in order to be able to include the output from B. This causes us to incorrectly accept C (7.5sat/vB including its parent B) in favor of A (10sat/vB).

Again, credit to @jnewbery for this discovery.

(3) I believe package RBF requires removal of BIP125#2, (explained here if you're interested). I know this is not a super robust argument, but it would be a much better interface if the two sets of RBF rules are the same.

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #23711 (docs: RBF policy and mempool limit exemptions by glozow)
• #22867 (test: Extend test coverage of BIP125 and document confusing/inconsistent behavior by mjdietzx)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

@glozow @jnewbery If you think this discovery has safety implications, have you done a responsible disclosure of this defect not only to the maintainers of this project but also potentially affected ecosystem stakeholders e.g maintainers of other full-nodes implementations ?

Good finding! IIUC, the bypass trick relies on extending the set of replaced transactions with a 1 input/1 output "bridge" transaction spending a targeted new unconfirmed intput. A new replacement candidate tries to replace the bridge and original (the setConflicts computed L620). As HasNoNewUnconfirmed considers the parent set of iters_conflicting any parent of the bridge and original are qualified of old inputs and thus allowed to be spend by the replacement candidate. I think the bridge transaction can be extended to N new unconfirmed inputs within package limits ? The bypass trick isn't zero-cost as the Rule#4 penalty must still be paid.

I think this Rule#2 bypass doesn't present obvious safety implications for LN, even with "anchor output" channel type. If an adversary needs currently unconfirmed UTXOs to be used as fee-bumping ones to succeed an attack, she can waits to have them confirmed before to initiate any malicious operation. That's an adversary "first-move" advantage anyway. In a pinch, unconfirmed UTXOs could be used to increase the rate of attacks launched sequentially if the UTXOs resources are limited...

If you think this discovery has safety implications, have you done a responsible disclosure of this defect not only to the maintainers of this project but also potentially affected ecosystem stakeholders e.g maintainers of other full-nodes implementations ?

@ariard I didn't think this is a safety issue for Bitcoin nodes, just a limitation that we no longer have. The "trick" isn't completely cost-free and the replacement transaction still needs to be higher fees due to the other BIP125 rules, it's just lower priority for mining than the mempool code thinks it is. Worst case scenario is if the original transaction was going to be in the next block and the replacement transaction isn't. That's unfortunate for the miner of this block since they might lose a bit on fees depending on the next-highest feerate packages, and not incentive-compatible behavior, so I think we should fix this.

The disclosed fee decrease (good catch) is a breach against the fee-bumping protocol for Revault and really any other protocol that broadcasts ANYONECANPAY-signed inputs. Sure you can always re-RBF it but in the end we can't assume honest node to engage in (and win) a race for fee-bumping.

@darosior Attempting to summarize, please correct me if I'm misunderstanding: when a transaction has all inputs signed ANYONECANPAY and RBF opt-in, any attacker can create a replacement transaction by adding any input they want. Coupled with the strategy mentioned above, they can reduce the ancestor score of this transaction, thereby pinning it. You can re-RBF it, but might need to pay more fees. 😱

Coupled with the strategy mentioned above, they can reduce the ancestor score of this transaction, thereby pinning it

Yes.

You can re-RBF it, but might need to pay more fees. scream

Yes, and they can do that again and again (paying more fee at each iteration though so it's a limiting factor). Since nodes will accept any of the low-feerate package or the higher-feerate one it's a game of who will be able to connect to the miners' nodes and maintain their version of the package: at this game we can expect an attacker running a custom software has a much higher success probability than a honest watchtower trying to feebump.

I don't suppose it's reasonable to recommend opting out of RBF for now? In any case, I think we need to add this ancestor score checking before we try to do full RBF, since it would leave all ANYONECANPAY-signed transactions vulnerable to this pinning attack.

Concept ACK

@glozow @jnewbery If you think this discovery has safety implications, have you done a responsible disclosure of this defect not only to the maintainers of this project but also potentially affected ecosystem stakeholders e.g maintainers of other full-nodes implementations ?

@ariard I didn't think this is a safety issue for Bitcoin nodes, just slightly incentive-incompatible behavior. The trick isn't completely cost-free and the replacement transaction still needs to be higher fees due to the other BIP125 rules, it's just lower priority for mining than the mempool code thinks it is. Worst case scenario is if the original transaction was going to be in the next block and the replacement transaction isn't. That's unfortunate for the miner of this block since they might lose a bit on fees, and definitely incentive-incompatible mempool behavior, so I think we should fix this.

@glozow @ariard even if this doesn't involve any security issues we should inform others who are not following each pull request in this repository every day. This looks like an important bug which needs a fix. Although I am still trying to understand everything involved.

And thanks for the diagrams, they are helpful.

@glozow

For public records, before to open this PR, have you informed Bitcoin Core maintainers of your discovery yes or no ?

I think by the past this project have always been careful about leveling the field in the miners block race (e.g ASICBOOST) and I think defects or bugs in our mempool code could be silently exploited by a miner to gain an advantage on the rest of the ecosystem. Of course, I understand to miss a potential safety impact on the mining ecosystem. Really, no one has a complete overview of the base-layer threats model, without even mentioning the layers above.

A responsible disclosure in the Bitcoin ecosystem is a really complex or hard task. If you are not aware about it, I would invite you to read the informative pieces written by MIT DCI. Going further, as soon as we're talking about security disclosures it's a grey area. I believe it's not a matter of who is wrong or right as an individual contributor. Instead, I believe the leading principle should be to follow a process minimizing the risks of harm inflicted to Bitcoin stakeholders. Where "harm" should be interpreted in the large sense as negative consequences, especially when those consequences are significant and unjust.

Even if this software is released as an "experimental" digital currency, and that users should be fully-aware it's a FOSS project and we don't engage our responsibility as contributors, I think we should keep in mind that our acts could provoke irrecoverable disruptions in the life of real people, even indirectly or unintentionally.

I think that's why we should be careful. I hold the belief that communicating to a crypto-currency project maintainers a vulnerability is one piece of such harm-minimization process and helpful to fully assess the safety risks and what can be done to remedy. A lightweight bug could reveal itself as a serious vulnerability affecting far more users than the initial thoughts of the discoverer let it imagine. For sure, if you communicate a vulnerability to a project maintainers and they don't reply back or take any action to patch a vulnerability, I believe it's a good behavior to disclose it to the wider public, instead of letting propagate a false sense of security and safety-critical problems to worsen.

That said, we all know we're working in a highly-dynamic environment, that our resources are limited and that 100% of "security" certainty is a lure. And that's okay to do mistakes, as long as we're learning from then. From my experience working on Lightning, I can testify I've done few of them by lack of patience.

I think it's good to time to reflect on how we do security disclosures in this ecosystem, notably with having more and more funds backed by newer "L2" security models. I would say the "unseen" impact of this current breach on Revault is a good proof of that. Even if I think the project philosophy is fluctuating about what components are safety-critical and thus require special care, what we do when we find vulnerabilities send a strong signal towards downstream project maintainers if Bitcoin Core and the community around are reliable for their use-cases or not.

Further, let's remember, one of the most nasty bug in the recent years (CVE-2018-17144) have been discovered by a developer of another full-node implementation. Lacking considerations towards the safety and reliability of their projects is likely to damage their good-will and kindness to share back future vulnerabilities that they might discover first and also affecting us.

IMHO, those are good reasons to express high-standards of behaviors among us, as otherwise we might as a group pay the indelicacies of one contributor.

I think it's important to have a safety-first mindset to contribute to Bitcoin protocols development.

1. Policy is a per-node and per-miner decision. What they choose should never be a security concern to anyone else - if it is, the "someone else" has the security flaw, not the node/miner imposing the policy. The "something else" in question should be fixed regardless of what policy nodes/miners choose.
2. If policies were based on what is good for the network, Bitcoin Core wouldn't make blocks over ~300k. Rather, unfortunately the policy here has been what certain devs expect to make miners the most short-term profit at the expense of the rest of the network and long-term.

I don't think @glozow did anything wrong by opening this PR here.

@glozow For public records, before to open this PR, have you informed Bitcoin Core maintainers of your discovery yes or no ?

No, because this is not a security vulnerability or even a bug in Bitcoin Core. A disclosure that boils down to "if your transaction is signed with ANYONECANPAY and opts in to RBF, anyone can pay to RBF it. Our mempool evaluates its fees according to the rules specified in BIP125" is unnecessary.

Thank you for the education on disclosing security issues delicately. If I find an issue that could cause mempool resource exhaustion, deviation from p2p protocol or consensus, or acceptance of uneconomical replacements, I'll keep it in mind.

As described in the OP, this PR implements a TODO item documented in the code. Code review and testing is welcome.

@luke-jr

Sure, I think it's one stand to recommend users or downstream projects to minimize assumptions on node policies, as it's ultimately not (and can't be) uniform on the p2p network. But I would say it's another thinking when we find a defect or bug in our code behavior, of which correctness signaling is present (AFAICT bip125, including the rule 2, is present in doc/bips.md). Without going as far as safety implications, a mempool behavior bug might disrupt the availability of some bitcoin services providers or even alter their economic units, as this knowledge could constitute a competitive advantage. E.g being able to fee-bump your transactions thanks to unconfirmed inputs to deliver withdraws faster than your competitors.

As your second point seems to indicate, policies design philosophy is a subject of discussions among devs. Advocating my position, I think we should aim to guarantee a high quality of service to upper layers and downstream projects, aligned with Bitcoin principles. And aiming to this end, promote good software engineering practices such as documenting our transaction relay behavior (see #22806).

As the project philosophy is still fluctuating w.r.t if and how we should handle newer security models, I agree that @glozow isn't wrong by opening this PR.

@glozow

No, because this is not a security vulnerability or even a bug in Bitcoin Core. A disclosure that boils down to "if your transaction is signed with ANYONECANPAY and opts in to RBF, anyone can pay to RBF it. Our mempool evaluates its fees according to the rules specified in BIP125" is unnecessary.

Well, I think that qualifies as a breach of the fee-bumping protocol of any protocols that broadcasts ANYONECANPAY-signed inputs ? As of today, I would say we're lucky it's not deployed (yet) in production :)

But in the coming years, if we have billions of funds secured by assumptions around mempool behavior, I think it's better to have a more defined security process than failing in a really noisy ecosystem drama. Better safe than sorry :/

If I find an issue that could cause mempool resource exhaustion, deviation from p2p protocol or consensus, or acceptance of uneconomical replacements, I'll keep it in mind.

Yeah, even if you have an established security model well in-mind, the public perception of how you handle potentially security-sensitive information is another thing. The question of "Oh shit we can lose money that way ?" can turn quickly as a not-that-clear one in Bitcoin. E.g, before the 2013 LevelDB bug (CVE-2013-3220), it wasn't really in developers common knowledge that a database change could provoke a consensus failure. So sharing the information with project maintainers or other regular contributors is a way to protect your reputation in case of after-the-fact issues.

Overall, thanks to John and you for this discovery, please find more of them and Concept ACK on this PR.

User @prayank23 is having difficulty commenting on this PR for some reason, so I am relaying his comments/questions from IRC:

Two questions for PR author:

1. Unconfirmed UTXO are discouraged in Core. Does this PR change default behaviour? Context: [Feature Request] Enable CPFP via GUI bitcoin-core/gui#242
2. Why do you think it's not a bug if attacker can confirm a tx with less fee rate by replacing? It can be exploited if we had on chain DeFi but I am not sure what all projects are currently impacted

rebased and added documentation for our RBF policy + difference with BIP125

Rebased

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

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

Thanks for the review @sdaftuar!

If we want to fix the issue where a replacement transaction might have a worse mining score than some transactions it replaces, then I think the conservative thing to do would be to compare the ancestor score of the replacement transaction with the actual feerates of the conflicted transactions themselves (ie not the ancestor feerate of the conflicted transactions).

The rationale is that you never know if some sibling transaction might exist in the mempool that would cause the ancestors of a target transaction to be mined, allowing the target transaction to be considered using its own feerate (rather than being weighed down by low feerate parents).

My understanding is: When a future block template is built, a transaction's mining score may include none, some, or all of its current mempool ancestors, e.g. because of a high feerate sibling.
To ensure that our replacement transaction is not a worse mining candidate than the conflicting transactions in a conservative manner, we'll require worst-case replacement tx feerate >= best-case conflicting tx feerate for every conflicting tx (best-case meaning highest feerate, and worst-case meaning lowest feerate).

Since individual feerate always >= ancestor feerate for any tx, this means we require
replacement tx ancestor feerate >= conflicting tx individual feerate for every conflicting transaction.

Edit: It's not true that individual feerate always >= ancestor feerate. We'd require
replacement tx min(ancestor feerate, individual feerate) > conflicting tx max(ancestor feerate, individual feerate)

To clarify, we would need to do this comparison with every conflicting transaction and all their descendants (not just direct conflicts), since they may have high-feerate descendants? Or do we only consider directly conflicting transactions, and perhaps the other RBF rules are sufficient to ensure we are being incentive-compatible (based on this comment)?

If we compare with all conflicts, this could be too conservative, at least for package RBF. For example:

Alice (adversary) and Bob (honest) have a LN channel, where Alice has commitment tx A1, Bob has commitment tx B1.

Alice broadcasts A1 <- A2 <- A3, where A2 is a very large child of A1, and A3 is a very small child of A2.
A2 has a low feerate and A3 has an extremely high feerate. This package, as a whole, has a low ancestor feerate.

Bob broadcasts a package, B1 <- B2, where B2 is a fee-bumping child of B1.
Perhaps Bob's package is higher feerate than Alice's package, but since B2's ancestor feerate must be higher than A3's individual feerate, Bob's package is rejected.

===

I think the real question that we're trying to answer with the feerate checks is something like "are the fees expected to be paid in the next (N?) blocks higher or lower if we process this transaction", which is not very easy to answer with the tools we have at our disposal.

I suppose if N=1, we can just compare ancestor feerates? Only when N>1, the transaction's future mining score may be different from its current ancestor feerate.

<snip summary of block construction and feerate scores, which all sounds correct to me>

To clarify, we would need to do this comparison with every conflicting transaction and all their descendants (not just direct conflicts), since they may have high-feerate descendants? Or do we only consider directly conflicting transactions, and perhaps the other RBF rules are sufficient to ensure we are being incentive-compatible (based on this comment)?

So if we only compare ancestor feerates to the direct conflicts' actual feerates, then we might very well replace a transaction that would be included in the next block:

Consider a set of transactions: A1 <- A2 where A2 is a child of A1, and suppose that A1 is small and very low fee, and A2 is small and very high fee. We can do this so that (A1, A2) would be a candidate for inclusion in the next block.

Then construct a transaction B that conflicts with A1, and is much larger than A1 and A2 and pays a low feerate (and greater total fee than A1+A2). It could satisfy the RBF total fee requirement and the requirement that its ancestor feerate exceed A1's actual feerate, without being a candidate for inclusion in any blocks in the near future, even though (A1, A2) might already be in our set of transactions to include in the next block.

So that seems like it wouldn't be incentive compatible.

If we compare with all conflicts, this could be too conservative, at least for package RBF. For example:

Alice (adversary) and Bob (honest) have a LN channel, where Alice has commitment tx A1, Bob has commitment tx B1.

Alice broadcasts A1 <- A2 <- A3, where A2 is a very large child of A1, and A3 is a very small child of A2. A2 has a low feerate and A3 has an extremely high feerate. This package, as a whole, has a low ancestor feerate.

Bob broadcasts a package, B1 <- B2, where B2 is a fee-bumping child of B1. Perhaps Bob's package is higher feerate than Alice's package, but since B2's ancestor feerate must be higher than A3's individual feerate, Bob's package is rejected.

Thanks for bringing up a concrete example to consider. (I'm just taking it as an assumption that any other issues around package RBF have already been solved -- I haven't thought it all through in a while.). In this example, since A3 is very small and B2+B1 already have pay enough total fee to exceed A1+A2+A3, isn't it a pretty small economic difference to further require that B2 have an ancestor feerate greater than A3's actual feerate?

I think the underlying issue is that we may already want to be relaxing the total fee requirement somehow, because transaction pinning with our current RBF rules -- ie, requiring that B1+B2 actually pay more total fee than A1+A2+A3, even though that package is low value to miners -- has been a problem for some time, and I think people would like a solution to that. However it's a bit tough to consider what the RBF feerate requirements should be in the absence of a concrete proposal of what we might do differently for the total fees as well. (If we relaxed both, then I think it'd be easy to construct examples where miners are reducing their fees in the next block, which wouldn't be incentive compatible.)

From a practical perspective, it seems to me like we could "solve" the issues around incentive compatibility with our current RBF rules (along the lines of what I described above of requiring ancestor feerates to be greater than actual feerates of all transactions which would be replaced), and then later address the pinning problems. However, I don't know if this is actually good for the ecosystem as a whole, since other Bitcoin transaction creators might care a lot about the precise relay behavior here, so making multiple changes -- and particularly, making transaction replacement worse somehow in the interim by becoming more conservative -- might be pretty unwelcome. So maybe it would be better to craft a new proposal that addresses both problems, try to solicit feedback about whether it would solve the issues people are running into, and then fix both?

From a practical perspective, it seems to me like we could "solve" the issues around incentive compatibility with our current RBF rules (along the lines of what I described above of requiring ancestor feerates to be greater than actual feerates of all transactions which would be replaced), and then later address the pinning problems. However, I don't know if this is actually good for the ecosystem as a whole, since other Bitcoin transaction creators might care a lot about the precise relay behavior here, so making multiple changes -- and particularly, making transaction replacement worse somehow in the interim by becoming more conservative -- might be pretty unwelcome. So maybe it would be better to craft a new proposal that addresses both problems, try to solicit feedback about whether it would solve the issues people are running into, and then fix both?

I agree it's not good to try to think about the multiple fee/feerate rules in isolation. I've also heard about issues with the current absolute fee rule, and definitely don't want to make things worse. Thanks a lot for your feedback! I'll come back with a new RBF proposal to address both issues.