Paper 2018/235

Combining Asynchronous and Synchronous Byzantine Agreement: The Best of Both Worlds

Julian Loss and Tal Moran


In the problem of byzantine agreement (BA), a set of n parties wishes to agree on a value v 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. (TOPLAS `82), 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 a one-half fraction of 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 D. By comparison, other protocols achieve much higher efficiency and work without these assumptions, but can tolerate only a one-third fraction of 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 the efficiency and robustness of their building blocks. 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 (binary) asynchronous byzantine agreement (ABA) which tolerates adaptive corruptions and matches the communication complexity of the best protocols in the static case.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Byzantine agreement
Contact author(s)
julian loss @ rub de
2018-06-19: last of 5 revisions
2018-03-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julian Loss and Tal Moran},
      title = {Combining Asynchronous and Synchronous Byzantine Agreement: The Best of Both Worlds},
      howpublished = {Cryptology ePrint Archive, Paper 2018/235},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.