Feedback-ID: i525146e8:Fastmail
Date: Fri, 22 Dec 2023 14:01:28 +0000
From: Peter Todd <pete@petertodd.org>
To: Antoine Riard <antoine.riard@gmail.com>
Message-ID: <ZYWWuBdcMaZS5elz@petertodd.org>
References: <ZXQ8uFLoNlSksalX@petertodd.org>
 <CALZpt+HLoomKZn=QsBZ-4M-WSDzjEA_p1nzk9N=+R4MveeAOFQ@mail.gmail.com>
 <ZX7UHOaUKk/+jbS1@petertodd.org>
 <CALZpt+Hy+ayawj38Bh3TLZqA3C=G-wGvy_nz9=_5S8-ZZiot7w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
 protocol="application/pgp-signature"; boundary="Qp2QITt/wI3Drh6d"
Content-Disposition: inline
In-Reply-To: <CALZpt+Hy+ayawj38Bh3TLZqA3C=G-wGvy_nz9=_5S8-ZZiot7w@mail.gmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement
 Cycling Mitigation
Precedence: list


--Qp2QITt/wI3Drh6d
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Dec 21, 2023 at 09:59:04PM +0000, Antoine Riard wrote:
> Hi Peter,
>=20
> > 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 neede=
d,
> as
> > any alturistic party can implement that cache for all nodes.
>=20
> Sure, note as soon as you start to introduce an altruistic party
> rebroadcasting for everyone in the network, we're talking about a differe=
nt
> security model for time-sensitive second-layers. And unfortunately, one c=
an
> expect the same dynamics we're seeing with BIP157 filter servers, a handf=
ul
> of altruistic nodes for a large swarm of clients.

Are you claiming that BIP157 doesn't work well? In my experience it does.

Rebroadcasting is additive security, so the minimum number you need for the
functionality to work is just one.

> > 1) That is trivially avoided by only broadcasting txs that meet the loc=
al
> > 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
>=20
> 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.

Huh? Bitcoin nodes almost always use the same mempool limit, 300MB, so memp=
ool
min fees are very consistent across nodes. I just checked four different lo=
ng
running nodes I have access to, running a variety of Bitcoin Core versions =
on
different platforms and very different places in the world, and their minfe=
es
all agree to well within 1%

In fact, they agree on min fee much *more* closely than the size of their
mempools (in terms of # of transactions). Which makes sense when you think
about it, as the slope of the supply/demand curve is fairly flat right now.

> > Did you actually read my email? I worked out the budget required in a
> > reasonable worst case scenario:
>=20
> 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.
>=20
> Of course, you can introduce an additional rate-limitation per-UTXO, thou=
gh
> I think this is very unsure how this rate-limit would not introduce a new
> pinning vector for "honest" counterparty transaction.

=46rom the point of view of a single node, an attacker can not reuse a UTXO=
 in a
replacement cycling attack. The BIP125 rules, in particular rule #4, ensure
that each replacement consumes liquidity because each replacement requires a
higher fee, at least high enough to "pay for" the bandwidth of the replacem=
ent.

An attacker trying to use the same UTXO's to cycle out multiple victim
transactions has to pay a higher fee for each victim cycled out. This is
because at each step of the cycle, the attacker had to broadcast a transact=
ion
with a higher fee than some other 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 enti=
re
> > replacement database in RAM costs under $1000
>=20
> > The reality is such an attack would probably be limited by P2P bandwidt=
h,
> 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=
 tx
> > broadcasting.
>=20
> 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.
>=20
> 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.

If I understand correctly, here you are talking about an attacker with
connections to many different nodes at once, using the same UTXO(s) to do
replacement cycling attacks against different victim transactions on many
different nodes at once.

There is no free lunch in this strategy. By using the same UTXO(s) against
multiple victims, the attacker dramatically reduces the effectiveness of the
attack because only a subset of nodes see each "side" of the attack.

Suppose that Mallory is connected directly or indirectly Alice and Bob's no=
des,
and attempts to do a replacement cycling attack against both Alice and Bob =
with
the same UTXO(s).

Both Alice and Bob's victim transactions spend different UTXOs, so every no=
de
on the network can add both transactions to their mempool. When Alice and B=
ob
broadcast their victim transactions, their nodes will tell multiple peers a=
bout
their respective transactions. Indeed, if alturistic rebroadcasting is to be
relevant at all, nodes other than Alice and Bob's *must* have learned about
their transactions!

Mallory on the other hand is creating divergent attack transactions that are
mututally incompatible. When Mallory broadcasts those attack transactions, =
=66rom
the perspective of some nodes, Alice's victim transaction will be replaced =
out
but not Bob's, and from the perspective of other nodes, the opposite.

Indeed, from the perspective of roughly half of the alturistic rebroadcasti=
ng
nodes, Alice's transaction was never cycled out, and the other half, Bob's =
was
never cycled out!

Even in this case where the attack only used the same UTXO for two targets,
each victim transaction gets to roughly 50% of the mining nodes, making the
attack ineffective. And the numbers for Mallory just keep getting worse as =
he
targets more victims at once.

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--Qp2QITt/wI3Drh6d
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmWFlrYACgkQLly11TVR
LzdEnRAArM6CCGd4cBHnBAXz1Sd0GetD+Kig1frJZ/vYgDv2mvkKLBdaLqVsyw+4
WLGvgLVHCFv6VlKho3hUezDE++NJh7rPhy02saqdnXJzBBNMPiov6aBwmoyxBpCX
LXxK6wBT5FYRuatpyJgYmhcPgbV4fFwWAKaqa39IuBFnAtUhUBjKM8FUvYbE61Ti
fYl77xJ9PsGvo9YelFs/+58okb/Fqv6/NXf90SIXNF8P2+AKZWDQflX700hL2JCP
CSZCc4hW7BJGRiZIajx0lfY1jr0YHyZ8DzqJxVoDbdZG2Is60pLQJnbvAF7fItDU
V/zuWS4PrKXX1zwSMSqLPFC6PHURYZgsQ/nwyXi7Annazc/1ZZP++MMEloONGzdE
kYHIQodGM+E2tIdVt3v4/bnICG7kbdANnjLQhXQMLmLtdevLysjzY7WF69LHCmeC
R+IMI2Y1CXHxCQ/Y3b5fWuUBxNb70EHgrojDy3gnUkuASi22WGQd8Y+zKoAsoDyz
iOuZx0x4DB4KElg7rT5cv4k3PDpSyShK+D4QSiJTCtQNGWnoBSlJVNF2lxSuQu5g
wBjOXNf4lEXaTI2IjGocGXb2HTDdCUzrj4ittOOMPc4oo4/V/JF4gmw+BmTFscnk
vv1dgcIXnkvbrkKWU4HcbmVcUW1covAFPXMRBSE7EvFoCgSLvGk=
=pj+P
-----END PGP SIGNATURE-----

--Qp2QITt/wI3Drh6d--