**On the Round Complexity of Randomized Byzantine Agreement**

*Ran Cohen and Iftach Haitner and Nikolaos Makriyannis and Matan Orland and Alex Samorodnitsky*

**Abstract: **We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that:

(1) BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate (under attack) at the end of the first round with probability at most $o(1)$ [resp., $1/2+ o(1)$].

(2) BA protocols resilient against $n/4$ corruptions terminate at the end of the second round with probability at most $1-\Theta(1)$.

(3) For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate at the end of the second round with probability at most $o(1)$ [resp., $1/2 + o(1)$].

The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI).

The third bound essentially matches the recent protocol of Micali (ITCS'17) that tolerates up to $n/3$ corruptions and terminates at the end of the third round with constant probability.

**Category / Keywords: **cryptographic protocols / Byzantine agreement; lower bound; round complexity

**Original Publication**** (with major differences): **DISC 2019

**Date: **received 25 Jul 2019, last revised 31 Jul 2019

**Contact author: **rancohen at ccs neu edu,iftachh@cs tau ac il,n makriyannis@gmail com,matanorland@mail tau ac il,salex@cs huji ac il

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

**Version: **20190731:210013 (All versions of this report)

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

[ Cryptology ePrint archive ]