MIME-Version: 1.0
References: <ZXQ8uFLoNlSksalX@petertodd.org>
 <CALZpt+HLoomKZn=QsBZ-4M-WSDzjEA_p1nzk9N=+R4MveeAOFQ@mail.gmail.com>
 <ZX7UHOaUKk/+jbS1@petertodd.org>
In-Reply-To: <ZX7UHOaUKk/+jbS1@petertodd.org>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Thu, 21 Dec 2023 21:59:04 +0000
Message-ID: <CALZpt+Hy+ayawj38Bh3TLZqA3C=G-wGvy_nz9=_5S8-ZZiot7w@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary="000000000000e5cdc5060d0c3545"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement
 Cycling Mitigation
Precedence: list

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

Hi Peter,

> Obviously a local replacement cache is a possibility. The whole point of
my
> email is to show that a local replacement cache isn't necessarily needed,
as
> any alturistic party can implement that cache for all nodes.

Sure, note as soon as you start to introduce an altruistic party
rebroadcasting for everyone in the network, we're talking about a different
security model for time-sensitive second-layers. And unfortunately, one can
expect the same dynamics we're seeing with BIP157 filter servers, a handful
of altruistic nodes for a large swarm of clients.

> 1) That is trivially avoided by only broadcasting txs that meet the local
> mempool min fee, plus some buffer. There's no point to broadcasting txs
that
> aren't going to get mined any time soon.
>
> 2) BIP-133 feefilter avoids this as well, as Bitcoin Core uses the
feefilter
> P2P message to tell peers not to send transactions below a threshold fee
rate.
>
> https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki

I know we can introduce BIP-133 style of filtering here only the top % of
the block template is altruistically rebroadcast. I still think this is an
open question how a second-layer node would discover the "global" mempool
min fee, and note an adversary might inflate the top % of block template to
prevent rebroadcast of malicious HTLC-preimage.

> Did you actually read my email? I worked out the budget required in a
> reasonable worst case scenario:

Yes. I think my uncertainty lies in the fact that an adversary can
rebroadcast _multiple_ times the same UTXO amount under different txids,
occupying all your altruistic bandwidth. Your economic estimation makes an
assumption per-block (i.e 3.125 BTC / 10 minutes). Where it might be
pernicious is that an adversary should be able to reuse those 3.125 BTC of
value for each inter-block time.

Of course, you can introduce an additional rate-limitation per-UTXO, though
I think this is very unsure how this rate-limit would not introduce a new
pinning vector for "honest" counterparty transaction.

> Here, we're talking about an attacker that has financial resources high
enough
> to possibly do 51% attacks. And even in that scenario, storing the entire
> replacement database in RAM costs under $1000

> The reality is such an attack would probably be limited by P2P bandwidth,
not
> financial resources, as 2MB/s of tx traffic would likely leave mempools
in an
> somewhat inconsistent state across the network due to bandwidth
limitations.
> And that is *regardless* of whether or not anyone implements alturistic t=
x
> broadcasting.

Sure, I think we considered bandwidth limitations in the design of the
package relay. Though see my point above, the real difficulty in your
proposed design sounds to me in the ability to reuse the same UTXO
liquidity for an unbounded number of concurrent replacement transactions
exhausting all the altruistic bandwidth.

One can just use a 0.1 BTC UTXO and just fan-out 3.125 BTC of concurrent
replacement transactions from then. So I don't think the assumed adversary
financial resources are accurate.

I think the best long-term way to fix replacement cycling is still more in
the direction of things like:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-December/02219=
1.html

With the additional constraint of removing package malleability, where all
the feerate is coming from package self-contained fee-bumping reserves
UTXOs.

Best,
Antoine

Le dim. 17 d=C3=A9c. 2023 =C3=A0 10:57, Peter Todd <pete@petertodd.org> a =
=C3=A9crit :

