Undetectable Selfish Mining

BY KEYHUNTER 05.03.2025
Undetectable Selfish Mining

Seminal work of Eyal and Sirer\textsuperscript{[7]} establishes that a strategic Bitcoin miner may strictly profit by deviating from the intended Bitcoin protocol, using a strategy now termed \textit{selfish mining}. More specifically, any miner with ( > \frac{1}{3} ) of the total hashrate can earn bitcoin at a faster rate by selfish mining than by following the intended protocol (depending on network conditions, a lower fraction of hashrate may also suffice).

One convincing critique of selfish mining in practice is that the presence of a selfish miner is \textit{statistically detectable}: the pattern of orphaned blocks created by the presence of a selfish miner cannot be explained by natural network delays. Therefore, if an attacker chooses to selfish mine, users can detect this, and this may (significantly) negatively impact the value of BTC. So while the attacker may get slightly more bitcoin by selfish mining, these bitcoin may be worth significantly less USD.

We develop a selfish mining variant that is provably \textit{statistically undetectable}: the pattern of orphaned blocks is statistically identical to a world with only honest miners but higher network delay. Specifically, we consider a stylized model where honest miners with network delay produce orphaned blocks at each height independently with probability ( \beta’ ). We propose a selfish mining strategy that instead produces orphaned blocks at each height independently with probability ( \beta > \beta’ ). We further show that our strategy is strictly profitable for attackers with 38.2% ( \ll ) 50% of the total hashrate (and this holds for all natural orphan rates ( \beta’ )).

1 Introduction

At their core, cryptocurrencies and other blockchain protocols aim to provide a totally-ordered ledger of transactions that can serve as a record of payments. Key to their value proposition is that these ledgers are maintained in a decentralized manner — anyone can join their network and start authorizing transactions (in Bitcoin, this process is referred to as mining and the participants as miners). However, miners must be incentivized in order to authorize transactions, and in particular to follow the intended protocol.

Nakamoto’s 2008 whitepaper [20] introducing Bitcoin applies a clever technique termed proof-of-work — miners are selected to authorize the next block of transactions proportionally to their computational power (often referred to as their hashrate, because they use this computational power to repeatedly compute the hash function SHA-256). That same whitepaper already observes that incentivizing miners to follow the intended protocol can be tricky, however. For example, Nakamoto observes that a miner with ( > \frac{1}{2} ) of the total hashrate in the network can strictly profit by deviating from the Bitcoin protocol. However, for several years it was largely assumed that 50% was the cutoff: as long no miner controlled more than half the total hashrate in the network, everyone should follow the intended protocol.

Eyal and Sirer prove this assumption false with their seminal paper introducing the Selfish Mining strategy (we will overview their strategy in detail in Section 2) [7]. Their strategy is strictly profitable compared to honestly following the Bitcoin protocol even with just ( > \frac{1}{3} ) of the total hashrate. Followup work of Sapirshtein, Sompolinsky, and Zohar later provides an improved strategy that is strictly profitable with just ( \approx 32.9% ) of the total hashrate, which is tight (for a strategic miner with poor network connectivity) [26]. With better network connectivity, Selfish Mining can be profitable with arbitrarily small fraction of hashrate — see discussion in Section 2.

From a mechanism design perspective, these facts initially appear somewhat alarming: Depending on the hashrate of the largest miner, and also on network conditions, following the protocol is not a Nash equilibrium. Moreover, the Selfish Mining attack is in a sense untraceable: because Bitcoin is pseudonymous, there is no way to distinguish among identities of block creators to determine which blocks were created by a dishonest miner. That is, depending on the hashrate of the largest miner and network conditions, there is an untraceable and strictly profitable deviation from the Bitcoin protocol.

However, one key critique of Selfish Mining (and other strategic deviations) in practice is its statistical detectability. That is, the pattern of blocks created in a world with a Selfish Miner does not have any “innocent explanation” due to network latency, and it will be clear that someone is Selfish Mining.(^1) Should Selfish Mining be detected, it is possible that the value of the underlying cryptocurrency will suffer significantly. Therefore, while Selfish Mining may be profitable when denominated in the underlying cryptocurrency (e.g. BTC), it could be wildly unprofitable when denominated in an objective unit of value (e.g. USD).(^2)

