International Association
for Cryptologic Research

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 these settings. 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 that a party will be either receive faulty or send faulty but not at the same time (called {\em non-overlapping model}). The extended model in Loss et al.~(TCC'24) further accommodates the \textit{overlapping model}, where a party can simultaneously exhibit both receive faulty and send faulty behaviors. However, despite this flexibility, {\em both} protocols incur a prohibitively high $O(n^5)$-bit communication cost, 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 (strongly adaptive) resilience. Our protocol supports the strongest overlapping model, 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 mixed faults. Beyond binary BA, we extend our protocol to a multi-valued BA setting, achieving an expected communication complexity of $O(\frac{n^2}{t}L + n^2\lambda^2)$ and a round complexity of $O(\kappa)$, where $t$ is the number of byzantine faults, $L$ is the bit-length of the input values, $\lambda$ is the computational security parameter, and $\kappa$ is the statistical security parameter. 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.