Synchronous byzantine agreement with nearly a cubic number of communication bits

This paper studies the problem of Byzantine consensus in a synchronous message-passing system of n processes. The first deterministic algorithm, and also the simplest in its principles, was the Exponential Information Gathering protocol (EIG) proposed by Pease, Shostak and Lamport in [19]. The algorithm requires processes to send exponentially long messages. Many follow-up works reduced the cost of the algorithm. However, they had to either lower the maximum number of faulty processes t from the optimal range t < n/3 to some smaller range of t [4, 11, 18], or increase the maximum worst-case number of rounds needed for termination (the lower bound being t + 1) [3, 9, 20]. Garay and Moses were the first and only who solved the problem by using a polynomial number of communication bits, for the whole optimal range t < n/3 of the number of Byzantine processes and within the optimal number (t+1) of communication rounds. Their solution, though very complex and sophisticated, requires processes to send O(n⁹) bits in total. In this work, we present much simpler solution that also holds for the whole optimal range t < n/3 and the optimal number t + 1 of communication rounds, and at the same time lowers the number of exchanged communication bits to O(n³ log n). For achieving such an improvement, processes no more exchange relayed proposed values, but information on suspicions "who suspects who", the size of which is quadratic in n in the worst case.