Paper 2025/1738

Optimal Byzantine Agreement in the Presence of Message Drops

Zhenliang Lu, City University of Hong Kong

Qiang Tang, University of Sydney

Yuchen Ye, University of Sydney

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.

@misc{cryptoeprint:2025/1738,
      author = {Hanwen Feng and Zhenliang Lu and Qiang Tang and Yuchen Ye},
      title = {Optimal Byzantine Agreement in the Presence of Message Drops},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1738},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1738}
}