Delivery-date: Mon, 22 Jul 2024 11:00:33 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of pete@petertodd.org designates 103.168.172.147 as permitted sender) client-ip=103.168.172.147;
Feedback-ID: i525146e8:Fastmail
Date: Mon, 22 Jul 2024 17:13:48 +0000
From: Peter Todd <pete@petertodd.org>
To: "David A. Harding" <dave@dtrt.org>
Cc: bitcoindev@googlegroups.com
Subject: Re: [bitcoindev] A "Free" Relay Attack Taking Advantage of The Lack
 of Full-RBF In Core
Message-ID: <Zp6TTAJ399CKbY5s@petertodd.org>
References: <Zpk7EYgmlgPP3Y9D@petertodd.org>
 <c6593662694f9d4a4fe999dd432f87ff@dtrt.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="/GffXKu588ogAARA"
Content-Disposition: inline
In-Reply-To: <c6593662694f9d4a4fe999dd432f87ff@dtrt.org>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com


--/GffXKu588ogAARA
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline

On Fri, Jul 19, 2024 at 08:41:07PM -1000, David A. Harding wrote:
> > I believe the authors of [BIP431...] don't want to admit that they've
> > wasted a large amount of engineering time on a bad proposal.
> 
> You've previously argued against designing contract protocols to depend
> CPFP-style fee bumping for their offchain transactions, however that is
> what is widely used by LN today and it appears to be what LN and other
> offchain protocol developers want to use in the future.  If we accept
> that, at least for the purposes of argument, what can we do to improve
> CPFP fee bumping for LN?

To be clear, the reason why I came up with one-shot RBFR was _because_ I wanted
to find a pinning solution for CPFP (and SIGHASH_ANYONECANPAY) transactions. If
everything could use pure RBF, eg via pre-signed transcations, RBFR would be
much less useful.

> All we really need at this point is to enable package relay so that
> parent transactions are no longer subject to a dynamic mempool minimum
> when they're bundled with a high-feerate child.  Preliminary support for
> that should be released in the next major version of Bitcoin Core, with
> improved support being worked on for later releases.
> 
> Package relay is the only thing we need at this point because the
> existing LN protocol makes use of CPFP carve-out, which minimizes
> transaction pinning issues.
> 
> However, another substantial Bitcoin Core improvement, cluster mempool,
> is incompatible with CPFP carve-out.  TRUC is an alternative to CPFP
> carve-out that is easy to reason about, easy to use, more general in
> nature (good news for newer contract protocols), and which can possibly
> be automatically applied to existing LN onchain transactions, allowing
> cluster mempool to be deployed ASAP without requiring any significant
> changes to anyone else's software.

So as I explained in my stand-alone email, we can cleanly get rid of the CPFP
carve-out with RBFR *without* needing to change anyone else's software:

https://groups.google.com/g/bitcoindev/c/vfbF7QyVwPE/m/-ewtlB5-AQAJ

TRUC does _not_ allow cluster mempool to be deployed ASAP. It requires all
existing L2 protocols that need the CPFP carve-out to upgrade, and likely close
and reopen channels.

This is a massive downside to TRUC.

> As you've shown[2], the main downside of TRUC transactions (if we're
> going to depend on CPFP-style fee bumping anyway) is that users of TRUC
> transactions who have a malicious counterparty might need to pay a
> slightly higher onchain feerate than they would need to pay under the
> same situation with CPFP carve-out.  However, the increase is small
> enough that most honest parties should be able to afford it, so there's
> no incentive for a counterparty to do it.

As I explained months ago, the oddly high 1000vB limit chosen in TRUC allows
attackers to make TRUC users pay significantly higher fee rates in many mempool
situations, including the situation we are in right now:

https://petertodd.org/2023/v3-txs-pinning-vulnerability

At the moment, a typical TRUC using LN transaction can, IIRC, be forced to pay
something like a 4x higher fee as the difference between "will confirm in the
next block" and "won't confirm for days, if ever", is less than 1sat/VB.

