View article

We address the problem of Reliable Broadcast in asynchronous message-passing systems with nodes, of which up to 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 an almost optimal amount of bits per node, where represents the length of the application message and is a security parameter. This improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Ta\"iani, SSS 2021), which incurs communication of bits per node. Our solution sends at most 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 message~. Instead, nodes forward authenticated fragments of the encoding of using an erasure-correcting code. Under the cryptographic assumptions of PKI and collision-resistant hash, and assuming , where the adversary drops at most~ messages per broadcast, our algorithm allows most of the correct nodes to reconstruct~, despite missing fragments caused by the malicious nodes and the message adversary.