Safety and Liveness Failure Under Budget-Constrained Mining: Composing Backbone Proofs with Endogenous Honest Majority

Abstract

We prove that Nakamoto proof-of-work consensus has a budget-determined population structure with three security regimes. We compose three layers: the imported Garay-Kiayias-Leonardos (GKL) sufficiency theorem [3]; new attack constructions, native to the GKL round model, showing that when adversarial hashrate weakly exceeds honest hashrate the private-chain attack violates Persistence with probability one and a censorship attack violates Liveness; and an economic model of $n$ heterogeneous miners under an operational-security threshold that determines the honest/adversarial partition endogenously. The composition yields a safe region where GKL guarantees apply, a margin region where they fail although honest miners retain a hashrate majority, and a majority-loss region where the certainty-style attacks apply. The block-rate side of the GKL condition is derived from difficulty adjustment, not assumed. Extensions cover probabilistic compromise, mining-pool aggregation with both safety-positive and safety-negative effects, a conditional adaptive-corruption upper bound (when adaptive reach contains the budget-determined static compromised set), and post-halving entry-exit dynamics.