> On Fri, Dec 15, 2023 at 10:29:22PM +0000, Antoine Riard wrote:
> > Hi Peter,
> >
> > > Altruistic third parties can partially mitigate replacement cycling(1=
)
> > attacks
> > > by simply rebroadcasting the replaced transactions once the replaceme=
nt
> > cycle
> > > completes. Since the replaced transaction is in fact fully valid, and
> the
> > > "cost" of broadcasting it has been paid by the replacement
> transactions,
> > it can
> > > be rebroadcast by anyone at all, and will propagate in a similar way =
to
> > when it
> > > was initially propagated. Actually implementing this simply requires
> code
> > to be
> > > written to keep track of all replaced transactions, and detect
> > opportunities to
> > > rebroadcast transactions that have since become valid again. Since an=
y
> > > interested third party can do this, the memory/disk space requirement=
s
> of
> > > keeping track of these replacements aren't important; normal nodes ca=
n
> > continue
> > > to operate exactly as they have before.
> >
> > I think there is an alternative to altruistic and periodic rebroadcasti=
ng
> > still solving replacement cycling at the transaction-relay level, namel=
y
> > introducing a local replacement cache.
> >
> > https://github.com/bitcoin/bitcoin/issues/28699
> >
> > One would keep in bounded memory a list of all seen transactions, which
> > have entered our mempool at least once at current mempool min fee.
>
> Obviously a local replacement cache is a possibility. The whole point of =
my
> email is to show that a local replacement cache isn't necessarily needed,
> as
> any alturistic party can implement that cache for all nodes.
>
> > For the full-nodes which cannot afford extensive storage in face of
> > medium-liquidity capable attackers, could imagine replacement cache nod=
es
> > entering into periodic altruistic rebroadcast. This would introduce a
> > tiered hierarchy of full-nodes participating in transaction-relay. I
> think
> > such topology would be more frail in face of any sybil attack or scarce
> > inbound slots connections malicious squatting.
> >
> > The altruistic rebroadcasting default rate could be also a source of
> > amplification attacks, where there is a discrepancy between the feerate
> of
> > the rebroadcast traffic and the current dynamic mempool min fee of the
> > majority of network mempools. As such wasting bandwidth for everyone.
>
> 1) That is trivially avoided by only broadcasting txs that meet the local
> mempool min fee, plus some buffer. There's no point to broadcasting txs
> that
> aren't going to get mined any time soon.
>
> 2) BIP-133 feefilter avoids this as well, as Bitcoin Core uses the
> feefilter
> P2P message to tell peers not to send transactions below a threshold fee
> rate.
>
> https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki
>
> > Assuming some medium-liquidity or high-liquidity attackers might reveal
> any
> > mitigation as insufficient, as an unbounded number of replacement
> > transactions might be issued from a very limited number of UTXOs, all
> > concurrent spends. In the context of multi-party time-sensitive protoco=
l,
> > the highest feerate spend of an "honest" counterparty might fall under
> the
> > lowest concurrent replacement spend of a malicious counterparty,
> occupying
> > all the additional replacement cache storage.
>
> Did you actually read my email? I worked out the budget required in a
> reasonable worst case scenario:
>
> > > Suppose the DoS attacker has a budget equal to 50% of the total block
> > > reward.
> > > That means they can spend 3.125 BTC / 10 minutes, or 520,833sats/s.
> > >
> > >     520,833 sats/s
> > >     -------------- =3D 2,083,332 bytes / s
> > >     0.25 sats/byte
> > >
> > > Even in this absurd case, storing a one day worth of replacements wou=
ld
> > > require
> > > just 172GB of storage. 256GB of RAM costs well under $1000 these days=
,
> > > making
> > > altruistic rebroadcasting a service that could be provided to the
> network
> > > for
> > > just a few thousand dollars worth of hardware even in this absurd cas=
e.
>
> Here, we're talking about an attacker that has financial resources high
> enough
> to possibly do 51% attacks. And even in that scenario, storing the entire
> replacement database in RAM costs under $1000
>
> The reality is such an attack would probably be limited by P2P bandwidth,
> not
> financial resources, as 2MB/s of tx traffic would likely leave mempools i=
n
> an
> somewhat inconsistent state across the network due to bandwidth
> limitations.
> And that is *regardless* of whether or not anyone implements alturistic t=
x
> broadcasting.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>

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

<div dir=3D"ltr">Hi Peter,<div><br></div><div>&gt; Obviously a local replac=
ement cache is a possibility. The whole point of my<br>&gt; email is to sho=
w that a local replacement cache isn&#39;t necessarily needed, as<br>&gt; a=
ny alturistic party can implement that cache for all nodes.<br></div><div><=
br></div><div>Sure, note as soon as you start to introduce an altruistic pa=
rty rebroadcasting for everyone in the network, we&#39;re talking about a d=
ifferent security model for time-sensitive second-layers. And unfortunately=
, one can expect the same dynamics we&#39;re seeing with BIP157 filter serv=
ers, a handful of altruistic nodes for a large swarm of clients.</div><div>=
<br></div><div>&gt; 1) That is trivially avoided by only broadcasting txs t=
hat meet the local<br>&gt; mempool min fee, plus some buffer. There&#39;s n=
o point to broadcasting txs that<br>&gt; aren&#39;t going to get mined any =
time soon.<br>&gt;<br>&gt; 2) BIP-133 feefilter avoids this as well, as Bit=
coin Core uses the feefilter<br>&gt; P2P message to tell peers not to send =
transactions below a threshold fee rate.<br>&gt;<br>&gt;=C2=A0<a href=3D"ht=
tps://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki" rel=3D"norefe=
rrer" target=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-013=
3.mediawiki</a><br></div><div><br></div><div>I know we can introduce BIP-13=
3 style of filtering here only the top % of the block template is altruisti=
cally rebroadcast. I still think this is an open question how a second-laye=
r node would discover the &quot;global&quot; mempool min fee, and note an a=
dversary might inflate the top % of block template to prevent rebroadcast o=
f malicious HTLC-preimage.</div><div><br></div><div>&gt; Did you actually r=
ead my email? I worked out the budget required in a<br>&gt; reasonable wors=
t case scenario:<br></div><div><br></div><div>Yes. I think my uncertainty l=
ies in the fact that an adversary can rebroadcast _multiple_ times the same=
 UTXO amount under different txids, occupying all your altruistic bandwidth=
