Sailfish: Towards Improving the Latency of DAG-based BFT

Sailfish: Towards Improving the Latency of DAG-based BFT

Speakers: Nibesh Shrestha, Researcher, Supra; Rohan Shrothrium; Aniket Kate; Kartik Nayak

Conference: IEEE S&P

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

Overview

In the realm of distributed systems, achieving both high performance and robust fault tolerance is a perennial challenge. This talk introduces Sailfish, a novel Byzantine Fault Tolerant (BFT) protocol designed to significantly improve the latency of State Machine Replication (SMR) in partially synchronous communication environments. Presented by Nibesh Shrestha from Supra, Sailfish addresses a fundamental limitation in existing Directed Acyclic Graph (DAG)-based BFT protocols, which, despite their promise for high throughput, have historically suffered from high commit latencies.

The core innovation of Sailfish lies in its ability to support a leader vertex in each round of the protocol, a capability previously deemed impossible or highly problematic by prior DAG BFT designs. By meticulously re-engineering the safety invariants and commitment rules, Sailfish drastically reduces the time it takes for both leader and non-leader transactions to be finalized. This work is critical for applications demanding both high reliability and low latency, such as decentralized finance, critical infrastructure control, and other distributed ledger technologies, offering a substantial leap forward in the practical deployment of BFT systems.

Background

▶ Watch: Introduction to Sailfish and existing DAG protocol limitations. (0:00)

State Machine Replication (SMR) is a cornerstone technique for building fault-tolerant distributed systems, ensuring that all honest nodes agree on a sequence of operations despite failures, including malicious (Byzantine) behavior. In a partially synchronous model, where network delays are bounded but unknown, achieving SMR with strong guarantees and high performance is complex. Traditional BFT protocols often face a trade-off between throughput and latency, with many protocols prioritizing one over the other.

Recently, DAG-based BFT protocols have emerged as a promising paradigm to boost the throughput of SMR. These protocols operate by allowing all nodes to act as proposers, contributing a single vertex to a DAG in each round. Each vertex is propagated using a Reliable Broadcast (RBC) primitive, ensuring eventual delivery to all honest nodes. A crucial aspect of these DAG structures is that a vertex in round r typically includes references to at least 2f+1 vertices from the previous round (r-1), where f is the maximum number of Byzantine nodes (assuming N > 3f total nodes). These references serve as "votes" and are later used to commit proposed vertices. While all nodes propose, there is typically a single designated leader in each round. The leader vertex is the one proposed by this leader, while all others are non-leader vertices. In existing DAG BFTs, only leader vertices are directly committed, with non-leader vertices being ordered as part of the causal history of a committed leader vertex.

The primary limitation of existing DAG-based protocols, however, has been their high commit latency. This is largely attributed to two structural issues:

1. Infrequent Leaders: Most existing DAG protocols feature a leader only every other round. This inherently delays the commitment process, as non-leader vertices must wait for a subsequent leader to be committed to be ordered.
2. High Leader Commit Latency: Even for leader vertices, the commitment process typically requires at least two RBCs. This means that a non-leader vertex from round r-1 might only be committed when a leader vertex from round r+1 is committed, demanding at least four RBCs in total. Given that non-leader vertices constitute the majority of proposed transactions in these high-throughput designs, this significantly inflates the overall latency experienced by the system.

The fundamental reason behind the "leaders every other round" design stems from a critical safety invariant. If the leader vertex of round r-1 is committed, it must be guaranteed that all subsequent leader vertices have a path linking back to this r-1 leader. If a leader were present in every round, this invariant could be easily broken. For instance, a round r leader might reference 2f+1 vertices from round r-1 without including the round r-1 leader itself. If such a round r leader vertex were committed, it would effectively commit round r before r-1, leading to safety violations where different honest nodes might commit different sequences of operations. This problem was widely considered "impossible" to solve in existing DAG BFT literature, leading to the adoption of less frequent leaders and the consequent latency penalties.

Key Findings

▶ Watch: Sailfish's breakthrough: supporting a leader in each round. (3:55)

Sailfish directly confronts the previously "impossible" problem of supporting a leader vertex in each round of a DAG-based BFT protocol, and in doing so, dramatically improves commit latency without sacrificing safety. The key findings and contributions of Sailfish are:

1. Feasibility of Leaders in Every Round: Sailfish demonstrates a novel mechanism that allows a leader vertex to be present and committed in every single round of the protocol. This directly addresses the safety invariant challenge that plagued prior designs, providing a robust solution where previous protocols deemed it unachievable.
2. Significantly Reduced Commit Latency:

