Lune

SODA2020Top-tier venue

The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains

Erica Blum, Aggelos Kiayias, Cristopher Moore, Saad Quader, Alexander Russell

Abstract

Blockchain data structures maintained via the longest-chain rule have emerged as a powerful algorithmic tool for consensus algorithms. The technique-popularized by the Bitcoin protocol-has proven to be remarkably flexible and now supports consensus algorithms in a wide variety of settings. Despite such broad applicability and adoption, current analytic understanding of the technique is highly dependent on details of the protocol's leader election scheme. A particular challenge appears in the proof-of-stake setting, where existing analyses suffer from quadratic dependence on suffix length.

We describe an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longestchain rule in quite general circumstances and establish bounds-optimal to within a constant-on the probability of a consistency violation. This settles a critical open question in the proof-of-stake setting where we achieve linear consistency for the first time.

Operationally, blockchain consensus protocols achieve consistency by instructing parties to remove a suffix of a certain length from their local blockchain. While the analysis of Bitcoin guarantees consistency with error 2 -by removing ( ) blocks, recent work on proof-of-stake (PoS) blockchains has suffered from quadratic dependence: (PoS) blockchain protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can only establish that the length of this suffix should be Θ( 2 ). This consistency guarantee is a fundamental design parameter for these systems, as the length of the suffix is a lower bound for the time required to wait for transactions to settle. Whether this gap is an intrinsic limitation of PoS-due to issues such as the "nothing-at-stake" problem-has been an urgent open question, as deployed PoS blockchains further rely on consistency for protocol correctness: in particular, security of the protocol itself relies on this parameter. Our general theory directly improves the required suffix length from Θ( 2 ) to Θ( ). Thus we show, for the first time, how PoS protocols can match proof-of-work blockchain protocols for exponentially decreasing consistency error.

Our analysis focuses on the articulation of a two-dimensional stochastic process that captures the features of interest, an exact recursive closed form for the critical functional of the process, and tail bounds established for associated generating functions that dominate the failure events. Finally, the analysis provides an explicit polynomial-time algorithm for exactly computing the exponentially-decaying error function which can directly inform practice.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Practical Settlement Bounds for Longest-Chain Consensus cites Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability
  • Practical Settlement Bounds for Longest-Chain Consensus cites Tight Consistency Bounds for Bitcoin
  • Nakamoto Consensus under Bounded Processing Capacity cites Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability
  • Nakamoto Consensus under Bounded Processing Capacity cites Tight Consistency Bounds for Bitcoin
  • The Generals' Scuttlebutt: Byzantine-Resilient Gossip Protocols cites Tight Consistency Bounds for Bitcoin
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. The Generals' Scuttlebutt: Byzantine-Resilient Gossip ProtocolsSandro Coretti, Aggelos Kiayias, Cristopher Moore, Alexander RussellCCS 2022 · 23 citations
  2. Minotaur: Multi-Resource Blockchain ConsensusMatthias Fitzi, Xuechao Wang, Sreeram Kannan, Aggelos Kiayias et al.CCS 2022 · 5 citations
  3. Practical Settlement Bounds for Longest-Chain ConsensusPeter Gazi, Ling Ren, Alexander RussellCRYPTO 2023 · 3 citations
  4. Nakamoto Consensus under Bounded Processing CapacityLucianna Kiffer, Joachim Neu, Srivatsan Sridhar, Aviv Zohar et al.CCS 2024 · 2 citations
  5. Tight Consistency Bounds for BitcoinPeter Gazi, Aggelos Kiayias, Alexander RussellCCS 2020

Builds on1

  1. Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic AvailabilityChristian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell et al.CCS 2018 · 306 citations

Related papers

  1. Everything is a Race and Nakamoto Always WinsAmir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse et al.CCS 2020 · 3 citations
  2. On the Anonymity Guarantees of Anonymous Proof-of-Stake ProtocolsMarkulf Kohlweiss, Varun Madathil, Kartik Nayak, Alessandra ScafuroS&P 2021 · 13 citations
  3. On the Limits of Consensus under Dynamic Availability and ReconfigurationJavier Nieto, Joachim Neu, Ling RenCCS 2026 · 2 citations
  4. Ouroboros Crypsinous: Privacy-Preserving Proof-of-StakeThomas Kerber, Aggelos Kiayias, Markulf Kohlweiss, Vassilis ZikasS&P 2019 · 82 citations
  5. Towards Practical Sleepy BFTDahlia Malkhi, Atsuki Momose, Ling RenCCS 2023 · 13 citations
Dusk over the sea between two cliffs drawn in fine vertical lines