Shoal++: High Throughput DAG BFT Can Be Fast!
2405.20488
0
0
Abstract
Today's practical partially synchronous Byzantine Fault Tolerant (BFT) consensus protocols trade off low latency and high throughput. On the one end, traditional BFT protocols such as PBFT and its derivatives optimize for latency. They require, in fault-free executions, only 3 message exchanges to commit, the optimum for BFT consensus. However, this class of protocols typically relies on a single leader, hampering throughput scalability. On the other end, a new class of so-called DAG-BFT protocols demonstrates how to achieve highly scalable throughput by separating data dissemination from consensus, and using every replica as proposer. Unfortunately, existing DAG-BFT protocols pay a steep latency premium, requiring on average 10.5 message exchanges to commit a transactions. This work aims to soften this tension and proposes Shoal++, a novel DAG-based BFT consensus system that offers the throughput of DAGs while reducing commit latency to an average of 4.5 message exchanges. Our empirical findings are encouraging, showing that Shoal++ achieves throughput comparable to state-of-the-art DAG BFT solutions while reducing latency by up to 60%.
Create account to get full access
Overview
- Shoal++ is a new Byzantine Fault Tolerant (BFT) protocol designed to achieve high throughput and low latency for distributed ledger systems.
- It uses a directed acyclic graph (DAG) structure to enable parallel transaction processing, improving on previous BFT protocols like Motorway, Probabilistic BFT, Moonshot, and BBCA.
- The paper claims Shoal++ can achieve very high throughput and low latency, even approaching the limits of Mysticeti.
Plain English Explanation
Shoal++ is a new way to process transactions in a distributed system, even when some of the nodes are untrustworthy (Byzantine faults). It uses a special graph structure called a directed acyclic graph (DAG) to allow many transactions to be processed in parallel, rather than processing them one-by-one like a traditional blockchain.
This parallel processing helps Shoal++ achieve very high transaction throughput (the number of transactions it can process per second) and low latency (the time it takes for a transaction to be confirmed). The paper claims Shoal++ can approach the performance limits of other cutting-edge BFT systems like Mysticeti.
The key ideas behind Shoal++ are:
- Using a DAG structure to enable parallel transaction processing
- Designing a BFT protocol that can run effectively on this DAG
By taking advantage of the DAG structure, Shoal++ can process many transactions at the same time, rather than being limited to a single serial chain like older BFT protocols. This allows it to reach much higher throughput and lower latency, which is critical for modern distributed ledger applications.
Technical Explanation
Shoal++ is a new Byzantine Fault Tolerant (BFT) protocol that uses a directed acyclic graph (DAG) structure to enable high throughput and low latency transaction processing.
The key technical elements of Shoal++ include:
-
DAG Structure: Shoal++ organizes transactions into a DAG, rather than a linear blockchain. This allows many transactions to be processed in parallel, rather than serially.
-
BFT Protocol: Shoal++ defines a BFT consensus protocol that can run effectively on the DAG structure. This includes mechanisms for nodes to agree on the ordering and validity of transactions, even in the presence of faulty or malicious nodes.
-
Incentive Mechanism: Shoal++ incorporates an incentive mechanism to encourage nodes to participate honestly and contribute to the system's performance.
The paper evaluates Shoal++'s performance through simulations and mathematical analysis, comparing it to other state-of-the-art BFT protocols like Motorway, Probabilistic BFT, Moonshot, and BBCA. The results suggest that Shoal++ can achieve extremely high throughput and low latency, even approaching the limits of Mysticeti.
Critical Analysis
The Shoal++ paper makes a strong case for the benefits of using a DAG structure to enable high throughput BFT. By parallelizing transaction processing, the protocol can achieve significantly better performance than traditional blockchain-based BFT systems.
However, the paper does not address some potential challenges and limitations of the Shoal++ approach:
-
Complexity: The DAG structure and associated BFT protocol are likely more complex to implement and reason about than simpler blockchain-based designs. This increased complexity could make Shoal++ more difficult to deploy and maintain in practice.
-
Finality: The paper does not discuss how Shoal++ ensures transaction finality, which is an important property for many applications. Ensuring finality in a DAG-based system may introduce additional challenges.
-
Scalability: While Shoal++ achieves high throughput, the paper does not explore how the protocol would scale to very large numbers of nodes or transactions. The overhead of the BFT protocol may become a bottleneck at larger scales.
-
Security Assumptions: Like other BFT protocols, Shoal++ relies on certain security assumptions, such as a limit on the number of faulty nodes. The paper does not provide a detailed security analysis or discuss the resilience of the protocol to various attack vectors.
Further research and real-world deployment experience would be needed to fully assess the practical benefits and limitations of the Shoal++ approach.
Conclusion
The Shoal++ paper presents a novel BFT protocol that leverages a DAG structure to achieve extremely high throughput and low latency, potentially outperforming other state-of-the-art BFT systems. This represents an important advance in the field of distributed ledger technology, which is critical for enabling secure and scalable decentralized applications.
While Shoal++ faces some potential challenges around complexity, finality, and scalability, the core ideas behind the protocol demonstrate the power of parallel transaction processing and innovative BFT design. As the demand for high-performance distributed systems continues to grow, Shoal++ and similar DAG-based BFT protocols could play a crucial role in unlocking the full potential of blockchain and other distributed ledger technologies.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
🏋️
Motorway: Seamless high speed BFT
Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, Natacha Crooks
0
0
Today's practical, high performance Byzantine Fault Tolerant (BFT) consensus protocols operate in the partial synchrony model. However, existing protocols are inefficient when deployments are indeed partially synchronous. They deliver either low latency during fault-free, synchronous periods (good intervals) or robust recovery from events that interrupt progress (blips). At one end, traditional, view-based BFT protocols optimize for latency during good intervals, but, when blips occur, can suffer from performance degradation (hangovers) that can last beyond the return of a good interval. At the other end, modern DAG-based BFT protocols recover more gracefully from blips, but exhibit lackluster latency during good intervals. To close the gap, this work presents Motorway, a novel high-throughput BFT protocol that offers both low latency and seamless recovery from blips. By combining a highly parallel asynchronous data dissemination layer with a low-latency, partially synchronous consensus mechanism, Motorway (i) avoids the hangovers incurred by traditional BFT protocols and (ii) matches the throughput of state of the art DAG-based BFT protocols while cutting their latency in half, matching the latency of traditional BFT protocols.
5/13/2024
Probabilistic Byzantine Fault Tolerance (Extended Version)
Diogo Avel~as, Hasan Heydari, Eduardo Alchieri, Tobias Distler, Alysson Bessani
0
0
Consensus is a fundamental building block for constructing reliable and fault-tolerant distributed services. Many Byzantine fault-tolerant consensus protocols designed for partially synchronous systems adopt a pessimistic approach when dealing with adversaries, ensuring safety in a deterministic way even under the worst-case scenarios that adversaries can create. Following this approach typically results in either an increase in the message complexity (e.g., PBFT) or an increase in the number of communication steps (e.g., HotStuff). In practice, however, adversaries are not as powerful as the ones assumed by these protocols. Furthermore, it might suffice to ensure safety and liveness properties with high probability. In order to accommodate more realistic and optimistic adversaries and improve the scalability of the BFT consensus, we propose ProBFT (Probabilistic Byzantine Fault Tolerance). ProBFT is a leader-based probabilistic consensus protocol with a message complexity of $O(nsqrt{n})$ and an optimal number of communication steps that tolerates Byzantine faults in permissioned partially synchronous systems. It is built on top of well-known primitives, such as probabilistic Byzantine quorums and verifiable random functions. ProBFT guarantees safety and liveness with high probabilities even with faulty leaders, as long as a supermajority of replicas is correct, and using only a fraction of messages employed in PBFT (e.g., $20%$). We provide a detailed description of ProBFT's protocol and its analysis.
6/12/2024
Moonshot: Optimizing Chain-Based Rotating Leader BFT via Optimistic Proposals
Isaac Doidge, Raghavendra Ramesh, Nibesh Shrestha, Joshua Tobkin
0
0
Existing chain-based rotating-leader BFT SMR protocols for the partially synchronous network model with constant commit latencies incur block periods of at least $2delta$ (where $delta$ is the message transmission latency). While a protocol with a block period of $delta$ exists under the synchronous model, its commit latency is linear in the size of the system. To close this gap, we present the first chain-based BFT SMR protocols with $delta$ delay between the proposals of consecutive honest leaders and commit latencies of $3delta$. We present three protocols for the partially synchronous model under different notions of optimistic responsiveness, two of which implement pipelining. All of our protocols achieve reorg resilience and two have short view lengths; properties that many existing chain-based BFT SMR protocols lack. We present an evaluation of our protocols in a wide-area network wherein they demonstrate significant increases in throughput and reductions in latency compared to the state-of-the-art, Jolteon. Our results also demonstrate that techniques commonly employed to reduce communication complexity$unicode{x2014}$such as vote-pipelining and the use of designated vote-aggregators$unicode{x2014}$actually reduce practical performance in many settings.
4/22/2024
BBCA-CHAIN: Low Latency, High Throughput BFT Consensus on a DAG
Dahlia Malkhi, Chrysoula Stathakopoulou, Maofan Yin
0
0
This paper presents a partially synchronous BFT consensus protocol powered by BBCA, a lightly modified Byzantine Consistent Broadcast (BCB) primitive. BBCA provides a Complete-Adopt semantic through an added probing interface to allow either aborting the broadcast by correct nodes or exclusively, adopting the message consistently in case of a potential delivery. It does not introduce any extra types of messages or additional communication costs to BCB. BBCA is harnessed into BBCA-CHAIN to make direct commits on a chained backbone of a causally ordered graph of blocks, without any additional voting blocks or artificial layering. With the help of Complete-Adopt, the additional knowledge gained from the underlying BCB completely removes the voting latency in popular DAG-based protocols. At the same time, causal ordering allows nodes to propose blocks in parallel and achieve high throughput. BBCA-CHAIN thus closes up the gap between protocols built by consistent broadcasts (e.g., Bullshark) to those without such an abstraction (e.g., PBFT/HotStuff), emphasizing their shared fundamental principles. Using a Bracha-style BCB as an example, we fully specify BBCA-CHAIN with simplicity, serving as a solid basis for high-performance replication systems (and blockchains).
5/28/2024