Efficient MDP Analysis for Selfish-Mining in Blockchains

Roi Bar Zur, Ittay Eyal, Aviv Tamar

Abstract

Analyzing selfish-mining strategies in Proof-of-Work blockchains typically involves solving complex non-linear ratio-optimization problems. We present Probabilistic Termination Optimization (PTO), a novel technique that transforms these problems into standard Markov Decision Processes (MDPs) with random termination. PTO achieves a 10x speedup over previous state-of-the-art methods like OSM while maintaining high precision. Applying PTO to Ethereum reveals a lower security threshold of 0.2468, indicating that the network is more vulnerable to selfish mining than previously estimated.

Introduction

In Proof-of-Work (PoW) blockchains, miners are incentivized to follow protocols to earn rewards proportional to their computational power. However, "selfish mining" allows a strategic miner to withhold blocks and create a private chain, potentially earning rewards exceeding their fair share. Determining a blockchain's security threshold—the minimum mining power required for such cheating to be profitable—is mathematically modeled as an MDP.

A significant challenge arises from the difficulty adjustment mechanism. A miner's objective is to maximize the ratio of their rewards to the total blocks found by the network (Average Reward Ratio or ARR), rather than a simple linear sum. Previous methods, such as Optimal Selfish Mining (OSM), addressed this through iterative binary searches, solving a new standard MDP at every step, which is computationally expensive.

Methodology: Probabilistic Termination Optimization (PTO)

PTO simplifies the ratio-optimization problem by augmenting the MDP with a "memoryless" random termination. Instead of solving the ratio directly, the system "tosses a coin" for every unit of difficulty contribution. If the coin lands on tails, the process terminates.

This transformation converts the complex ratio problem into a Stochastic Shortest Path (SSP) problem. The expected total reward in this terminating MDP approximates the reward-to-difficulty ratio of the original infinite-horizon process. Key advantages include:

  • Efficiency: PTO requires solving only a single standard MDP, leading to a significant reduction in computation time.
  • Memory Efficiency: Unlike fixed-horizon termination, PTO's random termination requires no additional state memory, preventing state-space explosion.
  • Provable Accuracy: The approximation error is inversely proportional to the user-defined "expected horizon" ($H$), allowing for a tunable balance between speed and precision.

Experimental Setup

The researchers evaluated PTO using mathematical models of Bitcoin and Ethereum:

  • Bitcoin Model: Based on the Sapirshtein et al. (2016) model, incorporating mining power ($\alpha$) and communication "rushing" ($\gamma$).
  • Ethereum Model: A complex model accounting for "uncle blocks" and specific difficulty adjustment rules. Sparse matrix representations were utilized to manage Ethereum's massive state space.

Key Results and Accuracy

Empirical results confirm that PTO is approximately 10 times faster than the OSM method. Crucially, this speedup does not come at the cost of accuracy. As shown in the comparison table below, the revenue calculated by PTO ($REV_{ARR}$) closely matches the results from the iterative OSM method across various mining power levels ($\alpha$).

Comparison of revenue calculations between PTO and the state-of-the-art OSM method.

The precision of PTO allowed for a more accurate analysis of Ethereum's security. The study found that a rational miner can profit from selfish mining with just 24.68% of the network power, a tighter bound than the previous 26% estimate.

Conclusion

Probabilistic Termination Optimization provides a highly efficient framework for analyzing blockchain security. By linearizing the reward-ratio problem, it enables the use of standard MDP tools on complex protocols like Ethereum. Future work may involve using PTO to stress-test emerging reward schemes and identify vulnerabilities before deployment. While PTO requires setting a horizon parameter $H$ to control error, its speed and scalability make it a superior alternative to iterative search methods.

Summary updated

BibTeX
@inproceedings{zur2020efficient,
  author = {Roi Bar Zur and Ittay Eyal and Aviv Tamar},
  title = {{Efficient MDP Analysis for Selfish-Mining in Blockchains}},
  booktitle = {AFT},
  year = {2020},
  url = {https://openreview.net/forum?id=B7KYgT9cI9H},
}
Figure