Delivery-date: Tue, 19 Mar 2024 07:03:38 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of pete@petertodd.org designates 103.168.172.157 as permitted sender) client-ip=103.168.172.157;
Feedback-ID: i525146e8:Fastmail
Date: Tue, 19 Mar 2024 13:46:30 +0000
From: Peter Todd <pete@petertodd.org>
To: Nagaev Boris <bnagaev@gmail.com>
Cc: bitcoindev@googlegroups.com
Subject: Re: [bitcoindev] A Free-Relay Attack Exploiting RBF Rule #6
Message-ID: <ZfmXNiscjatFOOCX@petertodd.org>
References: <Zfg/6IZyA/iInyMx@petertodd.org>
 <CAFC_Vt7BE866DJGQ9EqA+DroEkDH+4U_72-RpCUfyrLHmtnZ1Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="qpQqvMxvNFBvdgMC"
Content-Disposition: inline
In-Reply-To: <CAFC_Vt7BE866DJGQ9EqA+DroEkDH+4U_72-RpCUfyrLHmtnZ1Q@mail.gmail.com>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com


--qpQqvMxvNFBvdgMC
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, Mar 19, 2024 at 09:37:59AM -0300, Nagaev Boris wrote:
> Hi Peter,
>=20
> On Mon, Mar 18, 2024 at 10:24=E2=80=AFAM Peter Todd <pete@petertodd.org> =
wrote:
> > Rule #6 creates a path dependency: the order in which replacement trans=
actions
> > are received determines which transactions are ultimately accepted.
>=20
> I'd like to share my thoughts regarding RBFR rules and propose something.
>=20
> The proposed RBFR rule is also path-dependent. Two transactions can
> conflict with each other, but their fee rates can be too close for one
> of them to eliminate the other from nodes' mempools. The first
> transaction a node sees is kept in its mempool.

It's not really fair to say that "the proposed RBFR rule is also
path-dependent". What you're describing is a property of Bitcoin Core's mem=
pool
in general, for all transaction acceptance rules. We've *always* had the
property that two essentially identical transactions, differing only in a
trivial way, will be accepted on a first seen basis. Achieving consensus
requires bandwidth, and since you can generate an essentially infinite numb=
er
of almost identical transactions, you'll always be able to find cases with =
path
dependency.

> Is it possible to have a rule that is completely path-independent? The
> eviction rules are path-independent iff, for each pair of conflicting
> transactions A and B, it is always known which of them should be
> preferred over the other, and this relation is transitive. Having such
> a property would be very beneficial in preventing any attacks on the
> mempool. This property of the mempool can also be seen as the eventual
> consistency of all the mempools of the nodes. A good property, isn't
> it?

I'd suggest that you should argue concretely *why* this is a good property.=
 The
RBF Rule #6 issue isn't strong evidence, as it's only related to a specific
type of meaningful path dependency, where fees/size differ meaningfully. Yo=
u're
talking about all forms of path dependency, including trivial differences w=
here
fees/size are the same and only a txid differs due to a trivial change.

> How can we design such a rule system?
>=20
>  1. It must align with miners' incentives; otherwise, it simply won't wor=
k.
>  2. And it must not open the door for DoS attacks on the mempool.
>=20
> The naive approach satisfying the first requirement is a simple rule
> saying "the higher the fee rate, the more preferential is the
> transaction." However it does not specify what to do with two
> transactions of the same fee rate and also doesn't prevent DoS
> attacks. The former is easy to fix, e.g. preferring the transaction
> with lower txid. (Must be formally proven though.) Let's discuss the
> latter, which is a stumbling stone here.
>
> Traditionally, the way of preventing DoS was to reject some
> transactions and to stop their broadcasting at this node. What about
> deprioritizing them instead? Make two priority queues of transactions
> in the node: (1) to process incoming transactions and (2) to
> broadcast. When a transaction is double-spent, it is deprioritized in
> both queues. If an attacker sends many double-spending transactions to
> DoS the mempool, not all of them are broadcast further because by the
> time a transaction is ready to be broadcast, its newer version has
> already evicted it; the first one is not yet broadcasted. So a node
> broadcasts fewer transactions than it receives, which reduces the DoS
> effect. And still, the whole system is eventually consistent; just
> spammers get their transactions spread slower.
>=20
> What are your thoughts on this scheme?

So first of all, I'll point out that because you can brute force txid
variations, if the rule is lowest txid wins, it wouldn't be hard to do a bi=
t
of brute forcing to get, say, 2^32 =3D 4 billion different variations. For
practical purposes, that's basically infinite bandwidth.

OTOH, suppose the rule is that the txid with the most leading zeros wins. T=
his
fixes the infinite bandwidth problem, as it's a clear PoW with something li=
ke
48 possible total replacements at most (assuming a reasonable amount of tot=
al
PoW). But the mempool consensus problem remains unfixed, as there's essenti=
ally
infinite variations possible with the same number of leading zeros.

Bitcoin doesn't have this issue because it has a minimum PoW, set by the
difficulty algorithm. But we can't ask that of transactions in general. So =
I
think either way we've failed to actually achieve consensus over trivial
variations.


More broadly, I like the idea of using a bandwidth constrained channel for
doing replacements where there are meaningful, but small, differences in th=
e
size and/or fees paid. But I think we should persue the idea on the basis t=
hat
it makes economic sense. Not that it'll prevent mempools from being out of
consensus.

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

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

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

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

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmX5lzQACgkQLly11TVR
Lze78RAAwzDJmjgERASvWoiVrT85/SmE3Frb0SNS6qxqYFfhqke4bjOOyw413HMh
ubV4cYbyH7ctAGapp4RmrYdkTOPQEV/k9QZVVP+rlDJexPqyob6MD1fCrxJDrWeZ
Cxsg53qKNANFSpXjmdBfbgLysPTRmTa2QPX35WOLwq6wk2gRypz4+vZ7hYPT0zOT
HuXu6NxD85hCKMqRX062kN8Z98TrXMQWqQfOss4KO8Oq/qfSjJGOSgQfjVueOv/B
4RZZxGEFtOXLW8fdEhuP0ZTQN6ELJHW8lQchYwSnoB9egslMrMrf9hmDBkosyKXo
tAXHpLUXPKyX8NJMfwZnM3m7AiP6PrmFKSBmUyrHGjcN2L5owpSy3U5ns6WmYoTR
ixK7XlGsRu+6s2nmjJBmIChae5MzX+vqzasbv/q0UB6pyzLa2nLJD8ytx1SxoWug
25uSvUGmWFCIdC4C/ijsI1yRVoXfGJ9qZMTxQeReMFcMnQ33Xi/BU37jj4LPqOxy
Mj1VuLoO0ezlvAgpI0E97B7aIR+RfwXQNszdvBmZ/wtqZwSb14h2yQxmDFPFYwM5
sIZ1nJxWaVVYW/bdfFumnpQIpz8T1u79vM27jcGLVM8k+97i+azM9GLyhB/4X6Bx
F5tj9/Kx4w3ExzuqTKUYuJefPQ4x21MmZPfMhSKfVQQ2hyQxz/g=
=VzLJ
-----END PGP SIGNATURE-----

--qpQqvMxvNFBvdgMC--