path: root/8e/d2f6789ef140e9dacdb17ce3ada29f8df37e27

Delivery-date: Mon, 27 Jan 2025 07:40:03 -0800
Received: from mail-oo1-f58.google.com ([209.85.161.58])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBC3PT7FYWAMRBR6R326AMGQEAG4KLCQ@googlegroups.com>)
	id 1tcRDV-0005g9-1Q
	for bitcoindev@gnusha.org; Mon, 27 Jan 2025 07:40:03 -0800
Received: by mail-oo1-f58.google.com with SMTP id 006d021491bc7-5f70b0fad64sf1527982eaf.1
        for <bitcoindev@gnusha.org>; Mon, 27 Jan 2025 07:40:00 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1737992395; cv=pass;
        d=google.com; s=arc-20240605;
        b=Gunpb2eXoky1KyNy5RxafcT7gh2DYihnlGZcmT2u+4kVI30VNBxcXjyP9Y1f+v5ex+
         xxPQWfG+MLudnNzTI6qu/F7gn9hHtcGKU0SLR3DiTnLZLLyTdHtN/q/2FhEiK9gpyF3d
         MKYfAwf4AJzjNHqWF0fTTo+0YoGSgezswxEDIfWBUZs+UzUuUuxYVmjuozrWUOsI0Ppj
         C8ED46D7UbECLZQ/mQk0np12ScsjbkHZtzs4AdhcHx5jW/UcxfSemXyaqe8H1NZP7oLO
         lNnfhB0LGLQpsrBjHI/Dt2kqEMhX/xpTxlUohX8SIJ4rcizxPh8mZvdM4Ra94ThDV2tt
         K6qg==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:cc:to:subject:message-id:date:from
         :mime-version:sender:dkim-signature:dkim-signature;
        bh=U/OOxnBgX+iQ3EwU4zu9a1f/Dq6Yn247PZAxq1DvU34=;
        fh=Zq68jyUMroLZJBCbXBVg5GiHa4zvlpwziYtgfT6OSgc=;
        b=AJUWWOEGTwDIaxWFS6NdYCd+rVcZeb0kkyUOdkcA60kbbr5Xt3VrxNIRCOBfbi7Djr
         GXbaJen4O0KTYfDKguv6qQ3HSKG8pySi+M9zqwL6NqzlwwgGoZoBcPloIu5GP6uWiuvW
         zz1WSiDPfUcUel1le6dHjdDBILgkR8nVuFbUcZpni7AR5kB9MtM6qsVC1TX22UcB/bQO
         +mhDszbaPfQ1PLyGCXxb+qVQ2YOSu3vQhdX9lD5XWM94aSjHBT2l+eNP6vUpQAWWYeJA
         5MIolFGpoPn+X97XN9ZnDWQEj04k/zhBHl2j2GLiC49b7TNewFjJNxuITte8EAKO8CEZ
         /FHQ==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Cxpwmz0y;
       spf=pass (google.com: domain of antoine.riard@gmail.com designates 2607:f8b0:4864:20::1030 as permitted sender) smtp.mailfrom=antoine.riard@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1737992395; x=1738597195; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:mime-version
         :sender:from:to:cc:subject:date:message-id:reply-to;
        bh=U/OOxnBgX+iQ3EwU4zu9a1f/Dq6Yn247PZAxq1DvU34=;
        b=CX9/tZE5i9XustGP2yxAJs3BWfGaUyPYvSSrtyFOCjDx0tIiLiTNfEmM8N6eLLAeWH
         tOrfgagYwNZApWAe/7Nkmx7JU1NAjfRfd79kzYs3XhMAfm5B+RFqnfd3l8jvmjivZC0U
         E1DoT45WeDBtbfE/JI6ewBsikqEyMppLSRLBagNvCO685Z7/hExq5dw6kRPrdoGSFtVI
         a6Xoly7lMMDuTxrnNhC/O6V3vbOlO9to8FPW+sGRvinMvVbtKPWdH0qxbjioTlJhlYi/
         HyDqjHvWaGoTOh/8cgOF/kjcpGrfiF64LkaW353aZV6hAdhqVELsd9U2ONqteSzl8B/V
         pnAw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1737992395; x=1738597195; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:mime-version
         :from:to:cc:subject:date:message-id:reply-to;
        bh=U/OOxnBgX+iQ3EwU4zu9a1f/Dq6Yn247PZAxq1DvU34=;
        b=EIfaUBe9W5+BybVX0axmT6md73mM+Jt4USEZNp3vxMvV69Nn7d+wqYF8bV2+LYPQFW
         o5yTP4DJKnNk9vhxzyLjiqCyhIGcjnztLrMTJXdleznBi7Rf8k7xXou3uB/D/1+0lBKs
         i3VHO8HeEU6rIC2jGpCX/YrCH9CrnzbOxqtXFKHW+PiDce6JOeDXzDxEk+IrZTnPluD/
         N9fAmonsV1rLjnsb/YlMdmTHpWYhVnlkIm6kcai0JFG1/BYQdyFy6y2LO7VxVrmCry/z
         DjOZYUCXdMGQgSfgro023mUXtz+cE9UdR+G4p2L5r9zx3SvEtJKJXsdihpnSw/2ThYbz
         bXfA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1737992395; x=1738597195;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:mime-version
         :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
         :message-id:reply-to;
        bh=U/OOxnBgX+iQ3EwU4zu9a1f/Dq6Yn247PZAxq1DvU34=;
        b=kFEla9acdiyCFaQsRnVRe3187J6eoP/nfz0VkW+965iHe8+INRA0gcDYyvfj1QUxKc
         goDYsNuSaHE1Nt/X7Dui/Z+DnY43n0oqls/C/UY+dsgTHwhcc5G/jhh+0YsTrDcWsFxp
         iKD5JbIfMgzRC3YpnUQDpxKfiqvRoN/SYyrtm954u8ebYPSRzTP8tZL0eTf5AYtGqX0d
         A5kWd6m6caLTpuYz8aK+f669TCik89JOM45IbIaVUJj8WxEmEw0sIw02sLMGkGzCUZWl
         8WP+k9szVQswxWg70mYEuKk99fynElvxXz504icNEThVsUyZDCSGNnOzDvZw2yuYhWVc
         chbw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUwCdGzHJNCfAyV9/7kIS1OOYOE3xA+jPIH0qRwZazUFtL4YgdVowcHNPemq0QKnFKUm5i4CAqhTXAn@gnusha.org
