Paper 2025/1404
Optimistic Message Dissemination
, Lucerne University of Applied Sciences and Arts, Web3 Foundation, Primev, PartisiaAbstract
Message dissemination is a fundamental building block in distributed systems and guarantees that any message sent eventually reaches all parties. State of the art provably secure protocols for disseminating messages have a per-party communication complexity that is linear in the inverse of the fraction of parties that are guaranteed to be honest in the worst case. Unfortunately, this per-party communication complexity arises even in cases where the actual fraction of parties that behave honestly is close to 1. In this paper, we propose an optimistic message dissemination protocol that adopts to the actual conditions in which it is deployed, with optimal worst-case per-party communication complexity. Our protocol cuts the complexity of prior provably secure protocols for 49% worst-case corruption almost in half under optimistic conditions and allows practitioners to combine efficient heuristics with secure fallback mechanisms.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. 7th Conference on Advances in Financial Technologies (AFT 2025)
- Keywords
- floodingmessage disseminationoptimistic
- Contact author(s)
-
chen-da liuzhang @ hslu ch
christian @ primev xyz
soren eller thomsen @ partisia com - History
- 2025-08-03: approved
- 2025-08-01: received
- See all versions
- Short URL
- https://ia.cr/2025/1404
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1404,
author = {Chen-Da Liu-Zhang and Christian Matt and Søren Eller Thomsen},
title = {Optimistic Message Dissemination},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1404},
year = {2025},
url = {https://eprint.iacr.org/2025/1404}
}
