Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n 2 ) bits. In synchronous networks, with a known upper bound on message delays, solutions with optimal O(n 2 ) bit complexity, optimal fault tolerance, and no cryptography have been established for over three decades. However, these solutions lack robustness under adverse network conditions. Therefore, research has increasingly focused on Byzantine agreement for partially synchronous networks, which behave synchronously only eventually and are thus more reflective of real-world conditions. Numerous solutions have been proposed for the partially synchronous setting. However, these solutions are notoriously hard to prove correct, and the most efficient cryptography-free algorithms still require O(n 3 ) exchanged bits in the worst case. Even with cryptography, the state-of-the-art remains a κ-bit factor away from the Ω(n 2 ) lower bound (where κ is the security parameter). This discrepancy between synchronous and partially synchronous solutions has remained unresolved for decades.

In this paper, we tackle the discrepancy above by introducing Oper, the first generic transformation of deterministic Byzantine agreement algorithms from synchrony to partial synchrony. Oper requires no cryptography, is optimally resilient (n ≥ 3t+1, where t is the maximum number of failures), and preserves the worst-case per-process bit complexity of the transformed synchronous algorithm. Leveraging Oper, we present the first partially synchronous Byzantine agreement algorithm that (1) achieves optimal O(n 2 ) bit complexity, (2) requires no cryptography, and (3) is optimally resilient (n ≥ 3t + 1), thus showing that the Dolev-Reischuk bound is tight even in partial synchrony. Moreover, we adapt Oper for long values and obtain several new partially synchronous algorithms with improved complexity and weaker (or completely absent) cryptographic assumptions. Finally, we demonstrate the broad applicability of the Oper transformation by showcasing its use for randomized synchronous agreement algorithms. Indirectly, Oper contradicts the folklore belief that there is a fundamental gap between synchronous and partially synchronous agreement protocols. In a way, we show that there is no inherent trade-off between the robustness of partially synchronous algorithms on the one hand, and the simplicity/efficiency of synchronous ones on the other hand.