Paper 2022/608

Practical Provably Secure Flooding for Blockchains

Chen-Da Liu-Zhang
Christian Matt
Ueli Maurer
Guilherme Rito
Søren Eller Thomsen
Abstract

In recent years, permisionless blockchains have received a lot of attention both from industry and academia, where substantial effort has been spent to develop consensus protocols that are secure under the assumption that less than half (or a third) of a given resource (e.g., stake or computing power) is controlled by corrupted parties. The security proofs of these consensus protocols usually assume the availability of a network functionality guaranteeing that a block sent by an honest party is received by all honest parties within some bounded time. To obtain an overall protocol that is secure under the same corruption assumption, it is therefore necessary to combine the consensus protocol with a network protocol that achieves this property under that assumption. In practice, however, the underlying network is typically implemented by flooding protocols that are not proven to be secure in the setting where a fraction of the considered total weight can be corrupted. This has led to many so-called eclipse attacks on existing protocols and tailor-made fixes against specific attacks. To close this apparent gap, we present the first practical flooding protocol that provably delivers sent messages to all honest parties after a logarithmic number of steps. We prove security in the setting where all parties are publicly assigned a positive weight and the adversary can corrupt parties accumulating up to a constant fraction of the total weight. This can directly be used in the proof-of-stake setting, but is not limited to it. To prove the security of our protocol, we combine known results about the diameter of Erdős–Rényi graphs with reductions between different types of random graphs. We further show that the efficiency of our protocol is asymptotically optimal. The practicality of our protocol is supported by extensive simulations for different numbers of parties, weight distributions, and corruption strategies. The simulations confirm our theoretical results and show that messages are delivered quickly regardless of the weight distribution, whereas protocols that are oblivious of the parties' weights completely fail if the weights are unevenly distributed. Furthermore, the average message complexity per party of our protocol is within a small constant factor of such a protocol.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
blockchain flooding multicast network layer
Contact author(s)
chendaliu @ gmail com
cm @ concordium com
maurer @ inf ethz ch
gteixeir @ inf ethz ch
sethomsen @ cs au dk
History
2022-09-28: last of 2 revisions
2022-05-23: received
See all versions
Short URL
https://ia.cr/2022/608
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/608,
      author = {Chen-Da Liu-Zhang and Christian Matt and Ueli Maurer and Guilherme Rito and Søren Eller Thomsen},
      title = {Practical Provably Secure Flooding for Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2022/608},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/608}},
      url = {https://eprint.iacr.org/2022/608}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.