The main result of our paper introduces a statistically undetectable Selfish Mining strategy in Theorems 4 and 5. That is, the pattern of block creation induced by our strategy is statistically identical to that of a world with only honest miners but increased latency. The mathematics behind our results apply to the canonical setting studied in Eyal and Sirer’s seminal work: proof-of-work longest-chain protocols with block rewards.(^3) Still, we hope the reader takes away the following conceptual point much

1To clarify: it may not be clear who is Selfish Mining, nor how to punish them, but it will be clear that someone is Selfish Mining. Note also that collecting the relevant data needed to run the statistical test is non-trivial.

2Note that even if a deviator were to hedge against this possibility by shortselling the underlying cryptocurrency, there is still significant uncertainty in how the market might react (which may be sufficient to dissuade a risk-averse player, even if hedges exist to make deviating profitable in expectation).

3Our techniques may certainly be relevant more broadly to longest-chain protocols (e.g. with transaction fees instead of block rewards, or proof-of-stake instead of proof-of-work), simply because these settings have significant technical overlap. Still, we do not claim that any of our formal results carry to another setting, and applying our techniques in this setting may more broadly: attackers concerned about the impact of their attack on a cryptocurrency’s value may seek an undetectable variant. Therefore, designers must consider this possibility when claiming incentive compatibility of protocols (and especially if those claims reference a strategic deviation’s impact on the cryptocurrency’s value).

We discuss the implications of our results in more detail in Section 6. After overviewing related work below in Section 1.1, we proceed with a detailed description of Selfish Mining, along with a description of our model in Section 2. We follow this with formal statements of our main results in Section 3. Section 4 proves a warmup result to demonstrate some key ideas, and Section 5 proves our first main result. Appendix A contains a summary of discussions regarding Selfish Mining in practice. Extensions of our main results and omitted proofs are contained in later appendices.

1.1 Related Work

Strategic Manipulations of Consensus Protocols. Following Eyal and Sirer’s seminal work [7], there have been numerous papers on Selfish Mining. Most relevant to our work are those that understand the limits of its profitability, such as [15, 26]. In analyzing our most general result, we use tools initially developed in [26].

Strategic manipulation of consensus protocols via some form of “block withholding” is studied in a wide array of related domains. Those most similar to our work consider deviations in proof-of-work longest-chain protocols with transaction fees [4], proof-of-stake longest-chain protocols [3, 22, 23, 9], and leader-selection protocols [8]. Our work bears some similarity to these in that we also study strategic manipulation of consensus protocols via block withholding, but the models are distinct.

Other works examine different styles of profitable deviations from Proof-of-Work blockchain protocols. For example, [10, 12, 30, 29] consider manipulating difficulty adjustments to earn extra rewards. [30, 29] do so in particular by manipulating the timestamp of created blocks.

Strategic Manipulation in Practice. Among the broad line of works referenced above, [29] is especially impactful, as they also provide clear evidence of strategic manipulation in practice (which is the first such evidence, to the best of those authors’ and these authors’ knowledge). It is important for future work to understand the impact that their discovery had on the deviator (F2Pool) and/or the underlying currency (ETH) – this would quantitatively impact any risk assessment by miners considering strategic manipulation. In relation to our work, this would impact the importance of statistical undetectability to strategic miners.

We’ve informally used the term “strategic manipulation” to describe deviations from an intended consensus protocol that net the deviator additional rewards \textit{issued directly by the consensus protocol} in the form of block rewards. There is also a significant history of block producers acting selfishly to profit from economic activity on top of consensus protocols (e.g. double-spend attacks.)

Incentives beyond the Consensus Layer. Beyond incentive compatibility concerns arising from block rewards, there is also a growing literature considering incentive design in other aspects of blockchain protocols. One example is recent work on transaction fee mechanism design (auction design for the inclusion of transactions within a block in the presence of strategic block producers) [16, 31, 13, 24, 1, 6, 27]. These works also fit into a growing literature on mechanism design within consensus protocols, but otherwise have no technical overlap with ours.

…still require novel insight.

Detection of Selfish Mining in practice. We are aware of two lines of work related to statistical detection of Selfish Mining. One proposes statistical tests (such as the length of orphaned chains — longer orphan chains are claimed to be indicative of Selfish Mining), and perhaps evaluates them in a simulation environment [5, 28, 25]. To the best of our knowledge, most of these tests have not been deployed in practice, and therefore do not offer an opinion on whether or not Selfish Mining is occurring in practice.

