Leveraging the Verifier’s Dilemma to Double Spend in Bitcoin

BY KEYHUNTER 05.03.2025
Leveraging the Verifier’s Dilemma to Double Spend in Bitcoin

We describe and analyze \textit{perishing mining}, a novel block-withholding mining strategy that lures profit-driven miners away from doing useful work on the public chain by releasing block headers from a privately maintained chain. We then introduce the \textit{dual private chain (DPC) attack}, where an adversary that aims at double spending increases its success rate by intermittently dedicating part of its hash power to \textit{perishing mining}. We detail the DPC attack’s Markov decision process, evaluate its double spending success rate using Monte Carlo simulations. We show that the DPC attack lowers Bitcoin’s security bound in the presence of profit-driven miners that do not wait to validate the transactions of a block before mining on it.

\textbf{Keywords:} Bitcoin · Double spending · Block withholding attack

\section{Introduction}

Bitcoin’s security level is traditionally measured as the proportion of the mining power that an adversary must control to successfully attack it. Nakamoto assumed that an adversary would not control the majority of the mining power [28]. If this assumption does not hold, an attacker is able to spend a coin twice and affect the system consistency in what is known as a double spending attack or 51% attack. The soundness of the honest majority assumption has been discussed in the literature and mechanisms have been proposed to harden the mining process against the 51% attack without completely eliminating it [11,37,23,8].

Despite rewarding miners with newly minted coins and transaction fees, the Bitcoin mining process has also been shown to be vulnerable to selfish behaviors. Using selfish mining, a miner withholds mined blocks and releases them only after the honest miners have wasted computing resources mining alternative blocks. Selfish mining increases a miner’s revenue beyond the fair share it would obtain.

\textsuperscript{⋆} This work was partly performed while Tong Cao was with the University of Luxembourg. \textsuperscript{†} These authors are listed in alphabetical order and contributed equally. \textsuperscript{†} This paper will appear on the 27th Financial Cryptography and Data Security conference (FC 2023).

by following the default Bitcoin mining protocol [19]. Using simulations, selfish mining has been shown to be profitable only after a difficulty adjustment period in Bitcoin for any miner with more than 33% of the global hash power [21,30]. Variants of selfish mining further optimize a miner’s expected revenue [34].

Additionally, miners face the verifier’s dilemma [26,36,7], where upon receiving a block header they have to decide whether they should wait to have received and verified the corresponding transactions, or whether they should start mining right away based on the block header. Different miners might react differently to this dilemma.

Following previous works, we say that a chain of blocks is public if the honest miners are able to receive all its content, while we say that a chain is private if some contents of the chain are kept hidden by the adversary. In this paper, we show that an adversary can leverage a novel block withholding strategy, which we call perishing mining, to slow down the public chain in an unprecedented manner. More precisely, perishing mining leads miners that react differently to the verifier’s dilemma to mine on different forks. We then present the Dual Private Chain (DPC) attack, which further leverages the verifier’s dilemma to double spend on Bitcoin. This attack is, to the best of our knowledge, the first attack where an adversary temporarily sacrifices part of its hash power to later favor its double spending attack, and the first attack where an adversary simultaneously manages two private chains. Intuitively, the first adversarial chain inhibits the public chain’s growth, so that the second one benefits from more favorable conditions for a double spending attack.

To evaluate the impact of the distraction chain on the public chain we first establish the Markov decision process (MDP) of perishing mining. From this MDP, we obtain the probability for the system to be in each state, and quantify the impact of perishing mining on the public chain, i.e., its growth rate decrease. We further describe the DPC attack and its associated MDP. We then evaluate its expected success rate based on Monte Carlo simulations. Counterintuitively, our results show that the adversary increases its double spending success rate by dedicating a fraction of its hash power to slow the public chain down, instead of attacking it frontally with all its hash power.

Overall, this work makes the following contributions.

• We present perishing mining, a mining strategy that is tailored to slow down the progress of the public chain by leveraging the verifier’s dilemma. Using perishing mining an adversary releases the headers of blocks that extend the public chain so that some honest miners mine on them while some honest miners keep mining on the public chain, which effectively divides the honest miners hash power. We present the pseudocode of the perishing mining strategy, establish its Markov chain model and quantify its impact on the public chain growth.

