Fast BB:一种具有平方通信复杂度和最优交互轮数的拜占庭广播协议  

Fast BB:A Byzantine Broadcast Protocol with Quadratic Communication Complexity and Optimal Communication Rounds

作　　者：郭凯文 庄严 胡可欣 韩将 GUO Kai-Wen;ZHUANG Yan;HU Ke-Xin;HAN Jiang(University of Chinese Academy of Sciences,Beijing 100049,China;Institute of Software,Chinese Academy of Sciences,Beijing 100190,China;China Mobile Internet Company Limited,Guangzhou 510510,China)

机构地区：[1]中国科学院大学,北京100049 [2]中国科学院软件研究所,北京100190 [3]中移互联网有限公司,广州510510

出　　处：《密码学报(中英文)》2025年第1期200-214,共15页Journal of Cryptologic Research

基　　金：国家重点研发计划(2022YFB2701600)。

摘　　要：拜占庭广播协议是分布式系统中的重要研究方向,近几年来作为关键组件被广泛应用在安全多方计算和区块链系统中.Abraham等人提出的Abraham’s BB协议是首个在良好情况下实现最优的2轮消息交互,且满足此情况下的最优容错阈值n=5f−1的半同步拜占庭广播协议.但Abraham’s BB协议在视图切换过程中的通信复杂度高达O(n3),使得节点之间的通信代价过高.针对上述情况,本文改进了Abraham’s BB协议,提出了一种新的拜占庭广播协议,称作Fast BB.Fast BB协议在保持良好情况下最优交互轮数和最优容错阈值的同时,实现了O(n^(2))的通信复杂度.本文对Fast BB协议进行了严谨的理论分析和安全证明,通过实验对比了Abraham’s BB协议和Fast BB协议的性能.实验结果表明,在节点规模为100的情况下,Fast BB协议的通信代价约为Abraham’s BB协议的5%,确认延迟约为10%.Byzantine broadcast is pivotal in distributed systems and has been widely used as a key component in secure multi-party computing and blockchain systems in recent years.Abraham et al.introduced Abraham’s BB,a partially synchronous Byzantine broadcast protocol,achieving optimal good-case latency of two rounds and optimal resilience of n=5f−1.However,Abraham’s BB exhibits high communication complexity of up to O(n3)during the view-change process,resulting in excessive communication costs between replicas.This study improves Abraham’s BB and proposes a new Byzantine broadcast protocol called Fast BB.Fast BB significantly reduces communication complexity to O(n^(2))while maintaining the optimal good-case communication rounds and fault tolerance.Fast BB is rigorously analyzed and the security proofs are provided.Furthermore,experiments are conducted to compare Abraham’s BB and Fast BB.The experimental results show that at a scale of 100 replicas,the communication cost of the Fast BB protocol is about 5%compared to Abraham’s BB,and the confirmation latency is about 10%.

关 键 词：分布式系统 拜占庭广播协议 通信复杂度 交互轮数 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]