PaperlayerView exact revision on arXiv

Source-linked AI summary

Bullshark: DAG BFT Protocols Made Practical

Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, Lefteris Kokoris-Kogias

arXiv:2201.05677v3cs.CR

TL;DR

DAG-based Byzantine consensus traditionally optimized for asynchrony at the cost of synchronous latency and practical memory requirements. Bullshark adds a DAG-embedded fast path and a simpler partially synchronous implementation, achieving high throughput and low latency while retaining key asynchronous properties. Its bounded-memory fairness guarantee is limited to synchronous periods.

  • Problem

    DAG-based protocols optimize for asynchronous assumptions, leading to higher synchronous latency and requiring unbounded memory to preserve fairness.

  • Method

    BullShark embeds slow and fast consensus paths in a DAG, using synchronous fast-path conditions and DAG-encoded information instead of view changes.

  • Results

    125k TPS and 2-second latency are achieved with 50 honest parties, while the partially synchronous version uses 200 LOC and delivers 2x HotStuff throughput with 33% lower latency than Tusk.

  • Takeaways & Limitations

    BullShark combines optimal amortized communication, asynchronous liveness, post-quantum safety, garbage collection, and timely fairness after GST.

  • Takeaways & Limitations

    With bounded memory, BullShark guarantees timely fairness only during synchronous periods because arbitrarily delayed asynchronous blocks may be garbage-collected before inclusion.

Abstract

from arXiv · show

