In the problem of byzantine agreement (BA), n parties wish to agree on a value by jointly running a distributed protocol. The protocol is deemed secure if it achieves this goal in spite of a malicious adversary that corrupts a certain fraction of the parties and can make them behave in arbitrarily malicious ways. Since its first formalization by Lamport et al., the problem of BA has been extensively studied in the literature under many different assumptions. One common way to classify protocols for BA is by their synchrony and network assumptions. For example, some protocols offer resilience against up to f<n/2 corrupted parties by assuming a synchronized, but possibly slow, network, in which parties share a global clock and messages are guaranteed to arrive after a given time. By comparison, other protocols achieve much higher efficiency and work without these assumptions, but can tolerate only f<n/3 corrupted parties. A natural question is whether it is possible to combine protocols from these two regimes to achieve the "best of both worlds": protocols that are both efficient *and* robust. In this work, we answer this question in the affirmative.

 

Concretely, we make the following contributions:

- We give the first generic compilers that combine BA protocols under different network and synchrony assumptions and preserve both their efficiency and robustness. Our constructions are simple and rely solely on a secure signature scheme.

- We prove that our constructions achieve optimal corruption bounds.

- Finally, we give the first efficient protocol for asynchronous byzantine agreement (ABA) that tolerates *adaptive* corruptions and matches the communication complexity of the best protocols in the static-corruption case.