Cryptology ePrint Archive: Report 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.
Category / Keywords: cryptographic protocols / consensus, blockchains, distributed systems, cryptocurrency, modeling
Date: received 21 Sep 2016, last revised 15 Feb 2017
Contact author: runting at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20170216:013157 (All versions of this report)
Short URL: ia.cr/2016/918
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]