X-Gm-Message-State: AOJu0Yz7jvENvmfFVZMBUQNQ2ZTawWDjmBGT1EOSnZQStmwY0icOUKGM
	uzf6ZSHmuO923Qgn9H+8NPuDk4MvCaBxvIZNSXxdcBxji6QIPw+r
X-Google-Smtp-Source: AGHT+IG1ufkA+Orvja/Z5FZ/m2NzBsDZh3kH2JcD/7ALHlZQchNFvLYHVlT4XljXjAIDW1ijZ3bwFg==
X-Received: by 2002:a05:6830:390b:b0:71d:5336:df80 with SMTP id 46e09a7af769-7249dae0ae5mr29527692a34.20.1737992394720;
        Mon, 27 Jan 2025 07:39:54 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a4a:c189:0:b0:5eb:b8f8:e3d0 with SMTP id 006d021491bc7-5fa80401ec0ls1187677eaf.1.-pod-prod-06-us;
 Mon, 27 Jan 2025 07:39:51 -0800 (PST)
X-Received: by 2002:a05:6808:800f:b0:3ec:d34f:4c64 with SMTP id 5614622812f47-3f19fbfc769mr17666893b6e.6.1737992391135;
        Mon, 27 Jan 2025 07:39:51 -0800 (PST)
