Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
2106.10362
0
0
💬
Abstract
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.
Create account to get full access
Overview
- Current Byzantine state machine replication (SMR) protocols used in blockchains face a trade-off: they either achieve linear communication cost in the "happy path" but sacrifice liveness during periods of asynchrony, or they are robust (progress with probability one) but pay quadratic communication cost.
- The researchers believe this trade-off is unnecessary, as existing linear protocols still have asymptotic quadratic cost in the worst case.
- They present Ditto, a Byzantine SMR protocol that achieves optimal communication on and off the "happy path" (linear and quadratic, respectively) and provides progress guarantee under asynchrony and DDoS attacks.
- As an intermediate step, they also design Jolteon, a 2-chain version of the HotStuff protocol, which reduces the latency of the standard 3-chain HotStuff.
Plain English Explanation
Blockchains use a type of protocol called Byzantine state machine replication (SMR) to ensure that the ledger is updated correctly, even if some of the nodes in the network are behaving maliciously. Current SMR protocols used in production blockchains have to make a choice: they can either communicate efficiently (using a linear amount of messages) when everything is working well, but then they won't be able to make progress if the network becomes unreliable. Or, they can be more robust and keep making progress even if the network is behaving poorly, but then they have to use a quadratic (much more expensive) number of messages.
The researchers behind this paper believe this trade-off is unnecessary. They've designed a new protocol called Ditto that can communicate efficiently both when everything is working well and when the network is misbehaving. Ditto can still make progress and update the ledger correctly, even if the network is experiencing issues like distributed denial-of-service (DDoS) attacks.
As a stepping stone to Ditto, the researchers also developed a new version of an existing protocol called HotStuff, called Jolteon. Jolteon uses a different approach to reduce the time it takes to finalize updates to the ledger, compared to the original HotStuff.
Technical Explanation
The researchers start with the state-of-the-art HotStuff protocol, which achieves linear communication cost in the "happy path" but can lose liveness during periods of asynchrony. To address this, they gradually build Ditto, their new Byzantine SMR protocol.
As an intermediate step, the researchers design Jolteon, a 2-chain version of HotStuff that leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. Jolteon's commit latency outperforms HotStuff by 200-300 milliseconds, with varying system size.
The key innovation in Ditto is replacing the view-synchronization of partially synchronous protocols (like HotStuff) with an asynchronous fallback mechanism, without incurring extra asymptotic cost. This allows Ditto to enjoy optimal communication on and off the "happy path" (linear and quadratic, respectively) while also providing progress guarantee under asynchrony and DDoS attacks.
The researchers implement and experimentally evaluate all their systems. They show that Ditto adapts to the network conditions 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 demonstrates that breaking the robustness-efficiency trade-off is indeed practical.
Critical Analysis
The paper presents a comprehensive solution to the well-known trade-off in Byzantine SMR protocols. However, the researchers acknowledge that their approach still has some limitations:
- The asynchronous fallback mechanism in Ditto, while efficient, may introduce additional latency compared to purely synchronous protocols like HotStuff during the "happy path."
- The experiments were conducted in a controlled environment, and the performance of Ditto in real-world, large-scale blockchain deployments remains to be seen.
- The paper does not explore the potential impact of Ditto's design choices on other aspects of blockchain systems, such as incentive mechanisms or governance.
Additionally, the researchers could have further explored the connections between their work and other recent advances in partial synchrony-free and asynchronous Byzantine consensus protocols.
Overall, the Ditto protocol represents a significant step forward in the design of efficient and robust Byzantine SMR systems, though further research and real-world deployment experience will be needed to fully evaluate its capabilities and limitations.
Conclusion
The researchers have presented Ditto, a Byzantine state machine replication (SMR) protocol that achieves the best of both worlds: optimal communication efficiency on the "happy path" and during periods of network asynchrony, while also providing progress guarantees. Ditto's design represents an important advancement in the field of blockchain consensus protocols, as it demonstrates that the traditional trade-off between robustness and efficiency can be overcome in practice.
The researchers also developed Jolteon, a version of the HotStuff protocol that reduces latency by using a 2-chain structure instead of the standard 3-chain approach. Jolteon serves as an important stepping stone towards the Ditto protocol and showcases the researchers' innovative thinking in this domain.
Overall, the Ditto protocol has the potential to significantly impact the design and performance of production blockchain systems, helping to address some of the key challenges faced by current SMR protocols. The critical analysis highlights areas for further exploration, but the core contributions of this work represent an important milestone in the ongoing efforts to build more reliable and efficient 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
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
🏷️
Mysticeti: Reaching the Limits of Latency with Uncertified DAGs
Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, Mingwei Tian
0
0
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.
5/1/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
Synchronous Consensus in Partial Synchrony
Ivan Klianev
0
0
We demonstrate a deterministic Byzantine consensus algorithm with synchronous operation in partial synchrony. It is naturally leaderless, tolerates any number of $ f<n/2 $ Byzantine processes with 2 rounds of exchange of originator-only signed messages, and terminates within a bounded interval of time. The algorithm is resilient to transient faults and asynchrony in a fraction of links with known size per number of faulty processes. It circumvents asynchronous and faulty links with 3-hop epidemic dissemination. Key finding: the resilience to asynchrony of links and the enabled by it leaderless consensus in partial synchrony ensure algorithm operation with simultaneous validity, safety, and bounded liveness.
5/16/2024