A smaller line of work aims to detect Selfish Mining empirically. [17] claims to be the first paper to detect selfish mining in practice, building upon previous work of similar authors [18, 19]. Their statistical test looks exclusively at the main chain, and focuses on the distribution of consecutive blocks mined by the same miner. Their null hypothesis is that the miner of each block on the main chain should be independent of prior blocks, whereas a Selfish Miner would disproportionately mine their blocks consecutively. They claim that observed mining patterns fail their null hypothesis to varying degrees across five blockchains: Bitcoin, Litecoin, Ethereum PoW, Monacoin, and Bitcoin Cash. But, the authors acknowledge that their null hypothesis could fail for other reasons. For example, note that their null hypothesis would also fail when orphans naturally occur and miners tiebreak in favor of their own blocks (this is because a block competing in a natural fork is more likely to wind up in the longest chain when its creator finds the next block).

2 Background

2.1 Nakamoto Consensus and the Longest Chain Protocol

Bitcoin and many other altcoins use a longest-chain protocol with proof-of-work, which is often referred to as Nakamoto Consensus. We overview relevant details of the protocol below, and refer the reader to resources such as [21] for an explanation of why these details capture the Bitcoin protocol. Note that the features we highlight below are exactly the same features from [7] — the stylized model we pose below is not new, and is extensively studied following [7].

Nakamoto Consensus Game (NCG) There is a set $N$ of $n$ miners, and miner $i$ has hashrate $\alpha_i > 0$. Time proceeds in discrete steps $t = 1, 2, \ldots$. At the start of each timestep $t$, there is a set of blocks $B_t$ that have been previously broadcast, and a set of blocks $B_t^m$ that have been previously created by miner $i$ (perhaps broadcast, perhaps not). Initially, $B_t^i$ is empty for all $i$, and $B_1$ contains a single “genesis block.” At every time step $t$:

  • A miner $m_t$ is selected so that $m_t := i$ with probability $\alpha_i / (\sum_{j=1}^{n} \alpha_j)$, independently of all previous rounds. $m_t$ creates a block $b_t$, and $m_t$ chooses the block to which $b_t$ points: $m_t$ may choose any block in $B_t \cup B_t^m$ (that is, the newly created block must point to exactly one block, and that block can be any block that was broadcast before time $t$, or created by $m_t$ before time $t$, or both).
  • Every miner $i$ can choose to broadcast any blocks in $B_{t+1}^i \setminus B_t$ (that is, every miner $i$ can broadcast any block that they created in a timestep $\leq t$ and have not already broadcast).

We refer to the height of a block $h(b_t)$ as the number of blocks in the path leaving $b_t$ (i.e. by following pointers). A Longest Chain at time $t$ is any block in $B_t$ of greatest height. If the longest chain at time $t$ is unique, we denote by $R_t^i$ to be the fraction of blocks in the longest chain that were created by miner $i$. If the longest chain at time $t$ is not unique, let $t’ < t$ denote the most recent timestep where the longest chain at $t’$ is unique, and define $R_t^i := R_{t’}^i$. Observe that the longest chain at time 1 is unique, so this is always well-defined. Player $i$’s reward is $\lim \inf_{t \to \infty} R_t^i$.

\footnote{Our work and all prior works only consider strategy profiles where the limit exists, so the distinction between lim and lim inf is just a formality.}

In particular, observe in this game that every miner has two decisions every round: (a) if they create a block, what does it point to? and (b) what previously-created blocks do they broadcast? Observe also that miners are paid proportionally to the steady-state fraction of blocks they produce in the longest-chain — this captures the fact that miners are paid primarily according to a block reward that comes with each block, and that Nakamoto Consensus has a difficulty adjustment that causes the length of the longest chain to grow proportionally to time (we again refer the reader to [21, 7] for further details on connecting this game to Bitcoin and related cryptocurrencies).

Longest Chain Protocol The longest-chain protocol asks each miner to use a specific strategy in this game: Whenever you create a block, point to a longest chain, and immediately broadcast your block. We call a miner honest if they follow the longest-chain protocol, and strategic otherwise. The key question is whether it is a Nash equilibrium for every miner to follow the longest-chain protocol.

It is folklore knowledge from Nakamoto’s whitepaper [20] that the longest-chain protocol is not a Nash equilibrium if ( \alpha_i > \sum_j \alpha_j / 2 ) for any ( i ). In that case, Player ( i ) can simply ignore all blocks created by other miners and point only to their own most recent block (broadcasting all blocks upon creation). Then Player ( i ) will have reward 1, and all other players have reward 0.

