Sweeper: Breaking the Validity-Latency Tradeoff in Asynchronous Common Subset
Guoyu Yang, Chang Chen, Qi Chen, Jianan Jiang, Jin Li, Debiao He · IEEE Transactions on Information Forensics and Security · 2024
Asynchronous common subset (ACS) is an essential building block for Byzantine fault-tolerance and multi-party computation. The classic ACS framework is due to Ben-Or, Kemler, and Rabin (BKR), consisting of${n}$reliable broadcast (RBC) instances and${n}$asynchronous binary agreement (ABA) instances (where${n}$is the total number of replicas). Despite recent progresses of practical BKR-ACS, the state-of-the-art designs are still trapped by a validity-latency tradeoff. In this paper, we propose Sweeper, a new ACS protocol that breaks the tradeoff, achieving optimal validity and latency. Moreover, Sweeper maintains other benefits including optimal resilience, signature-free, and information-theoretic settings. Sweeper is built on RBC and composable biased reproposable ABA (CBiased RABA). Different from the conventional RABA, CBiased RABA allows replicas to be more biased towards specific RABA instances. We provide generic strategies to transform existing ABA/RABA protocols and a new RABA protocol that we introduce, to CBiased RABA. Furthermore, Sweeper can achieve up to$2 \times $the throughput of PACE-ACS (CCS 2022), the state-of-the-art ACS protocol that follows the BKR-ACS framework.