Paper 2022/1723

Asymptotically Optimal Message Dissemination with Applications to Blockchains

Chen-Da Liu-Zhang, NTT Research
Christian Matt, Concordium
Søren Eller Thomsen, Aarhus University

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)
Cryptographic protocols
Publication info
blockchain flooding blockchain multicast network layer
Contact author(s)
chen-da liuzhang @ ntt-research com
cm @ concordium com
sethomsen @ cs au dk
2022-12-14: approved
2022-12-14: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.