Received: by 2002:a05:6808:6044:b0:3eb:7446:f871 with SMTP id 5614622812f47-3f1efed1c35msb6e;
        Mon, 27 Jan 2025 07:22:53 -0800 (PST)
X-Received: by 2002:a17:90b:2c83:b0:2f2:a664:df20 with SMTP id 98e67ed59e1d1-2f782c6750cmr65086632a91.7.1737991372288;
        Mon, 27 Jan 2025 07:22:52 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1737991372; cv=none;
        d=google.com; s=arc-20240605;
        b=iLQ+SQDA189zHrcfo1/QJMYYzhWxvPDfj3ZfpXcnYYx2QFxAX7v5L2+DCIv5WWMVP3
         86/mPTkJYjhOcMl4lWAVJ9WS7TTei4J2UGHFhGfkrZfWoRbjy4c8ewDMwduLqFp0zHBt
         mpqu1qU7+YIwsasdws9oJXDkMewAx3Y2wGaQC8EqXd/pe87dLtQQw+yAkF1+p+yk9vSU
         oeupPrZGZIZch0tQMmYt4i4E3w3Nh6exmxEDWZuRyKK+/JG2rTJ+4B9auxV3LVtZ1RPD
         3Jrw+kocQ15J4YcjguvTevCzOKekUYWz4BZbQTtbUeB6VxotRNAAp83xyAGy/6vLA0eZ
         B+Uw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=cc:to:subject:message-id:date:from:mime-version:dkim-signature;
        bh=mBKp9h2HEwn/bUp2roiSt9f9TEq7mIi9oDTStqMZrjE=;
        fh=TrDDrH77hhIgp0mK2MdRvoco8jyXYiElDX5vXgyPiMs=;
        b=lcd/7hmLejXmlpJMx2/INhA+C8hVoFKFa9dJbJD4Qqk3TSRJHB75503st8jgMiY3PG
         3yMxKz/fOWfhZJF+di+JS4gIXQOZFcgOsF7xXM82pV99dBFygGwxSLKpg9k2viU+t4ut
         b1Drx2I7STpZKX6eIA/+WGR1Z+rj58dzCIpl06/++uZlN37rzckoj8z5NbP+i65kmx/O
         BNSkdjUoEfb/FihwS6m07XZGltYgFfWVo2F0AumZAEAjiqXeBGo4P7Icv45jNHpW3w9X
         oxeac1tyBpBwZ1ub///SYclNA6QhCGrPBkgGTHs1e1BdJR/mdhcsL6BlUUSp+n1UXeeZ
         12gg==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Cxpwmz0y;
       spf=pass (google.com: domain of antoine.riard@gmail.com designates 2607:f8b0:4864:20::1030 as permitted sender) smtp.mailfrom=antoine.riard@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-pj1-x1030.google.com (mail-pj1-x1030.google.com. [2607:f8b0:4864:20::1030])
        by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-2f7e46407aasi875197a91.1.2025.01.27.07.22.52
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Mon, 27 Jan 2025 07:22:52 -0800 (PST)
Received-SPF: pass (google.com: domain of antoine.riard@gmail.com designates 2607:f8b0:4864:20::1030 as permitted sender) client-ip=2607:f8b0:4864:20::1030;
Received: by mail-pj1-x1030.google.com with SMTP id 98e67ed59e1d1-2f43d17b0e3so8102919a91.0
        for <bitcoindev@googlegroups.com>; Mon, 27 Jan 2025 07:22:52 -0800 (PST)
X-Gm-Gg: ASbGncvQkeIpAtFh+qM09iLsm4m+Mx4E9hSxLFRZYL5AgIs0nqSi6MHzRWVoIUWQyXc
	+g0srF1VjijJPI/zj8rIY1u3wepE9DSlO6MiLyPRZw5ylxQjexDMs0OjocIP8zCguti+xMmE=
X-Received: by 2002:a17:90b:524d:b0:2ee:b26c:1099 with SMTP id
 98e67ed59e1d1-2f782d99563mr52817373a91.34.1737991370360; Mon, 27 Jan 2025
 07:22:50 -0800 (PST)
MIME-Version: 1.0
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 27 Jan 2025 15:22:38 +0000
X-Gm-Features: AWEUYZmi4Ir1iPKzWZC5cJaoUi1h0WnZiG_XV3kf6uO7ZV8WQY8H5DGNDVgx5us
Message-ID: <CALZpt+EnDUtfty3X=u2-2c5Q53Guc6aRdx0Z4D75D50ZXjsu2A@mail.gmail.com>
Subject: [bitcoindev] [FULL DISCLOSURE]: Replacement Cycling Attacks on
 Attacks on Bitcoin Miners Block Templates
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Cc: security@ariard.me
Content-Type: multipart/alternative; boundary="00000000000040cee0062cb1a68d"
X-Original-Sender: antoine.riard@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=Cxpwmz0y;       spf=pass
 (google.com: domain of antoine.riard@gmail.com designates 2607:f8b0:4864:20::1030
 as permitted sender) smtp.mailfrom=antoine.riard@gmail.com;       dmarc=pass
 (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

--00000000000040cee0062cb1a68d
Content-Type: text/plain; charset="UTF-8"

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.

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

<div dir=3D"ltr">Hi all,<br><br>I&#39;m writing a report to fully disclose =
the variant of replacement cycling attacks<br>enabling to censor transactio=
n traffic from miners block template and as such for<br>an attacker to achi=
eve a dominant strategy in the distribution of the bitcoin fee<br>reward fo=
r the generation of blocks in the longest valid chain among all honest<br>m=
ining nodes.<br><br>A proof-of-concept of this miner-level attack was teste=
d against a Bitcoin Core<br>26.0 branch before my previous disclosure of th=
e 16 October 2023 informing the community<br>on how the replace-by-fee mech=
anism could be used to break the security of the Lightning<br>channels. Dur=
ing the last months, it was independently rediscovered and noticed by<br>at=
 least Peter Todd (and I guess few other smart observers...) that replaceme=
nt cycling<br>attacks can affect miners block templates.<br><br>While the p=
racticality of replacement cycling attacks in the real-world is still an<br=
>open question among the bitcoin protocol experts, in my personal and humbl=
e opinion<br>this variant of replacement cycling attack is severe for the p=
erennity of the bitcoin<br>ecosystem at large, even more in a post-subsidy =
world.<br><br>The attack shares some similarities with fill-and-dump tricks=
 already known since years<br>among mempool experts, yet I think leveraging=
 non-utxo owned transaction traffic, targeting<br>properties of a chain of =
transactions itself to mount those replacement cycling attacks variant<br>a=
nd combining those techniques in new exploitation model are all novel.<br><=
br>As part of the full disclosure, I&#39;m making the following list of art=
ifacts publicly available.<br><br>Test of the feerate differential RCA vari=
ant on the classic mempool (bitcoin core branch 26.0 - commit 78b7e955):<br=
><a href=3D"https://github.com/ariard/bitcoin/commits/test-mempool-feerate-=
differential-rca/">https://github.com/ariard/bitcoin/commits/test-mempool-f=
eerate-differential-rca/</a><br><br>Test of the timing RCA on the classic m=
empool (bitcoin core branch 26.0 - commit 78b7e955):<br><a href=3D"https://=
github.com/ariard/bitcoin/commits/test-mempool-timing-rca/">https://github.=
com/ariard/bitcoin/commits/test-mempool-timing-rca/</a><br><br>Test of the =
feerate differential RCA variant on the cluster mempool (bitcoin core branc=
h 29.0 - commit 5acf12ba):<br><a href=3D"https://github.com/ariard/bitcoin/=
tree/test-mempool-feerate-differential-cluster-rca">https://github.com/aria=
rd/bitcoin/tree/test-mempool-feerate-differential-cluster-rca</a><br><br>Te=
st of the timing RCA variant on the cluster mempool (bitcoin core branch 29=
.0 - commit 5acf12ba):<br><a href=3D"https://github.com/ariard/bitcoin/tree=
/test-mempool-timig-cluster-rca">https://github.com/ariard/bitcoin/tree/tes=
t-mempool-timig-cluster-rca</a><br><br>Paper summarizing replacement cyclin=
g attacks on bitcoin miners block template:<br><a href=3D"https://github.co=
m/ariard/mempool-research/blob/2023-10-replacement-paper/rca-bmbt.pdf">http=
s://github.com/ariard/mempool-research/blob/2023-10-replacement-paper/rca-b=
mbt.pdf</a><br><br>Original proof-of-concept RCA on bitcoin miners mempool =
from October 2023:<br><a href=3D"https://github.com/ariard/bitcoin/commits/=
2023-poc-miner-jamming/">https://github.com/ariard/bitcoin/commits/2023-poc=
-miner-jamming/</a><br><br>If you&#39;re not already familiar with the idea=
 of replacement cycling attack, I can only <br>invite you to read the full =
disclosure report on how it affects Lightning:<br><a href=3D"https://github=
.com/ariard/mempool-research/blob/2023-10-replacement-paper/replacement-cyc=
ling.pdf">https://github.com/ariard/mempool-research/blob/2023-10-replaceme=
nt-paper/replacement-cycling.pdf</a><br><br>## Discovery<br><br>During the =
year 2022, eltoo lightning channels design are discussed, implemented<br>an=
d reviewed. In this context and after discussions on mempool anti-DoS rules=
, I<br>discovered that the replace-by-fee mechanism could be leveraged to b=
reak Lightning<br>channels security. The finding was reported at the near e=
nd of 2022 to some bitcoin<br>core developers and lightning maintainers.<br=
><br>During the year 2023, mitigations (mainly random rebroadcast of time-s=
ensitive<br>second-stage HTLC transactions) are implemented in the major li=
ghtning implementations<br>and the patched implementations are released for=
 dissemination across the ecosystem<br>during the first half of 2023. Date =
of full disclosure is set for mid-October.<br><br>During the first weeks of=
 October, while I was writing more proof-of-concepts and<br>doing experimen=
tal tests of replacement cycling attacks affecting Lightning, I realized<br=
>that a multi-party transaction could be pinned in the mempool with a branc=
h of jun<br>children blocking further RBF or CPFP of the multi-party transa=
ction and once a<br>replacement cycling trick have been played to kick out =
the junk children, the multi-party<br>transaction is dropped out of the vic=
tim&#39;s mempool.<br><br>A simple proof-of-concept of this attack variant =
was immediately shared with the<br>bitcoin core sec list members. As the fu=
ll disclosure date was already announced<br>for the lightning maintainers, =
I took the initiative to keep the initial schedule<br>for the full disclosu=
re of replacement cycling attacks on the lightning network.<br><br>During t=
he month of September 2024, Peter Todd published a blog post (&quot;Soft-Fo=
rk/<br>Covenant Dependent Layer 2 Review&quot;) with a section 4.3 on Repla=
cement Cycling<br>pointing out how RCA could be a form of economic exploit =
on miners.<br><br>## Background: Block template Construction, Multi-Party T=
ransaction and Replace-by-Fee<br><br>In Bitcoin, all full-nodes are by defa=
ult participating in the transaction-relay<br>network, announcing and broad=
casting new transactions to each other. Among the<br>full-nodes, miners are=
 specific full-nodes searching for a valid proof-of-work<br>to be allowed t=
o add a new block on the chain tip. While searching for a proof-of-work,<br=
>a mining node generates a block template from its local mempools, a cache =
for<br>the unconfirmed transactions. The block template is generally a coll=
ection of<br>unconfirmed transactions sorted by highest paying fees. Miners=
 are incentivized<br>to put transactions in a block template, as there are =
obtaining the fees.<br><br>Among all the bitcoin transaction traffic flowin=
g on the transaction-relay network,<br>there are numerous transactions whic=
h have being historically and which are still<br>multi-party transactions, =
e.g payout batch transaction, coinjoin transaction, <br>lightning liquidity=
 allocating transactions batching, colored coins transactions, etc.<br>One =
aspect of this multi-party transaction is that the inputs and the outputs m=
ight<br>dissociatively belong to a number of users equal or superiors to 2.=
 However, as soon<br>as an input or an output are added to a transaction, t=
his enable the owner of this<br>transaction component to eventually interfe=
res with the propagation of the transaction.<br><br>One mempool mechanism a=
ffecting the propagation of a transaction over the transaction-relay<br>net=
work is the replace-by-fee policy. Originally sketched out loosely by Satos=
hi Nakamoto,<br>it was implemented in Bitcoin Core 0.12.0, and since them t=
here have many (ongoing)<br>refinement to the replace-by-fee policy. Roughl=
y the mechanism works in the following way<br>by generating a new transacti=
on with higher absolute fee / higher feerate, an in-mempool<br>transaction =
spending some of the same coin can be kicked out of the mempool.<br><br>## =
The Problem: Forgeability of a Miner Block Template Ordering<br><br>When a =
miner is assembling a collection of transactions to constitute a block temp=
late<br>for the next block finding, they have to order this block template =
accordingly to the<br>state of their local(s) mempool(s). This state is ord=
ered by the miner to compose the<br>highest rewarding block according to so=
me classifying algorithm (e.g ancestor-feerate)<br><br>However, the generat=
ion of a block template is done &quot;discretely&quot; from the local mempo=
ol<br>state and this state can be read / write in an open way by transactio=
n-relay peers, by<br>abusing the replace-by fee mechanism or the expiration=
 time of transactions, among other<br>tricks.<br><br>Informally, a local me=
mpool can be computationally forged if the average quantity of<br>fees for =
a single unit is inferior to the attacker&#39;s mempool one for a given mea=
surement<br>unit (be it virtual bytes or weight), while the forgery cost fo=
r the attacker stay under<br>the average expected return of engaging in a f=
orgery.<br><br>Of course, mempools consistency has never been a design goal=
 of bitcoin transaction-relay<br>in a distributed system like the peer-to-p=
eer transaction-relay network, and some amount<br>of &quot;forgery&quot; ha=
s always been expected. Nevertheless, it appears from testing and analysis<=
br>there can be significant margins of exploitation offered to malicious ha=
shrate adversaries.<br>One such margin of exploitation can be instantiated =
by mounting a replacement cycling attack<br>on a miner mempool.<br><br>## A=
 Simple Replacement Cycling Attack on a Miner Mempool Example<br><br>Let&#3=
9;s say Mallet and Mary are both miners with equivalent hashrate capabiliti=
es (i.e<br>the same odds to mine a block for a given period). Alice is an e=
xchange doing batch<br>payment to pay its users withdrawing funds from the =
exchange. Mary is a solo miner<br>with limited CPUs / memory resources and =
she is refreshing her mining jobs with a<br>`getblocktemplate` only once by=
 minute.<br><br>During the setup phase of the attack, Mallet opens 2 low-va=
lue accounts at Alice&#39;s<br>exchange and wait for the time lapse of the =
next batch payout to be reached to ask<br>her 2 accounts to make a deposit.=
<br><br>Alice builds a batch payout transactions with N outputs for her hon=
est users and 2<br>more outputs for Mallet. The transaction is finalized an=
d broadcasts over the network<br>of mempools for inclusion in a block templ=
ate. The Alice batch transaction is of<br>size 1000, with ~10 payout for a =
feerate of 2 satoshis per virtual byte.<br><br>As soon as Alice&#39;s batch=
 transaction starts to propagate, Mallet consumes its 2 outputs<br>with 2 c=
hain of junk transactions to reach max package limits (25 descendants) and =
block<br>the carve-out. The junk transactions are of size 150 bytes and fee=
rates 2 satoshis per<br>virtual byte and they have 2 parents: one Alice&#39=
;s payout UTXO and one Mallet&#39;s UTXO.<br><br>Starting from this point, =
Alice&#39;s exchange server logic should either (a) attempts a CPFP<br>or (=
b) attempts a RBF on the batch transaction. As there is no global mempool, =
Alice is<br>uncertain on the explanation for the lack of propagation of her=
 batch transaction, it is<br>most likely she will broadcast a feerate incre=
