Optimal Reward Allocation via Proportional Splitting Thanks: This is the full version of the paper to appear at the 8th Conference on Advances in Financial Technologies (AFT 2026). Lukas Aumayr, Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, Shreekara Shastry Abstract Following the publication of Bitcoin’s arguably most famous attack, selfish mining, various works have introduced mechanisms to enhance blockchain systems’ game-theoretic resilience. The only proof-of-work reward rule with a Nash-equilibrium guarantee, FruitChains, demands reward finality on the order of days. The rules that settle in minutes have no such guarantee, and one of them, Reward Splitting, still outperforms FruitChains on most of the metrics that matter in deployment. This paper closes that gap between theory and practice. We introduce FairChain , a two-level transformation for any proof-of-work Nakamoto-style protocol. At the protocol layer, FairChain records low-difficulty samples called workshares alongside blocks. At the reward layer, it applies Proportional Reward Splitting (PRS) : each height’s reward is divided among the competing work objects in proportion to the intrinsic work behind them, with workshares supplying a fresh power estimate at every height. The fork-choice rule and block-production loop are left untouched, so the host chain’s security carries over unchanged. Workshares can be discarded once the corresponding rewards mature, leaving zero on-chain footprint. We prove FairChain is a ρ \rho -coalition-safe ϵ \epsilon -Nash equilibrium for sufficiently large parameters, matching FruitChains in theory. To evaluate practical performance, we leverage Markov decision processes and compute the optimal adversarial policy under each utility function, rather than the gain of any one attack. At a six-block confirmation window, FairChain raises the deviation threshold to 38 % 38\% of mining power and beats every mechanism in that framework on incentive compatibility, subversion gain (except FruitChains above 42 42 %), and censorship susceptibility (except FruitChains below 25 25 %). Our construction has been adopted by a live PoW blockchain, with sub-kilobyte per-block storage overhead in deployment. 1 Introduction Proof-of-work (PoW) blockchains pay miners to secure the ledger, and the rule that allocates these payments decides whether honest participation is rational. Selfish mining [ 7 ] was the first attack to make this precise: by withholding blocks and releasing them strategically, a miner with a minority of the hashing power can capture a share of the rewards exceeding its share of the power. The lasting contribution of that work was the lens rather than the strategy. It analyzed Bitcoin under proportional, rather than absolute, rewards, and showed that under this utility Bitcoin is not an equilibrium. Subsequent work optimized both the attack and its analysis [ 20 , 9 , 14 ] . Recent events have underscored that these incentives are not merely theoretical. In August 2025, the Qubic mining pool conducted a documented attack against the PoW-based Monero network, causing multiple chain reorganizations and triggering emergency mitigation proposals from the Monero research community [ 17 ] . FruitChains [ 16 ] answered selfish mining at the level of mechanism design. It guarantees fairness : every miner receives rewards approximately proportional to its power, so deviations are unprofitable. The mechanism rewards low-difficulty objects, called fruits, alongside blocks. Fruits are mined far more frequently than blocks and therefore sample the mining-power distribution more finely, so that rewards track a miner’s power rather than the variance in block discovery. FruitChains is a \rho -coalition-safe \epsilon -Nash equilibrium, the strongest game-theoretic guarantee in this line of work. The guarantee, however, holds only asymptotically. Fairness requires every fruit to be recorded within a window of R\cdot\kappa blocks, with recency parameter R=17 and security parameter \kappa , which places reward finality on the order of days. For any deployment where reward finality must be fast, this is not a usable regime. The distance between what is provable and what is deployable was made explicit by Zhang and Preneel [ 25 ] , who evaluated Nakamoto consensus [ 13 ] , FruitChains [ 16 ] , Reward Splitting [ 25 , 12 , 3 ] , and Subchains [ 19 ] under a single framework. They measured three quantities: (a) incentive compatibility, the fairness of the reward distribution; (b) subversion gain, the profitability of double spending; and (c) censorship susceptibility, the income an attacker can deny honest miners. At realistic parameters, FruitChains was not the best mechanism on most of these metrics. No prior mechanism in this literature simultaneously achieves asymptotic equilibrium guarantees and state-of-the-art practical performance. This paper closes that gap. We present Proportional Reward Splitting (PRS) , a reward mechanism that is a \rho -coalition-safe \epsilon -Nash equilibrium for large parameters, matching FruitChains in theory, and that achieves state-of-the-art practical performance at a six-block confirmation window, outperforming every mechanism of [ 25 ] on incentive compatibility and, with limited exceptions, on subversion gain and censorship susceptibility. The design begins with separating two roles that existing mechanisms conflate. On the one hand, Reward Splitting [ 25 , 12 , 3 ] makes attacks less profitable by compensating non-canonical work, but it uses a coarse 50 – 50 split whenever competing objects exist at the same height. On the other hand, FruitChains obtains a finer estimate of mining power from low-work samples, but its theoretical parameters are too large for practical finality. PRS combines these ideas by using low-work objects, which we call workshares , only as a local estimator for proportional splitting: it keeps the anti-forking effect of rewarding competing work, while replacing the coarse split by the measured mining-power distribution. For example, an adversary contributing 30\% of the power at a height receives approximately 30\% of its reward. This advantage is largest when the adversary’s power is meaningfully below one half and when the workshare sample is accurate; as the adversary approaches one half, the proportional split naturally converges to ordinary Reward Splitting. PRS could be applied to any PoW Nakamoto-style blockchain (e.g., Bitcoin [ 13 ] , PoEM [ 11 ] , Monero [ 22 ] ) by making two changes: blocks record workshares on-chain, and the reward rule is replaced with proportional splitting. Neither change affects the fork choice rule or block production, so security follows directly from the host protocol’s guarantees. We call the resulting transformation FairChain . We further provide an optimization in which workshares can be kept off-chain, thereby eliminating any on-chain costs of our transformation. Thus, the storage overhead is minimal: workshare data can be discarded once the corresponding rewards finalize. To evaluate practical performance, we follow the framework of Zhang and Preneel [ 25 ] . For each reward mechanism, we construct a Markov decision process (MDP) whose states encode the adversary’s private chain, the public chain, the current fork status, and the recent reward history. Solving this MDP yields the optimal adversarial policy for each utility objective, rather than measuring the performance of a fixed attack strategy. Under this evaluation, FairChain both increases the mining-power threshold beyond which an adversary profits from deviating and lowers its expected gain from doing so. For incentive compatibility, FairChain requires an adversary to exceed 38\% of the power to earn more than its fair share, against 35\% for the next-best mechanism, Reward Splitting. At 38\% power, an adversary earns 38\% of all rewards under FairChain , against 40\% under Reward Splitting and more than 50\% under Bitcoin or FruitChains. On subversion gain, FairChain matches or beats every alternative across the practical adversarial range, with a strict gap over every other mechanism between 30\% and 38\% power. On censorship susceptibility, it is the best mechanism above 25\% power and within two points of the best below. These advantages hold at every workshare and fork-eligibility window we test. Finally, we note that the reward mechanism introduced in this paper has been adopted in a deployed system: a live PoW blockchain based on PoEM [ 11 ] , 1 1 1 https://www.qu.ai which records workshares on-chain and allocates rewards proportionally to workshare-estimated mining power. Our discussion reports its workshare cap, freshness window, staleness discount, and resulting sub-kilobyte per-block storage overhead. These parameters ground FairChain in a deployed setting and show that the workshares required by FairChain incur only small overhead. Summary of Contributions and Roadmap. We make the following contributions: • We introduce FairChain , a protocol transformation that efficiently incorporates workshares in any PoW Nakamoto-style blockchain without changing the fork choice rule or block production. FairChain uses these workshares to realize PRS, the first reward allocation mechanism for PoW blockchains that is both incentive-compatible and practical for real-world parameters (Section 3 ). • We prove that FairChain is a \rho -coalition-safe \epsilon -Nash equilibrium for sufficiently large parameters, matching the asymptotic guarantee of FruitChains (Section 4 ). • We evaluate FairChain via Markov decision processes under practical parameters, comparing against prior mechanisms on incentive compatibility, subversion gain, and censorship susceptibility (Section 5 ). 2 Model and Notation This section first summarizes the notation ( Table 1 ) and cryptographic primitives and then outlines the execution, cryptographic, and game-theoretic models of our analysis. 2.1 Notation and Cryptographic Primitives Table 1 summarizes the notation used throughout the paper. Workshare-specific parameters are introduced where they first appear, in Sections 3 and 4 . Table 1: Summary of notation. Symbol Description Operators and sequences a.b element b of a (complex) object a A\,\|\,A^{\prime} concatenation of A and A^{\prime} |\cdot| length of an element (list items or bits) L\prec L^{\prime} L is a prefix of L^{\prime} Chains and blocks C[i] i -th block of a chain C ( C[-1] is the tip) C[{:}i],\ C[{-}i{:}] first (resp. last) i blocks of C B_{\mathsf{tx}} block in which transaction \mathsf{tx} is published \mathsf{view} execution-trace view Parties and power n total number of parties t=\rho n number of adversarial parties \rho adversarial mining power, as a fraction of the total Mining and timing Q hashing-oracle queries per party per round p probability that a player mines a block in a round \Delta network delay, in rounds w wait-time (liveness) parameter k common-prefix (safety) parameter Security parameters \kappa security parameter \lambda output length of H(\cdot) , in bits We rely on two cryptographic primitives. The function H(\cdot) is a hash function that maps an arbitrary bitstring to a value of \lambda bits and models a random oracle. 2 2 2 H should satisfy the standard hash function properties, namely collision, preimage, and second-preimage resistance. The function d(\cdot) maps a list of arbitrary bitstrings to a value of \lambda bits and is collision resistant; it can be instantiated e.g., via a Merkle tree, in which case d(\cdot) returns the tree’s root. 2.2 Execution Model Our analysis assumes a multi-party setting, following the model of Bitcoin Backbone [ 8 ] . An “environment” program \mathcal{Z} drives the execution of a protocol \Pi , by spawning for each party \mathcal{P} an instance of an “interactive Turing machine” (ITM) which executes the protocol. Interaction between parties is controlled by a program C , such that (\mathcal{Z},C) create a system of ITMs. Our analysis applies to “locally polynomially bounded” systems, ensuring polynomial time execution. Network. The execution proceeds in (a polynomial number of) rounds of size \Delta . In each round r , each party is activated and performs various operations based on its algorithm. An honest message produced at round r is delivered to all other parties at the beginning of round r+1 , i.e., our analysis assumes a synchronous network . Finally, we assume a diffuse functionality, i.e., a gossip protocol which allows the parties to share messages without the need of a fully connected graph. Parties. The set of n parties \mathbb{P} remains fixed for the duration of the execution. Each party \mathcal{P} can make a fixed number of queries to a hashing oracle, which enables participation in the distributed ledger protocol. The adversary controls at most t=\rho\cdot n parties, out of the total n at any given time, and its power is the sum of the corrupted parties’ power. Proof-of-Work. All parties have access to a random oracle \mathcal{O}_{\text{rnd}} . Each party can perform Q queries to the oracle in each round, while the adversary can perform t\cdot Q queries per round. Additionally, the protocol defines a difficulty parameter p , which denotes the probability that a player successfully creates a block in a round. In practice, the random oracle is instantiated as a hash function H(\cdot) . We assume that the codomain of H is large enough such that the outcomes of queries within a batch are practically independent. 2.3 Cryptographic Model In the cryptographic model, some parties are assumed honest (i.e., they follow the protocol) whereas the rest are Byzantine (i.e., they act arbitrarily). Note that incentives do not play a role in the security analysis under this model, and instead will be considered in the game theoretic analysis. Adversary. The adversary A is an ITM which, upon activation, may “corrupt” a number of parties by sending a relevant message to the controller after \mathcal{Z} instructs it to do so. Subsequently, when a corrupted party is supposed to be activated, A is activated instead. Furthermore, A is “adaptive”, i.e., corrupts parties on the fly, and “rushing”, i.e., decides its strategy and acts after observing the other parties’ messages. Randomized Execution. The execution of a protocol is probabilistic, with randomness coming from both honest parties and the adversary, denoted as A , which controls all corrupted nodes, as well as the environment Z , which provides inputs to honest nodes throughout the protocol’s execution. We denote a randomly sampled execution trace as \mathsf{view}\xleftarrow{\$}EXEC^{\Pi}(A,Z,\kappa) , where |\mathsf{view}| represents the number of rounds in the execution trace. Specifically, \mathsf{view} is a random variable that captures the joint perspective of all parties, encompassing their inputs, random coins, and received messages (including those from the random oracle). This joint view uniquely determines the entire execution. Restrictions on the Environment. Constraints on (A,Z) [ 8 ] . The environment Z and the adversary A must respect certain constraints. We say that a p.p.t. pair (A,Z) is (n,\rho,\Delta) -respecting w.r.t. \Pi , iff for every \kappa\in\mathbb{N} , every view in the support of EXEC^{\Pi}(A,Z,\kappa) , the following holds: • Z activates n parties in view; • For any message broadcast by an honest player at any time t in view, any player that is honest at time t+\Delta or later must have received the message. This means that in the case of newly spawned players, it instantly delivers messages that were sent more than \Delta rounds ago. As long as this \Delta constraint is respected, A is allowed to delay or reorder honest players’ messages arbitrarily. • At every round r in view, A controls at most \rho\cdot n parties. Let \Gamma(\cdot,\cdot,\cdot) be a boolean predicate. We say that a p.p.t. pair (A,Z) is \Gamma -compliant w.r.t. protocol \pi iff: (i) (A,Z) is (n,\rho,\Delta) -respecting w.r.t. \pi ; (ii) \Gamma(n,\rho,\Delta)=1 . 2.4 Game Theoretic Model In the game theoretic model, we assume that all parties are rational. Specifically, each party \mathcal{P} employs a strategy S , which is a set of rules and actions that the party makes depending on its input. In other words, S defines the part of the distributed protocol that \mathcal{P} performs. Each party has a well-defined utility U and chooses a strategy S with the goal of maximizing their utility. The literature of game theoretic analyses of blockchain protocols considers various types of utilities [ 1 ] : (i) absolute rewards; (ii) absolute profit, i.e., absolute rewards minus cost; (iii) relative rewards, i.e., the percentage of the party’s reward among all allocated rewards; (iv) relative profit, i.e., relative rewards minus (absolute) cost; (v) deposits and penalties, e.g., using a slashing mechanism; (vi) external rewards, e.g., bribes. A strategy profile \sigma is a vector of all parties’ strategies and it is an \epsilon -Nash equilibrium if no party can increase its utility more than \epsilon by unilaterally changing its strategy (Definition 1 ). Definition 1 ( \epsilon -Nash equilibrium) Let \mathbb{P} be the set of parties, \mathbb{S} the set of available strategies, and \sigma=\langle S_{i},S_{-i}\rangle a strategy profile, where S_{i} is the strategy of \mathcal{P}_{i} and S_{-i} are the strategies of all other parties. Let U_{i}(\sigma) denote the utility of \mathcal{P}_{i} under \sigma . The profile \sigma is an \epsilon -Nash equilibrium with respect to \bar{U}=\langle U_{1},\dots,U_{|\mathbb{P}|}\rangle if \forall\mathcal{P}_{i}\in\mathbb{P}\;\forall S^{\prime}_{i}\in\mathbb{S}:\quad U_{i}(\langle S_{i},S_{-i}\rangle)\geq U_{i}(\langle S^{\prime}_{i},S_{-i}\rangle)-\epsilon. 2.5 Property Definitions As our analysis is based on [ 8 ] and [ 15 ] , we first recall the definitions of chain growth, chain quality, and consistency from there. Next, we revisit the fairness definition of [ 16 ] . Chain Growth Let: \mathsf{min\text{-}chain\text{-}increase}_{t,t^{\prime}}(\mathsf{view})=\min_{i,j}|\mathsf{chain}^{t+t^{\prime}}_{j}(\mathsf{view})|-|\mathsf{chain}^{t}_{i}(\mathsf{view})| \mathsf{max\text{-}chain\text{-}increase}_{t,t^{\prime}}(\mathsf{view})=\max_{i,j}|\mathsf{chain}^{t+t^{\prime}}_{j}(\mathsf{view})|-|\mathsf{chain}^{t}_{i}(\mathsf{view})| where we quantify over nodes i,j such that i is honest at round t and j is honest at round t+t^{\prime} in \mathsf{view} . Let \mathsf{growth}^{t_{0},t1}(\mathsf{view},\Delta,T)=1 iff the following hold: • (consistent length) for all time steps t\leq|\mathsf{view}|-\Delta,t+\Delta\leq t^{\prime}\leq|\mathsf{view}| , for every two players i,j such that in \mathsf{view} i is honest at t and j is honest at t^{\prime} , we have that |\mathsf{chain}^{t^{\prime}}_{j}(\mathsf{view})|\geq|\mathsf{chain}^{t}_{i}(\mathsf{view})| • (chain growth lower bound) for every time step t\leq|\mathsf{view}|-t_{0} , we have \mathsf{min\text{-}chain\text{-}increase}_{t,t_{0}}(\mathsf{view})\geq T . • (chain growth upper bound) for every time step t\leq|\mathsf{view}|-t_{1} , we have \mathsf{max\text{-}chain\text{-}increase}_{t,t_{1}}(\mathsf{view})\leq T . Definition 2 (Chain growth) A blockchain protocol \Pi satisfies (T_{0},g_{0},g_{1}) -chain growth in \Gamma -environments, if for all \Gamma -compliant p.p.t. pair (A,Z) , there exists some negligible function \mathsf{negl} such that for every \kappa\in\mathbb{N} , T\geq T_{0} , t_{0}\geq\frac{T}{g_{0}} and t_{1}\leq\frac{T}{g_{1}} the following holds: \displaystyle Pr[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):growth^{t_{0},t_{1}}(\mathsf{view},\Delta,T)=1] \displaystyle\geq 1-\mathsf{negl}(\kappa) Chain Quality The second desired property is that the number of blocks contributed by the adversary is not too large. Given a \mathsf{chain} , we say that a block B:=\mathsf{chain}[j] is honest w.r.t. \mathsf{view} and prefix \mathsf{chain}[:j^{\prime}] where j^{\prime}\ell , i.e., \mathsf{chain}^{t^{\prime}}_{j}(view) cannot be too much shorter than \mathsf{chain}^{t}_{i}(view) given that t^{\prime}\geq t . Definition 4 (Consistency) A blockchain protocol \Pi satisfies T_{0} -consistency in \Gamma -environments if for all \Gamma -compliant p.p.t. pair (A, Z), there exists some negligible function negl such that for every \kappa\in\mathbb{N} and every T\geq T_{0} the following holds: \displaystyle Pr\big[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):\mathsf{consistent}^{T}(\mathsf{view})=1\big] \displaystyle\geq 1-\mathsf{negl}(\kappa) Fairness The results from [ 15 ] are parameterized by the following quantities: • \alpha:=1-(1-p)^{(1-\rho)n} : the probability that some honest player succeeds in mining a block in a round. • \beta:=\rho{}np : the expected number of blocks an attacker can mine in a round. • \gamma:=\frac{\alpha}{1+\Delta\alpha} : a discounted version of \alpha which takes into account that messages sent by honest parties can be delayed by up to \Delta rounds and this can lead to honest players redoing work; in essence, \gamma corresponds to the effective mining power. Compliant executions for Nakamoto’s blockchain. We now specify the compliance predicate \Gamma^{p}_{\mathsf{nak}} for Nakamoto’s blockchain. We say that \Gamma^{p}_{\mathsf{nak}}=1 iff there is a constant \lambda>1 , such that \alpha(1-2(\Delta+1)\alpha)\geq\lambda\beta where \alpha and \beta are functions of the parameters n,\rho,\Delta and \kappa as defined above. As shown in [ 15 ] , this condition implies the following: Fact 1 If (A,Z) is a \Gamma^{p}_{\mathsf{nak}} -compliant, then np\Delta<1 . Fact 2 If (A,Z) is a \Gamma^{p}_{\mathsf{nak}} -compliant, then \gamma\geq\frac{np}{8} . Subsequently, FruitChains [ 16 ] provided a definition for fairness as follows. Let a player subset selection, S(\mathsf{view},r) , be a function that, given (\mathsf{view},r) , outputs a subset of the players that are honest at round r in \mathsf{view} . S is a \phi -fraction player subset selection if S(\mathsf{view},r) always outputs a set of size \phi n (rounded upwards) where n is the number of players in \mathsf{view} . Given a player subset selection S , a record m is S -compatible w.r.t. \mathsf{view} and prefix \mathsf{chain} if there exists a player j and round r^{\prime} such that j is in S(\mathsf{view},r^{\prime}) , the environment provided m as an input to j at round r^{\prime} , and \mathsf{chain}\prec\mathsf{chain}^{r^{\prime}}_{j}(\mathsf{view}) , where \prec denotes “is a prefix of”. Let \mathsf{quality}^{T,S}(\mathsf{view},\mu)=1 iff for every round r and every player i such that i is honest in round r of \mathsf{view} , we have that among any consecutive sequence of T records \mathsf{chain}^{r}_{i}(\mathsf{view})[j+1:j+T] , the fraction of records that are S -compatible w.r.t. \mathsf{view} and prefix \mathsf{chain}^{r}_{i}(view)[:j] is at least \mu . Definition 5 (Fairness) A blockchain protocol \Pi has (approximate) fairness (T_{0},\delta) in \Gamma -environments, if for all \Gamma -compliant p.p.t. (A,Z) , every positive constant \phi\leq 1-\rho , every \phi -fraction subset selection S , there exists some negligible function \epsilon such that for every \kappa\in\mathbb{N} and every T\geq T_{0} the following holds: \displaystyle Pr[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):\mathsf{quality}^{T,S}(\mathsf{view},(1-\delta)\phi))=1] \displaystyle\geq 1-\epsilon(\kappa) 3 The FairChain Protocol FairChain is a two-level transformation on any proof-of-work longest-chain protocol. At the protocol level , it adds the recording of low-work objects, called workshares , on-chain alongside blocks. At the reward level , it replaces the existing allocation rule with proportional splitting: each height’s reward is distributed among all competing objects at that height in proportion to their intrinsic work. Neither modification touches the host protocol’s fork-choice rule or block-production mechanism; as such, FairChain inherits the host protocol’s security guarantees. FairChain Overview. The intrinsic work of any hash-based object \mathsf{obj} is \textsc{work}(\mathsf{obj})=\lambda-\lfloor\log H(\mathsf{obj})\rfloor, (1) the number of leading zero bits in its hash: the more zero bits, the higher the work. FairChain uses this measure to estimate each miner’s relative power via workshares. A workshare has the same structure as a block and is produced by the same mining loop, but satisfies a lower work threshold. Parties propagate workshares through the network and publish them in blocks, as they do with transactions. Since workshares and blocks are outputs of the same hash query, a miner neither chooses between the two nor knows in advance whether a query yields a workshare, a block, or neither; the hash function models a random oracle. Recording workshares is the only modification FairChain makes to the host protocol. Because workshares affect neither fork choice nor block production, FairChain inherits the host protocol’s security properties unchanged. At a high level, in each round a miner runs the PoW loop; a successful query yields a workshare, a block, or both, depending on the leading zero bits of its hash. The miner broadcasts every new object, and whoever mines the next block records the workshares and uncles it has seen inside that block. Once the relevant blocks are stable, the work recorded for a given height, across its block and the workshares pointing to it, determines how that height’s reward is split among miners ( Section 3.4 ). Workshares thus serve one purpose: they sample mining power between blocks, so that rewards track power closely. The accuracy of this power estimate is not a fixed per-block quantity: it depends jointly on the workshare rate, the block-production rate, and the reward-maturity window. A deployment can improve accuracy by increasing the workshare rate, by extending the maturity window, or both, without requiring all samples to appear in a single block. In the remainder of this section, we describe the protocol’s data objects, its core algorithm, the chain-selection and ledger-extraction mechanisms, the reward allocation rule, and an optimization that removes the on-chain storage overhead. 3.1 Blocks and Workshares A work object in FairChain has the following format: \mathsf{WorkObject}=\langle(d(\mathsf{TX});d(\mathsf{WS});h_{B^{\prime}};h_{\hat{B}}),\textsf{ctr}\rangle where \mathsf{TX} is the transaction list, \mathsf{WS} is the list of work objects (workshares or uncles) published when \mathsf{WorkObject} acts as a block, 3 3 3 An uncle satisfies the block work threshold but is not part of the canonical chain, i.e., it has been forked out. h_{B^{\prime}} and h_{\hat{B}} reference two prior blocks via their hashes, and ctr is the PoW nonce. A full block is the work object together with the explicit lists \mathsf{TX} and \mathsf{WS} . When an object is interpreted as a workshare, d(\mathsf{TX}) and d(\mathsf{WS}) are ignored; those fields are used only by the chain-selection and ledger-extraction mechanisms. Let R denote the recency window: a workshare or uncle is eligible for inclusion only if the block it references is at most R blocks behind the including block. In more detail, the validity rules for blocks and workshares are as follows. In addition, we assume the existence of a transaction validity predicate, which specifies the application logic of the ledger, e.g., preventing double spending. Block validity. B=(\langle(d(\mathsf{TX});d(\mathsf{WS});h_{B^{\prime}};h_{\hat{B}}),\textsf{ctr}\rangle,\mathsf{TX}) is valid w.r.t. a chain C if the following conditions hold: • d(\mathsf{TX}) is the digest of \mathsf{TX} . • h_{B^{\prime}},h_{\hat{B}} are references to C[-1],C[-k] respectively. • Every Workobject (workshare or uncle) in \mathsf{WS} is valid w.r.t. C (see below); • No Workobject is present in C multiple times. • Every transaction in \mathsf{TX} satisfies the protocol’s validity predicate. • \textsc{work}(B)>T_{\text{block}} , where T_{\text{block}} is a protocol parameter that defines the PoW lower bound for a block to be valid. Uncle validity. B=(\langle(d(\mathsf{TX});d(\mathsf{WS});h_{B^{\prime}};h_{\hat{B}}),\textsf{ctr}\rangle,\mathsf{TX}) is a valid uncle w.r.t. chain C , if all of the following hold: • B is included in \mathsf{WS} of exactly one block \overline{B} in C and B\notin C ; • h_{B^{\prime}} is a reference to C^{\prime}[-1] , which in turn is either a valid block in C or a valid uncle w.r.t. C ; • h_{\hat{B}} is a reference to C^{\prime}[-k] , which is a valid block in C ; • Let \overline{C} be the prefix of C that goes up to this block \overline{B} . |C^{\prime}| is between |\overline{C}|-R and |\overline{C}|-1 ; • Following the reference h_{B^{\prime}} to a block B^{\prime} , and then this block’s reference and so on at most k times, gives a block that is part of C ; • \textsc{work}(B)>T_{\text{block}} . Workshare validity. \mathsf{ws}=\langle(d(\mathsf{TX});d(\mathsf{WS});h_{B^{\prime}};h_{\hat{B}}),\textsf{ctr}\rangle is valid w.r.t. chain C if: • \mathsf{ws} is included in \mathsf{WS} of exactly one block \overline{B} in C ; • Let \overline{C} be the prefix of C that goes up to this block \overline{B} . h_{B^{\prime}} is a reference to any valid block or uncle with a height between |\overline{C}|-R and |\overline{C}|-1 ; • \textsc{work}(\mathsf{ws})>T_{\text{ws}} , where T_{\text{ws}} is a protocol parameter that defines the PoW lower bound for a workshare to be valid. Intuitively, T_{\text{ws}} and T_{\text{block}} define the minimum amount of intrinsic work that a workshare or block should have, respectively, and it holds that T_{\text{ws}}\leq T_{\text{block}} . Chain validity. Finally, a chain C is valid w.r.t. a genesis block G (denoted \textsc{Validate}_{G}(C) ) if every block in C is valid and they form a chain that starts from G . 3.2 Main Protocol The main function of FairChain is defined in Algorithm 1 . First, the party is constructed using the Constructor function (Line 4 ). In every round, each party is executed by the environment using the function Execute (this function is due to the round-based nature of our time model). The algorithm maintains a local chain C , which is initialized to the genesis block G , and proceeds as follows. Algorithm 1 The FairChain protocol 1: 2: G\leftarrow\emptyset 3: C\leftarrow[\,] 4: function Constructor ( G^{\prime} ) 5: G\leftarrow G^{\prime} \triangleright Select Genesis Block 6: C\leftarrow[G] \triangleright Add Genesis Block to start of chain 7: round \leftarrow 1 8: function \textsc{Execute}_{d,H} ( 1^{\kappa} ) 9: \mathbb{C}\leftarrow\textsc{re}\-\textsc{ceive}() \triangleright Receive chains from the network 10: C\leftarrow\textsc{MaxValid}(\{C\}\cup\mathbb{C}) \triangleright Apply host protocol’s chain-selection rule 11: \langle\mathsf{TX},\mathsf{WS}\rangle\leftarrow\textsc{input}() 12: \mathbb{B}\leftarrow\emptyset 13: \textsf{ctr}\overset{\$}{\leftarrow}\{0,1\}^{\lambda} 14: for i\leftarrow 1\text{ to }Q do 15: \mathsf{WorkObject}\leftarrow\langle(d(\mathsf{TX});d(\mathsf{WS});H(C[-1]);H(C[-k])),\textsf{ctr}\rangle 16: if \textsc{work}(\mathsf{WorkObject})>T_{\text{ws}} then 17: \mathsf{WS}\leftarrow\mathsf{WS}\,\|\,\mathsf{WorkObject} 18: if \textsc{work}(\mathsf{WorkObject})>T_{\text{block}} then 19: B\leftarrow\langle\mathsf{WorkObject},\mathsf{TX}\rangle 20: \mathbb{B}\leftarrow\mathbb{B}\,\|\,B 21: C\leftarrow C\,\|\,B 22: \textsf{ctr}\leftarrow\textsf{ctr}+1 23: \textsc{Diffuse}(C,\mathsf{WS}\,\|\,\mathbb{B}) 24: round \leftarrow round +1 Chains. The party first receives from the network the set of available chains via the function receive (Line 9 ). Out of all the available chains, including the local chain C , the party adopts the chain selected by the host protocol’s chain-selection rule, denoted MaxValid . Mempool. The party receives the set of transactions in the mempool \mathsf{TX} via the function input (Line 11 ) and attempts to publish them in the newly-mined block. Specifically, the party orders the transactions in \mathsf{TX} in an arbitrary manner in order to form the list \mathsf{TX} ; for ease of notation, we abstract the ordering process outside of the protocol of Algorithm 1 . The list’s digest d(\mathsf{TX}) is included in the new block’s header. Workshares. The party receives from the network workshares \mathsf{WS} , including uncle blocks (Line 11 ), and attempts to publish them in the new block. As opposed to transactions, the order of workshares does not matter, since they are only used for reward allocation (cf. Section 3.4 ). We note that \mathsf{TX} and \mathsf{WS} are both sanitized to contain valid objects w.r.t. the party’s local chain C , so that the transactions and workshares can be published in a new block. For ease of notation we omit this process from Algorithm 1 and assume that \mathsf{TX} and \mathsf{WS} (obtained from input ) are sanitized w.r.t. the local chain C at all rounds. In particular, all workshares fulfill the PoW inequality, there are no duplicate workshares in the chain, and uncle blocks are not part of the chain. Proof-of-Work loop. The main part of the protocol is the PoW loop, during which the party potentially creates workshares and blocks. Specifically, on each round the party can execute Q queries to the hash function. For each query, the work object includes a PoW nonce ctr and, depending on the amount of work that the object has, it may be a valid workshare and/or block. If a workshare is created, then it is immediately inserted into the list \mathsf{WS} . This has the implication that a workshare which is created on some round r may be published on a block that is created on the same round r . Similarly, if a block is created, it is immediately appended to the local chain C . Regardless of whether a workshare or block is created, the party exhausts all available hashing queries at their disposal without interrupting the PoW loop. Therefore, a party that follows the protocol may create multiple workshares and/or blocks on a single round. Finally, the party diffuses to the network their local chain and list of workshares and proceeds to the next round. 3.3 Chain Selection and Ledger Extraction Chain selection follows the host protocol’s MaxValid rule. Ledger extraction ( Algorithm 5 ) is parameterized by the safety parameter k . Given a chain C , the last k blocks are excluded from the ledger extraction process. The remaining blocks in C are parsed sequentially, starting from the genesis block G , and the ledger L is formed by concatenating each transaction in the list \mathsf{TX} of each block. 3.4 Proportional Reward Splitting Mechanism We now specify the reward rule of FairChain . At each block height, PRS distributes a fixed reward among all eligible work objects at that height in proportion to their intrinsic work. This refines Reward Splitting [ 25 , 12 , 3 ] , which also distributes a height’s reward across competing objects but uses a fixed 50 - 50 split regardless of the work behind them. PRS replaces this coarse split with the measured power distribution: a miner contributing 30\% of the work at a height receives 30\% of that height’s reward. 4 4 4 The power distribution is not directly observable; PRS estimates it from workshares, as analyzed in Section 5 . The estimate is recomputed at every height to track fluctuations in mining power as they occur. Eligibility windows. Two parameters control which objects are eligible for rewards at a given height ( Figure 1 ). The recency window R sets the finalization delay: the reward for height h is settled at height h+R , and only work objects published within that window are counted. The fork eligibility window k limits which forks contribute: an object is eligible only if the block it references lies at most k blocks into a fork, excluding objects that build on deeply invalid chains. In our analysis, k is set to the common-prefix (consistency) parameter T_{0} of the host protocol (cf. Definition 8 ). Reward rule. At height h+R , each eligible work object at height h receives a fraction of the height’s reward equal to its intrinsic work divided by the total intrinsic work of all eligible objects at that height. The height of a workshare or uncle is the height of the block it references via h_{B^{\prime}} , not the block in which it is published. Maturity delays of this kind are standard: Bitcoin requires 100 blocks before a coinbase transaction can be spent. 5 5 5 https://learnmeabitcoin.com/technical/mining/coinbase-transaction/#coinbase-maturity \displaystyle h_{i}+R \displaystyle h_{i} window \displaystyle k … ws fruit … uncle fruit Figure 1: Uncles can be referenced up to R blocks away. Objects pointing to blocks more than k blocks into a fork are ineligible. At height h_{i}+R , the reward at height h_{i} is distributed proportionally to the intrinsic work of the eligible objects at h_{i} . 3.5 Removing on-chain storage overhead FairChain does not modify the MaxValid fork-choice rule of the underlying proof-of-work chain, so work objects play no role in chain selection, only in reward allocation. Instead of recording them on-chain within blocks, it suffices that miners share them over the P2P network. Miners will verify reward (coinbase) transactions based on the work objects sent along with the block. Once the rewards for height h_{i} are finalized at height h_{i}+R (cf. Figure 1 ), all work objects older than R+k blocks behind the current tip can be safely discarded. Bootstrapping nodes need only download the longest chain; they can skip work object verification entirely. Thus, the storage overhead of FairChain is bounded by the work objects of the last R+k blocks. This storage improvement comes with a small tradeoff: a bootstrapping node cannot independently recompute past reward allocations. However, under the honest-majority assumption, honest miners validate reward allocations before extending a block, so a bootstrapping node can still infer their historical validity by following the heaviest PoW chain. 4 Theoretical Analysis Our analysis closely follows that of FruitChains [ 16 ] . The protocol difference mainly affects the analysis of workshare freshness. In the rest of this section, we prove workobject freshness, consistency, growth, and fairness, ultimately leading to incentive compatibility. We denote the probability that any player mines a block in a round as p , and similarly the probability that a player mines a workshare in a round as p_{f} , such that q=\frac{p_{f}}{p} . 4.1 Main Theorem Theorem 4.1 is the main theoretical result of our work, which shows that the workshare-based protocol guarantees the useful properties that we aim it to achieve, namely consistency, chain growth, and fairness. Theorem 4.1 (Security of FairChain ) For any constant 0<\delta<1 , and any p,p_{f} , let R=16 , k_{f}=2qRk , and T_{0}=5\frac{k_{f}}{\delta} . Then, in \Gamma_{\textsf{FairChain}}^{p,p_{f},R} -environments, the Workshare protocol denoted \Pi_{\textsf{FairChain}}(p,p_{f},R) satisfies (i) k_{f} - consistency , (ii) chain growth rate (T_{0},g_{0},g_{1}) with g_{0}=(1-\delta)(1-\rho)np_{f} and g_{1}=(1+\delta)np_{f} , and (iii) fairness (T_{0},\delta) . 4.2 Workobject Freshness A key property is for any Workobject (or fruit to follow [ 16 ] ) mined by an honest player to stay sufficiently fresh to be incorporated. In this section, we prove freshness. Note that we achieve a slightly better freshness parameter ( R=16 ) compared to FruitChains [ 16 ] ( R=17 ). Let \mathsf{WOfreshness}(\mathsf{view},w,k)=1 iff for every honest player i and for every round r<|view|-w , if i mines a Workobject at r in view, then for every honest player j there exists an index pos , such that the Workobject is at pos in the record chain (w.r.t. Nakamoto’s protocol) of j at every round r^{\prime}\geq r+w , and pos is at least k blocks away from the end of the chain. Let wait=2\Delta+\frac{2k}{\gamma} Lemma 1 Let R=16 . For any p , p_{f} , for any \Gamma_{\textsf{FairChain}}^{p,p_{f},R} -compliant (A,Z) , there exists a negligible function \epsilon such that for any \kappa\in\mathbb{N} , Pr\big[\mathsf{view}\leftarrow EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa): \mathsf{WOfreshness}(\mathsf{view},wait,k)=1\big]\geq 1-\epsilon(\kappa) Proof Disregard the blockchain consistency, liveness, and chain growth failure events, which only happen with negligible probability. Let wait=wait(k,n,\rho,\Delta) . • By blockchain consistency , at any point in the execution, whenever an honest player mines a Workobject (i.e., a block, an uncle block or a workshare) f , the block pointed to by that Workobject is at some fixed position pos on the blockchain of every honest player, now and at every time in the future. • Note that if \textsc{work}(\text{Workobject})>T_{\text{block}} , it is not clear at the time of mining whether it will be a block or an uncle block. • Honest players try to mine Workobjects that point to the last block in their chain. • Let \ell denote the length of the chain of the player that mines f ; by definition pos=\ell • By the description of the protocol, if the Workobject f is mined at round r^{\prime} , it gets seen by all honest players by round r^{\prime}+\Delta ; additionally, when this happens, all honest players attempt to add f to their chain as long as it remains recent (w.r.t. all honest players). • By liveness , the Workobject gets thus referenced by a block that is in the record chain of all honest players at some position pos that is at least k blocks away from the end of the chain by round r^{\prime}+\Delta+(1+\delta)\frac{k}{\gamma}\leq r^{\prime}+wait-\Delta • By the upper bound on chain growth, at most (1+\delta)np(\Delta+\frac{2k}{\gamma}) blocks are added in time wait-\Delta . Thus, by round r^{\prime}+wait-\Delta , no honest player has ever had a chain of length \ell^{\prime} , such that \ell^{\prime}>\ell+(1+\delta)np(\Delta+\frac{2k}{\gamma}) • Thus, by round r^{\prime}+wait-\Delta , for every such honest player’s chain length \ell^{\prime} , we have pos=\ell\geq\ell^{\prime}-(1+\delta)np(\Delta+\frac{2k}{\gamma}) • By our compliance assumption and by Fact 4 and Fact 5 , we have that \gamma\geq\frac{np}{8} and np\Delta<1 , thus pos>\ell^{\prime}-(1+\delta)-(1+\delta)16k\geq\ell^{\prime}-16k=\ell^{\prime}-Rk • By consistency , all honest players agree that f is found at position pos in their blockchain at any point after r^{\prime}+wait-\Delta ; additionally, by the consistent length property all honest players agree that position pos is at least k from the end of the chain by r^{\prime}+wait-\Delta+\Delta=r^{\prime}+wait . • It remains to show that the block B that is referenced by f is either a valid block of the chain C of honest users or a valid uncle, as this is the condition for Workobjects to be rewarded. Note that honest parties will reference the last block they see in their chain, which is valid, but not necessarily stable. Should it happen that the block does not end up in C , it thus has to become an uncle. Suppose there exists another block B^{\prime} that is competing with B . In any block that is building on top of B^{\prime} , B is treated as a Workobject (uncle). We have already proven that Workobjects get incorporated into the chain of every honest player; thus, B will be incorporated into the chain of every honest player. We also observe the following fact about wait , which says that the expected number of Workobject s mined by all players during wait+2 is upper bounded by k_{f} . Fact 3 For any p , p_{f} , any \Gamma_{\textsf{FairChain}}^{p,p_{f},R} -compliant (A,Z) , (wait+2)\cdot np_{f}\leq k_{f} Proof Note that by Fact 4 and Fact 5 , we have that \gamma>\frac{np}{8} and np\Delta<1 , thus (wait+2)\cdot np_{f}=(2\Delta+2\frac{k}{\gamma}+2)\cdot{}qpn\leq{}2q+2k\cdot{}8q+2\leq{}2qRk=k_{f} 4.3 Some Simplifying Assumptions Towards proving our main theorem, we state some simplifying assumptions that can be made without loss of generality. These assumptions (which all follow from properties of the random oracle H ) will prove helpful in our subsequent analysis. • WLOG1: We may without loss of generality assume that honest players never query the RO on the same input. More precisely, we analyze an experiment where if some honest player wants to query it on an “old” input, it re-samples the nonce until the input is “new”; since the nonce is selected from \{0,1\}^{\kappa} , this “re-sampling” experiment is identical to the real one except with negligible probability, thus we can WLOG analyze it. • WLOG2: We may, without loss of generality, assume that any Workobject that points to a block b which was first mined at time t has been mined after t . Additionally, any Workobject that points to a block that comes after b in a valid chain must have been mined after t . (If not, we can predict the outcome of the random oracle H on some input before having queried H , which is a contradiction. We omit the standard details.) • WLOG3: We may assume without loss of generality that all Workobject s mined by honest players are “new” (i.e., different from all valid Workobject s previously seen by honest players); this follows from WLOG1 and the fact that the probability of seeing a collision in the random oracle is negligible (by a simple union bound over the number of random oracle queries). • WLOG4: We may assume without loss of generality that any valid Workobject which appears in some honest player’s chain at round r was mined before r ; this follows from the unpredictability of the random oracle (and a simple union bound over the number of random oracle queries). • WLOG5: We may assume without loss of generality that there are no “blockchain collisions”, namely, there are no two different valid sequences of blocks which end with the same block. We now turn to proving the three security properties. 4.4 Workobject Consistency Disregard chain growth, consistency, and chain quality failure events–they happen with negligible probability. Consider some view \mathsf{view} in the support of EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa) , rounds r,r^{\prime} , s.t. r^{\prime}\geq r , and players i,j that are honest respectively at r,r^{\prime} in view. By consistency , the chains of i,j at r,r^{\prime} agree except for potentially the last k blocks in the chain of i . Let C=b_{0},\dots,b_{|C|} denote those blocks on which they agree and let b_{|C|+1},\dots denote the maximum k blocks in the chain of i at r which are not in the chain of j at r^{\prime} . We now bound the number of Workobjects that can be referenced in these remaining (maximum k ) inconsistent blocks. • By the “recency condition” of valid Workobject s, any valid Workobject in the chain of i at r which is after C must point to a block b_{j^{\prime}} such that j^{\prime}>|C|-Rk . • By the chain quality condition , there exists some j^{\prime\prime} s.t. |C|-R_{k}-k\leq j^{\prime\prime}\leq|C|-R_{k} and b_{j^{\prime\prime}} was mined by an honest player. Let r^{\prime}_{0} denote the round when this block was mined. • Note that r^{\prime}_{0} was mined by an honest player holding a chain of length j^{\prime\prime}\geq|C|-R_{k}-k ; additionally, at r , i is honest, holding a chain of length at most |C|+k (recall that —C— contains the blocks on which i and j agree, and by consistency, all but the last k blocks in the chain of i must be in the chain of j ). Thus, by the chain growth upper bound , at most \mu=(1+\delta)\frac{2k+Rk}{np} rounds could thus have elapsed between r^{\prime}_{0} and r. • By WLOG2, any Workobject which gets added after C must have been mined after r^{\prime}_{0} . By WLOG4, any such Workobject that is part of the chain of i by r was mined before r . • We thus conclude by the Chernoff bound that for every sufficiently small \delta^{\prime} except with probability e^{=\Omega(np_{f}\cdot\frac{k(R+2}{np})}=e^{-\Omega(q(R+2)k}) , there were at most (1+\delta^{\prime})^{2}\cdot{}np_{f}\cdot{}\frac{k(R+2)}{np}=(1+\delta^{\prime})^{2}q(R+2)k<2qRk=k_{f} “inconsistent” Workobject s in the chain of i at r 4.5 Workobject Growth Consistent length. The consistent length property follows directly from the consistent length property of the underlying blockchain. Lower bound. Consider any r,t and players i,j that are honest respectively at round r and r+t . Consider the t rounds starting from round r . • By the Workobject freshness condition, every Workobject that is mined by some honest party by round r+t-wait gets incorporated into (and remains in) the chain of player j by r+t . • By the Chernoff bound, in the t-wait rounds from r to r+t-wait , except with probability e^{-\Omega((t-wait)\alpha_{f})} , the honest parties mine at least (1-\delta^{\prime})(t-wait)\alpha_{f} Workobject s (where \delta^{\prime} is some arbitrarily small constant), which are all included in the chain of j at r+t . Additionally, by WLOG3 they are all “new” (i.e., not included in the chains of i at r ) and different. • Finally, by Workobject consistency (proved in Section 0.C.3 ), we have that all but potentially k_{f} of the Workobject s in the chain of i at r are still in the chain of j at r+t . • We conclude that, except with probability e^{-\Omega((t-wait)\alpha_{f})} the chain of j at r+t contains at least (1-\delta^{\prime})(t-wait)\alpha_{f}-k_{f} more Workobject s than the chain of j at r . By Fact 6 , wait\cdot\alpha_{f}=wait\cdot(1-\rho)np_{f}\leq(1-\rho)k_{f}\leq k_{f} ; thus, we have at least (1-\delta)(t-wait)\alpha_{f}-k_{f}\geq(1-\delta)\alpha_{f}{}t-2k_{f} (2) new Workobject . We conclude by noting that this implies that a Workobject growth lowerbound of g_{0}=\frac{1}{1+\delta}\alpha_{f}\geq(1-\delta)\alpha_{f} in the desired regime: Consider any T\geq\frac{5k_{f}}{\delta} and any t\geq\frac{T}{g_{0}}=\frac{T}{\frac{\alpha_{f}}{1+\delta}} As shown above (see Equation 4 ), except with a probability of e^{-\Omega((t-wait)\alpha_{f})} the chain must have grown by at least T(1+\delta)(1-\delta^{\prime})-2k_{f}=T(1+\frac{\delta}{2})(1-\delta^{\prime})+T\frac{\delta}{2}(1-\delta^{\prime})-2k_{f} For a sufficiently small \delta^{\prime} , the first term is greater than T , and the second term is greater than 2k_{f} , and thus the chain must have grown by at least T . Finally note that by Equation 4 e^{-\Omega((t-wait)\alpha_{f})}=e^{-\Omega(t\alpha_{f}-k_{f})}=e^{-\Omega(T-k_{f})}=e^{-\Omega(5k_{f}-k_{f})}=e^{-\Omega(k)} Thus, the chain growth is guaranteed except with negligible probability. Upper bound. Disregard the chain growth, consistency, and chain quality failure events–they happen with negligible probability. Consider some view \mathsf{view} in the support of EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa) , rounds r,r^{\prime} , s.t. r^{\prime}=r+t , and players i,j that are honest respectively at r,r^{\prime} in view. By consistency , the chains of i,j at r,r^{\prime} agree except for potentially the last k blocks in the chain of i . Let C=b_{0},\dots,b_{|C|} denote those blocks on which they agree and let b_{|C|+1},\dots denote the blocks in the chain of j at r^{\prime} which are not in the chain of i at r (there may be more than k such blocks since we are looking at the chain of j at a later time r^{\prime} ); We now upper bound the number of Workobject s in the new blocks in the chain of j which come after C , similarly to the Workobject consistency proof (the main difference is that we now consider the chain of j as opposed to the chain of i ). The details follow: • By the “recency condition” of valid Workobject , any valid Workobject in the chain of j at r^{\prime} which is after C must point back to a block b_{j^{\prime}} , such that j^{\prime}>|C|-Rk . • By the chain quality condition , there exists some j^{\prime\prime} s.t. |C|-Rk-k\leq{}j^{\prime\prime}\leq|C|-Rk and b_{j^{\prime\prime}} was mined by an honest player. Let r^{\prime}_{0} denote the round when this block was mined. • Note that at r^{\prime}_{0},b_{j^{\prime\prime}} was mined by an honest player holding a chain of length j^{\prime\prime}\geq|C|-Rk-k ; additionally, at r , i is honest, holding a chain of length at most |C|+k (recall that |C| contains the blocks on which i and j agree, and by consistency, all but the last k blocks in the chain of i must be in the chain of j ). Thus, by chain growth upper bound , for any arbitrarily small \delta^{\prime} at most \mu=(1+\delta^{\prime})\frac{2k+Rk}{np} rounds could thus have elapsed between r^{\prime}_{0} and r . • By WLOG2, any Workobject which gets added after C must have been mined after r^{\prime}_{0} . By WLOG4, any such Workobject that is part of the chain of j by r^{\prime} was mined before r^{\prime} . • We thus conclude by the Chernoff bound that except with a probability of e^{-\Omega(np_{f}\cdot\frac{k(R+2)}{np})}=e^{-\Omega(q(R+2)k)} , there were at most \begin{split}(1+\delta^{\prime})^{2}\cdot{}np_{f}\cdot\Big(\frac{k(R+2)}{np}+t\Big)=\\ (1+\delta^{\prime})^{2}(q(R+2)k+np_{f}t)\leq k_{f}+(1+\delta^{\prime})^{2}np_{f}t\end{split} (3) “new” Workobject s in the chain of j at r^{\prime} . We conclude by noting that this implies a Workobject growth upper bound of g_{1}=(1+\delta)np_{f} in the desired regime: Consider any T\geq\frac{5k_{f}}{\delta} and any t=\frac{T}{g_{1}}=\frac{T(1+\delta)}{np_{f}} As shown above (see Equation 5 ), during this time t , except with negligible probability, the chain must have grown by at most k_{f}+(1+\delta^{\prime})^{2}T(1-\delta)\leq T\delta/5+(1+\delta^{\prime})^{2}T/(1+\delta) For any 0<\delta<1 and \delta^{\prime}=0.1\delta , the above expression is upper bounded by T . 4.6 Workobject Fairness Disregard the chain growth, chain quality, Workobject freshness, and Workobject growth failure events, which happen with negligible probability (see above). Consider some \phi –fraction player subset selection S , some view \mathsf{view} in the support of EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa) , some round r and some player i that is honest in round r of \mathsf{view} . Let C=b_{0},\dots,b_{|C|} be the blocks in the view of i at r , let f_{0},\dots,f_{\ell} be the Workobject s contained in them, and let m_{0},\dots,m_{\ell} be the records contained in the Workobject s; let f_{j},\dots,f_{j+T} be the T consecutive Workobject s for some j , where T\geq\frac{5k_{f}}{\delta} . Let r_{0} be the round when the block in the view of i at r containing f_{j+k_{f}} was first added to some honest player j_{0} ’s chain; let r_{1} be the round when the block (again in the view of i at r ) containing f_{j+T} was first added to some honest player j_{1} ’s chain, and let t=r_{1}-r_{0}-2 be the number of rounds from r_{0}+1 to r_{1}-1 . We lower bound the number of S -compatible (honest) Workobject s in the sequence, similar to the proof of Workobject growth lower bound : • By the Workobject freshness condition, every Workobject mined by some honest player between (r_{0}+1) and (r_{1}-1)-wait will be in the chain of j_{1} at some position pos that is at least k positions from the end of the chain, before the beginning of round r_{1} and will remain so. • By the Chernoff bound, in the t-wait rounds from r_{0}+1 to (r_{1}-1)-wait , except with probability e^{-\Omega((t-wait)\phi{}np_{f})} , the honest parties in S mine at least (1-\delta^{\prime})(t-wait)\phi{}np_{f} Workobject s (where \delta^{\prime} is some arbitrarily small constant), which thus are all included in the chain of j_{1} by r_{1}-1 . • Since Workobject s are ordered by the block containing them, and since in round r_{1} a new block is added which contains f_{j+T} , it follows from blockchain consistency that all these Workobject s contained in the sequence f_{1},\dots,f_{j+T} (recall that all these Workobject s are found in blocks that are at least k positions from the end of the chain, so by consistency, those blocks cannot change and thus were not added in round r_{1} and consequently must come before the block containing f_{j+T} ). • By WLOG3 (cf. Section 0.C.2 ), these Workobject s are also all “new” (i.e., not included in the chains of j_{0} at r_{0} ) and different. Since in round r_{0} , the block containing f_{j+k_{f}} was added to the chain of j_{0} , and since by WLOG5, the chain of j_{0} at r_{0} up until (and including) the block which contains f_{j+k_{f}} is a prefix of C , all these Workobject s must in fact be contained in the sequence f_{j+k_{f}},\dots,f_{j+T} . • Finally, by Workobject consistency, at r_{0} all honest players’ Workobject chains contain f_{1},\dots,f_{j} (since recall that some player added f_{j+k_{f}} at r_{0} ). Thus, all these Workobject s are S -compatible w.r.t. the prefix f_{1},\dots,f_{j-1} before the T segment we are considering. We proceed to show that t is sufficiently large. Recall that j_{0} is honest at r_{0} and j_{1} is honest at r_{1} . We know that at r_{1} , the Workobject chain contains at least f_{j+T} Workobject s. Additionally, at r_{0} the Workobject f_{j+k_{f}} is added for the first time, so by Workobject consistency, at most j+2k_{f} Workobject s could have been in the chain of i at this point (since a Workobject at position j+k_{f} is modified). Thus, the Workobject chain must have grown by at least T-2k_{f} from r_{0} to r_{1} . By the upper bound on Workobject growth we have that: T-2k_{f}\leq k_{f}+(1-\delta^{\prime})^{2}np_{f}(t+2) . Thus: t\geq\frac{1}{(1+\delta^{\prime})^{2}np_{f}}(T-3k_{f})-2 . We conclude that (except with negligible probability) the number of Workobject s in the sequence is at least: \displaystyle(1-\delta^{\prime})\phi{}np_{f}\Big(\frac{1}{(1+\delta^{\prime})^{2}np_{f}}(T-3k_{f})-2-wait\Big)= \displaystyle(1-\delta^{\prime})\phi\Big(\frac{1}{(1+\delta^{\prime})^{2}}(T-3k_{f})-np_{f}(wait+2)\Big)\geq \displaystyle(1-\delta^{\prime})\phi\Big(\frac{1}{(1+\delta^{\prime})^{2}}(T-3k_{f})-k_{f}\Big)\geq \displaystyle(1-\delta^{\prime})\phi\Big(\frac{1}{(1+\delta^{\prime})^{2}}(T-4.5k_{f})\Big)\geq\phi(T-5k_{f}) where the first inequality follows from Fact 6 , and the second and third by taking a sufficiently small \delta^{\prime} . Since T\geq\frac{5k_{f}}{\delta} , we have that T-5k_{f}\geq(1-\delta)T , thus the number of Workobject s in the sequence is at least: (1-\delta)\phi{}T . 4.7 Incentive Compatibility Our final theoretical result is game-theoretic and concerns utility-maximizing participants. Any secure blockchain protocol that satisfies \delta -approximate fairness (where \delta<0.3 ) w.r.t T(\kappa) length windows can be used as the ledger underlying a cryptocurrency system while ensuring 3\delta -incentive compatibility if players (i.e., miners) only care about how much money they receive. We say that honest mining is a \rho -coalition-safe \epsilon -Nash equilibrium if, with overwhelming probability, no \rho^{\prime}<\rho fraction coalition can gain more than a multiplicative factor (1+\epsilon) in utility, no matter what transactions are being processed; formally, consider some environment providing transactions into the system. We restrict to a setting where the total rewards and transaction fees during the run of the system are some fixed constant V . Fairness implies that no matter what deviation the coalition performs, with overwhelming probability, the fraction of adversarial blocks in any T(\kappa) -length window of the chain is upper bounded by (1+\delta)\rho and thus the total amount of compensation received by the attacker is bounded by (1+\delta)\rho\cdot V ; in contrast, by fairness, if the coalition had been following the honest protocol, they are guaranteed to receive at least (1-\delta)\rho\cdot V ; thus, the multiplicative increase in utility is: \frac{1+\delta}{1-\delta}\leq 1+3\delta when \delta<0.3 . 5 Evaluation We now compare the Proportional Reward Splitting (PRS) mechanism to other reward mechanisms under realistic parameters. In order to perform the comparison, we utilized the Markov Decision Process (MDP) implementation of [ 25 ] . MDPs are fitting tools in our case since we want to evaluate the optimal strategies w.r.t. a specific utility. Therefore, when parameterizing our MDPs with realistic values, e.g., in terms of block finality, we can identify the optimal strategy that utility-maximizing rational parties would opt for. The model does not require knowledge of the identities of parties, or which parties are adversarial, but only assumes that the adversary A holds a certain amount of power. In practice, a protocol’s designer could use our analysis to get a lower bound on their protocol’s performance, by pinpointing the advantage of the strongest adversary that their protocol can tolerate. Next, we first outline the construction of the MDP and then compare PRS with other reward mechanisms under three metrics, namely incentive compatibility, subversion gain, and censorship susceptibility. We then evaluate how different values of the PRS’s parameters, namely the workshare and fork eligibility windows, affect its performance. Finally, we analyze the accuracy of estimating the adversarial and honest parties’ power via workshares and outline the tradeoff between sampling accuracy and storage overhead. 5.1 Description of Markov Decision Process The MDP implementation of PRS is a direct adaptation of the vanilla Reward Splitting (RS) MDP. Here we give a brief description of the MDP and refer to [ 25 ] for more details. Our implementation is available at [ 4 ] . We note that our evaluation is not a Monte Carlo simulation with independent runs. For each parameter point, we construct the corresponding finite MDP and solve for the optimal adversarial policy under the selected reward function. Therefore, the reported values correspond to expected long-run rewards induced by the optimal policy, rather than empirical means over repeated executions. The state of the MDP is a tuple of four elements \langle l_{a},l_{c},\text{fork},\text{history}\rangle : • l_{a} denotes the length of the (private) adversarial chain; • l_{c} denotes the length of the honest (public) chain; • fork takes three values: active if there is a tie, i.e., honest miners are split between two chains; cLast if the latest block is honest; aLast if the latest block is adversarial. • history is a bitstring as follows: (i) its length represents the number of consecutive attacker blocks in the common (main) chain; (ii) each position corresponds to a height of the main chain, starting from the last block (the tip of the chain); (iii) a 0 bit denotes that no competing honest block exists for the corresponding height, whereas 1 means that an honest block for that height exists. State transitions occur via the following actions: • Adopt : A adopts the public chain. • Wait : A keeps mining privately and publishes no blocks. • Match : A publishes a chain of private blocks equal to the length of the public chain, causing a tie; this is feasible when l_{a}\geq l_{c} and \text{fork}=\text{cLast} . • Override k : A publishes a chain of private blocks which is k blocks longer than the public chain. Finally, the reward allocation is the point of difference between PRS and RS. In RS, when choosing Adopt the honest miners and A each receive half of the rewards for heights where both honest and adversarial blocks exist. Instead, in PRS the rewards are split proportionally to each side’s mining power; for instance, if the honest miners (are set to) have 70 % of mining power, they receive 70 % of the rewards for these heights, instead of 50 % as in RS. 6 6 6 In practice it is impossible to know the exact power distribution between honest parties and the adversary. Instead, an approximation is made using workshares. The accuracy of this approximation is explored in Section 5.4 . For the heights where only honest blocks exist, the honest miners get the full reward. Additionally, the adversary receives the full reward for heights where honest objects (blocks and/or workshares) are “pushed out” of the history, i.e., the adversary creates enough consecutive blocks to censor their inclusion. 5.2 Comparison of Reward Mechanisms We first explore the metrics established in [ 25 ] , namely: (i) incentive compatibility; (ii) subversion gain; (iii) censorship susceptibility. For each metric, we compare PRS with Bitcoin, FruitChains, and vanilla RS. In all evaluations, we used the same parameters for the eligibility windows. The first window concerns object eligibility (i.e., the recency window), that is the number of block heights within which an object should be published in order to be eligible for rewards. This window was set to R=6 . The second window concerns fork eligibility, that is the depth of a fork up to which objects (that point to blocks of that depth) are eligible for rewards. This window was set to k=6 . The parameter \gamma , which indicates the percentage of honest miners that adopt the adversarial forks, is set to 0.5 for Bitcoin, RS, and PRS, and 0 and 1 for FruitChains. 7 7 7 For FruitChains we use both 0 and 1 because the FruitChains MDP implementation of [ 25 ] did not enable using 0.5 due to complexity issues. In essence, when two chains of the same height are available, \gamma=0.5 implies that honest miners choose between competing chains of equal height uniformly at random. Following the baseline configuration of [ 25 ] , we set the fruit-to-block ratio to 1. While higher fruit rates improve the incentive compatibility of FruitChains, at the cost of increased bandwidth, [ 25 ] observes only small improvements for higher ratios and finds RS to outperform FruitChains in its comparison. Incentive Compatibility. Figure 2: Incentive compatibility for various reward mechanisms. The eligibility window for fruits (in FruitChains) and objects (in Proportional Reward Splitting) is set to R=6 . The fork eligibility window for FruitChains, Reward Splitting, and Proportional Reward Splitting is set to k=6 . Larger values indicate worse performance. The first metric of comparison is incentive compatibility (IC). Briefly, IC expresses the percentage of rewards that the adversary gains compared to its fair share, that is, its relative mining power. Figure 2 depicts the IC for the reward mechanisms under question. In essence, values above the line x=y indicate that the adversary gains disproportionately more rewards, compared to its mining power, so larger values indicate worse IC performance. PRS outperforms all other mechanisms on IC. For adversarial power up to 25\% , all mechanisms except FruitChains are optimal. RS and PRS both remain optimal through 35\% ; beyond that, PRS strictly outperforms RS. Subversion Gain. Figure 3: Comparison of subversion gain for various reward mechanisms. The eligibility window for fruits (in FruitChains) and objects (in Proportional Reward Splitting) is set to R=6 . The fork eligibility window for FruitChains, Reward Splitting, and Proportional Reward Splitting is set to k=6 . Larger values indicate worse performance. Subversion gain indicates the profitability of double spending attacks. In particular, the profit from a double-spending attack is time-averaged and set to 3 times the block reward. In other words, if the adversary manages to orphan k blocks during the attack, it is granted 3\cdot k rewards. The confirmation time is set to 6 blocks, so the attack is successful if the adversary reverts 6 blocks in order to successfully double-spend the assets. If the attack is unsuccessful, the adversary gets no rewards, but also incurs no penalty. Figure 3 depicts the comparison of the reward mechanisms w.r.t. subversion gain. For the most part, PRS is again the better option. In particular, up to 30 % all mechanisms except FruitChains perform optimally, i.e., the adversary has zero gain. For the range of adversarial power between 30 % and 38 % PRS is the best option, whereas between 38 % and 42 % it is in effect equally good to Bitcoin. Above 42 %, FruitChains with \gamma=0 performs better, which is a result of the particularly favorable setting (compared to \gamma=0.5 for the other mechanisms); instead, under \gamma=1 , FruitChains is strictly worse than all others for all adversarial powers. In summary, PRS is optimal w.r.t. subversion gain and, in some cases, it is strictly better than all other options. Censorship Susceptibility. Figure 4: Comparison of censorship susceptibility for various reward mechanisms. The eligibility window for fruits (in FruitChains) and objects (in Proportional Reward Splitting) is set to R=6 . The fork eligibility window for FruitChains, Reward Splitting, and Proportional Reward Splitting is set to k=6 . Larger values indicate worse performance. Censorship susceptibility indicates the maximum fraction of income loss that the adversary can incur on honest miners under the threat of a censorship attack. Specifically, the adversary’s reward corresponds to the honest miners’ loss in the form of orphaned blocks. Figure 4 depicts the results for censorship susceptibility. These are consistent with [ 25 ] , wherein FruitChains outperforms the other mechanisms for smaller adversaries but becomes relatively worse for larger values. Interestingly, PRS strictly outperforms vanilla RS for all adversarial powers. As a result, FruitChains is the best option only for adversarial power up to 25 %, after which point PRS is the best option. Notably, even for smaller values of adversarial power, the difference between PRS and FruitChains is less than 2 %. 5.3 Comparison of Eligibility Parameters We now evaluate how the different eligibility parameters affect the performance of the reward mechanisms. In particular, we will compare the two types of reward splitting w.r.t. the fork and the workshare eligibility windows. The metric of comparison is incentive compatibility, since all metrics are affected in the same manner when changing the parameters. As before, we set \gamma to be 0.5 . Workshare Eligibility Window. The first parameter is the workshare eligibility window R . This is the distance between the block that a workshare references and the block within which it gets published. Intuitively, larger window values require the adversary to censor the chain for longer periods of time, in order to force an honest workshare to become ineligible, thus making the attack harder. However, they also incur a delay on the finalization of objects and, consequently, the allocation of rewards. Figure 5 depicts how the two reward splitting mechanisms perform for three workshare eligibility window values, R\in\{3,6,9\} . Evidently, Proportional Reward Splitting outperforms vanilla Reward Splitting in all cases. As expected, larger values of R result in better performance, that is, lower adversarial rewards. Consequently, PRS is optimal for larger values of adversarial power; when R=3 , PRS is optimal for adversarial power up to 33 %, whereas for R=9 this goes up to 38 %. Figure 5: Incentive compatibility w.r.t. the workshare eligibility window between Reward Splitting and Proportional Reward Splitting. The fork window for objects is set to k=6 . Larger values indicate worse performance. Fork Eligibility Window. The second parameter is the fork eligibility window k . This window sets the depth of a fork up to which objects are eligible for rewards. Specifically, if k=3 , then objects that point to a block in a fork are eligible for rewards only if this block is among the first 3 of the fork. Note that the height of the workshare, which is considered for the workshare eligibility window, is computed as the height of the referenced block. For example, if a workshare points to the second block of a fork which occurred at height 100 , then the workshare’s height is 102 and, in order to be eligible for rewards, it should be published in a (main chain) block up to height 102+R . Figure 6 depicts the effect of the fork eligibility window on incentive compatibility. Evidently, lower values of k result in better performance, i.e., lower adversarial rewards. One explanation for this could be that lower values of k penalize forking more, so the adversary is incentivized to abandon forks more often, hence its rewards get closer to its fair share. Interestingly, we observe that PRS outperforms RS even for different values of k . Specifically, PRS under k=6 performs better (for the most part) than RS under k=1 . Figure 6: Incentive compatibility for various values of the fork window between Reward Splitting and Proportional Reward Splitting. The eligibility window for objects is set to R=6 . Larger values indicate worse performance. 5.4 Sampling Accuracy So far, our evaluation of the proportional reward splitting mechanism assumes a perfect knowledge of the distribution of power between the honest parties and the adversary. In practice, this is not possible to achieve for proof-of-work (PoW) ledgers, as each party’s proportional power is not visible to anyone, not even to the party itself. Although a party knows its absolute power, they do not know the exact amount of power of other parties. Instead, the distribution of power can be inferred from observed events, specifically block creations. Since the probability that each party creates a block on each round is proportional to their power and each such event is independent, a large enough sample of blocks enables inferring the power distribution. A pertinent question is how many samples are needed to make an accurate enough estimation, with a low margin of error. In our setting, the samples correspond to workshares and blocks. Therefore, the question of interest is how many workshares should be published per height, such that each block’s rewards are distributed proportionally to each side’s power, accurately and in most cases (low margin of error). To estimate the number of workshares needed, we model the generation of workshares as a series of independent Bernoulli trials. Let X_{i}\in\{0,1\} be the i-th sample of random variable X , where 0 corresponds to an adversarial workshare creation and 1 corresponds to honest workshare. The probability of 1 for each X_{i} is p_{h} , so \{X_{i}\}_{i\in[n]} is independent and identically distributed to a Bernoulli trial \textsf{Bern}(p_{h}) . Let X=\sum_{i=1}^{n}X_{i} be the random variable that represents the sum of the observed values, i.e., the number of honest workshares. It holds that E[X]=n\cdot p_{h} , where n is the number of samples (i.e., Bernoulli trials) and p_{h} is the probability of creating an honest workshare. By the Chernoff bound: \text{Pr}\left[X\leq(1-\delta)\cdot E[X]\right]<\epsilon=e^{-\frac{\delta^{2}\cdot n\cdot p_{h}}{2}} . where: (i) \delta denotes the acceptable deviation from the completely accurate (expected) value; (ii) \epsilon denotes the error bound of the observation, i.e., the probability that the observed value is less accurate than \delta . By solving for n we find, for a given honest-power fraction p_{h} , the minimum number of workshares needed to get an accurate enough observation with low error probability: n=-\frac{2\cdot\log\epsilon}{\delta^{2}\cdot p_{h}} . Figure 7: Number of workshares needed to estimate the honest/adversarial power distribution, at error bound \epsilon=0.05 . Inaccuracy is the acceptable deviation from the ideal value. Figure 7 depicts how n is affected given various values of the other parameters. Here, we set the error bound to 0.05 ; in other words, the probability that the observed distribution between the honest and adversarial parties is less accurate than the acceptable level of inaccuracy is 5 %. The x-axis corresponds to the number of workshares, while the y-axis corresponds to the acceptable level of inaccuracy. We observe that inaccuracy drops exponentially w.r.t. the number of samples used. Additionally, inaccuracy drops at a faster rate when the adversarial power is lower. We assume that each workshare is equivalent to a Bitcoin block’s header, which amounts to 80 bytes. Therefore, the overhead per block increases linearly with the number of workshares. As we explain in Section 3.5 , however, this storage is off-chain and can be discarded after finalizing the rewards. For example, assume adversarial power is 15 %. 7{,}832 workshares achieve 3 % inaccuracy (with error probability 5 %), requiring 612 KB per block. Similarly, 1{,}000 workshares achieve approx. 8.5 % inaccuracy at 79 KB. On the other hand, assuming 35 % adversarial power, 3 % inaccuracy is achieved with 10{,}242 workshares, which corresponds to 800 KB. 6 Discussion and Deployment PRS in theory. PRS matches FruitChains in theoretical guarantees but outperforms it in practical settings. This is because the theoretical analysis evaluates the protocols asymptotically , for (very) large parameters. In practice, parameters like freshness or the fork eligibility window cannot be too large without delaying transaction and reward finalization. At realistic parameter values, the theoretical guarantees no longer apply, so we turn to the MDP evaluation. One explanation for why PRS outperforms FruitChains lies in the tradeoff between “Rewarding the Bad” and “Punishing the Good” identified in [ 25 ] . FruitChains eliminates the incentive to fork by rewarding the adversary for failed attempts. PRS does the same through workshares, but to a lesser degree: it splits rewards proportionally rather than yielding the full contested reward to the adversary. This finer split strikes a better balance in practice. PRS in practice. PRS outperforms Reward Splitting (RS) in practical terms. Both mechanisms follow the same punishment strategy, that is, splitting the rewards, but PRS does so in a more fine-grained way, which better approximates the distribution of power between the adversary and the honest parties. In other words, the gain of PRS comes from the difference between 50 % and the actual value of adversarial power; hence, when the latter approaches the former, the two lines converge. Dynamic difficulty. Our theoretical analysis follows the methodology of [ 16 ] , which operates in the static-difficulty setting; we therefore do not establish formal guarantees for variable-difficulty executions. We expect the same intuition to apply in this setting, similarly to variable-difficulty analyses of accumulated-work protocols such as NIPoPoWs: when the target changes, work should be interpreted relative to the target that was active when the object was created. In a deployment, the workshare target would be recalculated using the same difficulty-adjustment rule as the main block target, so that workshares continue to provide a fresh sample of the mining-power distribution. A formal analysis of PRS under variable difficulty is left for future work. Deployment of FairChain . Our FairChain transformation has been deployed in practice as part of a Proof-of-Work blockchain launched in January 2025 [ 5 ] that uses PoEM as its fork-choice rule. The live blockchain records workshares on-chain with a hard cap of 9 workshares per block and a soft target of 3, where each workshare header is approximately 120 bytes, which is comparable to a standard transaction header. Workshares older than 2 blocks (freshness parameter) are rejected by peers. Rewards are paid proportionally to each miner’s workshare-estimated power, with a linear staleness discount applied to shares approaching the freshness timeout, incentivizing timely propagation. At the current parameters, the storage overhead amounts to under 1 KB per block above baseline. 7 Related Work The work most directly related to FairChain is FruitChains [ 16 ] . FruitChains was shown to be a \rho -coalition-safe \epsilon -Nash equilibrium, i.e., any coalition of parties with a fraction of power less than \rho cannot gain more than \epsilon of their fair share of rewards. As shown in Section 4 , our mechanism achieves the same guarantee, as the analysis of FruitChains carries over in our case almost directly. Nonetheless, FairChain outperforms FruitChains in practice, that is, for parameter values smaller than the theoretical, unrealistic, bounds (cf. Section 5 ). The recording of low-work objects on-chain was explored in StrongChain [ 21 ] . StrongChain publishes workshares on-chain, as opposed to keeping them within a mining pool and invisible to the protocol. The paper offers a protocol implementation and a brief discussion of the protocol’s performance in the optimistic setting, where all parties are honest. However, StrongChain’s analysis is lacking in many aspects. Specifically, StrongChain offers only a high-level description of reward allocation and an intuition of why this allocation is beneficial. In comparison, our mechanism is analyzed both in theory, in a game-theoretic setting where parties are assumed rational instead of simply honest, and in practice via Markov decision processes. Moreover, StrongChain’s analysis considers only a specific instance of a selfish mining strategy, and analyzes the protocol’s performance under various parameter values, whereas our MDP analysis evaluates the performance of the optimal adversarial strategy. Another line of work on recording low-work objects on-chain builds on the idea of “weak blocks”. These works include Subchains [ 19 ] and Flux [ 23 ] . Here, the main idea is the formation of “sub-chains”, that is, chains of objects with less PoW than blocks. Therefore, between two consecutive (heavy) blocks, a sub-chain of weak blocks may be created, enabling a more fine-grained estimation of the power distribution among participants. Flux offered a simulation-based analysis, showing that it performs better w.r.t. selfish mining compared to Bitcoin. However, as was shown in [ 25 ] , Subchains performs worse in practice compared to Reward Splitting (RS). In comparison, our mechanism outperforms RS, and thus also Subchains, under the framework of [ 25 ] . The uncle reward system used in Ethereum [ 2 ] prior to its transition to Proof-of-Stake rewarded non-canonical work via uncle blocks . Ritz and Zugenmaier [ 18 ] show empirically that such a fixed partial reward is insufficient: it actually lowers the mining power threshold at which selfish mining becomes profitable, compared to Bitcoin, rather than eliminating the incentive. The core issue is that a fixed reward subsidizes the adversary regardless of their actual mining power. FairChain avoids this by splitting rewards proportionally to the power distribution, ensuring the adversary cannot benefit beyond their fair share. Finally, FairChain can be instantiated on any longest-chain protocol that guarantees safety and liveness, including Nakamoto Consensus [ 13 ] , uniform tie-breaking [ 6 , 7 ] , smallest-hash tie-breaking [ 12 ] , unpredictable deterministic tie-breaking [ 10 ] , Publish-or-Perish [ 24 ] , and PoEM [ 11 ] . The security analysis requires only that the host protocol satisfies these two properties; no other assumptions on the fork-choice rule are needed. Appendix 0.A Chain Selection and Ledger Extraction Here, we present two algorithms omitted from the main body: the ledger-extraction function (Algorithm 5 ), and an example instantiation of MaxValid (Algorithm 4 ). We illustrate MaxValid with PoEM [ 11 ] , which selects the chain with the most accumulated intrinsic work. PoEM is the natural pairing because it uses the same intrinsic-work measure that FairChain uses for reward weighting; any other host protocol’s chain-selection rule applies as well, including Bitcoin’s longest-chain rule. Algorithm 2 The ledger extraction mechanism 1: function \textsc{Extract}_{k,G} ( C ) 2: if \lnot\textsc{Validate}_{G}(C) then 3: return \bot 4: L\leftarrow[] \triangleright Initialize empty ledger 5: for B\in C[:-k] do \triangleright Parse each stable block 6: for \mathsf{tx}\in B.\mathsf{TX} do 7: L\leftarrow L\,\|\,\mathsf{tx}.\textsf{m} 8: return L Algorithm 3 The PoEM maxvalid algorithm 1: function \textsc{MaxValid}_{G,T} ( \overline{C} ) 2: C_{\textsf{max}}\leftarrow[\,] 3: \textsf{maxwork}\leftarrow 0 4: for C\in\overline{C} do 5: if \lnot\textsc{Validate}_{G}(C) then 6: continue 7: \textsf{thiswork}\leftarrow\widetilde{\textsc{work}}(C) \triangleright Computed as \sum_{B\in C}H(B)_{:\lambda} 8: if \textsf{thiswork}>\textsf{maxwork} then 9: C_{\textsf{max}}\leftarrow C 10: \textsf{maxwork}\leftarrow\textsf{thiswork} 11: return C_{\textsf{max}} 0.A.1 Property Definitions As our analysis is based on [ 8 ] and [ 15 ] , we first recall the definitions of chain growth, chain quality, and consistency from there. Next, we revisit the fairness definition of [ 16 ] . Chain Growth Let: \mathsf{min\text{-}chain\text{-}increase}_{t,t^{\prime}}(\mathsf{view})=\min_{i,j}|\mathsf{chain}^{t+t^{\prime}}_{j}(\mathsf{view})|-|\mathsf{chain}^{t}_{i}(\mathsf{view})| \mathsf{max\text{-}chain\text{-}increase}_{t,t^{\prime}}(\mathsf{view})=\max_{i,j}|\mathsf{chain}^{t+t^{\prime}}_{j}(\mathsf{view})|-|\mathsf{chain}^{t}_{i}(\mathsf{view})| where we quantify over nodes i,j such that i is honest at round t and j is honest at round t+t^{\prime} in \mathsf{view} . Let \mathsf{growth}^{t_{0},t1}(\mathsf{view},\Delta,T)=1 iff the following hold: • (consistent length) for all time steps t\leq|\mathsf{view}|-\Delta,t+\Delta\leq t^{\prime}\leq|\mathsf{view}| , for every two players i,j such that in \mathsf{view} i is honest at t and j is honest at t^{\prime} , we have that |\mathsf{chain}^{t^{\prime}}_{j}(\mathsf{view})|\geq|\mathsf{chain}^{t}_{i}(\mathsf{view})| • (chain growth lower bound) for every time step t\leq|\mathsf{view}|-t_{0} , we have \mathsf{min\text{-}chain\text{-}increase}_{t,t_{0}}(\mathsf{view})\geq T . • (chain growth upper bound) for every time step t\leq|\mathsf{view}|-t_{1} , we have \mathsf{max\text{-}chain\text{-}increase}_{t,t_{1}}(\mathsf{view})\leq T . Definition 6 (Chain growth) A blockchain protocol \Pi satisfies (T_{0},g_{0},g_{1}) -chain growth in \Gamma -environments, if for all \Gamma -compliant p.p.t. pair (A,Z) , there exists some negligible function \mathsf{negl} such that for every \kappa\in\mathbb{N} , T\geq T_{0} , t_{0}\geq\frac{T}{g_{0}} and t_{1}\leq\frac{T}{g_{1}} the following holds: \displaystyle Pr[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):growth^{t_{0},t_{1}}(\mathsf{view},\Delta,T)=1] \displaystyle\geq 1-\mathsf{negl}(\kappa) Chain Quality The second desired property is that the number of blocks contributed by the adversary is not too large. Given a \mathsf{chain} , we say that a block B:=\mathsf{chain}[j] is honest w.r.t. \mathsf{view} and prefix \mathsf{chain}[:j^{\prime}] where j^{\prime}\ell , i.e., \mathsf{chain}^{t^{\prime}}_{j}(view) cannot be too much shorter than \mathsf{chain}^{t}_{i}(view) given that t^{\prime}\geq t . Definition 8 (Consistency) A blockchain protocol \Pi satisfies T_{0} -consistency in \Gamma -environments if for all \Gamma -compliant p.p.t. pair (A, Z), there exists some negligible function negl such that for every \kappa\in\mathbb{N} and every T\geq T_{0} the following holds: \displaystyle Pr\big[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):\mathsf{consistent}^{T}(\mathsf{view})=1\big] \displaystyle\geq 1-\mathsf{negl}(\kappa) Fairness The results from [ 15 ] are parameterized by the following quantities: • \alpha:=1-(1-p)^{(1-\rho)n} : the probability that some honest player succeeds in mining a block in a round. • \beta:=\rho{}np : the expected number of blocks an attacker can mine in a round. • \gamma:=\frac{\alpha}{1+\Delta\alpha} : a discounted version of \alpha which takes into account that messages sent by honest parties can be delayed by up to \Delta rounds and this can lead to honest players redoing work; in essence, \gamma corresponds to the effective mining power. Compliant executions for Nakamoto’s blockchain. We now specify the compliance predicate \Gamma^{p}_{\mathsf{nak}} for Nakamoto’s blockchain. We say that \Gamma^{p}_{\mathsf{nak}}=1 iff there is a constant \lambda>1 , such that \alpha(1-2(\Delta+1)\alpha)\geq\lambda\beta where \alpha and \beta are functions of the parameters n,\rho,\Delta and \kappa as defined above. As shown in [ 15 ] , this condition implies the following: Fact 4 If (A,Z) is a \Gamma^{p}_{\mathsf{nak}} -compliant, then np\Delta<1 . Fact 5 If (A,Z) is a \Gamma^{p}_{\mathsf{nak}} -compliant, then \gamma\geq\frac{np}{8} . Subsequently, FruitChains [ 16 ] provided a definition for fairness as follows. Let a player subset selection, S(\mathsf{view},r) , be a function that, given (\mathsf{view},r) , outputs a subset of the players that are honest at round r in \mathsf{view} . S is a \phi -fraction player subset selection if S(\mathsf{view},r) always outputs a set of size \phi n (rounded upwards) where n is the number of players in \mathsf{view} . Given a player subset selection S , a record m is S -compatible w.r.t. \mathsf{view} and prefix \mathsf{chain} if there exists a player j and round r^{\prime} such that j is in S(\mathsf{view},r^{\prime}) , the environment provided m as an input to j at round r^{\prime} , and \mathsf{chain}\prec\mathsf{chain}^{r^{\prime}}_{j}(\mathsf{view}) , where \prec denotes “is a prefix of”. Let \mathsf{quality}^{T,S}(\mathsf{view},\mu)=1 iff for every round r and every player i such that i is honest in round r of \mathsf{view} , we have that among any consecutive sequence of T records \mathsf{chain}^{r}_{i}(\mathsf{view})[j+1:j+T] , the fraction of records that are S -compatible w.r.t. \mathsf{view} and prefix \mathsf{chain}^{r}_{i}(view)[:j] is at least \mu . Definition 9 (Fairness) A blockchain protocol \Pi has (approximate) fairness (T_{0},\delta) in \Gamma -environments, if for all \Gamma -compliant p.p.t. (A,Z) , every positive constant \phi\leq 1-\rho , every \phi -fraction subset selection S , there exists some negligible function \epsilon such that for every \kappa\in\mathbb{N} and every T\geq T_{0} the following holds: \displaystyle Pr[\mathsf{view}\leftarrow EXEC^{\Pi}(A,Z,\kappa):\mathsf{quality}^{T,S}(\mathsf{view},(1-\delta)\phi))=1] \displaystyle\geq 1-\epsilon(\kappa) Appendix 0.B Chain Selection and Ledger Extraction Here, we present two algorithms omitted from the main body: the ledger-extraction function of FairChain (Algorithm 5 ), and an example instantiation of MaxValid (Algorithm 4 ). We illustrate MaxValid with PoEM [ 11 ] , which selects the chain with the most accumulated intrinsic work. PoEM is the natural pairing because it uses the same intrinsic-work measure that FairChain uses for reward weighting; any other host protocol’s chain-selection rule applies as well, including Bitcoin’s longest-chain rule. Algorithm 4 The PoEM maxvalid algorithm 1: function \textsc{MaxValid}_{G,T} ( \overline{C} ) 2: C_{\textsf{max}}\leftarrow[\,] 3: \textsf{maxwork}\leftarrow 0 4: for C\in\overline{C} do 5: if \lnot\textsc{Validate}_{G}(C) then 6: continue 7: \textsf{thiswork}\leftarrow\widetilde{\textsc{work}}(C) \triangleright Computed as \sum_{B\in C}H(B)_{:\lambda} 8: if \textsf{thiswork}>\textsf{maxwork} then 9: C_{\textsf{max}}\leftarrow C 10: \textsf{maxwork}\leftarrow\textsf{thiswork} 11: return C_{\textsf{max}} Algorithm 5 The ledger extraction mechanism 1: function \textsc{Extract}_{k,G} ( C ) 2: if \lnot\textsc{Validate}_{G}(C) then 3: return \bot 4: L\leftarrow[] \triangleright Initialize empty ledger 5: for B\in C[:-k] do \triangleright Parse each stable block 6: for \mathsf{tx}\in B.\mathsf{TX} do 7: L\leftarrow L\,\|\,\mathsf{tx}.\textsf{m} 8: return L Appendix 0.C Extended Analysis In this section, we provide the remaining parts of the analysis that were omitted from the main body of the paper due to space constraints. The analysis is largely based on FruitChains [ 16 ] . 0.C.1 Workobject Freshness A key property is for any Workobject (or fruit to follow [ 16 ] ) mined by an honest player to stay sufficiently fresh to be incorporated. In this section, we prove freshness. Note that we achieve a slightly better freshness parameter ( R=16 ) compared to FruitChains [ 16 ] ( R=17 ). Let \mathsf{WOfreshness}(\mathsf{view},w,k)=1 iff for every honest player i and for every round r<|view|-w , if i mines a Workobject at r in view, then for every honest player j there exists an index pos , such that the Workobject is at pos in the record chain (w.r.t. Nakamoto’s protocol) of j at every round r^{\prime}\geq r+w , and pos is at least k blocks away from the end of the chain. Let wait=2\Delta+\frac{2k}{\gamma} Lemma 2 Let R=16 . For any p , p_{f} , for any \Gamma_{\textsf{FairChain}}^{p,p_{f},R} -compliant (A,Z) , there exists a negligible function \epsilon such that for any \kappa\in\mathbb{N} , Pr\big[\mathsf{view}\leftarrow EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa): \mathsf{WOfreshness}(\mathsf{view},wait,k)=1\big]\geq 1-\epsilon(\kappa) Proof Disregard the blockchain consistency, liveness, and chain growth failure events, which only happen with negligible probability. Let wait=wait(k,n,\rho,\Delta) . • By blockchain consistency , at any point in the execution, whenever an honest player mines a Workobject (i.e., a block, an uncle block or a workshare) f , the block pointed to by that Workobject is at some fixed position pos on the blockchain of every honest player, now and at every time in the future. • Note that if \textsc{work}(\text{Workobject})>T_{\text{block}} , it is not clear at the time of mining whether it will be a block or an uncle block. • Honest players try to mine Workobjects that point to the last block in their chain. • Let \ell denote the length of the chain of the player that mines f ; by definition pos=\ell • By the description of the protocol, if the Workobject f is mined at round r^{\prime} , it gets seen by all honest players by round r^{\prime}+\Delta ; additionally, when this happens, all honest players attempt to add f to their chain as long as it remains recent (w.r.t. all honest players). • By liveness , the Workobject gets thus referenced by a block that is in the record chain of all honest players at some position pos that is at least k blocks away from the end of the chain by round r^{\prime}+\Delta+(1+\delta)\frac{k}{\gamma}\leq r^{\prime}+wait-\Delta • By the upper bound on chain growth, at most (1+\delta)np(\Delta+\frac{2k}{\gamma}) blocks are added in time wait-\Delta . Thus, by round r^{\prime}+wait-\Delta , no honest player has ever had a chain of length \ell^{\prime} , such that \ell^{\prime}>\ell+(1+\delta)np(\Delta+\frac{2k}{\gamma}) • Thus, by round r^{\prime}+wait-\Delta , for every such honest player’s chain length \ell^{\prime} , we have pos=\ell\geq\ell^{\prime}-(1+\delta)np(\Delta+\frac{2k}{\gamma}) • By our compliance assumption and by Fact 4 and Fact 5 , we have that \gamma\geq\frac{np}{8} and np\Delta<1 , thus pos>\ell^{\prime}-(1+\delta)-(1+\delta)16k\geq\ell^{\prime}-16k=\ell^{\prime}-Rk • By consistency , all honest players agree that f is found at position pos in their blockchain at any point after r^{\prime}+wait-\Delta ; additionally, by the consistent length property all honest players agree that position pos is at least k from the end of the chain by r^{\prime}+wait-\Delta+\Delta=r^{\prime}+wait . • It remains to show that the block B that is referenced by f is either a valid block of the chain C of honest users or a valid uncle, as this is the condition for Workobjects to be rewarded. Note that honest parties will reference the last block they see in their chain, which is valid, but not necessarily stable. Should it happen that the block does not end up in C , it thus has to become an uncle. Suppose there exists another block B^{\prime} that is competing with B . In any block that is building on top of B^{\prime} , B is treated as a Workobject (uncle). We have already proven that Workobjects get incorporated into the chain of every honest player; thus, B will be incorporated into the chain of every honest player. We also observe the following fact about wait , which says that the expected number of Workobject s mined by all players during wait+2 is upper bounded by k_{f} . Fact 6 For any p , p_{f} , any \Gamma_{\textsf{FairChain}}^{p,p_{f},R} -compliant (A,Z) , (wait+2)\cdot np_{f}\leq k_{f} Proof Note that by Fact 4 and Fact 5 , we have that \gamma>\frac{np}{8} and np\Delta<1 , thus (wait+2)\cdot np_{f}=(2\Delta+2\frac{k}{\gamma}+2)\cdot{}qpn\leq{}2q+2k\cdot{}8q+2\leq{}2qRk=k_{f} 0.C.2 Some Simplifying Assumptions Towards proving our main theorem, we state some simplifying assumptions that can be made without loss of generality. These assumptions (which all follow from properties of the random oracle H ) will prove helpful in our subsequent analysis. • WLOG1: We may without loss of generality assume that honest players never query the RO on the same input. More precisely, we analyze an experiment where if some honest player wants to query it on an “old” input, it re-samples the nonce until the input is “new”; since the nonce is selected from \{0,1\}^{\kappa} , this “re-sampling” experiment is identical to the real one except with negligible probability, thus we can WLOG analyze it. • WLOG2: We may, without loss of generality, assume that any Workobject that points to a block b which was first mined at time t has been mined after t . Additionally, any Workobject that points to a block that comes after b in a valid chain must have been mined after t . (If not, we can predict the outcome of the random oracle H on some input before having queried H , which is a contradiction. We omit the standard details.) • WLOG3: We may assume without loss of generality that all Workobject s mined by honest players are “new” (i.e., different from all valid Workobject s previously seen by honest players); this follows from WLOG1 and the fact that the probability of seeing a collision in the random oracle is negligible (by a simple union bound over the number of random oracle queries). • WLOG4: We may assume without loss of generality that any valid Workobject which appears in some honest player’s chain at round r was mined before r ; this follows from the unpredictability of the random oracle (and a simple union bound over the number of random oracle queries). • WLOG5: We may assume without loss of generality that there are no “blockchain collisions”, namely, there are no two different valid sequences of blocks which end with the same block. We now turn to proving the three security properties. 0.C.3 Workobject Consistency Disregard chain growth, consistency, and chain quality failure events–they happen with negligible probability. Consider some view \mathsf{view} in the support of EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa) , rounds r,r^{\prime} , s.t. r^{\prime}\geq r , and players i,j that are honest respectively at r,r^{\prime} in view. By consistency , the chains of i,j at r,r^{\prime} agree except for potentially the last k blocks in the chain of i . Let C=b_{0},\dots,b_{|C|} denote those blocks on which they agree and let b_{|C|+1},\dots denote the maximum k blocks in the chain of i at r which are not in the chain of j at r^{\prime} . We now bound the number of Workobjects that can be referenced in these remaining (maximum k ) inconsistent blocks. • By the “recency condition” of valid Workobject s, any valid Workobject in the chain of i at r which is after C must point to a block b_{j^{\prime}} such that j^{\prime}>|C|-Rk . • By the chain quality condition , there exists some j^{\prime\prime} s.t. |C|-R_{k}-k\leq j^{\prime\prime}\leq|C|-R_{k} and b_{j^{\prime\prime}} was mined by an honest player. Let r^{\prime}_{0} denote the round when this block was mined. • Note that r^{\prime}_{0} was mined by an honest player holding a chain of length j^{\prime\prime}\geq|C|-R_{k}-k ; additionally, at r , i is honest, holding a chain of length at most |C|+k (recall that —C— contains the blocks on which i and j agree, and by consistency, all but the last k blocks in the chain of i must be in the chain of j ). Thus, by the chain growth upper bound , at most \mu=(1+\delta)\frac{2k+Rk}{np} rounds could thus have elapsed between r^{\prime}_{0} and r. • By WLOG2, any Workobject which gets added after C must have been mined after r^{\prime}_{0} . By WLOG4, any such Workobject that is part of the chain of i by r was mined before r . • We thus conclude by the Chernoff bound that for every sufficiently small \delta^{\prime} except with probability e^{=\Omega(np_{f}\cdot\frac{k(R+2}{np})}=e^{-\Omega(q(R+2)k}) , there were at most (1+\delta^{\prime})^{2}\cdot{}np_{f}\cdot{}\frac{k(R+2)}{np}=(1+\delta^{\prime})^{2}q(R+2)k<2qRk=k_{f} “inconsistent” Workobject s in the chain of i at r 0.C.4 Workobject Growth Consistent length. The consistent length property follows directly from the consistent length property of the underlying blockchain. Lower bound. Consider any r,t and players i,j that are honest respectively at round r and r+t . Consider the t rounds starting from round r . • By the Workobject freshness condition, every Workobject that is mined by some honest party by round r+t-wait gets incorporated into (and remains in) the chain of player j by r+t . • By the Chernoff bound, in the t-wait rounds from r to r+t-wait , except with probability e^{-\Omega((t-wait)\alpha_{f})} , the honest parties mine at least (1-\delta^{\prime})(t-wait)\alpha_{f} Workobject s (where \delta^{\prime} is some arbitrarily small constant), which are all included in the chain of j at r+t . Additionally, by WLOG3 they are all “new” (i.e., not included in the chains of i at r ) and different. • Finally, by Workobject consistency (proved in Section 0.C.3 ), we have that all but potentially k_{f} of the Workobject s in the chain of i at r are still in the chain of j at r+t . • We conclude that, except with probability e^{-\Omega((t-wait)\alpha_{f})} the chain of j at r+t contains at least (1-\delta^{\prime})(t-wait)\alpha_{f}-k_{f} more Workobject s than the chain of j at r . By Fact 6 , wait\cdot\alpha_{f}=wait\cdot(1-\rho)np_{f}\leq(1-\rho)k_{f}\leq k_{f} ; thus, we have at least (1-\delta)(t-wait)\alpha_{f}-k_{f}\geq(1-\delta)\alpha_{f}{}t-2k_{f} (4) new Workobject . We conclude by noting that this implies that a Workobject growth lowerbound of g_{0}=\frac{1}{1+\delta}\alpha_{f}\geq(1-\delta)\alpha_{f} in the desired regime: Consider any T\geq\frac{5k_{f}}{\delta} and any t\geq\frac{T}{g_{0}}=\frac{T}{\frac{\alpha_{f}}{1+\delta}} As shown above (see Equation 4 ), except with a probability of e^{-\Omega((t-wait)\alpha_{f})} the chain must have grown by at least T(1+\delta)(1-\delta^{\prime})-2k_{f}=T(1+\frac{\delta}{2})(1-\delta^{\prime})+T\frac{\delta}{2}(1-\delta^{\prime})-2k_{f} For a sufficiently small \delta^{\prime} , the first term is greater than T , and the second term is greater than 2k_{f} , and thus the chain must have grown by at least T . Finally note that by Equation 4 e^{-\Omega((t-wait)\alpha_{f})}=e^{-\Omega(t\alpha_{f}-k_{f})}=e^{-\Omega(T-k_{f})}=e^{-\Omega(5k_{f}-k_{f})}=e^{-\Omega(k)} Thus, the chain growth is guaranteed except with negligible probability. Upper bound. Disregard the chain growth, consistency, and chain quality failure events–they happen with negligible probability. Consider some view \mathsf{view} in the support of EXEC^{\Pi_{\textsf{FairChain}}(p,p_{f},R)}(A,Z,\kappa) , rounds r,r^{\prime} , s.t. r^{\prime}=r+t , and players i,j that are honest respectively at r,r^{\prime} in view. By consistency , the chains of i,j at r,r^{\prime} agree except for potentially the last k blocks in the chain of i . Let C=b_{0},\dots,b_{|C|} denote those blocks on which they agree and let b_{|C|+1},\dots denote the blocks in the chain of j at r^{\prime} which are not in the chain of i at r (there may be more than k such blocks since we are looking at the chain of j at a later time r^{\prime} ); We now upper bound the number of Workobject s in the new blocks in the chain of j which come after C , similarly to the Workobject consistency proof (the main difference is that we now consider the chain of j as opposed to the chain of i ). The details follow: • By the “recency condition” of valid Workobject , any valid Workobject in the chain of j at r^{\prime} which is after C must point back to a block b_{j^{\prime}} , such that j^{\prime}>|C|-Rk . • By the chain quality condition , there exists some j^{\prime\prime} s.t. |C|-Rk-k\leq{}j^{\prime\prime}\leq|C|-Rk and b_{j^{\prime\prime}} was mined by an honest player. Let r^{\prime}_{0} denote the round when this block was mined. • Note that at r^{\prime}_{0},b_{j^{\prime\prime}} was mined by an honest player holding a chain of length j^{\prime\prime}\geq|C|-Rk-k ; additionally, at r , i is honest, holding a chain of length at most |C|+k (recall that |C| contains the blocks on which i and j agree, and by consistency, all but the last k blocks in the chain of i must be in the chain of j ). Thus, by chain growth upper bound , for any arbitrarily small \delta^{\prime} at most \mu=(1+\delta^{\prime})\frac{2k+Rk}{np} rounds could thus have elapsed between r^{\prime}_{0} and r . • By WLOG2, any Workobject which gets added after C must have been mined after r^{\prime}_{0} . By WLOG4, any such Workobject that is part of the chain of j by r^{\prime} was mined before r^{\prime} . • We thus conclude by the Chernoff bound that except with a probability of e^{-\Omega(np_{f}\cdot\frac{k(R+2)}{np})}=e^{-\Omega(q(R+2)k)} , there were at most \begin{split}(1+\delta^{\prime})^{2}\cdot{}np_{f}\cdot\Big(\frac{k(R+2)}{np}+t\Big)=\\ (1+\delta^{\prime})^{2}(q(R+2)k+np_{f}t)\leq k_{f}+(1+\delta^{\prime})^{2}np_{f}t\end{split} (5) “new” Workobject s in the chain of j at r^{\prime} . We conclude by noting that this implies a Workobject growth upper bound of g_{1}=(1+\delta)np_{f} in the desired regime: Consider any T\geq\frac{5k_{f}}{\delta} and any t=\frac{T}{g_{1}}=\frac{T(1+\delta)}{np_{f}} As shown above (see Equation 5 ), during this time t , except with negligible probability, the chain must have grown by at most k_{f}+(1+\delta^{\prime})^{2}T(1-\delta)\leq T\delta/5+(1+\delta^{\prime})^{2}T/(1+\delta) For any 0<\delta<1 and \delta^{\prime}=0.1\delta , the above expression is upper bounded by T .