Paper 2025/779

Towards Reliable Broadcast with Optimal Communication and Round Complexity

Abstract

The reliable broadcast protocol with the best communication complexity for long messages to date is the MiniCast protocol of Locher & Shoup (2024). To reliably broadcast a message m to n parties, MiniCast has communication complexity ~ 1.5|m|n when the size |m| of m is large. However, the round complexity of MiniCast is 4, which is worse than the 3 rounds of the classical protocol of Bracha. We give a new reliable broadcast protocol whose communication complexity is essentially the same as that of MiniCast, but whose round complexity is just 3. For large |m|, the communication complexity of our new protocol is essentially optimal (for 3-round protocols with sufficiently well-balanced communication). Like MiniCast, our new protocol does not rely on any cryptography other than hash functions. We also give two new 2-round protocols that rely on signatures. The communication complexity of the first protocol is also ~ 1.5|m| n, unless the sender provably misbehaves, in which case its communication complexity may degrade to at most ~ 2|m|n. The communication complexity of the second protocol is ~ 1.5|m|n, even in the worst case, but (unlike our other protocols) the communication is unbalanced.

Note: (1) 2025-05-01: initial version. (2) 2025-10-03: changed title (originally "Improving the Round Complexity of MiniCast"); added new protocol UB-MiniCast; changed protocol names [Opt]MiniCast' to [Opt]MiniCast*.