Research Article
Byzantine Protocols with Asymptotically Optimal Communication Complexity
@INPROCEEDINGS{10.1007/978-3-031-64948-6_13, author={Hanzheng Lyu and Shaokang Xie and Jianyu Niu and Chen Feng}, title={Byzantine Protocols with Asymptotically Optimal Communication Complexity}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2024}, month={10}, keywords={Blockchain Byzantine agreement State machine replication Communication complexity Round complexity}, doi={10.1007/978-3-031-64948-6_13} }- Hanzheng Lyu
Shaokang Xie
Jianyu Niu
Chen Feng
Year: 2024
Byzantine Protocols with Asymptotically Optimal Communication Complexity
SECURECOMM
Springer
DOI: 10.1007/978-3-031-64948-6_13
Abstract
Byzantine agreement protocols are essential components in distributed systems and hold significant relevance for blockchain networks. However, the communication complexity of these protocols remains a major obstacle when considering their application in large-scale blockchain systems. Recently, several elegant Byzantine protocols in the synchronous authenticated setting have been proposed to enjoy expected constant round complexity or optimal good-case latency. However, their overall communication complexity is still(\varOmega (n^2 \ell ))bits for an(\ell )-bit message to be agreed by a set ofnreplicas. This quadratic communication complexity makes them unsuitable for large-scale applications. In this paper, we systematically aim to reduce the communication complexity of these protocols. In particular, we show how these protocols can be extended to have a complexity of(O(n\ell + n^2 \kappa ))bits, where(\kappa )is determined by the security parameter(\lambda ). This communication complexity is optimal when(\ell )reaches(\varOmega (\kappa n)).
