Consensus Under Adversary Majority Done Right
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912390891700224 |
|---|---|
| author | Sridhar, Srivatsan Tas, Ertem Nusret Neu, Joachim Zindros, Dionysis Tse, David |
| author_facet | Sridhar, Srivatsan Tas, Ertem Nusret Neu, Joachim Zindros, Dionysis Tse, David |
| contents | A specter is haunting consensus protocols--the specter of adversary majority. Dolev and Strong in 1983 showed an early possibility for up to 99% adversaries. Yet, other works show impossibility results for adversaries above 50% under synchrony, seemingly the same setting as Dolev and Strong's. What gives? It is high time that we pinpoint a key culprit for this ostensible contradiction: 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01689 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Consensus Under Adversary Majority Done Right Sridhar, Srivatsan Tas, Ertem Nusret Neu, Joachim Zindros, Dionysis Tse, David Cryptography and Security Distributed, Parallel, and Cluster Computing A specter is haunting consensus protocols--the specter of adversary majority. Dolev and Strong in 1983 showed an early possibility for up to 99% adversaries. Yet, other works show impossibility results for adversaries above 50% under synchrony, seemingly the same setting as Dolev and Strong's. What gives? It is high time that we pinpoint a key culprit for this ostensible contradiction: 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. |
| title | Consensus Under Adversary Majority Done Right |
| topic | Cryptography and Security Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2411.01689 |