Paper 2016/918

The Sleepy Model of Consensus

Rafael Pass and Elaine Shi

Abstract

The distributed systems literature adopts two primary network models, the synchronous model where honest messages are delivered in the next round, and the partially synchronous (or asynchronous) model where honest messages are subject to unpredictable adversarial delays. In this paper, we show that more nuanced formal models exist beyond the traditional synchrony and asynchrony stratification -- and interestingly, such new models allow us to articulate new robustness properties that traditional models would have failed to capture. More specifically, we articulate a new formal model called “the sleepy model of consensus”, where we classify honest nodes as being either alert or sleepy. Alertness implies that the node is online and has good network connections; whereas sleepiness captures any type of failure or network jitter. We then describe the Sleepy consensus protocol that achieves security as long as at any time, the number of alert nodes outnumber corrupt ones. No classical synchronous or asynchronous protocols attain such robustness guarantees, and yet we show how to leverage Nakamoto’s blockchain protocol, but without proofs-of-work, to achieve these properties, assuming collision resistant hash functions, the existence of a public-key infrastructure and a common reference string.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
consensusblockchainsdistributed systemscryptocurrencymodeling
Contact author(s)
runting @ gmail com
History
2017-05-11: last of 5 revisions
2016-09-22: received
See all versions
Short URL
https://ia.cr/2016/918
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/918,
      author = {Rafael Pass and Elaine Shi},
      title = {The Sleepy Model of Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2016/918},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/918}},
      url = {https://eprint.iacr.org/2016/918}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.