• Building on perishing mining, we describe the DPC attack that an adversary can employ to double spend by maintaining up to two private chains. The first chain leverages the perishing mining strategy to slow down the public chain’s growth and ease the task of the second chain, which aims at double spending. We provide the pseudocode of the attack, and characterize the states and transitions of its Markov chain model.

  • We evaluate the perishing mining strategy and the DPC attack based on extensive Monte Carlo simulations. Our results indicate that perishing mining reduces the public chain progress by 69% when the adversary owns 20% of the global power and 50% of the hash power belongs to miners that mine on block headers without verifying their transactions. In comparison, selfish mining, which aims at optimizing a miner’s revenue share, would only decrease it down by 15%. Our evaluation also shows that an adversary that owns 30% of the global hash power can double spend with 100% success rate when 50% of the hash power belongs to optimistic miners who do not verify transactions (i.e., type 2 miners in §3.2). While we focus on the double spending threat, we also show that the DPC attack allows an adversary to obtain a higher revenue than the one it would obtain by mining honestly or following previously known strategies (Appx. C).

This paper is organized as follows. §2 discusses the related work and provides some necessary background. §3 defines our system model. §4 provides an overview of the DPC attack. §5 details the perishing mining strategy and the DPC attack that builds on it. §6 presents our evaluation results. §7 provides a discussion on other aspects of the attack. Finally, §8 concludes this paper.

2 Related Work

Double spending attack. The double spending attack on Bitcoin was described in Nakamoto’s whitepaper [28], and has been further analyzed since [25,33]. Nowadays, ( z = 6 ) blocks need to be appended after a block for its transactions to be considered permanent. An adversary with more than 50% of the global mining power is able to use a coin in a first validated transaction and, later on, in a second conflicting transaction. Nakamoto characterized the race between the attacker and the honest miners as a random walk, and calculated the probability for an attacker to catch up with the public chain after ( z ) blocks have been appended after its initial transaction. Our DPC attack aims at double spending, and improves upon the classical double spending’s success rate.

Block-withholding attacks. Selfish mining was the first mining strategy that allows a rational miner to increase its revenue share [19], and was later shown to harm the mining fairness [10,15]. Selfish mining is not more profitable than honest mining when the mining difficulty remains constant despite the fact that the adversary is able to increase its revenue share [22,21]. Nayak et al. proposed plausible values for the selfish miner’s propagation factor by utilizing the public overlay network data [29]. They pointed out that the attacker could optimize its revenue and win more blocks by eclipsing [24] honest miners when the propagation factor increases. Gervais et al. analyzed the impact of stale rate on selfish mining attack [21]. Negy et al. pointed out that applying selfish mining in Bitcoin is profitable after at least one difficulty adjustment period (i.e., after approximately two weeks at least) [30]. The DPC attack differs from these works.

Table 1: Notations.

SymbolInterpretation
$\alpha \in [0, 0.5]$Mining power of the adversary.
$\beta \in [0, 1]$Fraction of its mining power that the adversary dedicates to its first private chain.
$\mu \in [0, 0.5]$Mining power of type 2 miners.
$v_t$Value of the transaction the adversary inserts in a block when starting the DPC attack and attempts to double spend.
$v_b$Mining reward per block.

in the sense that its main goal is not to increase the adversary’s mining share but to double spend with higher probability than previous attacks.

Combining selfish mining and double spending. Previous works have shown that an adversary can combine the double spending attack with selfish mining [21,35]. In this attack, the attacker maintains a single chain, which lowers the double spending success rate compared to the initial double spending attack. Our DPC attack shows that an adversary can simultaneously manage two private chains to launch a more powerful double spending attack.

Blockchain Denial of Service Attacks. The BDOS attack proposed strategies to partially or completely shut down the mining network [27]. To do so, the adversary only sends the block header to the network whenever she discovers a block that is ahead of the public chain and there is no fork, and publishes the block body if the next block is generated by the honest miners. By doing so, the profitability and utility of the rational miners and Simplified Payment Verification (SPV) miners is decreased, so that they eventually leave the mining network. The objective of BDOS attacks is to halt the system. An adversary would need to spend approximately 1 million USD per day to shut down the system. Our DPC attack frequently separates other miners’ hash power, which has some similarities with the BDOS attack’s partial shut down case. However, the DPC attack allows the adversary to double spend.

3 System Model

This section introduces the categories of miners we consider, and the adversary that launches a DPC attack. Table 1 summarizes our notations.

3.1 Bitcoin mining and the verifier’s dilemma

Bitcoin mining is a trial-and-error process(^4). The public blockchain (or chain) is visible to all participants, and is maintained by honest miners. To achieve consistency, honest miners accept the longest chain in case of visible forks [31,20,17].

