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

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 signature-free asynchronous ABC protocol that achieves optimal $O(n^{2})$ messages and $O(1)$ expected time, where $n$ is the total number of replicas. Our ABC protocol adopts a new design, relying on a reduction from-perhaps surprisingly-a somewhat neglected primitive called multivalued Byzantine agreement (MBA).