Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining

Source: arXiv:2607.24415 · Published 2026-07-27 · By Akira Sakurai, Taishi Nakai, Kazuyuki Shudo

TL;DR

This paper addresses the fundamental question of when honest Bitcoin mining is rational from an incentive-compatibility perspective within proof-of-work blockchains. Previous works by Sapirshtein et al. used computational Markov Decision Process (MDP) methods to derive near-tight bounds on the incentive-compatibility threshold, while Kiayias et al. provided theoretical bounds but with limitations: a narrow action space for miners and idealized tie-breaking assumptions, resulting in a wide interval between their lower and upper bounds (0.308 to 0.455).

The authors resolve these limitations by proposing a more realistic model called REAL, which expands miners' action spaces and incorporates asymmetric tie-breaking parameters ( \gamma^- ) and ( \gamma^+ ) representing how honest miners split mining effort on competing chains during ties. They develop new algorithms that compute lower and upper bounds on the incentive-compatibility threshold with a maximum error under 0.001, effectively tightening the theoretical bounds by over two orders of magnitude compared to prior theory. They also prove monotonicity properties of the threshold under variations of the tie-breaking parameters, enabling certified intervals of width at most 0.001 uniformly over all parameter pairs in [0,1]^2.

Overall, this work significantly advances the theoretical guarantee precision for incentive compatibility in Bitcoin mining by combining a rich game-theoretic model with novel algorithmic certificate construction and linear programming techniques to characterize strategic behavior in a more realistic and general setting.

Key findings

• Introduced the REAL mining model with richer miner action space and asymmetric tie-breaking parameters (\gamma^-, \gamma^+ ) capturing realistic tie resolutions.
• Developed certificate linear programs (LP) to rigorously compute provable lower and upper bounds on the incentive-compatibility threshold (\alpha^*(\gamma^-, \gamma^+)) in the REAL model.
• Demonstrated a maximum pointwise gap of 2.415 × 10^-7 in the IDEAL model between lower and upper bound evaluations across 1,000,000 parameter pairs in {0, 0.001, ..., 0.999}^2.
• Using coordinatewise monotonicity, established certified intervals on the threshold for all parameters with width at most 9.98006 × 10^-4, improving prior bound width from 0.147 to under 0.001.
• Proved the incentive-compatibility threshold is coordinatewise nonincreasing in the tie-breaking parameters (\gamma^-, \gamma^+).
• Proposed a canonicalization argument reducing the analysis of strategic miner deviations to a restricted action set IDEAL model, enabling tractable LP formulations.
• Modeled mining state space with detailed canonical states including public ties, private branches, lead states, and reserves to capture all relevant strategic dynamics.
• Provided exact and conservative centered Bellman inequalities characterizing optimal miner utilities for verifying incentive compatibility rigorously via potentials.

Threat model

The adversary is a single Bitcoin miner controlling hash power p less than 50% (p < 1/2) who may deviate arbitrarily from the honest Frontier mining strategy by employing strategic release and mining policies within a broad action space. The adversary cannot control other miners and does not collude. Honest miners coordinate tie breaks according to fixed asymmetric parameters ( \gamma^- ) and ( \gamma^+ ), and the network propagates blocks as modeled, but no external censorship or Byzantine actions other than strategic mining deviations occur.

Methodology — deep read

The authors aim to characterize when honest mining is incentive compatible—that is, when following the honest Frontier strategy forms a Nash equilibrium—under a more realistic and generalized model of Bitcoin mining.

1. Threat model & assumptions: The adversary is a miner with hash power (p < 1/2) deviating strategically from honest Frontier mining. All other miners collectively follow the Frontier strategy. Miners can split hash power between a strategic "core" component and an honest "Frontier" component. The model assumes asymmetric tie-breaking parameters (\gamma^-) and (\gamma^+) controlling how honest miners mine on branches during ties, capturing practical network behaviors.

2. Data & preprocessing: The study is theoretical/computational without empirical data. The model state space is a large discrete Markov process defined by canonical states representing miner lead/lag and tie status. This state space is enumerated over a fine-grained 2D grid of tie parameters (\gamma^-, \gamma^+ \in [0,1]) at resolution 0.001, producing 1,000,000 parameter pairs analyzed exhaustively.

3. Architecture & algorithms: The REAL model defines strategic miner policies over "core" and "Frontier" components, with miners choosing from release or mining actions abiding by mining-anchor rules. The IDEAL model restricts core actions to a canonical finite set (Wait, Hedge, Override, TieWait, Match, etc.) to make analysis tractable. Using this, the authors construct a system of exact and conservative centered Bellman inequalities representing single-step Bellman conditions for a potential function V on the canonical state space. The key contribution is formulating these into linear programs (LPs) that verify whether V satisfying the inequalities exists for a given hash power bound p, certifying incentive compatibility or deviation profitability.

