Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining
2026-07-27 • Cryptography and Security
Cryptography and SecurityComputer Science and Game Theory
AI summaryⓘ
The authors study when it makes sense for Bitcoin miners to follow the rules honestly. Previous work either used complex computations with tight bounds or simpler theory with less accurate results. The authors improve on past theory by using a more realistic model that lets miners choose from more actions and includes different ways to handle ties. They also create an algorithm that finds very precise bounds on when honest mining is the best strategy.
Bitcoin miningproof-of-workincentive compatibilityMarkov Decision Processblockchaintie-breakingmining strategyalgorithmgame theory
Authors
Akira Sakurai, Taishi Nakai, Kazuyuki Shudo
Abstract
When is honest Bitcoin mining rational? This question is central to the incentive design of proof-of-work blockchains. Sapirshtein et al. computationally derived near-tight lower and upper bounds on the incentive-compatibility threshold using a Markov Decision Process. Kiayias et al.'s Blockchain Mining Games instead derived theoretical lower and upper bounds. However, this theoretical approach has two limitations: its model restricts miners to a narrow action space and assumes idealized tie behavior, and its lower and upper bounds are far from tight. We resolve both limitations. We develop a more realistic model with a broader miner action space and asymmetric tie-breaking parameters $γ^-$ and $γ^+$. We then propose an algorithm that computes lower and upper bounds on the incentive-compatibility threshold with a maximum error of $9.98006\times10^{-4}$.