ase in the dark. To replace Alice&#39;s parent<br>batch transaction and Mal=
let&#39;s junk children transaction, a replace-by-fee must have<br>an absol=
ute fee superior to 9800 satoshis. The replace-by-fee transaction is assume=
d to<br>be blocked by Mallet as this absolute fee, so its fees are 9800 sat=
oshis.<br><br>The feerate increase transaction (a RBF or CPFP) should be ne=
gated by Mallet outbid<br>by the constant cycle of replacement junk transac=
tion. As soon as the RBF or CPFP has<br>been re-cycled out for a give perio=
d, the chain of junk replacement transaction can<br>be re-attached on anoth=
er package to provoke a higher replace-by-fee from Alice&#39;s server.<br><=
br>If the counter-square of the Alice&#39;s RBF and the subsequent replacem=
ent out of Mallet&#39;s<br>transaction is achieved before Mary is fetching =
the latest highest feerate group of the<br>mempools, she should only get Al=
ice root&#39;s batch transaction and Mallet&#39;s junk children<br>transact=
ions.<br><br>At equal odds of mining blocks, the absolute fees yield by the=
ir respective block template<br>is the following:<br>- Mary&#39;s block tem=
plate: 9800 satoshis<br>- Mallet&#39;s block template: 17600 satoshis<br><b=
r>The question is from where Mallet&#39;s advantage is coming. As the owner=
 of the utxos used<br>to build the chain of junk transactions, he can cumul=
ate both spending Alice&#39;s utxo with<br>her own replace-by-fee transacti=
on and a withhold chain of new transactions spending his<br>non-collaborati=
ve UTXOs. Mary is only seeing in her mempool the latest result of mempool<b=
r>acceptance, and not the highest combination of absolute fees for a combin=
ation of given<br>UTXOs.<br><br>It should be noted, the advantage of Mallet=
 can be diluted with the number of replacement<br>cycling done to block the=
 fee-bump of Alice&#39;s batch transaction, due to the RBF penalty.<br>Howe=
ver, the penalty can be compensated by targeting many unrelated multi-party=
 transactions.<br><br>## Solutions<br><br>I&#39;m marking few solutions tha=
t could improve replacement cycling attacks on miners block<br>template, wh=
ile their exact efficiency is still a subject to be analyzed.<br><br>Cluste=
r mempool: this is a proposal to associate each unconfirmed transaction in =
a mempool<br>with related transactions, creating a cluster. Each cluster co=
ntains feerate-sorted chunks<br>consisting one or more transactions. Ideall=
y, the cluster mempool would allow to build more<br>efficient eviction and =
replacement algorithms on top of it. In the context of RCA on miners,<br>it=
 could potentially diminish the differential that can be generated at the a=
dvantage of the<br>attacker.<br><br>Replace-by-Feerate: this is proposal to=
 allow replacement to only happen when it would<br>immediately bring a tran=
