Practical Signature-Free Multivalued Validated Byzantine Agreement and Asynchronous Common Subset in Constant Time
- 9 September 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 74 (12) , 4138-4152
Abstract
Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. BKR ACS has an $O(\log n)$ running time (where $n$ is the number of replicas) due to the usage of $n$ parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16$\sim$ 64 replicas, the parallel ABA phase occupies about 95%$\sim$ 97% of the total runtime. A long-standing open problem is whether we can build an ACS framework with $O(1)$ time while not increasing the message or communication complexity of the BKR protocol. We resolve the open problem, presenting the first constant-time ACS protocol with $O(n^{3})$ messages in the information-theoretic and signature-free settings. Our key ingredient is the first information-theoretic and constant-time multivalued validated Byzantine agreement (MVBA) protocol. Our results can improve—asymptotically and concretely—various applications using ACS and MVBA. As an example, we implement FIN, a BFT protocol instantiated using our framework. Via a 121-server deployment on Amazon EC2, we show FIN reduces the overhead of the ABA phase to as low as 1.23% of the total runtime.
Keywords
Funding Information
- National Key R&D Program of China (2022YFB2701700)
This publication has 42 references indexed in Scilit:
- Shoal: Improving DAG-BFT Latency and Robustness2025
- How to achieve adaptive security for asynchronous BFT?Journal of Parallel and Distributed Computing, 2022
- Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time2015
- Asynchronous Byzantine Agreement with optimal resilienceDistributed Computing, 2013
- Vector Commitments and Their Applications2013
- Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using CryptographyJournal of Cryptology, 2005
- Resilient-optimal interactive consistency in constant timeDistributed Computing, 2003
- Secure and Efficient Asynchronous Broadcast Protocols2001
- More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous SystemsInformation and Computation, 1993
- Asynchronous Byzantine agreement protocolsInformation and Computation, 1987