Reducing Round Complexity of Byzantine Broadcast

Linda Chen; Jun Wan

Paper 2020/1352

Reducing Round Complexity of Byzantine Broadcast

Linda Chen and Jun Wan

Abstract

Byzantine Broadcast is an important topic in distributed systems and improving its round complexity has long been a focused challenge. Under honest majority, the state of the art for Byzantine Broadcast is 10 rounds for a static adversary and 16 rounds for an adaptive adversary. In this paper, we present a Byzantine Broadcast protocol with expected 8 rounds under a static adversary and expected 10 rounds under an adaptive adversary. We also generalize our idea to the dishonest majority setting and achieve an improvement over existing protocols.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Broadcast Distributed systems Byzantine Agreement Consensus
Contact author(s): lindachen465 @ gmail com
History: 2020-10-29: received
Short URL: https://ia.cr/2020/1352
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1352,
      author = {Linda Chen and Jun Wan},
      title = {Reducing Round Complexity of Byzantine Broadcast},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1352},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1352}
}