saction close enough to the top of the mempool to be mined in the<br>next b=
lock or so. In the context of RCA on miners, this could increase the jammin=
g cost<br>burdened by the attacker.<br><br>Chain of Transactions Topologica=
l Restrictions: currently, full-node mempool are generally<br>allowing 25 a=
ncestors and 25 descendants by default. By restraining the topological dime=
nsions<br>of a chain of transaction, this renders the computation of mempoo=
l algorithms more tractable.<br>In the context of RCA on miners, this might=
 have the indirect effect to potentially diminish<br>the differential that =
can be generated at the advantage of the attacker.<br><br>UTXO-based Transa=
ction Announcement: currently, transaction-relay is only done based on the<=
br>txid or wtxid of a transaction. In the future, the best feerate known fo=
r a set or subset<br>of UTXOs could be propagated among nodes, before they =
proceed to the actual transaction relay.<br>In the context of RCA on miners=
, an enhanced mempool could be re-download the best known<br>in the past tr=
ansaction branch for a UTXO, if there is subsequent downgrade of the best<b=
r>feerate branch for this same given UTXO.<br><br>## Timeline<br><br>- 2022=
-12: Report of the replacement cycling attacks on lightning channel to a se=
lected<br>group of bitcoin core contributors and lightning maintainers<br>-=
 2023-06: Week of mid-october 2023 proposed for full disclosure of replacem=
