[bitcoindev] [FULL DISCLOSURE]: Replacement Cycling Attacks on Attacks on Bitcoin Miners Block Templates

[Antoine Riard <antoine.riard@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 15861 bytes --]

Hi all,

I'm writing a report to fully disclose the variant of replacement cycling
attacks
enabling to censor transaction traffic from miners block template and as
such for
an attacker to achieve a dominant strategy in the distribution of the
bitcoin fee
reward for the generation of blocks in the longest valid chain among all
honest
mining nodes.

A proof-of-concept of this miner-level attack was tested against a Bitcoin
Core
26.0 branch before my previous disclosure of the 16 October 2023 informing
the community
on how the replace-by-fee mechanism could be used to break the security of
the Lightning
channels. During the last months, it was independently rediscovered and
noticed by
at least Peter Todd (and I guess few other smart observers...) that
replacement cycling
attacks can affect miners block templates.

While the practicality of replacement cycling attacks in the real-world is
still an
open question among the bitcoin protocol experts, in my personal and humble
opinion
this variant of replacement cycling attack is severe for the perennity of
the bitcoin
ecosystem at large, even more in a post-subsidy world.

The attack shares some similarities with fill-and-dump tricks already known
since years
among mempool experts, yet I think leveraging non-utxo owned transaction
traffic, targeting
properties of a chain of transactions itself to mount those replacement
cycling attacks variant
and combining those techniques in new exploitation model are all novel.

As part of the full disclosure, I'm making the following list of artifacts
publicly available.

Test of the feerate differential RCA variant on the classic mempool
(bitcoin core branch 26.0 - commit 78b7e955):
https://github.com/ariard/bitcoin/commits/test-mempool-feerate-differential-rca/

Test of the timing RCA on the classic mempool (bitcoin core branch 26.0 -
commit 78b7e955):
https://github.com/ariard/bitcoin/commits/test-mempool-timing-rca/

Test of the feerate differential RCA variant on the cluster mempool
(bitcoin core branch 29.0 - commit 5acf12ba):
https://github.com/ariard/bitcoin/tree/test-mempool-feerate-differential-cluster-rca

Test of the timing RCA variant on the cluster mempool (bitcoin core branch
29.0 - commit 5acf12ba):
https://github.com/ariard/bitcoin/tree/test-mempool-timig-cluster-rca

Paper summarizing replacement cycling attacks on bitcoin miners block
template:
https://github.com/ariard/mempool-research/blob/2023-10-replacement-paper/rca-bmbt.pdf

Original proof-of-concept RCA on bitcoin miners mempool from October 2023:
https://github.com/ariard/bitcoin/commits/2023-poc-miner-jamming/

If you're not already familiar with the idea of replacement cycling attack,
I can only
invite you to read the full disclosure report on how it affects Lightning:
https://github.com/ariard/mempool-research/blob/2023-10-replacement-paper/replacement-cycling.pdf

## Discovery

During the year 2022, eltoo lightning channels design are discussed,
implemented
and reviewed. In this context and after discussions on mempool anti-DoS
rules, I
discovered that the replace-by-fee mechanism could be leveraged to break
Lightning
channels security. The finding was reported at the near end of 2022 to some
bitcoin
core developers and lightning maintainers.

During the year 2023, mitigations (mainly random rebroadcast of
time-sensitive
second-stage HTLC transactions) are implemented in the major lightning
implementations
and the patched implementations are released for dissemination across the
ecosystem
during the first half of 2023. Date of full disclosure is set for
mid-October.

During the first weeks of October, while I was writing more
proof-of-concepts and
doing experimental tests of replacement cycling attacks affecting
Lightning, I realized
that a multi-party transaction could be pinned in the mempool with a branch
of jun
children blocking further RBF or CPFP of the multi-party transaction and
once a
replacement cycling trick have been played to kick out the junk children,
the multi-party
transaction is dropped out of the victim's mempool.

A simple proof-of-concept of this attack variant was immediately shared
with the
bitcoin core sec list members. As the full disclosure date was already
announced
for the lightning maintainers, I took the initiative to keep the initial
schedule
for the full disclosure of replacement cycling attacks on the lightning
network.

