FIN: Practical Signature-Free 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. However, the BKR protocol 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 64 replicas, the parallel ABA phase occupies about 95% 97% of the total runtime in BKR. 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.