Paper 2017/241

Linear Consistency for Proof-of-Stake Blockchains

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

Abstract

Blockchain protocols achieve consistency by instructing parties to remove a suffix of a certain length from their local blockchain. The current state of the art in Proof of Stake (PoS) blockchain protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017) suggests that the length of the segment should be $\Theta(k^2)$ for the consistency error to be exponentially decreasing in $k$. This is in contrast with Proof of Work (PoW) based blockchains for which it is known that a suffix of length $\Theta(k)$ is sufficient for the same type of exponentially decreasing consistency error. This quadratic gap in consistency guarantee is quite significant as the length of the suffix is a lower bound for the time required to wait for transactions to settle. Whether this is an intrinsic limitation of PoS--due to issues such as the "nothing-at-stake" problem--or it can be improved is an open question. In this work we put forth a novel and general probabilistic analysis for PoS consistency that improves the required suffix length from $\Theta(k^2)$ to $\Theta(k)$ thus showing, for the first time, how PoS protocols can match PoW blockchain protocols for exponentially decreasing consistency error. Moreover, our detailed analysis provides an explicit polynomial-time algorithm for exactly computing the (exponentially-decaying) error function which can directly inform practice.

Note: Minor updates throughout the paper.