Source-linked AI summary
Blockchain Mining Games
Aggelos Kiayias, Elias Koutsoupias, Maria Kyropoulou, Yiannis Tselekounis
TL;DR
The paper asks how Bitcoin miners’ incentives shape block selection and release, and formalizes these choices as stochastic games on block trees. It analyzes immediate-release and strategic-release complete-information models, finding thresholds below which Frontier is a Nash equilibrium and above which miners may deviate. The study provides bounds for both settings while leaving tighter thresholds and higher-power equilibria open.
Problem
Miner incentives can produce strategic branching and vulnerabilities, but systematic analysis of miners’ block-selection and release choices remains difficult.
Method
The paper studies two complete-information stochastic games on rooted block trees, modeling miners’ block choices and, in the strategic-release model, their release decisions.
Results
Frontier remains a Nash equilibrium below computational-power thresholds, with 0.361 ≤ h0 ≤ 0.455 for immediate release and ˆh0 ≥ 0.308 for strategic release.
Takeaways & Limitations
Miners with sufficiently large computational power may mine away from the frontier or withhold blocks, creating strategic deviations from the expected honest behavior.
Takeaways & Limitations
The analysis restricts miners to complete information and leaves threshold tightening and equilibria above the thresholds open.
Abstract
from arXiv · showhide
We study the strategic considerations of miners participating in the bitcoin's protocol. We formulate and study the stochastic game that underlies these strategic considerations. The miners collectively build a tree of blocks, and they are paid when they create a node (mine a block) which will end up in the path of the tree that is adopted by all. Since the miners can hide newly mined nodes, they play a game with incomplete information. Here we consider two simplified forms of this game in which the miners have complete information. In the simplest game the miners release every mined block immediately, but are strategic on which blocks to mine. In the second more complicated game, when a block is mined it is announced immediately, but it may not be released so that other miners cannot continue mining from it. A miner not only decides which blocks to mine, but also when to release blocks to other miners. In both games, we show that when the computational power of each miner is relatively small, their best response matches the expected behavior of the bitcoin designer. However, when the computational power of a miner is large, he deviates from the expected behavior, and other Nash equilibria arise.
1 Introduction
The paper models miners’ strategic choices in Bitcoin as complete-information stochastic games, focusing on which blocks to mine and when to release them. It identifies computational-power thresholds below which Frontier remains a Nash equilibrium and above which miners may deviate.
- Motivation: Game-theoretic analysis matters because miner incentives affect blockchain execution, Bitcoin’s survival, and the protocol’s strengths and vulnerabilities.
- Models: The paper studies two complete-information models that isolate miners’ choices of which block to mine and when to release mined blocks.The complete-information assumption weakens immediate applicability but provides a clean framework for rigorous analysis.
- Game structure: Miners build a rooted block tree, succeed with probabilities proportional to computational power, and receive utility from blocks in the common history.The common history is the longest path from the root.
- Strategic deviations: Above a computational-power threshold, a miner may mine non-frontier nodes or withhold blocks so others spend power on blocks excluded from the common history.
- Results: 0.361 ≤ h0 ≤ 0.455: in the immediate-release game, Frontier is a Nash equilibrium below the threshold; experiments place the threshold near h0 ≈ 0.42.A miner with at most 36% computational power cannot gain more than his fair 36% reward share, while miners above 46% always deviate.
- Results: 0.308: in the strategic-release game, the threshold is rigorously lower bounded by ˆh0 ≥ 0.308, the root of p^3 − 6p^2 + 5p − 1.The bound is exact but suboptimal and is obtained through exact best-response analysis rather than computational approximation.
- Open problems: The analysis leaves open tightening both thresholds and characterizing Nash equilibria above them.
2 The Bitcoin Mining Game and its Variants
The paper formalizes Bitcoin mining as stochastic games on rooted block trees, with miners choosing where to mine and, in one model, when to release blocks. It defines payment, state, and strategy rules while explicitly restricting the analysis to complete information.
- Game parameters: Miners’ success probabilities p1, …, pn are proportional to computational power and sum to 1; the model normally assumes exactly one miner succeeds per phase.The paper notes that simultaneous successes and phases with no awarded block are omitted in the basic model.
- Payments: The payment depth d delays rewards until a sufficiently long descendant path exists; the current Bitcoin implementation uses d = 100, while the analysis mainly considers d = ∞.Stale siblings and their descendants receive no later payment.
- Game representation: The game state is a rooted tree whose labeled nodes represent mined blocks, with at most one node labeled for each miner at any level.
- Scope: The paper analyzes complete-information variants because incomplete-information private states and beliefs make the full game substantially more complex.The strategic-release model is presented as an intermediate theoretical model for studying block withholding.
- Immediate-release model: In the immediate-release model, every mined block is released immediately and becomes available for continued mining.
- Strategic-release model: In the strategic-release model, a mined block becomes common knowledge immediately, but its creator may postpone release, preventing others from mining from it.
- Strategies: A strategy consists of a mining function selecting a public node and a release function adding private tree material to the public state.Both functions depend on the miner’s state of knowledge.
- Frontier: Frontier releases every mined block immediately and selects one of the deepest nodes; the immediate-release game is its special case with release fixed.
3 The Immediate-Release Game
The immediate-release game models miners choosing which announced block to extend, with Frontier tested as a best response and Nash equilibrium. The analysis identifies computational-power thresholds below which Frontier remains optimal and above which miners benefit from deviating.
- Game model: The game reduces to Miner 1 choosing among mining, capitulation, and winning states while Miner 2 follows Frontier.States are represented by two branch lengths, (a, b), after stale branches are pruned.
- Game model: Miner 1’s long-run objective is to maximize expected gain per level, represented by a potential function measuring the advantage of state (a, b).The potential is defined by subtracting long-run gain from finite-horizon expected gain.
- Equilibrium criterion: Frontier is a Nash equilibrium when each miner’s best response has expected gain equal to their relative computational power.When all miners follow Frontier, revenue is proportional to computational power.
- Threshold results: For the immediate-release model, Frontier is a Nash equilibrium when every miner has computational power below 0.361.Theorem 1 supplies the rigorous lower-side guarantee.
- Threshold results: The experimentally estimated threshold is h0 = 0.418, while Frontier is not a best response when Miner 1’s power is at least 0.455.Finite-depth optimal strategies produce upper bounds converging relatively quickly to 0.418.
4 The Strategic-Release Game
The strategic-release game lets miners choose both which blocks to mine and when to release them, while other miners observe announcements but can mine only released blocks. The analysis shows Frontier is a Nash equilibrium when each miner’s computational power is at most 0.308, with strategic withholding justified when a miner is sufficiently far ahead.
- Game model: The strategic-release game allows miners to choose mining targets and withhold blocks after announcing that they mined them.Other miners can mine only blocks declared released, so the game retains complete information while restricting available mining choices.
- Game model: The state tracks the two branches’ lengths and which blocks Miner 1 has released; without loss of generality, released blocks equal min{a, b}.The state is represented by a, ar, and b, with ar normalized to min{a, b} because the honest miner capitulates once Miner 1 releases more than b blocks.
- Optimal response: Miner 1’s choices are to capitulate or mine when a ≤ b, and additionally to release blocks when a > b.The finite-horizon recurrence takes the maximum over capitulation and mining, with release represented by the first term max_{s=0,...,b−1} ˆgk(0, s).
- Optimal response: The potential recurrence maximizes among mining, releasing, and capitulating, with ˆϕ(a, 0) = −∞ when a < 0 and ˆϕ(0, 0) = 0.The potential measures Miner 1’s state-dependent advantage, while ˆg* is the expected gain per level in the long run.
- Equilibrium result: Frontier is a Nash equilibrium in the strategic-release model when every miner has relative computational power p_i ≤ 0.308.The proof shows the optimal gain per step cannot exceed p, making Frontier a best response against other miners using Frontier.
- Equilibrium result: When a miner is one block ahead, withholding risks a stale branch; when at least two blocks ahead, withholding is safe until the opponent catches up within one block.These state-dependent incentives motivate the piecewise potential used in the equilibrium proof.
- Equilibrium result: 0.308 is the threshold established by Lemma 7: the strategic-release potential satisfies its recurrence when p ≤ 0.308, the root of p3 −6p2 + 5p −1.The proof verifies the recurrence separately across states where the miner is behind, ahead by more than one block, or exactly one block ahead.