Subject: [bitcoindev] Re: A Free-Relay Attack Exploiting RBF Rule #6

From: Antoine Riard <[email-masked]>
Date: Fri, 22 Mar 2024 16:18:18 -0700 (PDT)

Hi Peter,

> The marginal cost to an attacker who was planning on broadcasting B 
anyway is 
> fairly small, as provided that sufficiently small fee-rates are chosen 
for A_n, 
> the probability of A_n being mined is low. The attack does of course 
require 
> capital, as the attacker needs to have UTXO's of sufficient size for A_n.

I think an attacker does not necessarily need to have a UTXO's of 
sufficient size for A_n.
One could reuse feerate ascending old LN states, where the balance on 
latest states is
in favor of your counterparty. So it might be a lower assumption on 
attacker ressources,
you only needs to have been _allocate_ a shared-UTXO in the past.

> The larger the mempool size limit, the more 
> effective the attack tends to be. Similarly, the attack is more effective 
with 
> a larger size difference between A and B. Finally, the attack is more 
effective 
> with a smaller minimum incremental relay fee, as more individual versions 
of 
> the transaction can be broadcast for a given fee-delta range.

I think the observation on larger the mempool size, more effective the 
attack tends
to come as a novel insight to me. Naively, in a world where the future 
blockspace
demand is uncertain, miners have an incentive to scale up their mempool 
size limit.
As such, holding a cache of non-mined low-feerates transactions. The type 
of bandwidth,
denial-of-service described sounds effectively to affect more full-nodes 
with large 
mempools. Fair point, it's expected they have more bandwidth ressources 
available too.

> Of course, this attack can be parallelized, with many non-conflicting A_n 
> chains at once. Depending on P2P topology, maximum bandwidth may be 
consumable 
> by broadcasting multiple _conflicting_ A's to different nodes at once², a 
> fairly obvious attack that I (and probably others) have already disclosed.

Yes, if I remember correctly bandwidth wasting attacks by exploiting RBF 
propagation
asymmetries were considered in 2021 when an automatic mempool 
rebroadcasting implementation
was proposed in Bitcoin Core. And alternatively, I echoed mempool 
partitioning concerns
during the tx-relay workshops on IRC in the same year of 2021, notably how 
you can use
to increase pinning attacks odds of success (assuming time-sensitive nodes 
e.g LN have
a single local mempool).

Commenting on this, do we have a free-relay attack variant where an 
attacker with reasonable
visibility on the transaction-relay network could exploit propagation 
asymmetries due to
*_INVENTORY_BROADCAST_INTERVAL and re-inject A_n traffic in a targeted 
fashion ?
I don't think it's worst than the parallelization you're describing, it's 
just another approach.

> Requiring replacements to increase the fee-rate by a certain ratio would 
also 
> mitigate the attack. However doing so would break a lot of wallet 
software that 
> bumps fees by values equal or close to the minimum relay fee.

I think there is still the open questions of the economic relevance of 
replace-by-fee if
the local mempool is completely empty. Here a miner is optimizing to 
maximize absolute
fee as a transaction replaced by a higher-feerate, lower fee is less 
interesting if you have
less than 1 MB virtual bytes / 4 MB WU.

> Ironically, the existence of this attack is an argument in favor of 
> replace-by-fee-rate. While RBFR introduces a degree of free-relay, the 
fact 
> that Bitcoin Core's existing rules *also* allow for free-relay in this 
form 
> makes the difference inconsequential.

Back on the point where an attacker ability to provoke bandwidth DoS in 
considerations
of the UTXO-amount available, a minimal absolute fee as a proof of owning 
some UTXO
amount could be still maintained (or maybe after a _bounded_ number of 
replacement under
a given block period).

We studied proof-of-UTXO ownership as a p2p DoS mitigation approach in the 
past with Gleb:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-November/002884.html

Best,
Antoine

Le lundi 18 mars 2024 à 13:24:12 UTC, Peter Todd a écrit :

