Cryptology ePrint Archive: Report 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.
Category / Keywords: cryptographic protocols/blockchain
Date: received 8 Mar 2017, last revised 1 Nov 2018
Contact author: acr at uconn edu
Available format(s): PDF | BibTeX Citation
Note: Minor updates throughout the paper.
Version: 20181101:215037 (All versions of this report)
Short URL: ia.cr/2017/241
[ Cryptology ePrint archive ]