Paper 2023/1549

Signature-Free Atomic Broadcast with Optimal O(n2) Messages and O(1) Expected Time

Xiao Sui, Shandong 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(n2) 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
Preprint.
Keywords
atomic broadcastByzantine fault tolerancesignature-free
Contact author(s)
suixiao @ mail sdu edu cn
wangxin87 @ tsinghua edu cn
duansisi @ tsinghua edu cn
History
2024-05-08: revised
2023-10-09: received
See all versions
Short URL
https://ia.cr/2023/1549
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.