10 February 2026 in IEEE Transactions on Dependable and Secure Computing
Byzantine Fault-tolerant State Machine Replication (BFT SMR) is essential for ensuring the security of high-level services such as blockchain, particularly in scenarios where a subset of nodes may exhibit arbitrary faults. As Byzantine Fault-tolerant broadcast in asynchronous networks is a core component of BFT SMR, this paper studies this broadcast primitive. We propose a novel broadcast protocol in which nodes encode large messages $M$ using erasure codes, aggregate the encoded codewords into a vector via a Bloom filter, and employ error correction codes to encode the vector. This approach achieves the known lower bound on the communication complexity of $O(|M|n+\kappa n^{2})$, where $\kappa$ represents the output size of a collision-resistant hash function and $n$ is the total number of nodes. Performance tests in the Amazon cloud environment demonstrate that when nodes broadcast large messages ($|M|\gg \kappa n^{2}$), the throughput of the new protocol is twice that of existing solutions. Furthermore, the Bloom filter enables the broadcast protocol to possess customizable features for the first time, allowing developers to reduce communication costs through parameter tuning.