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

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

Abstract

The security of most existing cryptocurrencies relies on Proof-of-Work (PoW), where transaction authorization is tied to computational effort ("one unit of computation, one vote"). While PoW is robust, it necessitates massive expenditures on hardware and electricity. Proof-of-Stake (PoS) offers a "wasteless" alternative by selecting block authors proportional to their wealth ("one coin, one vote"). However, the lack of physical resource expenditure introduces the "Nothing-at-Stake" problem: there is no inherent cost to deviating from the protocol. This paper establishes formal barriers to designing incentive-compatible PoS protocols, proving that any longest-chain PoS system is mathematically forced into a trade-off between predictability and recency, both of which create significant vulnerabilities to strategic actors.

Introduction

Transitioning from Proof-of-Work to Proof-of-Stake is a primary goal for the blockchain industry to reduce environmental impact. In PoW, mining on a fork requires real-world energy; in PoS, validating multiple versions of history is computationally trivial. While previous research often focused on "adversarial corruption" (where a fixed fraction of nodes are malicious), this work shifts the focus to "incentive-driven deviations." In this model, every participant is a rational actor who will deviate from the protocol if doing so increases their revenue. This paper demonstrates that the very nature of internal randomness in PoS creates fundamental security hurdles that do not exist in PoW.

A Formal Framework for PoS

To analyze these barriers, the authors define any longest-chain PoS protocol through two deterministic functions:

  1. $V_P$ (Validating): A function that determines if a block is valid based on the current time and the specific coin used to "witness" or sign it.
  2. $M_P$ (Mining): The process by which a coin owner generates a new block.

Unlike PoW, where randomness is "external" (the physical difficulty of finding a hash), PoS must generate randomness "internally" from the blockchain itself. This leads to a fundamental taxonomy of PoS protocols based on two mutually exclusive properties:

  • $D$-Local Predictability: A protocol is predictable if a coin owner can look at the current state of the chain and determine if they will be eligible to mine a block $D$ steps into the future.
  • $D$-Recency: A protocol is recent if the validity of a new block depends strictly on a very small window of recent history (the last $D$ blocks).

The "No Free Lunch" Theorem

The core contribution of this research is a formal proof that no longest-chain PoS protocol can avoid both predictability and recency. If a protocol attempts to make the "lottery" for the next block unpredictable, it must rely on the entropy of the most recent blocks. Conversely, if it tries to avoid relying on recent blocks (to prevent long-range attacks), the lottery becomes predictable.

This trade-off creates two distinct categories of strategic attacks:

1. The Fragility of Predictable Protocols

In protocols that are $D$-locally predictable, attackers can engage in Predictable Selfish Mining. Because an attacker knows they are scheduled to win a future block, they can strategically withhold blocks to orphan the work of honest miners with zero risk.

This predictability significantly degrades the security of transaction confirmations. For example, to defend against a double-spend attack from an actor holding 40% of the stake, a vendor in a predictable PoS system might need to wait for hundreds of blocks to achieve the same level of security that PoW provides in a fraction of the time.

2. The Recency Trap and Undetectable Deviations

In $D$-recent protocols, attackers can exploit the "Nothing-at-Stake" problem through Undetectable Forking. An attacker can mine on multiple forks simultaneously. Crucially, in a $D$-recent system, this behavior is mathematically indistinguishable from an honest miner experiencing network latency or a temporary partition. Consequently, the protocol cannot punish the attacker without also penalizing innocent users with poor connectivity. This strategy allows a rational attacker to produce blocks at nearly twice the rate of an honest miner, effectively siphoning rewards from the rest of the network.

Conclusion

The findings suggest that the "internal randomness" of PoS is a double-edged sword. While it eliminates the need for energy-intensive computation, it introduces formal vulnerabilities that rational actors can exploit. These barriers apply specifically to longest-chain PoS variants (such as Ouroboros or early iterations of Ethereum’s Casper).

While these results are proven under ideal network conditions, they imply even greater risks in real-world scenarios with latency. Potential solutions to bypass these barriers may include the use of "trusted external randomness" (e.g., a NIST beacon) or "trusted checkpointing," though these methods introduce their own trade-offs regarding decentralization. Ultimately, the paper highlights that achieving the same incentive-compatibility as Proof-of-Work in a Proof-of-Stake environment requires moving beyond simple longest-chain rules or accepting significant trade-offs in confirmation speed and security.

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 Christos-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},
}
Figure