(^4) https://en.bitcoin.it/wiki/Block_hashing_algorithm

However, temporary block withholding attacks have been shown to threaten Bitcoin’s security [25,33,19,34]. Honest miners monitor the network to verify block headers and verify transactions.

In the Bitcoin’s network, block headers are often propagated faster than transactions. Bitcoin’s incentive mechanism does not directly reward the verification of transactions, and BIP-152(^5) introduced the compact block propagation optimization where each node can relay a block in a compact format before verifying its transactions. In this case, a miner that immediately mines on the block header of a correct block gets a time advantage to find the next block. If the miners instead wait and verify the included transactions before the next mining round, then they might sacrifice some non-negligible time in the mining race [26,36,7,12].

We assume that miners follow the traditional block exchange pattern [16,27] using the overlay network. Block dissemination over the overlay network takes seconds, whereas the average mining interval is 10 minutes. While accidental forks (which may occur every 60 blocks [16] on average) reduce the effective honest mining power on the public chain and makes our attack easier, we do not consider accidental forks created by honest miners in order for simplicity. We evaluate mining and double spending strategies using event-based simulations where an event is the discovery of a block by a category of miner. We note (v_b) the mining reward that miners obtain whenever a block they have discovered is permanently included in the blockchain.

3.2 Miner Categories

We consider two types of honest Bitcoin miners that react differently to the verifier’s dilemma: type 1 honest miners and type 2 honest miners.

Type 1 honest miners always follow the default mining protocol and mine on the longest chain of fully verified blocks. In particular, these miners do not mine on a block header that extends a longer non-fully verified concurrent chain.

Type 2 honest miners are profit-driven. As Bitcoin allows miners to accept and generate new blocks without verifying their transactions, type 2 miners start mining on a new block or its header if it extends the longest chain without verifying the transactions it contains. Note that type 2 miners can verify transactions whenever they are received and stop mining on a block header when associated transactions are faulty, or if they successfully mine the next block without having received the previous transactions. In our experiments, we consider two opposite categories of type 2 miners that behave differently upon reception of successive block headers to evaluate the best and worst possible attack results.

  • Optimistic type 2 miners always mine on the longest chain of blocks, which is possibly made of several block whose transactions have not yet been received. In particular, Simplified Payment Verification (SPV) miners [3,4,5,6] can be categorized as optimistic type 2 miners. Upon finding a

(^5) https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki

block, optimistic type 2 miners can create an empty block or include transactions that they know cannot create conflicts (e.g., internal transactions for mining pools).

– Pessimistic type 2 miners only accept to mine on a block header if it extends a chain of full blocks. In particular, a pessimistic type 2 miner that extends a block header would then mine on the last block with transactions not to waste time. If the missing transactions eventually arrive, they then release the next full block. While if they extend over the last full block, they then create a fork.

In practice, it would be difficult for the adversary to identify the exact proportion of the global mining power that each type 2 miner subcategory represents. However, the adversary can be conservative and assume that all type 2 miners are pessimistic, since our attack still improves over the state-of-the-art in that case. We also discuss evidence for SPV mining in §7, which is arguably the simplest type 2 mining strategy.

The adversary owns a fraction $\alpha \in [0, 0.5]$ of the global hash power and its aim is to double spend with higher probability than using previous attacks. When launching its attack the adversary introduces a transaction of value $v_t$ in a block that is included in the public chain and that it attempts to double spend. We also assume that the adversary cannot break cryptographic primitives. Contrary to the selfish mining’s adversary model [19,21], our model does not assume that the adversary has a privileged network access, which is required in selfish mining when the adversary releases a conflicting block it had pre-mined in reaction to the extension of the public chain by an honest miner. For simplicity, we consider that every newly discovered and propagated block is almost instantaneously received by all miners. Several works evaluated and modeled network propagation delays in various cryptocurrencies [16,13,12].

4 Attack Overview

This section provides a high-level description of the Dual Private Chain (DPC) attack, where an adversary maintains two private chains. It then summarizes the respective roles of adversary’s two private chains and their interactions.

4.1 Intuition

In a DPC attack, the adversary maintains two private chains from which it might release block headers or full blocks with the ultimate goal of double spending. During the attack, both of the adversary’s private chains compete with the public chain and may diverge from it starting from different blocks. At a given point in time, the adversary might dedicate its full hash power to one of its private chains, or divide its hash power to simultaneously extend both private chains.

