Paper 2024/1799

Consensus Under Adversary Majority Done Right

Srivatsan Sridhar, Stanford University
Ertem Nusret Tas, Stanford University
Joachim Neu, a16z Crypto Research
Dionysis Zindros, Common Prefix
David Tse, Stanford University
Abstract

A spectre is haunting consensus protocols—the spectre of adversary majority. The literature is inconclusive, with possibilities and impossibilities running abound. Dolev and Strong in 1983 showed an early possibility for up to 99% adversaries. Yet, we have known impossibility results for adversaries above 1/2 in synchrony, and above 1/3 in partial synchrony. What gives? It is high time that we pinpoint the culprit of this confusion: the critical role of the modeling details of clients. Are the clients sleepy or always-on? Are they silent or communicating? Can validators be sleepy too? We systematize models for consensus across four dimensions (sleepy/always-on clients, silent/communicating clients, sleepy/always-on validators, and synchrony/partial-synchrony), some of which are new, and tightly characterize the achievable safety and liveness resiliences with matching possibilities and impossibilities for each of the sixteen models. To this end, we unify folklore and earlier results, and fill gaps left in the literature with new protocols and impossibility theorems.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
svatsan @ stanford edu
nusret @ stanford edu
jneu @ a16z com
dionyziz @ commonprefix com
dntse @ stanford edu
History
2024-11-04: approved
2024-11-03: received
See all versions
Short URL
https://ia.cr/2024/1799
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2024/1799,
      author = {Srivatsan Sridhar and Ertem Nusret Tas and Joachim Neu and Dionysis Zindros and David Tse},
      title = {Consensus Under Adversary Majority Done Right},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1799},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1799}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.