Subject: Re: [bitcoindev] Over Half of Replace-by-Fee-Rate Replacements Are Mined

From: Nagaev Boris <[email-masked]>
Date: Sat, 24 Feb 2024 17:54:52 -0300

On Sat, Feb 24, 2024 at 3:45 PM Peter Todd <[email-masked]> wrote:
>
> On Sat, Feb 24, 2024 at 02:55:26PM -0300, Nagaev Boris wrote:
> > > I recently released a [prototype Libre Relay fork](https://github.com/petertodd/bitcoin/tree/libre-relay-v26.0) of Bitcoin Core v26.0, that among
> > > other things, implements [Pure Replace-By-Fee-Rate](/2024/one-shot-replace-by-fee-rate#pure-replace-by-fee-rate) (RBFR)
> > > with a 2x ratio. This means that transactions will be replaced if the fee-rate
> > > of the new transaction is at least 2x higher than the old transaction(s), even
> > > if the absolute fee is lower.
> >
> > I like the idea of pure replacement by fee rate, but I'm not sure
> > about the 2x coefficient. I'm afraid it can result in overpaying.
> >
> > What is the purpose of the 2x coefficient? Is it needed to prevent DoS
> > by continuously increasing feerate by a fraction of a percent? Isn't
> > 1.1x enough to prevent this DoS vector? A rise from 100 sats/byte to
> > 110 sats/byte is easier to bear, then a rise from 100 to 200,
> > especially if the next block feerate is 105.
>
> The coefficient is a trade-off between overpaying and DoS attack cost. The
> smaller the coefficient, the more replacements that can be done:
>
> 2^10    = 1024
> 1.5^10  = 58
> 1.25^10 = 9.3
> 1.1^10  = 2.6

Very interesting!

To assess the number of DoS replacements, given RBFR is implemented
with coefficient K, we need to know the following two numbers,
available on mempool.space front page:

 - Purging feerate (P)
 - Next block feerate (N)

For an attacker, to cause the most number of replacements, it is
rational to first introduce a tx with fee rate just above purging
feerate and then increase its feerate by K times until it reaches next
block feerate (N).

So the number of replacements he can successfully cause paying price N
per byte is:

floor(log(K, N/P))

Currently N=11, P=1.13 (satoshis/byte).
For K=2 the number of replacements is 3.
For K=1.25 it is 10.
For K=1.1 it is 23.

It would be valuable to get access to archival values of Purging
feerate and Next block feerate. Knowing max(N/P) over the whole time
is needed to know the exact number of replacements for an attack in
the worst case in the past.

The strength of a DoS attack is proportional to 1/log(K).
So the price of a DoS attack is proportional to log(K).
The price of RBFR for a legitimate user is proportional to K - 1 - N /
R, where N is the Next block feerate at RBF time and R is the feerate
at which the tx was previously broadcasted (originally or previous
RBF).

Another piece of data which would be very valuable are N and R for
historical RBF events. If K is set to median N / R, then RBFR would
cost nothing to the average legitimate user and cost something to an
attacker, which is a good thing.

> I picked 2x for the prototype because it's:
>
> 1) A safe default that makes DoS attacks _very_ expensive.
> 2) Low enough that the primary purpose of preventing pinning attacks still
>    works.
> 3) High enough to be clearly incentive compatible for miners.
> 4) A ratio that's easy to implement with addition.
>
> The last reason is kinda funny... CFeeRate in Bitcoin Core v26.0 doesn't
> support multiplication or division operations. So I implemented the 2x ratio by
> just adding a fee-rate to itself.

Yeah, it is funny :-)

By the way, K=1.25 is also easy to implement using just additions:

bool enough_increase(CFeeRate oldrate, newrate) {
  auto oldx2 = oldrate + oldrate;
  auto oldx5 = oldx2 + oldx2 + oldrate;
  auto newx2 = newrate + newrate;
  auto newx4 = newx2 + newx2;
  return newx4 >= oldx5;
}

Also CFeeRate supports integer multiplication, so it can be simplified as:

bool enough_increase(CFeeRate oldrate, newrate) {
  return (4 * newrate) >= (5 * oldrate);
}

> Personally, I think 1.25 would be a reasonable ratio. But I wanted to release a
> conservative version first to minimize the impact of DoS attacks.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org

-- 
Best regards,
Boris Nagaev

-- 
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/CAFC_Vt4icK4RMm2UgqsgoV2Qude7e8ThL%2B3Hm%2B9DXfB0BgC6ZQ%40mail.gmail.com.