**Linear Consistency for Proof-of-Stake Blockchains**

*Erica Blum and Aggelos Kiayias and Cristopher Moore and Saad Quader and 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 longest-chain 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^{-k}$ by removing $O(k)$ 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 $\Theta(k^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 $\Theta(k^2)$ to $\Theta(k)$. 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.

**Category / Keywords: **cryptographic protocols / blockchains, proof-of-stake

**Date: **received 8 Mar 2017, last revised 22 Nov 2019

**Contact author: **acr at uconn edu,saad quader@uconn edu

**Available format(s): **PDF | BibTeX Citation

**Note: **This is the full version accompanying the paper in SODA 2020.

**Version: **20191122:175902 (All versions of this report)

**Short URL: **ia.cr/2017/241

[ Cryptology ePrint archive ]