Mysticeti: Reaching the Latency Limits with Uncertified DAGs

Mysticeti: Reaching the Latency Limits with Uncertified DAGs

Speakers: Kushal Babel, Mist Labs

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=AaRKeA3pSNA

Overview

This article delves into Mysticeti, a novel Byzantine fault-tolerant (BFT) consensus protocol developed by Mist Labs, presented by Kushal Babel at the NDSS Symposium. Mysticeti belongs to the family of Proof-of-Stake (PoS) consensus mechanisms, designed to operate within a predefined set of validators while tolerating both network and machine failures, as well as the malicious behavior of up to one-third of the participating nodes. The core objective of such protocols is to ensure that all honest validators eventually agree on the same state, which, in Mysticeti's application within blockchain, primarily involves agreeing on a definitive list of transactions.

The significance of Mysticeti lies in its ambitious goal to overcome a fundamental trade-off observed in previous generations of blockchain consensus protocols: the often-conflicting demands of high transaction throughput and low transaction finality latency. Traditional consensus protocols typically offer decent latency but struggle with throughput, while many modern Directed Acyclic Graph (DAG)-based protocols achieve remarkable throughput but often at the cost of increased latency. Mysticeti proposes an innovative approach using an uncertified DAG to achieve both, delivering sub-second transaction finality while supporting hundreds of thousands of transactions per second.

This work is not merely theoretical; Mysticeti has been successfully deployed in a live Layer 1 blockchain, Sui, demonstrating its practical efficacy and robust performance in a production environment. The migration of Sui to Mysticeti serves as a compelling real-world validation of its capabilities, showcasing a dramatic reduction in transaction finality times. This advancement is crucial for the scalability and user experience of decentralized applications, offering a blueprint for future high-performance blockchain architectures.

Background

▶ Watch: Introduction to Mysticeti consensus protocol (0:00)

The evolution of Byzantine fault-tolerant consensus protocols in blockchain has seen several distinct phases, each attempting to address the inherent challenges of distributed agreement in the presence of malicious actors. Early iterations, often termed "traditional consensus protocols," are typically proposal-based. In these systems, a designated leader for each round proposes a set of transactions, and validators engage in a multi-round communication process to commit this proposal. Protocols like HotStuff exemplify this approach, offering relatively low "leader commit latency" – the time it takes for a correct leader's proposal to be finalized. However, a significant drawback is that these protocols primarily focus on committing leader-proposed blocks and do not inherently address the transaction finality from a user's perspective. The process of how a user's transaction reaches the leader and gets included in a proposed block is handled by a separate component, often referred to as a mempool. The overall latency for a user's transaction finality is therefore the sum of mempool propagation time and consensus commitment time.

To address the throughput limitations of traditional consensus, particularly the bottleneck associated with a single leader, subsequent efforts focused on decoupling transaction dissemination from consensus. This led to the development of DAG-based mempools, such as Narwhal. These mempools efficiently distribute a large volume of transactions among validators, forming a DAG where each node represents a block containing transactions and references to previously seen blocks from other validators. This approach enables very high transaction throughput, often exceeding 100,000 transactions per second. However, these systems still required a separate consensus protocol to agree on the order or hash of the DAG's nodes. This two-phase architecture—first propagating through a DAG mempool, then committing via a separate consensus—resulted in a high overall transaction finality latency, despite the impressive throughput.

The next evolutionary step aimed to integrate the mempool and consensus layers. Protocols like Narwhal-Bullshark emerged, where the DAG itself is interpreted to derive a canonical order of transactions, effectively removing the need for a distinct consensus protocol. While this design maintains very high throughput (e.g., 200,000 transactions per second), it often comes with even higher latency compared to traditional consensus, as the process of deriving a global order from a distributed, asynchronously built DAG can be complex and time-consuming. The reason for this increased latency in previous DAG-based consensus protocols, particularly those employing "certified DAGs," is the overhead required to ensure that every element in the graph has been sufficiently "certified" or acknowledged by a supermajority of validators. This certification process, while providing strong guarantees against Byzantine behavior, typically requires one to one-and-a-half round trips for each element, contributing significantly to overall latency. It is against this backdrop of high-throughput, high-latency DAGs and low-throughput, low-latency traditional consensus that Mysticeti was conceived, aiming to bridge this gap by offering the best of both worlds.

