Paper 2024/1108

Faster Asynchronous Blockchain Consensus

Abstract

The fastest asynchronous (block-chained) consensus protocols, a.k.a. BFT SMR, follow a design that dates back at least to AMS (Podc'19). AMS compiles any responsive consensus, $\Pi$, based on rotating proposers, into an asynchronous consensus. It is tempting to instantiate AMS with $\Pi$ equal to the fastest-known proposer-based consensus with quadratic complexity, which is 2-phase Hotstuff (2HS, Podc'19). However, we demonstrate a lack of liveness of AMS(2HS). The fastest known chained consensus, called 2-chain VABA (Podc'21 and FC'22), is a tweak of AMS intended to circumvent the livelessness of AMS(2HS). We describe attacks on its consistency and liveness, leading to the conclusion that the AMS approach is hopeless with 2HS. We introduce a new design, called 2PAC ({2-phase} asynchronous consensus), which modifies both the AMS design and the voting rule of the compiled consensus $\Pi$. Of independent interest, we then address the issue that, in all previous approaches (2-chain VABA, Cordial Miners (DISC'23), GradedDAG, LightDAG) a block pipelined by a leader in the middle of the view had almost twice larger latency than the non-pipelined block. We introduce a fast decision mechanism which decides the pipelined block (and all non-leader blocks referred to within) with even smaller latency than the non-pipelined block in a wide set of scenarios (even with faults and message reorderings). Instantiated over 2PAC it gives ``s2PAC''. Instantiating s2PAC with the appropriate modifications of, respectively, 2HS, and a DAG-ified version of Jolteon* (in production by Aptos), we obtain the fastest asynchronous consensus in their respective complexity classes: s2PAC$^\text{lean}$ (in $O(n^2)$, i.e., quadratic) and s2PAC$^\text{BIG}$-DAG ($O(n^3)$, i.e., cubic). Our large-scale experiments confirm their superiority over the state of the art, i.e., a chained version of (sMVBA, CCS'22) in $O(n^2)$; and (GradedDAG, SRDS'23) in $O(n^3)$.