Feedback-ID: i525146e8:Fastmail
Date: Wed, 31 Jan 2024 08:40:12 +0000
From: Peter Todd <pete@petertodd.org>
To: Murch <murch@murch.one>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <ZboHbJyfayUNTgKj@petertodd.org>
References: <Zalsq+Nq7RRr/CAR@petertodd.org>
 <9a89eca8-61fd-4156-825d-c9b718dc3034@murch.one>
 <ZbSueoReTvEmm1s9@petertodd.org>
 <42006209-4ea4-4008-b3b3-556a8461323c@murch.one>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="Du+qgbGRSD2WU7EO"
Content-Disposition: inline
In-Reply-To: <42006209-4ea4-4008-b3b3-556a8461323c@murch.one>
Subject: Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Precedence: list


--Du+qgbGRSD2WU7EO
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sun, Jan 28, 2024 at 12:27:06PM -0500, Murch via bitcoin-dev wrote:
> I agree in the detail, but not about the big picture. You are right that
> it=E2=80=99s a problem that `tx_LM` and `tx_HS` spend the same input and =
therefore
> are direct conflicts.
>=20
> Luckily, it is unnecessary for my scenario that `tx_LM` and `tx_HS`
> conflict. The scenario only requires that `tx_LM` conflicts with `tx_LL` =
and
> `tx_RBFr`. `tx_HS` is supposed to get dropped indirectly per the conflict
> with `tx_LL`.
>=20
> It seems to me that my example attack should work when a third confirmed
> input `c3` is introduced as follows:
> `tx_LM` spends `c3` instead of `c2`, and `tx_RBFr` spends both `c2` and
> `c3`, which allows the following four conflicts:
>=20
> - `tx_HS` and `tx_RBFr` conflict on spending `c2`
> - `tx_HS` and `tx_LS` conflict on spending `tx_LL:0`
> - `tx_LL` and `tx_LM` conflict on spending `c1`
> - `tx_LM` and `tx_RBFr` conflict on spending `c3`
>=20
> `tx_RBFr` would end up slightly bigger and therefore have a bigger fee, b=
ut
> otherwise the number should work out fine as they are.
> I have not verified this yet (thanks for sharing your code), but I might =
be
> able to take another look in the coming week if you haven=E2=80=99t by th=
en.
>=20
> It seems to me that my main point stands, though: the proposed RBFr rules
> would enable infinite replacement cycles in combination with the existing
> RBF rules.

Yes, *that* version of the attack does work, and I was able to succesfully
create a modified version of the previous script that demonstrates it on a
regtest node.

The attack is still exploiting a failure of our current RBF rules: the
replacement of tx_RBFr with tx_HS represents a fee-rate/mining score decrea=
se
that replaces a more profitable transaction, tx_RBFR, with an much less
profitable transaction, ts_HS. Notably, I belive that sdaufter's "Enforce
incentive compatibility" pull-req(1) would reject it, though I haven't actu=
ally
tested that.

To fix this issue I've added a commit(2) to the libre-relay-v26.0 branch th=
at
rejects replacements that spend unconfirmed inputs if the replacement is
conflicting with multiple transactions at once.


Let's look at why this change fixes the issue, making cycles impossible.

Bitcoin Core already uses the term "mining score" to try to measure the
profitability of a transaction. We'll define a similar measure, fee-rate-de=
pth,
a tuple consisting of the raw fee-rate of a transaction and the depth of the
transaction, in terms of the maximum depth of unconfirmed parents that must=
 be
mined for the transaction to be mined. The fee-rate-depth is improved if the
fee-rate is increased and/or the depth is decreased.

For example suppose we have the following unconfirmed transaction graph:

    t1 <- t2 <- t3

The depth of t1 is 0, as it only spends confirmed inputs. The depth of t2 i=
s 1,
as it spends a 0-depth transaction, and the depth of t3 is 2, as it spends a
1-depth transaction.

Suppose we have a new transaction, t2b, that conflicts with t2, and with
fee-rates t2 < t2b < t3. Assuming that the total fee paid by t2b is high
enough, an RBF replacement is allowed:

    t1 <- t2b

While t3 paid a higher fee-rate than t2b, the fee-rate-depth has still
improved, because the depth of t2b is less than the depth of t3.


With this new change, is the fee-rate-depth always improved? Yes.

Rule #6/PaysMoreThanConflicts ensures that the fee-rate of direct conflicts=
 is
always improved by the replacement. With *indirect* conflicts, while the
fee-rate may or may not be improved, the *depth* is improved, because we are
replacing a deeper transaction with a shallower transaction.

Secondly, for direct replacements the modified HasNoNewUnconfirmed function
ensures that the depth of fee-rate-depth is never made worse by prohibiting=
 the
replacement of shallower transactions with deeper transactions. This is
impossible because with the new rule, if a transaction has any unconfirme
dinputs at all - a non-zero depth - only a single transaction is allowed to=
 be
replaced at a time. Thus at worse the depth will remain constant, while rul=
e #6
will ensure that the fee-rate is improved.


Obviously, we could probably improve on this further with more nuanced rule=
s.
But the HasNoNewUnconfirmed fix is simple to implement, and in practice
shouldn't affect very many use-cases. Pretty much all replacements of
transactions spending unconfirmed outputs is for CPFP, and I'm not actually
aware of any wallets that try to batch CPFP transactions together. There
probably are some. But it's certainly not common. That's sufficient for the
purposes of Libre Relay, whose replace-by-fee-rate implementation is intend=
ed
as a prototype to validate the idea.

1) https://github.com/bitcoin/bitcoin/pull/26451
2) https://github.com/petertodd/bitcoin/commit/fec7965277c2287d3eaba59fdc5b=
75729bd4838a

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

--Du+qgbGRSD2WU7EO
Content-Type: application/pgp-signature; name="signature.asc"

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

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmW6B2sACgkQLly11TVR
LzcrYg//czv28I2HZJtde4nk6g4Yfm/3M8QONtkEzbn5z2NgXXlkv+oJOX7gDMxK
46jR6pWei7x8hR/f3iTYu85i9r6uX7LKFGrOOmuzTwoCyR0+pbA46IoOZhv84ElV
0TAC8reX6z/abE8JvbGGSEtAXGqINhYmD32/x0lcHjAVT7/w+4vHWOx0QJsykjTl
gMB8E/DhQcNcZsEFy78YvuuKbZuDkeLmDIeIQeosJS0vmmY0n+baoyILESulag90
7G6LB+A1q9GykQXgPh2EPT4wLVuaUq18rsL1i98JZg/SiOmbYNFX6qFDL9BdUSRY
Jr6ZDX5zltHNWRJ7NP4IcSwNjup2YB9eu6kWoowyRVbfUM2CrvdAebHz7OucMuqO
PCA9dryjhyrX3Jx4LuRqwQpdfSlgRR0ce93sO9MnoSY7admXHqjZDUKuWm+sBv7K
E0hZTSa0OaitwrQaQEeaW794QUZM/SVI5kr0PxMgyo8TkgkmaiMdPUpQqN3hpyOD
0mnh2XnjMz/SNqf+s6zfAfi4OHP5fFP0QR0Q7hDxgLMzUdYjv58e0bDRPxG57bMa
A6Dz8OUr9Ha7AuTxZqLEh/W0W5/Q+JWyQcFrVHsJkCsc+q3JywSTcOJIJ4dgzejR
YgpqNnOlLWGSs7Ji0OihUlTw/+GbPpN41uPXkeA+EAaBaKWZtv0=
=GC8L
-----END PGP SIGNATURE-----

--Du+qgbGRSD2WU7EO--