The DPC attack starts when the adversary creates a transaction of value $v_t$ that is the basis for its double spending attempt. Once the adversary generates the block that contains this transaction, she initializes both its private chains

with it and starts mining on it. Initially, the two chains are therefore equal, but they might diverge or converge again later on depending on the created blocks. The double spending attack succeeds if the double spending chain becomes longer than the public chain and if the public chain contains ( z = 6 ) blocks that have been included after the block that contains the initial transaction of the adversary.

Role of the Distraction Chain. The first private chain that the adversary maintains is called the distraction chain. We present perishing mining, a strategy that the adversary employs to maintain its first private chain to waste the hash power of type 2 honest miners and slow down the public chain. Whenever the adversary divides its hash power to simultaneously mine on its two private chains, it dedicates ( \beta ) of its hash power to mine on its first private chain. This chain is private in the sense that the adversary never releases the full blocks, but only the corresponding block headers. The strategy that the adversary applies on its distraction chain divides the honest miners so that they mine on different blocks, and wastes the hash power of type 2 honest miners, which collectively account for hash power ( \mu ). The adversary leverages a BDOS-like attack to only share the header of blocks it discovers on the distraction chain (see Section 5). As the body of those blocks contain adversary-created transactions that are never publicly released, only type 2 honest miners mine on them. In this way, the adversary can distract type 2 honest miners from mining on the public chain.

Role of the Double Spending Chain. The adversary maintains a second private chain to attempt to double spend, and we therefore call this chain the double spending chain. Whenever the adversary is simultaneously mining on its two private chains it dedicates ( \alpha(1-\beta) ) of the global hash power to its second private chain. This chain is private in the sense that, even though block headers might be released, the actual blocks it contains are only published if the double spending attack is successful. Following previous analyses [28,33], we consider that a double spending attempt is successful when: (i) the double spending chain’s length is larger than or equal to the public chain’s length; and (ii) ( z-1 ) blocks have been appended after the block that contains the adversary’s initial transaction (( z = 6 ) in Bitcoin).

4.2 Interplay Between the Two Private Chains

Whenever type 1 and type 2 miners are mining on the same block, the adversary divides its hash power to concurrently mine with hash power ( \alpha\beta ) on the last block of its distraction chain, which is then equal to the public chain, and mine with mining power ( \alpha(1-\beta) ) on its double spending chain. The adversary’s goal is then to create a fork and release a block header so that type 1 and type 2 honest miners mine on different blocks. Note that the adversary will use all its hash power on the second private chain as long as the first private chain is longer than the public chain. This hash power shifting between two private chains is at the core of the DPC attack, which is detailed in Section 5.2.

In the DPC attack, the adversary executes different actions to lead the honest miners to mine on different blocks. Fig. 1 shows two possible scenarios where the attack is initialized based on block ( B_n ). The adversary generates a pair of Fig. 1: Illustration of two possible cases that would lead type 2 miners to waste their hash power during a DPC attack. $B_n, B_{n+1}, B’{n+1}, B{n+2}$ are full blocks, $B^h_{n+1}, B^h_{n+2}$ are block headers, and $B^b_{n+1}, B^b_{n+2}$ are block bodies. We use solid rectangles when the content of a block is visible to honest miners, and a dotted rectangle when it is hidden by the adversary. We note interesting adversary’s actions with $\text{action}_1$ and $\text{action}_2$ (see text for explanations).

conflicting transactions for its double spending attack. The first transaction is released to the public network and collected by the honest miners. The second transaction is kept private by the adversary. In both examples, after $\text{action}1$, the adversary separates her hash power into two parts: she uses $\alpha \beta$ to work on public block lead $B{n+1}$, and $\alpha(1-\beta)$ to work on extending $\text{chain}_2$ to double spend. After $\text{action}_2$ the adversary releases the block header and uses all of her hash power to extend $\text{chain}_2$ for double spending. In both cases, type 2 honest miners (with $\mu$ of global hash power) are led to generate some blocks that will never be included in the public chain due to the adversary’s block body withholding strategy. Consequently, the adversary’s second private chain $\text{chain}_2$, which is used to attempt to double spend, benefits from the distraction of $\text{chain}_1$. We detail the DPC attack in §5.

5 The Dual Private Chains Attack

This section presents the details of the DPC attack, which attempts to lure type 2 honest miners away from extending the public chain, thus, facilitates a double spending attack. We first describe perishing mining, a strategy that a miner can use to slow down the progress of the public chain by making honest miners mine on different blocks. We then describe the full DPC attack that builds on perishing mining to maintain the adversary’s first private chain. We provide an additional discussion on the DPC attack in §7.