However, until Eyal and Sirer’s seminal work, it was assumed that the longest-chain protocol is indeed a Nash equilibrium when ( \alpha_i < \sum_j \alpha_j / 2 ) for all ( i ).

2.2 Selfish Mining

We now overview the Selfish Mining strategy, and review its performance when all other miners are using the longest-chain protocol. Let’s first consider the case where all other miners break ties in favor of the strategic miner ( i ) (that is, if the longest chain is not unique, they will point their block towards the one that is created by miner ( i )). Consider the following strategy in NCG:

Strong Selfish Mining:

  • When selected to mine a block, point to a longest-chain, breaking ties in favor of a block created by yourself.
  • Do not immediately broadcast this block. Instead, during any round ( t ) where you are not selected to mine, and the longest chain before round ( t ) has height ( h ), broadcast a block of height ( h + 1 ) (if you have one).

If a strategic miner ( i ) uses Strong Selfish Mining and all other miners follow the longest chain protocol, then the following occurs. First, every block created by miner ( i ) is broadcast during the same round as a block created by another miner of the same height. In other words, every height either contains a single block created by a miner ( \neq i ), or two conflicting blocks broadcast during the same round, with one created by miner ( i ). Second, because every miner tiebreaks in favor of miner ( i ), all of ( i )’s blocks will enter the longest chain (and conflicting blocks will not). Therefore:

Theorem 1 ([7]). If all miners ( \neq i ) use a longest-chain protocol that tiebreaks in for Miner ( i ), and Miner ( i ) uses Strong Selfish Mining, then Miner ( i ) gets reward ( \frac{\alpha_i}{\sum_j \alpha_j} > \frac{\alpha_i}{\sum_j \alpha_j} ).

Strong Selfish Mining is strictly profitable for any ( \alpha_i > 0 ), but relies on the fact that all other miners tiebreak in its favor. Eyal and Sirer connect tiebreaking in the above-described Nakamoto Consensus Game:

[ ^5 \text{Note that, beyond the fact that Player } i \text{ is accumulating all of the mining rewards, they control the entire content of the ledger, and can launch significantly more malicious attacks.} ]

to network connectivity in practice. Really, a “timestep” in the Nakamoto consensus game corresponds to “some miner has just succeeded in inverting SHA-256 and created a new block.” An extremely well-connected miner can (a) listen for this block to be broadcast, and then (b) broadcast their own previously-withheld block, while still (c) ensuring that their own block arrives at other miners first. Mapping this onto the stylized Nakamoto consensus game yields Strong Selfish Mining. For the rest of this paper, we’ll replace “during any round ( t ) where you are not selected to mine, and the longest chain before round ( t ) has height ( h )” with “during any round ( t ) where another miner broadcasts a block of height ( h + 1 )” to emphasize this connection (and so that our language sounds less tailored to this specific stylization).

Of course, it is not realistic to assume that any strategic miner has such strong network connectivity. Eyal and Sirer further pose the (canonical) Selfish Mining strategy that is profitable even when the strategic miner loses all tiebreaks — this corresponds to a reality where the poorly-connected miner can still execute (a) and (b), but not (c). Instead, their canonical strategy (paraphrased below) relies only on the fact that honest miners will still always select a strictly longer chain over a strictly shorter one.

Selfish Mining:

  • When selected to mine a block, point to a longest-chain, breaking ties in favor of a block created by yourself.
  • Do not (necessarily) immediately broadcast this block. Instead, for each block ( b ) of height ( h ) that you create:
    • At the moment where another miner broadcasts a block of height ( h ), broadcast ( b ).
    • Or, during the moment/round where ( b ) becomes pivotal, broadcast ( b ). A block of height ( h ) is pivotal if (a) a block of height ( h – 1 ) has been broadcast by another miner, (b) you created a block of height ( h – 1 ), and (c) you have not yet created a block of height ( h + 1 ).

