Welcome to the resource topic for
**2019/868**

**Title:**

On the Round Complexity of Randomized Byzantine Agreement

**Authors:**
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, 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 a fraction of corruptions greater than 1/4 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 a fraction of corruptions greater than 1/3 [resp., 1/4] 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.

**ePrint:**
https://eprint.iacr.org/2019/868

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .