International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Round Complexity of Randomized Byzantine Agreement

Authors:
Ran Cohen
Iftach Haitner
Nikolaos Makriyannis
Matan Orland
Alex Samorodnitsky
Download:
DOI: 10.1007/s00145-022-09421-7
Search ePrint
Search Google
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)$$ 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)$$ 1 - Θ ( 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)$$ 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.
BibTeX
@article{jofc-2022-32799,
  title={On the Round Complexity of Randomized Byzantine Agreement},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={35},
  doi={10.1007/s00145-022-09421-7},
  author={Ran Cohen and Iftach Haitner and Nikolaos Makriyannis and Matan Orland and Alex Samorodnitsky},
  year=2022
}