[Resource Topic] 2022/255: Round-Optimal Byzantine Agreement

Welcome to the resource topic for 2022/255

Round-Optimal Byzantine Agreement

Authors: Diana Ghinea, Vipul Goyal, Chen-Da Liu-Zhang


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.

ePrint: https://eprint.iacr.org/2022/255

Talk: https://www.youtube.com/watch?v=abb2tE7oEPQ

Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/155/slides.pdf

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 .