Key Findings

▶ Watch: DAG-based mempools for high throughput (Narwhal) (3:00)

Mysticeti's primary contribution is its ability to deliver both very high throughput and very low transaction finality latency, a combination that has historically proven challenging for Byzantine fault-tolerant consensus protocols. The protocol achieves throughputs of up to 500,000 transactions per second and can potentially push even higher, while maintaining sub-second transaction commit times, comparable to the leader-commit latency of traditional consensus protocols, even before factoring in mempool propagation.

The cornerstone of Mysticeti's design is its use of an uncertified DAG. Unlike previous DAG-based protocols like Narwhal, which rely on certified DAGs, Mysticeti allows validators to create elements (blocks) in the DAG with less overhead. Specifically, making an element in an uncertified DAG requires only half a round trip, significantly faster than the one to one-and-a-half round trips needed for a certified DAG element. This reduction in the cost of creating DAG elements directly translates to lower latency at the individual validator level.

However, the "uncertified" nature implies that certain Byzantine scenarios, which certified DAGs are designed to prevent at the element creation stage, become possible within Mysticeti. To compensate for this, Mysticeti's consensus mechanism requires more rounds to achieve finality—three rounds compared to two for Narwhal. Despite the increased number of rounds, the overall mathematical analysis demonstrates that Mysticeti achieves lower transaction finality latency due to the much faster creation of individual DAG elements. This trade-off between individual element creation speed and the number of consensus rounds is central to Mysticeti's performance advantage.

Beyond its core consensus mechanism, Mysticeti also introduces a sub-protocol called Fast Pass. This optimization allows for even faster commitment of specific types of transactions under certain conditions. Leveraging findings from prior research on fast payments, Fast Pass enables users to make transactions that can be committed more quickly, without requiring any new RPCs or significant protocol changes; it primarily involves adding specific metadata to blocks within the existing Mysticeti DAG structure.

A crucial finding validating Mysticeti's efficacy is its real-world deployment. The Sui Layer 1 blockchain, initially launched with the Narwhal-Bullshark consensus protocol in May 2023, fully migrated to Mysticeti a few months later in Fall 2023. This live migration on a mainnet blockchain is a rare and significant event in the industry. The results were dramatic: transaction finality on Sui mainnet, which was previously around two seconds with Narwhal-Bullshark, dropped to approximately 400 milliseconds after switching to Mysticeti. This concrete performance improvement in a production environment unequivocally demonstrates Mysticeti's practical value and its ability to deliver on its promise of high throughput and low latency.

Technical Deep Dive

▶ Watch: Mysticeti's uncertified DAG innovation for low latency (4:40)

Mysticeti is a Byzantine fault-tolerant (BFT) consensus protocol operating in a Proof-of-Stake (PoS) environment. Its architecture is specifically designed to achieve an optimal balance between throughput and latency, leveraging an innovative approach to DAG construction and ordering.

At its core, Mysticeti builds a Directed Acyclic Graph (DAG) of blocks, similar to previous DAG-based mempools, but critically, it employs an uncertified DAG. The distinction between certified and uncertified DAGs is fundamental:

• Certified DAGs (e.g., Narwhal): Each block or element in the DAG requires a cryptographic "certification" by a supermajority of validators before it is considered valid and incorporated. This certification process is robust against Byzantine behavior but is resource-intensive, typically requiring one to one-and-a-half round trips of communication for each element. This overhead contributes to higher latency.
• Uncertified DAGs (Mysticeti): Elements can be created with significantly less overhead, requiring only half a round trip of communication. This means a validator can propose a block without waiting for a full round of supermajority acknowledgements. While this speeds up individual block creation, it introduces the possibility of Byzantine actors creating "bad" or inconsistent blocks more easily. Mysticeti's consensus mechanism is designed to handle these potential Byzantine scenarios by requiring three rounds of communication to achieve finality, compared to two rounds for certified DAGs. Despite the extra consensus round, the overall mathematical model and empirical results show that the gains from faster element creation outweigh the cost of the additional round, leading to lower overall transaction finality.

The protocol's implementation details reflect a focus on performance and robustness:

