Subject: Re: [bitcoindev] A Free-Relay Attack Exploiting RBF Rule #6

From: Peter Todd <[email-masked]>
Date: Tue, 19 Mar 2024 13:46:30 +0000

On Tue, Mar 19, 2024 at 09:37:59AM -0300, Nagaev Boris wrote:
> Hi Peter,
> 
> On Mon, Mar 18, 2024 at 10:24 AM Peter Todd <[email-masked]> wrote:
> > Rule #6 creates a path dependency: the order in which replacement transactions
> > are received determines which transactions are ultimately accepted.
> 
> I'd like to share my thoughts regarding RBFR rules and propose something.
> 
> 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 mempool
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 number
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. You're
talking about all forms of path dependency, including trivial differences where
fees/size are the same and only a txid differs due to a trivial change.

> How can we design such a rule system?
> 
>  1. It must align with miners' incentives; otherwise, it simply won't work.
>  2. And it must not open the door for DoS attacks on the mempool.
> 
> 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.
> 
> 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 bit
of brute forcing to get, say, 2^32 = 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. This
fixes the infinite bandwidth problem, as it's a clear PoW with something like
48 possible total replacements at most (assuming a reasonable amount of total
PoW). But the mempool consensus problem remains unfixed, as there's essentially
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 the
size and/or fees paid. But I think we should persue the idea on the basis that
it makes economic sense. Not that it'll prevent mempools from being out of
consensus.

-- 
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 [email-masked].
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZfmXNiscjatFOOCX%40petertodd.org.