Byzantine broadcast (BC) is a fundamental problem in distributed systems. To build communication-efficient BC protocols, erasure coding is a key tool. In systems under thefn/3 setting, wherenis the total number of parties (also called replicas) andfis the number of Byzantine failures, correct replicas can simply encode the data block through erasure coding, share data fragments, and interact to validate that the decoded data is consistent with the original data block. Such a paradigm is powerful in primitives such as BC, asynchronous verifiable information dispersal, and atomic broadcast. However, in systems with corrupt majority or even in thefn/2 setting, it becomes less straightforward to use erasure coding to build communication-efficient protocols. In this work, we introduce an erasure coding proof (ECP) system which allows the encoder to prove succinctly and non-interactively that an erasure-coded fragment is consistent with a constant-sized commitment to the original data block. Each fragment can be verified independently of the other fragments. We present two synchronous BC protocols from the ECP system, one under thefnassumption and one under thefn/2 assumption, where ϵ is a constant and ϵ ∈ (0, 1). Both protocols improve the communication complexity and time complexity compared to the state-of-the-art BC protocols.

This paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for n nodes and input message M that has communication cost O(n|M|+n2 logn), which is nearoptimal due to the lower bound of Ω(n|M|+n2). The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation:We propose a newconstruction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message M while other nodes only needs to multicast coded fragments of size O(|M|/n + logn). The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.

We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs -- only a factor of O(κ) gap from the lower bounds.