Delivery-date: Wed, 27 Mar 2024 12:18:44 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of antoine.riard@gmail.com designates 2607:f8b0:4864:20::d36 as permitted sender) client-ip=2607:f8b0:4864:20::d36;
MIME-Version: 1.0
References: <Zfg/6IZyA/iInyMx@petertodd.org> <0a377ddb-b001-41ba-9208-27b3fa059bb5n@googlegroups.com>
 <ZgQZUOCc/dSjKMoL@petertodd.org>
In-Reply-To: <ZgQZUOCc/dSjKMoL@petertodd.org>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Wed, 27 Mar 2024 19:17:24 +0000
Message-ID: <CALZpt+GOCiwYdK4vfkODrT0Sx6HxCAuvhVqa1c5o3Xjy03OiAQ@mail.gmail.com>
Subject: Re: [bitcoindev] Re: A Free-Relay Attack Exploiting RBF Rule #6
To: Peter Todd <pete@petertodd.org>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="0000000000005c28910614a9425b"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--0000000000005c28910614a9425b
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Peter,

Answering the latest 2 emails.

> Since this attack is just a relatively minor extension of existing,
publicly
> disclosed, attacks, I don't think there was any need for formal disclosur=
e
> timelines. It's interesting that the attack exists; it does not
substantially
> change the status quo.

Of course, it's always a matter of appreciation when an attack should get a
formal
disclosure process and when it can be publicized with minimal process
effort.
Given this class of attacks was already known from some experts, I don't
think it
requires a formal process either. Attaching a timeline to a disclosure
email doesn't hurt.

> I don't believe the other attacks in this attack class are even possible
to
fix. We just have to live with the fact that a degree of free relay is
always
going to be possible.

See comments under proof-of-UTXO ownership as plausible mitigations.

In anway, I think this is not the type of fixes we can land in a covert
fashion given the
order of magnitude of engineering effort and potential tx-relay network
impact.

> Can you explain in more detail how exactly you'd pull that off? Are you
aware
of LN implementations that actually create feerate ascending LN states?

I think you can create feerates ascending LN states with today's LN
implementations by playing with BOLT2's `dust_limit_satoshis`.
State 1 has 1 dust HTLC trimmed, state 2 has 2 dust HTLCs trimmed, ...
State N has N dust HTLCs trimmed.

> Imagine if the mempool size was 1TB, an amount larger than the entire BTC
> blocksize to date. I think that example helps make it obvious that with
such an
> enormous mempool, there *must* be free relay attacks, because it's simply
> impossible for all broadcast transactions to even get mined.

I think there is an interesting distinction that can be made between
mempool size
ressources dedicated to increase block template efficiency and minimum
mempool size
to just ensure you have good BIP152 compact block validation time.
Obviously if you're
aiming for the first, you're incentivized to offer "free-relay" bandwidth
to your peers and
increase your view of the ongoing transaction traffic.

> All the existing replacement mechanisms _are_ basically a proof-of-UTXO
> ownership, because they're transactions spending UTXOs. The only question
is
> the details of how that proof works.

Yeah somehow it's correct that any replacement mechanisms encompass a
proof-of-UTXO
ownership mechanism. Yet in a world you can partition mempool like you show
with your
for example, it's easy to make this proof-of-UTXO economically unpaid by
the attacker. Asking
aged UTXOs attached to a replacement candidate could be make such proof
more robust, in
my understanding.

Best,
Antoine


Le mer. 27 mars 2024 =C3=A0 13:04, Peter Todd <pete@petertodd.org> a =C3=A9=
crit :

