Safe Permissionless Consensus

Youer Pu; Lorenzo Alvisi; Ittay Eyal

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/796

Safe Permissionless Consensus

Youer Pu, Cornell University

Lorenzo Alvisi, Cornell University

Ittay Eyal, Technion – Israel Institute of Technology

Abstract

Nakamoto's consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: Consensus Permissionless Nakamoto Deterministic Safety
Contact author(s): yp348 @ cornell edu
la13 @ cornell edu
ittay @ technion ac il
History: 2022-08-23: last of 2 revisions; 2022-06-20: received; See all versions
Short URL: https://ia.cr/2022/796
License: CC BY

BibTeX

@misc{cryptoeprint:2022/796,
      author = {Youer Pu and Lorenzo Alvisi and Ittay Eyal},
      title = {Safe Permissionless Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2022/796},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/796}},
      url = {https://eprint.iacr.org/2022/796}
}