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

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

TL;DR

This paper proves a fundamental "no-free-lunch" theorem for Proof-of-Stake (PoS) cryptocurrencies: any protocol following the "longest-chain" rule is mathematically forced to be either predictable or reliant on very recent history. Both states create massive openings for strategic attackers to either game future block rewards or mine on multiple forks simultaneously without being detected.

What Problem Does This Paper Address?

The crypto world has long sought to move from Proof-of-Work (PoW)—which consumes as much electricity as small nations—to Proof-of-Stake (PoS), where "one coin equals one vote." However, PoS faces a unique challenge: it is "wasteless." In PoW, mining on a fake fork costs real electricity. In PoS, it costs nothing to try and validate every possible version of history. This is known as the "Nothing-at-Stake" problem.

While many PoS protocols exist, most lack rigorous proofs of security in a "strategic" model—where every participant is a rational actor trying to maximize their own profit, rather than just a mix of "honest" and "malicious" players. The authors aim to find if there are fundamental, formal barriers that prevent PoS from being as incentive-compatible as PoW.

Methods

The authors develop a formal mathematical framework to define any longest-chain PoS protocol using two deterministic functions:

  1. $V_P$ (Validating): Determines if a block is valid based on the current time and the coin used to "witness" it.
  2. $M_P$ (Mining): The process by which a coin owner creates a new block.

Crucially, they define two mutually exclusive properties that every PoS protocol must satisfy:

  • $D$-Local Predictability: Can a coin owner look at the current chain and predict if they will be eligible to mine a block $D$ steps into the future?
  • $D$-Recency: Does the validity of a block depend strictly on the very recent history (the last $D$ blocks)?

By proving that every protocol is either predictable or recent, they create a taxonomy of vulnerabilities and then design specific "strategic" attacks for each category.

Datasets

As a theoretical paper in computer science and game theory, this work does not use empirical datasets. Instead, it uses:

  • Formal Proofs: To establish the predictability/recency trade-off.
  • Probabilistic Modeling: Using the "Random Oracle" model (treating the mining function as a source of perfect randomness) to calculate the success rates of various attacks.
  • Simulations: Calculating "safe" confirmation windows using binomial distributions to compare PoS security against PoW benchmarks.

Key Insights and Ideas

  • The Inevitable Trade-off: You cannot design a longest-chain PoS protocol that is neither predictable nor recent. If you try to make the "lottery" for the next block unpredictable, you must rely on the entropy of the most recent blocks. If you try to avoid relying on recent blocks (to prevent long-range attacks), the lottery becomes predictable.
  • External vs. Internal Randomness: PoW is secure because its randomness is "external" (the physical difficulty of hashing). PoS tries to generate randomness "internally" from the blockchain itself. This paper shows that internal randomness is a double-edged sword that attackers can always sharpen.
  • The "Undetectable" Threat: In $D$-recent protocols, an attacker can perform "Nothing-at-Stake" (mining on multiple forks) in a way that is mathematically indistinguishable from an honest miner experiencing network lag. This means the protocol cannot punish the attacker without also punishing innocent users with poor internet connections.

Key Results

  • Predictable Protocols are Fragile: If a protocol is predictable, attackers can perform "Predictable Selfish Mining." They can see they will win a future block and choose to withhold it to orphan other miners' work with zero risk.
  • Confirmation Times: To defend against a double-spend attack in a predictable PoS protocol where an attacker holds 40% of the stake, a vendor might need to wait for hundreds of blocks (potentially hours) to reach the same level of security that PoW achieves much faster.
  • The 2x Advantage: In $D$-recent protocols, the "Undetectable Nothing-at-Stake" strategy allows an attacker to produce blocks at nearly twice the rate of an honest miner, effectively siphoning rewards from the rest of the network.

Limitations and Future Work

  • Ideal Network Assumptions: The authors prove these barriers exist even in an "ideal" network with zero latency and perfect synchronization. If PoS is vulnerable in a perfect world, it is certainly vulnerable in the messy real world.
  • Scope: The results apply specifically to longest-chain PoS variants (like early versions of Ethereum's Casper or Ouroboros). They do not necessarily apply to Byzantine Fault Tolerant (BFT) consensus protocols like Algorand, which avoid the longest-chain rule entirely.
  • Future Directions: The authors suggest exploring "trusted external randomness" (like a NIST beacon) or "trusted checkpointing" as potential ways to bypass these formal barriers, though both introduce their own centralization risks.

Summary updated

Abstract

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).
BibTeX
@inproceedings{browncohen2019formal,
  author = {Jonah Brown-Cohen and Arvind Narayanan and Alexandros Psomas and S. Matthew Weinberg},
  title = {{Formal Barriers to Longest-Chain Proof-of-Stake Protocols}},
  booktitle = {EC},
  year = {2019},
  doi = {10.1145/3328526.3329567},
}

Loading related content...

Figure