On the Amortized Communication Complexity of Byzantine Broadcast
On the Amortized Communication Complexity of Byzantine Broadcast
复制标题
DOI：
10.1145/3583668.3594596
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Jun Wan;Atsuki Momose;Ling Ren;E. Shi;Zhuolun Xiang
中科院分区：
文献类型：
--
作者：
Jun Wan;Atsuki Momose;Ling Ren;E. Shi;Zhuolun Xiang
设计一个有效的拜占庭广播解决方案是许多分布式计算和加密任务的重要问题。在理论上和实践中，人们已经从多个方向尝试实现次二次通信复杂度，各有利弊。本文开始研究另一种尝试：提高多镜头拜占庭广播的平摊通信复杂度。也就是说，当我们有连续的多个广播实例时，我们试图提高平均成本。我们提出了一个在诚实多数条件下实现最优平摊线性复杂度的协议。我们的核心技术是通过跟踪多个实例上的不诚实行为，有效地形成一个传播发送者信息的网络。我们还将该技术推广到不诚实多数，以实现平摊的二次通信复杂度。
Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.