Cryptology ePrint Archive: Report 2022/554

Byzantine Reliable Broadcast with $O(nL+kn+n^2 log n)$ Communication

Sisi Duan and Haibin Zhang

Abstract: Byzantine reliable broadcast (BRB) is one of the most fundamental primitives in fault-tolerant distributed computing. It is well-known that the best BRB protocol one can hope for has $O(nL+n^2)$ communication. It is unclear if this bound is achievable.

This paper provides a novel BRB protocol---BRB1, which achieves $O(nL + kn + n^2 log n)$ communication, where $n$, $L$, and $k$ are the number of replicas, the message length, and the security parameter, respectively. Our protocol is efficient, because the only building blocks we need are threshold signatures which have been used in various Byzantine fault-tolerant (BFT) protocols (e.g., SBFT, HoneyBadgerBFT, HotStuff). Our protocol is the first asynchronous BRB protocol that breaks the known $O(nL+kn^2)$ bound.

Category / Keywords: Byzantine reliable broadcast, BRB, broadcast, BFT, threshold signature, consistent broadcast

Date: received 6 May 2022, last revised 10 May 2022

Contact author: duansisi at tsinghua edu cn, haibin at bit edu cn

Available format(s): PDF | BibTeX Citation

Version: 20220510:082337 (All versions of this report)

Short URL: ia.cr/2022/554


[ Cryptology ePrint archive ]