Received-SPF: pass
    (redirect.mail.gandi.net: Sender is authorized to use 'SRS0=slBF=KU=petertodd.org=pete@redirect.mail.gandi.net' in 'mfrom' identity (mechanism 'include:_nblcust.gandi.net' matched))
    receiver=mx3.messagingengine.com;
    identity=mailfrom;
    envelope-from="SRS0=slBF=KU=petertodd.org=pete@redirect.mail.gandi.net";
    helo=redirect.mail.gandi.net;
    client-ip=217.70.178.232
Feedback-ID: i525146e8:Fastmail
Date: Thu, 14 Mar 2024 15:46:22 +0000
From: Peter Todd <pete@petertodd.org>
To: security@bitcoincore.org
Subject: RBF Rule #6 DoS Attack
Message-ID: <ZfMbzhPUDKSaxf9x@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="LuptQxBpgf3rLObG"
Content-Disposition: inline
Content-Length: 5005


--LuptQxBpgf3rLObG
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

I do _not_ think the following issue is particularly serious due to the high
capital requirements necessary to use a significant amount of bandwidth, and
the existence of similar attacks=B9. But I wanted to run it by you guys bef=
ore
publishing it openly in case someone has a very good argument for it being
serious enough to keep quiet.


RBF Rule #6, implemented by Bitcoin Core on top of the BIP-125 rules, requi=
res
that a replacement transaction have a fee-rate higher than the fee-rate of =
all
directly 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 pai=
d by
the replacement is more.

However, the addition of this rule on top of BIP-125 introduces a new form =
of
DoS attack due to the path dependency of replacements. Basically, depending=
 on
what transaction a node sees first, for a given set of replacement transact=
ions
different nodes may end up with different transactions in their mempool.

Concretely, an attacker can do the following:

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 l=
ower
   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 sl=
ope
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 w=
ith
a larger size difference between A and B. Finally, the attack is more effec=
tive
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 consum=
able
by broadcasting multiple _conflicting_ A's to different nodes at once=B9, a
fairly obvious attack that I (and probably others) have already disclosed.

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 >=3D 2x, if A starts at 3sat/VB, the attacker can only =
do 2
cycles of the attack as a B >=3D 6sat/VB will simply replace A.

Requiring the fee-rate to increase by at least some ratio in each replaceme=
nt
would also mitigate the attack at higher fee-rates. For example, at a fee-r=
ate
of 100sat/VB, a minimum fee-rate ratio of 10% would constitute a 10x reduct=
ion
in bandwidth usage vs the incremental fee-rate of 1sat/vB.

1) https://petertodd.org/2024/one-shot-replace-by-fee-rate#the-status-quo

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--LuptQxBpgf3rLObG
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmXzG8cACgkQLly11TVR
Lzd7pQ/+OEoOokNZTjNB3rappZvDdrCIij8cenWff3RJrTsaiw4WqF9c9acqSOut
rtYPUvjIDn4s6oOzG6JGQV5Jy4KPqS40eoPZGgoiUxqeEkfzjN2+SIWxuUUeeffu
CjCM+yaxoKylGcYyuzJ97YdSi+ZdGgTYRs6ahOBtHotS6aioxES4wYuIFXhlC2QA
HBqEa1tXWE2vTUAt9hVPHn3kQYZAZgvjoA0i+tlBODgDjJCJWIbX9v8Ttov2g0Xq
nnoC5UafHkhnW1fKdWkHu1dLQ+hXx6hDM/NcsFCa2UMNKlC6iXpxz2maB2aPis2O
9cm/k6ipI0GDlUqb0lS17/Sn2A5BLexP27S3fnW49UmSsgZ5UpOr3KeIYKDrZ9/E
sxU/PHSkBMswMw7MzJV02uA0y3N7P8J8E26UCdRibooCnuoIH1a3uFCP2B4ffDBF
HPicLKKPEpYf/rcnjfq4pTQn4KfliH46ttzgP5eP8t0bzulWNiwCANcRGm54BHZQ
q8cEItou1QHeqT2WcWmw3qnESeXLg6EW3+6E2ww6ChtC7XzG343/eLErkyHX0yjh
lEaTV6JmFdW3DvCszsT8kfS1ePAgtRiwVGkS505ZOszZ3KwBVKLG7Z4bp2PH4d8a
SU7BS8eT/VPlHnj9bnulz3T8CmLDkqBtfUVSR2cQ1ikt99+r9bw=
=d4CI
-----END PGP SIGNATURE-----

--LuptQxBpgf3rLObG--