Paper 2020/1091

Ebb-and-Flow Protocols: A Resolution of the Availability-Finality Dilemma

Joachim Neu, Ertem Nusret Tas, and David Tse

Abstract

The CAP theorem says that no blockchain can be live under dynamic participation and safe under temporary network partitions. To resolve this availability-finality dilemma, we formulate a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. The finalized ledger falls behind the full ledger when the network partitions but catches up when the network heals. Gasper, the current candidate protocol for Ethereum 2.0's beacon chain, combines the finality gadget Casper FFG with the LMD GHOST fork choice rule and aims to achieve this property. However, we discovered an attack in the standard synchronous network model, highlighting a general difficulty with existing finality-gadget-based designs. We present a construction of provably secure ebb-and-flow protocols with optimal resilience. Nodes run an off-the-shelf dynamically available protocol, take snapshots of the growing available ledger, and input them into a separate off-the-shelf BFT protocol to finalize a prefix. We explore connections with flexible BFT and improve upon the state-of-the-art for that problem.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.Forthcoming in 42nd IEEE Symposium on Security and Privacy 2021
Keywords
blockchainconsensus
Contact author(s)
jneu @ stanford edu
nusret @ stanford edu
dntse @ stanford edu
History
2021-02-08: last of 2 revisions
2020-09-15: received
See all versions
Short URL
https://ia.cr/2020/1091
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1091,
      author = {Joachim Neu and Ertem Nusret Tas and David Tse},
      title = {Ebb-and-Flow Protocols: A Resolution of the Availability-Finality Dilemma},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1091},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1091}},
      url = {https://eprint.iacr.org/2020/1091}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.