### Asymptotically Optimal Message Dissemination with Applications to Blockchains

##### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
blockchain flooding blockchain multicast network layer
Contact author(s)
chen-da liuzhang @ ntt-research com
cm @ concordium com
sethomsen @ cs au dk
History
2022-12-14: approved
See all versions
Short URL
https://ia.cr/2022/1723

CC BY

BibTeX

@misc{cryptoeprint:2022/1723,
author = {Chen-Da Liu-Zhang and Christian Matt and Søren Eller Thomsen},
title = {Asymptotically Optimal Message Dissemination with Applications to Blockchains},
howpublished = {Cryptology ePrint Archive, Paper 2022/1723},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1723}},
url = {https://eprint.iacr.org/2022/1723}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.