BBCA-CHAIN: Low Latency, High Throughput BFT Consensus on a DAG
2310.06335
0
0
Abstract
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).
Create account to get full access
Overview
- This paper presents BBCA-Chain, a new Byzantine Fault Tolerant (BFT) consensus protocol that achieves low latency and one-message consensus on a Directed Acyclic Graph (DAG) data structure.
- BBCA-Chain aims to improve upon existing BFT protocols by providing faster consensus with less communication overhead.
- The key innovations include using causal ordering to achieve low latency consensus and a novel weighted voting mechanism to reach agreement.
Plain English Explanation
BBCA-Chain is a new way for computers in a network to come to agreement, even if some of the computers are faulty or acting maliciously. Traditional consensus protocols can be slow and require a lot of back-and-forth messaging between the computers. BBCA-Chain improves on this by using a clever technique called "causal ordering" to reach consensus much faster, with just a single message from each computer.
The core idea is that instead of having the computers vote directly on proposed actions, BBCA-Chain has them vote on the order in which messages should be processed. This "causal ordering" allows the computers to quickly agree on the sequence of events, even if some of them are misbehaving. BBCA-Chain also uses a weighted voting system, where computers with more "influence" in the network get a stronger vote, to help reach consensus efficiently.
By using these innovations, BBCA-Chain is able to achieve low-latency, one-message Byzantine fault-tolerant consensus, which could be very useful for applications that require fast, secure agreement between a distributed group of computers, such as blockchain systems or decentralized finance.
Technical Explanation
BBCA-Chain builds on prior work in Byzantine fault-tolerant consensus by leveraging a DAG-based data structure and a novel voting mechanism. The key innovations are:
-
Causal Ordering: Instead of having nodes directly vote on proposed actions, BBCA-Chain has them vote on the causal ordering of messages. This allows for much faster consensus, as nodes only need to relay a single message to reach agreement.
-
Weighted Voting: BBCA-Chain uses a weighted voting system, where nodes with more "influence" in the network (e.g. based on their stake or reputation) have a stronger vote. This helps the protocol converge more efficiently to consensus.
The BBCA-Chain protocol works as follows:
- Nodes receive transactions and package them into messages.
- Nodes vote on the causal ordering of the messages using the weighted voting mechanism.
- Once a message reaches a certain voting threshold, it is considered finalized and added to the DAG.
The authors evaluate BBCA-Chain through both theoretical analysis and simulations, demonstrating its ability to reach consensus faster and with lower communication overhead compared to other BFT protocols like MOTRA and PBFT.
Critical Analysis
The BBCA-Chain paper presents a promising approach to BFT consensus, but there are a few potential limitations and areas for further research:
-
Weighted Voting Assumptions: The weighted voting mechanism relies on some assumptions about the distribution of node influence in the network, which may not always hold true in practice. The authors acknowledge this and suggest further research on more adaptive voting schemes.
-
DAG Complexity: Maintaining and processing the DAG data structure could introduce additional computational and storage overhead, especially as the network grows. The authors do not provide a thorough analysis of the scalability of this approach.
-
Practical Deployment Challenges: While the theoretical analysis and simulations are promising, the authors do not address the practical challenges of deploying BBCA-Chain in real-world, heterogeneous network environments with varying node capabilities and network conditions.
Despite these potential issues, BBCA-Chain represents an innovative approach to BFT consensus that could have significant implications for the development of secure and scalable distributed systems. Further research and experimentation will be needed to fully understand the capabilities and limitations of this protocol.
Conclusion
The BBCA-Chain protocol introduces a novel approach to Byzantine fault-tolerant consensus that leverages causal ordering and weighted voting to achieve low-latency, one-message consensus on a DAG data structure. This could lead to significant improvements in the performance and security of distributed systems, such as blockchain networks and decentralized applications, where fast and reliable consensus is critical.
While the paper presents promising theoretical and simulation results, there are still some open questions and practical deployment challenges that require further investigation. Nonetheless, BBCA-Chain represents an important step forward in the ongoing effort to develop more efficient and robust consensus protocols for the distributed computing era.
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
Shoal++: High Throughput DAG BFT Can Be Fast!
Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, Alexander Spiegelman
0
0
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%.
6/3/2024
🏋️
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
Byzantine Reliable Broadcast with Low Communication and Time Complexity
Thomas Locher
0
0
Byzantine reliable broadcast is a fundamental problem in distributed computing, which has been studied extensively over the past decades. State-of-the-art algorithms are predominantly based on the approach to share encoded fragments of the broadcast message, yielding an asymptotically optimal communication complexity when the message size exceeds the network size, a condition frequently encountered in practice. However, algorithms following the standard coding approach incur an overhead factor of at least 3, which can already be a burden for bandwidth-constrained applications. Minimizing this overhead is an important objective with immediate benefits to protocols that use a reliable broadcast routine as a building block. This paper introduces a novel mechanism to lower the communication and computational complexity. Two algorithms are presented that employ this mechanism to reliably broadcast messages in an asynchronous network where less than a third of all nodes are Byzantine. The first algorithm reduces the overhead factor to 2 and has a time complexity of 3 if the sender is honest, whereas the second algorithm attains an optimal time complexity of 2 with the same overhead factor in the absence of equivocation. Moreover, an optimization for real-world implementations is proposed, reducing the overhead factor to 3/2 under normal operation. Lastly, a lower bound is proved that an overhead factor lower than 3/2 cannot be achieved for a relevant class of reliable broadcast algorithms.
4/15/2024