Welcome to the resource topic for 2022/052
Title:
Near-optimal Balanced Reliable Broadcast and Asynchronous Verifiable Information Dispersal
Authors: Sourav Das, Zhuolun Xiang, 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.
ePrint: https://eprint.iacr.org/2022/052
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .