Paper 2022/255

Round-Optimal Byzantine Agreement

Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang

Abstract

Byzantine agreement is a fundamental primitive in cryptography and distributed computing, and minimizing its round complexity is of paramount importance. It is long known that any randomized $r$-round protocol must fail with probability at least $(c\cdot r)^{-r}$, for some constant $c$, when the number of corruptions is linear in the number of parties, $t = \theta(n)$. On the other hand, current protocols fail with probability at least $2^{-r}$. Whether we can match the lower bound agreement probability remains unknown. In this work, we resolve this long-standing open question. We present a protocol that matches the lower bound up to constant factors. Our results hold under a (strongly rushing) adaptive adversary that can corrupt up to $t = (1-\epsilon)n/2$ parties, and our protocols use a public-key infrastructure and a trusted setup for unique threshold signatures. This is the first protocol that decreases the failure probability (overall) by a 'super-constant' factor per round.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2022
Keywords
Byzantine agreementoptimalround complexity
Contact author(s)
chendaliu @ gmail com
History
2022-03-02: received
Short URL
https://ia.cr/2022/255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/255,
      author = {Diana Ghinea and Vipul Goyal and Chen-Da Liu-Zhang},
      title = {Round-Optimal Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2022/255},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/255}},
      url = {https://eprint.iacr.org/2022/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.