You are looking at a specific version 20220214:153958 of this paper. See the latest version.

Paper 2022/052

Near-optimal Balanced Reliable Broadcast and Asynchronous Verifiable Information Dispersal

Sourav Das and 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 $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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Asynchronous NetworksReliable BroadcastCommunication ComplexityLower Bounds.
Contact author(s)
souravd2 @ illinois edu,renling @ illinois edu,xiangzl @ illinois edu
History
2022-02-14: revised
2022-01-18: received
See all versions
Short URL
https://ia.cr/2022/052
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.