International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Round-Optimal Byzantine Agreement

Diana Ghinea , ETH Zurich
Vipul Goyal , Carnegie Mellon University and NTT Research
Chen-Da Liu-Zhang , Carnegie Mellon University
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
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 \emph{super-constant} factor per round.
Video from EUROCRYPT 2022
  title={Round-Optimal Byzantine Agreement},
  author={Diana Ghinea and Vipul Goyal and Chen-Da Liu-Zhang},