> On Fri, Mar 22, 2024 at 04:18:18PM -0700, Antoine Riard wrote:
> > Hi Peter,
> >
> > > The marginal cost to an attacker who was planning on broadcasting B
> > anyway is
> > > fairly small, as provided that sufficiently small fee-rates are chose=
n
> > for A_n,
> > > the probability of A_n being mined is low. The attack does of course
> > require
> > > capital, as the attacker needs to have UTXO's of sufficient size for
> A_n.
> >
> > I think an attacker does not necessarily need to have a UTXO's of
> > sufficient size for A_n.
> > One could reuse feerate ascending old LN states, where the balance on
> > latest states is
> > in favor of your counterparty. So it might be a lower assumption on
> > attacker ressources,
> > you only needs to have been _allocate_ a shared-UTXO in the past.
>
> Can you explain in more detail how exactly you'd pull that off? Are you
> aware
> of LN implementations that actually create feerate ascending LN states?
>
> > > The larger the mempool size limit, the more
> > > effective the attack tends to be. Similarly, the attack is more
> effective
> > with
> > > a larger size difference between A and B. Finally, the attack is more
> > effective
> > > with a smaller minimum incremental relay fee, as more individual
> versions
> > of
> > > the transaction can be broadcast for a given fee-delta range.
> >
> > I think the observation on larger the mempool size, more effective the
> > attack tends
> > to come as a novel insight to me. Naively, in a world where the future
> > blockspace
> > demand is uncertain, miners have an incentive to scale up their mempool
> > size limit.
> > As such, holding a cache of non-mined low-feerates transactions. The
> type
> > of bandwidth,
> > denial-of-service described sounds effectively to affect more full-node=
s
> > with large
> > mempools. Fair point, it's expected they have more bandwidth ressources
> > available too.
>
> Imagine if the mempool size was 1TB, an amount larger than the entire BTC
> blocksize to date. I think that example helps make it obvious that with
> such an
> enormous mempool, there *must* be free relay attacks, because it's simply
> impossible for all broadcast transactions to even get mined.
>
> > Commenting on this, do we have a free-relay attack variant where an
> > attacker with reasonable
> > visibility on the transaction-relay network could exploit propagation
> > asymmetries due to
> > *_INVENTORY_BROADCAST_INTERVAL and re-inject A_n traffic in a targeted
> > fashion ?
> > I don't think it's worst than the parallelization you're describing,
> it's
> > just another approach.
>
> Well, whether or not that is an attack depends on how exactly the
> transcation
> could be rebroadcast.
>
> > > Requiring replacements to increase the fee-rate by a certain ratio
> would
> > also
> > > mitigate the attack. However doing so would break a lot of wallet
> > software that
> > > bumps fees by values equal or close to the minimum relay fee.
> >
> > I think there is still the open questions of the economic relevance of
> > replace-by-fee if
> > the local mempool is completely empty. Here a miner is optimizing to
> > maximize absolute
> > fee as a transaction replaced by a higher-feerate, lower fee is less
> > interesting if you have
> > less than 1 MB virtual bytes / 4 MB WU.
>
> Obviously. That's why I proposed one-shot replace-by-fee-rate. Not pure
> replace-by-fee-rate.
>
> > > Ironically, the existence of this attack is an argument in favor of
> > > replace-by-fee-rate. While RBFR introduces a degree of free-relay, th=
e
> > fact
> > > that Bitcoin Core's existing rules *also* allow for free-relay in thi=
s
> > form
> > > makes the difference inconsequential.
> >
> > Back on the point where an attacker ability to provoke bandwidth DoS in
> > considerations
> > of the UTXO-amount available, a minimal absolute fee as a proof of
> owning
> > some UTXO
> > amount could be still maintained (or maybe after a _bounded_ number of
> > replacement under
> > a given block period).
> >
> > We studied proof-of-UTXO ownership as a p2p DoS mitigation approach in
> the
> > past with Gleb:
> >
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-November/0=
02884.html
>
> All the existing replacement mechanisms _are_ basically a proof-of-UTXO
> ownership, because they're transactions spending UTXOs. The only question
> is
> the details of how that proof works.
>
> --
> 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/CALZpt%2BGOCiwYdK4vfkODrT0Sx6HxCAuvhVqa1c5o3Xjy03OiAQ%40mail.gma=
il.com.

--0000000000005c28910614a9425b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Peter,<div><br></div><div>Answering the latest 2 emails=
.</div><div><br></div><div>&gt; Since this attack is just a relatively mino=
r extension of existing, publicly<br>&gt; disclosed, attacks, I don&#39;t t=
hink there was any need for formal disclosure<br>&gt; timelines. It&#39;s i=
nteresting that the attack exists; it does not substantially<br>&gt; change=
 the status quo.<br><br><div>Of course, it&#39;s always a matter of appreci=
ation when an attack should get a formal</div><div>disclosure process and w=
hen it can be publicized with minimal process effort.</div><div>Given this =
class of attacks was already known from some experts, I don&#39;t think it<=
/div><div>requires a formal process either. Attaching a timeline to a discl=
osure email doesn&#39;t hurt.</div></div><div><br></div><div>&gt; I don&#39=
;t believe the other attacks in this attack class are even possible to</div=
>fix. We just have to live with the fact that a degree of free relay is alw=
ays<br>going to be possible.<div><br></div><div>See comments under proof-of=
-UTXO ownership as plausible mitigations.</div><div><br></div><div>In anway=
, I think this is not the type of fixes we can land in a covert fashion giv=
en the</div><div>order of magnitude of engineering effort and potential tx-=
relay network impact.</div><div><div><br></div><div>&gt; Can you explain in=
 more detail how exactly you&#39;d pull that off? Are you aware</div>of LN =
