PaperlayerView exact revision on arXiv

Source-linked AI summary

Formal Barriers to Longest-Chain Proof-of-Stake Protocols

Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, S. Matthew Weinberg

arXiv:1809.06528v1cs.GTcs.CR

TL;DR

The paper examines security challenges in cryptocurrency consensus and develops a formal analysis of incentive-driven deviations in longest-chain Proof-of-Stake protocols. It identifies attacks and concludes that modeled protocols face undesirable properties, while discussing defenses and scope boundaries.

  • Problem

    Cryptocurrency nodes must agree on ledger events, including which of two conflicting transactions spending the same coins is accepted.

    Source: §1.1 · p. 2

  • Method

    The paper formalizes attacks on longest-chain protocols by analyzing predictable mining opportunities and how recency affects deviations.

    Source: §4.1 · p. 10, §4.2 · p. 11

  • Results

    Several hundred confirmation blocks might be necessary to defend against predictable double-spend attacks, making quick confirmation virtually impossible without further defenses in predictable Proof-of-Stake.

    Source: §5 · p. 12

  • Takeaways & Limitations

    Future Proof-of-Stake proposals should transparently prove defenses against predictable double-spend, predictable selfish-mine, and undetectable nothing-at-stake in the ideal model.

    Source: §5 · p. 13

    The results do not apply to protocols using external randomness, which fail to satisfy Chain Dependence; obtaining trusted randomness remains an open challenge.

    Source: §5 · p. 13

Abstract

from arXiv · show

