Signature-Free Atomic Broadcast with Optimal $O(n^2)$ Messages and $O(1)$ Expected Time

Xiao Sui; Xin Wang; Sisi Duan

Paper 2023/1549

Signature-Free Atomic Broadcast with Optimal $O(n^2)$ Messages and $O(1)$ Expected Time

Xiao Sui

, Tsinghua University

Xin Wang, Tsinghua University

Sisi Duan

, Tsinghua University

Abstract

Byzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first information-theoretic (IT) and signature-free asynchronous ABC protocol that achieves optimal $O(n^2)$ messages and $O(1)$ expected time. Our ABC protocol adopts a new design, relying on a reduction from---perhaps surprisingly---a somewhat neglected primitive called multivalued Byzantine agreement (MBA).

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. IEEE Symposium on Security and Privacy 2025
Keywords: atomic broadcast Byzantine fault tolerance signature-free
Contact author(s): suixiao @ mail tsinghua edu cn
wangxin87 @ tsinghua edu cn
duansisi @ tsinghua edu cn
History: 2026-06-10: last of 3 revisions; 2023-10-09: received; See all versions
Short URL: https://ia.cr/2023/1549
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1549,
      author = {Xiao Sui and Xin Wang and Sisi Duan},
      title = {Signature-Free Atomic Broadcast with Optimal $O(n^2)$ Messages and $O(1)$ Expected Time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1549},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1549}
}