2026-07-25T12:18:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22550 2025-10-02T11:05:57Z ddc:004 open_access

Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary Albouy, Timothé Frey, Davide Gelles, Ran Hazay, Carmit Raynal, Michel Schiller, Elad Michael Taïani, François Zikas, Vassilis Asynchronous message-passing Byzantine fault-tolerance Message adversary Reliable broadcast Erasure-correction codes {Threshold} signatures {Vector commitments} We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothé Albouy and Davide Frey and Ran Gelles and Carmit Hazay and Michel Raynal and Elad Michael Schiller and François Taïani and Vassilis Zikas 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.14 urn:nbn:de:0030-drops-225503 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode