Paper 2019/868

On the Round Complexity of Randomized Byzantine Agreement

Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, 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 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. DISC 2019
Keywords
Byzantine agreementlower boundround complexity
Contact author(s)
cohenran @ idc ac il
iftachh @ cs tau ac il
n makriyannis @ gmail com
matanorland @ mail tau ac il
salex @ cs huji ac il
History
2022-02-12: last of 3 revisions
2019-07-30: received
See all versions
Short URL
https://ia.cr/2019/868
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/868,
      author = {Ran Cohen and Iftach Haitner and Nikolaos Makriyannis and Matan Orland and Alex Samorodnitsky},
      title = {On the Round Complexity of Randomized Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2019/868},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/868}},
      url = {https://eprint.iacr.org/2019/868}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.