Source-linked AI summary
Optimal Selfish Mining Strategies in Bitcoin
Ayelet Sapirshtein, Yonatan Sompolinsky, Aviv Zohar
TL;DR
Selfish mining challenges Bitcoin’s incentive compatibility because withholding blocks can increase an attacker’s revenue and threaten the system. The paper models optimal selfish-mining behavior, develops an ε-optimal policy algorithm with revenue bounds, and evaluates thresholds, countermeasures, delays, and double spending. It finds that optimal policies outperform SM1, require less computational power to become profitable, and under delays give every attacker with α > 0 a strict better response to honest mining.
Problem
Bitcoin’s protocol is not incentive compatible because miners can increase revenue by selectively withholding blocks, with potentially destructive consequences for the system.
Method
The paper extends the selfish-mining model, formulates revenue optimization over the model, and uses an algorithm based on approximate-root search to compute ε-optimal policies and bounds.
Results
Optimal policies earn more than SM1 and are profitable for smaller miners; with network delays, the profit threshold equals 0 and every attacker with α > 0 has a strict better response to honest mining.
Takeaways & Limitations
Selfish-mining resilience depends on attacker resources and communication conditions, while delays make Bitcoin more vulnerable to deviations from the protocol.
Takeaways & Limitations
The optimal gains from deviations under delays remain unquantified, and the overall effect depends on network topology, attacker location, and topology knowledge.
Abstract
from arXiv · showhide
Bitcoin is a decentralized crypto-currency, and an accompanying protocol, created in 2008. Bitcoin nodes continuously generate and propagate blocks---collections of newly approved transactions that are added to Bitcoin's ledger. Block creation requires nodes to invest computational resources, but also carries a reward in the form of bitcoins that are paid to the creator. While the protocol requires nodes to quickly distribute newly created blocks, strong nodes can in fact gain higher payoffs by withholding blocks they create and selectively postponing their publication. The existence of such selfish mining attacks was first reported by Eyal and Sirer, who have demonstrated a specific deviation from the standard protocol (a strategy that we name SM1). In this paper we extend the underlying model for selfish mining attacks, and provide an algorithm to find $ε$-optimal policies for attackers within the model, as well as tight upper bounds on the revenue of optimal policies. As a consequence, we are able to provide lower bounds on the computational power an attacker needs in order to benefit from selfish mining. We find that the profit threshold -- the minimal fraction of resources required for a profitable attack -- is strictly lower than the one induced by the SM1 scheme. Indeed, the policies given by our algorithm dominate SM1, by better regulating attack-withdrawals. Using our algorithm, we show that Eyal and Sirer's suggested countermeasure to selfish mining is slightly less effective than previously conjectured. Next, we gain insight into selfish mining in the presence of communication delays, and show that, under a model that accounts for delays, the profit threshold vanishes, and even small attackers have incentive to occasionally deviate from the protocol. We conclude with observations regarding the combined power of selfish mining and double spending attacks.
1 Introduction
Selfish mining exploits Bitcoin’s block-publication and fork-resolution rules, allowing attackers to increase revenue and potentially threaten system security. This paper develops optimal-policy analysis showing improved attacks, lower profit thresholds, and implications for countermeasures and delayed networks.
- Motivation: Bitcoin’s standard protocol is not incentive compatible because miners can increase revenue by selectively withholding blocks.Eyal and Sirer’s SM1 strategy demonstrates this deviation from immediate block publication.
- Motivation: Selfish mining exploits Bitcoin’s conflict-resolution rule by creating deliberate forks that can cause honest blocks to be discarded.Only blocks on the ultimately valid chain receive rewards.
- Motivation: Selfish mining can become increasingly destructive as attackers gain computational power, potentially enabling control over rewards, double spending, and transaction processing above 50%.The paper notes that successful attackers may also grow by acquiring hardware or attracting miners.
- Contributions: The paper provides an efficient algorithm for computing ε-optimal selfish-mining policies, proves its correctness and error bound, and validates generated strategies in simulation.The algorithm applies to any ε > 0 within the Eyal–Sirer model when other nodes follow the standard protocol.
- Contributions: Optimal policies earn more than SM1 and are profitable for smaller miners, while their gains are relatively small.The paper uses these policies to lower-bound the computational resources required for profitable attacks.
- Contributions: The analysis evaluates a proposed random tie-breaking countermeasure and studies selfish mining under communication delays and alongside double spending.The paper’s structure includes theoretical bounds, algorithmic results, protocol-modification analysis, delay models, and combined attacks.
2 Model
The paper models selfish mining as a single-player decision problem in which an attacker chooses block-building and publication actions to maximize relative revenue. The model tracks fork states, stochastic block creation, communication capabilities, and rewards under an extended action space.
- Assumptions: The attacker controls fraction α of computational power, while honest miners control 1−α; blocks are generated by a Poisson process and assigned accordingly.
- Attacker model: Selfish mining allows the attacker to extend any historical block and withhold created blocks, choosing actions after each block-creation event.
- State representation: The model restricts attention to reasonable strategies maintaining one secret branch after the latest fork, tracking attacker and honest branch lengths as a and h.
- Decision problem: The decision problem is represented by M = ⟨S, A, P, R⟩, with state space, actions, stochastic transitions, and two-dimensional rewards for attacker and honest nodes.
- Objective: The attacker maximizes relative payoff—the share of accepted blocks—rather than its absolute block count, and pathological policies waiting forever are excluded.
- State representation: States are triples (a, h, fork), where fork records whether matching is irrelevant, relevant, or active and therefore affects feasible actions and transitions.
- Objective: The profit threshold is the minimal α, for fixed γ, at which some dishonest policy earns more than honest mining.
3 A Simple Upper Bound
The longest-chain rule yields an immediate upper bound on selfish-mining revenue by limiting the attacker to using each attacker-created block to override one honest block. The paper presents this bound as intuitive general guidance rather than a tight estimate.
- The longest-chain mechanism bounds the attacker’s relative revenue by the strategy of using every attacker-created block to override one honest-network block.
- The bound is usually far from the actual maximal revenue and is provided mainly for general insight.
4 Solving for the Optimal Policy
The paper converts the attacker’s nonlinear relative-revenue objective into a family of linear-reward MDPs and searches for a zero-valued transformed problem. Finite under- and over-paying MDPs then provide computable bounds and an approximately optimal policy.
- 4.1 Method: The nonlinear objective is handled by assuming a candidate revenue ρ, constructing an average-reward MDP, and solving it with standard MDP techniques.
- 4.1 Method: The transformation w_ρ(x, y) = (1−ρ)·x−ρ·y converts two-dimensional rewards into scalar rewards while preserving the original state, action, and transition structure.
- 4.1 Method: Because the optimal transformed value v*_ρ decreases monotonically with ρ, binary search efficiently locates an approximate ρ whose optimal value is zero.
- 4.1 Method: Finite-state under-paying and over-paying MDPs are used to bound the original problem despite continuous search and finite solver accuracy.
- Algorithm: Algorithm 1 takes α, γ, truncation T_0, and error parameters, then returns an approximately optimal policy and revenue bounds.
- Guarantees: The over-paying construction yields an upper bound satisfying ρ′ + 2·(u + ϵ′) > max_{π′∈A}{REV(π′)}.
- Threshold bounds: For fixed γ and α, a computed value u ≤ −ϵ certifies that honest mining is optimal and therefore that the profit threshold satisfies ˆα(γ) ≥ α.
5 Results
The algorithm produces ε-optimal selfish-mining policies and reveals how they differ from SM1, including lower profit thresholds. Under uniform tie breaking, some attackers gain more from deviation despite the modification.
- 5.1 Optimal Values: The algorithm computes ε-optimal policies and compares their revenues with SM1 and a computed upper bound across α values at γ = 0.Table 2 reports attacker revenue under SM1 and ε-OPT policies for various α.
- 5.2 Optimal Policies: Optimal policies differ from SM1 by delaying adopt actions, enabling the attacker to catch up from behind.This behavior violates the longest-chain rule.
- 5.2 Optimal Policies: Optimal policies use match more extensively, overriding the honest chain with one block less when successful with probability γ.The policy tables encode actions for irrelevant, relevant, and active fork states.
- 5.3 Profit Thresholds: Optimal policies induce lower profit thresholds than SM1.Figure 2 compares thresholds generated by optimal policies with those induced by SM1.
- 5.4 Evaluation of Protocol Modifications: Under uniform tie breaking, attackers with γ = 0.5 and 0.2321 < α < 0.5 benefit from the modification, lowering the profit threshold from 0.25 to 0.2321.Equal-length chains are mined equally, giving attackers additional opportunities to match and catch up from behind.
- 5.5 Verification: Simulator revenues matched algorithmic revenues within ±10^-6 after runs of 10^7 block-creation events.The simulator evaluated policies across various α and γ values.
6 A Model that Considers Delays
The delay-aware model accounts for communication latency and naturally occurring forks, and shows that every attacker can benefit from some deviation from honest mining. The paper leaves the optimal gains from such deviations unquantified.
- Model and qualitative effects: Communication delays create natural chain splits and make attacker capabilities depend on network topology, location, and available knowledge.The delay model also allows partial state knowledge and blocks published too late to reach the honest network.
- Main result: Any attacker with α > 0 has a strict better-response strategy to honest mining when the network suffers delays.The paper concludes that the selfish-mining profit threshold therefore equals 0.
- Proof strategy: The policy π_k waits instead of adopting at state (k−1, k), then attempts to catch up until success or discovery of another honest block.Its expected rewards at that state exceed those of honest mining under the stated comparison.
- Proof strategy: The comparison uses a success-probability lower bound q, with positive reward for overriding the honest chain and negative reward for failure.The bound is chosen to avoid dependencies on k and is derived from block-generation and communication-delay events.
- Implications: Delays make the algorithm’s delayed-adoption feature more important because natural splits occur even when all miners follow honest mining.The paper states that the additional benefit is mild without delays but becomes more important under latency.
- Limitations: The optimal gains from delay-induced deviations remain an open question, and vulnerability increases when delays become more prominent, such as with larger blocks.The paper does not quantify the optimal gains in the delay setting.
7 Effect on Double Spending Attacks
Selfish mining can be combined with double spending by hiding a conflicting transaction in secret blocks while conducting public transactions. If selfish mining is at least as profitable as honest mining, repeated double-spending attempts can eventually succeed without an additional cost.
- Combined attacks: An attacker can continuously selfish-mine while hiding a conflicting transaction in its secret blocks for a public transaction.If the selfish-mining attack succeeds after the receiver accepts the public payment, the conflicting transaction may also succeed.
- Security consequence: A miner whose selfish-mining revenue is at least honest-mining revenue bears no cost for continuously attempting double spending and eventually succeeds.The argument concerns repeated attempts enabled by selfish mining that is no less profitable than honest mining.
- Security consequence: Even miners unable to profit from selfish mining alone might become profitable in the long run by combining selfish mining with double spending.The paper identifies this combination as potentially affecting the profit threshold.
8 Related Work
The paper extends prior selfish-mining models by analyzing optimal policies beyond SM1 and by considering communication delays. It contrasts its conclusions with earlier results on Nash equilibria, delayed SM1, and Bitcoin stability.
- Bitcoin incentives: Nakamoto’s model requires a majority of protocol-following nodes for blockchain security, while Kroll et al. identify longest-chain extension as a weak non-unique Nash equilibrium in a simpler model.The simpler model does not account for block withholding.
- Selfish mining: Eyal and Sirer’s SM1 withholds blocks but otherwise follows the longest-chain rule, whereas this paper finds that longest-chain adherence is not always a best response.The paper also claims to characterize optimal policies and compute the threshold for honest mining as a strict unique Nash equilibrium.
- Communication delays: The paper’s model differs from prior delayed-SM1 analysis, which used memoryless block transmission and found SM1 unprofitable under that model.The authors instead show that other profitable selfish-mining attacks exist with delays.
- Adjacent work: Prior work also reports incentives not to propagate transactions and studies block creation, throughput, double spending, and Bitcoin stability from related perspectives.These works provide surrounding analyses rather than the paper’s central optimal-policy result.
A Generality of the Model
The paper justifies restricting attention to a three-action strategy model, with wait added, without loss of optimality. Its argument shows that extending alternative branches or overriding with extra blocks cannot improve the attacker’s value under the model.
- Generality of the model: The general strategy space allows extending arbitrary block-tree locations and publishing more than h + 1 blocks when overriding.The paper argues that these actions are suboptimal and formalizes the restriction below.
- Override restriction: Publishing multiple blocks at once can be replaced by waiting without reducing the strategy’s value, using the paper’s value-function argument.The construction changes an override-by-j action to wait and preserves the relevant continuation value.
- Scope boundary: The formal proof has an informality because immediate rewards for adopt and override make reversing decisions on older abandoned chains hypothetical under the model.The paper nevertheless argues that adopting older abandoned chains would be suboptimal.
- Branch restriction: If an alternative branch B was available before the first deviation, extending the current public-chain block H0 was already at least as profitable and remains dominant under future events.Thus the attacker can repeat the initial choice of H0 instead of B.
- Branch restriction: If B was created later, extending the attacker’s existing block A_l is likewise at least as profitable, so alternative branch extensions can be discarded.This supports restricting strategies to the current secret branch and the honest network’s current longest branch.
- Conclusion: The resulting restriction retains the three actions adopt, override, and match, with wait as a fourth action.The paper presents this restricted action scheme as sufficient for optimal strategies.
B Proof of Proposition 1
The proof bounds selfish-mining revenue by mapping overridden honest blocks to attacker blocks, then uses long-run block counts to derive the revenue limit. The bound is tight when γ = 1 under SM1.
- Every overridden honest block is mapped to an attacker block because overriding requires publishing a longer attacker chain.This establishes an upper bound on the number of honest blocks excluded from the main chain.
- At time T, the honest network has l_T = T − k_T blocks when the attacker has built k_T blocks.The proof compares these cumulative block counts as T grows.
- The Strong Law of Large Numbers supplies the limiting ratios for the attacker’s and honest network’s block counts.This converts the finite-time count comparison into an almost-sure long-run revenue statement.
- SM1 achieves the bound when γ = 1 because each attacker block overrides one honest block and no attacker block is overridden.Both inequalities in the proof therefore become equalities.
C Correctness of Algorithm 1
The correctness proof establishes that Algorithm 1 terminates and returns an approximately optimal policy and revenue threshold. It combines renewal and Markov-chain arguments with binary search over a monotonically decreasing value function.
- Renewal analysis: Under a fixed stationary policy, τ1 is a renewal time ending when the game reaches a state with transition probabilities α and 1 − α to the two base states.This renewal structure supports long-run reward calculations.
- Renewal analysis: The reachable states form an irreducible positive recurrent Markov chain, allowing the Strong Law of Large Numbers for Markov chains to derive long-run reward limits.Finite expected return times to the reference state establish the recurrence property used in the argument.
- Approximation transfer: For sufficiently small truncated-policy value, an optimal policy in the truncated model is approximately optimal in the full model.The argument transfers guarantees from M^T0_ρ to M when |v^π_ρ| is below the specified tolerance.
- Correctness guarantee: The algorithm’s returned threshold satisfies ρ′ + 2 · (u + ǫ′) > maxπ′∈A {REV (π′)}.This gives an explicit upper-bound relation between the computed quantities and the best policy revenue.