path: root/31/7c36fad1bd9652eb9232b2421ca006d30fa3bc

Return-Path: <antoine.riard@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 64C6AC0037
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 15 Dec 2023 22:29:37 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 3839B40549
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 15 Dec 2023 22:29:37 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 3839B40549
Authentication-Results: smtp2.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20230601 header.b=kRESwgEx
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id OxDxEK20kQ79
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 15 Dec 2023 22:29:35 +0000 (UTC)
Received: from mail-io1-xd29.google.com (mail-io1-xd29.google.com
 [IPv6:2607:f8b0:4864:20::d29])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 1542A401C9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 15 Dec 2023 22:29:34 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 1542A401C9
Received: by mail-io1-xd29.google.com with SMTP id
 ca18e2360f4ac-7b72192f7a1so56303739f.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 15 Dec 2023 14:29:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1702679374; x=1703284174;
 darn=lists.linuxfoundation.org; 
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :from:to:cc:subject:date:message-id:reply-to;
 bh=n0Zcmq/XLGolXshXGbji9WX/BH8W2qRnM7CUuJRoW0A=;
 b=kRESwgEx6nHSPLccJFU2YDO4Cu2qQzAG4ZRn96clOD0PvzbxhkQLDp5Ah6u6NLOIHS
 oaNO2FCie7/2oLsTZAUZt8fV2Jo1ZPXIYGwNyaefyq1lwIowCngL/94sWgyp/n682cQZ
 d5z10Bp8JTnrBq8xxnueU0Tf8h4U/zpSLD+1cJRycAw5xwCcJxwbeH4+lwovzejH/YZl
 ULmq9lV7mX8lxL79xMyvdaoS384hytHlJZbbPXP77O852AnadeFd5PqeMo6KcaiFQCt8
 HofpwKEg9GKsARAyZ3pMqcyzuKxRJ/RHeLJhoCEli4PjSeGDMJQF9hC4BrobVUGGS+tf
 UPKg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1702679374; x=1703284174;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
 bh=n0Zcmq/XLGolXshXGbji9WX/BH8W2qRnM7CUuJRoW0A=;
 b=Y/oll3BXfbFK1JP7/J3ePMYg3o0LqMlJOh8RMtebiq2DuXNT1OeYcrN092dMPCfD3O
 +jS/0BU55gVyTzNZaVYB+dmdiT3NbMDsJ+8hakRXTLtaxZVJyoozL6wvD3hp1Npk2h9/
 XiapvmdovE+1k0mlkEIhvR69r8+XoCcQ7IKCZoC6Lk7VUwYGxHP0RzY1Qn8zMCbRQMOn
 FSDbJYbPSJRUNFRGiDpdO6mOjpQvqvjW6NuQzQYjR6VtiGYsi/+PkycObruQRWJb6zeI
 qIE42zWCoMAb9epMJFevDZeoSMMo6QIgT6Avmyr6Rakl2Q2X3I9K2TOosEbbjqgm+iCf
 +5bg==
X-Gm-Message-State: AOJu0Yyc79TR7ffkwOIOdzHg/VTHvk8m2d0WK6i5ac8xHRfZYuHSfWIn
 DUsNPZ8tn6LPQCvlw4Yu6RjTs8/9UjxSYQTpNNyKaBUqkdOXYw==
X-Google-Smtp-Source: AGHT+IGQiwPrRj1dhWhLWafW0ZYnsYBdelsSnNYrUVhN85rtGaPQ7BxFlFCcFRwjFbivdtW+/XYKprVmgu6aCCgeNeM=
X-Received: by 2002:a05:6e02:20c3:b0:35d:59b3:2f84 with SMTP id
 3-20020a056e0220c300b0035d59b32f84mr10111632ilq.25.1702679373502; Fri, 15 Dec
 2023 14:29:33 -0800 (PST)
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"
X-Mailman-Approved-At: Fri, 15 Dec 2023 22:48:29 +0000
Subject: Re: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement
 Cycling Mitigation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 15 Dec 2023 22:29:37 -0000

--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--