The security of most existing cryptocurrencies is based on a concept called Proof-of-Work, in which users must solve a computationally hard cryptopuzzle to authorize transactions (`one unit of computation, one vote'). This leads to enormous expenditure on hardware and electricity in order to collect the rewards associated with transaction authorization. Proof-of-Stake is an alternative concept that instead selects users to authorize transactions proportional to their wealth (`one coin, one vote'). Some aspects of the two paradigms are the same. For instance, obtaining voting power in Proof-of-Stake has a monetary cost just as in Proof-of-Work: a coin cannot be freely duplicated any more easily than a unit of computation. However some aspects are fundamentally different. In particular, exactly because Proof-of-Stake is wasteless, there is no inherent resource cost to deviating (commonly referred to as the `Nothing-at-Stake' problem). In contrast to prior work, we focus on incentive-driven deviations (any participant will deviate if doing so yields higher revenue) instead of adversarial corruption (an adversary may take over a significant fraction of the network, but the remaining players follow the protocol). The main results of this paper are several formal barriers to designing incentive-compatible proof-of-stake cryptocurrencies (that don't apply to proof-of-work).

1 Introduction

Cryptocurrencies must reach agreement on ledger events, but permissionless participation makes random selection vulnerable to Sybil identities. The paper formalizes incentive-driven barriers for longest-chain Proof-of-Stake protocols, showing that every protocol in its model has a property exploitable by strategic deviation.

1.1 What is a Cryptocurrency?

  • Permissionless cryptocurrencies need consensus on ledger events and Sybil-proof selection, since users can create identities to manipulate uniform participant selection.A double-spend illustrates the stakes: a conflicting ledger can leave a buyer with both the car and the spent coins.Source: §1.1 · p. 2

1.2 Security Concerns Specific to Proof-of-Stake

  • Proof-of-Stake avoids Proof-of-Work’s resource waste, but its costless deviations create the Nothing-at-Stake challenge.Participants can copy outdated histories and participate in them alongside the current history.Source: §1.2 · p. 3
  • The paper studies strategic security, where all users maximize rewards, and proves that every modeled longest-chain Proof-of-Stake protocol satisfies one of two properties exploitable by incentive-driven attacks.Its model captures a wide range of commercial and academic proposals.Source: §1.2 · p. 3, §1.5 · p. 5

1.3 Our Model: Formal Guarantees in Ideal Network Conditions

  • The analysis considers an ideal network with synchronized clocks and zero message latency, while warning that protocols secure only under this assumption may fail under even minimal latency.The authors report that incentive issues remain challenging even in this ideal setting.Source: §1.3 · p. 4

1.4 Comparison to Related Work

  • Prior academic Proof-of-Stake work generally emphasizes network-intrusion security, whereas this paper isolates strategic incentives and recommends analyzing its deviations alongside known attacks.Prior work also includes limited incentive guarantees for specific deviations.Source: §1.4 · p. 4

1.5 Summary of Contributions and Roadmap

  • The paper’s roadmap defines protocol properties, develops attacks against protocols exhibiting them, and then discusses prior work and future directions.Source: §1.5 · p. 5

2 Preliminaries

The preliminaries model ledgers as predecessor-linked blocks and define Proof-of-Stake through validity and mining functions. They also state assumptions intended to support convergence after network partitions and define longest-chain variants by increasing block scores.

Blocks and coins

  • A block points to its predecessor and records its miner and claimed timestamp; its contents and predecessor history describe a potential event history.A coin’s owner is determined by the transactions in that history.Source: §2 · p. 5

Consensus and assumptions

  • Consensus is the central problem: nodes must eventually agree on events, while validity restricts which messages can become blocks.The model assumes validity depends only on a block, time, and its predecessors, and that validity persists as the graph grows and time advances.Source: §2 · p. 5
  • Chain Dependence and Monotonicity prevent a block once accepted as valid from later becoming invalid as the graph expands or time advances.The assumptions are motivated partly by Eclipse attacks, which can partition the network and interrupt consensus.Source: §2 · pp. 5–6

Proof-of-Stake protocol

  • A Proof-of-Stake protocol uses deterministic validation and mining functions; mining is efficiently computable by the coin owner, distinguishing it from work-based mining.The validity rule also constrains the coin witness and claimed timestamp, while the mining function returns a block only when an eligible one exists.Source: §2 · pp. 6–7

Longest-chain variants

  • Longest-chain variants assign blocks monotonically increasing scores and direct users to mine on the highest-scoring valid block they know.Their stated robustness benefit is rapid convergence to the higher-scoring history after a partition ends; protocols with finality may instead stall or fail to reunite on consensus.Source: §2 · p. 7

3 Properties of Protocols

The section introduces predictability and recency as protocol properties relevant to strategic attacks. It defines local and global predictability, and treats recency as its complement, with an observation establishing their dichotomy.

3.1 (Un)-Predictability

  • Unpredictability is desirable because advance knowledge of mining eligibility can make attacks such as double-spending or selfish-mining more profitable.Source: §3.1 · p. 7
  • D-local predictability means a coin’s owner can efficiently predict eligibility D predecessors before a block; global predictability extends that ability to every participant.Every Proof-of-Stake protocol is 1-locally predictable for timestamps later than the block’s timestamp.Source: §3.1 · p. 8

3.2 (Non)-Recency

  • D-recency means eligibility depends on information in the last D predecessors, and for any block, timestamp, and D, a coin is either D-locally predictable or D-recent.The passage notes that shared pseudorandomness across chains can make certain deviations easier to detect.Source: §3.2 · p. 8

4 Security Implications

The section describes two incentive-driven attacks: global predictability lets miners selectively withhold blocks without risking failure, while recency permits undetectable Nothing-at-Stake behavior. Under stated assumptions, both can increase an attacker’s fraction of blocks, though profitability depends on the reward scheme.

4 Security Implications

  • The section frames these attacks as consequences of global predictability and recency, which create distinct security vulnerabilities in longest-chain variants.Its opening states that the section elaborates on the security implications of both properties.Source: §4 · p. 9, §4.1 · p. 10, §4.2 · p. 12

4.1 Global Predictability

  • The section also identifies globally predictable double-spending: overwriting a transaction can let an attacker effectively spend the same coins twice and receive goods for free.The authors defer its detailed treatment, along with locally predictable variants, to the appendices.Source: §4.1 · p. 9
  • With sufficient global predictability, an attacker can withhold only blocks for which a private chain will outpace the competing chain, avoiding the risk of ordinary selfish mining.The attack delays announcing mined blocks to claim extra mining rewards; Figure 1 illustrates the strategy using S(B) as the number of predecessors of B.Source: §4.1 · pp. 9–10, Figure 1 · p. 9
  • For standard reward schemes, globally predictable selfish mining is profitable because it lets an attacker produce a greater fraction of blocks on the longest chain.How often the attack is available depends on the scoring function and protocol; the analyzed probability case assumes the simple longest-chain rule and a random-oracle protocol.Source: §4.1 · p. 10

4.2 Recency

  • An undetectable Nothing-at-Stake strategy mines on multiple blocks at once, announcing an alternative block only when doing so creates no provable deviation.Figure 2 depicts two blocks; checking whether both are valid has no resource cost, and announcing both may yield an expected monetary gain depending on the reward scheme.Source: §4.2 · pp. 10–11, Figure 2 · p. 11
  • The strategy never produces a provable deviation, so its announcements cannot be distinguished from honest behavior using that criterion.For D-recent protocols, block validity can depend on blocks between an alternative parent and PredD(A), giving each coin a fresh chance to be eligible to mine on the alternative block.Source: §4.2 · p. 11
  • With the simple longest-chain rule and a random-oracle protocol, when the system has more coins than the protocol’s recency, the strategy announces twice as many blocks as honest mining.Profitability still depends on the reward scheme, but the strategy can undetectably increase the attacker’s fraction of blocks; the section concludes that recent longest-chain variants are vulnerable.Source: §4.2 · pp. 11–12

5 Discussion

The discussion surveys defenses against predictable attacks while emphasizing that incentive-compatible longest-chain Proof-of-Stake remains challenging even in an ideal network. It calls for transparent ideal-model proofs and leaves key questions about randomness and checkpointing open.

5 Discussion

  • The paper concludes that every Longest-Chain-Variant-Proof-of-Stake protocol has some undesirable property, even with perfect connectivity and no latency.It asks whether Byzantine consensus or a true longest-chain variant can provide the desired guarantees; trusted randomness and trusted checkpointing remain open questions.Source: §5 · pp. 12–13

Preventing predictable selfish mining

  • Fruitchains, Ouroboros, and Tezos require both a majority of blocks and a majority of support tokens or fruits in a window to selfish-mine.Snow White and Ouroboros bound deviation rewards by ε, but whether these schemes strictly disincentivize known attacks remains open.Source: §5 · p. 12

Preventing predictable double-spend

  • Several hundred confirmation blocks may be needed to defend against predictable double-spends, making quick confirmations difficult without further defenses.Ouroboros suggests 148 minutes at one block per minute against an attacker controlling 40% of stake, consistent with the paper’s analysis.Source: §5 · p. 12

Defending against Undetectable Nothing-at-Stake

  • Commercial protocols commonly use large D and checkpointing to address undetectable Nothing-at-Stake, but this defense has not been rigorously analyzed.Checkpointing may be external, hard-coded, or based on participants’ trust that they will not consider forks deeper than D blocks.Source: §5 · p. 12
  • Casper’s proposed “dunkles” punish miners whose blocks are orphaned, potentially discouraging attacks but also punishing some honest miners by bad luck.The proposal currently lacks a formal specification and rigorous evaluation.Source: §5 · pp. 12–13

Rigorously and Transparently Evaluate Protocols in the Ideal Model

  • The authors argue that future Proof-of-Stake proposals should rigorously and transparently defend against predictable attacks in the ideal model, while mapping richer-model incentive claims to transparent ideal-model claims.They identify a tradeoff between D-local predictability and D-recency, and say external-randomness protocols fall outside their results because they fail Chain Dependence.Source: §5 · p. 13

A.1 Assumption 1

The examples show how external randomness and validity rules dependent on other blocks can violate Chain Dependence and Monotonicity, respectively. The paper notes that such protocols are more vulnerable to Eclipse attacks than virtually all existing proposals.

A.1 Assumption 1

  • A protocol whose block validity depends on a trusted external randomness source violates Chain Dependence because that randomness is not contained in the blockchain.The NIST beacon is given as an example.Source: §A.1 · p. 15
  • A rule invalidating a block when its creator proposed another block in the same two-week period violates Monotonicity.The block is valid when considered with its own predecessors, but invalid in a graph containing both blocks and their predecessors.Source: §A.1 · p. 15
  • These example protocols are more vulnerable to Eclipse attacks than virtually all existing proposals..Source: §A.1 · p. 15

A.2 Freezing

The appendix allows Proof-of-Stake definitions to require coins to remain owned by the miner for multiple blocks before use. It also illustrates how predictability varies across protocols, including examples that are globally predictable and one whose predictions are constrained by signing authority.

A.2 Freezing

  • A freezing parameter F can require a coin’s owner to remain unchanged throughout the F blocks before the coin is used for mining.Definition 3 is the special case F = 1; freezing can also be incorporated into the validity predicate, but treating it separately simplifies later definitions.Source: §A.2 · p. 16

A.3 Predictability

  • In P1, every coin is D-globally predictable for all D and all A because users can compute the hash-based eligibility conditions across candidate times and predecessors.The protocol accepts a block exactly when HASH(A, tB, cB) < T.Source: §A.3 · p. 16
  • In P2, every coin is D-globally predictable for all D and all A because users can enumerate potential block times and check HASH(t, c) < T.The protocol uses that hash condition for block validity.Source: §A.3 · p. 16
  • P3 is 1-locally predictable, but an owner cannot efficiently predict whether a block exists when producing it would require signing as another coin’s owner.The example uses blocks carrying miner signatures and a validity test based on HASH(sB) < T.Source: §A.3 · pp. 16–17

B.1 Locally Predictable Selfish Mining

Locally predictable selfish mining uses knowledge of one’s own future eligible blocks to choose when to withhold, retaining a statistical edge without predicting when other miners will produce blocks. The paper states that this attack is available to every Proof-of-Stake protocol and can increase expected rewards under suitable thresholds.

B.1 Locally Predictable Selfish Mining

  • Unlike globally predictable mining, this attack cannot predict when the rest of the network will find blocks, but timing one’s own blocks gives a statistical edge.Withholding is favorable when one’s blocks arrive earlier than normal and unfavorable when they arrive later.Source: §B.1 · p. 17
  • The attack waits for a future time when the miner can publish a privately built path whose score exceeds the current score by k, then withholds until that time.The definition uses a cutoff Tk and publishes the block and its predecessors at the selected time.Source: §B.1 · p. 17
  • For any α > 0 stake share, suitable thresholds let a miner produce more than an α-fraction of longest-chain blocks and strictly increase expected reward.This applies to existing longest-chain variants in the paper’s framework; 1-local predictability suffices because the attacker needs to predict only its own blocks.Source: §B.1 · p. 17
  • Every Proof-of-Stake protocol is vulnerable to locally predictable selfish mining, and an eligible miner can attempt the attack for any k.The paper says reward increases vary by protocol but are non-zero in all existing protocols known to the authors.Source: §B.1 · pp. 17–18
  • Greater local predictability gives earlier notice that an attack may succeed, which might help with bribery or a predictable double-spend.The paper says this advance notice is of unclear significance for reward-seeking attacks alone.Source: §B.1 · p. 18

B.2 Predictable Double-Spend

The attack exploits predictable mining opportunities to replace a payment history after a vendor accepts the transaction, potentially obtaining goods without payment. Its success depends on confirmation timing and whether the attacker can produce a longer chain faster than the rest of the network.

B.2 Predictable Double-Spend

  • Confirmation time is vendor-dependent, ranging from accepting a signed, broadcast payment to waiting for several blocks after its inclusion.A vendor exchanges goods once it believes the history defined by the protocol; the required confirmation may vary by transaction.Source: §B.2 · p. 18
  • The attacker privately prepares a payment, compares earliest times to build a longer chain than others, then times the payment announcement and chain release.The strategy uses t′k for an attacker-built chain and t∗k for a chain built by other users; its later steps include hoping the payment is confirmed before releasing the private chain.Source: §B.2 · p. 19
  • A successful attack replaces the history containing the payment, so the attacker gets the goods for free; it parallels selfish mining but seeks to cancel a transaction.The locally predictable version adds announcing the transaction to the corresponding selfish-mining attack.Source: §B.2 · p. 19
  • The attacker can attempt either predictable attack when its earliest time to create ℓ blocks is less than the rest of the network’s, though further protocol details determine success.With a random-oracle mining function, the attacker can estimate the network’s earliest time with high probability; global predictability lets it compute that time with probability 1.Source: §B.2 · p. 20
  • The race probability is computed from 2ℓ−1 biased coin flips with heads probability α, and ℓ is safe when the attacker’s win probability is below threshold T.ℓ∗α,T is the smallest safe window for a chosen tolerance threshold.Source: §B.2 · p. 20
  • For 40% stake, the analysis expects no successful race of 816 blocks over the cryptocurrency’s lifetime under the stated threshold assumptions.The example assumes a lifetime of about 5 × 10^8 blocks and sets the per-race threshold T to 2 · 10^-16 to bound lifetime success probability by 10^-7.Source: §B.2 · p. 20

B.3 Recency

For D-Recent protocols with random-oracle recency ℓ < D, Undetectable Nothing-at-Stake can let a miner announce blocks more often than an honest miner. The advantage depends on how often the safety check can detect reuse of a coin across forks.

B.3 Recency

  • A protocol that is not D-Recent for any D can make same-coin blocks on separate forks share eligibility, causing the deviation check to reject the extra block.The paper’s example uses VP(B) = 1 iff HASH(tB, cB) < T; the strategy then behaves like honest mining.Source: §B.3 · pp. 21–22
  • When ℓ < D, forks use independent pseudorandom seeds, so the safety check rarely stops an illegitimate block from being announced.Both the honest protocol and Undetectable Nothing-at-Stake satisfy the More-Than-Honest strategy definition.Source: §B.3 · p. 22
  • The bound is framed for miners that extend the best-known block when eligible but may announce additional blocks; D < λ/2 is the stated defense concern.The paper says protocols expecting at least λ actively mining coins must defend against the strategy whenever D < λ/2.Source: §B.3 · p. 22
  • The Undetectable Nothing-at-Stake strategy announces blocks at least 2 − 2D/(λ + 1) times as often as an honest strategy under the proposition’s assumptions.The proposition assumes a D-Recent protocol with random-oracle recency ℓ < D, at least λ coins, and miners using a More-Than-Honest strategy.Source: §B.3 · p. 22
  • The safety check can block a second announcement only if that coin previously mined within D blocks of the relevant predecessor; growth beyond D is sufficient to let it through.The within-D condition is necessary, but not sufficient, for a coin to have mined on top of PredD(B).Source: §B.3 · p. 22
  • A coin attempting to mine in two locations accounts for at most 2/(λ + 1) of timesteps, and each such event can claim D later timesteps for the safety check.The remaining timesteps allow publication of both blocks, yielding the lower-bound announcement rate in Proposition 2.Source: §B.3 · p. 23

C Existing Proof-of-Stake Protocols

The paper applies its predictability and Nothing-at-Stake analysis to existing Proof-of-Stake proposals, while noting that some protocols do not fit its framework. Snow White and Ouroboros are predictable and face the paper’s identified attack questions, with existing defenses or guarantees addressing some but not all of them.

Snow White

  • Snow White is predictable and vulnerable to predictable selfish mining and double-spending, while its fruit rewards bound an α < 1/2 miner’s reward share to α + ε.The authors state that Snow White’s long confirmation times can mitigate predictable double-spending, but otherwise the attack is not addressed; Snow White is not vulnerable to Undetectable Nothing-at-Stake because it is not Recent.Source: C Existing Proof-of-Stake Protocols · p. 23

Ouroboros

  • Ouroboros is L-globally predictable, and its cited calculations require 148-minute confirmations at 40% attacker stake and 663 minutes at 45% for 99.9% confidence against the double-spend.Its miners are assigned time slots within epochs, and it also proves an (α − ε, α + ε) reward-share bound when α < 1/2 and other miners follow the protocol.Source: C Existing Proof-of-Stake Protocols · p. 24

No Rewards

  • No-rewards retains prior formal guarantees with ε = 0, but remains at least as vulnerable to predictable double-spending because attempting it costs nothing.The authors say its incentive compatibility is uncertain: stake holders may remain online to preserve currency value, but double-spends may run rampant without strict incentives to follow the protocol.Source: C Existing Proof-of-Stake Protocols · p. 24

Scope and other protocols

  • Algorand [6] and DFinity do not cleanly fit the framework, while the paper focuses on core protocols and proposes further analysis of its formalized deviations.DFinity uses threshold signatures as a future pseudorandomness source, which the authors say entails trusted setup when the eligible signer set changes and a new consensus problem over waiting for signatures.Source: C Existing Proof-of-Stake Protocols · pp. 23–25

Bentov-Gabizon-Mizrahi

  • Chains-of-Activity is l-globally predictable because seeds from one group select miners for a later group; Dense-CoA is 1-Recent.The authors discuss l-step confirmation times for Chains-of-Activity and do not discuss predictable selfish mining there.Source: C Existing Proof-of-Stake Protocols · p. 25

D Proof-of-Stake and GHOST

GHOST selects the largest-subtree fork, allowing forks to contribute to chain selection. The paper describes an exponential-forking attack in which an attacker can grow a chosen subtree faster than honest block production, forcing GHOST-following miners onto it.

D Proof-of-Stake and GHOST

  • GHOST greedily follows the child with the largest subtree, treating descendants as votes to include their ancestors.The protocol defines W(B) as the size of the subtree rooted at B, starts at the tree root, and repeats the largest-subtree choice until reaching a leaf.Source: D Proof-of-Stake and GHOST · pp. 25–26
  • In a D-Recent Proof-of-Stake protocol, an attacker can greatly enlarge a chosen subtree by mining simultaneously on top of every node in it.The section considers a 1-Recent protocol acting as a random oracle with recency 1 and introduces exponential forking to force GHOST-following miners onto the attacker’s subtree.Source: D Proof-of-Stake and GHOST · p. 26
  • The attacker adds an average of αx_t blocks per timestep to a subtree of size x_t, while honest miners add blocks at rate 1 − α.The paper models the total honest blocks added up to time t as y_t before solving the recurrences.Source: D Proof-of-Stake and GHOST · p. 26
  • The attacker’s chosen subtree grows exponentially faster than other blocks, quickly forcing GHOST-following miners to mine on it.The paper states this follows from solving the recurrences after k steps.Source: D Proof-of-Stake and GHOST · p. 26

Related papers

Loading 1809.06528v1…