Paper 2017/241
Linear Consistency for Proof-of-Stake Blockchains
Erica Blum, Aggelos Kiayias, Cristopher Moore, 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
Note: This is the full version accompanying the paper in SODA 2020.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- blockchainsproof-of-stake
- Contact author(s)
-
acr @ uconn edu
saad quader @ uconn edu - History
- 2019-11-22: last of 5 revisions
- 2017-03-14: received
- See all versions
- Short URL
- https://ia.cr/2017/241
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/241, author = {Erica Blum and Aggelos Kiayias and Cristopher Moore and Saad Quader and Alexander Russell}, title = {Linear Consistency for Proof-of-Stake Blockchains}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/241}, year = {2017}, url = {https://eprint.iacr.org/2017/241} }