Byzantine agreements tolerate reordered messages with new security limits
Scalable Composition of Byzantine Agreements under Reorder Attacks
Cryptography and SecurityData Structures and Algorithms
Summary
Byzantine agreement helps computers agree even if some parts act wrongly. The authors found that messing with message order in the network can break many agreements. They created a new way to think about attacks that change message order and party behavior together. They also proved exactly when agreement is possible or impossible with these combined attacks. Finally, they designed methods to safely run many agreements at once without much extra communication cost.
What this means in practice
- •For blockchain developers: Design blockchain protocols that remain secure when messages are reordered across multiple consensus instances.
- •For distributed system engineers: Build fault-tolerant distributed services that resist combined attacks on parties and network message order.
A theory result. No direct application yet.
Authors
Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, Wentao Zhou
Abstract
Byzantine agreement (BA) is a foundational building block in distributed systems, and the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol's security guarantees, In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when $n \leq 3t$ or $n \leq 2c + 2t + 1$, where $t$ and $c$ denote the number of corrupted parties and communication channels, respectively, and $n$ is the number of parties. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when $n > \max\{3t, 2c+2t+1\}$. We first provide general black-box compilers that transform any single-instance secure BA protocol into one that is secure under parallel and concurrent executions without additional security assumptions. To optimize performance, we further design refined compilers using erasure-correcting codes. These refined versions significantly reduce communication overhead, particularly for long messages, where they achieve a constant multiplicative overhead compared with the original protocol, thus achieving the same asymptotic communication complexity.