Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Broadcast, Distributed systems, Byzantine Agreement, Consensus

Date: received 26 Oct 2020

Contact author: lindachen465 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201029:145456 (All versions of this report)

Short URL: ia.cr/2020/1352