We present Bullshark, the first directed acyclic graph (DAG) based asynchronous Byzantine Atomic Broadcast protocol that is optimized for the common synchronous case. Like previous DAG-based BFT protocols, Bullshark requires no extra communication to achieve consensus on top of building the DAG. That is, parties can totally order the vertices of the DAG by interpreting their local view of the DAG edges. Unlike other asynchronous DAG-based protocols, Bullshark provides a practical low latency fast-path that exploits synchronous periods and deprecates the need for notoriously complex view-change mechanisms. Bullshark achieves this while maintaining all the desired properties of its predecessor DAG-Rider. Namely, it has optimal amortized communication complexity, it provides fairness and asynchronous liveness, and safety is guaranteed even under a quantum adversary. In order to show the practicality and simplicity of our approach, we also introduce a standalone partially synchronous version of Bullshark which we evaluate against the state of the art. The implemented protocol is embarrassingly simple (200 LOC on top of an existing DAG-based mempool implementation (Narwhal & Tusk). It is highly efficient, achieving for example, 125,000 transaction per second with a 2 seconds latency for a deployment of 50 parties. In the same setting the state of the art pays a steep 50% latency increase as it optimizes for asynchrony.

1 INTRODUCTION

Bullshark addresses practical gaps in DAG-based Byzantine consensus by adding a synchronous fast path while retaining asynchronous guarantees and fairness. Its partially synchronous implementation is simple and efficient, with low latency and high throughput.

  • Motivation: DAG-based protocols can totally order transactions by locally interpreting graph edges after dissemination, requiring no extra consensus communication.The DAG separates transaction dissemination from ordering logic.
  • Motivation: Existing DAG protocols optimize for asynchronous networks, causing higher good-case latency and requiring unbounded memory for fairness.Tusk provides garbage collection but lacks quantifiable fairness during synchrony.
  • BullShark: BullShark adds a synchronous fast path while preserving DAG-Rider’s optimal O(n) amortized communication, post-quantum safety, and asynchronous liveness.It needs 2 roundtrips during synchrony and 6 roundtrips in expectation asynchronously.
  • Evaluation: 125k TPS and 2-second latency are achieved with 50 honest parties in BullShark’s partially synchronous variant.The implementation is described as an additional 200 lines of code and is productionized for integration in blockchain systems.
  • Contributions: BullShark’s partially synchronous protocol is simpler than prior work and improves latency and resilience while supporting garbage collection and timely fairness after GST.Its practical design is built on Narwhal’s DAG-based mempool.

2 TECHNICAL CHALLENGES.

BullShark’s design addresses the tension between asynchronous worst-case guarantees and synchronous performance, while avoiding view changes and confronting bounded-memory fairness limits.

  • Theoretical challenges: Round advancement based only on 2f+1 delivered vertices cannot guarantee deterministic synchronous liveness because message ordering can bypass predefined leaders.BullShark therefore extends the advancement condition to commit honest leaders after GST.
  • Theoretical challenges: BullShark must exploit synchronous periods without sacrificing asynchronous worst-case latency.It introduces steady-state and fallback votes organized into four-round waves.
  • Theoretical challenges: BullShark avoids view-change and view-synchronization mechanisms by using DAG-encoded causal histories to inspect which leaders other parties could have committed.Parties traverse the DAG backward wave by wave after a leader is committed.
  • Practical challenges: The bounded-memory implementation guarantees timely fairness only during synchronous periods and uses retransmission for messages sent before GST.Before GST, guarantees apply only to an unbounded execution.

3 PRELIMINARIES

The paper formalizes Byzantine atomic broadcast under reliable message passing, eventual synchrony, and a bounded Byzantine adversary. Its practical validity requirement is restricted after GST because asynchronous bounded-memory fairness is impossible.

  • System model: The model contains n parties and allows a dynamic adversary to corrupt up to f < n/3 parties, which may behave arbitrarily.Honest parties follow the protocol and the adversary is computationally bounded.
  • System model: Eventually synchronous executions have a global stabilization time after which honest-party messages arrive within a known bound Δ.Links between honest parties are reliable and sender identities are verifiable.
  • Evaluation conditions: The evaluation distinguishes asynchronous executions with Byzantine parties from synchronous, failure-free executions and their post-GST counterparts.These scenarios represent worst-case and common-case conditions.
  • Building blocks: Reliable broadcast provides delivery, integrity, and validity abstractions for messages associated with rounds and senders.An honest sender’s broadcast is eventually delivered by every other honest party and at most once.
  • Building blocks: The global perfect coin provides agreement, termination, unpredictability, and fairness for wave leader selection.Its fairness condition assigns probability 1/n to each party.
  • Problem definition: Byzantine atomic broadcast adds total ordering to reliable broadcast and supports proposing and delivering messages by sequence number.In asynchronous executions, validity is probabilistic, while the bounded-memory practical version requires validity only after GST.

4 DAG CONSTRUCTION

BullShark modifies DAG construction with timeouts and structured edges so the DAG supports deterministic synchronous progress while retaining asynchronous advancement. Vertices carry transaction blocks and strong or weak causal references used by the ordering protocol.

  • DAG construction: BullShark integrates timeouts into DAG construction because deterministic synchronous latency cannot be guaranteed by asynchronous round advancement alone.Despite timeouts, the DAG advances at network speed when the leader is honest.
  • DAG data structures: Each DAG vertex represents a reliably broadcast message containing a transaction block, source, round, and references to earlier vertices.Each party maintains a local DAG view that may differ according to delivery order.
  • DAG data structures: Strong edges reference at least 2f+1 vertices from the previous round, while weak edges reference up to f older vertices lacking another path.Strong edges support safety and weak edges help include all vertices for validity.
  • Leader selection: BullShark groups four rounds into waves with predefined steady-state leaders and randomly selected fallback leaders.Leader vertices act as proposals, while following vertices with strong edges act as votes.
  • Round advancement: The protocol validates delivered vertices, adds them when their causal history is ready, and advances rounds on vertex delivery or timeout expiration.Each party broadcasts a new vertex and starts a timeout when advancing.
  • Synchronous progress: After GST, timeouts do not expire for honest leaders and the DAG advances at network speed.The round conditions are extended to ensure honest steady-state leaders are committed promptly.

5 THE BULLSHARK PROTOCOL

BullShark interprets a four-round DAG wave using steady-state and fallback leaders, committing leaders from locally observed votes while preventing conflicting vote types. Once a leader commits, parties order its causal history and recover earlier leaders deterministically without extra communication.

  • Wave structure: BullShark divides each local DAG view into four-round waves with two predefined steady-state leaders and one retrospectively elected fallback leader.Steady-state leaders occupy the first and third rounds; the fallback leader occupies the first round and is selected using randomness from the fourth round.
  • Performance and liveness: During asynchrony, BullShark commits a fallback leader every 6 rounds in expectation with probability-1 liveness, while synchronous execution commits steady-state leaders in two DAG rounds.The fast path also avoids external view-change and view-synchronization mechanisms because the DAG records the information needed for safety.
  • Voting Types: Parties assign each party a steady-state or fallback voting type so the two leader types cannot both be committed in one wave.A party’s type is determined from whether its causal history contains enough information to commit a prior steady-state or fallback leader.
  • Commit rules: At least 2f + 1 appropriate votes with strong paths commit a steady-state or fallback leader.The procedures separately count votes from steadyVoters or fallbackVoters before invoking leader commitment.
  • Ordering The DAG: A committed leader triggers backward traversal of the DAG to identify earlier leaders that other honest parties could have committed.A leader is ordered when it has at least f + 1 votes while the competing leader has at most f; otherwise both are skipped.
  • Ordering The DAG: All honest parties order the same leaders in the same order, then deterministically deliver the blocks in their causal histories.The ordering procedure is invoked after leader commitment and finishes by ordering each leader’s vertices.

6 EVENTUALLY SYNCHRONOUS BULLSHARK

The eventually synchronous BullShark variant removes fallback leaders and repeatedly commits predefined steady-state leaders. After synchrony begins, two consecutive honest leaders synchronize progress and ensure the second leader is committed by all honest parties.

  • Protocol variant: The eventually synchronous variant omits fallback leaders and repeatedly attempts to commit steady-state leaders.Its ordering procedure tries the second leader of the previous wave and the first leader of the current wave.
  • Liveness: After GST, two consecutive honest predefined leaders guarantee that the second leader is committed by all honest parties.An honest first leader synchronizes parties before the third round; an honest second leader makes them wait until they observe at least 2f + 1 votes.
  • Commit rule: A steady-state leader is committed when at least f + 1 observed vertices have strong paths to it.The variant then pushes the leader onto the ordering stack and may traverse earlier leaders two rounds at a time.

7 GARBAGE COLLECTION IN BULLSHARK

BullShark addresses the tension between fairness and bounded memory by accepting fairness only after GST and garbage collecting rounds using timestamps and committed leaders. The mechanism preserves delivery guarantees after GST while enabling bounded memory.

  • Fairness and memory: Fully asynchronous executions cannot provide fairness with bounded memory because honest blocks may be arbitrarily delayed.The protocol cannot distinguish a faulty party from a slow honest party whose block must still be awaited.
  • Fairness and memory: BullShark maintains bounded memory by providing fairness only after GST and using a strong, complete failure detector after GST.The failure detector permits garbage collection without waiting indefinitely for faulty parties.
  • Fairness: If an honest party broadcasts after GST, every honest party eventually delivers its message, satisfying BullShark’s post-GST fairness definition.The fairness proof uses reliable delivery after GST and the median timestamp of each round.
  • Garbage-collection mechanism: Every vertex receives a timestamp, while GCround prevents parties from adding vertices to already collected rounds.The implementation uses broadcast times and a garbage-collection frontier to remove old DAG data.
  • Garbage-collection mechanism: After parties agree which leaders to order, reliable broadcast makes them agree on the causal histories and the rounds to garbage collect.This agreement preserves the protocol’s safety and liveness properties during garbage collection.
  • Bounded memory: For every round r, a later committed leader eventually has a high enough timestamp for round r to be garbage collected.The proof establishes eventual commitment and therefore eventual reclamation of earlier rounds.

8 IMPLEMENTATION

BullShark is implemented as a networked, multi-core eventually synchronous protocol by modifying Narwhal’s structured DAG and existing Tusk codebase. The implementation adds fewer than 200 lines and no extra protocol messages or cryptographic tools.

  • Implementation: BullShark forks Narwhal, reuses its structured DAG, and modifies it to support the fast path under partial synchrony.The implementation also uses Narwhal’s benchmarking infrastructure and production-oriented networking and persistence components.
  • Implementation: The implementation is written in Rust and uses tokio for asynchronous networking, ed25519-dalek for signatures, RocksDB for persistence, and TCP for reliable channels.The system is released with orchestration scripts and measurement data to support reproducibility.
  • Implementation: Implementing BullShark requires editing less than 200 LOC and adds no extra protocol message or cryptographic tool.The changes affect the proposer and consensus components of the existing codebase.

9 EVALUATION

The evaluation measures BullShark against HotStuff and Tusk across committee sizes, WAN conditions, load, and crash faults. BullShark combines Tusk-like throughput and scalability with HotStuff-like latency, while retaining a fallback mode for asynchrony.

  • Evaluation setup: The AWS evaluation targets high throughput, low latency under WAN load and large committees, and robustness to crash faults.The authors note that evaluating BFT protocols under Byzantine faults remains an open research question.
  • Evaluation setup: Measurements average two independent runs, with error bars showing one standard deviation; baseline settings use 10 honest parties, 500KB blocks, and 512B transactions.Each benchmark runs for five minutes with one collocated client per party.
  • Common-case performance: HotStuff reaches 70,000 tx/s with 10 parties, up to 50,000 tx/s with 20 parties, and around 30,000 tx/s with 50 parties, with latency around 2 seconds before saturation.These results show decreasing throughput as committee size increases.
  • Common-case performance: Tusk peaks at 110,000 tx/s with 10 parties and around 160,000 tx/s with 20 and 50 parties, but its latency remains around 3 seconds.The throughput increase with committee size is attributed to improved multiplexing of underutilized resources.
  • Common-case performance: BullShark reaches 110,000 tx/s with 10 parties and 130,000 tx/s with 50 parties, while maintaining around 2-second latency across committee sizes.Its latency is 33% lower than Tusk’s and comparable to HotStuff’s because it commits within 2 DAG rounds rather than 4.
  • Performance under faults: With three crash faults, HotStuff’s throughput drops by over 10x and its latency increases by 15x compared with no faults, whereas Tusk and BullShark maintain good throughput.The underlying DAG continues collecting transactions despite crashes.
  • Performance under asynchrony: Before GST, the partially synchronous BullShark variant can lose liveness when leader proposals are delayed, so it falls back to Tusk-like behavior under asynchrony.Fallback preserves asynchronous liveness but relinquishes BullShark’s latency advantage until synchrony returns.

10 RELATED WORK

BullShark is compared with asynchronous DAG protocols and partially synchronous systems, emphasizing practical performance, implementation effort, and evaluation scope. The comparison highlights BullShark’s resilience under faults and its compact implementation, while noting limits on directly comparing omitted systems.

  • Performance comparisons: BullShark is compared with Tusk and HotStuff because they provide open-source implementations with similar systems infrastructure and WAN-oriented designs.The selected implementations use Rust and share network, cryptographic, and storage libraries with BullShark.
  • Comparison scope: The comparison omits several related works because their implementations differ in cryptography, languages, storage, networking, or multithreading.The authors instead discuss those alternatives using their reported performance.
  • Partially-synchronous protocols: BullShark adds about 200 LOC over Narwhal, compared with more than 4k LOC for HotStuff over a DAG.The paper characterizes BullShark’s engineering effort as roughly half that of HotStuff-over-Narwhal.
  • Partially-synchronous protocols: Mir-BFT reaches around 80,000 tx/sec under 2 seconds for 20 WAN parties, but crash-faults can reduce throughput to zero for up to 50 seconds.Operation resumes after reconfiguration excludes faulty nodes.

11 DISCUSSION

BullShark combines partially synchronous fast-path behavior with asynchronous fallback while using the DAG to avoid extra communication and view-change machinery. Its ordering rules commit selected leaders and then deterministically order their causal histories.

  • Discussion: BullShark combines partially synchronous and asynchronous behavior while retaining optimal amortized complexity, asynchronous liveness, and post-quantum security.Parties switch their voting type to fallback after every unsuccessful wave.
  • Discussion: The partially synchronous version uses 200 LOC, achieves 2x HotStuff’s throughput, and has 33% lower latency than asynchronous Tusk over Narwhal.The DAG supplies the information needed without view-change or view-synchronization mechanisms.
  • Partially synchronous Bullshark: Odd DAG rounds designate leaders, while even-round vertices vote for the previous-round leader; a leader commits with at least f + 1 votes.In the illustrated n = 4, f = 1 example, L3 commits with three votes.
  • Partially synchronous Bullshark: Quorum intersection ensures that if a future leader has no path to leader L, no party committed L and it is safe to skip L.This reconciles differing local DAG views among parties.
  • Partially synchronous Bullshark: Committed leaders are ordered by checking paths to preceding leaders, skipping leaders without a path and recursively ordering reachable predecessors.After leader ordering, parties deterministically order each committed leader’s causal history.

B LOGICAL VS PHYSICAL DAG

The authors compare embedding timeouts directly in the physical DAG with a separate virtual consensus layer. The evaluated logical split increased latency without improving throughput, so the integrated construction was preferred.

  • Physical DAG: BullShark embeds timeouts into DAG construction to support deterministic fast-path liveness during synchrony.The authors considered this preferable to a separate virtual consensus layer.
  • Logical DAG: A virtual consensus layer would place consensus headers on selected physical-DAG nodes and advance virtual rounds independently of physical rounds.Timeouts would apply only at the virtual level.
  • Evaluation: Around 50% latency increase occurred for the logical DAG construction without any significant throughput benefit.The evaluation therefore did not support separating virtual and physical DAG layers.
  • Evaluation: Because Narwhal disseminates data independently at network speed, slower DAG-round advancement increases metadata per vertex without compromising throughput.This decoupling explains why integrating timeouts into DAG construction need not reduce transaction throughput.

C PROOFS

The paper provides correctness proofs for both versions of BullShark.

  • Proofs: Correctness proofs are provided for both BullShark versions.

C.1 BullShark With Fallback

BullShark locally interprets a four-round DAG wave using steady-state and fallback leaders, with consistent vote-type determination and mutually exclusive leader commitments. The protocol establishes total order, validity, and progress while honest parties commit the same leaders in the same order.

  • Wave structure and leader selection: BullShark divides the DAG into four-round waves containing two steady-state leaders and one randomly selected fallback leader.Parties vote either for the steady-state leaders or for the fallback leader, preventing both leader types from being committed in the same wave.
  • Wave structure and leader selection: Every party determines each party’s vote type consistently within a wave, so different parties cannot assign conflicting vote types.The protocol adds vertices only after their complete causal histories, supporting consistent local DAG views.
  • Safety and ordering: Honest parties commit the same leaders and in the same order, yielding the protocol’s Total order property.This follows from the commitment claims and the stated corollary for honest parties.
  • Liveness and validity: For every round, each honest party eventually receives a vertex from every honest party, supporting continued DAG growth.The protocol also proves that an honest party commits a leader in a higher wave with probability 1.
  • Liveness and validity: The algorithms satisfy Validity in addition to Total order, as stated by the protocol’s formal lemmas.The section presents these properties alongside probabilistic progress claims for higher waves.
  • Liveness and validity: If all honest parties reach a wave after GST and both predefined leaders are honest, all honest parties commit a leader in that wave.The fallback mechanism supplies an alternative leader path when the steady-state path does not commit one.
Loading 2201.05677v3…