Practical Signature-Free Multivalued Validated Byzantine Agreement and Asynchronous Common Subset in Constant Time

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 <inline-formula><tex-math notation="LaTeX">$O(\log n)$</tex-math></inline-formula> running time (where <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> is the number of replicas) due to the usage of <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16<inline-formula><tex-math notation="LaTeX">$\sim$</tex-math></inline-formula> 64 replicas, the parallel ABA phase occupies about 95%<inline-formula><tex-math notation="LaTeX">$\sim$</tex-math></inline-formula> 97% of the total runtime. A long-standing open problem is whether we can build an ACS framework with <inline-formula><tex-math notation="LaTeX">$O(1)$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$O(n^{3})$</tex-math></inline-formula> 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.