I suggested that limit be reduced to something closer to a typical CPFP
use-case, and my suggestion was rejected.

This gets even worse with keyless ephemeral outputs using TRUC, as *anyone* can
itercept one of those and create a pin. An attacker could, for example, run
compact block enabled nodes and simply wait for LN nodes using compact blocks
to broadcast keyless ephemeral output, CPFP-using transactions, detect those
transactions, and automatically pin them.

> The alternative to TRUC that you've proposed is replace-by-feerate
> (RBFr).  This is also compatible with existing LN transactions and it's
> conceptually super simple (I assume the code is too), which is
> wonderful.  However, it's downsides are:
> 
> 1. It fundamentally enables a significant amount of free relay.  I'll
>    sketch a super basic attack at the end of this email that costs 0.55
>    BTC per day ($67,000 USD) to 100x the amount of bandwidth used by
>    relay nodes.  I'm sure more efficient attacks are possible.

See my analysis at the end. You are analyzing the wrong thing, and missing the
fact that comparable attacks are already possible. Indeed, even attacks that
are probably much *worse*.

>    An attacker who is able to consume an excessive amount of relay node
>    bandwidth at relatively low cost may be able to create both
>    short-term and long-term problems for all Bitcoin users.  If the
>    created problems result in a rapid increase in user feerates, then
>    free relay attacks become cheaper due to low feerate transactions
>    being automatically evicted from the bottom of the mempool.

Relay bandwidth and fee-rates don't have any direct connection in Bitcoin Core.
Fee-rates are set by users outbidding each other. Unless an attacker is willing
to outbid actual user transactions, paying money to do so, they can't make
fee-rates increase (modulo certain exploitable/broken fee-rate estimators
making bad assumptions about mempools, but that's not a new problem).

> 2. It may allow empting the mempool at relatively low cost.  An attacker
>    sending just 750 transactions at the top mempool feerate can
>    guarantee eviction of every honest user's transactions.  The attacker
>    can then replace 300 MB of transactions with a single 43,179 vbyte
>    transaction.  Even if the replacement transaction pays 100
>    sats/vbyte, when you compare that to the 1,000,000 vbytes of
>    next-block transactions each miner lost, the miner is only earning an
>    effective feerate of 4.3 sats/vbyte.

I covered that attack in my one-shot RBFR writeup:

https://petertodd.org/2024/one-shot-replace-by-fee-rate#fill-and-dump-attack

It's not a concern for a few reasons:

0. It's a class of attack that is already possible without RBFR: obviously, you
   can fill and dump by simply double-spending your fill transactions. Eg, this
   is obviously easy to do with full-rbf!

1. One-shot RBFR - my actual incentive-compatible proposal - is not vulnerable
   to fill-and-dump attacks the way you described, as you can't "dump" the top
   of the mempool with one-shot RBFR. The "dump" transactions won't be
   accepted, as one-shot RBFR only allows you to replace transactions with a
   low fee-rate that won't be mined in the near future.

2. Miners routinely run with much larger mempools than normal nodes. As I
   mentioned elsewhere, in my discussions with miners, mempools of 1GB or more
   were common.

3. Rebroadcasting is easy. Anyone can rebroadcast previously broadcast
   transactions. If people actually tried fill-and-dump attacks, all they'd
   succeed in doing is briefly kick out some transactions from typical
   mempools, at the cost of creating a bunch of higher fee-rate transactions
   that will most likely get mined at great expense to the attacker.

>    Further, it's easy to imagine situations where evicting
>    time-sensitive transactions from mempools might allow theft of funds
>    in excess of a few thousand dollars (my immediate thoughts go to
>    situations involving watchtowers).

Watchtowers are actually a uniquely *bad* example. Recall that watchtowers
merely broadcast pre-signed justice transactions in response to a revoked
commitment transaction being mind. AFAIK, all existing watchtower
implementations pre-sign the transactions with a fixed, high, fee-rate. What
they actually should do is provide the watchtower with multiple pre-signed
transactions at different fee-rates, up to the economic maximum. But I digress.

As explained above, rebroadcasting is trivial, and watchtowers are expected to
run 24/7 anyway. Secondly, one-shot RBFR prevents the replacement of any
transaction that is expected to be mined soon. So if the justice transaction
was signed with a high enough fee-rate to get mined, the only thing the
attacker can do is outbid it (and all transactions before it). Which is true
without RBFR anyway!

Finally, in general, while applications like Lightning are time-sensitive,
they're not *that* time sensitive. LND uses 144 blocks as its default CSV
delay, giving you an entire day to get a transaction mined. Doing fill-and-dump
attacks dozens of times in a row is not cheap.

> 3. Limiting the worst-case free relay and excessive mempool eviction
>    requires additional rules (e.g. one-shot RBFr) that are challenging
>    to implement and analyze at present, as several devs have noted[3].
>    Both implementation and analysis should become much easier if cluster
>    mempool is deployed (also noted by devs), but the deployment of
>    cluster mempool requires removal of CPFP carve-out, and removal of
>    CPFP carve-out requires either the upgrade of thousands of LN nodes
>    and channels or a drop-in solution (ideally one that can be analyzed
>    independently from cluster mempool, like TRUC).

As I explained separately, you are very incorrect in your description of the
CPFP carve-out. In fact, it's RBFR that is our only path to having a cluster
mempool without requiring existing applications to upgrade.

As for implementation, it is true that implementing one-shot RBFR is harder
without a cluster mempool. But fee estimation is something Bitcoin Core already
does. It would be fine to either 1) re-use the fee estimation machinery to get
a reasonable minimum one-shot fee-rate, 2) periodically generate a block and
use the minimum fee-rate of that block. Mempools aren't a consensus, so it
simply isn't necessary for every mempool to agree exactly on what the minimum
one-shot fee-rate is, for the same reason that it's not necessary for every
mempool to agree on the same minimum relay fee-rate.