If a strategic miner ( i ) uses Selfish Mining, and all other miners follow the longest-chain protocol, then the following occurs. At all points in time, there may be a unique longest chain with height ( h ). If so, and a miner ( \neq i ) creates the next block, it will be broadcast and the height increases to ( h + 1 ). If instead ( i ) creates the next block, ( i ) will withhold the block and eventually create a conflict at height ( h + 1 ). If there are multiple longest chains with height ( h ), then miner ( i ) may have created blocks that haven’t been broadcast. If miner ( i ) has only one such block, then it is pivotal, and miner ( i ) will immediately broadcast it (to ensure that it wins the conflict, because it can only win with a strictly longer chain). If miner ( i ) has multiple such blocks, it can safely wait until broadcasting, as long as they broadcast their last hidden block the moment it becomes pivotal. Intuitively, the Selfish Miner faces a risk compared to the longest-chain protocol: when withholding their first block, there is a chance that they do not find either of the next two blocks. In this case, their block is orphaned. If they find exactly one of the next two blocks, then this block becomes pivotal and broadcast — this allows the Strategic Miner to orphan another miner’s block (thus increasing its own ratio). If instead they find both of the next two blocks, then they now have a lead of three withheld blocks, and will be able to orphan even more blocks of other miners (thus further increasing its own ratio). Because there is a risk, the strategy is only profitable for sufficiently large ( \alpha_i ).

Theorem 2 ([7]). If all miners ( \neq i ) use a longest-chain protocol that tiebreaks against Miner ( i ), and Miner ( i ) uses Selfish Mining, then Miner ( i ) gets reward ( > \alpha_i ) if and only if ( \alpha_i > 1/3 ).

6A block is “orphaned” if it is not in the eventual longest chain.

2.3 Detecting Selfish Mining

Because Bitcoin is pseudonymous, an attacker can create a new public key for every block they create, so there is no record of the same miner creating multiple blocks. With no identity attached to any particular block, there is little to distinguish the Selfish Miner’s blocks from others.(^7)

While a Selfish Miner may not be identifiable, their presence is statistically detectable. To help make this point more rigorous, consider the following generalized Nakamoto consensus game, parameterized by a latency $\ell$.(^8)

Nakamoto Consensus Game, parameterized by $\ell$ ($\ell$-NCG) The Nakamoto Consensus Game, parameterized by $\ell > 0$ is identical to the Nakamoto Consensus Game except in who is selected to mine during a step $t$. Instead of picking a miner proportional to their hashrate, a coin is flipped independently for each miner $i$ that is heads with probability $\ell \cdot \alpha_i$ (we will only ever consider games where $\ell \leq \max_j {1/\alpha_j}$). The set of coins is repeatedly flipped until at least one lands heads. Then, all miners whose coins are heads produce a block this round.

As $\ell > 0$ approaches 0, the distribution of miners selected to create blocks in each round approaches that of the original Nakamoto Consensus Game, so we formally define 0-NCG as the original NCG (where exactly one miner is selected each round).

$\ell$-NCG is a natural extension of the original stylized model to incorporate a stylized model of latency. Even if every miner is honestly following the longest-chain protocol, there will inevitably be conflicts and orphaned blocks (for example, during any round in which there are multiple miners). We now build up language to formalize what we mean by statistical undetectability.

Definition 1 (View of a Nakamoto Consensus Game). As a Nakamoto Consensus Game is played, we refer to the view as the collection of all blocks that are eventually broadcast (treated as nodes in a directed graph — the only information in the view is the pointer). We also refer to the view up to height $h$ as the collection of all blocks of height at most $h$ that are eventually broadcast. Observe that for any $\ell$-NCG and any strategy profile, the view is drawn according to some distribution.

Definition 2 (Statistically Undetectable Deviant Strategy). We say that a strategy $s$ for miner $i$ in $\ell$-NCG is $\ell’$-statistically undetectable with respect to $\vec{s}{-i}$ if the view of the game when Miner $i$ uses $s$ and and all other miners use $\vec{s}{-i}$ is identically distributed to the view of the $\ell’$-NCG when Miner $i$ uses some longest-chain strategy and all other miners use $\vec{s}{-i}$. We say that an ensemble of strategies ${s{\epsilon}}{\epsilon > 0}$ is statistically undetectable with respect to $\vec{s}{-i}$ if for all $\epsilon > 0$ there exists an $\ell’ \in (\ell, \ell + \epsilon)$ such that $s_{\epsilon}$ is $\ell’$-statistically undetectable with respect to $\vec{s}_{-i}$. In all applications of these definitions, each $s_j$ will be a longest-chain strategy (but may tie-break differently for different applications).

