Welcome to the resource topic for 2020/590
Title:
Expected Constant Round Byzantine Broadcast under Dishonest Majority
Authors: Jun Wan, Hanshen Xiao, Elaine Shi, Srinivas Devadas
Abstract:Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes n. However, whether we can match the expected constant round complexity in the corrupt majority setting — or more precisely, when f \geq n/2 + \omega(1) — remains unknown, where f denotes the number of corrupt nodes. In this paper, we are the first to resolve this long-standing question. We show how to achieve BB in expected O((n/(n-f))^2) rounds. Our results hold under both a static adversary and a weakly adaptive adversary who cannot perform ``after-the-fact removal’’ of messages already sent by a node before it becomes corrupt.
ePrint: https://eprint.iacr.org/2020/590
Talk: https://www.youtube.com/watch?v=BNhUx8EJaBY
Slides: https://iacr.org/submit/files/slides/2020/tcc/tcc2020/124/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 .