Skip to main content

Consensus on IOTA

Narwall and Bullshark​

IOTA uses Narwhal, and Bullshark, the high-throughput mempool and consensus engines developed by Mysten Labs, to sequence transactions that require total ordering, synchronize transactions between validators, and periodically checkpoint the network's state.

Narwhal ensures that data that was submitted for consensus is readily available, while Bullshark is in charge of generating a consensus on the specific ordering of said data.

The IOTA consensus engine is a cutting-edge advancement in multi-proposer, high-throughput consensus algorithms. It can achieve over 125,000 transactions per second with a two-second latency for a deployment of 50 participants. This includes production-level cryptography, permanent storage, and a scaled-out primary-worker architecture.

The IOTA consensus engine offers significant scalability advantages in the following scenarios:

  • A blockchain that has experimented with larger blocks and encountered increased latency before the execution phase.
  • A blockchain with fast execution (e.g., focused on transactions or using a UTXO data model) where the mempool and consensus processes cannot keep up.

Key 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 information.
  • A scaled architecture that splits disk I/O and networking requirements across several workers

Architecture​

A Narwhal instance sets up a message-passing system with a set of 3f+13f+1 units of stake divided among nodes. It assumes a computationally bounded adversary that controls the network and can corrupt parties holding up to ff units of stake. The validators collaborate to form a leaderless graph of transaction batches, referred to as collections in IOTA (often called blocks in DAG-based consensus literature). This process uses mempool data with an unspecified consensus algorithm.

The graph's vertices are certified collections. Each valid collection, signed by its validator-author, must include a round number and a certificate of availability signed by a quorum (2f+1) of validator stake. Each collection must also contain hash pointers to a quorum of valid certificates (from validators with 2f + 1 units of stake) from the previous round, forming the edges of the graph.

Collections are formed as follows: 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. Signatures from 2f + 1 validators by stake form a certificate of availability, which is then shared and potentially included in collections at round r + 1.

The following figure represents five rounds of constructing such a DAG (1 to 5), with validators 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 with solid lines in the graph.

How It Works​

  • The graph construction enables the insertion of more transactions into the system by each authority and in each round.
  • Certificates prove the data availability of each collection or block in every round.
  • The contents form a DAG that can be identically traversed by each honest node.

Dependencies​

Narwhal is implemented using:

Generic cryptography is implemented in fastcrypto.

Configuration​

You can follow the instructions on Running Benchmarks to conduct a fresh deployment of IOTA Consensus Engine.

Further Reading​

Narwhal and Tusk (Danezis et al., 2021) is a consensus system that leverages directed acyclic graphs (DAGs). DAG-based consensus has been developed over the last 30 years, with some history summarized in Wang et al. (2020). The theoretical ancestor of Narwhal and Tusk is DAG-Rider (Keidar et 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 IOTA today.

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

Bibliography​