implementations that actually create feerate ascending LN states?<div><br><=
/div><div>I think you can create=C2=A0feerates ascending LN states with tod=
ay&#39;s LN implementations by playing with BOLT2&#39;s `dust_limit_satoshi=
s`.</div><div>State 1 has 1 dust HTLC trimmed, state 2 has 2 dust HTLCs tri=
mmed, ... State N has N dust HTLCs trimmed.</div><div><br></div><div>&gt; I=
magine if the mempool size was 1TB, an amount larger than the entire BTC<br=
>&gt; blocksize to date. I think that example helps make it obvious that wi=
th such an<br>&gt; enormous mempool, there *must* be free relay attacks, be=
cause it&#39;s simply<br>&gt; impossible for all broadcast transactions to =
even get mined.<br></div><div><br></div><div>I think there is an interestin=
g distinction that can be made between mempool size</div><div>ressources de=
dicated to increase block template efficiency and minimum mempool size</div=
><div>to just ensure you have good BIP152 compact block validation time. Ob=
viously if you&#39;re</div><div>aiming for the first, you&#39;re incentiviz=
ed to offer &quot;free-relay&quot; bandwidth to your peers and</div><div>in=
crease your view of the ongoing transaction traffic.</div><div><br></div><d=
iv>&gt; All the existing replacement mechanisms _are_ basically a proof-of-=
UTXO<br>&gt; ownership, because they&#39;re transactions spending UTXOs. Th=
e only question is<br>&gt; the details of how that proof works.<br></div><d=
iv><br></div><div>Yeah somehow it&#39;s correct that any replacement=C2=A0m=
echanisms encompass a proof-of-UTXO</div><div>ownership mechanism. Yet in a=
 world you can partition mempool like you show with your</div><div>for exam=
ple, it&#39;s easy to make this proof-of-UTXO economically unpaid by the at=
tacker. Asking</div><div>aged UTXOs attached to a replacement candidate cou=
ld be make such proof more robust, in</div><div>my understanding.</div><div=
><br></div><div>Best,</div><div>Antoine</div><div><br></div></div></div><br=
><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0m=
er. 27 mars 2024 =C3=A0=C2=A013:04, Peter Todd &lt;<a href=3D"mailto:pete@p=
etertodd.org">pete@petertodd.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-=
width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);paddin=
g-left:1ex">On Fri, Mar 22, 2024 at 04:18:18PM -0700, Antoine Riard wrote:<=
br>
&gt; Hi Peter,<br>
&gt; <br>
&gt; &gt; The marginal cost to an attacker who was planning on broadcasting=
 B <br>
&gt; anyway is <br>
&gt; &gt; fairly small, as provided that sufficiently small fee-rates are c=
hosen <br>
&gt; for A_n, <br>
&gt; &gt; the probability of A_n being mined is low. The attack does of cou=
rse <br>
&gt; require <br>
&gt; &gt; capital, as the attacker needs to have UTXO&#39;s of sufficient s=
ize for A_n.<br>
&gt; <br>
&gt; I think an attacker does not necessarily need to have a UTXO&#39;s of =
<br>
&gt; sufficient size for A_n.<br>
&gt; One could reuse feerate ascending old LN states, where the balance on =
<br>
&gt; latest states is<br>
&gt; in favor of your counterparty. So it might be a lower assumption on <b=
r>
&gt; attacker ressources,<br>
&gt; you only needs to have been _allocate_ a shared-UTXO in the past.<br>
<br>
Can you explain in more detail how exactly you&#39;d pull that off? Are you=
 aware<br>
of LN implementations that actually create feerate ascending LN states?<br>
<br>
&gt; &gt; The larger the mempool size limit, the more <br>
&gt; &gt; effective the attack tends to be. Similarly, the attack is more e=
ffective <br>
&gt; with <br>
&gt; &gt; a larger size difference between A and B. Finally, the attack is =
more <br>
&gt; effective <br>
&gt; &gt; with a smaller minimum incremental relay fee, as more individual =
versions <br>
&gt; of <br>
&gt; &gt; the transaction can be broadcast for a given fee-delta range.<br>
&gt; <br>
&gt; I think the observation on larger the mempool size, more effective the=
 <br>
&gt; attack tends<br>
&gt; to come as a novel insight to me. Naively, in a world where the future=
 <br>
&gt; blockspace<br>
&gt; demand is uncertain, miners have an incentive to scale up their mempoo=
l <br>
&gt; size limit.<br>
&gt; As such, holding a cache of non-mined low-feerates transactions. The t=
ype <br>
&gt; of bandwidth,<br>
&gt; denial-of-service described sounds effectively to affect more full-nod=
es <br>
&gt; with large <br>
&gt; mempools. Fair point, it&#39;s expected they have more bandwidth resso=
urces <br>
&gt; available too.<br>
<br>
Imagine if the mempool size was 1TB, an amount larger than the entire BTC<b=
r>
blocksize to date. I think that example helps make it obvious that with suc=
h an<br>
enormous mempool, there *must* be free relay attacks, because it&#39;s simp=
ly<br>
impossible for all broadcast transactions to even get mined.<br>
<br>
&gt; Commenting on this, do we have a free-relay attack variant where an <b=
r>
&gt; attacker with reasonable<br>
&gt; visibility on the transaction-relay network could exploit propagation =
<br>
&gt; asymmetries due to<br>
&gt; *_INVENTORY_BROADCAST_INTERVAL and re-inject A_n traffic in a targeted=
 <br>
&gt; fashion ?<br>
&gt; I don&#39;t think it&#39;s worst than the parallelization you&#39;re d=
escribing, it&#39;s <br>
&gt; just another approach.<br>
<br>
Well, whether or not that is an attack depends on how exactly the transcati=
on<br>
could be rebroadcast.<br>
<br>
&gt; &gt; Requiring replacements to increase the fee-rate by a certain rati=
o would <br>
&gt; also <br>
&gt; &gt; mitigate the attack. However doing so would break a lot of wallet=
 <br>
&gt; software that <br>
&gt; &gt; bumps fees by values equal or close to the minimum relay fee.<br>
&gt; <br>
&gt; I think there is still the open questions of the economic relevance of=
 <br>
&gt; replace-by-fee if<br>
&gt; the local mempool is completely empty. Here a miner is optimizing to <=
br>
&gt; maximize absolute<br>
&gt; fee as a transaction replaced by a higher-feerate, lower fee is less <=
br>
&gt; interesting if you have<br>
&gt; less than 1 MB virtual bytes / 4 MB WU.<br>
<br>
Obviously. That&#39;s why I proposed one-shot replace-by-fee-rate. Not pure=
<br>
replace-by-fee-rate.<br>
<br>
&gt; &gt; Ironically, the existence of this attack is an argument in favor =
of <br>
&gt; &gt; replace-by-fee-rate. While RBFR introduces a degree of free-relay=
, the <br>
&gt; fact <br>
&gt; &gt; that Bitcoin Core&#39;s existing rules *also* allow for free-rela=
y in this <br>
&gt; form <br>
&gt; &gt; makes the difference inconsequential.<br>
&gt; <br>
&gt; Back on the point where an attacker ability to provoke bandwidth DoS i=
n <br>
&gt; considerations<br>
&gt; of the UTXO-amount available, a minimal absolute fee as a proof of own=
ing <br>
&gt; some UTXO<br>
&gt; amount could be still maintained (or maybe after a _bounded_ number of=
 <br>
&gt; replacement under<br>
&gt; a given block period).<br>
&gt; <br>
&gt; We studied proof-of-UTXO ownership as a p2p DoS mitigation approach in=
 the <br>
&gt; past with Gleb:<br>
&gt; <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-dev/2=
020-November/002884.html" rel=3D"noreferrer" target=3D"_blank">https://list=
s.linuxfoundation.org/pipermail/lightning-dev/2020-November/002884.html</a>=
<br>
<br>
All the existing replacement mechanisms _are_ basically a proof-of-UTXO<br>
ownership, because they&#39;re transactions spending UTXOs. The only questi=
on is<br>
the details of how that proof works.<br>
<br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/CALZpt%2BGOCiwYdK4vfkODrT0Sx6HxCAuvhVqa1c5o3Xjy03OiAQ=
%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.go=
ogle.com/d/msgid/bitcoindev/CALZpt%2BGOCiwYdK4vfkODrT0Sx6HxCAuvhVqa1c5o3Xjy=
03OiAQ%40mail.gmail.com</a>.<br />

--0000000000005c28910614a9425b--