Paper 2023/1738

Byzantine Agreement Decomposed: Honest Majority Asynchronous Atomic Broadcast from Reliable Broadcast

Simon Holmgaard Kamp, Aarhus University
Jesper Buus Nielsen, Aarhus University

It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this conceptually simple contribution by instantiating RB under various assumptions to get AB under the same assumptions. Using this framework we obtain the first asynchronous AB with sub-quadratic communication and optimal corruption threshold $t < n/3$, and the first network agnostic AB which is optimistically responsive. The latter result is secure in a relaxed synchronous model where parties locally decide timeouts and do not have synchronized clocks. Finally, we provide asynchronous ABs with covert security and mixed adversary structures.

Available format(s)
Publication info
Contact author(s)
kamp @ cs au dk
jbn @ cs au dk
2024-04-05: revised
2023-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Simon Holmgaard Kamp and Jesper Buus Nielsen},
      title = {Byzantine Agreement Decomposed: Honest Majority Asynchronous Atomic Broadcast from Reliable Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1738},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.