. Your economic estimation makes an assumption per-block (i.e 3.125 BTC / 1=
0 minutes). Where it might be pernicious is that an adversary should be abl=
e to reuse those 3.125 BTC of value for each inter-block time.</div><div><b=
r></div><div>Of course, you can introduce an additional rate-limitation per=
-UTXO, though I think this is very unsure how this rate-limit would not int=
roduce a new pinning vector for &quot;honest&quot; counterparty transaction=
.</div><div><br></div><div>&gt; Here, we&#39;re talking about an attacker t=
hat has financial resources high enough<br>&gt; to possibly do 51% attacks.=
 And even in that scenario, storing the entire<br>&gt; replacement database=
 in RAM costs under $1000<br><br>&gt; The reality is such an attack would p=
robably be limited by P2P bandwidth, not<br>&gt; financial resources, as 2M=
B/s of tx traffic would likely leave mempools in an<br>&gt; somewhat incons=
istent state across the network due to bandwidth limitations.<br>&gt; And t=
hat is *regardless* of whether or not anyone implements alturistic tx<br>&g=
t; broadcasting.<br></div><div><br></div><div>Sure, I think we considered b=
andwidth limitations in the design of the package relay. Though see my poin=
t above, the real difficulty in your proposed design sounds to me in the ab=
ility to reuse the same UTXO liquidity for an unbounded number of concurren=
t replacement transactions exhausting all the altruistic bandwidth.</div><d=
iv><br></div><div>One can just use a 0.1 BTC UTXO and just fan-out 3.125 BT=
C of concurrent replacement transactions from then. So I don&#39;t think th=
e assumed adversary financial resources are accurate.</div><div><br></div><=
div>I think the best long-term way to fix replacement cycling is still more=
 in the direction of things like:</div><div><a href=3D"https://lists.linuxf=
oundation.org/pipermail/bitcoin-dev/2023-December/022191.html">https://list=
s.linuxfoundation.org/pipermail/bitcoin-dev/2023-December/022191.html</a></=
div><div><br></div><div>With the additional constraint of removing package =
malleability, where all the feerate is coming from package self-contained f=
ee-bumping reserves UTXOs.</div><div><br></div><div>Best,</div><div>Antoine=
=C2=A0</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"=
gmail_attr">Le=C2=A0dim. 17 d=C3=A9c. 2023 =C3=A0=C2=A010:57, Peter Todd &l=
t;<a href=3D"mailto:pete@petertodd.org">pete@petertodd.org</a>&gt; a =C3=A9=
crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-col=
or:rgb(204,204,204);padding-left:1ex">On Fri, Dec 15, 2023 at 10:29:22PM +0=
000, Antoine Riard wrote:<br>
&gt; Hi Peter,<br>
&gt; <br>
&gt; &gt; Altruistic third parties can partially mitigate replacement cycli=
ng(1)<br>
&gt; attacks<br>
&gt; &gt; by simply rebroadcasting the replaced transactions once the repla=
cement<br>
&gt; cycle<br>
&gt; &gt; completes. Since the replaced transaction is in fact fully valid,=
 and the<br>