Note that in order to profit, Attacker must create orphans even if the base game is NCG. Therefore, in order for the view to look consistent with fully honest participants, Attacker will need to target an $\ell’ > 0$ (and hence, even if one primarily wishes to study the original NCG as the “real world”, one must study $\ell’ > 0$ for the world created by Attacker).

(^7)But they are not fully indistinguishable. The Selfish Miner’s blocks will always be created before the competing blocks, and this can manifest in a few ways (including timestamps and transaction content). One might therefore propose to mitigate the profitability of Selfish Mining by asking honest miners to tiebreak in favor of blocks that were created most recently. Unfortunately, this creates significant incentive issues (that designers are well aware of): now an attacker need not build upon the current longest-chain because they can just replace it instead. In general, targeted punishments against blocks that could have been created by Selfish Mining may be worthwhile to explore, but this is very far from current norms (and may be impossible to do without creating new incentive issues).

(^8)Appendix B contains a brief discussion relating this stylized latency model to richer latency models considered in Distributed Systems.

Let us now quickly understand why both Selfish Mining Strategies are statistically detectable. Both claims will use the following notation (which our later proofs will also use) – the purpose of this is to ease notational burden and support a reduction from analyzing the full $n$-player game to a 2-player game. To ease notation here, and in the rest of the paper, we will w.l.o.g. always consider Player 1 to be the strategic player.

Definition 3 (Single/Pair). We say that height $h$ in a view of a Nakamoto Consensus Game has state Pair if there is a block of height $h$ created by Player 1, and also a block of height $h$ created by a Player $> 1$ (possibly multiple players). Otherwise, $h$ has state Single.

Definition 4 (SP-Simple). Consider any execution of a Nakamoto Consensus Game where all other players use the same deterministic longest-chain strategy. Consider also modifying the execution so that in every round, if at least one Miner $> 1$ is selected to create a block, instead only Miner 2 creates a block. A strategy for Miner 1 is SP-Simple if it takes identical actions in both games.

That is, when playing against a profile of identical deterministic longest-chain strategies, an SP-Simple strategy is agnostic to how many blocks are created by other miners during a particular round, or which miner created them, given that some other miner created a block during this round.

Proposition 1. Let $s$ be any SP-Simple strategy for Miner 1 and $\vec{s}{-1}$ be a profile where all other players use the same longest-chain strategy $s’$, and $s’$ tiebreaks in either lexicographical or reverse lexicographical order. Then for all $\ell, \ell’$, $s$ is $\ell’$-statistically undetectable for $\ell$-NCG with hashrates $\vec{\alpha}$ with respect to $\vec{s}{-1}$ if and only if $s$ is $\ell’$-statistically undetectable for $\ell$-NCG with hashrates $\langle \alpha_1, 1-\prod_{i=2}^n (1-\alpha_i)^{\ell} \rangle$ with respect to $s’$.

Moreover, Miner 1’s reward using $s$ in $\ell$-NCG with hashrates $\vec{\alpha}$ against $\vec{s}{-1}$ is equal to that when using $s’$ in $\ell$-NCG with hashrates $\langle \alpha_1, 1-\prod{i=2}^n (1-\alpha_i)^{\ell} \rangle$ against $s’$.

A proof of Proposition 1 appears in Appendix F. Intuitively, Proposition 1 follows by observing that a single Player 2 produces a block in the proposed two-player game with the same probability that any Player $> 1$ produces a block in the original game. Proposition 1 allows us to focus just on the two-player game, which has significantly simpler notation.

Proposition 2. For any $\vec{\alpha}$, and any player $i$, Strong Selfish Mining is not $\ell’$-statistically undetectable for any $\ell’$ in the Nakamoto Consensus Game with respect to the strategy profile where other players use longest-chain and tiebreak in favor of $i$.

Proof. We use Proposition 1 and prove the claim for every two-player game. Indeed, observe that in any two-player game parameterized by $\ell$, if we let $\beta’ = \frac{\alpha_1 \cdot \alpha_2}{1-\alpha_1 \cdot \alpha_2}$ denote the probability that both players produce a block in the same round, then height $h$ is Pair with probability $\beta’$ independently for all $h$.

If instead we consider a Nakamoto Consensus Game where Miner 1 uses Strong Selfish Mining, then observe that height $h$ is Single if and only if Miner 2 produces the first block at height $h$, and is Pair if and only if Miner 1 produces the first block at height $h$.

