Delivery-date: Sat, 24 Feb 2024 14:54:05 -0800
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of bnagaev@gmail.com designates 2607:f8b0:4864:20::12d as permitted sender) client-ip=2607:f8b0:4864:20::12d;
MIME-Version: 1.0
References: <ZdoSP+Z/f17TYOD+@petertodd.org> <CAFC_Vt5TSjGVk58o5G8aW4Jt4aJyDQvR9yE4eLvtB1t+m1jrYg@mail.gmail.com>
 <Zdo5VZIu3gU5wVQM@petertodd.org>
In-Reply-To: <Zdo5VZIu3gU5wVQM@petertodd.org>
From: Nagaev Boris <bnagaev@gmail.com>
Date: Sat, 24 Feb 2024 17:54:52 -0300
Message-ID: <CAFC_Vt4icK4RMm2UgqsgoV2Qude7e8ThL+3Hm+9DXfB0BgC6ZQ@mail.gmail.com>
Subject: Re: [bitcoindev] Over Half of Replace-by-Fee-Rate Replacements Are Mined
To: Peter Todd <pete@petertodd.org>
Cc: bitcoindev@googlegroups.com
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

On Sat, Feb 24, 2024 at 3:45=E2=80=AFPM Peter Todd <pete@petertodd.org> wro=
te:
>
> 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 amon=
g
> > > other things, implements [Pure Replace-By-Fee-Rate](/2024/one-shot-re=
place-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. Th=
e
> smaller the coefficient, the more replacements that can be done:
>
> 2^10    =3D 1024
> 1.5^10  =3D 58
> 1.25^10 =3D 9.3
> 1.1^10  =3D 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=3D11, P=3D1.13 (satoshis/byte).
For K=3D2 the number of replacements is 3.
For K=3D1.25 it is 10.
For K=3D1.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 stil=
l
>    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 ra=
tio by
> just adding a fee-rate to itself.

Yeah, it is funny :-)

By the way, K=3D1.25 is also easy to implement using just additions:

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

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

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

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


--=20
Best regards,
Boris Nagaev

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