path: root/c2/7a4440237246e97321891acd492fb4eccfad0a

Return-Path: <pete@petertodd.org>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 9EEB1C0037
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 31 Jan 2024 08:40:23 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 5683D41E56
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 31 Jan 2024 08:40:23 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 5683D41E56
Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key,
 unprotected) header.d=messagingengine.com header.i=@messagingengine.com
 header.a=rsa-sha256 header.s=fm3 header.b=a1ckbb49
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level: 
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H5=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id d9fT62YkpBZk
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 31 Jan 2024 08:40:21 +0000 (UTC)
Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com
 [64.147.123.20])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 1607B41E31
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 31 Jan 2024 08:40:20 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 1607B41E31
Received: from compute7.internal (compute7.nyi.internal [10.202.2.48])
 by mailout.west.internal (Postfix) with ESMTP id A2C483200094;
 Wed, 31 Jan 2024 03:40:19 -0500 (EST)
Received: from mailfrontend1 ([10.202.2.162])
 by compute7.internal (MEProxy); Wed, 31 Jan 2024 03:40:19 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
 messagingengine.com; h=cc:content-type:content-type:date:date
 :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to
 :message-id:mime-version:references:reply-to:subject:subject:to
 :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=
 fm3; t=1706690419; x=1706776819; bh=ns81vdYLVMn6TJ6xPTpF0VUaUbn5
 rNRrK1G2DEzKgBk=; b=a1ckbb49jGqu96YZa5Ssc2R9rx16G0PJ3Jvh59TvTxrK
 sQh4YU3VAIhLp/ajHTAoh6iHewN4Bh2fMTtI02coBYFgVOkec5Wqt9RB4gVCig9F
 PM0/xNmA7Pu7nNdiJQxWhi6YvIE/3wLW5SJg0vHcvx3hNuXTuS+xHkn9W56NfwX7
 hf3WVmhheF1FXC3A4ex4FY82hnnGGJWGNGrgeo0Q4bplHZiwWw0RoQG3fxmz+8FF
 ivtI21fZqp/TOO8Wra7Vs7aNbp4IZSAXZ+gA+720TMq8YSxeIcAXpbMoIHiL6awD
 E8Qf6PETR1rqERCBXMwckagozxIZYpq+DmZVHSsyCg==
X-ME-Sender: <xms:cge6Za7NDWg7gWz0Iqduzz0oGYabNo-93eQfs_Jn_cZ-MykgzOgXgA>
 <xme:cge6ZT4DCX0iJIoYgU0Ehvb64Jf3goZHGPUpXQYx5xlGzkFVxTovEPjOfQ7I-wNzb
 IupvRV_vKHDUJ2odSY>
X-ME-Received: <xmr:cge6ZZdtSA6q6yHP1eLEDBHDJxCa10u2Y5TrbHKYKkRik2FEyIvUz3sbtZFa>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedtkedguddvtdcutefuodetggdotefrod
 ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh
 necuuegrihhlohhuthemuceftddtnecunecujfgurhepfffhvffukfhfgggtuggjsehgtd
 orredttdejnecuhfhrohhmpefrvghtvghrucfvohguugcuoehpvghtvgesphgvthgvrhht
 ohguugdrohhrgheqnecuggftrfgrthhtvghrnhepgeethfffjedugeffueejhfekiedttd
 dutedvgfejiefhvdffjefhledtiedtieelnecuffhomhgrihhnpehgihhthhhusgdrtgho
 mhdpphgvthgvrhhtohguugdrohhrghenucevlhhushhtvghrufhiiigvpedtnecurfgrrh
 grmhepmhgrihhlfhhrohhmpehpvghtvgesphgvthgvrhhtohguugdrohhrgh
X-ME-Proxy: <xmx:cge6ZXK_Y2WXWs4g5I3KdVWbts3haON_MrAtdEHq1x-B09I_COTV3A>
 <xmx:cge6ZeKz1F5To2kcqwwhhF0DfzhU20Rx_jVcdTX-OvTjOoqnlEJw6g>
 <xmx:cge6ZYw_bMuByNh8H2cBKeP3Wc12yN8xsX2tVA5z9sYg7OrI84VNUQ>
 <xmx:cwe6ZTEZ8m3te0Efrste6bWvk_15SM09FGDw6N-xVy_ow5thNDT8aA>
Feedback-ID: i525146e8:Fastmail
Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed,
 31 Jan 2024 03:40:17 -0500 (EST)
Received: by localhost (Postfix, from userid 1000)
 id E2B1C5F81A; Wed, 31 Jan 2024 08:40:12 +0000 (UTC)
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 31 Jan 2024 08:40:23 -0000


--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--