Byzantine Protocols with Asymptotically Optimal Communication Complexity

Byzantine Protocols with Asymptotically Optimal Communication Complexity

연구 분야: Networking

학회: International Conference on Security and Privacy in Communication Systems

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 bits for an -bit message to be agreed by a set of n replicas. 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 bits, where is determined by the security parameter . This communication complexity is optimal when reaches .