• Leader Vertices: Sailfish reduces the commit latency for leader vertices from the typical two RBCs in existing protocols to an unprecedented 1 RBC + 1 delta, where delta represents the actual transmission delay of messages in the network. This is a substantial improvement, effectively halving the latency for critical leader-proposed transactions.
• Non-Leader Vertices: As a direct consequence of supporting a leader in each round and the optimized leader commit latency, non-leader vertices now only require an additional 1 RBC to be ordered after their respective leader commits. This translates to an overall ordering latency of 2 RBCs + 1 delta for non-leader vertices, a significant reduction from the four RBCs or more typically observed in prior DAG BFTs for these common transactions.

1. Empirical Performance Superiority: Experimental evaluations in a geo-distributed network spanning five Google Cloud Platform (GCP) regions demonstrate that Sailfish achieves "significantly better" latency compared to established DAG-based protocols such as Bullshark and SoL. This empirical validation underscores Sailfish's practical efficiency and potential for real-world deployment.

Technical Deep Dive

▶ Watch: How Sailfish ensures safety with a leader in every round. (4:15)

Sailfish's breakthroughs are rooted in two primary technical innovations: a refined constraint on leader vertex proposals to enable leaders in every round, and an optimized commitment rule that accelerates leader vertex finalization.

Enabling Leaders in Every Round

To overcome the safety invariant challenge, Sailfish introduces a conditional constraint on how a round r leader vertex is proposed. Specifically, a round r leader vertex must either:

1. Directly reference the round r-1 leader vertex: This is the ideal scenario where the r-1 leader was successfully delivered and agreed upon by honest parties. By including a reference, the round r leader explicitly acknowledges and incorporates the r-1 leader into its causal history, maintaining the necessary path for safety. Honest parties, upon receiving the r-1 leader vertex in a timely manner, will naturally vote for it by including its hash in their own round r proposals, including the leader's.
2. **Provide a cryptographic proof that the round r-1 leader vertex could not have been committed:** This is the mechanism that handles scenarios where the r-1 leader was either faulty or experienced significant network delays, preventing its timely delivery and subsequent commitment.

The "proof of non-commitment" mechanism works as follows:

• If honest parties fail to deliver the round r-1 leader vertex in a timely manner (e.g., due to a Byzantine leader or network issues), they cannot vote for it.
• Instead, these parties send "no board messages" (effectively "no vote" messages) to the round r leader vertex. These messages explicitly state that they did not vote for the round r-1 leader.
• If the round r leader receives a set of 2f+1 such "no board messages", this collection of messages serves as irrefutable proof that the round r-1 leader vertex will not be committed by the protocol. This threshold of 2f+1 is critical because it guarantees that at least f+1 of these messages must originate from honest parties, ensuring their collective decision is irreversible.
• Upon possessing this 2f+1 proof, the round r leader is then permitted to propose its vertex without referencing the round r-1 leader. This maintains safety because all honest nodes now agree that the r-1 leader is not committed, and thus, subsequent commitments do not need to establish a path to it. This elegant conditional logic allows Sailfish to safely support a leader in every round, addressing a problem previously considered intractable.

Reducing Leader Vertex Commit Latency

Existing DAG protocols typically wait for two full RBCs to terminate before committing a leader vertex. Sailfish optimizes this by leveraging an observation about the nature of RBCs:

• When the sender of an RBC is honest, the value included in the first message of the RBC is the value that will eventually be delivered and agreed upon by all honest parties.
• When the sender is Byzantine, the final delivered value could potentially differ from the value in the first message.

Sailfish capitalizes on the honest sender case to accelerate commitment. It commits a round r-1 leader vertex as soon as it receives 2f+1 "votes" (references) for that r-1 leader from the round r vertices.

• These 2f+1 votes are essentially acknowledgments or endorsements from subsequent vertices.
• Crucially, out of these 2f+1 votes, at least f+1 must originate from honest parties. This threshold is sufficient to ensure safety. If f+1 honest parties have voted for the r-1 leader, it means they have seen and accepted it. Since honest parties are guaranteed to eventually deliver messages from other honest parties, this ensures that all honest parties will eventually agree on the commitment of that r-1 leader.
• By adopting this rule, Sailfish avoids the need to wait for the completion of a second full RBC phase, directly reducing the leader vertex commit latency to 1 RBC + 1 delta. This streamlined commitment process, combined with leaders in every round, is the foundation for Sailfish's superior latency performance.

Demo / Proof of Concept

▶ Watch: Sailfish's method for reducing leader vertex commit latency. (6:00)

While the talk did not feature a live, interactive demonstration in the traditional sense, the speaker presented the results of an extensive experimental evaluation of Sailfish. This evaluation served as the empirical proof of concept, showcasing the protocol's performance benefits in a realistic, geo-distributed network environment.

