Introduction

Aptos and Sui team members previously worked at Meta (Facebook), which was trying to build a blockchain called Diem. So, you could think Aptos and Sui share some similar ideas about how to build their blockchains. Though Sui chose to use DAG as its consensus foundation, called Bullshark, while integrating with Fastpay to give birth to Sui Lutris, which allows it the ability of parallel execution. On the one hand, Aptos chose to stick with the blockchain structure and gave birth to AptosBFT, the Hotstuff variant. Aptos also integrates Block-STM into its chain to allow validators to execute transactions in parallel. Although they seem different in their approaches, the mempool, named Narwhal, that is used in both protocols, is the same. Of course, in this article, I will write about the Narwhal DAG-based mempool protocol. So without more introduction, let's dig in.

The Problems that Narwhal is Trying to Solve

As we know, traditional blockchains suffer from scalability issues. Many blockchains have addressed this problem by modifying their consensus protocols, enabling validators to rapidly agree on blocks. Although this approach seems elegant, some overlook that the mempool is also a bottleneck in their consensus. Why? Because, typically, when users submit their transactions to validators, each validator gossips their received transactions to other validators' mempools. In each round, a leader is selected, and then it proposes a new block, created using transactions from its mempool. So, what's the issue here? The problem is that one transaction gets broadcast twice! This is not efficient at all!

Therefore, the idea behind Narwhal is to separate transaction dissemination from consensus. This allows validators to gossip transactions at the mempool level and only use a small fixed-size reference (like a hash) to refer to a transaction while creating a block. Moreover, Narwhal is designed to support horizontal scaling, where one can add more workers (threads, CPUs) to achieve greater data dissemination throughput.

How does it work?

To achieve horizontal scaling, each validator is composed of workers and one primary. Workers are the key to horizontal scalability and have two main responsibilities:

1. Stream batches of transactions to corresponding validators’ workers, as illustrated in Figure 1.

2. Send digests (hashes) of received batches to its primary. The primary then uses these digests to form its local round-based DAG.

To form a round-based DAG structure, a validator aggregates transactions received from users into a batch before broadcasting this batch to other validators, as mentioned above. When a validator receives a batch, it stores the batch as a vertex in its local DAG view. Here, validators can apply a soft consensus logic, ensuring that a validator can only move to the next round (proposing a new batch of transactions) if a supermajority of nodes (2/3 of all nodes) have received its batch. This process contributes to the DAG structure, as depicted in Figure 2. Each validator follows these steps at round $r$:

1. The primary sends a message to all other validators containing metadata, including:

   1. A batch digest.

   2. $2f+1$ references (certificates) to other batches (vertices) from the previous round $r-1$.

2. Upon receiving a message, the primary stores the batch corresponding to the message and sends an acknowledgment back to the sender with its signature only if:

   1. Its workers have already received and stored the data corresponding to the digest received by the primary.

   2. It has not previously replied to this validator in this round.

3. A validator aggregates $2f+1$ signatures received from different validators to form a certificate. It then sends this certificate to other validators, enabling them to add this batch as a vertex in their local view of this round.

4. A validator can advance to the next round, $r+1$, only if it receives $2f+1$ vertices with valid certificates.

Certificates help ensure that at least $f+1$ honest nodes have the data in their local view, thus ensuring data availability. Naturally, with $2f+1$ validators agreeing on the history of transactions, a (partially synchronous or asynchronous) consensus logic can be built efficiently atop this DAG structure. For instance, consensus logics like Tusk, Bullshark (used in Sui), and DAG Rider add zero communication overhead when used with Narwhal. In these scenarios, each validator can examine their local DAG, interpret it, and fully order and reach a consensus on the vertices (transactions) without sending a single extra message.

References