Overview

There are two types of transactions on Sui: simple transactions involving address-owned and transactions immutable objects that can be processed quickly (fast path) and special transactions involving shared objects that need to go through Consensus.

Sui’s object model also allows for more scalability by allowing batching and ordering transactions around the objects associated with such transactions. Instead of a single-lane system, which is the case with most blockchains, Sui can process many groups of transactions at once, making Sui one of the fastest and most scalable blockchains. To read more about scalability and transaction execution, go here.

The names highlight that the components split the responsibilities of:

Narwhal - ensuring the availability of data submitted to Consensus;
Bullshark - agreeing on a specific ordering of this data.

DAG Data Structure

Narwhal and Bullshark arranges transactions in a DAG (Directed Acyclic Graph) data structure, in which transactions are sequenced in consecutive rows at each round and form an acyclic graph, instead of put in line, one by one. At each round, transactions in the row are selected to be executed. Then, as all rounds pass, these transactions are executed in a batch.

The figure below shows how transactions are ordered and sequenced following the DAG structure.

Narwhal Mempool

The Narwhal Mempool merges dependable broadcasting and storage. Each validator keeps track of the current local round 𝑟, which starts at zero. Validators continuously accept transactions from clients and compile them into a transaction queue.

They also receive certificates of availability for blocks at 𝑟 and gather them into a certificate list. Once certificates for round 𝑟 − 1 are collected from 2𝑓 + 1 unique validators, a validator advances the local round to 𝑟, forms, and disseminates a block for the new round. Each block encompasses its creator’s identity, local round 𝑟, the present list of transactions and certificates from 𝑟 −1, and a signature from its creator. Accurate validators only generate a single block per round.

Validators dependably broadcast each block they form to ensure its integrity and availability. In essence, the block creator transmits the block to all validators, who verify its validity and then respond with their signatures. A valid block must:

a) include a valid signature from its creator;
b) be at the local round 𝑟 of the validator verifying it;
c) be at round 0 (genesis) or include certificates for at least 2𝑓 + 1 blocks of round 𝑟 − 1;
d) be the first one received from the creator for round 𝑟.

If a block is valid, the other validators store and acknowledge it by signing its block digest, round number, and creator’s identity. However, blocks with a future round contain 2𝑓 + 1 certificates that ensure a validator progresses its round into the future and signs the newer block. Once the creator receives 2𝑓 + 1 distinct acknowledgments for a block, it combines them into a certificate of block availability that includes the block digest, current round, and creator identity. Then, the creator transmits the certificate to all other validators so that they can incorporate it in their next block.

The system is initialized through all validators forming and certifying empty blocks for round 𝑟 = 0. These blocks do not encompass any transactions and are valid without reference to certificates for past blocks.

The figure below illustrates the Narwhal Mempool operation.

TLDR, 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

Bullshark Consensus Mechanism

Sui Lutris validators operate the Narwhal Mempool. Each validator locally interprets its local view of the DAG
and use the shared randomness to determine the total order.

Validators partition the DAG into waves, each comprising 3 sequential rounds for interpretation.

1. In the initial round of a wave, every validator puts forth its block.
2. In the subsequent round, each validator casts votes on the proposals by incorporating them into their block.
3. In the final round, validators generate randomness by retrospectively electing one random leader’s block.

Upon the revelation of the random coin for the wave, each validator 𝑣 commits the elected leader block 𝑏 of a wave 𝑤 if there exist 𝑓 + 1 blocks in the second round of wave 𝑤 (in validator 𝑣’s local perspective of the DAG) that reference block 𝑏. In this case, validator 𝑣 meticulously arranges block 𝑏’s causal history up to the garbage collection point. However, as validators might acquire different local views of the DAG, some might commit a leader block in a wave while others might not.

To ensure that all honest validators eventually sequence the same block leaders, after committing the leader in wave 𝑤, validator 𝑣 designates it the next candidate to be sequenced and recursively reverts to the last wave 𝑤′ in which it committed a leader.

For each wave 𝑖 in between waves 𝑤′ and 𝑤, validator 𝑣 verifies whether there exists a path between the candidate leader and the leader block 𝑏 of wave 𝑖. In the event that such a path exists, validator 𝑣 sequences block 𝑏 before the current candidate sets the correct candidate to block 𝑏 and continues the recursion.

The figure below demonstrates how transactions are selected to be added to a certificate at each round. Every odd round possesses a coin value that selects a leader of round 𝑟 − 2. If the leader has less than 𝑓 + 1 support (red), they are disregarded; otherwise (blue), the algorithm explores the causal DAG to commit all preceding leaders (including red) and sequences the remainder of the DAG afterward.

Then, the transactions are added to certificates to be added to a checkpoint.