Paper 2023/154

FIN: Practical Signature-Free Asynchronous Common Subset in Constant Time

Sisi Duan, Tsinghua University
Xin Wang, Tsinghua University
Haibin Zhang, Beijing Institute of Technology

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. In this paper, 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. Moreover, as a key ingredient of our new ACS framework and an interesting primitive in its own right, we provide the first information-theoretic multivalued validated Byzantine agreement (MVBA) protocol with $O(1)$ time and $O(n^3)$ messages. Both results can improve---asymptotically and concretely---various applications using ACS and MVBA in the information-theoretic, quantum-safe, or signature-free settings. As an example, we implement FIN, a BFT protocol instantiated using our framework. Via a 121-server deployment on Amazon EC2, we show FIN is significantly more efficient than PACE (CCS 2022), the state-of-the-art asynchronous BFT protocol of the same type. In particular, FIN reduces the overhead of the ABA phase to as low as 1.23% of the total runtime, and FIN achieves up to 3.41x the throughput of PACE. We also show that FIN outperforms other BFT protocols with the standard liveness property such as Dumbo and Speeding Dumbo.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
Asynchronous common subsetACSBFTByzantine fault toleranceagreement on a subsetMVBAMPCADKG
Contact author(s)
duansisi @ tsinghua edu cn
wangxin87 @ mail tsinghua edu cn
bchainzhang @ aliyun com
2023-07-29: revised
2023-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sisi Duan and Xin Wang and Haibin Zhang},
      title = {FIN: Practical Signature-Free Asynchronous Common Subset in Constant Time},
      howpublished = {Cryptology ePrint Archive, Paper 2023/154},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.