ent cycling attacks<br>on the Lightning Network<br>- 2023-08-10: CVEs assig=
ned by MITRE for the Lightning project<br>- 2023-10-05: Pre-disclosure of L=
N CVEs numbers and replacement cycling attack existence<br>to <a href=3D"ma=
ilto:security@bitcoincore.org">security@bitcoincore.org</a><br>- 2023-10-15=
: Finding that replacement cycling attack can put a DoS risk on multi-party=
<br>transactions and the hypothetical effect on miners mempools ; Sharing o=
f a proof-of-conceptual test<br>to <a href=3D"mailto:security@bitcoincore.o=
rg">security@bitcoincore.org</a><br>- 2023-10-16: Full disclosure of CVE-20=
23-40231 / CVE-2023-40232/ CVE-2023-40233 / CVE-2023-40234<br>and replaceme=
nt cycling attacks<br>- 2024-09-02: Peter Todd publishes a public blog post=
 analysis some soft-fork proposals and in<br>this post loosely mention the =
potential effect of RCA on miners<br>- 2024-09-07: Sharing to Peter Todd, A=
ntoine Poinsot and Greg Maxwell the proof-of-conceptual<br>test of RCA at t=
he miner-level and hypothesis<br>- 2024-09-30: Sharing additional info on R=
CA at the miner-level to the same group of 4 with<br>the addition of Michae=
l Ford, Ava Chow and Eric Voskuil ; Proposal for a disclosure in the last<b=
r>weeks of January<br>- 2025-01-27: Full disclosure of &quot;Replacement Cy=
cling Attacks on Bitcoin Miners Block Templates&quot;<br><br>## Conclusion<=
br><br>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<br>in the global distribution of the =
fee reward coming from confirmed transactions. While the<br>exact practical=
ity of this attack is still to be investigated, the main tricks have been<b=
r>tested both on a classic mempool on a bitcoin core running a 26.0 branch =
and cluster-based<br>mempool on a bitcoin core node running a 29.0 branch.<=
br><br>Do not trust, verify. All mistakes and opinions are my own.<br><br>A=
ntoine <br><br>&quot;trust yourself when all men doubt you,<br>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 but make allowance for their doubting too&quot; - K<br></=
div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CALZpt%2BEnDUtfty3X%3Du2-2c5Q53Guc6aRdx0Z4D75D50ZXjsu2A%40mail.g=
mail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/=
d/msgid/bitcoindev/CALZpt%2BEnDUtfty3X%3Du2-2c5Q53Guc6aRdx0Z4D75D50ZXjsu2A%=
40mail.gmail.com</a>.<br />

--00000000000040cee0062cb1a68d--