Paper 2025/1738

Optimal Byzantine Agreement in the Presence of Message Drops

Abstract

To more accurately capture real-world network and adversarial behaviors, recent research has explored Byzantine Agreement (BA) under various mixed-fault models. The breakthroughs by Loss et al. (TCC'23, TCC'24) have established the feasibility of optimally resilient BA in some of these models. Specifically, their protocols tolerate up to $t$ byzantine parties, $r$ receive faulty parties, and $s$ send faulty parties in a network of $n > 2t + r + s$ parties. Initially, Loss et al. (TCC'23) considers a model in which a party may be either receive faulty or send faulty but not at the same time (called the non-overlapping setting). The extended model in Loss et al. (TCC'24) further accommodates the \textit{overlapping setting}, where a party can simultaneously exhibit both receive faulty and send faulty behaviors. However, despite this flexibility, both protocols incur a prohibitively high communication cost of $O(n^5)$ bits, leaving open the fundamental question of whether the optimal $O(n^2)$-bit complexity achieved by many classical BA protocols is attainable in the optimally resilient mixed-fault model (with overlapping faults or not). In this work, we answer these open questions affirmatively. We present a mixed-fault BA protocol that achieves the optimal expected $O(n^2\lambda)$ communication complexity while maintaining expected $O(1)$ round complexity and optimal (rushing and strongly adaptive) resilience. Our protocol supports the strongest overlapping setting, while matching the best-known complexity of classical BA protocols. To achieve this, we develop a series of novel techniques, carefully designed to ensure efficient and secure agreement even under the mixed-fault model. Beyond binary BA, we extend our protocol to a multi-valued BA setting, achieving an expected $O(\tfrac{n^2}{t}L + n^2\lambda^2)$ communication complexity and an $O(1)$ expected round complexity, where $t$ is the number of byzantine faults and $L$ is the bit-length of the input values. In particular, for $t = O(n)$, the communication reduces to $O(nL + n^2\lambda^2)$. Notably, our protocols operate under the same setup and cryptographic assumptions as those in Loss et al.

Note: This revision presents an improved multi-valued BA protocol, reducing the round complexity from $O(\kappa)$ to $O(1)$, where $\kappa$ is the statistical security parameter. It also provides extended proofs, refined complexity analyses, and a more comprehensive preliminaries section.