**Round Complexity of Byzantine Agreement, Revisited**

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

**Abstract: **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).

**Category / Keywords: **foundations / byzantine agreement, consensus

**Date: **received 1 Aug 2019

**Contact author: **runting at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20190805:221637 (All versions of this report)

**Short URL: **ia.cr/2019/886

[ Cryptology ePrint archive ]