5.1 Perishing mining

We call perishing mining the strategy that the adversary uses on the distraction chain (whenever she is mining on it). After the initialization of the perishing mining strategy, the distraction chain and the public chain mine on the same block. The adversary’s action then depends on whether the next block is discovered by the public miners or by itself, as shown in Alg. 1 (Appx. A). First, when the adversary discovers a block $B_{n+1}$ that makes its distraction chain longer than the public chain, it releases the corresponding block header to the network (Alg. 1, l. 9). Upon receiving this header, type 2 miners start mining based on it, while type 1 miners continue working on block $B_n$. Second, when type 1 miners discover a block, the public chain is extended (Alg. 1, l. 13). Third, when type 2 miners find a block, the public chain is extended when the public chain is equal to the private chain (Alg. 1, l. 20). Otherwise, the block is abandoned due to the incomplete block verification, which wastes the hash power of type 2 miners. Note that when type 2 miners are optimistic the private chain is extended when it is not equal to the public chain (Alg. 1, l. 25).

Fig. 2 illustrates the MDP models of the perishing mining strategy assuming that type 2 miners are either optimistic or pessimistic. In this Markov chains, $\alpha$, $\mu$ and $1-\alpha-\mu$, are respectively the probabilities for the adversary, type 2 and type 1 miners to discover a block. We use a tuple $(i,j)$ to denote the state in perishing mining’s MDP, where $i$ and $j$ are respectively the lengths of the private chain and the public chain. The fact that the adversary adopts the public chain whenever it is longer than the private chain implies that $i \leq j$. The adversary releases the header of the leading block to lure type 2 miners. When type 2 miners are optimistic (Fig. 2a), the adversary relies on type 2 miners that also attempt to extend the private chain. When type 2 miners are pessimistic (Fig. 2b), the adversary is not able to use them to extend the private chain. We evaluate the negative impact of perishing mining on the public chain growth in §6.2.

5.2 Combining Perishing Mining and Double Spending

The DPC attack leverages the perishing mining strategy to distract type 2 miners and facilitate double spending. Alg. 2 (Appx. B) details the attack’s pseudocode, where $l_1$, $l_2$, and $l_{pub}$ represent the length of the first private chain $\text{chain}1$, the second private chain $\text{chain}2$, and the public chain $\text{chain}{pub}$ respectively. During the DPC attack, the two invariants $l_2 \leq l_1$ and $l{pub} \leq l_1$ are verified. The distraction chain is therefore always the longest chain among the three chains, and can adopt the public chain and the double spending chain when it is not the longest chain. For example, if it happens that the double spending becomes the longest chain then the distraction chain is set to be equal to the double spending chain. As a consequence, the type 2 miners would mine on the headers of the double spending chain, which would facilitate the double spending attack.

When the DPC attack starts, all three chains are equal and all miners mine on the same block (Alg. 2, l. 1). The adversary’s actions are defined in reaction to block discoveries.

When the adversary finds a block on the distraction chain (Alg. 2, l. 8), it releases the corresponding block header so that type 2 miners mine on it, because the distraction chain is then the longest chain. If the two private chains are equal, the newly found block also extends the double spending chain. As a consequence, the adversary extends the distraction chain, and type 1 miners mine on the last full block of the public chain while type 2 miners mine on the last block header of the distraction chain. The adversary then allocates all its hash power ($\alpha$) to mining on the double spending chain.

When the adversary finds a block on its double spending chain (Alg. 2, l. 20), it releases the block header if the second private chain becomes the longest chain. In this case, type 2 miners then mine on the double spending chain. The first private chain also adopts the second private chain so that the total hash power used to extend the double spending chain is $\alpha + \mu$. When the second private chain is shorter than the public chain, the adversary keeps mining on it with $1 – \beta$ of its hash power. As soon as the double spending chain becomes longer than the public chain and that at least 6 blocks have been appended to the public chain since the beginning of the attack, the adversary uses the double spending chain to override the public chain, and the DPC attack succeeds.

When type 1 miners find a block (Alg. 2, l. 30), they extend the public chain. If the public chain becomes the longest chain, then all honest miners will mine on the public chain and the adversary modifies its first private chain so that it adopts the public chain. The adversary then allocates $\alpha \beta$ of hash power to its distraction chain so that it tries to generate a block that will divide again the honest miners.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO