MIME-Version: 1.0
References: <ZXQ8uFLoNlSksalX@petertodd.org>
In-Reply-To: <ZXQ8uFLoNlSksalX@petertodd.org>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Fri, 15 Dec 2023 22:29:22 +0000
Message-ID: <CALZpt+HLoomKZn=QsBZ-4M-WSDzjEA_p1nzk9N=+R4MveeAOFQ@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000395f1a060c93ef05"
Subject: Re: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement
 Cycling Mitigation
Precedence: list

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

Hi Peter,

> Altruistic third parties can partially mitigate replacement cycling(1)
attacks
> by simply rebroadcasting the replaced transactions once the replacement
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 any
> interested third party can do this, the memory/disk space requirements of
> keeping track of these replacements aren't important; normal nodes can
continue
> to operate exactly as they have before.

I think there is an alternative to altruistic and periodic rebroadcasting
still solving replacement cycling at the transaction-relay level, namely
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.

For the full-nodes which cannot afford extensive storage in face of
medium-liquidity capable attackers, could imagine replacement cache nodes
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.

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 protocol,
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.

Best,
Antoine

Le sam. 9 d=C3=A9c. 2023 =C3=A0 10:09, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> While this seems like a reasonably obvious idea, I couldn't find a previo=
us
> example of it published on bitcoin-dev or elsewhere. So for the ability t=
o
> cite
> it, I'll publish it now.
>
>
> # Summary
>
> Altruistic third parties can partially mitigate replacement cycling(1)
> attacks
> by simply rebroadcasting the replaced transactions once the replacement
> 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 any
> interested third party can do this, the memory/disk space requirements of
> keeping track of these replacements aren't important; normal nodes can
> continue
> to operate exactly as they have before.
>
>
> # Background
>
> To recall, a replacement cycling attack has three basic stages:
>
> 0) Target transaction tx0_a is broadcast, spending one or more outputs
> 1) Attacker broadcasts double-spend tx0_b, spending an additional output
>    under the attacker's control
> 2) Attacker broadcasts double-spend tx1, double-spending only the
> additional
>    input, resulting in the original input set not being spent
>
> Replacement cycling is a potential threat any time two or more parties
> have the
> ability to spend a single txout, and rendering that output _unspent_ is
> harmful. For example, replacement cycling is an attack on lightning HTLCs=
,
> because it can result in an HTLC pre-image not being observed by a party
> until
> after the HTLC expires. Similarly, replacement cycling is a potential
> attack on
> signatureless anchor outputs, as it can allow third parties to revoke a
> CPFP
> anchor spend, making the parent transaction(s) unminable.
>
>
> # Altruistic Rebroadcasting
>
> Bitcoin Core keeps no records of replaced transactions. Thus after the
> replacement cycling attack is complete, tx0_a has been entirely purged
> from a
> Bitcoin Core node's mempool, and all inputs to tx0_a are unspent. Thus it
> is
> just as valid to broadcast as before.
>
>
> ## Resources Required
>
> Let's suppose we have a DoS attacker who is constantly broadcasting
> replacement
> in an effort to overwhelm nodes performing altruistic rebroadcasting. The
> BIP-125 RBF rules require that a replacement transaction pay for the
> bandwidth
> used by the replacement. On Bitcoin Core, this defaults to 1sat/vByte.
> Assuming
> the attacking transactions are ~100% witness bytes, that is ~0.25sats/byt=
e
> of
> relay bandwidth per peer.
>
> 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 would
> 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 case.
>
> It's notable that miners may in fact want to run replacement rebroadcasti=
ng
> software themselves, to ensure they are not missing any valid, profitable=
,
> transactions. In the context of a large mining pool, the additional cost
> over
> running a regular node may be affordable.
>
>
> ## Limitations
>
> At the moment, Bitcoin Core propagates transactions purely via INV
> announcements; there is no set reconciliation mechanism to synchronize
> mempools
> between peers. If an INV announcement is missed for some reason, it's qui=
te
> possible that the transaction will be missed. Thus rebroadcasting may be
> defeated if the % of nodes who do *not* have the transaction at the time =
of
> rebroadcast is below the percolation threshold. Indeed, with good timing
> and a
> sybil attack, an attacker may be able to deliberately trigger this
> condition.
>
> Improvements like the Transaction Announcements Reconciliation(2) BIP may
> be
> able to mitigate this issue, by ensuring that regardless of the timing of
> replacements, the rebroadcast transaction eventually reaches all nodes vi=
a
> the
> reconciliation process.
>
>
> # References
>
> 1)
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/0219=
99.html
> 2)
> https://github.com/naumenkogs/bips/blob/bip_0330_updates/bip-0330.mediawi=
ki
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr">Hi Peter,<div><br></div><div>&gt; Altruistic third parties=
 can partially mitigate replacement cycling(1) attacks<br>&gt; by simply re=
broadcasting the replaced transactions once the replacement cycle<br>&gt; c=
ompletes. Since the replaced transaction is in fact fully valid, and the<br=
>&gt; &quot;cost&quot; of broadcasting it has been paid by the replacement =
transactions, it can<br>&gt; be rebroadcast by anyone at all, and will prop=
agate in a similar way to when it<br>&gt; was initially propagated. Actuall=
y implementing this simply requires code to be<br>&gt; written to keep trac=
k of all replaced transactions, and detect opportunities to<br>&gt; rebroad=
cast transactions that have since become valid again. Since any<br>&gt; int=
erested third party can do this, the memory/disk space requirements of<br>&=
gt; keeping track of these replacements aren&#39;t important; normal nodes =
can continue<br>&gt; to operate exactly as they have before.<br></div><div>=
<br></div><div>I think there is an alternative=C2=A0to altruistic and perio=
dic rebroadcasting still solving replacement cycling at the transaction-rel=
ay level, namely introducing a local replacement cache.</div><div><br></div=
><div><a href=3D"https://github.com/bitcoin/bitcoin/issues/28699">https://g=
ithub.com/bitcoin/bitcoin/issues/28699</a><br></div><div><br></div><div>One=
 would keep in bounded memory a list of all seen transactions, which have e=
ntered our mempool at least once at current mempool min fee.</div><div><br>=
</div><div>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 ti=
ered hierarchy of full-nodes participating in transaction-relay. I think su=
ch topology would be more frail in face of any sybil attack or scarce inbou=
nd slots connections malicious squatting.</div><div><br></div><div>The altr=
uistic rebroadcasting default rate could be also a source of amplification =
attacks, where there is a discrepancy between the feerate of the rebroadcas=
t traffic and the current dynamic mempool min fee of the majority of networ=
k mempools. As such wasting bandwidth for everyone.</div><div><br></div><di=
v>Assuming some medium-liquidity or high-liquidity attackers might reveal a=
ny mitigation as insufficient, as an unbounded number of replacement transa=
ctions might be issued from a very limited number of UTXOs, all concurrent =
spends. In the context of multi-party time-sensitive protocol, the highest =
feerate spend of an &quot;honest&quot; counterparty might fall under the lo=
west concurrent replacement spend of a malicious counterparty, occupying al=
l the additional replacement cache storage.</div><div><br></div><div>Best,<=
/div><div>Antoine</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr=
" class=3D"gmail_attr">Le=C2=A0sam. 9 d=C3=A9c. 2023 =C3=A0=C2=A010:09, Pet=
er Todd via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfounda=
tion.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8=
ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,=
204,204);padding-left:1ex">While this seems like a reasonably obvious idea,=
 I couldn&#39;t find a previous<br>
example of it published on bitcoin-dev or elsewhere. So for the ability to =
cite<br>
it, I&#39;ll publish it now.<br>
<br>
<br>
# Summary<br>
<br>
Altruistic third parties can partially mitigate replacement cycling(1) atta=
cks<br>
by simply rebroadcasting the replaced transactions once the replacement cyc=
le<br>
completes. Since the replaced transaction is in fact fully valid, and the<b=
r>
&quot;cost&quot; of broadcasting it has been paid by the replacement transa=
ctions, it can<br>
be rebroadcast by anyone at all, and will propagate in a similar way to whe=
n it<br>
was initially propagated. Actually implementing this simply requires code t=
o be<br>
written to keep track of all replaced transactions, and detect opportunitie=
s to<br>
rebroadcast transactions that have since become valid again. Since any<br>
interested third party can do this, the memory/disk space requirements of<b=
r>
keeping track of these replacements aren&#39;t important; normal nodes can =
continue<br>
to operate exactly as they have before.<br>
<br>
<br>
# Background<br>
<br>
To recall, a replacement cycling attack has three basic stages:<br>
<br>
0) Target transaction tx0_a is broadcast, spending one or more outputs<br>
1) Attacker broadcasts double-spend tx0_b, spending an additional output<br=
>
=C2=A0 =C2=A0under the attacker&#39;s control<br>
2) Attacker broadcasts double-spend tx1, double-spending only the additiona=
l<br>
=C2=A0 =C2=A0input, resulting in the original input set not being spent<br>
<br>
Replacement cycling is a potential threat any time two or more parties have=
 the<br>
ability to spend a single txout, and rendering that output _unspent_ is<br>
harmful. For example, replacement cycling is an attack on lightning HTLCs,<=
br>
because it can result in an HTLC pre-image not being observed by a party un=
til<br>
after the HTLC expires. Similarly, replacement cycling is a potential attac=
k on<br>
signatureless anchor outputs, as it can allow third parties to revoke a CPF=
P<br>
anchor spend, making the parent transaction(s) unminable.<br>
<br>
<br>
# Altruistic Rebroadcasting<br>
<br>
Bitcoin Core keeps no records of replaced transactions. Thus after the<br>
replacement cycling attack is complete, tx0_a has been entirely purged from=
 a<br>
Bitcoin Core node&#39;s mempool, and all inputs to tx0_a are unspent. Thus =
it is<br>
just as valid to broadcast as before.<br>
<br>
<br>
## Resources Required<br>
<br>
Let&#39;s suppose we have a DoS attacker who is constantly broadcasting rep=
lacement<br>
in an effort to overwhelm nodes performing altruistic rebroadcasting. The<b=
r>
BIP-125 RBF rules require that a replacement transaction pay for the bandwi=
dth<br>
used by the replacement. On Bitcoin Core, this defaults to 1sat/vByte. Assu=
ming<br>
the attacking transactions are ~100% witness bytes, that is ~0.25sats/byte =
of<br>
relay bandwidth per peer.<br>
<br>
Suppose the DoS attacker has a budget equal to 50% of the total block rewar=
d.<br>
That means they can spend 3.125 BTC / 10 minutes, or 520,833sats/s.<br>
<br>
=C2=A0 =C2=A0 520,833 sats/s<br>
=C2=A0 =C2=A0 -------------- =3D 2,083,332 bytes / s<br>
=C2=A0 =C2=A0 0.25 sats/byte<br>
<br>
Even in this absurd case, storing a one day worth of replacements would req=
uire<br>
just 172GB of storage. 256GB of RAM costs well under $1000 these days, maki=
ng<br>
altruistic rebroadcasting a service that could be provided to the network f=
or<br>
just a few thousand dollars worth of hardware even in this absurd case.<br>
<br>
It&#39;s notable that miners may in fact want to run replacement rebroadcas=
ting<br>
software themselves, to ensure they are not missing any valid, profitable,<=
br>
transactions. In the context of a large mining pool, the additional cost ov=
er<br>
running a regular node may be affordable.<br>
<br>
<br>
## Limitations<br>
<br>
At the moment, Bitcoin Core propagates transactions purely via INV<br>
announcements; there is no set reconciliation mechanism to synchronize memp=
ools<br>
between peers. If an INV announcement is missed for some reason, it&#39;s q=
uite<br>
possible that the transaction will be missed. Thus rebroadcasting may be<br=
>
defeated if the % of nodes who do *not* have the transaction at the time of=
<br>
rebroadcast is below the percolation threshold. Indeed, with good timing an=
d a<br>
sybil attack, an attacker may be able to deliberately trigger this conditio=
n.<br>
<br>
Improvements like the Transaction Announcements Reconciliation(2) BIP may b=
e<br>
able to mitigate this issue, by ensuring that regardless of the timing of<b=
r>
replacements, the rebroadcast transaction eventually reaches all nodes via =
the<br>
reconciliation process.<br>
<br>
<br>
# References<br>
<br>
1) <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-=
October/021999.html" rel=3D"noreferrer" target=3D"_blank">https://lists.lin=
uxfoundation.org/pipermail/bitcoin-dev/2023-October/021999.html</a><br>
2) <a href=3D"https://github.com/naumenkogs/bips/blob/bip_0330_updates/bip-=
0330.mediawiki" rel=3D"noreferrer" target=3D"_blank">https://github.com/nau=
menkogs/bips/blob/bip_0330_updates/bip-0330.mediawiki</a><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>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000395f1a060c93ef05--