Mysticeti: Reaching the Limits of Latency with Uncertified DAGs
2310.14821
0
0
🏷️
Abstract
We introduce Mysticeti-C the first DAG-based Byzantine consensus protocol to achieve the lower bounds of latency of 3 message rounds. Since Mysticeti-C is built over DAGs it also achieves high resource efficiency and censorship resistance. Mysticeti-C achieves this latency improvement by avoiding explicit certification of the DAG blocks and by proposing a novel commit rule such that every block can be committed without delays, resulting in optimal latency in the steady state and under crash failures. We further extend Mysticeti-C to Mysticeti-FPC, which incorporates a fast commit path that achieves even lower latency for transferring assets. Unlike prior fast commit path protocols, Mysticeti-FPC minimizes the number of signatures and messages by weaving the fast path transactions into the DAG. This frees up resources, which subsequently result in better performance. We prove the safety and liveness of the protocols in a Byzantine context. We evaluate Mysticeti and compare it with state-of-the-art consensus and fast path protocols to demonstrate its low latency and resource efficiency, as well as its more graceful degradation under crash failures. Mysticeti is the first Byzantine consensus protocol to achieve WAN latency of 0.5s for consensus commit while simultaneously maintaining state-of-the-art throughput of over 100k TPS. Finally, we report on integrating Mysticeti-C as the consensus protocol into a major blockchain, resulting in 4x latency reduction.
Create account to get full access
Overview
- Introduces Mysticeti-C, a new Byzantine consensus protocol built on a Directed Acyclic Graph (DAG) structure
- Achieves the lower bound of 3 message rounds for latency, which is the fastest possible
- Also provides high resource efficiency and censorship resistance due to the DAG design
- Extends Mysticeti-C to Mysticeti-FPC, which adds a fast commit path for asset transfers with even lower latency
Plain English Explanation
Mysticeti-C is a new way to reach agreement (consensus) in a distributed system, even when some participants might be untrustworthy or trying to disrupt the process. It's built on a Directed Acyclic Graph (DAG), which is a special type of data structure that allows for high efficiency and resistance to censorship.
The key innovation of Mysticeti-C is that it achieves the fastest possible latency, or time delay, for reaching consensus - just 3 message rounds. This is the theoretical lower bound for this type of system. It does this by avoiding explicit certification of the DAG blocks and using a novel commit rule that allows every block to be committed without delays.
The researchers then extend Mysticeti-C to create Mysticeti-FPC, which adds an even faster commit path specifically for transferring digital assets. This minimizes the number of signatures and messages required, freeing up resources and further improving performance.
The protocols are proven to be safe and live in the face of Byzantine (untrustworthy) participants. Experimental evaluation shows Mysticeti provides very low latency (0.5s for wide-area networks) while maintaining high throughput, and it degrades more gracefully than other systems when some nodes crash.
Technical Explanation
Mysticeti-C is a Byzantine consensus protocol built on a Directed Acyclic Graph (DAG) data structure. This allows it to achieve the lower bound of 3 message rounds for latency, which is the fastest possible for this type of system.
The protocol avoids explicit certification of the DAG blocks, and instead uses a novel commit rule that allows every block to be committed without delays, resulting in optimal latency in the steady state and under crash failures. This is an improvement over prior Byzantine reliable broadcast protocols.
The researchers further extend Mysticeti-C to create Mysticeti-FPC, which adds a fast commit path for transferring digital assets. Unlike previous fast commit path protocols, Mysticeti-FPC minimizes the number of signatures and messages required by weaving the fast path transactions directly into the DAG structure. This frees up resources and improves overall performance.
The safety and liveness of both protocols are proven in a Byzantine context. Experimental evaluation shows Mysticeti achieves very low latency (0.5s for wide-area networks) while maintaining over 100k TPS throughput. It also demonstrates more graceful degradation under crash failures compared to other consensus and fast path protocols.
Critical Analysis
The paper thoroughly evaluates the performance of Mysticeti under various conditions, including crash failures. However, it does not explore potential vulnerabilities to Byzantine attacks that could disrupt the consensus process. Further research would be needed to understand the system's robustness against more sophisticated adversarial scenarios.
Additionally, the paper does not provide much detail on the practical considerations of integrating Mysticeti into a real-world blockchain system. The brief mention of integrating it into a major blockchain is interesting, but more information on the challenges and tradeoffs involved would be helpful for readers to fully assess the protocol's applicability.
Overall, the Mysticeti protocols represent a significant advancement in Byzantine consensus, achieving impressive performance results. However, further research is needed to thoroughly understand its security properties and real-world implementation considerations.
Conclusion
Mysticeti-C and Mysticeti-FPC are new Byzantine consensus protocols that introduce several important innovations. By building on a DAG structure, they are able to achieve the lower bound of 3 message rounds for latency, the fastest possible for this type of system. They also provide high resource efficiency and censorship resistance.
The extensions in Mysticeti-FPC further improve performance by minimizing the overhead of the fast commit path for asset transfers. Experimental results demonstrate that Mysticeti can provide sub-second latency for wide-area networks while maintaining high throughput, and it degrades more gracefully than other consensus and fast path protocols under crash failures.
These advances in Byzantine consensus have significant implications for the design of secure, low-latency distributed systems, including blockchain and cryptocurrency applications. As the research continues, it will be important to further explore the security properties and real-world deployment considerations of these protocols.
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
💬
Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, Zhuolun Xiang
0
0
Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear communication cost in the happy path, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds: optimal communication on and off the happy path (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems. Notably, Jolteon's commit latency outperforms HotStuff by 200-300ms with varying system size. Additionally, Ditto adapts to the network and provides better performance than Jolteon under faulty conditions and better performance than VABA (a state-of-the-art asynchronous protocol) under faultless conditions. This proves our case that breaking the robustness-efficiency trade-off is in the realm of practicality.
5/2/2024
🌐
Refined Bitcoin Security-Latency Under Network Delay
Mustafa Doger, Sennur Ulukus
0
0
We study security-latency bounds for Nakamoto consensus, i.e., how secure a block is after it becomes $k$-deep in the chain. We improve the state-of-the-art bounds by analyzing the race between adversarial and honest chains in three different phases. We find the probability distribution of the growth of the adversarial chains under models similar to those in [Guo, Ren; AFT 2022] when a target block becomes $k$-deep in the chain. We analyze certain properties of this race to model each phase with random walks that provide tighter bounds than the existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small $lambdaDelta$.
5/29/2024