• Language: The entire protocol is written in Rust, a language known for its performance, memory safety, and concurrency features. The speaker highlights Rust as a superior choice to Go and a more manageable alternative to C++ for high-performance systems like blockchains, noting its widespread adoption in modern blockchain development.
• Networking: The networking layer is remarkably simple, consisting primarily of a single RPC (Remote Procedure Call). Validators connect to peers and request blocks, and they also send their own blocks to connected nodes. This "pull and push" model is implemented over TCP sockets and utilizes async IO for efficient handling of concurrent network operations without blocking.
• Consensus Logic: While the networking is asynchronous, the consensus logic itself is designed to be largely synchronous. This design choice aims to reduce the complexity and potential for subtle bugs often associated with highly asynchronous state management in complex distributed systems.
• Cryptographic Signatures: ED25519 signatures are used for cryptographic authentication and integrity, providing strong security guarantees.
• Storage: To combat the I/O bottleneck that arises with very high throughput, even on modern SSDs, Mysticeti employs WAL-based storage (Write-Ahead Log) instead of traditional database solutions like RocksDB. WAL-based storage significantly reduces write amplification, ensuring that disk operations remain efficient under heavy load.

Performance benchmarks, conducted on a real cluster of 100 or more nodes distributed globally (across Asia, Europe, United States, Australia), illustrate Mysticeti's superiority. Compared to HotStuff (a traditional consensus protocol), Narwhal-HotStuff (DAG mempool + traditional consensus), and Bullshark (a previous generation DAG-based consensus), Mysticeti demonstrates consistently lower latency across a wide range of throughputs. While latency does increase with higher TPS due to implementation details and network saturation, Mysticeti maintains sub-second latency even at 300,000 transactions per second, a remarkable feat. The protocol's ability to achieve up to 500,000 transactions per second with comparable low latency positions it as a leader in high-performance BFT consensus.

The Fast Pass sub-protocol further enhances latency for specific transaction types. It leverages insights from prior work like "Fast Pay" to enable faster commitments. This is achieved by adding extra metadata to existing blocks within the Mysticeti DAG, rather than introducing new RPCs or fundamentally altering the core protocol. This demonstrates the extensibility of the Mysticeti DAG as a foundational layer upon which other specialized protocols can be built.

Demo / Proof of Concept

▶ Watch: Summary of Mysticeti's advantages and trade-offs (5:50)

While the conference talk did not feature a live, interactive demonstration of Mysticeti, the speaker provided compelling evidence of its real-world efficacy through its deployment on the Sui blockchain. This production-grade implementation serves as a robust proof of concept, validating Mysticeti's performance claims under live network conditions.

The Sui Layer 1 blockchain, initially launched in May 2023 utilizing the Narwhal-Bullshark consensus protocol, underwent a full migration to Mysticeti in Fall 2023. This transition represented a significant engineering feat, as few live blockchains switch their core consensus protocol. Post-migration, the impact on transaction finality was immediately apparent and substantial. Mainnet data from Sui showed that transaction finality, which hovered around two seconds with Narwhal-Bullshark, dramatically decreased to approximately 400 milliseconds with Mysticeti. This 80% reduction in latency on a live network with real users and real transactions is a powerful testament to Mysticeti's design and implementation.

Furthermore, the development and validation of Mysticeti were supported by extensive testing in a large-scale, globally distributed cluster. This test environment comprised 100 or more nodes strategically placed across various continents, including Asia, Europe, the United States, and Australia. Such rigorous testing in a realistic, geographically dispersed setting ensures that the protocol's performance holds up under conditions that mimic a real-world blockchain network, accounting for network latencies and potential inconsistencies inherent in a global distributed system. The combination of comprehensive testing and successful mainnet deployment provides a strong empirical foundation for Mysticeti's capabilities.

Defensive Implications

▶ Watch: Mysticeti implementation details and testing (7:10)

Mysticeti's advancements in Byzantine fault-tolerant consensus have several significant defensive implications, primarily for blockchain operators, decentralized application (dApp) developers, and end-users. While the talk focuses on performance improvements rather than specific vulnerabilities, the inherent properties of Mysticeti enhance the overall security, reliability, and usability of blockchain systems.

