International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Synchronous Consensus with Optimal Asynchronous Fallback Guarantees

Authors:
Erica Blum
Jonathan Katz
Julian Loss
Download:
DOI: 10.1007/978-3-030-36030-6_6
Search ePrint
Search Google
Abstract: Typically, protocols for Byzantine agreement (BA) are designed to run in either a synchronous network (where all messages are guaranteed to be delivered within some known time Δ from when they are sent) or an asynchronous network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start.Fix some number of parties n, and 0<ta<n/3≤ts<n/2. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that is resilient to (1) ts corruptions when run in a synchronous network and (2) ta faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if ta+2⋅ts<n.
BibTeX
@article{tcc-2019-29970,
  title={Synchronous Consensus with Optimal Asynchronous Fallback Guarantees},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={131-150},
  doi={10.1007/978-3-030-36030-6_6},
  author={Erica Blum and Jonathan Katz and Julian Loss},
  year=2019
}