# MEV meets DAG: Exploring MEV in DAG-based blockchains

[Rohan Shrothrium](https://twitter.com/0xtrojan_) , [Samuel Laferriere](https://twitter.com/samlafer)

## Introduction

Chains like Sui and Aptos use multi-proposer based consensus algorithms that leverage Narwhal, a relatively novel total order broadcast DAG-structured mempool mechanisms. At the cost of slightly extra latency, their unique way of allowing every validator to propose partial blocks simultaneously is a breakthrough addressing one of blockchain's most persistent challenges: achieving high throughput. However, the questions of transaction ordering and MEV extraction on these blockchains remains criminally understudied and to our knowledge still a largely unresolved issue. As the [Sui](https://defillama.com/chain/Sui) and [Aptos](https://defillama.com/chain/Aptos) TVL keep increasing these chains' sequencing algorithms will no-doubt come to the forefront of MEV-related interest, just like happened on [ethereum](https://github.com/ethereum/go-ethereum/issues/21350), [avalanche](https://x.com/samlafer/status/1559087867581779969?s=20), [solana](https://www.umbraresearch.xyz/writings/mev-on-solana), and others.

In this article, we aim to provide the readers with a basic introduction to the Narwhal Mempool, the existing landscape of MEV on chains that use Narwhal-DAG-based consensus algorithms, and analyze how the ordering of transactions within the DAG impacts MEV.

In this article we describe the parts of Narwhal/Bullshark that are relevant to MEV, but defer to the original [paper](https://arxiv.org/pdf/2201.05677.pdf) for further details and full explanation of the protocol.

## Lexicon

- narwhal round: synchronous time block (typically 2s) during which all validators create blocks, forward them to other validators, and gather a signature certificate from 2f+1 other validators
- anchor: vertex of the narwhal DAG which is selected to be the leader for that round. Its block will get committed if it has received f+1 signatures in the following round.
- committed meta-block: when an anchor's block receives f+1 signatures, its block, as well as its causal history of blocks (excluding those that were committed by previous anchors) are grouped, ordered, and committed as a "meta"-block. We often use this laxly to refer to the actual underlying transactions, forgetting about the DAG structure.
- block: The actual Narwhal structure consists of 1) transaction batch hashes 2) 2f+1 certificates from previous round 3) signature from validator who created the block
- certificate: 2f+1 signatures of a given block hash
- transaction batch: group of transactions propagated together between workers that is hashed and included as part of a block