&gt; &gt; &quot;cost&quot; of broadcasting it has been paid by the replacem=
ent transactions,<br>
&gt; it can<br>
&gt; &gt; be rebroadcast by anyone at all, and will propagate in a similar =
way to<br>
&gt; when it<br>
&gt; &gt; was initially propagated. Actually implementing this simply requi=
res code<br>
&gt; to be<br>
&gt; &gt; written to keep track of all replaced transactions, and detect<br=
>
&gt; opportunities to<br>
&gt; &gt; rebroadcast transactions that have since become valid again. Sinc=
e any<br>
&gt; &gt; interested third party can do this, the memory/disk space require=
ments of<br>
&gt; &gt; keeping track of these replacements aren&#39;t important; normal =
nodes can<br>
&gt; continue<br>
&gt; &gt; to operate exactly as they have before.<br>
&gt; <br>
&gt; I think there is an alternative to altruistic and periodic rebroadcast=
ing<br>
&gt; still solving replacement cycling at the transaction-relay level, name=
ly<br>
&gt; introducing a local replacement cache.<br>
&gt; <br>
&gt; <a href=3D"https://github.com/bitcoin/bitcoin/issues/28699" rel=3D"nor=
eferrer" target=3D"_blank">https://github.com/bitcoin/bitcoin/issues/28699<=
/a><br>
&gt; <br>
&gt; One would keep in bounded memory a list of all seen transactions, whic=
h<br>
&gt; have entered our mempool at least once at current mempool min fee.<br>
<br>
Obviously a local replacement cache is a possibility. The whole point of my=
<br>
email is to show that a local replacement cache isn&#39;t necessarily neede=
d, as<br>
any alturistic party can implement that cache for all nodes.<br>
<br>
&gt; For the full-nodes which cannot afford extensive storage in face of<br=
>
&gt; medium-liquidity capable attackers, could imagine replacement cache no=
des<br>
&gt; entering into periodic altruistic rebroadcast. This would introduce a<=
br>
&gt; tiered hierarchy of full-nodes participating in transaction-relay. I t=
hink<br>
&gt; such topology would be more frail in face of any sybil attack or scarc=
e<br>
&gt; inbound slots connections malicious squatting.<br>
&gt; <br>
&gt; The altruistic rebroadcasting default rate could be also a source of<b=
r>
&gt; amplification attacks, where there is a discrepancy between the feerat=
e of<br>
&gt; the rebroadcast traffic and the current dynamic mempool min fee of the=
<br>
&gt; majority of network mempools. As such wasting bandwidth for everyone.<=
br>
<br>
1) That is trivially avoided by only broadcasting txs that meet the local<b=
r>
mempool min fee, plus some buffer. There&#39;s no point to broadcasting txs=
 that<br>
aren&#39;t going to get mined any time soon.<br>
<br>
2) BIP-133 feefilter avoids this as well, as Bitcoin Core uses the feefilte=
r<br>
P2P message to tell peers not to send transactions below a threshold fee ra=
te.<br>
<br>
<a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki" =
rel=3D"noreferrer" target=3D"_blank">https://github.com/bitcoin/bips/blob/m=
aster/bip-0133.mediawiki</a><br>
<br>
&gt; Assuming some medium-liquidity or high-liquidity attackers might revea=
l any<br>
&gt; mitigation as insufficient, as an unbounded number of replacement<br>
&gt; transactions might be issued from a very limited number of UTXOs, all<=
br>
&gt; concurrent spends. In the context of multi-party time-sensitive protoc=
ol,<br>
&gt; the highest feerate spend of an &quot;honest&quot; counterparty might =
fall under the<br>
&gt; lowest concurrent replacement spend of a malicious counterparty, occup=
ying<br>
&gt; all the additional replacement cache storage.<br>
<br>
Did you actually read my email? I worked out the budget required in a<br>
reasonable worst case scenario:<br>
<br>
&gt; &gt; Suppose the DoS attacker has a budget equal to 50% of the total b=
lock<br>
&gt; &gt; reward.<br>
&gt; &gt; That means they can spend 3.125 BTC / 10 minutes, or 520,833sats/=
s.<br>
&gt; &gt;<br>
&gt; &gt;=C2=A0 =C2=A0 =C2=A0520,833 sats/s<br>
&gt; &gt;=C2=A0 =C2=A0 =C2=A0-------------- =3D 2,083,332 bytes / s<br>
&gt; &gt;=C2=A0 =C2=A0 =C2=A00.25 sats/byte<br>
&gt; &gt;<br>
&gt; &gt; Even in this absurd case, storing a one day worth of replacements=
 would<br>
&gt; &gt; require<br>
&gt; &gt; just 172GB of storage. 256GB of RAM costs well under $1000 these =
days,<br>
&gt; &gt; making<br>
&gt; &gt; altruistic rebroadcasting a service that could be provided to the=
 network<br>
&gt; &gt; for<br>
&gt; &gt; just a few thousand dollars worth of hardware even in this absurd=
 case.<br>
<br>
Here, we&#39;re talking about an attacker that has financial resources high=
 enough<br>
to possibly do 51% attacks. And even in that scenario, storing the entire<b=
r>
replacement database in RAM costs under $1000<br>
<br>
The reality is such an attack would probably be limited by P2P bandwidth, n=
ot<br>
financial resources, as 2MB/s of tx traffic would likely leave mempools in =
an<br>
somewhat inconsistent state across the network due to bandwidth limitations=
.<br>
And that is *regardless* of whether or not anyone implements alturistic tx<=
br>
broadcasting.<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>

--000000000000e5cdc5060d0c3545--