Skip to main content

Sui Mempool and Consensus Engines

This is a brief introduction to Narwhal, and Bullshark, the high-throughput mempool and consensus engines offered by Mysten Labs. Sui uses Narwhal as the mempool and Bullshark as the consensus engine by default, to sequence transactions that require a total ordering, synchronize transactions between validators and periodically checkpoint the network's state.

The names highlight that the components split the responsibilities of:

  • ensuring the availability of data submitted to consensus = Narwhal
  • agreeing on a specific ordering of this data = Bullshark

The Sui consensus engine represents the latest variant of decades of work on multi-proposer, high-throughput consensus algorithms that reach throughputs of more than 125,000 transactions per second with a two-second latency for a deployment of 50 parties, with production cryptography, permanent storage, and a scaled-out primary-worker architecture.

The Sui consensus engine approach can offer dramatic scalability benefits in the following cases:

  • a blockchain that has experimented with larger and larger blocks and has measured runaway latencies before the execution phase
  • a blockchain with fast execution (e.g., focused on transactions or with an UTXO data model), but which mempool and consensus do not keep up

Features​

The Narwhal mempool offers:

  • a high-throughput data availability engine, with cryptographic proofs of data availability at a primary node
  • a structured graph data structure for traversing this information
  • a scaled architecture, splitting the disk I/O and networking requirements across several workers

The consensus component offers a zero-message overhead consensus algorithm, leveraging graph traversals.

Architecture​

A Narwhal instance sets up a message-passing system comprised of a set of 3f+13f+1 units of stake divided amongst a set of nodes, and assumes a computationally bounded adversary that controls the network and can corrupt parties holding up to f units of stake. The validators collaborate in forming a leaderless graph of batches of transactions - which the literature (in the context of DAG-based consensus) designates as blocks and that Sui labels collections - to emphasize that this happens in a context where the mempool data is used by an unspecified consensus algorithm.

The graph's vertices consist of certified collections. Each valid collection signed by its validator-author must contain a round number and must itself be signed by a quorum (2f+1) of validator stake. These 2f+1 signatures are called a certificate of availability. Furthermore, that collection must contain hash pointers to a quorum of valid certificates (that is, certificates from validators with 2f + 1 units of stake) from the previous round (see Danezis & al. Fig 2), which constitute the edges of the graph.

Each collection is formed in the following way: each validator reliably broadcasts a collection for each round. Subject to specified validity conditions, if validators with 2f + 1 stake receive a collection, they acknowledge it with a signature each. Signatures from 2f + 1 validators by stake form a certificate of availability that is then shared and potentially included in collections at round r + 1.

The following figure represents five rounds of construction of such a DAG (1 to 5), with authorities A, B, C and D participating. For simplicity, each validator holds 1 unit of stake. The collections transitively acknowledged by A's latest round in A5 are represented in full lines in the graph.

How it works​

  • The graph construction allows inserting more transactions in the system at each authority and at each round.
  • The certificates prove the data availability of each collection, or block, at each round.
  • Their contents constitute a DAG that can be traversed identically at each honest node.

Dependencies​

Narwhal is implemented using Tokio, RocksDB and generic cryptography implemented in fastcrypto.

Configuration​

To conduct a fresh deployment of Sui Consensus Engine, follow the instructions at Running Benchmarks.

Further reading​

Narwhal and Tusk (Danezis et al. 2021) is a consensus system leveraging directed acyclic graphs (DAG). DAG-based consensus has been developed over the last 30 years, and some of the history is summarized in (Wang & al. 2020). The theoretical ancestor of Narwhal and Tusk is DAG-Rider (Keidar & al. 2021).

Narwhal and Tusk are developed in the asynchronous model. A partially synchronous variant of Narwhal and Tusk is called Bullshark (Spiegelman et al. 2022).

Narwhal and Tusk started as a research prototype at Facebook Novi.

Bullshark: DAG BFT Protocols Made Practical - Bullshark replaces Tusk for even greater performance.

Bullshark: The Partially Synchronous Version - A simplified version of Bullshark that is used in Sui today.

DAG Meets BFT - The Next Generation of BFT Consensus - Explains the evolution of the consensus protocol used by Sui.

Bibliography​