TL;DR
Researchers from Technion have developed Probabilistic Termination Optimization (PTO), a novel technique that simplifies the complex task of finding optimal "selfish mining" strategies in blockchains. By transforming a non-linear ratio-optimization problem into a single, standard Markov Decision Process (MDP) with random termination, PTO achieves a 10x speedup over previous methods and has already been used to lower the known security threshold for Ethereum to 0.2468.
What Problem Does This Paper Address?
In Proof-of-Work (PoW) blockchains like Bitcoin, "miners" are supposed to follow a specific protocol to earn rewards proportional to their computational power. However, "selfish mining" allows a sufficiently large miner to deviate from the protocol—withholding blocks to create a private chain—to earn more than their fair share.
To determine if a blockchain is secure, researchers calculate a security threshold: the minimum mining power a miner needs before cheating becomes more profitable than being honest. Mathematically, this is modeled as an MDP. The challenge is that blockchains have a difficulty adjustment mechanism. This means a miner's goal isn't just to maximize rewards, but to maximize the ratio of their rewards to the total blocks found by the network.
Standard MDP tools are designed to maximize a linear sum of rewards, not a non-linear ratio (called an Average Reward Ratio or ARR-MDP). Previous state-of-the-art methods (like OSM) solved this by running a slow binary search, solving a new standard MDP at every single step of the search.
Methods
The authors introduce Probabilistic Termination Optimization (PTO). Instead of trying to solve the ratio directly or using an iterative search, they augment the MDP with a "memoryless" random termination.
- The "Coin Toss" Intuition: For every unit of "difficulty contribution" (the denominator of the ratio) generated in the system, the MDP "tosses a coin." If it lands on tails, the process terminates.
- Linearization: This transformation turns the complex ratio problem into a Stochastic Shortest Path (SSP) problem. Because the termination is probabilistic and depends on the difficulty contribution, the expected total reward in this terminating MDP naturally approximates the reward-to-difficulty ratio of the original infinite-horizon process.
- Efficiency: Because it only requires solving one standard MDP instead of a series of them, it is significantly faster.
- Provable Accuracy: The authors provide a theoretical proof that the approximation error is inversely proportional to the "expected horizon" ($H$)—a parameter the user can set to balance speed and precision.
Datasets
The paper does not use traditional external datasets. Instead, it utilizes and extends mathematical models of the Bitcoin and Ethereum protocols:
- Bitcoin Model: Based on the Sapirshtein et al. (2016) model, incorporating parameters like mining power ($\alpha$) and communication "rushing" ($\gamma$).
- Ethereum Model: A more complex model that accounts for "uncle blocks" (blocks not in the main chain that still receive partial rewards) and Ethereum's specific difficulty adjustment rules.
- Codebase: The authors validated their work using the original OSM source code for Bitcoin and released their own implementation for both Bitcoin and Ethereum on GitHub.
Key Insights and Ideas
- Memoryless is Key: A naive way to solve the ratio would be to terminate after a fixed number of blocks, but that would require the MDP to "remember" how many blocks have passed, exploding the state space. PTO’s random termination requires zero extra memory, keeping the state space small and manageable.
- Ergodicity Matters: The proof of optimality relies on the fact that these blockchain MDPs are "ergodic"—meaning they eventually return to a starting state (like when the honest miners catch up). This allows the authors to use classical Markov chain results to bound the error.
- Sparse Matrices for Ethereum: While Bitcoin's state space is relatively small, Ethereum's is massive due to uncle block tracking. The authors used sparse matrix representations to fit the Ethereum transition matrix into memory, a hurdle that previous researchers avoided by using Deep Reinforcement Learning (which is less precise).
Key Results
- Speed: PTO is approximately 10 times faster than the previous state-of-the-art (OSM) while maintaining the same level of accuracy.
- Ethereum Security: Using PTO, the authors found that a rational miner in Ethereum can start profiting from selfish mining with just 24.68% of the network power. This is a tighter (lower) bound than previous estimates, which were around 26%.
- Convergence: Empirical tests showed that the approximate revenue converges very quickly to the optimal value as the expected horizon ($H$) increases, confirming the theoretical $O(1/H)$ error bound.
Limitations and Future Work
- A Priori Error Bounds: Unlike the binary search method (OSM), which takes a target error ($\epsilon$) as an input, PTO's error is controlled by the horizon $H$, but the exact error for a specific $H$ isn't known before running the calculation.
- Model Truncation: To keep the state space finite, the authors have to limit the "maximum fork length." While they show that very long forks are statistically improbable, it remains a necessary approximation for any MDP-based approach.
- Future Directions: The authors suggest PTO could be used to "fuzz" or stress-test new blockchain reward schemes to find vulnerabilities before they are deployed in the real world.
Summary updated