So consider any height $h$ such that $h$ is Single. This means that Miner 2 produced the first block at height $h$ and immediately broadcast it. Therefore, Miner 1 produces the first block at height $h + 1$ with probability $\alpha_1/(\alpha_1 + \alpha_2)$, and height $h + 1$ has state Pair with exactly this probability. If instead $h$ is Pair, then Miner 1 has (at least) one withheld block, and Miner 1 produces the first block of height $h + 1$ with probability $> \alpha_1/(\alpha_1 + \alpha_2)$ (because Miner 2 would need to produce at least the next two blocks in order to produce the first block of height $h + 1$). Therefore, the probability of seeing Single vs. Pair at height $h + 1$ depends on whether height $h$ is Single vs. Pair, and this cannot be identically distributed to honest parties in a Nakamoto consensus game with any latency.

[9] That is, $s’$ either always tiebreaks in favor of 1, or never in favor of 1.

Intuitively, Proposition 2 observes that Strong Selfish Mining is more likely to produce a Pair when it has just produced a Pair (because it must already have hidden blocks at the moment a height is determined to be Pair).

Proposition 3. For any $\vec{\alpha}$, and any player $i$, Selfish Mining is not $\ell’$-statistically undetectable for any $\ell’$ in the Nakamoto Consensus Game with respect to the strategy profile where other players use longest-chain and tiebreak against $i$.

Proof. We use Proposition 1 and prove the claim for every two-player game. Indeed, observe that in any two-player game parameterized by $\ell$, if we let $\beta’ = \frac{\alpha_1 \cdot \ell \cdot \alpha_2 \cdot \ell}{1 – \alpha_1 \cdot \ell \cdot \alpha_2 \cdot \ell}$ denote the probability that both players produce a block in the same round, then height $h$ is Pair with probability $\beta’$ independently for all $h$.

If instead we consider a Nakamoto Consensus Game where Miner 1 uses Selfish Mining, then observe that height $h$ is Single if and only if Miner 1 has no hidden blocks when the block of height $h$ is broadcast. In particular, if two consecutive states $(h, h+1)$ are (Single, Pair), it must be that Miner 1 has no hidden blocks at height $h$, and $h+1$ is determined to be state Pair as soon as Miner 1 finds the next block. From here, state $h+2$ is Pair if and only if Miner 1 finds the next block, which occurs with probability $\alpha_1 / (\alpha_1 + \alpha_2)$.

If instead two consecutive states $(h, h+1)$ are (Pair, Pair), it must be that Miner 1 found a block at height $h+2$ before Miner 2 found a block at height $h$, state $h+1$ is determined to be Pair the moment this happens. From here, state $h+2$ is Pair with probability $> \alpha_1 / (\alpha_1 + \alpha_2)$ (because Miner 2 would need to produce at least the next two blocks in order for Miner 1’s block at height $h+2$ to become pivotal). Therefore, the probability of seeing Single vs. Pair depends on whether the previous two heights are (Single, Pair) vs. (Pair, Pair), and this cannot be identically distributed to honest parties in a Nakamoto Consensus Game with any latency.

Importantly, the above propositions note that Selfish Mining is statistically detectable only by looking at the view of the game. In particular, it does not require timestamping information (which can easily be manipulated [30, 29] and intentionally has minimal role in the consensus protocol), or real-time monitoring of the network (the entire purpose of a consensus protocol is to cope with the fact that messages arrive at unpredictable times due to latency). Still, we briefly discuss in Section 6 alternative detection methods based on these.

3 Main Results and Technical Outline

We now state our main results, which provide a statistically undetectable and profitable Selfish Mining strategy. All of our strategies have the following format: they begin with a strictly profitable selfish mining strategy (for our warmup, Strong Selfish Mining. For our first main result, Selfish Mining. For our second main result, a natural extension of Selfish Mining when there are sometimes natural forks), and sometimes “wastes” a hidden lead in order to preserve undetectability. That is, when a strategic miner has (say) five hidden blocks, they can reap the greatest profit by causing a fork with at least the first four. But, this creates a lot of sequential orphans. Our strategies will sometimes broadcast some of these blocks without creating an orphan. This sacrifices profit, but enables the strategy to appear indistinguishable from latency. The challenge is finding an appropriate broadcast pattern to be undetectable, and also analyzing when such patterns are still strictly profitable. We first begin with a warmup theorem that demonstrates some key ideas.