4. Training regime: Not applicable. They solve large-scale LPs numerically. They scan a dense grid of parameters ((\gamma^-, \gamma^+)) and hash power bounds to find tight lower and upper bounds on the incentive compatibility threshold (\alpha^*(\gamma^-, \gamma^+)).

5. Evaluation protocol: For each parameter pair, the method computes LP lower and upper bounds on (\alpha^*) verifying if honest mining is or is not equilibrium up to that hash bound. They prove exact monotonicity properties enabling certified bounds over the entire parameter space. The bounds achieve a maximum width below 0.001 (compared to prior theoretical gaps of ~0.147). The paper reports formal proofs for correctness, stability, and tightness.

6. Reproducibility: The paper does not include public code or datasets but gives fully formal LP formulations and state space representations. The parameter grid and LP constraints are explicitly defined enabling independent verification.

7. Concrete example end-to-end: For a fixed tie-breaking parameter pair, the algorithm enumerates the IDEAL canonical states, sets up the Bellman inequalities for values V(x) over the large discrete state space, encodes recursive constraints from miner action transitions, and solves the LP feasibility problem to certify whether utility gains exist for deviant miners above hash power p, thus bounding the incentive compatibility threshold tightly.

Through this multi-step mathematical modeling, state space canonicalization, and LP-based certificate construction, the authors rigorously bridge the gap between coarse theoretical bounds and computationally near-tight incentive guarantees in realistic Bitcoin mining scenarios.

Technical innovations

• REAL mining model with an expanded action space and asymmetric tie-breaking parameters ( \gamma^-, \gamma^+ ) representing realistic miner behaviors during blockchain ties.
• Formulation of exact and conservative centered Bellman inequalities capturing miners’ long-term utility in a canonical Markov state space model for incentive analysis.
• Construction of finite-dimensional linear programs (LPs) over potentials parametrizing the infinite state space that certify incentive compatibility threshold bounds.
• Proof of coordinatewise monotonicity of the incentive-compatibility threshold in tie-breaking parameters enabling uniform certified near-tight intervals.

Baselines vs proposed

• Kiayias et al. theoretical bounds: incentive-compatibility threshold interval width = 0.147 (0.308 lower bound to 0.455 upper bound)
• Sapirshtein et al. MDP computed bounds: near-tight but computational and model complexity limitations (prior computational complexity)
• Proposed method: maximum pointwise gap on incentive-compatibility threshold under 9.98006 × 10^-4 across 1,000,000 parameter pairs, improving tightness by two orders of magnitude

Limitations

• The model assumes a fixed set of miners with static hash power shares and does not consider dynamic entry/exit or network churn.
• The adversary is restricted to unilateral deviations; collusion or multi-miner strategic coalitions are not analyzed.
• The LP approach, while mathematically rigorous, relies on numerical solvers and discretization which may impose scalability challenges beyond the demonstrated grid.
• The REAL model, though more realistic than IDEAL, still idealizes aspects like network delays or miner communication behaviors not explicitly modeled.
• Code and implementations are not publicly released, limiting immediate reproducibility or application without re-implementation.

Open questions / follow-ons

• How does the incentive-compatibility threshold behave under colluding multiple adversaries or miner coalitions beyond unilateral deviations?
• Can the REAL model be extended to incorporate network latency, messaging delays, or probabilistic network partitions affecting tie-breaking behavior?
• What are the computational tradeoffs and potential scalability improvements for certificate LP resolution on higher-dimensional or dynamic miner hash power profiles?
• How robust are the theoretical bounds under more complex blockchain reward schemes or other consensus protocols beyond proof-of-work like proof-of-stake?

Why it matters for bot defense

For bot-defense or CAPTCHA practitioners focused on blockchain-based anti-abuse or decentralized verification systems, understanding the incentive landscape of Bitcoin mining is critical. This paper provides a mathematically rigorous characterization of when rational miners have no incentive to deviate from honest mining, even when allowed a wide range of strategic actions, under realistic tie-breaking assumptions. This insight helps in designing blockchain protocols or bot-defense mechanisms that rely on proof-of-work security guarantees, by precisely quantifying mining power thresholds below which the protocol's incentive structure is stable.

Moreover, the approach combining game-theoretic modeling with algorithmic certificate methods can inspire analogous techniques in CAPTCHA or bot-detection to formally verify equilibrium properties or robustness guarantees in adversarial systems. The detailed treatment of tie resolution and miner action spaces offers a framework for designing anti-censorship and anti-manipulation criteria crucial for decentralized verification. However, the highly domain-specific focus on mining incentives means direct applicability requires careful adaptation. The methods highlight how precise incentive alignment analysis can tighten trust in blockchain-based systems underpinning some modern bot-defense solutions.

Cite

@article{arxiv2607_24415,
  title={ Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining },
  author={ Akira Sakurai and Taishi Nakai and Kazuyuki Shudo },
  journal={arXiv preprint arXiv:2607.24415},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.24415}
}

Read the full paper

• arXiv:2607.24415 (abstract)
• arXiv:2607.24415 (PDF)