> > this is quite an odd case of Core politics
> 
> I began writing this reply to force me to examine your claims for
> myself.  You have a long history of noticing things other people missed.

Thanks!

> A simple free relay attack using RBFr
> 
> ## Constants
> 
> 100,000 vbytes == ~400,000 bytes
>   A 1-input, 1-output P2TR scriptpath spend with the maximum amount
>   of witness data allowed by Bitcoin Core defaults
> 
> 111 vbytes == 162 bytes
>   A 1-input, 1-output P2TR keypath spend
> 
> ## Attack
> 
> - Attacker obtains 500,000 UTXOs
> 
> - For each UTXO
> 
>   - At the dynamic mempool minimum, broadcasts a 100,000 vbyte (400,000
>     byte) transacton.
> 
>   - Waits for it to propagate.
> 
>   - At 1.25x the dynamic mempool minimum, broadcasts a RBFr replacement
>     that is 111 vbytes (162 bytes).
> 
> ## Analysis
> 
> - At 162 bytes each, 500,000 transactions is 81 MB.  I think that will
>   fit in a default-sized mempool.
> 
> - The total amount of transaction data relayed is 500_000 * (400_000 +
>   162), or about 200 GB.
> 
> - The typical daily bandwidth requirement of a blocks-only node is
>   roughly 2.5 MB * 144, or about 0.36 GB per day.  Ideally a relaying
>   node is about the same due to compact blocks, but realistically, it's
>   a small multiple of that.  Call it 2 GB per day.
> 
>   - This implies the attack push each RBFr relay node to use 100x a
>     non-RBFr relay node.
> 
> - At 111 vbytes each, 500,000 transactions is 55.5 million vbytes.  At
>   my nodes current mempoolminfee (1 sat/vb), that's 55.5 million sats,
>   or 0.55 BTC (about $37,000 USD).
> 
> - This analysis ignores the cost of obtaining the UTXOs and possibly
>   later consolidating them, but it also ignores some easy optimizations
>   such as batching the replacements.
G
First of all, subtlety of the class of attack you are describing is it matters
a lot whether or not you expect the double-spend transactions to be mined in
the near future.

With one-shot RBFR - my actual proposal for Bitcoin Core - the fee-rate of the
double-spend is required to be sufficiently high to be likely to be mined in
the near future. With pure RBFR, which is implemented in Libre Relay as an
_experiment_, the double-spend merely needs to be a higher fee-rate. This
difference is one reason why I'm not proposing that Core actually implement
pure RBFR!

So the relevant question is, can you pull off this class of attack with Bitcoin
Core's current relay rules? The answer is absolutely yes. The only significant
difference is you'll be invalidating the big, "fill", transactions with
transations paying economic fee-rates, either in a block, or likely to soon be
in a block. Thus one-shot RBFR makes no difference: the same class of attacks
are possible whether or not it exists.


Secondly, your attack requires $37,000. That amount of money would pay for
2700TB of bandwidth at 0.01 USD/GB, the (expensive!) cost of bandwidth on
Digital Ocean.  There's about 20,000 publicly accessible nodes. So for that
amount of money, you could just DoS attack all 20,000 nodes simultanously with
about 185GB of data each. Digital Ocean is a very expensive way to get DoS
attack bandwidth, so realistically an attacker would probably pay even less for
the attack.

Even worse, you could use that bandwidth to perform a conflicting transactions
attack. For each publicly accessible node, broadcast a different,
100,000vB/400,000B, transaction spending the same UTXO. Each node will waste
bandwidth telling it's ~100 peers (including non-public nodes) about that
transaction, reducing the attackers bandwidth cost by a factor of ~100.

-- 
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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/Zp6TTAJ399CKbY5s%40petertodd.org.

--/GffXKu588ogAARA
Content-Type: application/pgp-signature; name="signature.asc"

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

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmaek0EACgkQLly11TVR
Lzew2g//Wy67c/8Eh02NhzVaKPOo4svIOpPNGLmEiXfsmzQqSSWEDzfcIcIC2WK9
utfP6q+NOeDrlAmj9orgqN/a4h8dkyGw7EQgHr9itIt/eC2CcHpFc7uiXojEFtJ3
4QcJpmSPfDLbTfcyX9OIBtBtXT70vltq+aSk7JxvjSJc2c8QX5TmKQoDVWftRYvg
5ii1JSEhtE6A0rqFzpNdKkpRS/xJaWxeBJLu6hlGPvrWi6HtJ4cIdFsamh5u/9yA
CJQQunwjSt6GDsG3xi3K6f9XsHNCdTFrebkay4tQk29IFiydY45S4XfrPQo2Vpji
xVlDxvwAefFmI2lgiD+OScOVlPVyxPjYSK5PfO/V478vL+KzDkNYyW1ekaWmh2wE
UQ/R1kaVsELzoXIV4XuXqguN0JrcfyTkReyXqEGEqGQKVQUFjBuM2JqdFvp72IUg
7vjccjnZUGrYkBEQP5NLfzV1a42gGMQScONy9zkg4/EtPqdlYCwUf5Ry7DpvczX3
M8PBsWxs2GTUdnIOrcW0gFfJ5VryAIYhITojvqMTcA73+ZA8l/ESBNtUfbMWmbTq
J3mthKLutzWriHnvg3JczDf+IQymptu5+a3H5XyczjPyLzvLOv8jLnTyN4bKp49b
bLo5avrM2cZWuhXXPy2M+oV3i+/cOD2C3lPDFSgT13L2fb8dcIk=
=lnz8
-----END PGP SIGNATURE-----

--/GffXKu588ogAARA--