Expected Constant Round Byzantine Broadcast under Dishonest Majority

Jun Wan; Hanshen Xiao; Elaine Shi; Srinivas Devadas

Paper 2020/590

Expected Constant Round Byzantine Broadcast under Dishonest Majority

Jun Wan, Hanshen Xiao, Elaine Shi, and 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 . However, whether we can match the expected constant round complexity in the corrupt majority setting --- or more precisely, when --- remains unknown, where 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 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. TCC 2020
Keywords: Multicast Byzantine Agreement
Contact author(s): junwan @ mit edu
runting @ gmail com
devadas @ csail mit edu
hsxiao @ mit edu
History: 2020-10-19: last of 2 revisions; 2020-05-22: received; See all versions
Short URL: https://ia.cr/2020/590
License: CC BY

BibTeX

@misc{cryptoeprint:2020/590,
      author = {Jun Wan and Hanshen Xiao and Elaine Shi and Srinivas Devadas},
      title = {Expected Constant Round Byzantine Broadcast under Dishonest Majority},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/590},
      year = {2020},
      url = {https://eprint.iacr.org/2020/590}
}