Theorem 3. Let $\vec{s}{-1}$ be the strategy profile where every miner uses longest-chain and tiebreaks for Miner 1. Then for any $\vec{\alpha}$, there is a statistically undetectable ensemble of strictly profitable strategies for Miner 1 in the Nakamoto Consensus Game with respect to $\vec{s}{-1}$.

We provide a complete proof of Theorem 3 in Section 4. We give quantitative bounds on the profitability of the strategy in Lemma 3. We then prove our first main result:

Theorem 4. Let ( \vec{s}{-1} ) be the strategy profile where every miner uses longest-chain and tiebreaks against Miner 1. Then for any ( \vec{\alpha} ) with ( \alpha_1 \geq \frac{3}{2} \sqrt{\frac{5}{2}} \cdot \sum_j \alpha_j ), there is a statistically undetectable ensemble of strictly profitable strategies for Miner 1 in the Nakamoto Consensus Game with respect to ( \vec{s}{-1} ).

Our bound of ( \frac{3}{2} \sqrt{\frac{5}{2}} ) is not tight for our strategy, although we provide a complete description of an infinite Markov chain that can be simulated in order to nail the tight bound to higher precision.(^{11}) Interestingly, even our loose bound is not too far from the 1/3-fraction of hashrate that is required for Selfish Mining to be profitable without concern for undetectability. This establishes that adding undetectability to a profitable strategy (if possible) need not significantly detriment its performance.

We include a complete proof of Theorem 4 in Section 5. Quantitative bounds on the profitability of this strategy are given in Claim 3 and Lemma 4. Finally, we extend Theorem 4 to begin from any parameterized Nakamoto Consensus Game.

Theorem 5. Let ( \vec{s}{-1} ) be the strategy profile where every miner uses longest-chain and tiebreaks against Miner 1. Then for any ( \vec{\alpha} ) with ( \alpha_1 \geq 0.382 \cdot \sum_j \alpha_j ), there is a statistically undetectable ensemble of strictly profitable strategies for Miner 1 in the Nakamoto Consensus Game parameterized by ( \ell ) with respect to ( \vec{s}{-1} ).(^{12})

At the end of Section 5, we overview ways in which the proof of Theorem 5 requires additional complexity, and defer a complete proof to Appendix E. In summary, Theorem 5 establishes that a strategic miner can strictly profit against honest miners who tiebreak against them in a way so that the view appears as though all miners are honest but with an arbitrarily small increase to latency.

4 Warmup: Tiebreaking in favor of Strategic Miner

In this section, we prove Theorem 3, which introduces some of the key ideas of our analysis.

For simplicity of notation in this section and in all remaining technical sections, we let ( n = 2 ) and ( \alpha := \alpha_1 / (\alpha_1 + \alpha_2) ). This is w.l.o.g. due to Proposition 1. We will also refer to Miner 1 as Attacker and Miner 2 as Honest. We first remind the reader of the concept of a state, specialized to ( n = 2 ).

Definition 5 (State). When ( n = 2 ), observe that the state of a height ( h ), ( S(h) ), is Pair if and only if both players create a block of height ( h ), and Single if only one player creates a block of height ( h ). We let ( S(0) = \text{Single} ), namely there is a unique genesis block.

We will describe our strategy first as labeling all heights as Single or Pair, and then describe the actual broadcasting strategy to match it. The outline of this section is as follows: Definition 6 describes the labeling strategy. Lemma 1 specifies how the labeling strategy can be implemented via a broadcasting schedule. Lemma 2 argues that this strategy achieves undetectability. Finally, Lemma 3 argues that the strategy is strictly profitable.

(^{10})Note that ( \frac{3}{2} \sqrt{\frac{5}{2}} \leq 38.2% ).

(^{11})We suspect our bound is not far from tight, however.

(^{12})Proposition 5 provides a (significantly) more precise sufficient condition on ( \alpha, \beta’ ) in order for a strictly profitable and undetectable strategy to exist. Theorem 5 follows by verifying that this condition holds for all ( \alpha \geq 0.382 ) and all ( \beta’ \in [0, 1] ). It could be that our sufficient condition also holds for all ( \alpha \geq \frac{3}{2} \sqrt{\frac{5}{2}} ) and all ( \beta \in [0, 1] ), but our computational software is not precise enough to verify this. Recall that ( \frac{3}{2} \sqrt{\frac{5}{2}} \leq 0.382 ), so the gap in analysis for ( \beta’ > 0 ) and ( \beta’ = 0 ) is fairly small.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO