Paper 2022/1723

Asymptotically Optimal Message Dissemination with Applications to Blockchains

Chen-Da Liu-Zhang, HSLU, Web3 Foundation
Christian Matt, Primev
Søren Eller Thomsen, Partisia
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 per-party communication complexity of $\Omega(l\cdot \gamma^{-1} \cdot (\log(n) + \kappa))$ bits to disseminate an $l$-bit message among $n$ parties with security parameter $\kappa$ when it is guaranteed that a $\gamma$ fraction of the parties remain honest. In this work, we present the first flooding protocols with a per-party communication complexity of $O(l\cdot \gamma^{-1})$ bits. We further show that this is asymptotically optimal and that our protocols can be instantiated provably securely in the usual setting for 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 a blockchain.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
Keywords
blockchainfloodingmulticastnetwork layer
Contact author(s)
chendaliu @ gmail com
christian @ primev xyz
s eller thomsen @ gmail com
History
2024-03-07: last of 2 revisions
2022-12-14: received
See all versions
Short URL
https://ia.cr/2022/1723
License
Creative Commons Attribution
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.