Subject: Re: [bitcoin-dev] Altruistic Rebroadcasting - A Partial Replacement Cycling Mitigation

From: Peter Todd <[email-masked]>
Date: Fri, 22 Dec 2023 14:01:28 +0000

On Thu, Dec 21, 2023 at 09:59:04PM +0000, Antoine Riard wrote:
> 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.

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

Huh? Bitcoin nodes almost always use the same mempool limit, 300MB, so mempool
min fees are very consistent across nodes. I just checked four different long
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 minfees
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:
> 
> 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.

From 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 replacement.

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 transaction
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 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 tx
> > 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.

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 nodes,
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 node
on the network can add both transactions to their mempool. When Alice and Bob
broadcast their victim transactions, their nodes will tell multiple peers about
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, from
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 rebroadcasting
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.

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