1. Enhanced Transaction Finality and Reliability: The core defensive benefit is Mysticeti's ability to provide sub-second transaction finality at high throughputs. From a defensive perspective, faster finality reduces the window of opportunity for certain types of attacks, such as front-running or reorg attacks, where malicious actors attempt to manipulate transaction order or rewrite blockchain history. Consistent and rapid finality ensures that once a transaction is committed, its state is quickly and irreversibly agreed upon by the network, bolstering the integrity of the ledger.
2. Robust Byzantine Fault Tolerance: As a BFT protocol, Mysticeti is designed to tolerate up to one-third of validators behaving maliciously, running arbitrary code, or attempting to subvert the protocol. This built-in resilience is a fundamental defensive mechanism against internal threats and collusion among a minority of validators, ensuring the network remains secure and operational even in adversarial conditions.
3. Scalability and DDoS Resilience: The protocol's high throughput capabilities (up to 500,000 TPS) inherently improve the network's resilience against Denial of Service (DoS) attacks. A network that can process a vast number of transactions per second is less susceptible to being overwhelmed by a flood of illegitimate transactions, as legitimate user activity can still be processed efficiently.
4. Optimized Resource Utilization: The use of WAL-based storage instead of traditional databases like RocksDB to reduce write amplification is a critical defensive strategy against disk I/O bottlenecks. In high-throughput scenarios, disk saturation can lead to performance degradation, network instability, and potential vulnerability to resource exhaustion attacks. By optimizing disk writes, Mysticeti helps maintain node stability and performance, even under extreme load.
5. Secure and Performant Implementation (Rust): The choice of Rust for implementation contributes to defensive posture by leveraging its strong type safety, memory safety, and concurrency features. These language characteristics significantly reduce the likelihood of common vulnerabilities such as buffer overflows, null pointer dereferences, and data races, which often plague systems written in less memory-safe languages like C++.
6. Insights for System Design: For developers building other high-performance distributed systems, Mysticeti's design choices offer valuable lessons. The strategy of using a simpler, uncertified DAG for faster element creation, coupled with a more robust multi-round consensus to handle Byzantine scenarios, presents an alternative paradigm for balancing performance and security. The emphasis on simple networking combined with synchronous consensus logic for critical components also provides a blueprint for maintaining code clarity and reducing bug surface area in complex systems.
7. Real-World Validation: The successful migration and sustained operation of Mysticeti on the Sui mainnet provide a high degree of confidence in its production readiness and security. This real-world stress test demonstrates that the protocol can withstand the rigors of a live, economically significant blockchain, offering assurance to projects considering similar high-performance BFT solutions.

In essence, Mysticeti strengthens the defensive posture of blockchain networks by delivering a highly performant, resilient, and efficiently engineered consensus mechanism that mitigates several operational risks and enhances the security properties of transaction finality.

Key Takeaways

• Breaks the Throughput-Latency Trade-off: Mysticeti is a Byzantine fault-tolerant consensus protocol that achieves both exceptionally high throughput (up to 500,000 transactions per second) and very low transaction finality latency (sub-second), a significant advancement over previous protocols.
• Innovates with Uncertified DAGs: Its core innovation is the use of an uncertified DAG, allowing for faster creation of individual blocks (half a round trip) compared to certified DAGs (1-1.5 round trips). While requiring more consensus rounds (three vs. two), this design ultimately results in lower overall transaction finality.
• Proven in Production: Mysticeti has been successfully deployed and is actively running on the Sui Layer 1 blockchain mainnet. This migration reduced Sui's transaction finality from approximately two seconds (with Narwhal-Bullshark) to a mere 400 milliseconds, demonstrating its robust real-world performance.
• Engineered for Efficiency: The protocol is implemented in Rust for performance and safety, features a simple RPC-based networking layer with async IO, and employs WAL-based storage to minimize write amplification and prevent disk I/O bottlenecks under high load.
• Fast Pass Optimization: Mysticeti includes a Fast Pass sub-protocol, which allows for even quicker commitment of specific types of transactions by leveraging additional metadata within existing blocks, further enhancing latency for conditional use cases.
• Robustness Through Testing: Extensive testing on a globally distributed cluster of over 100 nodes confirms Mysticeti's resilience and performance under realistic network conditions, solidifying its position as a leading solution for scalable blockchain consensus.

About the Speaker(s)

Kushal Babel is an author and contributor to the Mysticeti consensus protocol, developed at Mist Labs. His presentation at the NDSS Symposium highlighted the technical innovations and real-world impact of Mysticeti, particularly its successful integration into the Sui blockchain.