> RBF Rule #6 requires that a replacement transaction have a fee-rate higher 
> than
> the fee-rate of all conflicting transactions. This rule aligns economic
> incentives, as in most circumstances miners earn more money by mining a 
> higher
> fee-rate transaction than a lower fee-rate transaction, even if the 
> absolute
> fee paid by the replacement is more.
>
> While RBF Rule #6 was implemented as part of my original Full-RBF opt-in
> pull-req¹, it was mistakenly left out of BIP-125, which was written later 
> by
> Harding. Thus it's often forgotten in analysis of RBF.
>
> Rule #6 creates a path dependency: the order in which replacement 
> transactions
> are received determines which transactions are ultimately accepted. This
> creates an opportunity for free-relay, as follows:
>
> 1. Create two transactions, A and B, where A is a large, low fee-rate, high
> absolute fee, transaction, and B is a small, high fee-rate, low absolute 
> fee
> transaction.
>
> 2. Broadcast A and B to different nodes simultaneously.
>
> 3. Nodes that receive A first will not replace A with B, because B pays a 
> lower
> fee, violating RBF Rule #3. Notes that receive B first, will not replace B 
> with
> A, because A has a lower fee-rate, violating RBF Rule #6.
>
> 4. Create A_1, a transaction with the same (large) size as A, but paying a
> slightly higher fee (and thus fee-rate). Nodes that received A first will
> replace A with A_1, consuming bandwidth. These nodes will also broadcast 
> A_1 to
> peers who have B, consuming their bandwidth even though they reject A_1.
>
> 5. Repeat until A_n has a fee-rate high enough to have a non-trivial risk 
> of
> being mined. Or B is mined, invalidating all A_n.
>
> The marginal cost to an attacker who was planning on broadcasting B anyway 
> is
> fairly small, as provided that sufficiently small fee-rates are chosen for 
> A_n,
> the probability of A_n being mined is low. The attack does of course 
> require
> capital, as the attacker needs to have UTXO's of sufficient size for A_n.
>
> The attack is most effective in cases where fee-rates have a significant 
> slope
> to them, with the minimum relay fee being small compared to the 
> competitive fee
> to get into the next block. The larger the mempool size limit, the more
> effective the attack tends to be. Similarly, the attack is more effective 
> with
> a larger size difference between A and B. Finally, the attack is more 
> effective
> with a smaller minimum incremental relay fee, as more individual versions 
> of
> the transaction can be broadcast for a given fee-delta range.
>
> Of course, this attack can be parallelized, with many non-conflicting A_n
> chains at once. Depending on P2P topology, maximum bandwidth may be 
> consumable
> by broadcasting multiple _conflicting_ A's to different nodes at once², a
> fairly obvious attack that I (and probably others) have already disclosed.
>
>
> # Mitigations
>
> Replace-by-Fee-Rate mitigates the attack, by limiting the possible range of
> fee-rate delta. For example, in Libre Relay, which does 
> replace-by-fee-rate at
> a fee-rate ratio of >= 2x, if A starts at 3sat/VB, the attacker can only 
> do 2
> cycles of the attack as a B >= 6sat/VB will simply replace A.
>
> The attack itself is arguably an economic exploit: *because* Bitcoin Core
> doesn't yet implement replace-by-fee-rate, nodes who accepted A first, are
> wasting their bandwidth relaying variations on A that are clearly less
> desirable to miners than B. An economically rational miner would just mine 
> B
> right now, and the fact that _other_ economically rational miners would 
> mine B
> just strengthens the case for mining B now. Indeed, real-world 
> measurements of
> replace-by-fee-rate have found that (most likely) due to mempool
> inconsistencies, roughly half or more³ of RBFR replacements are mined 
> already.
>
> Requiring replacements to increase the fee-rate by a certain ratio would 
> also
> mitigate the attack. However doing so would break a lot of wallet software 
> that
> bumps fees by values equal or close to the minimum relay fee.
>
>
> # Related Attacks
>
> Rule #6 is just one of many ways to achieve the same effect: getting a 
> miner to
> invalidate a set of large transactions, wasting bandwidth. For example, 
> miners
> who accept payment for guaranteeing that a specific transaction gets mined 
> also
> make this kind of attack possible.
>
>
> # Discussion
>
> Ironically, the existence of this attack is an argument in favor of
> replace-by-fee-rate. While RBFR introduces a degree of free-relay, the fact
> that Bitcoin Core's existing rules *also* allow for free-relay in this form
> makes the difference inconsequential.
>
>
> # Disclosure
>
> This issue was disclosed to bitcoin-security first. I received no 
> objections to
> making it public. All free-relay attacks are mitigated by the requirement 
> to at
> least have sufficient funds available to allocate to fees, even if the 
> funds
> might not actually be spent.
>
>
> # References
>
> 1) https://github.com/bitcoin/bitcoin/pull/6871
> 2) https://petertodd.org/2024/one-shot-replace-by-fee-rate#the-status-quo
> 3) https://petertodd.org/2024/replace-by-fee-rate-success-rate
>
> -- 
> https://petertodd.org 'peter'[:-1]@petertodd.org
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/0a377ddb-b001-41ba-9208-27b3fa059bb5n%40googlegroups.com.