Paper 2019/886

Round Complexity of Byzantine Agreement, Revisited

T-H. Hubert Chan, Rafael Pass, and Elaine Shi


Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. First, although expected constant-round protocols are known in the honest majority setting, it is unclear whether one has to settle for expected constant-round or whether there exist better protocols that are worst-case constant-round. Second, for the corrupt majority setting, the existence of sublinear-round BA protocols continues to ellude us except for the narrow regime when only sublinearly more than a half are corrupt. In this paper, we make a couple important steps forward in bridging this gap. We show two main results: - No (even randomized) protocol that completes in worst-case $o\left(\log(1/\delta)/\log \log(1/\delta)\right)$ rounds can achieve BA with $1-\delta$ probability, even when only 1% of the nodes are corrupt. In comparison, known expected constant-round, honest-majority protocols complete in $O(\log(1/\delta))$ rounds in the worst-case. Therefore, our lower bound is tight upto a $\log\log$ factor for the honest majority setting. - There exists a corrupt-majority BA protocol that terminates in $O(\log(1/\delta)/\epsilon)$ rounds in the worst case and tolerates $(1-\epsilon)$ fraction of corrupt nodes. Our upper bound is optimal upto a logarithmic factor in light of the elegant $\Omega(1/\epsilon)$ lower bound by Garay et al. (FOCS'07).

Available format(s)
Publication info
Preprint. MINOR revision.
byzantine agreementconsensus
Contact author(s)
runting @ gmail com
2019-08-05: received
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Rafael Pass and Elaine Shi},
      title = {Round Complexity of Byzantine Agreement, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/886},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.