Welcome to the resource topic for 2024/1108
Title:
Faster Asynchronous Blockchain Consensus and MVBA
Authors: Matthieu Rambaud
Abstract:Blockchain consensus, a.k.a. BFT SMR, are protocols enabling n processes to decide on an ever-growing chain. The fastest known asynchronous one is called 2-chain VABA (PODC’21 and FC’22), and is used as fallback chain in Abraxas* (CCS’23). It has a claimed 9.5\delta expected latency when used for a single shot instance, a.k.a. an MVBA.
We exhibit attacks breaking it. Hence, the title of the fastest asynchronous MVBA with quadratic messages complexity goes to sMVBA (CCS’22), with 10\delta expected latency.
Our positive contributions are two new and complementary designs.
\bullet 2PAC (2-phase asynchronous consensus). It has a simpler and lighter chaining than in previous approaches. Instantiated with either quadratic or cubic phases of voting, it yields:
2PAC$^\text{lean}: +90%$ throughput and 9.5\delta expected latency, with quadratic (O(n^2)) messages complexity. In both 2-chain VABA and sMVBA (as if chained, with pipelining), the quorum-certified transactions which were produced in the worst-case 1/3 of views with a slow leader were dumped, so the work was lost. The simpler design of 2PAC inserts such blocks in straight-line in the chain.
Thus, contrary to naive uncle-referencing, this comes with no computational overhead, yielding a net +50\% throughput gain over chained sMVBA. Both the remaining throughput and latency (-0.5\delta) gains, come from the lighter interactive construction of proofs of consistency appended to proposed blocks, compared to sMVBA.
2PAC$^\text{BIG}$: the fastest asynchronous blockchain consensus with cubic (O(n^3)) messages complexity. Fault-free single shot MVBA runs decide in just 4\delta, as soon as no message is delivered more than twice faster than others: GradedDAG (SRDS’23) required furthermore no messages reordering.
\bullet Super Fast Pipelined Blocks. This is an upgrade of previous approaches for pipelining: in 2-chain VABA, Cordial Miners (DISC’23) and GradedDAG, a block pipelined by a leader in the middle of the view had almost twice larger latency than the non-pipelined block. Our design provides a fast path deciding the pipelined block with even smaller latency than the non-pipelined block. The fast delay is guaranteed in all executions with a fair scheduler, but remarkably, whatever the behaviors of faulty processes. Consistency is preserved by a lightweight mechanism, of one threshold signature appended per proposal.
Instantiated with the previous protocols, it yields: s2PAC$^\text{lean}$, with fast decision of pipelined blocks in 4\delta; s2PAC$^\text{BIG}$, in 3\delta; and sGradedDAG, in 3\delta.
ePrint: https://eprint.iacr.org/2024/1108
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 .