Welcome to the resource topic for 2023/154
Title:
Practical Signature-Free Asynchronous Common Subset in Constant Time
Authors: Sisi Duan, Xin Wang, Haibin Zhang
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 (IT) 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 IT (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 IT-secure 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 IT, 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.
ePrint: https://eprint.iacr.org/2023/154
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .