As the first Byzantine fault-tolerant (BFT) protocol with linear communication complexity, HotStuff (PODC 2019) has received significant attention. HotStuff has three round-trips for both normal case operations and view change protocols. Follow-up studies attempt to reduce the number of phases for HotStuff. However, most studies give up on one thing in return for another. This paper extends our previous work Marlin (DSN 2022) to Pike, another BFT protocol with two phases and linear communication complexity. Both Pike and Marlin use the same cryptographic tools as in HotStuff and introduce no additional assumptions. Marlin has a more efficient view change (i.e., leader election) protocol but a more complicated data structure. Pike further simplifies the data structure at the cost of longer view changes in extreme cases. We implement the Pike, Marlin, HotStuff, and HotStuff-2, showing that both Pike and Marlin outperform HotStuff in normal case operations.

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$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$\sim$64 replicas, the parallel ABA phase occupies about 95%$\sim$97% of the total runtime. 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. 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. 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.