### Synchronous Consensus with Optimal Asynchronous Fallback Guarantees

Erica Blum, Jonathan Katz, and Julian Loss

##### 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 $\Delta$ 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 < t_a < n/3 \leq t_s < n/2$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that (1) is resilient to $t_s$ corruptions when run in a synchronous network and (2) remains resilient to $t_a$ 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 $t_a + 2\cdot t_s < n$.

Note: Minor fix in BA protocol

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2019
Keywords
Byzantine agreement
Contact author(s)
jkatz2 @ gmail com
History
2021-09-27: last of 5 revisions
See all versions
Short URL
https://ia.cr/2019/692

CC BY

BibTeX

@misc{cryptoeprint:2019/692,
author = {Erica Blum and Jonathan Katz and Julian Loss},
title = {Synchronous Consensus with Optimal Asynchronous Fallback Guarantees},
howpublished = {Cryptology ePrint Archive, Paper 2019/692},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/692}},
url = {https://eprint.iacr.org/2019/692}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.