Source-linked AI summary
Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus
George Danezis, Eleftherios Kokoris Kogias, Alberto Sonnino, Alexander Spiegelman
TL;DR
High-performance ledgers are constrained by reliable transaction dissemination as well as consensus ordering. The paper separates these tasks with Narwhal, a causal-history mempool, and combines it with HotStuff or Tusk; WAN experiments report high throughput, while asynchronous protocols retain a fairness limitation for slow authorities.
Problem
Reliable transaction dissemination can bottleneck ledger performance when consensus protocols handle bulk transaction data in their critical path.
Method
Narwhal provides reliable asynchronous dissemination and storage of causal transaction histories, which can be paired with HotStuff or Tusk for ordering.
Results
130,000 tx/sec at under 2 seconds latency is achieved by Narwhal-HotStuff, while Tusk achieves 160,000 TPS with about 3 seconds latency.
Takeaways & Limitations
Separating dissemination from ordering supports high-throughput quorum-based ledgers and scale-out to potentially millions of transactions per second.
Takeaways & Limitations
Slow authorities are indistinguishable from faulty ones, so correct geographically distant authorities may commit transactions submitted to them later.
Abstract
from arXiv · showhide
We propose separating the task of reliable transaction dissemination from transaction ordering, to enable high-performance Byzantine fault-tolerant quorum-based consensus. We design and evaluate a mempool protocol, Narwhal, specializing in high-throughput reliable dissemination and storage of causal histories of transactions. Narwhal tolerates an asynchronous network and maintains high performance despite failures. Narwhal is designed to easily scale-out using multiple workers at each validator, and we demonstrate that there is no foreseeable limit to the throughput we can achieve. Composing Narwhal with a partially synchronous consensus protocol (Narwhal-HotStuff) yields significantly better throughput even in the presence of faults or intermittent loss of liveness due to asynchrony. However, loss of liveness can result in higher latency. To achieve overall good performance when faults occur we design Tusk, a zero-message overhead asynchronous consensus protocol, to work with Narwhal. We demonstrate its high performance under a variety of configurations and faults. As a summary of results, on a WAN, Narwhal-Hotstuff achieves over 130,000 tx/sec at less than 2-sec latency compared with 1,800 tx/sec at 1-sec latency for Hotstuff. Additional workers increase throughput linearly to 600,000 tx/sec without any latency increase. Tusk achieves 160,000 tx/sec with about 3 seconds latency. Under faults, both protocols maintain high throughput, but Narwhal-HotStuff suffers from increased latency.
1 Introduction
The paper argues that reliable transaction dissemination should be separated from consensus ordering, because bulk data transfer—not metadata message complexity—limits ledger performance. Narwhal implements this separation and, with HotStuff and scale-out workers, substantially improves WAN throughput.
- 1 Introduction: Consensus message complexity overlooks the bandwidth burden of disseminating bulk transaction data, which is orders of magnitude larger than metadata.The paper contrasts roughly 10MB blocks with typical 100B consensus messages for committees of up to about 50 nodes.
- 1 Introduction: Separating reliable dissemination from ordering lets consensus sequence small fixed-size references rather than transaction data.The paper hypothesizes that this makes overall throughput less dependent on consensus throughput.
- 1 Introduction: Narwhal provides reliable dissemination and storage of causal transaction histories, while Narwhal-HotStuff combines it with partially synchronous ordering.The design addresses prior approaches that separate transmission from metadata without guaranteeing reliability.
- 1 Introduction: More workers increase throughput to over 500,000 tx/sec while keeping latency below 3.5 seconds.Figure 1 compares traditional mempools, Narwhal, and many-worker configurations for 512B transactions.
2 Overview
Narwhal is a persistent, Byzantine fault-tolerant DAG mempool that reliably disseminates transaction blocks and exposes their causal structure. Its certificates, containment properties, rate controls, and worker-based scale-out support both robust consensus integration and high throughput.
- 2 Overview: Narwhal provides a persistent Byzantine fault-tolerant store with availability and a partial order over transaction blocks under asynchronous communication.The system assumes eventually reliable links among honest parties with unbounded and unknown message delays.
- 2 Overview: A block digest identifies its contents, while references to prior blocks encode causal happened-before relations.Transaction and reference order within a block also contributes to the encoded ordering.
- 2 Overview: Narwhal’s mempool operations provide integrity, block availability, containment, and 2/3-causality guarantees.A successful causal read includes at least two-thirds of blocks written successfully before the corresponding write was invoked.
- 2 Overview: Causality and containment allow consensus to order accumulated causal histories after synchrony returns, preserving throughput during asynchrony.The consensus layer can agree on a block digest and then safely totally order its causally ordered blocks.
- 2.2 Intuitions behind the Narwhal design: Narwhal’s rate restrictions provide chain quality and censorship resistance by ensuring proposals include honest transactions and preventing flooding.The paper states that proposals include at least 50% of honest transactions, including proposals from Byzantine leaders.
- 4.2 Scale-Out Validators: Scale-out workers parallelize transaction batching, transfer, and storage, while primaries share compact batch hashes and references.A quorum acknowledgment is obtained before a batch hash is shared with the primary.
3 Narwhal Core Design
Narwhal builds a persistent block DAG that certifies transaction availability and supports consensus by ordering certificate references rather than bulk transactions. Its quorum structure also enables bounded storage and safe garbage collection.
- Core protocol: Narwhal combines reliable broadcast, reliable storage, and threshold clocks to maintain a DAG-based mempool.Validators advance rounds after collecting 2f+1 certificates and create blocks containing transactions and prior-round certificates.
- Core protocol: 2f+1 acknowledgments form an availability certificate, while quorum intersection supports block availability and integrity.At least f+1 honest validators have checked and stored each certified block.
- Consensus integration: Consensus protocols can order Narwhal certificates; validators then deterministically order and commit their causal histories.Narwhal makes the referenced blocks and transactions retrievable for sequencing.
- Consensus integration: Narwhal continues certifying blocks during asynchrony, although eventually synchronous consensus still loses liveness and incurs increased latency.Tusk is introduced to address this liveness problem.
- Garbage collection: Validators can use fixed-size memory because certificates preserve availability and integrity while older rounds can be safely removed.Garbage collection re-injects delayed transactions into later rounds, preserving eventual inclusion.
4 Building a Practical System
Narwhal’s practical design uses quorum-certified dissemination, worker-primary scale-out, streaming, and pull-based retrieval to preserve availability while reducing primary and retransmission costs.
- Quorum-based reliable broadcast: 2f+1 signatures certify block availability, and subsequent certificates plus pull requests recover missing causal-history blocks.This avoids perfect point-to-point channels and bounds retransmission storage by round advancement and block retrieval time.
- Scale-out architecture: A primary-worker architecture parallelizes transaction transfer and storage while the primary handles DAG metadata and worker-batch hashes.Workers exchange batches across validators; the primary includes their hashes in blocks.
- Scale-out architecture: Worker storage and adapted signing rules ensure every batch referenced by an availability certificate can be retrieved.Primaries pull missing batches directly from the creator’s associated worker.
- Streaming: Streaming small batches makes transaction data available before primary blocks arrive, reducing signing and round-advance wait time.The batches are approximately 500KB and contain a few hundred to a few thousand transactions.
- Future bottlenecks: At extreme scale, primary-block size may become the bottleneck, although evaluation did not observe it and the design estimates about 12,000 workers before parity with worker data volume.A 512KB batch represented by a 40B hash-and-metadata reference yields a 1:12 volume reduction.
5 Tusk asynchronous consensus
Tusk interprets Narwhal’s causal DAG in three-round waves, using shared randomness to select leaders and locally derive a total order with zero extra communication. Its recursive ordering preserves agreement among honest validators and yields constant-round commitment guarantees under both asynchronous and randomly delayed networks.
- Protocol design: Tusk uses Narwhal’s causally ordered DAG and shared randomness to totally order blocks without extra communication.Each validator locally interprets its DAG view and uses the shared coin to determine the total order.
- Protocol design: Each Tusk wave has three rounds for proposing blocks, voting on proposals, and generating randomness to retrospectively elect a leader.A leader commits when at least f+1 blocks in the wave’s second round refer to it.
- Safety: Tusk recursively orders intervening leaders by checking causal paths, ensuring that honest validators commit the same sequence of block leaders.Narwhal’s containment property then makes honest validators agree on the total order of DAG blocks.
- Performance: Tusk adds zero message overhead over Narwhal while retaining Narwhal’s theoretical throughput.Neither shared-coin generation nor consensus logic introduces additional messages.
- Liveness and latency: Tusk commits a block leader every 7 rounds in expectation under an asynchronous adversary.Randomness selects the leader only after the wave’s first two rounds are fixed, supporting liveness against an adaptive asynchronous adversary.
- Liveness and latency: 4.5 rounds is Tusk’s expected commitment interval for each DAG block when message delays are randomly distributed.This improves on DAG-Rider’s 5.5-round common-case interval through three-round waves and piggybacking.
6 Implementation
The authors implement and evaluate networked multi-core versions of Narwhal-based protocols and Hotstuff, adding persistent storage, WAN evaluation, and a pacemaker to the Hotstuff implementation.
- Implementation: The implementation is a networked multi-core Narwhal validator written in Rust with asynchronous networking, signatures, persistent RocksDB storage, and reliable TCP channels.The system maintains peer-send queues in memory and transmits messages over persistent point-to-point channels.
- Evaluation setup: The evaluation covers Tusk, HS-over-Narwhal, and two Hotstuff variants designed for fair comparison.The Hotstuff implementation adds persistent storage, WAN evaluation, and a pacemaker based on the LibraBFT specification.
7 Evaluation
AWS experiments evaluate Narwhal, Narwhal-HotStuff, Tusk, and baselines across WAN configurations, validator counts, workers, latency, throughput, and crash faults. Narwhal-based systems sustain high throughput, scale with workers, and remain more resilient to faults than baseline approaches, although latency can increase.
- Experimental setup: The WAN testbed spans five AWS regions using m5.8xlarge instances, and each graph measurement averages two runs.The experiments measure latency from client submission until commitment under high load.
- Baselines: 70,000 tx/sec is the maximum observed for Batched HotStuff with 10 nodes, compared with baseline HotStuff staying below 1,800 tx/s for 10 or 20 validators.Batched HotStuff reaches up to 50,000 tx/s with 20 nodes, while baseline latency is around 1 second at low throughput.
- Narwhal-HotStuff: 140,000 tx/sec at latency consistently below 2 seconds is achieved by Narwhal-HotStuff across committee sizes with one worker per validator.The evaluation uses Narwhal with HotStuff across different committee sizes.
- Tusk: 170,000 tx/sec is the peak throughput observed for Tusk with 50 validators, while latency remains around 3 seconds across committee sizes.Tusk uses one worker collocated with the primary per validator.
- Worker scaling: Throughput scales approximately linearly with the number of workers while latency remains unchanged in the worker-scaling experiments.Deployments with more workers saturate later, and the reported scaling is close to workers multiplied by one-worker throughput.
- Performance under faults: With three crash faults, baseline HotStuff drops 5x in throughput and increases latency 40x, while Batched HotStuff drops 30x and increases latency 10x.Tusk and Narwhal-HotStuff maintain good throughput under one or three crash faults; Tusk commits in less than 6 seconds under three faults.
8 Related work & Limitations
The paper argues that reliable transaction dissemination, not isolated consensus message complexity, determines ledger performance under faults. It also identifies boundaries involving fairness, storage retrieval, execution capacity, and the decision not to address sharding.
- Limitations: The paper does not address sharding, and Narwhal's scale-out shifts transaction retrieval to the execution engine while high throughput requires an execution engine able to match it.Efficient execution for Narwhal is deferred to future work.
- Limitations: Narwhal's reactive asynchronous design cannot distinguish slow authorities from faulty ones, creating fairness and incentive issues for geographically distant but correct authorities.The paper leaves fairness mechanisms for future work.
- Limitations: Narwhal relies on client re-submission when a faulty leader prevents timely sequencing; submitting to f+1 authorities would divide authority bandwidth by O(n).Submitting to a fixed k authorities incurs O(1) overhead and rapidly increases the probability of including a correct authority.
9 Conclusion
The conclusion presents Narwhal as a high-throughput mempool that lets quorum-based consensus remain performant under faults and asynchrony. Tusk extends this structure to asynchronous consensus, while scale-out raises throughput without increasing latency in the reported design.
- Conclusion: 130,000 tx/sec at under 2 seconds latency is achieved by HotStuff with Narwhal across 50 geographically distributed single-machine validators.The conclusion also states that Narwhal helps quorum-based protocols maintain throughput during faults or asynchrony when consensus eventually regains liveness.
- Conclusion: Narwhal and Tusk identify reliable transaction dissemination as the main cost of large-scale blockchain protocols rather than consensus.The conclusion frames this as motivation to rethink distributed-ledger and state-machine-replication architecture.
- Conclusion: Hundreds of thousands of transactions per second are reached through scale-out without impact on latency.The paper describes dissemination as embarrassingly parallelizable when global sequencing is separated from it.
- Conclusion: The proposed architecture pairs a high-throughput mempool for faults and asynchrony with consensus for low-latency ordering of fixed-size messages.Tusk supplies a zero-message-overhead consensus protocol secure under full asynchrony.
A.1 DAG
The DAG protocol provides integrity, block availability, containment, causality, and censorship-resistance properties through certified blocks and quorum-based storage and references.
- DAG guarantees: Integrity ensures that certified blocks cannot yield conflicting values from honest reads.The protocol requires 2f+1 signatures and honest validators do not sign two different same-round blocks from one author.
- DAG guarantees: Block-Availability ensures that a later honest read of a successfully written block eventually returns that block.At least f+1 honest validators store every certified block, and reads wait for n−f replies.
- DAG guarantees: Containment requires causal-read results to be nested: a later read's returned block set is a subset of the earlier set.This preserves consistency among causal histories exposed by the DAG.
A.2 Asynchronous consensus
The asynchronous-consensus appendix establishes ordered, consistent leader commits and analyzes Tusk's expected commit progress under asynchronous and random-delay settings.
- Safety: Any two honest validators commit the same sequence of block leaders.The result follows from the property that later committed leaders have paths to earlier committed leaders.
- Safety: At least f+1 blocks in the first round of every wave satisfy Tusk's commit rule.The appendix derives this from quorum links among second-round blocks and first-round blocks.
- Liveness: In expectation, Tusk commits a block leader every 7 rounds under an asynchronous adversary.The proof uses a uniformly distributed random coin and a lower-bounded probability of selecting a leader satisfying the commit rule.
- Liveness: With random message delays, Tusk commits each DAG block in expectation in 4.5 rounds.The appendix analyzes the probability that enough second-round blocks reference the instance leader.
- Reproducibility: The implementation and benchmark orchestration scripts, measurements, and data are open-sourced for reproducibility.The appendix identifies Rust implementations and AWS benchmarking resources.
B.4.1 Major Claims.
The section reports Narwhal’s claimed advantages, linear scale-out, and Tusk’s performance as a consensus protocol. It also describes experiments varying workers, committee sizes, and crash-faults, with AWS costs noted as a limitation.
- Narwhal is claimed to improve on the existing simple mempool and straightforward extensions.
- Tusk leverages Narwhal to maintain high throughput as the number of validators increases.
- The experiments evaluate common-case performance across committee sizes, worker scalability, and crash-fault configurations.
- The configurations vary committee sizes from 10 to 50 nodes, workers from 1 to 10, and crash-faults from 0 to 3.
- The AWS experiments can be very expensive, creating a practical evaluation constraint.