During the month of September 2024, Peter Todd published a blog post
("Soft-Fork/
Covenant Dependent Layer 2 Review") with a section 4.3 on Replacement
Cycling
pointing out how RCA could be a form of economic exploit on miners.

## Background: Block template Construction, Multi-Party Transaction and
Replace-by-Fee

In Bitcoin, all full-nodes are by default participating in the
transaction-relay
network, announcing and broadcasting new transactions to each other. Among
the
full-nodes, miners are specific full-nodes searching for a valid
proof-of-work
to be allowed to add a new block on the chain tip. While searching for a
proof-of-work,
a mining node generates a block template from its local mempools, a cache
for
the unconfirmed transactions. The block template is generally a collection
of
unconfirmed transactions sorted by highest paying fees. Miners are
incentivized
to put transactions in a block template, as there are obtaining the fees.

Among all the bitcoin transaction traffic flowing on the transaction-relay
network,
there are numerous transactions which have being historically and which are
still
multi-party transactions, e.g payout batch transaction, coinjoin
transaction,
lightning liquidity allocating transactions batching, colored coins
transactions, etc.
One aspect of this multi-party transaction is that the inputs and the
outputs might
dissociatively belong to a number of users equal or superiors to 2.
However, as soon
as an input or an output are added to a transaction, this enable the owner
of this
transaction component to eventually interferes with the propagation of the
transaction.

One mempool mechanism affecting the propagation of a transaction over the
transaction-relay
network is the replace-by-fee policy. Originally sketched out loosely by
Satoshi Nakamoto,
it was implemented in Bitcoin Core 0.12.0, and since them there have many
(ongoing)
refinement to the replace-by-fee policy. Roughly the mechanism works in the
following way
by generating a new transaction with higher absolute fee / higher feerate,
an in-mempool
transaction spending some of the same coin can be kicked out of the mempool.

## The Problem: Forgeability of a Miner Block Template Ordering

When a miner is assembling a collection of transactions to constitute a
block template
for the next block finding, they have to order this block template
accordingly to the
state of their local(s) mempool(s). This state is ordered by the miner to
compose the
highest rewarding block according to some classifying algorithm (e.g
ancestor-feerate)

However, the generation of a block template is done "discretely" from the
local mempool
state and this state can be read / write in an open way by
transaction-relay peers, by
abusing the replace-by fee mechanism or the expiration time of
transactions, among other
tricks.

Informally, a local mempool can be computationally forged if the average
quantity of
fees for a single unit is inferior to the attacker's mempool one for a
given measurement
unit (be it virtual bytes or weight), while the forgery cost for the
attacker stay under
the average expected return of engaging in a forgery.

Of course, mempools consistency has never been a design goal of bitcoin
transaction-relay
in a distributed system like the peer-to-peer transaction-relay network,
and some amount
of "forgery" has always been expected. Nevertheless, it appears from
testing and analysis
there can be significant margins of exploitation offered to malicious
hashrate adversaries.
One such margin of exploitation can be instantiated by mounting a
replacement cycling attack
on a miner mempool.

## A Simple Replacement Cycling Attack on a Miner Mempool Example

Let's say Mallet and Mary are both miners with equivalent hashrate
capabilities (i.e
the same odds to mine a block for a given period). Alice is an exchange
doing batch
payment to pay its users withdrawing funds from the exchange. Mary is a
solo miner
with limited CPUs / memory resources and she is refreshing her mining jobs
with a
`getblocktemplate` only once by minute.

During the setup phase of the attack, Mallet opens 2 low-value accounts at
Alice's
exchange and wait for the time lapse of the next batch payout to be reached
to ask
her 2 accounts to make a deposit.

Alice builds a batch payout transactions with N outputs for her honest
users and 2
more outputs for Mallet. The transaction is finalized and broadcasts over
the network
of mempools for inclusion in a block template. The Alice batch transaction
is of
size 1000, with ~10 payout for a feerate of 2 satoshis per virtual byte.

As soon as Alice's batch transaction starts to propagate, Mallet consumes
its 2 outputs
with 2 chain of junk transactions to reach max package limits (25
descendants) and block
the carve-out. The junk transactions are of size 150 bytes and feerates 2
satoshis per
virtual byte and they have 2 parents: one Alice's payout UTXO and one
Mallet's UTXO.

Starting from this point, Alice's exchange server logic should either (a)
attempts a CPFP
or (b) attempts a RBF on the batch transaction. As there is no global
mempool, Alice is
uncertain on the explanation for the lack of propagation of her batch
transaction, it is
most likely she will broadcast a feerate increase in the dark. To replace
Alice's parent
batch transaction and Mallet's junk children transaction, a replace-by-fee
must have
an absolute fee superior to 9800 satoshis. The replace-by-fee transaction
is assumed to
be blocked by Mallet as this absolute fee, so its fees are 9800 satoshis.

The feerate increase transaction (a RBF or CPFP) should be negated by
Mallet outbid
by the constant cycle of replacement junk transaction. As soon as the RBF
or CPFP has
been re-cycled out for a give period, the chain of junk replacement
transaction can
be re-attached on another package to provoke a higher replace-by-fee from
Alice's server.

If the counter-square of the Alice's RBF and the subsequent replacement out
of Mallet's
transaction is achieved before Mary is fetching the latest highest feerate
group of the
mempools, she should only get Alice root's batch transaction and Mallet's
junk children
transactions.

At equal odds of mining blocks, the absolute fees yield by their respective
block template
is the following:
- Mary's block template: 9800 satoshis
- Mallet's block template: 17600 satoshis

The question is from where Mallet's advantage is coming. As the owner of
the utxos used
to build the chain of junk transactions, he can cumulate both spending
Alice's utxo with
her own replace-by-fee transaction and a withhold chain of new transactions
spending his
non-collaborative UTXOs. Mary is only seeing in her mempool the latest
result of mempool
acceptance, and not the highest combination of absolute fees for a
combination of given
UTXOs.

It should be noted, the advantage of Mallet can be diluted with the number
of replacement
cycling done to block the fee-bump of Alice's batch transaction, due to the
RBF penalty.
However, the penalty can be compensated by targeting many unrelated
multi-party transactions.

## Solutions

I'm marking few solutions that could improve replacement cycling attacks on
miners block
template, while their exact efficiency is still a subject to be analyzed.

Cluster mempool: this is a proposal to associate each unconfirmed
transaction in a mempool
with related transactions, creating a cluster. Each cluster contains
feerate-sorted chunks
consisting one or more transactions. Ideally, the cluster mempool would
allow to build more
efficient eviction and replacement algorithms on top of it. In the context
of RCA on miners,
it could potentially diminish the differential that can be generated at the
advantage of the
attacker.

Replace-by-Feerate: this is proposal to allow replacement to only happen
when it would
immediately bring a transaction close enough to the top of the mempool to
be mined in the
next block or so. In the context of RCA on miners, this could increase the
jamming cost
burdened by the attacker.

Chain of Transactions Topological Restrictions: currently, full-node
mempool are generally
allowing 25 ancestors and 25 descendants by default. By restraining the
topological dimensions
of a chain of transaction, this renders the computation of mempool
algorithms more tractable.
In the context of RCA on miners, this might have the indirect effect to
potentially diminish
the differential that can be generated at the advantage of the attacker.

UTXO-based Transaction Announcement: currently, transaction-relay is only
done based on the
txid or wtxid of a transaction. In the future, the best feerate known for a
set or subset
of UTXOs could be propagated among nodes, before they proceed to the actual
transaction relay.
In the context of RCA on miners, an enhanced mempool could be re-download
the best known
in the past transaction branch for a UTXO, if there is subsequent downgrade
of the best
feerate branch for this same given UTXO.

## Timeline

- 2022-12: Report of the replacement cycling attacks on lightning channel
to a selected
group of bitcoin core contributors and lightning maintainers
- 2023-06: Week of mid-october 2023 proposed for full disclosure of
replacement cycling attacks
on the Lightning Network
- 2023-08-10: CVEs assigned by MITRE for the Lightning project
- 2023-10-05: Pre-disclosure of LN CVEs numbers and replacement cycling
attack existence
to security@bitcoincore.org
- 2023-10-15: Finding that replacement cycling attack can put a DoS risk on
multi-party
transactions and the hypothetical effect on miners mempools ; Sharing of a
proof-of-conceptual test
to security@bitcoincore.org
- 2023-10-16: Full disclosure of CVE-2023-40231 / CVE-2023-40232/
CVE-2023-40233 / CVE-2023-40234
and replacement cycling attacks
- 2024-09-02: Peter Todd publishes a public blog post analysis some
soft-fork proposals and in
this post loosely mention the potential effect of RCA on miners
- 2024-09-07: Sharing to Peter Todd, Antoine Poinsot and Greg Maxwell the
proof-of-conceptual
test of RCA at the miner-level and hypothesis
- 2024-09-30: Sharing additional info on RCA at the miner-level to the same
group of 4 with
the addition of Michael Ford, Ava Chow and Eric Voskuil ; Proposal for a
disclosure in the last
weeks of January
- 2025-01-27: Full disclosure of "Replacement Cycling Attacks on Bitcoin
Miners Block Templates"

## Conclusion

By leveraging the replace-by-fee and mempool mechanisms of a mempool, an
adversarial miner can deliberately jam the quality of its competitors block
template, and gain an advantage
in the global distribution of the fee reward coming from confirmed
transactions. While the
exact practicality of this attack is still to be investigated, the main
tricks have been
tested both on a classic mempool on a bitcoin core running a 26.0 branch
and cluster-based
mempool on a bitcoin core node running a 29.0 branch.

Do not trust, verify. All mistakes and opinions are my own.

Antoine

"trust yourself when all men doubt you,
        but make allowance for their doubting too" - K

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CALZpt%2BEnDUtfty3X%3Du2-2c5Q53Guc6aRdx0Z4D75D50ZXjsu2A%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 17815 bytes --]