Paper 2022/052

Near-optimal Balanced Reliable Broadcast and Asynchronous Verifiable Information Dispersal

Sourav Das, Zhuolun Xiang, and Ling Ren

Abstract

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 $$, and the broadcaster has imbalanced cost of $$. We then use our new balanced RBC and additional techniques to design an asynchronous verifiable information dispersal (AVID) protocol with total dispersal cost $$, retrieval cost $$, and no trusted setup. In our AVID protocol, the client incurs a communication cost of $$ in comparison to $$ of prior best. Moreover, each node in our AVID protocol incurs a storage cost of $$ bits, in comparison to $$ 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 $$ or $$ gap from the lower bounds.