Paper 2022/776

Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation

Nicolas Alhaddad, Boston University
Sourav Das, University of Illinois Urbana-Champaign
Sisi Duan, Tsinghua University
Ling Ren, University of Illinois Urbana-Champaign
Mayank Varia, Boston University
Zhuolun Xiang, University of Illinois Urbana-Champaign
Haibin Zhang, Beijing Institute of Technology

This paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for $n$ nodes and input message $M$ that has communication cost $O(n|M|+n^2\log n)$, which is near-optimal due to the lower bound of $\Omega(n|M|+n^2)$. The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation: We propose a new construction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message $M$ while other nodes only needs to multicast coded fragments of size $O(|M|/n + \log n)$. The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM PODC 2022
Asynchronous Networks Reliable Broadcast Communication Complexity Computation Complexity Lower Bounds
Contact author(s)
nhaddad @ bu edu
souravd2 @ illinois edu
duansisi @ tsinghua edu cn
renling @ illinois edu
varia @ bu edu
xiangzl @ illinois edu
haibin @ bit edu cn
2022-06-16: approved
2022-06-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Alhaddad and Sourav Das and Sisi Duan and Ling Ren and Mayank Varia and Zhuolun Xiang and Haibin Zhang},
      title = {Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/776},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.