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

被引:10
作者
Alhaddad, Nicolas [1 ]
Das, Sourav [2 ]
Duan, Sisi [3 ]
Ren, Ling [2 ]
Varia, Mayank [1 ]
Xiang, Zhuolun [2 ]
Zhang, Haibin [4 ]
机构
[1] Boston Univ, Boston, MA USA
[2] Univ Illinois, Champaign, IL USA
[3] Tsinghua Univ, Beijing, Peoples R China
[4] Beijing Inst Technol, Beijing, Peoples R China
来源
PROCEEDINGS OF THE 2022 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2022 | 2022年
关键词
Asynchronous Networks; Reliable Broadcast; Communication Complexity; Computation Complexity; Lower Bounds; SHORT SIGNATURES;
D O I
10.1145/3519270.3538475
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.. nodes and input message.. that has communication cost O (n|M |+n(2) logn), which is nearoptimal 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 newconstruction 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.. while other nodes only needs to multicast coded fragments of size O(|M |/n + logn). 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.
引用
收藏
页码:399 / 417
页数:19
相关论文
共 47 条
[41]   POLYNOMIAL CODES OVER CERTAIN FINITE FIELDS [J].
REED, IS ;
SOLOMON, G .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1960, 8 (02) :300-304
[42]  
Reiter M. K., 1994, 2nd ACM Conference on Computer and Communications Security, P68, DOI 10.1145/191177.191194
[43]  
Shoup V, 2000, LECT NOTES COMPUT SC, V1807, P207
[44]  
Toueg S., 1984, P 3 ANN ACM S PRINC, P163, DOI DOI 10.1145/800222.806744
[45]  
Welch L. R., 1986, U.S. Patent
[46]  
Yurek Thomas, 2022, P 29 ANN NETWORK DIS
[47]  
Zhang Haibin, 2022, ACM CCS