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 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 \(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)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Byzantine Protocols with Asymptotically Optimal Communication Complexity

  • Hanzheng Lyu,
  • Shaokang Xie,
  • Jianyu Niu,
  • Chen Feng

摘要

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 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 \(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)\) .