[논문 리뷰] Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus

Authors

  : George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman

 

Journal/Conference

  : EuroSys '22, New York, NY, USA, 34–50.

 

Source

  :  https://doi.org/10.1145/3492321.3519594

 

---

Abstract

  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.

---

Introduction

• Leader-based BFT protocols have leader-bottleneck.
• Block message size (10MB) is larger than consensus message size (100B). Therefore, they should be separated.
• Implemented Batched-HS(using WRBC), Narwhal-HS, and Tusk.

---

Narwhal

  : shared mempool protocol. A leader in any leader-based BFT protocols combined with Narwhal can just propose block hash and its own id (40B in Narwhal-HotStuff).

 

• HotStuff-like round structure (Threshold Clock structure) => using qualified certificates, and \(O(n)\) bits complexity.
• All parties are leaders, meaning that each party propose a block of transactions in a Threshold Clock structured way, and contructs a DAG locally using qualified certificates, which includes causual history of broadcasts.
• Garbage collection
• Adopt pull strategy to re-transmission for missing blocks at the next round.

DAG + Threshold qualified certificates + pull strategy => amortized O(n) communication complexity RBC with censorship resilience.

---

Tusk

  : fully asynchronous BFT protocol by combining Narwhal and modified DAG-Rider.

• Replace RBC protocol \(O(n^2)\) to Narwhal \(O(n)\).
• Remove weak-links for garbage collection.
• Reduce the number of rounds per a wave. Therefore, the expected number of rounds is reduced from 5.5 rounds to 4.5 rounds 

---

Limitations

• Fairness: slow authorities are indistinguishable from faulty ones, and as a result the protocol proceeds without them. This creates issues around fairness and incentives, since perfectly correct, but geographically distant authorities may only be able to commit transactions submitted to them much later --> fundamental limitation of asynchronous protocols
• Censorship: Narwhal relies on clients to re-submit a transaction if it is not sequenced in time, due to the leader being faulty.
• Narwhal 's scale-out approach places a new burden on the execution engine. The execution engine now needs to locate and retriever transaction data from the various workers
• the high throughput of Narwhal and Tusk is only useful if there exist a transaction engine capable to match their speed.