Welcome to the resource topic for 2022/1723
Title:
Asymptotically Optimal Message Dissemination with Applications to Blockchains
Authors: Chen-Da Liu-Zhang, Christian Matt, Søren Eller Thomsen
Abstract:Messages in large-scale networks such as blockchain systems are typically disseminated using flooding protocols, in which parties send the message to a random set of peers until it reaches all parties. Optimizing the communication complexity of such protocols and, in particular, the per-party communication complexity is of primary interest since nodes in a network are often subject to bandwidth constraints. Previous flooding protocols incur a communication complexity of \Omega(l\cdot n \cdot (\log(n) + \kappa)) bits to disseminate an l-bit message among n parties with security parameter \kappa. In this work, we present the first flooding protocols with optimal total communication complexity of O(l\cdot n) bits and per-party communication of O(l) bits. We further show how our protocols can be instantiated provably securely in proof-of-stake blockchains.
To demonstrate that one of our new protocols is not only asymptotically optimal but also practical, we perform several probabilistic simulations to estimate the concrete complexity for given parameters. Our simulations show that our protocol significantly improves the per-party communication complexity over the state-of-the-art for practical parameters. Hence, for given bandwidth constraints, our results allow to, e.g., increase the block size, improving the overall throughput of the blockchain.
ePrint: https://eprint.iacr.org/2022/1723
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 .