arXiv CSopen access

Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining

arXiv:2607.24415v1 [cs.CR] 27 Jul 2026

Near-Tight Theoretical Bounds for Incentive Compatibility in Bitcoin Mining Akira Sakurai

Taishi Nakai

Kazuyuki Shudo

Kyoto University Email: [email protected]

Kyoto University Email: [email protected]

Kyoto University Email: [email protected]

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 neartight 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 × 10−4 .

1. Introduction When is honest Bitcoin mining rational? This is one of the most fundamental questions in blockchain protocol design. Bitcoin [1] is permissionless and has no central administrator, which gives it strong censorship resistance. At the same time, because the system is maintained by selfinterested participants, it is crucial to design incentives that align individual behavior with the interests of the system as a whole. Sapirshtein et al. used a Markov Decision Process analysis to derive near-tight lower and upper bounds on the incentive-compatibility threshold [2]. Their reported bounds rely on a numerical MDP solver satisfying a prescribed accuracy guarantee. Kiayias et al.’s Blockchain Mining Games takes a complementary theoretical approach and derives provable lower and upper bounds on the threshold [3]. However, two challenges remain: •

•

Model realism. Their bounds are established in an idealized model that restricts miners to a simplified action space and assumes that, when a blockchain tie occurs, all honest miners mine on the honest branch. Tightness. Their theoretical lower and upper bounds for the incentive-compatibility threshold are 0.308 and 0.455, respectively, leaving an interval of width 0.147.

We make two contributions. •

•

REAL mining model. We allow miners to take broader actions and introduce two asymmetric tiebreaking parameters, γ − and γ + . Here, γ − denotes the fraction of honest miners who mine on the deviating miner’s branch when the deviating miner catches up, while γ + denotes the corresponding fraction when the honest chain catches up with the deviating miner. Theoretical threshold characterization. We give independent algorithms for computing a lower bound and an upper bound, respectively, on the incentivecompatibility threshold. Exact rational evaluation of both algorithms over all 1,000,000 pairs in {0, 0.001, . . . , 0.999}2 gives a maximum pointwise gap of 2.415 × 10−7 . We also prove that the threshold is coordinatewise nonincreasing in (γ − , γ + ). Coordinatewise monotonicity then gives a certified interval of width at most 9.98006 × 10−4 for every parameter pair in [0, 1]2 .

2. Model and Our Goal 2.1. REAL Model The REAL model is an n-miner game with strategic core components and Frontier components. 2.1.1. Miners. Let M = {m1 , . . . , mn }

be the fixed set of miners. Each miner mi ∈ M has total economic hash-power share αi > 0,

n X

αi = 1.

i=1

A miner is the unit of reward ownership and utility accounting. Its hash power is split between the core component and the Frontier component defined below.

2.1.2. Blocks. The unique block that references no parent block is called the genesis block. Every other block references exactly one parent block. Each block carries a source-component label and a reward-owner label. The source-component label records the operational source of the block: it is ci for a block generated by core component ci , and Frontier for a block generated by a Frontier component. The reward-owner label records the miner mi that owns the generating component and to whom the block reward is credited. The source-component label is visible only within the component that generated the block. The reward-owner label is visible only within the miner that owns the block. 2.1.3. Core Component. The REAL model has exactly two operational components for each miner: a core component and a Frontier component. The core component is the only strategic component. It maintains a core-local state and follows a core policy; its operational hash share is assigned by the miner’s REAL strategy, defined below. Core states are managed independently. A core component does not obtain another component’s private tree, unreleased blocks, or mining targets, even when the two components have the same reward owner. Core state. The state of core component ci is the triple x = (T pub , Tci , σci ) ∈ X , where Tci is the core-local tree. It contains the public tree and all unreleased blocks known privately to ci , so T

pub

⊆ Tci .

pub

The public block tree T is global. The tie-origin coordinate satisfies σci ∈ {⊥, −, +}. Initially, σci = ⊥, meaning that no origin has yet been set. Whenever the maximum public height increases, ci compares it with the height of its highest private block, taking the genesis height if no such block exists. It sets σci = + if the private height is at least the new public height, and σci = − otherwise. A private-block discovery alone does not change the label. Actions. At any state x, a core component selects exactly one action. An action is either a release action mine or a mining action. Let Arel (x) denote the ci (x) and Aci corresponding feasible action sets, and define ˙ mine (x). Aci (x) = Arel ci (x) ∪ Aci

A release action ρ ∈ Arel ci (x) specifies a finite, possibly empty, set of currently unreleased blocks in Tci to be published. The published blocks are added to T pub in the state of every component. The release must be ancestryclosed: if a block is released, then all of its unreleased ancestors are released by the same action. The action that publishes the empty set is denoted NoRelease; it leaves the state unchanged but is recorded in the history. A release action is applied instantaneously and no proofof-work discovery occurs while it is applied. Release actions selected at the same state are applied simultaneously, after

which policies are evaluated again. This continues until every core component selects a mining action. Between a state-changing mining event and the next mining action, each core component may select NoRelease only finitely many times. Since each nonempty release action publishes at least one previously unreleased block and no block is generated during this phase, this restriction ensures that the release phase terminates after finitely many steps. A mining action of core component ci at state x is either a target-mining action or the action NoMining. A target-mining action selects a single target z ∈ Fci (x), where Fci (x) is the feasible mining-target set defined by the mining-anchor restriction below. A target-mining action remains in force until the core state changes. The action NoMining has no mining target. If the next mining opportunity belongs to ci , no block is generated, the state is unchanged, and the core policy selects another action. Otherwise, NoMining remains in force until another component discovers a block and changes the state. When a component c discovers a block, the block is appended to its mining target and is initially added as an unreleased block to its component-local tree Tc . The discovered block updates the state, and policies are then evaluated at the successor state before the next mining event. Mining anchor. For a state x, let Pmax (x) be the set of public branches of maximum length. Define Ppub (x) = lcp{P : P ∈ Pmax (x)}.

Thus, if the public longest branch is unique, Ppub (x) is that branch; if a public tie is present, Ppub (x) is the common branch shared by the tied public longest branches. For a core component ci , let Vci (x) be the set of blocks in Tci whose source component is ci . For each v ∈ Vci (x), let path(v) be the unique path from the genesis block to v . If Vci (x) is nonempty, the mining anchor is ! n o
aci (x) = tip max lcp Ppub (x), path(v) : v ∈ Vci (x) . ⪯

If Vci (x) is empty, ci has not yet generated a block and aci (x) is defined as the genesis block. The feasible mining-target set of core component ci is Fci (x) = {z ∈ Tci : aci (x) ⪯ z},

where u ⪯ v means that u is an ancestor of v . The mininganchor restriction applies only to mining actions of core components. It does not restrict release actions or Frontier components. History. For a root state x⋆ ∈ X , a finite core history is a sequence h = (x0 , u0 , x1 , . . . , ut−1 , xt )

with x0 = x⋆ , us ∈ Aci (xs ), and xs+1 a possible successor of xs under us for every s < t. Let Hci (x⋆ ) be the set of these histories and write cur(h) = xt .

Policy. A core policy from x⋆ assigns each history a feasible action: [ πic : Hci (x⋆ ) −→ Aci (x), x∈X

πic (h) ∈ Aci (cur(h))

for every h ∈ Hci (x⋆ ).

Two histories ending in the same state may prescribe different actions. 2.1.4. Frontier Component. A Frontier component is an honest component that executes the protocol using the hash power assigned to it by its owner’s strategy. It is operationally separate from the owner’s core component. The two components differ in their policies, the application of the mining-anchor restriction, and their tie-breaking behavior. Policy. Unlike a core component, a Frontier component follows the Frontier policy. If it holds any unreleased private block, it selects the release action that publishes all such blocks. Otherwise, it selects a mining action on a public branch of maximum length. If the public longest branch is unique, the action targets its tip; if a public tie is present, the action follows the tie-breaking rule below. A block discovered by a Frontier component has sourcecomponent label Frontier and reward-owner label equal to the owner of that component. Mining anchor. Unlike a core component, a Frontier component is not subject to the mining-anchor restriction. Tie-breaking. The REAL model has two tiebreaking parameters, γ − , γ + ∈ [0, 1].

For σ ∈ {−, +}, write ( γ−, γ = γ+, σ

σ = −, σ = +.

When a public tie occurs, the core’s recorded origin σ ∈ {−, +} determines the Frontier allocation. A fraction γ σ of Frontier hash power mines on the core-side branches, while the remaining fraction 1 − γ σ mines on the Frontierside branches. If more than two branches participate in the tie, the total Frontier hash power assigned to the coreside and Frontier-side branches remains γ σ and 1 − γ σ , respectively. Among multiple core-side branches, the coreside share mines on the branch whose tied-height block was generated first if the branches are published simultaneously; otherwise, it mines on the branch published first. Additional tied branches do not change either total.

operational hash share αi pi and executes the core policy πic . The remaining operational hash share αi (1 − pi ) is assigned to the Frontier component fi , which executes the Frontier policy. The core component and Frontier component of a miner are operationally separate and do not share state. Their only shared quantity is the final economic block reward of miner mi . The core-REAL model is the restricted model in which pi ∈ {0, 1} for every miner mi . The REAL Frontier strategy of mi , denoted ΣFi , is represented by assigning all hash share to the Frontier component, i.e., pi = 0. A miner using ΣFi is called a Frontier miner. When no ambiguity arises, we write Frontier for this REAL strategy. 2.1.6. Execution. The initial state consists only of the genesis block. The genesis block belongs to no miner and is not counted as any miner’s block. An execution is a realized sequence of mining-event outcomes defined independently of the REAL strategy profile. It records the component selected at each event. A selected component using a target-mining action creates a block; a selected core using NoMining instead makes another policy decision without changing the state. When a public tie is present and the next block is generated by the Frontier aggregate, the execution also supplies the random draw used by the tie-breaking rule. The current tie and this draw determine which tied branch the Frontier block extends. Thus the strategy profile together with the execution determines the realized block tree and the utilities. 2.1.7. Utility. The common trunk is the path from the root on which the network has reached agreement. A path is agreed if, from that point onward, the actions prescribed by every miner’s strategy leave it unchanged under every possible continuation of the execution. For transition t, let Ri,t denote the reward credited to miner mi for blocks newly included in the common trunk by that transition, as determined by reward-owner labels, and let Lt denote the public-frontier advancement. After n transitions, define Ri,n :=

n−1 X

Ri,t ,

Ln :=

t=0

n−1 X

Lt .

t=0

The long-run utility of miner mi is 2.1.5. REAL Strategies and the Frontier Strategy. A REAL strategy of miner mi specifies both the core policy πic executed by ci and how mi splits its economic hash power between its core component ci and Frontier component fi . Formally, a REAL strategy is Σi = (pi , πic ),

0 ≤ pi ≤ 1.

Here pi is the fraction of miner mi ’s hash power assigned to the core component. Thus the core component ci has

Ui = lim inf n→∞

E[Ri,n ] . E[Ln ]

Thus the denominator measures cumulative public-frontier advancement, not advancement of the common trunk or the mining anchor. Regardless of whether a split is used, rewards and utility are determined by the reward-owner labels.

2.2. IDEAL Model The IDEAL model restricts the tested core of hash share p to the canonical actions defined below, while aggregating all remaining hash power into Frontier. It retains the REAL state, tie-breaking rule, and utility accounting. We use it both for the certificate LP and as the target of the canonicalization argument in Section 4. 2.2.1. Canonical Actions. The IDEAL model restricts the deviating core component to the following canonical action families: Wait, Hedge, NoMining, TieWait, NoRelease, Override, Match, TieOverride. No other action or private-forest operation is available in the IDEAL model. Wait. At a non-public-tie state, Wait is the canonical mining action that mines on the deviating core’s highest block outside the public longest branch. Hedge. At a non-public-tie state, Hedge is the canonical mining action that mines on a public block such that, upon success, the newly generated block has greater height than the block generated by a successful Wait action from the same state. If no Wait target exists, Hedge may mine on any public block. NoMining. At any state, NoMining is the canonical mining action with no mining target. With probability p, the state remains unchanged and the deviating core selects its next action. With probability q = 1 − p, the core performs no mining and waits until the state changes. NoRelease. At any state, NoRelease is the canonical release action that publishes no blocks. It leaves the state unchanged, after which the core selects its next action. As in the REAL model, only finitely many consecutive selections of NoRelease are allowed between a state-changing mining event and the next mining action. Override. At a non-public-tie state, Override is the release action that publishes exactly enough blocks to make the core-side branch strictly longer than the Frontier-side branch, which is the public longest branch. All other private blocks remain unpublished. Match. At a non-public-tie state, Match is the release action that publishes exactly enough private blocks to make the core-side branch as high as the Frontier-side branch. All other private blocks remain unpublished. This creates a public tie. If the core has caught up to the Frontierside branch, the tie has no hidden reserve. If the core is strictly ahead, the released prefix creates a public tie and the unreleased part remains as hidden reserve behind the core-side tied branch. Because Match does not increase the maximum public height, it does not update the tie-origin coordinate. The recorded value σci ∈ {−, +} is carried into the public tie and determines the parameter γ σci . TieWait. At a public-tie state, TieWait is the canonical mining action that mines on the highest block generated by the deviating core. If the deviating core discovers the next block, the new block is withheld and the reserve length

increases by one. If the Frontier aggregate discovers the next block, the public tie is resolved according to the tie-breaking rule: for tie origin σ ∈ {−, +}, a γ σ fraction of Frontier hash power mines on the core-side tied branch, and the remaining 1 − γ σ fraction mines on the Frontier-side branch. TieOverride. At a public-tie state, TieOverride is the release action that publishes exactly enough private blocks to make the core-side branch strictly longer than the Frontierside branch. All other private blocks remain unpublished.

2.3. Our Goal For fixed γ − , γ + ∈ [0, 1], our goal is to identify the incentive-compatibility threshold of the REAL model. For a hash-share bound c ∈ [0, 1), the REAL model is incentivecompatible at c if the Frontier profile is a Nash equilibrium in every REAL instance satisfying αi ≤ c for every miner. Let I REAL (γ − , γ + ) denote the set of incentive-compatible hash-share bounds. The set I REAL (γ − , γ + ) contains 0 and is prefix-closed. We define the REAL incentive-compatibility threshold by α∗ (γ − , γ + ) := sup I REAL (γ − , γ + )

The REAL model is incentive-compatible at every c < α∗ and is not incentive-compatible at every c > α∗ ; the endpoint may or may not be incentive-compatible. We provide algorithms for computing provable lower and upper bounds on α∗ and show that these bounds are near-tight.

3. Certificate LP in the IDEAL Model We construct a certificate LP whose feasibility certifies incentive compatibility in the IDEAL model. To prove incentive compatibility in the IDEAL model, we use a one-deviation argument. Fix an arbitrary miner mi , fix all other miners to the Frontier strategy, and analyze the best unilateral deviation of mi in the IDEAL model. Throughout this section, all miners in M \ {mi } follow the Frontier strategy and are aggregated into a single Frontier aggregate. Let p be miner mi ’s hash share in the IDEAL model, and let q = 1 − p.

We assume p < 1/2.

3.1. Reduction to the IDEAL One-Deviation Game Every reachable IDEAL one-deviation state is represented in the following canonical state space: Xb = {(0, 0)} ∪ {(a, 0) : a ≥ 1} ∪ {(a, b) : 0 ≤ a < b} ∪ {(a, b)σ : a > b ≥ 1, σ ∈ {−, +}} ∪ {Dbσ : b ≥ 1, σ ∈ {−, +}} σ ∪ {Eb,r : b ≥ 1, r ≥ 0, σ ∈ {−, +}}.

The first coordinate a is the residual height of the active core-side branch above the mining anchor, and the second coordinate b is the residual height of the Frontier-side branch. The state (a, 0) has no positive Frontier-side suffix. A state (a, b) with 0 ≤ a < b is a strict catch-up state; its tie-origin label is necessarily minus and is therefore omitted. A state (a, b)σ with a > b ≥ 1 is a strict lead state whose current tie-origin label is σ . The state Dbσ is a private diagonal state of height b with tie-origin label σ . It is not a public tie: it records private equality, possibly before the core-side branch is released. Private block generation does not change σ . Whenever the maximum public height increases, the successor label is plus if the private height is at least the new public height and minus otherwise, as specified in Section 2.1. σ Public tie states are denoted by Eb,r for σ ∈ {−, +}. Here b is the length of the tied public branches, σ is the tieorigin label carried into the tie, and r is the hidden reserve length behind the core-side tied public branch. In each canonical state, the active branch is the unique core-side branch that extends, and hence does not conflict with, the current mining anchor. Every other core-side branch is non-active. The definition of a canonical state requires every nonactive core-side branch to have height strictly below the current mining anchor. Lemma 1. Every reachable IDEAL one-deviation state has a unique representation as an element of Xb. In this representation, core-side suffixes and reserves consist only of mi blocks, while Frontier-side suffixes consist only of Frontieraggregate blocks. Proof. We induct on the number of primitive transitions. The initial state is (0, 0), so the claim is immediate. Assume that the current state has a canonical representation with branch separation. We check its state type and the feasible canonical actions. At every state, NoRelease leaves the state unchanged and therefore preserves both the canonical representation and branch separation. It remains to check the other canonical actions. Initial and strict catch-up states. At (0, 0), Hedge(0) leads to (1, 0) after an mi -success and to (0, 1) after a Frontier success. Under NoMining, the state remains (0, 0) and the core selects another action with probability p; with probability q , it waits until a Frontier success gives (0, 1). At a strict catch-up state (a, b) with 1 ≤ a < b, a feasible Wait gives  −  mi -success and a + 1 = b, Db , (a, b) −→ (a + 1, b), mi -success and a + 1 < b,  (a, b + 1), Frontier success. At every strict catch-up state, including (0, b), a feasible

Hedge(d) gives

  (1, 0), mi -success and d = 0,   −  D1 , mi -success and d = 1, (a, b) −→  (1, d), mi -success and d ≥ 2,   (a, b + 1), Frontier success. On an mi -success, the new core-side suffix is the single new mi -block and the length-d Frontier-side suffix contains only Frontier-aggregate blocks. If an old core-side branch exists, it becomes non-active and, by Hedge feasibility, lies strictly below the successor mining anchor, as required by the canonical-state definition. On a Frontier success, only the Frontier-side suffix grows. Under NoMining, the state remains (a, b) and the core selects another action with probability p. With probability q , it waits until a state change gives (a, b + 1). Lead states. At (a, 0) with a ≥ 1, Wait gives (a + 1, 0) after an mi -success. A Frontier success gives D1+ if a = 1 and (a, 1)+ if a > 1. Under NoMining, the state remains (a, 0) on its probability-p branch and has the same statechanging successor as Wait on its probability-q branch. At a signed lead state (a, b)σ with a > b ≥ 1, Wait gives (a + 1, b)σ after an mi -success. A Frontier success + gives Db+1 if a = b + 1 and (a, b + 1)+ if a > b + 1. Under NoMining, the state remains (a, b)σ on its probabilityp branch and has the same state-changing successor on its probability-q branch. Writing a = b + m, Override(j) from either kind of lead state leaves (m−j, 0). From (b+r, b)σ with b, r ≥ 1, Match σ creates Eb,r . These release actions preserve the all-mi coreside suffix or reserve. Private diagonal states. From Dbσ , Wait gives (b+1, b)σ after an mi -success and (b, b + 1) after a Frontier success. Under NoMining, the state remains Dbσ and the core selects another action with probability p; with probability q , it waits until a state change gives (b, b + 1). The action Match gives σ Eb,0 . These transitions preserve branch separation. σ Public tie states. From Eb,r , an mi -success under σ TieWait gives Eb,r+1 . A Frontier success on the Frontierside branch gives   r = 0, (b, b + 1), + Db+1 , r = 1,  (b + r, b + 1)+ , r ≥ 2, while a Frontier success on the core-side tied branch gives   r = 0, (0, 1), + D1 , r = 1,  (r, 1)+ , r ≥ 2. σ Under NoMining, the state remains Eb,r and the core selects another action with probability p. With probability q , it waits until a state change gives the two outcomes above, with conditional probabilities 1 − γ σ and γ σ , respectively. Under TieWait, the mi -success appends an mi -block to the reserve. In either Frontier outcome, the new block is the

only new Frontier-aggregate block on the relevant Frontierside suffix. Finally, TieOverride(j) leaves the residual state (r −j, 0). Thus every successor again has branch separation. The state classes in Xb are disjoint, and their numerical coordinates and origin labels are uniquely determined by the current canonical tree. Hence the representation is unique. b For each x ∈ Xb, let A(x) denote the canonical actions defined in Section 2.2 that are feasible at x.

3.2. Exact Centered Bellman Inequalities For each realized canonical transition from a reduced state x, under a feasible canonical action u, to a successor state x′ , let R(x, u, x′ ) denote the reward credited to mi for blocks newly included in the common trunk by that transition, as determined by their reward-owner labels, and let L(x, u, x′ )

denote the public-frontier advancement caused by that transition. The quantity L does not measure advancement of the common trunk or the mining anchor. Let V : Xb → R≥0 be a nonnegative potential normalized by

t, let Yt = cur(Ht ), and let Xt be the canonical reduced representation of Yt . Set Ut = π(Ht ). Write Rt = R(Xt , Ut , Xt+1 ),

Lt = L(Xt , Ut , Xt+1 ).

Since Ut is Ft -measurable, applying (3.1) conditionally on Ft gives E[Rt − pLt + V (Xt+1 ) | Ft ] ≤ V (Xt ).

(3.2)

Taking expectations, summing over t = 0, . . . , n − 1, and canceling the intermediate potential terms yields "n−1 # X E (Rt − pLt ) ≤ V (X0 ) − E[V (Xn )] ≤ 0, (3.3) t=0

where the last inequality uses X0 = (0, 0), V (0, 0) = 0, and V ≥ 0. Define the cumulative reward and cumulative publicfrontier advancement by Rn :=

n−1 X

Rt ,

Ln :=

t=0

n−1 X

Lt .

(3.4)

t=0

Equation (3.3) is therefore equivalent to E[Rn ] ≤ p E[Ln ]

(3.5)

for every transition depth n. Whenever E[Ln ] > 0, this is equivalently E[Rn ] ≤ p. (3.6) E[Ln ] Taking the lim inf in (3.6) gives Ui ≤ p.

V (0, 0) = 0.

For each feasible state–action pair (x, u), where x ∈ Xb and b , let X ′ be the successor state and define the exact u ∈ A(x) centered action value by BV (x, u) = E[R(x, u, X ′ ) − pL(x, u, X ′ ) + V (X ′ ) | x, u] .

The exact centered Bellman inequality is the one-step condition V (x) ≥ BV (x, u) (3.1) for every reduced state x ∈ Xb and every feasible canonical b . action u ∈ A(x) The inequality says that the potential at the current state covers the expected centered reward R − pL from the next transition together with the potential remaining at the successor state. Lemma 2. Suppose that V ≥ 0, V (0, 0) = 0, and V satisfies the exact centered Bellman inequality (3.1) for every reduced canonical state x ∈ Xb and every feasible canonical b . Then every IDEAL policy has long-run action u ∈ A(x) utility Ui ≤ p. Proof. Fix an IDEAL policy π . Let (Ft )t≥0 be the natural filtration, let Ht be the IDEAL history through transition

3.3. Conservative Action Values The action values below are conservative upper bounds on the exact centered action values defined in Section 3.2. b , For each feasible state–action pair (x, u) with u ∈ A(x) let B V (x, u) denote the corresponding conservative action value. It is chosen so that BV (x, u) ≤ B V (x, u).

Consequently, if V (x) ≥ B V (x, u)

for every reduced state and feasible canonical action, then the exact centered Bellman inequality (3.1) also holds. For a potential V , we write these conservative centered action values as follows. For σ ∈ {−, +}, set ( γ − , σ = −, σ γ = γ + , σ = +. For origin-sensitive lead and equality successors, write   V (Dbσ ), a = b ≥ 1,    σ V ((a, b) ), a > b ≥ 1, V σ (a, b) =  V (0, 0), a = b = 0,   V (a, b), otherwise.

Thus the superscript records the tie origin of a signed lead or private diagonal state; it never denotes a public tie. Wait. At a strict catch-up state (a, b) with 1 ≤ a < b, Wait has conservative centered value WV (a, b) = pV − (a + 1, b) + qV (a, b + 1) − pq.

(3.7)

At a lead state with no positive Frontier-side suffix, the value is WV (a, 0) = pV (a + 1, 0) + qV + (a, 1) − pq,

a ≥ 1.

At a signed lead state (a, b)σ with a > b ≥ 1, the value is WVσ (a, b) = pV σ (a + 1, b) + qV + (a, b + 1) − pq.

In a private diagonal state Dbσ , where σ ∈ {−, +}, Wait has conservative centered value σ WD,V (b) = pV σ (b + 1, b) + qV (b, b + 1) − pq.

(3.8)

The core-success branch retains σ , whereas the Frontiersuccess branch enters the unsigned strict catch-up region. Override. Suppose the state has lead m: a = b + m,

m ≥ 1.

For b = 0 the state is (a, 0); for b ≥ 1 it is (a, b)σ . For 1 ≤ j ≤ m, Override(j) releases b + j active-branch blocks, makes the core-side branch uniquely longest, and leaves residual lead m − j . Its conservative centered value is Oj,V (b + m, b) = V (m − j, 0) + b + j − p.

(3.9)

When j = m, the successor is (0, 0), so (3.9) uses V (0, 0) = 0. Match. From private diagonal states, Match creates a public tie with no immediate reward and no conservative advancement charge: σ σ TD,V (b) = V (Eb,0 ),

σ ∈ {−, +}.

(3.10)

At the initial state (0, 0), Hedge(0) is feasible, with conservative centered value H0,V (0, 0) = pV (H0 ) + qV (0, 1) − pq.

At a strict catch-up state (a, b) with 0 ≤ a < b, Hedge(d) is feasible for 0≤d≤b

if a = 0,

0≤d<b−a

if a ≥ 1.

Its conservative centered value is Hd,V (a, b) = pV (Hd ) + qV (a, b + 1) − pq.

(3.12)

In this conservative accounting, the miner-success branch receives no immediate reward or advancement charge. The Frontier-success branch extends the public branch by one and contributes the term −pq . σ TieWait. At a public tie state Eb,r , TieWait mines on mi ’s tied branch or reserve tip and withholds any newly discovered block. Its conservative centered value is σ σ WE,V (b, r) = pV (Eb,r+1 ) + γ σ q{b + V + (r, 1)}

+ (1 − γ σ )qV + (b + r, b + 1) − pq. (3.13) The value V + (r, 1) is used because, when equality occurs at (1, 1), the equality is plus-origin. Likewise, if b + r = b + 1, + then V + (b + r, b + 1) = V (Db+1 ). NoMining. At the initial state or a strict catch-up state (a, b), NoMining has conservative centered value NV (a, b) = pV (a, b) + q{V (a, b + 1) − p}.

At a lead state (a, 0), its value is NV (a, 0) = pV (a, 0) + q{V + (a, 1) − p},

a ≥ 1.

At a signed lead state (a, b)σ , its value is NVσ (a, b) = pV ((a, b)σ ) + q{V + (a, b + 1) − p}.

At a private diagonal state Dbσ , its value is σ ND,V (b) = pV (Dbσ ) + q{V (b, b + 1) − p}.

Equivalently, Match

− Db− −−−−→ Eb,0 ,

σ At a public tie state Eb,r , its conservative centered value is

Match

+ Db+ −−−−→ Eb,0 .

σ σ NE,V (b, r) = pV (Eb,r ) h σ + q γ {b + V + (r, 1)}

From a signed lead state (b + r, b)σ ,

b ≥ 1,

r ≥ 1,

Match creates a public tie carrying the current origin and leaves reserve r: σ σ TL,V (b, r) = V (Eb,r ).

(3.11)

The ensuing public-tie dynamics are handled by later transitions. Hedge. For Hedge(d), define the successful reanchoring successor   (1, 0), d = 0, Hd = D1− , d = 1,  (1, d), d ≥ 2.

i + (1 − γ σ )V + (b + r, b + 1) − p . The first term is the outcome in which the core is selected, the state remains unchanged, and the core chooses again. The bracketed term is the conditional value when the core waits until the state changes. For the core-side tie resolution, fixing b core blocks while advancing the public frontier by one contributes b − p; the competing resolution contributes −p. NoRelease. At every reduced state x, NoRelease has exact and conservative centered value B V (x, NoRelease) = V (x).

σ TieOverride. At Eb,r , the action TieOverride(j) immediately publishes j existing reserve blocks and breaks the public tie in favor of mi ’s branch. The feasible range is

1 ≤ j ≤ r.

For b > N , set V (Db− ) = D− (b) = g − b + h− ,

and V (Db+ ) = D+ (b) = g + b + h+ ,

Its conservative centered value is Qσj,V (b, r) = V (r − j, 0) + b + j − p.

(3.14)

3.4. Potential Family

− V (Eb,0 ) = Mb ,

We construct a finite-dimensional family of potentials. The parameter N controls the finite core depth, and D controls the number of explicit deficit tails. For 1 ≤ d ≤ D + 1, define Bd = max{N + 1, d + 1}.

The lower bound Bd is the smallest value of b for which a strict catch-up tail state with deficit d = b − a has both b > N and a ≥ 1. We also define K = max{2, N − D}.

The terminal coefficients w1 , . . . , wK are included as LP variables. If D ≥ N , then K = 2, and the terminal part uses only w1 , w2 explicitly. Capitulation states. For all b ≥ 0, set (3.15)

Lead states. For a ≥ b + 1, define the affine lead potential L(a, b) = λa − µb − κ, (3.16) where λ, µ, κ are LP variables. We assign this potential to the unsigned lead states with no positive Frontier-side suffix and to both origins of every signed lead state: V (a, 0) = L(a, 0)

+ V (Eb,0 ) = Pb .

− V (Eb,0 ) = E0− (b) = e− b + f − ,

(3.21a)

+ V (Eb,0 ) = E0+ (b) = e+ b + f + ,

(3.21b)

and where e− , f − , e+ , f + are LP variables. Public tie states with reserve. For every b ≥ 1, r ≥ 1, and σ ∈ {−, +}, define σ V (Eb,r ) = L(b + r, b).

(3.22)

Thus reserve-carrying public tie states introduce no additional LP variables. In particular, Match from a strict lead state σ (b + r, b)σ → Eb,r has the same potential value on both sides: σ V ((b + r, b)σ ) = L(b + r, b) = V (Eb,r ).

The Bellman inequality for this Match transition is therefore automatically satisfied as equality. Affine strict catch-up tails. Let d=b−a

be the deficit. For b > N and 1 ≤ d ≤ D, set

(a ≥ 1),

V (a, b) = Cd (b) = ud b + vd ,

and V ((a, b)σ ) = L(a, b)

(3.20)

For b > N , set

D ≥ 1.

V (0, b) = 0.

(3.19b)

where g − , h− , g + , h+ are LP variables. Public tie states with no reserve. For 1 ≤ b ≤ N , introduce LP variables only for reserve-zero public tie states:

Fix integers N ≥ 1,

(3.19a)

(a > b ≥ 1, σ ∈ {−, +}).

Thus the signed lead states add no LP variables. Finite strict catch-up core. For 1 ≤ a < b ≤ N,

(3.23)

where ud , vd are LP variables. Terminal superharmonic tail. For b > N and d > D, write d = D + k. For 1 ≤ k ≤ K , set

set V (a, b) = Sa,b ,

(3.17)

where each Sa,b is an LP variable. Private diagonal states. For 1 ≤ b ≤ N , introduce LP variables V (Db− ) = Db− ,

V (Db+ ) = Db+ .

(3.18)

These are private equal decision states, not public tie states.

V (a, b) = awk .

(3.24)

For k > K , the remaining sequence wK+1 , wK+2 , . . .

is not included in the finite LP. Its existence is guaranteed later by the terminal extension lemma.

3.5. Shorthand for Boundary Values We use the following shorthand in the LP constraints. For private diagonal states, define ( Dbσ , 1 ≤ b ≤ N, σ D (b) = σ ∈ {−, +}. σ σ g b + h , b > N, (3.25) Here (g σ , hσ ) means (g − , h− ) for σ = − and (g + , h+ ) for σ = +. For reserve-zero public tie states, define ( Mb , 1 ≤ b ≤ N, − E0 (b) = (3.26a) − − e b + f , b > N,

ensures that every terminal value appearing in the finite-core boundary constraints is represented among w1 , . . . , wK . Values with terminal index larger than K are handled by the terminal extension lemma rather than by additional LP variables.

3.6. Certificate LP Constraints

(3.26b)

For all public tie states, including reserve-carrying ones, define ( E0σ (b), r = 0, E σ (b, r) = (3.27) L(b + r, b), r ≥ 1. For unsigned states and the common potential of signed lead states appearing in finite constraints, define  0, a = 0,      L(a, b), a ≥ b + 1,  V(a, b) = Sa,b , 1 ≤ a < b ≤ N,    C (b), b > N, 1 ≤ b − a ≤ D, b−a    awb−a−D , b > N, D < b − a ≤ D + K. (3.28) For a > b ≥ 1, V(a, b) = L(a, b) is the common value assigned to both (a, b)− and (a, b)+ . When a = b > 0, the appropriate value is the private diagonal value D− (b) or D+ (b). For origin-sensitive successor values, define   a = b = 0, 0, σ σ V (a, b) = D (b), a = b ≥ 1, σ ∈ {−, +}.  V(a, b), otherwise, (3.29) Thus V σ (a, b) selects the origin-specific diagonal value when a = b and the common signed-lead potential when a > b ≥ 1. The value of a successful Hedge successor is abbreviated by   V(1, 0), d = 0, Hd = D− (1), d = 1, (3.30)  V(1, d), d ≥ 2. Here V(1, 0) = L(1, 0). Finally, define Xb = V(b, b + 1).

K = max{2, N − D}

For fixed p, γ − , γ + , all constraints below are linear. The certificate LP is denoted by

and ( Pb , 1 ≤ b ≤ N, + E0 (b) = e+ b + f + , b > N.

Thus Xb is the strict catch-up value reached when the Frontier aggregate extends a private diagonal state of length b, or when the Frontier side wins a public tie of length b with no remaining hidden reserve. The choice

LN,D (p, γ − , γ + ).

As before, let q = 1 − p.

Whenever an affine slack ∆(b) is required to be nonnegative for all b ≥ b0 , we impose the two linear constraints slopeb ∆(b) ≥ 0,

∆(b0 ) ≥ 0.

The same convention is used for affine scaling slacks. The LP contains Bellman inequalities and, for several constraint families, additional prefix-scaling constraints. For an inequality slack ∆ with auxiliary slack Γ, the corresponding scaling slack is Ξ = ∆ + pΓ ≥ 0.

This prefix-scaling constraint is stronger than what is needed for soundness at a fixed p, but it is useful for the prefixmonotonicity argument. C0: Nonnegativity and terminal bounds. For all finite strict catch-up states, Sa,b ≥ 0

(1 ≤ a < b ≤ N ).

(C0.1)

For all finite private diagonal states, Db− ≥ 0,

Db+ ≥ 0

(1 ≤ b ≤ N ).

(C0.2)

For all finite reserve-zero public tie states, Mb ≥ 0,

Pb ≥ 0

(1 ≤ b ≤ N ).

(C0.3)

For every affine strict catch-up tail 1 ≤ d ≤ D, ud ≥ 0,

(C0.4)

ud Bd + vd ≥ 0.

(C0.5)

and For the private diagonal tails, g − ≥ 0,

g − (N + 1) + h− ≥ 0,

(C0.6)

g + ≥ 0,

g + (N + 1) + h+ ≥ 0.

(C0.7)

and (3.31)

For the reserve-zero public tie tails,

Impose

e− ≥ 0,

e− (N + 1) + f − ≥ 0,

+

+

(C0.8)

slopeb ∆W d (b) ≥ 0,

(C2.3)

∆W d (Bd ) ≥ 0.

(C2.4)

and

and e ≥ 0,

e (N + 1) + f

+

≥ 0.

(C0.9)

For the terminal coefficients, 0 ≤ wk ≤ q

(1 ≤ k ≤ K).

(C0.10)

For Hedge monotonicity in the terminal region, impose wk ≥ wk+1

(1 ≤ k < K).

(C0.11)

C1: Lead constraints. The lead coefficients satisfy (C1.1)

λ ≥ 1,

(C1.2)

µ ≥ 0,

(C1.3)

λ − µ ≥ 1,

(C1.4)

qµ − pλ + pq ≥ 0.

(C1.5)

and These constraints imply nonnegativity of the lead potential for (a, 0) and for both signed states (a, b)σ with a > b ≥ 1. They also imply all Override inequalities from these lead states, all Match inequalities from signed lead states, all TieOverride inequalities from reserve-carrying public tie states, and the TieWait inequalities at reserve r ≥ 2. C2: Strict catch-up Wait constraints. First consider the finite strict catch-up core. For every

define Za,b = V(a, b + 1).

(C3.2)

Here an mi -success from Dbσ reaches (b + 1, b)σ , whose potential is L(b + 1, b) for either origin; a state-changing Frontier discovery reaches the unsigned catch-up state (b, b+ 1). The associated prefix-scaling constraint is Dbσ ≥ Xb

(C3.3)

and Db+ ≥ Pb .

(C3.5)

These encode Match

− Db− −−−−→ Eb,0 ,

Match

+ Db+ −−−−→ Eb,0 .

For the private diagonal Wait tails b ≥ N + 1 and σ ∈ {−, +}, define

∆σD,W (N + 1) ≥ 0.

(C3.8)

The corresponding tail scaling slack is

and otherwise Ya,b = V(a + 1, b). Impose the Bellman inequality Sa,b ≥ pYa,b + qZa,b − pq,

(C2.1)

For affine strict catch-up tails, let 1 ≤ d ≤ D and b ≥ Bd . Define ( D− (b), d = 1, Yd (b) = Cd−1 (b), 2 ≤ d ≤ D, Cd+1 (b + 1), (b − D)w1 ,

(1 ≤ b ≤ N, σ ∈ {−, +}).

For every 1 ≤ b ≤ N , impose the private diagonal Match constraints Db− ≥ Mb , (C3.4)

Ya,b = D− (b),

Zd (b) =

Db+ ≥ pL(b + 1, b) + qXb − pq.

and

Equivalently, if a + 1 = b, then

(

(C3.1)

∆σD,W (b) = Dσ (b) − {pL(b + 1, b) + qC1 (b + 1) − pq}. (C3.6) Impose slopeb ∆σD,W (b) ≥ 0, (C3.7)

1 ≤ a < b ≤ N,

and

Db− ≥ pL(b + 1, b) + qXb − pq,

and

λ − κ = q,

Ya,b = V − (a + 1, b),

The boundary successor for d = 1 is the minus-origin private diagonal value D− (b), not a public tie value. C3: Private diagonal constraints. For every 1 ≤ b ≤ N , impose the private diagonal Wait constraints

1 ≤ d < D, d = D.

(C3.9)

slopeb ΞσD,W (b) ≥ 0,

(C3.10)

ΞσD,W (N + 1) ≥ 0.

(C3.11)

Impose and For the private diagonal Match tails, define − − ∆− D,M (b) = D (b) − E0 (b),

(C3.12)

+ + ∆+ D,M (b) = D (b) − E0 (b).

(C3.13)

and Impose

The affine Wait slack is ∆W d (b) = Cd (b) − {pYd (b) + qZd (b) − pq}.

ΞσD,W (b) = Dσ (b) − C1 (b + 1).

(C2.2)

slopeb ∆− D,M (b) ≥ 0,

slopeb ∆+ D,M (b) ≥ 0, (C3.14)

and

and

∆− D,M (N + 1) ≥ 0,

∆+ D,M (N + 1) ≥ 0.

C4: Public tie constraints. Public tie states are decision states. The LP explicitly imposes TieWait constraints for reserve r = 0 and reserve r = 1. The reserve r ≥ 2 TieWait constraints follow from C1, and TieOverride constraints are implied by C1. NoMining requires no additional constraints: its inequalities follow from the existing C1, C3, C4, and C7 constraints. σ First consider reserve-zero public tie states Eb,0 . For every 1 ≤ b ≤ N and σ ∈ {−, +}, impose E0σ (b) ≥ pL(b + 1, b) + γ σ qb + (1 − γ σ )qXb − pq.

(C4.1)

The associated prefix-scaling constraint is E0σ (b) ≥ γ σ qb + (1 − γ σ )Xb .

∆σE1,W (N + 1) ≥ 0.

(C3.15)

The corresponding tail scaling slack is ΞσE1,W (b) = L(b + 1, b)

n o − γ σ qb + γ σ D+ (1) + (1 − γ σ )D+ (b + 1) . (C4.14) Impose (C4.15)

ΞσE1,W (N + 1) ≥ 0.

(C4.16)

C5: Hedge-success upper constraints. The successful Hedge successor Hd must satisfy V (Hd ) ≤ q.

(C5)

The case d = 0 is

∆σE0,W (b) = E0σ (b)

n

slopeb ΞσE1,W (b) ≥ 0,

and

(C4.2)

For the reserve-zero public tie tails b ≥ N + 1, define

(C4.13)

V (H0 ) = V (1, 0) = L(1, 0) = q, σ

− pL(b + 1, b) + γ qb

(C4.3)

which follows from C1.1. For d = 1, impose

o + (1 − γ σ )qC1 (b + 1) − pq .

D1− ≤ q.

(C5.1)

(C5.2)

For 2 ≤ b ≤ N , impose

Impose slopeb ∆σE0,W (b) ≥ 0,

(C4.4)

S1,b ≤ q.

∆σE0,W (N + 1) ≥ 0.

(C4.5)

For affine-tail Hedge successors, equivalently states (1, d + 1) with d + 1 > N and 1 ≤ d ≤ D, impose

and The corresponding tail scaling slack is

Cd (d + 1) ≤ q.

ΞσE0,W (b) = E0σ (b) − γ σ qb − (1 − γ σ )C1 (b + 1). (C4.6)

Impose slopeb ΞσE0,W (b) ≥ 0,

(C4.7)

ΞσE0,W (N + 1) ≥ 0.

(C4.8)

and σ Next consider reserve-one public tie states Eb,1 . Since σ V (Eb,1 ) = L(b + 1, b),

For terminal Hedge successors, no additional constraint is needed because C0.10 gives wk ≤ q . C6: Hedge monotonicity constraints. By C5, for every feasible Hedge(d), pV (Hd ) + qV (a, b + 1) − pq ≤ qV (a, b + 1).

Since V ≥ 0, it is enough to impose the stronger monotonicity condition V (a, b) ≥ V (a, b + 1)

TieWait gives, for every 1 ≤ b ≤ N and σ ∈ {−, +}, L(b + 1, b) ≥ pL(b + 2, b) + γ σ q{b + D+ (1)} + (1 − γ σ )qD+ (b + 1) − pq.

(C4.9)

The associated prefix-scaling constraint is L(b+1, b) ≥ γ σ qb+γ σ D+ (1)+(1−γ σ )D+ (b+1). (C4.10)

For the reserve-one public tie tails b ≥ N + 1, define ∆σE1,W (b) = L(b + 1, b) n − pL(b + 2, b) + γ σ q{b + D+ (1)} o + (1 − γ σ )qD+ (b + 1) − pq . (C4.11) Impose slopeb ∆σE1,W (b) ≥ 0, (C4.12)

(C5.3)

throughout the strict catch-up region. For every finite strict catch-up state 1 ≤ a < b ≤ N , impose Sa,b ≥ V(a, b + 1). (C6.1) For affine strict catch-up tails, let 1 ≤ d ≤ D and b ≥ Bd . Define ( Cd+1 (b + 1), 1 ≤ d < D, H Zd (b) = (b − D)w1 , d = D. The affine Hedge-monotonicity slack is H ∆H d (b) = Cd (b) − Zd (b).

(C6.2)

slopeb ∆H d (b) ≥ 0,

(C6.3)

Impose

and ∆H d (Bd ) ≥ 0.

In the terminal region, Hedge monotonicity is guaranteed by C0.11 and Lemma 3. C7: One-block lead Wait constraints. The lead-state Wait constraints with lead at least two are implied by C1. The remaining cases are (1, 0) and, for b ≥ 1, the two signed one-block lead states σ

(b + 1, b) ,

σ ∈ {−, +}.

For every 0 ≤ b ≤ N , impose L(b + 1, b) ≥ pL(b + 2, b) + qD+ (b + 1) − pq.

(C7.1)

+ Here a state-changing Frontier discovery reaches Db+1 from σ

(1, 0) when b = 0 and from either (b + 1, b) when b ≥ 1. The constraint is independent of the incoming sign because both signed lead states have potential L(b + 1, b). The associated prefix-scaling constraint is L(b + 1, b) ≥ D+ (b + 1)

(0 ≤ b ≤ N ).

Finally, impose the terminal extension lower condition p (C8.5) wK ≥ wK−1 . q

(C6.4)

Together with C0.10 and C0.11, this condition permits an infinite terminal extension satisfying the required superharmonicity and monotonicity constraints.

3.7. Terminal Extension Lemma 3. Let p < 1/2, q = 1 − p, and p ρ= . q Suppose wK−1 , wK satisfy 0 ≤ wK−1 ≤ q,

0 ≤ wK ≤ q,

wK−1 ≥ wK ,

wK ≥ ρwK−1 .

Then there exists an infinite sequence

(C7.2)

For the one-block lead tail b ≥ N + 1, define ∆1,W (b) = L(b + 1, b) − {pL(b + 2, b) + qD+ (b + 1) − pq}. (C7.3) Impose slopeb ∆1,W (b) ≥ 0, (C7.4)

wK+1 , wK+2 , . . .

such that, for every k ≥ K , 0 ≤ wk ≤ q, wk ≥ wk+1 ,

and

and ∆1,W (N + 1) ≥ 0.

Proof. Re-index the prescribed pair as

The corresponding scaling slack is Ξ1,W (b) = L(b + 1, b) − D+ (b + 1).

wk − pwk−1 − qwk+1 ≥ 0.

(C7.5)

z1 = wK−1 ,

(C7.6)

z2 = wK .

We construct an infinite sequence

Impose slopeb Ξ1,W (b) ≥ 0,

(C7.7)

Ξ1,W (N + 1) ≥ 0.

(C7.8)

z1 , z2 , z3 , . . .

and then set

and C8: Terminal strict catch-up constraints. At deficit d = D + 1, write

wK+ℓ−1 = zℓ+1

Define A=

a = b − (D + 1).

The terminal boundary Wait slack is ∆bd (b) = aw1 − {pCD (b) + qaw2 − pq}.

(C8.1)

and (C8.3)

For the explicit terminal prefix, impose wk − pwk−1 − qwk+1 ≥ 0

If K = 2, this family is empty.

z2 − ρz1 , 1−ρ

B=

z1 − z2 , 1−ρ

and set

It must hold for every b ≥ BD+1 . Since it is affine in b, impose slopeb ∆bd (b) ≥ 0, (C8.2) ∆bd (BD+1 ) ≥ 0.

(ℓ ≥ 1).

(2 ≤ k ≤ K − 1). (C8.4)

zℓ = A + Bρℓ−1

(ℓ ≥ 1).

Since z2 ≥ ρz1 , we have A ≥ 0. Since z1 ≥ z2 , we have B ≥ 0. The definition gives the prescribed first two terms: A + B = z1 ,

A + Bρ = z2 .

Because 0 < ρ < 1 and B ≥ 0, the sequence is nonincreasing: zℓ ≥ zℓ+1

(ℓ ≥ 1).

It is also nonnegative and bounded above by z1 ≤ q , so 0 ≤ zℓ ≤ q

(ℓ ≥ 1).

Finally, for every ℓ ≥ 2,

Using (C1.1)–(C1.4), we have

zℓ − pzℓ−1 − qzℓ+1 = A(1 − p − q) + Bρℓ−2 {ρ − p − qρ2 }.

The first term is zero because p + q = 1. The second term is also zero because ρ = p/q , and hence ρ − p − qρ2 = 0.

λ ≥ 1,

λ − µ ≥ 1.

Hence the minimum over b ≥ 0 and m ≥ 1 occurs at b = 0, m = 1, where L(1, 0) = λ − κ = q ≥ 0.

Thus all lead states are nonnegative. Since reserve-carrying public tie states satisfy

Therefore zℓ − pzℓ−1 − qzℓ+1 = 0

λ − κ = q,

σ V (Eb,r ) = L(b + r, b)

(ℓ ≥ 2).

(r ≥ 1),

Translating the sequence back to the w-notation gives an infinite extension with 0 ≤ wk ≤ q, wk ≥ wk+1 , wk − pwk−1 − qwk+1 ≥ 0

they are also nonnegative. At the initial state, the only relevant public-mining transition is the canonical Hedge(0) transition. Since

for every k ≥ K . This proves the lemma.

and

V (H0 ) = V (1, 0) = L(1, 0) = q V (0, 1) = 0,

3.8. Soundness

its conservative centered value is

Theorem 1. Fix p < 1/2 and γ − , γ + ∈ [0, 1]. If LN,D (p, γ − , γ + )

is feasible, then the potential V constructed from the feasible solution satisfies the exact centered Bellman inequality for every reduced state and every feasible canonical action. Consequently, no IDEAL policy can obtain long-run utility exceeding p. Proof. Take a feasible solution of LN,D (p, γ − , γ + ).

Construct V from the potential family in Section 3.4, use the shorthand of Section 3.5, and extend the terminal sequence using Lemma 3. By Section 3.3, it suffices to verify the conservative Bellman inequalities V (x) ≥ B V (x, u)

pV (1, 0) + qV (0, 1) − pq = pq − pq = 0 = V (0, 0).

Thus the Bellman inequality holds at the initial state. 2. Wait from finite strict catch-up states. Let 1 ≤ a < b ≤ N. The Wait value is pYa,b + qZa,b − pq,

where Ya,b = V − (a + 1, b),

Za,b = V(a, b + 1).

Constraint (C2.1) states exactly Sa,b ≥ pYa,b + qZa,b − pq.

Since V (a, b) = Sa,b on the finite strict catch-up core, the Bellman inequality holds. The boundary case a + 1 = b is handled by

for every reduced state x and every feasible canonical action b . These inequalities imply the exact centered u ∈ A(x) Bellman inequality (3.1). 1. Nonnegativity and the initial state. First, V (0, 0) = 0 by construction. We also have V (x) ≥ 0 for every reduced state x. For finite strict catch-up states, finite private diagonal states, and finite reserve-zero public tie states, nonnegativity follows from (C0.1)–(C0.3). For affine strict catch-up tails it follows from (C0.4)–(C0.5). For private diagonal tails it follows from (C0.6)–(C0.7), and for reserve-zero public tie tails it follows from (C0.8)–(C0.9). For terminal tails it follows from (C0.10) and Lemma 3. It remains only to check lead states and reserve-carrying public tie states. Both are governed by the lead potential. Write a = b + m, m ≥ 1. For b = 0 the lead state is (a, 0); for b ≥ 1 it is (a, b)σ . In either case its potential is

By (C2.3)–(C2.4), this affine slack is nonnegative for every b ≥ Bd . Therefore the Wait Bellman inequality holds throughout every affine strict catch-up tail. For d = 1, the miner-success successor is the minusorigin private diagonal tail value

L(b + m, b) = b(λ − µ) + mλ − κ.

D− (b),

Ya,b = D− (b),

so a miner discovery enters the minus-origin private diagonal state Db− , not a public tie state. 3. Wait from affine strict catch-up tails. Let b > N,

1 ≤ d = b − a ≤ D,

a ≥ 1.

Then b ≥ Bd , and the Wait slack is ∆W d (b) = Cd (b) − {pYd (b) + qZd (b) − pq}.

not a public tie value. 4. Wait from terminal strict catch-up tails. Let b > N,

d = b − a > D,

d = D + k.

First consider the terminal boundary k = 1, so that a = b − (D + 1).

Since

V (Db− ) = Db− ,

V (Db+ ) = Db+ ,

the Bellman inequality holds for Wait from every finite private diagonal state. 6. Wait from private diagonal tails. Let b ≥ N + 1, σ ∈ {−, +}. The private diagonal Wait slack is

The Wait slack is ∆bd (b) = aw1 − {pCD (b) + qaw2 − pq}.

By (C8.2)–(C8.3), this affine slack is nonnegative for every b ≥ BD+1 .

Hence the Bellman inequality holds at the boundary between the explicit affine-tail region and the terminal region. Now consider k ≥ 2. In the terminal region, V (a, b) = awk .

If mi discovers the next block under Wait, then the successor is (a + 1, b) and has value (a + 1)wk−1 .

If the Frontier aggregate discovers the next block, then the successor is (a, b + 1) and has value awk+1 .

The Wait slack is therefore awk − {p(a + 1)wk−1 + qawk+1 − pq} = p(q − wk−1 ) + a{wk − pwk−1 − qwk+1 }.

The first term is nonnegative because wk−1 ≤ q , by (C0.10) and Lemma 3. The second term is nonnegative by (C8.4) when 2 ≤ k < K , and by Lemma 3 when k ≥ K . Thus the Bellman inequality holds for all terminal strict catch-up states. 5. Wait from finite private diagonal states. Let 1 ≤ b ≤ N, σ ∈ {−, +}. The mi -success from Dbσ reaches (b + 1, b)σ and retains the sign; both signed successors have potential L(b + 1, b). The Frontier-success branch reaches (b, b + 1). Hence the Wait value is pL(b + 1, b) + qXb − pq. For σ = −, constraint (C3.1) gives Db− ≥ pL(b + 1, b) + qXb − pq.

For σ = +, constraint (C3.2) gives Db+ ≥ pL(b + 1, b) + qXb − pq.

∆σD,W (b) = Dσ (b) − {pL(b + 1, b) + qC1 (b + 1) − pq}.

By (C3.7)–(C3.8), this affine slack is nonnegative for every b ≥ N +1. Thus the Bellman inequality holds for Wait from all private diagonal tail states. 7. Wait from one-block lead states. A one-block lead state is (1, 0) when b = 0 and (b + 1, b)σ when b ≥ 1. Both signed states are covered by the same constraint because their potential is L(b + 1, b). For 0 ≤ b ≤ N , constraint (C7.1) gives L(b + 1, b) ≥ pL(b + 2, b) + qD+ (b + 1) − pq.

This is exactly the Wait Bellman inequality, because a statechanging Frontier discovery reaches the plus-origin private diagonal state + Db+1 . For b ≥ N + 1, the one-block lead Wait slack is ∆1,W (b) = L(b + 1, b) − {pL(b + 2, b) + qD+ (b + 1) − pq}.

By (C7.4)–(C7.5), this affine slack is nonnegative for every b ≥ N +1. Thus the Bellman inequality holds for Wait from every one-block lead state. 8. Wait from lead states with lead at least two. Let m ≥ 2. The state is (m, 0) when b = 0 and (b + m, b)σ when b ≥ 1. An mi -success retains σ in the signed region, whereas a state-changing Frontier discovery assigns plus origin. Both successors have the same affine lead potential. Using L(a, b) = λa − µb − κ,

the Wait slack is L(b + m, b) − {pL(b + m + 1, b) + qL(b + m, b + 1) − pq} = qµ − pλ + pq. This is nonnegative by (C1.5). Therefore the Bellman inequality holds for Wait from every lead state with lead at least two. 9. Override from lead states. Let m ≥ 1. The state is (m, 0) when b = 0 and (b + m, b)σ when b ≥ 1; the calculation is independent of σ . For 1 ≤ j ≤ m, the Override value is V (m − j, 0) + b + j − p.

First suppose j < m. Then the successor (m − j, 0) is a lead state, and V (m − j, 0) = L(m − j, 0).

The Override slack is

By C5,

L(b + m, b) − {L(m − j, 0) + b + j − p} = b(λ − µ − 1) + j(λ − 1) + p.

This is nonnegative by (C1.2) and (C1.4). Now suppose j = m. Then the successor is (0, 0), and the Override slack is L(b + m, b) − (b + m − p) = b(λ − µ − 1) + m(λ − 1) + p − κ.

V (Hd ) ≤ q.

Hence pV (Hd ) + qV (a, b + 1) − pq ≤ qV (a, b + 1).

For a = 0, we have V (0, b) = V (0, b + 1) = 0,

so the Bellman inequality holds. For 1 ≤ a < b, C6 imposes

The minimum over b ≥ 0 and m ≥ 1 occurs at b = 0, m = 1, where it equals

V (a, b) ≥ V (a, b + 1)

λ−κ+p−1=q+p−1=0

through the finite-core, affine-tail, and terminal monotonicity constraints. Since V ≥ 0 and q ≤ 1,

by (C1.1). Hence every Override action from every lead state satisfies the Bellman inequality. 10. Match from private diagonal states. A Match action from a private diagonal state creates the corresponding reserve-zero public tie state and records no immediate reward or conservative advancement charge: Match

Match

− Db− −−−−→ Eb,0 ,

+ Db+ −−−−→ Eb,0 .

For 1 ≤ b ≤ N , constraints (C3.4)–(C3.5) give Db− ≥ Mb ,

Db+ ≥ Pb .

Thus the Bellman inequality holds for Match from finite private diagonal states. For b ≥ N + 1, the Match slacks are − − ∆− D,M (b) = D (b) − E0 (b),

and + + ∆+ D,M (b) = D (b) − E0 (b).

By (C3.14)–(C3.15), both affine slacks are nonnegative for every b ≥ N + 1. Hence the Bellman inequality holds for Match from all private diagonal tail states. 11. Match from strict lead states. Let the signed lead state be (b + r, b)σ ,

b ≥ 1,

r ≥ 1.

V (a, b) ≥ V (a, b + 1) ≥ qV (a, b + 1).

Thus every strict-catch-up Hedge(d) action satisfies the Bellman inequality. 13. TieWait from reserve-zero public tie states. Let σ Eb,0 , σ ∈ {−, +}. The two state-changing successors are (0, 1) and (b, b + 1), both in the unsigned strict catch-up region. For 1 ≤ b ≤ N , the TieWait Bellman inequality is precisely (C4.1): E0σ (b) ≥ pL(b + 1, b) + γ σ qb + (1 − γ σ )qXb − pq.

For b ≥ N + 1, the reserve-zero TieWait slack is ∆σE0,W (b) = E0σ (b) n − pL(b + 1, b) + γ σ qb

o + (1 − γ σ )qC1 (b + 1) − pq . By (C4.4)–(C4.5), this affine slack is nonnegative for every b ≥ N + 1. Thus the Bellman inequality holds for TieWait from all reserve-zero public tie states. 14. TieWait from reserve-one public tie states. Let σ Eb,1 , σ ∈ {−, +}.

A Match action creates the reserve-carrying public tie state

The public-height update assigns plus origin to both state+ changing successors, D1+ and Db+1 . Since

σ Eb,r .

σ V (Eb,1 ) = L(b + 1, b),

By definition of the potential on reserve-carrying public tie states,

the finite reserve-one TieWait inequality is exactly (C4.9):

σ V (Eb,r ) = L(b + r, b) = V ((b + r, b)σ ).

The conservative action value records no immediate reward or advancement charge at the Match step. Therefore the conservative Bellman inequality holds as equality. 12. Hedge actions. Consider a strict catch-up state (a, b) with 0 ≤ a < b, and let Hedge(d) be feasible. Thus 0 ≤ d ≤ b if a = 0, and 0 ≤ d < b − a if a ≥ 1. Its conservative centered value is pV (Hd ) + qV (a, b + 1) − pq.

L(b + 1, b) ≥ pL(b + 2, b) + γ σ q{b + D+ (1)} + (1 − γ σ )qD+ (b + 1) − pq

for 1 ≤ b ≤ N . For b ≥ N + 1, the reserve-one TieWait slack is ∆σE1,W (b) = L(b + 1, b) n − pL(b + 2, b) + γ σ q{b + D+ (1)} o + (1 − γ σ )qD+ (b + 1) − pq .

By (C4.12)–(C4.13), this affine slack is nonnegative for every b ≥ N + 1. Thus the Bellman inequality holds for TieWait from all reserve-one public tie states. 15. TieWait from public tie states with reserve at least two. Let σ Eb,r , r ≥ 2. Both state-changing successors are plus-origin lead states, (r, 1)+ and (b + r, b + 1)+ . The potential is σ V (Eb,r ) = L(b + r, b).

The conservative TieWait centered value is pL(b + r + 1, b) + γ σ q{b + L(r, 1)} + (1 − γ σ )qL(b + r, b + 1) − pq.

Subtracting this value from L(b + r, b) gives bγ σ q(λ − µ − 1) + (qµ − pλ + pq).

The first term is nonnegative by (C1.4), and the second term is nonnegative by (C1.5). Therefore the Bellman inequality holds for TieWait from all public tie states with reserve at least two. 16. TieOverride actions. σ At a public tie state Eb,r , the feasible range for TieOverride(j) is 1 ≤ j ≤ r. There is no TieOverride action when r = 0. The TieOverride value is V (r − j, 0) + b + j − p.

Since σ V (Eb,r ) = L(b + r, b),

the TieOverride slack is L(b + r, b) − {V (r − j, 0) + b + j − p}.

This is exactly the Override slack from the lead state (b + r, b)

σ

18. NoMining actions. Every NoMining value has the form pV (x) + qCV (x), where CV (x) is the conditional value obtained by waiting until a state change. Since p < 1/2, we have q > 0, and ⇐⇒

At a strict catch-up state, C6 gives V (a, b) ≥ V (a, b + 1),

and at a private diagonal state the finite constraint C3.3 and the tail constraints C3.9–C3.11 give V (Dbσ ) ≥ V (b, b + 1).

These inequalities are stronger than the corresponding NoMining conditional inequalities, whose right-hand sides subtract p. For (1, 0) and the signed one-block lead states (b+1, b)σ , the same conclusion follows from C7.2 in the finite region and C7.6–C7.8 in the tail. For a lead of at least two blocks, C1 gives L(a, b) − L(a, b + 1) = µ ≥ 0, which again implies the NoMining inequality for either incoming origin; the state-changing successor has plus origin but the lead potential is the same for both signs. For the public-tie cases, the finite and tail prefix-scaling constraints C3.3, C3.9–C3.11, C7.2, and C7.6–C7.8, together with C1, give Xb ≤ D+ (b) ≤ L(b, b − 1) ≤ L(b + 1, b).

The last inequality follows from λ − µ ≥ 1, and L(b + 1, b) = b(λ − µ) + q ≥ b + q. σ At Eb,0 , write

N0σ (b) = γ σ b + (1 − γ σ )Xb − p.

The preceding bounds imply N0σ (b) ≤ L(b + 1, b). The TieWait constraint C4.1, or its tail version C4.3–C4.5, therefore gives σ V (Eb,0 ) ≥ pL(b + 1, b) + qN0σ (b) ≥ N0σ (b). σ , let At Eb,1

with override parameter j . By paragraph 9, it is nonnegative. Therefore every TieOverride action satisfies the Bellman inequality. 17. NoRelease actions. For NoRelease, the successor is the current state and both reward and public-frontier advancement are zero. Its Bellman inequality is therefore the identity V (x) ≥ V (x).

V (x) ≥ pV (x) + qCV (x)

It therefore suffices to bound the conditional state-changing value. At a capitulation state (0, b), including (0, 0), this value is V (0, b + 1) − p = −p ≤ 0 = V (0, b).

V (x) ≥ CV (x).

N1σ (b) = γ σ {b + D+ (1)} + (1 − γ σ )D+ (b + 1) − p.

Constraint C7.2 at zero and C1 give D+ (1) ≤ L(1, 0) = q,

while the finite or tail C7 constraints give D+ (b + 1) ≤ L(b + 1, b) < L(b + 2, b).

Moreover, C1 implies b + q ≤ L(b + 2, b). Hence N1σ (b) ≤ L(b+2, b), and the TieWait constraint C4.9, or its tail version C4.11–C4.13, yields σ V (Eb,1 ) = L(b + 1, b) ≥ pL(b + 2, b) + qN1σ (b) ≥ N1σ (b).

Finally, let r ≥ 2. Then σ V (Eb,r ) = L(b + r, b),

and both state-changing successors are plus-origin lead states. The conditional slack is h L(b + r, b) − γ σ {b + L(r, 1)} i + (1 − γ σ )L(b + r, b + 1) − p = γ σ b(λ − µ − 1) + µ + p ≥ 0,

where the final inequality uses λ − µ ≥ 1 and µ ≥ 0 from C1. Therefore CV (x) ≤ V (x) at every state. Thus every feasible canonical state-action pair satisfies its conservative Bellman inequality. Section 3.3 then gives the exact centered Bellman inequality (3.1) for every pair. By Lemma 2, every IDEAL policy has long-run utility at most p.

3.9. Monotonicity in Hash Share

Reserve-carrying public tie values also scale automatically, because for r ≥ 1, σ σ Vp (Eb,r ) = Lp (b + r, b) = θLc (b + r, b) = θVc (Eb,r ).

We verify that the scaled variables satisfy every constraint of LN,D (p, γ − , γ + ). C0: Nonnegativity and terminal bounds. All nonnegativity constraints are preserved because θ > 0. For example, upd Bd + vdp = θ(ucd Bd + vdc ),

and the same argument applies to finite core variables, private diagonal tails, reserve-zero public tie tails, and terminal coefficients. The terminal upper bounds are preserved because 0 ≤ wkc ≤ qc

=⇒

0 ≤ wkp = θwkc ≤ θqc = qp .

LP feasibility is prefix-monotone in the tested miner’s hash share. This property justifies threshold search over p.

The terminal monotonicity constraints are homogeneous:

Theorem 2. Fix (N, D) and γ − , γ + . If the certificate LP

p c = θ(wkc − wk+1 ) ≥ 0. wkp − wk+1

The terminal extension lower condition is also preserved. Since the function x 7→ x/(1 − x) is increasing on (0, 1) and p < c, we have c p < . qp qc

LN,D (c, γ − , γ + )

is feasible at some c < 1/2, then LN,D (p, γ − , γ + )

Hence

is feasible at every p < c.

p c wK = θwK ≥θ

Proof. Let qc = 1 − c,

qp = 1 − p,

and define θ=

C1: Lead constraints. The lead normalization is preserved:

qp > 1. qc

λp − κp = θ(λc − κc ) = θqc = qp .

Take a feasible solution of

The inequalities −

+

LN,D (c, γ , γ ).

λ ≥ 1,

Let Vc be the corresponding potential, with terminal sequence extended by Lemma 3. Define

Equivalently, scale every LP variable by the same factor θ:

for σ ∈ {−, +}. Capitulation values remain Vp (0, b) = 0.

λ−µ≥1

are preserved because θ > 1. It remains to check the lead mining constraint. Let

be its slack at hash share t. Direct substitution gives ∆plead = θ{∆clead + (c − p)(λc + µc − qc )}.

(Dbσ )p = θ(Dbσ )c ,

Mbp = θMbc , Pbp = θPbc , p c ud = θud , vdp = θvdc , (g σ )p = θ(g σ )c , (hσ )p = θ(hσ )c , σ p σ c (e ) = θ(e ) , (f σ )p = θ(f σ )c , wkp = θwkc , λp = θλc , µp = θµc , κp = θκc ,

µ ≥ 0,

∆tlead = qt µt − tλt + tqt

Vp = θVc . p c Sa,b = θSa,b ,

c p p p c c w = wK−1 ≥ wK−1 . qc K−1 qc qp

The scaling slack is (3.32)

∆clead + c(λc + µc − qc ) = µc ,

which is nonnegative by C1.3. Therefore C1.5 is preserved by the generic calculation below. Generic prefix scaling. We use the following calculation repeatedly. For each one-step constraint family, let ∆t denote its inequality slack at hash share t, and let Γt denote the corresponding auxiliary slack obtained by separating the t-dependence of that

centered one-step expression. Direct substitution under the scaling above gives ∆p = θ{∆c + (c − p)Γc }.

(3.33)

Define the scaling slack Ξt = ∆t + tΓt .

be the reserve-zero TieWait slack at hash share p, and let Ξσ,p E0,W (b) be the scaling slack from C4.2 or C4.6. These slacks satisfy the prefix-scaling identity (3.35), and the scaling slack is homogeneous as in (3.36). Hence C4.1–C4.8 are preserved. For reserve-one public tie states, let

(3.34)

∆σ,p E1,W (b)

The LP imposes ∆c ≥ 0,

Ξc ≥ 0

for every one-step constraint family, where the prefix-scaling constraint is sometimes an existing constraint such as C6.1, C1.3, or C0.11. Hence   c−p p ∆c + Ξc ≥ 0. (3.35) ∆p = θ c c The scaling slack itself is homogeneous: Ξp = θΞc ≥ 0.

(3.36)

For affine-tail constraints, the same identities apply pointwise in the tail parameter b. Therefore slopes and leftendpoint values are preserved whenever the corresponding inequality slack and scaling slack are constrained at c. C2: Strict catch-up Wait constraints. The finite strict catch-up Wait constraints are exactly of the generic form A = Sa,b ,

Y = Ya,b ,

Z = Za,b .

The prefix-scaling constraint Sa,b ≥ Za,b is exactly the finite Hedge-monotonicity constraint C6.1. Thus C2.1 is preserved by (3.35), and the scaling slack is already preserved by (3.36) as part of C6. For affine strict catch-up tails, the inequality slack ∆W d (b)

is preserved by the same generic identity, using the affine Hedge-monotonicity slack C6.2 as the scaling slack. Therefore the slope and left-endpoint constraints C2.3–C2.4 are preserved for every 1 ≤ d ≤ D. C3: Private diagonal constraints. The private diagonal Wait constraints are of the generic form A = Dσ (b),

Y = L(b + 1, b),

Z = V(b, b + 1),

with σ ∈ {−, +}. Hence the finite constraints C3.1–C3.3 and the tail constraints C3.6–C3.11 are preserved. The private diagonal Match constraints are homogeneous: D− (b) ≥ E0− (b),

D+ (b) ≥ E0+ (b).

Their slacks are multiplied by θ, so C3.4–C3.5 and C3.12– C3.15 are preserved. C4: Public tie constraints. For reserve-zero public tie states, let ∆σ,p E0,W (b)

be the reserve-one TieWait slack at hash share p, and let Ξσ,p E1,W (b) be the scaling slack from C4.10 or C4.14. The same prefix-scaling identity preserves C4.9–C4.16. For reserve r ≥ 2, no additional finite LP variables are introduced. The TieWait inequalities are consequences of C1, and TieOverride is handled through the same lead/Override dominance argument used in the soundness proof. Since C1 is preserved, the reserve-r ≥ 2 public tie part remains valid. C5: Hedge-success upper constraints. Every Hedge-success upper constraint has the form V (Hd ) ≤ q.

After scaling, Vp (Hd ) = θVc (Hd ) ≤ θqc = qp .

Thus C5 is preserved, including the finite, affine-tail, and terminal Hedge successor cases. C6: Hedge monotonicity constraints. Hedge monotonicity constraints are homogeneous: V (a, b) ≥ V (a, b + 1).

After scaling, Vp (a, b) − Vp (a, b + 1) = θ{Vc (a, b) − Vc (a, b + 1)} ≥ 0.

Therefore C6.1–C6.4 are preserved. The terminal monotonicity part is already covered by C0.11 and Lemma 3. C7: One-block lead Wait constraints. The one-block lead Wait constraints are of the generic form A = L(b + 1, b),

Y = L(b + 2, b),

Z = D+ (b + 1).

The prefix-scaling constraint is exactly C7.2 in the finite region and C7.6–C7.8 in the tail region. Hence the finite constraints C7.1–C7.2 and the tail constraints C7.3–C7.8 are preserved by the generic scaling calculation. C8: Terminal strict catch-up constraints. The terminal boundary constraint at deficit D + 1 is also of the generic form: write a = b − (D + 1) and set A = aw1 , Y = CD (b), Z = aw2 .

The scaling slack is aw1 ≥ aw2 , which follows from terminal monotonicity C0.11. Therefore C8.1–C8.3 are preserved by (3.35), and no additional C8 prefix-scaling constraint is needed.

For the explicit terminal superharmonic constraints, compute p p wkp − pwk−1 − qp wk+1 c c = θ(wkc − cwk−1 − qc wk+1 ) (3.37) c c + (c − p)θ(wk−1 − wk+1 ). Here the scaling slack is c c c c c (wkc − cwk−1 − qc wk+1 ) + c(wk−1 − wk+1 ) = wkc − wk+1 ,

which is nonnegative by terminal monotonicity C0.11. Hence C8.4 is preserved. The terminal extension lower condition C8.5 was already checked under C0. Thus every constraint of LN,D (p, γ − , γ + )

Let u, u′ ∈ A(x). We say that u′ weakly dominates u at x, and write u ⪯x u′ , if the following holds. For every continuation policy π starting from x whose first action is u, there exist a continuation policy π ′ starting from x whose first action is u′ and a coupling of the two continuations such that, on every coupled execution, for every finite transition depth n ∈ Z≥0 , ′

Lπn = Lπn ,

′

Rcπi ,n ≥ Rcπi ,n .

Lemma 4. Let x be a canonical REAL state. The following action dominances hold at x. 1)

is satisfied by the scaled variables. Therefore the LP is feasible at every p < c.

4. From IDEAL to REAL

First, suppose that a release action u publishes one or more blocks on a non-active private branch. Let u′ be the release action obtained by omitting all non-active blocks while leaving every other released block unchanged. Then u ⪯x u′ .

We transfer the certificate from IDEAL to REAL in two steps. First, we lift it to core-REAL by canonicalizing arbitrary core deviations into IDEAL policies. Second, split accounting transfers the core-REAL bound to arbitrary REAL deviations.

Second, suppose that a release action u publishes only blocks on the active core-side branch but creates neither a public tie nor a strictly longest core-side branch. Let ū = NoRelease. Then u ⪯x ū.

4.1. From IDEAL to core-REAL

2)

Fix a tested miner mi and a strategic core ci of hash share p. All operational identities other than ci , including the Frontier component of mi if present, follow the Frontier strategy. Throughout this section, write q = 1 − p.

We aggregate these Frontier-following operational identities into a Frontier aggregate of hash share q . A Frontier discovery is always understood together with the Frontier strategy’s immediate publication of the discovered block. Thus one effective Frontier transition includes the newly published Frontier block. A REAL history has a canonical prefix if every action already taken by ci is one of the canonical actions defined in Section 2.2: Wait, Hedge, NoMining, NoRelease, Override, Match, TieWait, TieOverride. By Lemma 1, every canonical-prefix REAL history has a unique current reduced state in the canonical state space Xb defined in Section 3.1. Fix a canonical REAL state x, and write A(x) = Aci (x) for the strategic core’s feasible action set. For a continuation policy π starting from x, let rcπi ,t be the reward from blocks with source component ci that become newly included in the common trunk in transition t, and let ℓπt be its publicfrontier advancement. Define n−1 n−1 X X Rcπi ,n := rcπi ,t , Lπn := ℓπt . t=0

t=0

Suppose there is an active core-side branch B of height H ≥ 1. Let A be a mining action that does not extend the tip of B , and suppose an mi success under A creates a branch of unresolved height ℓ ≤ H + 1. Let N = NoMining, and let W be the canonical action that extends the tip of B , namely Wait at a non-public-tie state and TieWait at a public-tie state. Then A ⪯x N

if ℓ ≤ H,

A ⪯x W

if ℓ = H + 1.

Proof. For part 1, fix a continuation policy π whose first action is u. In the first case, replace u by u′ ; any activebranch publication, including one that creates a tie or an override, is retained. The omitted branches are strictly below the relevant public branch by the canonical-state definition and therefore do not affect the public longest-branch comparison. In the second case, replace u by ū; this also preserves that comparison because u creates neither a tie nor an override. In both cases, keep the omitted blocks private and simulate π . Couple all later actions, discoveries, and tie-breaking outcomes identically. This coupling witnesses the required dominance and proves part 1. For part 2, fix a continuation policy π whose first action is A, and let BA be the branch created by an mi -success. First suppose ℓ ≤ H and replace A by N . Couple the statepreserving probability-p branch of N with the A-success branch, and its probability-q state-changing branch with the Frontier-success branch under A. After the state-preserving branch, let the next action begin a simulation of the continuation after the A-success, replacing BA by the heightℓ prefix of B . Map every later mining or release action

involving BA to this substituted prefix and copy all other actions and discoveries. At every coupled increase of the maximum public height, the two continuations compare the same private and public heights and therefore update to the same tie-origin label. Together with the fixed total Frontier allocation in a multi-branch tie, this preserves every later tie resolution. The paired first transitions have zero reward and advancement, and all later transitions are paired one-forone. Thus public evolution and advancement are identical. If BA enters the common trunk, its substitute contains weakly more mi -blocks; otherwise the reward is unchanged. Hence A ⪯x N . Now suppose ℓ = H + 1 and replace A by W . Couple the next discovery and any tie-breaking outcome. A Frontier discovery gives the same successor. On an mi success, W creates an all-mi path B + of height H + 1, the same height as BA . Simulate the continuation after the A-success by replacing BA with B + , mapping later mining and release actions to the substituted path and copying all other actions and discoveries. Again, the public evolution and advancement are identical, while every common-trunk prefix contains weakly more mi -blocks. Hence A ⪯x W .

Every action in Tb is canonical. Fix j ≥ 0. The remaining breadth-first replacements from Tj to Tb are weakly dominating, and their couplings compose. Thus, on every coupled execution and at every finite transition depth n, LTn = LTnj , b

RcTi ,n ≥ RcTij,n . b

Taking expectations and the long-run liminf gives, for every j ≥ 0, Upcore (Tj ; γ − , γ + ) ≤ Upcore (Tb; γ − , γ + ).

Hence the utility of Tb is an upper bound on the utilities of all Tj , including T0 . Each replacement does not increase the number of release actions in a release phase, so Tb satisfies the restriction on consecutive NoRelease actions. Thus Tb specifies an IDEAL policy π b. Since T0 is the policy tree of π c , it follows that Upcore (π c ; γ − , γ + ) ≤ Upcore (π b; γ − , γ + ).

Theorem 4. Suppose the certificate LP We define a policy tree rooted at x as a rooted tree whose root state is x. Each nonterminal node is a state– action pair (y, u), where u is feasible at y , and each possible transition under u gives an edge to a child whose state is the corresponding successor. Different nodes may have the same state and choose different actions. A policy induces a policy tree by assigning to each node the action prescribed for its root-to-node history; conversely, a policy tree specifies a policy on its histories. A policy tree rooted at the initial state is called simply a policy tree. Theorem 3. For every feasible core policy π c of the strategic core ci , there exists an IDEAL policy π b, using only the release actions NoRelease,

Override,

Match,

TieOverride,

LN,D (p, γ − , γ + )

is feasible. Then every feasible core policy π c of a strategic core with hash share p satisfies Upcore (π c ; γ − , γ + ) ≤ p,

where Upcore is the long-run ratio of cumulative strategiccore reward to cumulative public-frontier advancement. Proof. Fix any core policy π c . By Theorem 3, there is an IDEAL policy π b such that Upcore (π c ; γ − , γ + ) ≤ Upcore (π b; γ − , γ + ).

Feasibility of LN,D (p, γ − , γ + ) gives a potential satisfying every centered Bellman inequality. By Lemma 2, Upcore (π b; γ − , γ + ) ≤ p.

and the mining actions Wait,

Hedge,

NoMining,

TieWait,

Therefore Upcore (π c ; γ − , γ + ) ≤ Upcore (π b; γ − , γ + ) ≤ p.

such that Upcore (π c ; γ − , γ + ) ≤ Upcore (π b; γ − , γ + ).

Proof. Let T0 be the policy tree induced by π c . Construct a sequence T0 , T1 , T2 , . . . by breadth-first canonicalization. At stage j , a processed prefix contains only canonical actions. At the first node following such a prefix whose action is noncanonical, apply Lemma 4 to replace it by a canonical action. Use the dominating residual continuation supplied by the lemma to obtain Tj+1 from Tj . The breadth-first construction replaces every node only finitely many times and therefore defines a unique limit tree Tb.

4.2. From core-REAL to REAL Theorem 5. Let hLB < 1/2 satisfy LN,D (hLB , γ − , γ + )

is feasible.

If every miner mi ∈ M satisfies αi ≤ hLB ,

then the Frontier profile is a Nash equilibrium in the REAL model.

Proof. By prefix monotonicity, feasibility at hLB implies feasibility at every β ≤ hLB . By Theorem 4, every core policy of core share β ≤ hLB satisfies Uβcore (π c ) ≤ β.

Fix a miner mi with αi ≤ hLB and a REAL deviation (p, π c ), where 0 ≤ p ≤ 1. Set β = αi p,

k=

αi (1 − p) . 1 − αi p

Then β ≤ hLB , so Uβcore (π c ) ≤ β.

Moreover, 0 ≤ k ≤ 1 because αi < 1. At transition depth n, let Cn be the cumulative commontrunk reward whose source component is the strategic core, and let Fn be the cumulative common-trunk reward whose source component belongs to the Frontier aggregate. Since Frontier components are operationally indistinguishable, the Frontier component of mi receives the fraction k of the expected Frontier-aggregate reward. Hence E[Ri,n ] = E[Cn ] + k E[Fn ]. The common trunk cannot extend beyond the maximum public height. Therefore, for the cumulative public-frontier advancement Ln , Cn + Fn ≤ Ln

pathwise. It follows that E[Ri,n ] = k E[Cn + Fn ] + (1 − k)E[Cn ] ≤ k E[Ln ] + (1 − k)E[Cn ]. Whenever E[Ln ] > 0, division by E[Ln ] gives E[Ri,n ] E[Cn ] ≤ k + (1 − k) . E[Ln ] E[Ln ] Taking the long-run lower limit and using the core bound yields Ui ((p, π c ), ΣF−i ) ≤ k + (1 − k)Uβcore (π c ) ≤ k + (1 − k)β = αi .

Thus no REAL deviation gives mi utility greater than αi . Since mi was arbitrary, Frontier is a Nash equilibrium.

5. Algorithm for Lower Bounds We now give an algorithm for computing a lower bound for the REAL model. It searches for a feasible certificate LP in the IDEAL model. Once such a certificate is found, Theorems 4 and 5 give the corresponding REAL guarantee. The input is a REAL-model parameter tuple (γ − , γ + ), LP parameters (N, D), and a precision parameter ε. The output is the certified lower bound LB αN,D (γ − , γ + )

Algorithm 1 REAL lower-bound algorithm Require: γ − , γ + , N, D, ε LB Ensure: αN,D (γ − , γ + ) 1: ℓ ← 0 2: u ← 1/2 LB 3: αN,D (γ − , γ + ) ← 0 4: while u − ℓ > ε do 5: p ← (ℓ + u)/2 6: if LN,D (p, γ − , γ + ) is feasible then 7: ℓ←p LB 8: αN,D (γ − , γ + ) ← p 9: else 10: u←p 11: end if 12: end while LB 13: return αN,D (γ − , γ + ) such that, if every miner mi ∈ M satisfies LB αi ≤ αN,D (γ − , γ + ),

then the Frontier profile is a Nash equilibrium in the REAL model. Let LN,D (p, γ − , γ + ) denote the certificate LP defined in Section 3.6. Theorem 6. Suppose Algorithm 1 returns LB αN,D (γ − , γ + ).

Then the returned value is a lower bound on the REAL incentive-compatibility threshold: LB αN,D (γ − , γ + ) ≤ α∗ (γ − , γ + ).

Proof. By Theorem 2, LP feasibility is prefix-monotone in p, so Algorithm 1 returns a certified feasible point. Theorem 5 then places this point in I REAL (γ − , γ + ), proving the claim.

6. Algorithm for Upper Bounds This section gives an algorithm for computing an upper bound on the incentive-compatibility threshold from fixed tie-breaking parameters (γ − , γ + ). We first define two explicit trigger policies and use SM1 as a third policy [4]. We then derive the trigger-policy gains in closed form and minimize the hash shares at which the candidate policies become profitable.

6.1. Candidate Deviation Policies Fix a tested miner with hash share p ∈ (0, 1/2) and write q = 1 − p. For an absolute Frontier-side height b, abbreviate T1 (b) := (b − 1, b),

T2 (b) := (b − 2, b).

Thus T1 (b) and T2 (b) are states in which the tested miner trails by one and two blocks, respectively.

The plus-trigger and minus-trigger algorithms use the same matched-trail rule with an integer trigger height B ≥ 3: 1) 2)

3) 4)

σ At Dbσ , apply Match and enter Eb,0 . σ At Eb,0 , apply TieWait. A tested-miner discovery σ enters Eb,1 and is followed by TieOverride(1), which settles b + 1 tested-miner blocks. A Frontier discovery on the core-side tied branch settles b tested-miner blocks and one Frontier block. A Frontier discovery on the competing branch enters T1 (b + 1). At T1 (b), apply Hedge(1) if b = 1 and Wait if b ≥ 2. A tested-miner discovery enters Db− , and a Frontier discovery enters T2 (b + 1). At T2 (h), end the current cycle and begin a new cycle under Frontier mining if h < B , and apply Wait if h ≥ B . In the latter case, a tested-miner discovery returns to T1 (h), whereas a Frontier discovery ends the current cycle and begins a new cycle under Frontier mining.

+ Algorithm 2 Plus-trigger policy πB

Require: Trigger height B ≥ 3 1: Start a renewal cycle from the initial public state 2: if Frontier discovers the first block then 3: End the current cycle and begin a new cycle under Frontier mining 4: else 5: Withhold the first tested-miner block 6: end if 7: if the tested miner discovers the second block then 8: Mine privately until the lead falls from two to one 9: Publish the private branch, override, and end the cycle 10: else 11: Enter D1+ and follow the matched-trail rule with trigger B 12: end if − Algorithm 3 Minus-trigger policy πB

Require: Trigger height B ≥ 3 1: Start a renewal cycle from the initial public state 2: if the tested miner discovers the first block then 3: Release that block and end the cycle 4: else 5: Enter T1 (1) and follow the matched-trail rule with trigger B 6: end if The two trigger policies differ only in how they enter the matched-trail subsystem. The plus-trigger policy starts a private branch after the tested miner’s first discovery, whereas the minus-trigger policy starts one block behind after a first discovery by Frontier. We also use SM1, the standard one-block selfish-mining policy, which uses only the plus-origin tie-breaking parameter.

6.2. Preliminaries for the Gain Analysis For an explicit regenerative policy π , consider one renewal cycle. Let Rπ be the reward credited to the tested miner for blocks newly included in the common trunk during the cycle, and let Lπ be the public-frontier advancement during the cycle. If the cycle has finite expected length and E[Lπ ] > 0, then E[Rπ ] . Uπ = E[Lπ ] Define the centered renewal gain ∆π (p) := E[Rπ − pLπ ].

(6.1)

Then Uπ − p =

∆π (p) . E[Lπ ]

(6.2)

Thus every p at which an explicit policy has positive centered gain is an upper bound on the incentive-compatibility threshold. We next derive the recurrence shared by the plus-trigger and minus-trigger families. Let Fb be the expected centered reward from T1 (b), let Jb be the value from T2 (b), and let Mσ (b) be the value after Match at Dbσ . Resolving the public tie gives Mσ (b) = pq(b + 1) + γ σ q(qb − p) + (1 − γ σ )qFb+1 .

(6.3)

For b ≥ B , the policy continues from a two-block deficit, so Fb = pM− (b) + qJb+1 ,

Jb = pFb − pq(b + 1). (6.4)

The solution is affine in b. Define r3 := pq(2 − γ − ), s := 1 − r3 , pq(p − q + γ − q) , A := s r3 A + pq(p − 2q − γ − p) C := . s

(6.5)

FB−1 = A(B − 1) + C.

(6.6)

Then Below the trigger height, a Frontier discovery from a two-block deficit ends the cycle. With r2 := pq(1 − γ − ),

the finite-prefix recurrence is   Fb = r2 Fb+1 − pq q(1 − γ − )b + q + γ − p .

(6.7)

Hence F2 = r2B−3 {A(B − 1) + C} B−4 X j  (6.8) − pq r2 q(1 − γ − )(j + 2) + q + γ − p , j=0

6.5. Upper-Bound Algorithm

and F1 = r2B−2 {A(B − 1) + C} B−3 X j  (6.9) − pq r2 q(1 − γ − )(j + 1) + q + γ − p .

For SM1 [4], the sign-change point is θSM1 (γ + ) =

j=0

1 − γ+ . 3 − 2γ +

(6.12)

For each B ≥ 3, define An empty sum is interpreted as zero. Since p < q and pq(2− γ − ) ≤ 1/2, all three policies have finite expected cycle length.

6.3. Plus-Trigger Gain

Algorithm 4 REAL upper-bound algorithm

For Algorithm 2, first condition on the tested miner discovering the first two blocks. The private lead is then two. Let τ be the number of subsequent discoveries until this lead first falls to one, and let Aτ and Hτ be the numbers of tested-miner and Frontier discoveries before that time. At stopping, Hτ − Aτ = 1. Since p < q , Wald’s identity gives (q − p)E[τ ] = 1,

+ − − + θB (γ , γ + ) := inf{p ∈ (0, 1/2) : ∆+ B (p, γ , γ ) > 0}, − − − θB (γ ) := inf{p ∈ (0, 1/2) : ∆− B (p, γ ) > 0}. (6.13) The infimum of an empty set is +∞.

E[Hτ ] = q E[τ ] =

Require: γ − , γ + and an integer Bmax ≥ 3 UB Ensure: αB (γ − , γ + ) max 1: u ← θSM1 (γ + ) 2: for B = 3, . . . , Bmax do + − − 3: Compute θB and θB from the signs of ∆+ B and ∆B + − 4: u ← min{u, θB , θB } 5: end for UB 6: return αB (γ − , γ + ) ← u max Theorem 7. For every Bmax ≥ 3 and (γ − , γ + ) ∈ [0, 1]2 , Algorithm 4 returns an upper bound on the REAL incentivecompatibility threshold:

q . q−p

When the lead reaches one, the policy overrides with a branch consisting entirely of tested-miner blocks. The branch has length Hτ + 1. Its reward and public-frontier advancement are both Hτ + 1, so the conditional expected centered gain is   q K2 = q E[Hτ + 1] = q 1 + . q−p If instead the tested miner discovers the first block and Frontier discovers the second, the process reaches D1+ . Substituting b = 1 and σ = + into Equation (6.3) yields M+ (1) = 2pq + γ + q(q − p) + (1 − γ + )qF2 .

UB α∗ (γ − , γ + ) ≤ αB (γ − , γ + ). max

Proof. Each candidate in Algorithm 4 is the infimum of hash shares at which one explicit REAL policy has positive centered gain. By Equation (6.2), every such positive-gain point admits a profitable unilateral deviation. The threshold is no larger than the infimum of those points for each policy, and hence no larger than their minimum.

7. γ -Monotonicity The REAL incentive-compatibility threshold is coordinatewise nonincreasing in (γ − , γ + ). Write Γ = (γ − , γ + )

Finally, a first discovery by Frontier contributes −p and ends the cycle. Conditioning on the first two discoveries therefore gives   − + ∆+ (6.10) B (p, γ , γ ) = −pq + p pK2 + qM+ (1) . The plus-trigger policy is profitable if and only if this gain is positive.

6.4. Minus-Trigger Gain

and abbreviate I REAL (Γ) := I REAL (γ − , γ + ),

We order tie-breaking pairs coordinatewise: ΓL ⪯ ΓH

⇐⇒

− + γL− ≤ γH and γL+ ≤ γH .

Fix a strategic-core hash share p ∈ (0, 1) and set q = 1 − p. For n ≥ 0, let JnΓ (x) be the supremum expected cumulative centered gain over all canonical IDEAL policy trees rooted at x and having depth at most n. Stopping at any node is allowed. Hence

For Algorithm 3, the centered renewal gain is − ∆− B (p, γ ) = pq + qF1 .

α∗ (Γ) := α∗ (γ − , γ + ).

J0Γ (x) = 0

(6.11)

The minus-trigger policy is profitable if and only if this gain is positive. It does not depend on γ + .

For n ≥ 1, define  QΓn (x, u) := EΓ R(x, u, X ′ ) − pL(x, u, X ′ )  Γ + Jn−1 (X ′ ) | x, u .

The Bellman recursion is (

)

JnΓ (x) = max 0, max QΓn (x, u) .

(7.1)

b u∈A(x)

These finite policy trees are analytical objects; their nodes need not merge when they have the same reduced state. σ At a public tie state Eb,r , the two Frontier-success successors under TieWait are   r = 0, (0, 1), + Cb,r := D1 , r = 1,  (r, 1)+ , r ≥ 2,   r = 0, (b, b + 1), + Fb,r := Db+1 , r = 1,  (b + r, b + 1)+ , r ≥ 2. The state Cb,r follows a discovery on the core-side tied branch and immediately fixes its length-b all-core prefix. The state Fb,r follows a discovery on the competing Frontier-side branch. Lemma 5. For every Γ, n ≥ 0, b ≥ 1, and r ≥ 0, b + JnΓ (Cb,r ) ≥ JnΓ (Fb,r ).

(7.2)

Lemma 6. If ΓL ⪯ ΓH , then for every canonical state x and every n ≥ 0, (7.3)

Proof. We induct on n. The claim is immediate for n = 0. Assume it holds at depth n − 1. Except for TieWait and NoMining at a public tie state, the transition law and centered increment do not depend directly on Γ. The induction hypothesis therefore orders the value of every such action under ΓL and ΓH . It remains to consider TieWait and NoMining. For σ σ TieWait at Eb,r , write E ′ = Eb,r+1 , C = Cb,r , and F = Fb,r . Its depth-n action value is Γ Γ QΓn = pJn−1 (E ′ ) + qγ σ {b − p + Jn−1 (C)}

+ q(1 − γ

σ

Γ ){−p + Jn−1 (F )}.

ΓH ΓL QΓnH − QΓnL = p{Jn−1 (E ′ ) − Jn−1 (E ′ )} ΓH ΓL + qγLσ {Jn−1 (C) − Jn−1 (C)} ΓH ΓL + q(1 − γLσ ){Jn−1 (F ) − Jn−1 (F )} ΓH ΓH σ + q(γH − γLσ ){b + Jn−1 (C) − Jn−1 (F )}. (7.5) The first three terms are nonnegative by the induction hypothesis. The last is nonnegative by Lemma 5. Thus the TieWait value is weakly larger under ΓH . σ At E = Eb,r , the depth-n NoMining action value is Γ Γ QΓn,N (E) = pJn−1 (E) + qγ σ {b − p + Jn−1 (C)} Γ + q(1 − γ σ ){−p + Jn−1 (F )}.

Using ΓL as the baseline gives L H (E) (E) − QΓn,N QΓn,N

Proof. Take any depth-n canonical policy tree rooted at Fb,r and simulate it from Cb,r . Apply every action to the corresponding suffix and couple all discoveries and tiebreaking outcomes identically. The two states have the same public height and relative lead r −1. They are both unsigned strict catch-up states when r = 0, plus-origin diagonal states when r = 1, and plus-origin lead states when r ≥ 2. Thus the simulation is feasible and preserves both depth and public-frontier advancement. The only difference is the length-b prefix. At Cb,r , its b all-mi blocks have already been fixed. If the simulated continuation from Fb,r later fixes the core-side prefix, this initial reward b exactly matches its reward; if it fixes the competing Frontier prefix, the Cb,r execution earns b more. Thus the simulated centered gain plus b is pathwise at least the original gain. Taking expectations and then the supremum proves (7.2).

JnΓL (x) ≤ JnΓH (x).

Both Frontier-success outcomes advance the public frontier by one; the core-side outcome additionally fixes b core blocks. Their centered increments are therefore b − p and σ −p, respectively. Let γLσ and γH denote the corresponding coordinates of the two parameter pairs. Expanding the difference using the lower parameter as the baseline gives

ΓH ΓL = p{Jn−1 (E) − Jn−1 (E)} ΓH ΓL + qγLσ {Jn−1 (C) − Jn−1 (C)} ΓH ΓL + q(1 − γLσ ){Jn−1 (F ) − Jn−1 (F )} ΓH ΓH σ + q(γH − γLσ ){b + Jn−1 (C) − Jn−1 (F )}.

The induction hypothesis makes the first three terms nonnegative, and Lemma 5 makes the last term nonnegative. Thus every feasible action has weakly larger depth-n value under ΓH . Taking the maximum in (7.1) completes the induction. The lemma compares optimized finite-depth values, not the value of every fixed policy. After a favorable tie outcome becomes more likely, the optimal continuation may change. Lemma 7. Fix p ∈ (0, 1) and Γ. If JnΓ (0, 0) > 0

for some finite n, then there is a core-REAL policy π c satisfying Upcore (π c ; Γ) > p. (7.6) Proof. Choose a finite canonical policy tree T with positive expected centered gain G := EΓ [RT − pLT ] > 0.

The canonical tree can be executed directly in REAL. At each leaf, choose a public maximum tip, mine on it until the next discovery, and release a core discovery immediately. The resulting public longest branch is unique and one block higher. This reset has expected centered gain at least p(1 − p) + (1 − p)(−p) = 0.

Let dT ≥ 1 be the depth of T and set (7.4)

M = 2dT .

Every private or public branch created during T has height at most dT above the cycle root. The reset adds one public block, and dT + 1 ≤ M . From the unique public tip, use Frontier-style public mining until the cycle’s total advancement is exactly M . Thus the final public tip lies above every private and public branch created during T . Each padding block has expected centered gain zero, so the resulting finite cycle has advancement M on every path and expected centered gain at least G. Repeat this cycle above each successive unique public tip and ignore private branches left by earlier cycles. This defines a core-REAL policy π c . Since every cycle has expected centered gain at least G and advancement M , G > p. Upcore (π c ; Γ) ≥ p + M Theorem 8. If ΓL ⪯ ΓH , then Consequently,

I REAL (ΓH ) ⊆ I REAL (ΓL ).

(7.7)

α∗ (ΓL ) ≥ α∗ (ΓH ).

(7.8)

Proof. We prove the set inclusion by contraposition. Suppose c∈ / I REAL (ΓL ). Then some REAL instance in which every miner has hash share at most c admits a profitable deviation by a miner mi of share αi ≤ c. Let β be the operational hash share assigned to its core component. The split-accounting argument in Theorem 5 gives, for some k ∈ [0, 1], Ui ≤ k + (1 − k)Uβcore ,

αi = k + (1 − k)β.

8. Algorithm for Arbitrary Tie Parameters In this section, we provide an algorithm that, for any tie-breaking pair, returns lower and upper bounds on the incentive-compatibility threshold together with a theoretical guarantee on their accuracy. The monotonicity result extends bounds computed on a finite grid to every tie-breaking pair. Fix a spacing h = 1/M , where M is a positive integer, and consider the grid Gh = {0, h, . . . , 1}2 .

Suppose that a certified lower bound αLB (Γg ) and a verified upper bound αUB (Γg ) are available at the required grid points. For a target pair Γ = (γ − , γ + ) ∈ [0, 1]2 , let i = min{⌊γ − /h⌋, M − 1}, j = min{⌊γ + /h⌋, M − 1}, ΓL = (ih, jh), ΓH = ((i + 1)h, (j + 1)h).

(8.1)

Here ΓL and ΓH denote the coordinatewise lower and upper corners of the grid cell. In coordinatewise order, ΓL ⪯ Γ ⪯ ΓH .

Algorithm 5 Threshold bounds at arbitrary tie parameters Require: Γ = (γ − , γ + ), h = 1/M , and grid bounds αLB , αUB Ensure: [αh (Γ), αh (Γ)] 1: Compute ΓL and ΓH from Equation (8.1) 2: αh (Γ) ← αLB (ΓH ) 3: αh (Γ) ← αUB (ΓL ) 4: return [αh (Γ), αh (Γ)]

Profitability therefore implies Uβcore > β,

0 < β ≤ c.

(7.9)

Apply Theorem 3 under ΓL . It yields an IDEAL policy with utility greater than β . For some finite transition depth n, the policy’s expected cumulative centered gain is therefore positive. Unfolding its first n transitions gives a finite canonical policy tree, so JnΓL (0, 0) > 0.

Theorem 9. For every Γ ∈ [0, 1]2 , Algorithm 5 returns bounds satisfying αh (Γ) ≤ α∗ (Γ) ≤ αh (Γ).

Moreover, αh (Γ) − αh (Γ) ≤ εh ,

where εh :=

Lemma 6 gives JnΓH (0, 0) > 0,

and Lemma 7 converts this witness into a profitable coreREAL policy of share β under ΓH . Finally, create a REAL instance with one strategic miner of share β and split the remaining share 1−β equally among m Frontier miners, where   1−β m≥ . c Every miner then has share at most c, but the strategic miner’s core policy is profitable. Hence c∈ /I

REAL

(ΓH ).

This proves (7.7). Taking suprema gives (7.8).

(8.2)

max

0≤i,j<M

 UB α (ih, jh) − αLB ((i + 1)h, (j + 1)h) . (8.3)

Proof. Theorem 8 and the pointwise guarantees of Algorithms 1 and 4 give αLB (ΓH ) ≤ α∗ (ΓH ) ≤ α∗ (Γ) ≤ α∗ (ΓL ) ≤ αUB (ΓL ).

The endpoints in this chain are exactly the values returned by the algorithm. For the cell indexed by (i, j), their difference is αUB (ih, jh) − αLB ((i + 1)h, (j + 1)h).

Taking the maximum over all cells proves the width bound.

9. Experiments

weights θk ≥ 0 and value is

This section implements the lower- and upper-bound algorithms using exact rational arithmetic and reports the maximum pointwise gap over the evaluated parameter pairs and the uniform interval width guaranteed over [0, 1]2 .

P

k θk = 1, its exact centered action

K X

θk BV (x, uk ).

k=1

The Bellman inequality for every uk therefore implies the same inequality for their convex combination.

9.1. Implementation 10.2. Stale Blocks For each γ − , γ + ∈ {0, 0.001, . . . , 0.999}, we use exact rational arithmetic to examine hash shares of the form p = m/1010 . Algorithm 1 with N = D = 20 reports the largest feasible value as the lower bound, while Algorithm 4 with Bmax = 24 reports the smallest value with strictly positive centered gain as the upper bound.

9.2. Results Let E := {0, 0.001, . . . , 0.999}2 . For each evaluated pair Γ ∈ E , define the pointwise gap d(Γ) := αUB (Γ) − αLB (Γ).

Exact rational evaluation gives max d(Γ) = Γ∈E

2415 = 2.415 × 10−7 1010

For Γi,j := (0.001i, 0.001j), define the width of grid cell (i, j) by ei,j := αUB (Γi,j ) − αLB (Γi+1,j+1 ).

Following Gervais et al. [5], suppose that a fraction s ∈ [0, 1) of the blocks generated by every miner other than the deviating miner becomes stale. For a deviating miner of hash share α, deleting these stale discoveries leaves the original model with effective hash share α ps (α) = . α + (1 − s)(1 − α) Equivalently, the nondeviating miners’ hash power is multiplied by 1 − s and the remaining hash power is normalized. The resulting threshold αs∗ satisfies ps (αs∗ ) = α∗ . Solving gives αs∗ (γ − , γ + ) =

(1 − s)α∗ (γ − , γ + ) . 1 − sα∗ (γ − , γ + )

Thus the stale-block model requires no new strategic analysis: the same transformation gives its threshold and maps the original lower and upper bounds to stale-block lower and upper bounds.

11. Related Work

The maximum grid-cell envelope width is ε0.001 :=

max

0≤i,j<1000

ei,j =

9,980,060 = 9.98006 × 10−4 . 1010

Thus Algorithm 5 returns, for every (γ − , γ + ) ∈ [0, 1]2 , an interval containing α∗ (γ − , γ + ) with width at most 9.98006 × 10−4 .

10. Discussion 10.1. Multiple Ties The allocation of Frontier hash power among multiple core-side branches is immaterial. The total core-side share must remain γ σ , but its division among those branches may be arbitrary. To see this, extend an IDEAL core mining action so that it may allocate hash power among finitely many feasible targets. In the simulation of Lemma 4, part 2, the IDEAL core uses the same relative allocation over the corresponding targets as the Frontier core-side share. Conditional on the successful target, the original branchwise coupling then applies unchanged. This extension requires no change to the certificate LP. If an allocation uses pure target actions u1 , . . . , uK with

The work most directly related to ours studies strategic mining and the incentive-compatibility threshold. Eyal and Sirer introduced selfish mining and showed that it can be profitable below the majority threshold [4]. Nayak et al. enlarged this strategy space with stubborn-mining policies [6]. Sapirshtein et al. proposed a method for deriving optimal selfish-mining strategies using a Markov Decision Process and computed near-tight numerical threshold bounds [2]. Bar-Zur et al. improved the efficiency of this MDP computation [7]. Kiayias et al. derived theoretical sufficient and necessary conditions for honest mining [3]. We continue this line of work while providing theoretical lower and upper bounds in the broader REAL model. Although our model is an n-miner game, the proof concerns unilateral deviations from the all-Frontier profile; multiple simultaneously strategic miners are studied in [8], [9]. Several extensions study related thresholds under different network or protocol assumptions. Gervais et al. incorporate naturally stale blocks and network parameters into proof-of-work security analysis [5]. Bahrani et al. study selfish mining under general stochastic rewards [10]. Chatterjee et al. provide automated selfish-mining analysis for efficient proof-system blockchains [11]. Niu and Feng, and Ritz and Zugenmaier, study how Ethereum’s uncle rewards affect selfish mining [12], [13]. Bitcoin-NG separates leader

election from transaction serialization [14], and Niu et al. study its protocol-specific incentive compatibility [15]. Other important work addresses adjacent incentive and security questions. Carlsten et al. show that fee-dominated rewards can destabilize Bitcoin after block subsidies decline [16]. Badertscher et al. use rational protocol design to show that rational incentives can replace the honest-majority assumption under suitable reward conditions [17]. Garay et al. establish the Bitcoin backbone properties [18]. Gaži et al. and Dembo et al. independently derive tight bounds for longest-chain consistency [19], [20]. These security thresholds bound the adversarial power under which safety or liveness is preserved, whereas our incentive-compatibility threshold asks whether Frontier mining is a best response for miners. Propagation incentives are studied for transactions by Babaioff et al. [21] and for blocks by Maeda et al. [22]. Schrijvers et al. separately characterize the incentive compatibility of mining-pool reward functions [23].

12. Conclusion We studied the incentive compatibility of the REAL model, which allows a broad miner action space and asymmetric tie-breaking. Our IDEAL-to-REAL reduction turns the certificate LP into a theoretical lower-bound algorithm, while explicit deviation policies give an independent theoretical upper-bound algorithm. Coordinatewise monotonicity and exact rational evaluation extend these bounds to every (γ − , γ + ) ∈ [0, 1]2 , with interval width at most 9.98006 × 10−4 . Thus, the two algorithms give a near-tight theoretical characterization of the incentive-compatibility threshold in the REAL model.

References

[9]

F. J. Marmolejo-Cossı́o, E. Brigham, B. Sela, and J. Katz, “Competing (semi-)selfish miners in Bitcoin,” in Proceedings of the 1st ACM Conference on Advances in Financial Technologies. ACM, 2019.

[10] M. Bahrani, M. Neuder, and S. M. Weinberg, “Selfish mining under general stochastic rewards,” in Proceedings of the 7th ACM Conference on Advances in Financial Technologies, ser. Leibniz International Proceedings in Informatics, vol. 353, 2025, pp. 20:1–20:24. [11] K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K. Pietrzak, M. Yeo, and D. Zikelic, “Fully automated selfish mining analysis in efficient proof systems blockchains,” in Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. ACM, 2024. [12] J. Niu and C. Feng, “Selfish mining in Ethereum,” in 2019 IEEE 39th International Conference on Distributed Computing Systems. IEEE, 2019, pp. 1306–1316. [13] F. Ritz and A. Zugenmaier, “The impact of uncle rewards on selfish mining in Ethereum,” in 2018 IEEE European Symposium on Security and Privacy Workshops. IEEE, 2018, pp. 50–57. [14] I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse, “Bitcoin-NG: A scalable blockchain protocol,” in 13th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, 2016, pp. 45–59. [Online]. Available: https://www. usenix.org/conference/nsdi16/technical-sessions/presentation/eyal [15] J. Niu, Z. Wang, F. Gai, and C. Feng, “Incentive analysis of BitcoinNG, revisited,” Performance Evaluation, vol. 144, p. 102144, 2020. [16] M. Carlsten, H. Kalodner, S. M. Weinberg, and A. Narayanan, “On the instability of Bitcoin without the block reward,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016, pp. 154–167. [17] C. Badertscher, J. Garay, U. Maurer, D. Tschudi, and V. Zikas, “But why does it work? a rational protocol design treatment of Bitcoin,” in Advances in Cryptology–EUROCRYPT 2018. Springer, 2018, pp. 34–65. [18] J. A. Garay, A. Kiayias, and N. Leonardos, “The Bitcoin Backbone Protocol: Analysis and applications,” in Advances in Cryptology– EUROCRYPT 2015. Springer, 2015, pp. 281–310. [19] P. Gaži, A. Kiayias, and A. Russell, “Tight consistency bounds for Bitcoin,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2020. [Online]. Available: https://eprint.iacr.org/2020/661

[1]

S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008. [Online]. Available: https://bitcoin.org/bitcoin.pdf

[2]

A. Sapirshtein, Y. Sompolinsky, and A. Zohar, “Optimal selfish mining strategies in bitcoin,” in Financial Cryptography and Data Security. Springer, 2016, pp. 515–532.

[3]

A. Kiayias, E. Koutsoupias, M. Kyropoulou, and Y. Tselekounis, “Blockchain mining games,” in Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 2016, pp. 365–382.

[4]

I. Eyal and E. G. Sirer, “Majority is not enough: Bitcoin mining is vulnerable,” in Financial Cryptography and Data Security. Springer, 2014, pp. 436–454.

[22] F. Maeda, A. Sakurai, T. Nakai, and K. Shudo, “On the incentive compatibility of block propagation in Bitcoin,” 2026, arXiv:2606.06860. [Online]. Available: https://arxiv.org/abs/2606. 06860

[5]

A. Gervais, G. O. Karame, K. Wüst, V. Glykantzis, H. Ritzdorf, and S. Capkun, “On the security and performance of proof of work blockchains,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016, pp. 3–16.

[23] O. Schrijvers, J. Bonneau, D. Boneh, and T. Roughgarden, “Incentive compatibility of Bitcoin mining pool reward functions,” in Financial Cryptography and Data Security. Springer, 2016, pp. 477–498.

[6]

K. Nayak, S. Kumar, A. Miller, and E. Shi, “Stubborn mining: Generalizing selfish mining and combining with an eclipse attack,” in 2016 IEEE European Symposium on Security and Privacy. IEEE, 2016, pp. 305–320.

[7]

R. Bar-Zur, I. Eyal, and A. Tamar, “Efficient MDP analysis for selfishmining in blockchains,” in Proceedings of the 2nd ACM Conference on Advances in Financial Technologies. ACM, 2020, pp. 113–131.

[8]

Q. Bai, Y. Xu, N. Liu, and X. Wang, “Blockchain mining with multiple selfish miners,” IEEE Transactions on Information Forensics and Security, vol. 18, 2023.

[20] A. Dembo, S. Kannan, E. N. Tas, D. Tse, P. Viswanath, X. Wang, and O. Zeitouni, “Everything is a race and Nakamoto always wins,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2020, pp. 859–878. [21] M. Babaioff, S. Dobzinski, S. Oren, and A. Zohar, “On Bitcoin and red balloons,” in Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 2012, pp. 56–73.