Cryptology ePrint Archive: Report 2020/590

Expected Constant Round Byzantine Broadcast under Dishonest Majority

Jun Wan and Hanshen Xiao and 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 $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. In particular, even when 99\% of the nodes are corrupt we can achieve expected constant 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.

Category / Keywords: cryptographic protocols / multicast, Byzantine Agreement

Date: received 19 May 2020, last revised 23 May 2020

Contact author: junwan at mit edu,runting@gmail com,devadas@csail mit edu,hsxiao@mit edu

Available format(s): PDF | BibTeX Citation

Version: 20200524:012713 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]