Paper 2022/052

Near-optimal Balanced Reliable Broadcast and Asynchronous Verifiable Information Dispersal

Sourav Das, Zhuolun Xiang, and Ling Ren


In this paper, we present near-optimal asynchronous Byzantine reliable broadcast (RBC) protocols with balanced costs and an improved asynchronous verifiable information dispersal (AVID) protocol. Assuming the existence of collision-resistant hash functions, our RBC protocol broadcasts a message $M$ among $n$ nodes with total communication cost $O(n|M|+\kappa n^2)$ and per-node communication cost $O(|M|+\kappa n)$. In contrast, the state-of-the-art reliable broadcast protocol either has per-node cost $O(|M|+\kappa \log n)$, or has imbalanced costs where the broadcaster incurs $O(n|M|)$ while other nodes incur a communication cost of $O(|M|+\kappa n)$. We also present an error-free RBC protocol that makes no computational assumption and has total communication cost $O(n|M|+ n^2\log n)$ and per-node communication cost $O(|M|+ n\log n)$. In contrast, the state-of-the-art error-free RBC protocol has total cost of $O(n|M|+ n^3\log n)$, and the broadcaster has imbalanced cost of $O(n|M|+ n^2\log n)$. We then use our new balanced RBC and additional techniques to design an asynchronous verifiable information dispersal (AVID) protocol with total dispersal cost $O(|M|+\kappa n^2)$, retrieval cost $O(|M|+\kappa n)$, and no trusted setup. In our AVID protocol, the client incurs a communication cost of $O(|M|+\kappa n)$ in comparison to $O(|M|+\kappa n\log n)$ of prior best. Moreover, each node in our AVID protocol incurs a storage cost of $O(|M|/n+\kappa)$ bits, in comparison to $O(|M|/n+\kappa \log n)$ bits of prior best. Finally, we present lower bound results on communication cost and show that our balanced RBC and AVID protocols have near-optimal communication costs -- only an factor of $O(\kappa)$ or $O(\log n)$ gap from the lower bounds.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Asynchronous NetworksReliable BroadcastCommunication ComplexityLower Bounds.
Contact author(s)
souravd2 @ illinois edu
renling @ illinois edu
xiangzl @ illinois edu
2022-02-14: revised
2022-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sourav Das and Zhuolun Xiang and Ling Ren},
      title = {Near-optimal Balanced Reliable Broadcast and Asynchronous Verifiable Information Dispersal},
      howpublished = {Cryptology ePrint Archive, Paper 2022/052},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.