A good reference to understand these terms is figure 2 in the original [Narwhal and Tusk](https://arxiv.org/pdf/2105.11827.pdf) paper.

## Narwhal Mempool
The idea of Narwhal is to separate dissemination of data (transactions) from metadata (hashes of batches of transactions) ordering, which allows every validator to be proposing simultaneously, and hence leads to higher throughput. The protocol provides a method to reliably disseminate data, gather certificates of availability, and build a DAG of transaction batch certificates. Narwhal's architecture is such that it can be scaled horizontally, by increasing the number of workers (see diagram below). Narwhal alone is not sufficient for the nodes in the network to achieve consensus on transaction ordering, because the blocks in the DAG, as well as the transactions they contain, must be totally ordered. There are multiple consensus protocols built on top of Narwhal which are constantly being improved (Sui is using [Sui-Lutris](https://sonnino.com/papers/sui-lutris.pdf), Aptos is soon to release [Shoal](https://arxiv.org/abs/2306.03058)). We will for the sake of simplicity focus on the original Bullshark, which is a zero-message overhead protocol for achieving consensus on transaction ordering. We will dive deeper into Bullshark in the next section.

As seen in the diagram below, each node has $k$ workers and a single primary. As all these components are part of a single validator node, it is safe to assume that they fall under the same trusted entity. The role of each of the components is the following:
1. **Workers**: The job of each worker is to pick up client transactions, batch them, and disseminate them across the network. Each worker $w_i$ of a validator node only interacts with $w_i$ of other validator nodes. Once the worker broadcasts a batch, the hash digest of the batch is sent to the primary. We can see how a larger number of transactions can be propagated by just increasing the number of workers for each validator.
2. **Primary**: The role of the primary is to create a block (vertex of the Narwhal DAG) in each round. To do this, the primary gathers the tx batch digests provided by the workers and at least $2f+1$ certificates from the previous round into a block, broadcasts this block to the other primaries, gathers at least $2f+1$ signatures into a certificate, and broadcasts the certificate back to other validators. This structure prevents equivocation at the level of the (structured) mempool!

While workers constantly disseminate batches of transactions, a primary proposes at most one vertex to the DAG per round. As depicted in the diagram below, a round in Narwhal includes a primary constructing a block, creating a certificate by gathering votes from at least $2f+1$ validator nodes, and then broadcasting this certificate to all the validator nodes.

## Bullshark
The vertices from Narwhal not only contain blocks of transactions but also have references to previously received messages (blocks and certificates), which together form a directed acyclic graph (DAG). The DAG encodes information that allows parties to totally order the DAG by locally interpreting their view of it without sending any extra messages. That is, once the DAG is built, Bullshark achieves consensus on the order with zero overhead of communication. This is achieved by using a deterministic total ordering function. One such function is to naively order all transactions by gas price(Sui).

Bullshark does so by doing the following:
1. Every alternate round has a predefined anchor (leader).
2. If an anchor in the $n^{th}$ round receives at least $f+1$ votes in the $(n+1)^{th}$ round in the local view of a validator, they commit the meta-block formed from the DAG's causal history starting from the anchor as the root.
3. If the anchor does not receive enough votes in the local view of a validator, they move to the next round until an anchor receives sufficient votes. Once the validator receives a committed anchor, it checks if there is any uncommitted anchor in its causal history and commits all such anchors with the oldest uncommitted anchor having the highest priority.

The [Bullshark paper](https://arxiv.org/pdf/2201.05677.pdf) proves the safety and liveness properties.

## MEV in DAG-based consensus

After an anchor is elected as leader, its causal history of blocks that haven't previously been committed are committed as one meta-block.


<!--- excalidraw source for image: https://excalidraw.com/#json=cGfJd8jK_yoP3-fpjomdq,Ax1TftmMN8owobKYxAcpBA --->

A deterministic function is used to totally order all the transactions within this meta-block, and each such function defines a very different "MEV game". Two major categories of such functions are those that unbundle blocks, and those that don't.

### Unbundle Blocks and (Re)order All Transactions
This involves fetching all the transactions in a meta-block and ordering them. There are a number of ways this can be done and we describe a few below:
#### Ordered by Gas Price (Current [Sui implementation](https://github.com/MystenLabs/sui/blob/main/crates/sui-core/src/post_consensus_tx_reorder.rs#L21))
In the current implementation on Sui mainnet, once an anchor is elected, the transactions in its meta-block are totally ordered based on gas price, with highest price getting top of the meta-block. The leader, in the round during which it is an anchor, thus has an exact picture of the transactions other than his own that will be committed as part of its meta-block. This allows the anchor to extract the following MEV:
- **Top of Block**: When an anchor proposes its vertex, it has the ability to select and/or insert transactions that offer a sufficiently high gas price, ensuring these transactions are consistently positioned at the beginning of the block. This setup enables the anchor to potentially auction off this position to external searchers or to insert its own transactions. The most profitable MEV opportunities, such as CEX-DEX arbs are invariably found at the top of the block, allowing the anchor to secure these opportunities.
- **Bottom of Block**: Just as transactions with high gas prices are placed at the beginning of the block, anchors also have the discretion to select and/or insert transactions with lower gas prices for inclusion, ensuring these are systematically positioned at the end of the block. This mechanism allows for the anchor to strategically include their transactions to capture MEV such as DEX-DEX arbs and backrunning AMM pools, which typically find their place at the block's bottom. There are even opportunities for cheap CEX-DEX arbs if they exist.
- **Sandwiching or frontrunning** specific transactions becomes **significantly challenging** when the transactions are closely priced, meaning numerous transactions share the same gas price. This tight pricing scenario makes it difficult to target individual transactions for manipulation.

Non-anchor nodes don't have any scope to extract MEV as they are unaware of the state of other blocks in that round. Anchor nodes can always front-run the other nodes because of having additional information.

As transactions are ordered by gas price, the anchor does not have any incentive to include transactions that are already included in its causal history. This does not have any direct implications on the throughput of the system.

#### Ordered by Other Considerations

Many other orderings have been discussed in the context of other blockchain's default client behavior. These other considerations are also very important in the context of the previous section, because one needs to decide [how to break gas price ties](https://github.com/ethereum/go-ethereum/issues/21350). In order to keep this note brief, and also because many of these other orderings have been discredited elsewhere, we will simply state them without discussing their full subtleties, which would require another article:
- random ordering
- based on "proof-of-work" style mining (see the fiasco that ensued from arbitrum's [proposal](https://research.arbitrum.io/t/thoughts-on-arbitrums-proposal-to-score-connections-by-pow/8121) which eventually lead to them proposing [timeboost](https://medium.com/offchainlabs/time-boost-a-new-transaction-ordering-policy-for-arbitrum-5b3066382d62))
- Sui is also considering including [object hotness](https://github.com/MystenLabs/sui/blob/266311d7b3815e49bf21c6436412a1a5aa53ce1a/crates/sui-core/src/post_consensus_tx_reorder.rs#L18) as a criteria for ordering.

### Only (Re)order Blocks, Not Their Internal Order

Ordering blocks instead of transactions creates a very different MEV landscape, with PBS-like tendencies. These strategies make the most sense when coupled with a topological sort of the DAG blocks, that is, sorting the blocks according to the round they were included in (ascending/descending). As the anchor has the highest round number, it has a deterministic position in the block (top of block/ bottom of block). Let us analyze MEV and throughput implications for both scenarios.

#### Anchor gets Top of Block

- This allows a full block auction and enables PBS as the transactions included in the anchor always have the highest priority.
- The role of non-anchor blocks is reduced to being an inclusion lists.
- The anchor can include all the transactions included in its causal history to extract the maximum MEV. This would lead to a decrease in throughput as there would be a lot of redundant transactions.

#### Anchor gets Bottom of Block (Current [Aptos implementation](https://github.com/aptos-labs/aptos-core/blob/main/consensus/src/dag/order_rule.rs#L198-L202))

- The anchor can deterministically include transactions at the bottom of the block. This mechanism allows for the anchor to include their transactions to capture MEV such as DEX-DEX arbs and backrunning AMM pools.
- The anchor can also capture any CEX-DEX that exists at the end of the block.
- As the anchor gets the bottom of the block, it does not have any incentive to include transactions that are already included in its causal history. This does not have any direct implications on the throughput of the system.


### Mitigate PBS

One method to reduce the impact and power of PBS like structures, is to force proposers/builders to build without perfect state knowledge. Using encrypted mempools is the classic way proposed to do this, but Narwhal based DAG consensus protocols create new ways to achieve similar results. The two main ways to do this are to force the anchor to be elected retroactively, or to include the anchor's block in the next meta-block.

Most of the analysis in this article assumes that the anchors are known ahead of time. This is the current behavior in both Aptos and Sui, where the leader schedule is decided at the beginning of each epoch. The original tusk protocol worked differently, where the anchors were decided retroactively in round n+1 by using randomness. By using such a strategy, any of the proposers could be the leader, but they can't build as aggressively without having the guarantee.

Another way to achive a similar result is by excluding the anchor's transactions from the current meta-block and including it in the next meta-block. This ensures that none of the blocks proposed by the validator nodes have a deterministic position or have the view of the meta-block before proposing their block in the round. This method also emphasizes fairness and prevents the leader from exploiting their position.

## Conclusion
We believe sequencing and MEV in multi-proposer consensus algorithms is largely unexplored and can determine the endgames of chains like Sui and Aptos. Although DAG based consensus algorithms solve the larger problem of throughput, we belive designing better deterministic total ordering function would decide how MEV can be extracted on these chains, which might be the only way to prevent the natural [tendency towards PBS](https://x.com/txsequencer/status/1754266310283071974?s=20).