Feedback-ID: i525146e8:Fastmail
Date: Sat, 9 Dec 2023 10:08:56 +0000
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <ZXQ8uFLoNlSksalX@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="RWq1h5nm+ReKvAbI"
Content-Disposition: inline
Subject: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement
	Cycling Mitigation
Precedence: list


--RWq1h5nm+ReKvAbI
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

While this seems like a reasonably obvious idea, I couldn't find a previous
example of it published on bitcoin-dev or elsewhere. So for the ability to =
cite
it, I'll publish it now.


# Summary

Altruistic third parties can partially mitigate replacement cycling(1) atta=
cks
by simply rebroadcasting the replaced transactions once the replacement cyc=
le
completes. Since the replaced transaction is in fact fully valid, and the
"cost" of broadcasting it has been paid by the replacement transactions, it=
 can
be rebroadcast by anyone at all, and will propagate in a similar way to whe=
n it
was initially propagated. Actually implementing this simply requires code t=
o be
written to keep track of all replaced transactions, and detect opportunitie=
s to
rebroadcast transactions that have since become valid again. Since any
interested third party can do this, the memory/disk space requirements of
keeping track of these replacements aren't important; normal nodes can cont=
inue
to operate exactly as they have before.


# Background

To recall, a replacement cycling attack has three basic stages:

0) Target transaction tx0_a is broadcast, spending one or more outputs
1) Attacker broadcasts double-spend tx0_b, spending an additional output
   under the attacker's control
2) Attacker broadcasts double-spend tx1, double-spending only the additional
   input, resulting in the original input set not being spent

Replacement cycling is a potential threat any time two or more parties have=
 the
ability to spend a single txout, and rendering that output _unspent_ is
harmful. For example, replacement cycling is an attack on lightning HTLCs,
because it can result in an HTLC pre-image not being observed by a party un=
til
after the HTLC expires. Similarly, replacement cycling is a potential attac=
k on
signatureless anchor outputs, as it can allow third parties to revoke a CPFP
anchor spend, making the parent transaction(s) unminable.


# Altruistic Rebroadcasting

Bitcoin Core keeps no records of replaced transactions. Thus after the
replacement cycling attack is complete, tx0_a has been entirely purged from=
 a
Bitcoin Core node's mempool, and all inputs to tx0_a are unspent. Thus it is
just as valid to broadcast as before.


## Resources Required

Let's suppose we have a DoS attacker who is constantly broadcasting replace=
ment
in an effort to overwhelm nodes performing altruistic rebroadcasting. The
BIP-125 RBF rules require that a replacement transaction pay for the bandwi=
dth
used by the replacement. On Bitcoin Core, this defaults to 1sat/vByte. Assu=
ming
the attacking transactions are ~100% witness bytes, that is ~0.25sats/byte =
of
relay bandwidth per peer.

Suppose the DoS attacker has a budget equal to 50% of the total block rewar=
d.
That means they can spend 3.125 BTC / 10 minutes, or 520,833sats/s.

    520,833 sats/s
    -------------- =3D 2,083,332 bytes / s
    0.25 sats/byte

Even in this absurd case, storing a one day worth of replacements would req=
uire
just 172GB of storage. 256GB of RAM costs well under $1000 these days, maki=
ng
altruistic rebroadcasting a service that could be provided to the network f=
or
just a few thousand dollars worth of hardware even in this absurd case.

It's notable that miners may in fact want to run replacement rebroadcasting
software themselves, to ensure they are not missing any valid, profitable,
transactions. In the context of a large mining pool, the additional cost ov=
er
running a regular node may be affordable.


## Limitations

At the moment, Bitcoin Core propagates transactions purely via INV
announcements; there is no set reconciliation mechanism to synchronize memp=
ools
between peers. If an INV announcement is missed for some reason, it's quite
possible that the transaction will be missed. Thus rebroadcasting may be
defeated if the % of nodes who do *not* have the transaction at the time of
rebroadcast is below the percolation threshold. Indeed, with good timing an=
d a
sybil attack, an attacker may be able to deliberately trigger this conditio=
n.

Improvements like the Transaction Announcements Reconciliation(2) BIP may be
able to mitigate this issue, by ensuring that regardless of the timing of
replacements, the rebroadcast transaction eventually reaches all nodes via =
the
reconciliation process.


# References

1) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/021=
999.html
2) https://github.com/naumenkogs/bips/blob/bip_0330_updates/bip-0330.mediaw=
iki

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--RWq1h5nm+ReKvAbI
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmV0PKUACgkQLly11TVR
LzdWpw//fnWHLOIRIT8y0dvlQUHZTw+3y6oqz7O4rgJvR2g+kjr738idR7DEzDRZ
gERk+iEeKrpYkx29S53aMK8QhjqF+hCxPHPV/hCTumji8kcT7GU8Inx+o9ad0xrv
zulpyu796RlPF/WrOP9nzQRLhfqvKcYoZEQbF9tebfWuJsaQOBCTucuGGRjhDr9D
Zk8r3ZZYrhpa1Dzd6EXQZA+6LfR0SOJnCTaArOckXDnxWxJNpKjQLvalSrjrO8d+
vH/SbKtFfO/abiTZnmVpZoFROkfofK1/UfDK2sRMjJMpOUz6VP+VwVzCGdIU3Kgz
psMo36TEK1QRJ5I2APdJYHx3yHPYDrv6rbWpKFXgAhD/wWnQb+n1fCenvQ0ZILNF
hmPwH8Ya8QrxtDPLh9y2QUIOJjgxeP7cPO43v4slJLD+RV4mnqzkw+F81wShXbTD
7kvYIZJfVP/UWHTGD7clmVXnHT1kBHTnawBLyNJL4dh4OmoNMwVOSj4W1g5V1NgI
E2FTj424YJQYyMmaW208TWmYxu45pCa65CXRSvX6hV+u+CkNZKHPlSvu9Zr4gX2b
aDGYUnpb0WJ/iT9Z5P8gB+Z3RQOMf2kFwEEBUCjoNRSYTur1MQK4ynZbqpaFGPve
3LRTqOL74nUSb8JxVoWsul9aDO0Dg3OySvOe9uclDyP9bXIb3NE=
=BPVC
-----END PGP SIGNATURE-----

--RWq1h5nm+ReKvAbI--