Paper 2022/554

Byzantine Reliable Broadcast with $O(nL+kn+n^2 log n)$ Communication

Sisi Duan and Haibin Zhang

Abstract

Byzantine reliable broadcast (BRB) is one of the most fundamental primitives in fault-tolerant distributed computing. It is well-known that the best BRB protocol one can hope for has $O(nL+n^2)$ communication. It is unclear if this bound is achievable. This paper provides a novel BRB protocol---BRB1, which achieves $O(nL + kn + n^2 log n)$ communication, where $n$, $L$, and $k$ are the number of replicas, the message length, and the security parameter, respectively. Our protocol is efficient, because the only building blocks we need are threshold signatures which have been used in various Byzantine fault-tolerant (BFT) protocols (e.g., SBFT, HoneyBadgerBFT, HotStuff). Our protocol is the first asynchronous BRB protocol that breaks the known $O(nL+kn^2)$ bound.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Byzantine reliable broadcastBRBbroadcastBFTthreshold signatureconsistent broadcast
Contact author(s)
duansisi @ tsinghua edu cn
haibin @ bit edu cn
History
2022-05-10: revised
2022-05-10: received
See all versions
Short URL
https://ia.cr/2022/554
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/554,
      author = {Sisi Duan and Haibin Zhang},
      title = {Byzantine Reliable Broadcast with $O({nL}+kn+n^2 log n)$ Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/554},
      year = {2022},
      url = {https://eprint.iacr.org/2022/554}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.