The experiments were conducted across five Google Cloud Platform (GCP) regions, simulating a global distributed system. This setup allowed for an accurate assessment of latency under varying network conditions and geographical distances. The results, visualized in a figure mentioned by the speaker, demonstrated that Sailfish achieved "significantly better" latency compared to existing and well-regarded DAG-based BFT protocols, specifically citing Bullshark and SoL. The empirical data validated the theoretical latency improvements of 1 RBC + 1 delta for leader vertices and 2 RBC + 1 delta for non-leader vertices, confirming Sailfish's practical advantages over its predecessors. This rigorous experimental validation acts as a strong proof point for the efficacy and efficiency of the Sailfish design.

Defensive Implications

▶ Watch: Experimental results: Sailfish's significant latency improvement. (6:50)

Sailfish's contributions primarily impact the design and implementation of highly resilient distributed systems, rather than offering direct defensive actions for end-users or traditional network defenders. Its implications are strategic for architects and developers building critical infrastructure where Byzantine fault tolerance, high throughput, and low latency are paramount.

The key defensive implications are:

• Enhanced Resilience for Critical Systems: By providing a BFT protocol with demonstrably lower latency and higher efficiency, Sailfish enables the construction of more responsive and robust distributed applications. This is crucial for systems that cannot tolerate downtime or inconsistencies, even in the presence of malicious actors, such as financial trading platforms, supply chain management, or decentralized identity systems.
• Improved Responsiveness for SMR: For any application relying on State Machine Replication, Sailfish offers a pathway to significantly reduce the time required for transaction finality. This directly translates to a more responsive user experience and faster completion of distributed operations, which is a defensive measure against user dissatisfaction and operational bottlenecks.
• Foundation for Future BFT Research: Sailfish's solution to the "leader in every round" problem opens new avenues for research in DAG-based BFTs. Future protocols can build upon its innovations to further optimize other aspects of distributed consensus, potentially leading to even more performant and secure systems.
• Guidance for Protocol Selection: System designers evaluating BFT solutions for new deployments or upgrades now have a strong contender that offers a superior latency profile compared to existing DAG BFTs like Bullshark and SoL. This provides a clear benchmark and consideration for environments where latency is a critical performance metric.
• Addressing Fundamental BFT Challenges: By tackling a problem previously deemed "impossible" (safe leaders in every round), Sailfish strengthens the overall understanding and capabilities within the BFT research community, ultimately contributing to the development of more secure and reliable distributed computing paradigms.

In essence, Sailfish represents a significant defensive upgrade at the architectural level, enabling systems to perform better and resist a broader range of failures and attacks more efficiently.

Key Takeaways

• Solves the "Leader in Every Round" Problem: Sailfish successfully addresses a long-standing challenge in DAG-based BFT protocols, enabling the safe inclusion of a leader vertex in every round, a capability previously deemed impossible due to safety invariant concerns.
• Drastically Reduces Commit Latency: The protocol achieves a significant reduction in commit latency for both leader vertices (down to 1 RBC + 1 delta) and non-leader vertices (down to 2 RBC + 1 delta), an improvement from typical latencies of 2 RBCs and 4 RBCs respectively in existing designs.
• Introduces Novel Leader Proposal Constraint: Sailfish mandates that a leader vertex either explicitly references the previous round's leader or provides 2f+1 "no board messages" as proof that the previous leader could not have been committed, ensuring safety with frequent leaders.
• Optimized Commitment Rule: The protocol commits leader vertices faster by relying on 2f+1 votes from subsequent round vertices (with at least f+1 from honest parties), avoiding the need to wait for a second full RBC phase.
• Empirically Proven Performance: Experimental evaluations in a geo-distributed network (5 GCP regions) confirm Sailfish's superior latency performance when compared to established DAG-based BFT protocols like Bullshark and SoL.
• Enables More Responsive SMR Systems: By combining high throughput with low latency, Sailfish provides a robust foundation for building highly performant and fault-tolerant State Machine Replication systems for critical applications.

About the Speaker(s)

The primary presenter of the talk was Nibesh Shrestha, identified as a researcher at Supra. While the transcript focuses on Nibesh's presentation, the talk metadata also credits Rohan Shrothrium, Aniket Kate, and Kartik Nayak as speakers, indicating their significant contributions as co-authors to the Sailfish project. As a researcher, Nibesh Shrestha's work at Supra contributes to advancing the state of the art in distributed systems and consensus protocols, specifically in the domain of Byzantine Fault Tolerance, with a focus on practical performance improvements. The collaborative effort of the speaker team highlights a concerted academic and industry pursuit of highly efficient and secure decentralized technologies.