Modular construction of a Byzantine agreement protocol with optimal message bit complexity

This paper presents a new Byzantine agreement protocol that tolerates t processor faults using 3t + 1 processors, t + o(t) rounds, O(t2) total message bits, and O(tɛ) maximum message size, for any ɛ > 0. The protocol is optimal or near optimal in all cost measures: the number of processors is optimal, the message bit complexity is optimal, the number of rounds exceeds the lower bound by o(t), and the maximum message size exceeds the lower bound by O(tɛ). The round complexity is uniformly better than 2·(t + 1) and thus is reasonable even for small t. This is the first Byzantine agreement protocol to have optimal message bit complexity. The new protocol is constructed by recursively applying a simple, yet general, transformation that changes the number of rounds, total message bits, and maximum message size required by a Byzantine agreement protocol, but preserves correctness, number of processor faults tolerated, and total number of processors. Each application of this new transformation reduces the number of message bits sent—at the expense of adding rounds of communication. Surprisingly, the base case of the recursive construction is the agreement protocol of Lamport, Shostak, and Pease, which has a number of message bits exponential in t