Paper 2023/1549
Signature-Free Atomic Broadcast with Optimal $O(n^2)$ Messages and $O(1)$ Expected Time
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)
- 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
-
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} }