Skip to main content

Notions of Fairness in Mysticeti

· 38 min read
The world if all blockchains were DAG-based
Kevin Aftermath

CTO & Co-Founder, Aftermath Finance

Introduction​

Blockchains have ushered in a new era where decentralization and fairness take center stage. Early DeFi primitives embraced these ideals, but as blockchains matured and were better understood, a supply chain focused on value extraction emerged. Simultaneously, builders recognized the challenges of constructing entirely on-chain solutions in an increasingly unfair environment. Consequently, much of modern "DeFi" has evolved into a mix of centralized off-chain infrastructure with on-chain custody. These off-chain solutions seemingly contradict the ethos behind blockchain, by reintroducing centralization, allowing for increased value extraction, and reducing the ability for competition.

Recent discussions have resurfaced Multiple Concurrent Proposers (MCP) as a viable solution to several key issues plaguing the adoption of truly on-chain applications, including the increasing demand for heightened censorship resistance [1], and the rise of harmful Maximal Extractable Value (MEV) tactics. These challenges are all interrelated and touch on different dimensions of fairness within the blockchain stack.

Directed Acyclic Graph (DAG)-based Byzantine Fault Tolerant (BFT) protocols naturally rely on multiple proposers to construct the underlying DAG. DAGs progress in a series of rounds, wherein each proposer¹ submits a unique block. Each block must link to a quorum of blocks from the previous round to maintain validity. It's this back linking of blocks across rounds that forms the DAG. As a result, DAG-based blockchains inherently deliver many of the benefits being discussed in relation to MCP.

Overview​

Understanding how a blockchain promotes fairness is crucial for identifying the potential limitations you'll face when building on-chain, particularly fully on-chain applications. Raikwar et al. [2] explores various definitions of fairness within Distributed Ledger Technology (DLT) and examines how DAG-based DLTs can address fairness concerns in modern blockchains. However, since Raikwar's study predates the first release of Mysticeti [3], it lacks an in-depth analysis of fairness within the context of Mysticeti. This articles aims to bridge that gap by applying the fairness concepts from [2] to the Mysticeti family of protocols.

Since its initial debut, Mysticeti has been integrated into one production-ready environment: the Sui blockchain. To further elevate this study, I will also expand the scope of my analysis to cover aspects of the Sui protocol that enhance fairness. Because of this, I will distinguish between elements relevant to base Mysticeti as described by Babel et al., those specific to the current implementation of Mysticeti within Sui, and those inherent to the Sui protocol itself.

The purpose of this article is threefold:

  1. Highlight the unique properties of fairness that both Mysticeti and Sui inherently provide,

  2. Urge the community to preserve these levels of fairness in the protocols they create,

  3. Enrich discussions around Sui, as it spreads awareness on the aspects of the Sui protocol that remain largely underexposed (deterministic ordering, opportunities for MEV, transaction lifecycle, etc).

The article is organized as follows: In § Mysticeti, I provide a high-level overview of the Mysticeti family of protocols. In § Fairness, I break down the different definitions of fairness described in Raikwar et al. and detail how each applies to both Mysticeti and Sui. Finally, I discuss broader implications in § Discussion and offer closing thoughts in § Conclusion.

Mysticeti​

Mysticeti is a family of DAG-based Byzantine Agreement (BA) protocols recently proposed in [3] and, as of July 25th of this year, integrated into the Sui blockchain. The Mysticeti family consists of two closely related protocols: Mysticeti-C and Mysticeti-FPC. 

Mysticeti-C. Mysticeti-C is the first DAG-based BFT consensus protocol to match the commit latency—3 message rounds—of classical BFT protocols (e.g., HotStuff [4]). It achieves this while maintaining the inherent advantages of DAGs, such as high throughput, symmetric resource utilization, and robust resistance to censorship.

Mysticeti-FPC. Mysticeti-FPC builds upon Mysticeti-C by introducing a fast path specifically for transactions that do not require consensus, colloquially known as single-writer transactions on Sui. These transactions exclusively interact with state that can only be accessed on-chain by a single entity, hence the name single-writer, enabling them to bypass the sequential nature inherent to state contention.

Mysticeti is composed of two subsystems: one dedicated to constructing the DAG and another focused on interpreting the DAG to establish a deterministic ordering of transactions.

Data Dissemination​

Mysticeti breaks away from the traditional chain-based blockchain model by eliminating the reliance on a single entity for data dissemination. Instead, all validators contribute simultaneously to propose blocks and build the DAG at network speed. This design ensures that the overall system throughput around DAG construction is not compromised by a single slow validator.

In Mysticeti, the DAG is constructed through a series of rounds, where each honest validator proposes a single uncertified block. Throughout a round, validators receive both client transactions and blocks proposed by other validators in the prior round. Once a validator has collected blocks from a quorum of 2f + 1 validators and waited for a leader timeout, the validator will assemble references to these previous blocks and the received client transactions into a new block and broadcast it to all other validators.

The underlying DAG structure

Figure 1: At any given round, each validator will have their own local view of the DAG.

Unlike its predecessor Narwhal [5] & Bullshark [6], Mysticeti leverages an uncertified DAG. This distinction is key as it enables Mysticeti to (1) achieve a consensus latency with a lower bound of three message rounds and (2) significantly reduce the CPU consumption spent on both signature generation and verification that would be required during the certification step of the certified DAG.

Certified DAG. Blocks in certified DAGs contain 2f + 1 references to quorum certificates instead of blocks directly. Quorum certificates ensure validity and availability on all proposed blocks and are obtained through a back and forth process between validators: validators first disseminate their constructed blocks, collect signatures from their peers, and then aggregate these signatures into a quorum certificate. The certificate is then rebroadcasted to all other validators for inclusion in their blocks. This entire process spans three message rounds—equivalent to 1½ round trip time (RTT)—and increases the minimum commit latency as such.

Uncertified DAG. Mysticeti eliminates the certification step, reducing the block construction process to a single message round—½ RTT. This simplification, however, introduces added complexity in the DAG interpretation rules, which must now safeguard against equivocation by malicious validators [7]. The absence of a certification process, which ensures that validators propose only one block per round, means Mysticeti must rely on its block validation and commit rules to preserve safety.

DAG Interpretation​

Mysticeti achieves consensus through each validator independently interpreting their local view of the DAG. This avoids any additional communication overhead among validators, a common bottleneck on throughput, and allows validators to achieve consensus as quickly as they are able to individually apply Mysticeti's commit rule.

The locality of consensus requires that transaction ordering be deterministic; any deviation in this ordering by a single validator could cause a network fork. As such, a leader schedule deterministically decides a sequence of leaders, and a commit rule is applied to each leader to determine whether the leader's block and its causal history can be directly committed to the DAG. Ultimately, all validators will eventually agree on the same committed leader blocks, which are then linearized and their transactions sequenced for execution.²

The underlying DAG structure

Figure 2: Each validator locally interprets their view of the DAG to derive a deterministic commit sequence.

Commit Rule. The commit rule functions by identifying patterns within the DAG to determine whether blocks can be directly committed. If a block B from round r is referenced by a quorum of blocks in round r + 1, and a block C at round r + 2 references this quorum of blocks, block C becomes a certificate for block B. If 2f + 1 certificates are observed for block B must be directly committed. Conversely, if it is observed that a quorum of blocks in r + 1 do not reference B, then B will be skipped directly and instead committed—with high probability—in a future block's causal history.

If neither case occurs, Mysticeti employs an indirect commit rule to determine the edge cases. The indirect commit rule ensures that any discrepancies between each validator's local view of the DAG are resolved into a consistent and deterministic commit sequence.

Universal Commit Rule. Mysticeti enhances the basic commit rule by introducing the universal committer abstraction, extending the rule to be customized with various strategies. The Universal Commit Rule supports the commitment of up to n blocks in each round, where n is the total number of validators. Additionally, the commit rule is pipelined, ensuring a leader block can be committed in every round. These are significant advancements over Bullshark's commit rule, which allowed only one leader to be committed every three rounds.

Fairness​

The idea of fairness within blockchains can take on different meanings depending on whose perspective is being considered. Users want their transactions to be included in a timely manner without experiencing value leakage or negative extraction. Validators, on the other hand, desire fair participation, ensuring they have equal opportunities to propose blocks to the chain and earn the native token. To preserve fairness for all participants, consensus protocols and the related layers of the blockchain stack need to be carefully constructed.

Raikwar et al. identify and categorize various notions of fairness, each aimed at different participants or layers within the blockchain stack. They also discusses how DAG-based DLTs are well-suited to address prevalent concerns around fairness, particularly those related to harmful MEV extraction and centralization. I will briefly mention each fairness definition here, leaving the detailed exploration to [2].

It's important to highlight that Mysticeti-C is a standalone BFT consensus protocol that has been adopted by Sui. My primary focus will be on the Mysticeti-C implementation within the Sui protocol, where its fairness properties are closely intertwined with the inner workings of Sui, including its tokenomics model [8], current validator set [9], congestion control mechanism [10], and DAG linearization model. If a fairness benefit emerges from the way Mysticeti has been adapted by Sui, I will clearly distinguish how it differs from the original definition by Bushal et al. and its specific implementation within Sui.

Similarly, the fairness concepts I will outline should be seen as a spectrum rather than a rigid checklist. Comparable levels of overall fairness can be attained by implementing mechanisms that address different subsets of these concepts—it's not always essential for a single protocol to address every definition in its entirety.

Fairness to the Participants​

The transaction lifecycle is anchored by the network's main participants at either end—clients and validators—each expecting different notions of fairness. Clients, who initiate the transaction lifecycle, expect their transactions to be executed in a timely manner. Validators, positioned at the end of the lifecycle, aggregate client transactions and propose them as blocks on the ledger. In multi-proposer environments, validators desire equal access to have their proposed blocks appended to the chain.

For Validators​

Fairness for validators can be evaluated by their ability to have their blocks committed, regardless of differences in networking latency or their competitiveness in hardware specs. In other words, slower yet honest validators should not lose the ability to have their blocks added to the DAG simply due to their slower participation. Fairness for validators is vital for maintaining greater censorship resistance—a necessary attribute for moving logic on-chain [1]—fostering a more geospatially distributed network, and leads to higher levels of Chain Quality [5].

Mysticeti promotes validator fairness in several ways:

  1. Recall that Mysticeti operates in a series of rounds; in each round r, all validators aggregate client transactions into blocks. For a block to be valid, it must reference at least n - f blocks from the previous round r - 1. This quorum of back references forces a validator to wait until it has received at least 2f + 1 blocks from other validators, allowing slower validators the chance to be referenced by the sub-DAGs local to other validators.

  2. In addition to referencing n - f blocks from the previous round, Mysticeti blocks can also contain references to blocks from all prior rounds. These references, known as weak links [6], further enhance fairness for slower validators. With weak links, even if there is a momentary delay in disseminating a block during a given round, validators still have the opportunity to have their blocks included in the DAG in future rounds.

    A DAG containing a weak link

    Figure 3: Weak link allowing an older block to be appended to the DAG.

  3. Mysticeti, like prior work (e.g., Bullshark [6]), is a leader-based BFT protocol. Every m rounds, a leader is selected deterministically, and its sub-DAG is voted on for commitment. Mysticeti expands on this by employing a multi-leader and pipelined commit rule—the Universal Commit Rule—which aims to directly commit a constant number of proposed blocks from each round.

    In each round, s blocks are chosen and intrinsically voted on to be committed, including any uncommitted portions of their causal history. The larger the value of s, the greater the degree of fairness, as more blocks have the ability to be directly committed within the three-message lower bound. However, this also increases the likelihood of Byzantine validators causing delays in the commit sequence, necessitating a balance between fairness and commit latency when picking the value of s.

  4. Lastly, an important yet underappreciated aspect of Mysticeti is its inherent capacity to foster greater geospatial distribution among validators. This distribution is crucial for any blockchain, as it not only strengthens the network's resilience but also alleviates the legal and regulatory challenges of operating a validator node, while most importantly, promoting equitable access for both its users and validators [11].

    Current geospatial distribution of the Sui Network

    Figure 4: Current geospatial distribution of Sui's 108 validators, spanning 20 countries. Snapshot taken at epoch 515.

    Mysticeti supports this diversity through several means:

    1. Mysticeti operates under the assumption of a partially synchronous network, tolerating variances in network conditions that are more evident in geospatially distributed networks. This assumption enables Mysticeti to maintain fairness for validators once Global Stabilization Time (GST) is reached.

    2. Furthermore, Mysticeti's commit rule is designed to efficiently tolerate crash faults, ensuring that geographically isolated validators do not hinder the network's performance.

    3. As mentioned, the use of weak links allows slower validators to have their blocks included in future rounds of the DAG, even if they are slightly delayed in disseminating them—often a consequence of being geographically distant.

    The primary drawback for distant validators is that they will likely have a decreased chance to be selected as leader, as a result of Mysticeti's performance-aware leader scheduling protocol known as HammerHead [3]. However, this is not economically significant on Sui, as PoS rewards are not directly linked to consensus participation. Instead, validator rewards are tied to the output of the Tallying rule [8], a mechanism in which validators subjectively score the performance of all other validators. While doing so, a validator should incorporate geospatial location—such as the Geospatial Diversity Index of a Validator [11]—into their individual scoring mechanism.

Mysticeti strikes a balance between fairness for validators and commit latency, while also enhancing censorship resistance and network distribution. The DAG's need for a quorum of back links inherently supports inclusion, while Mysticeti's commit rule, coupled with weak links, ensures that all validators have equitable chances to contribute to the DAG. These features also support the development of a more geospatially disperse validator set, further improving fairness for validators.

For Potential Validators​

An aspect not addressed by Raikwar et al. that affects fairness for validators, particularly potential validators, is the ease of entry for new validators. The more costly or hardware-intensive it is to become a validator, the higher the barrier to entry, which naturally results in increased centralization within the active validator set.

The validator committee on Sui has grown modestly from 95 validators at Genesis to 106 currently [9]. This slow growth can be seen as a byproduct of the large amount of stake (30M SUI) that is required to become an active validator. In the past, Mysten Labs has indicated that expanding the committee size is on their short-to-midterm roadmap.

In fact, while preparing this article, a new Sui Improvement Proposal (SIP) [12] was introduced to tackle this exact issue. This SIP proposes changing the criteria for new validators from being based on the total stake to be gated by relative voting power, which is a function of a validator's stake relative to the total network stake. This adjustment would reduce the largest barrier to entry for new validators, thereby improving the overall fairness around participation.

Similarly, a major advancement from Narwhal and Bullshark to Mysticeti is the transition from a certified DAG to an uncertified DAG. In Certified DAGs, blocks must be signed by a quorum of validators before they can be appended to the DAG. This certification process consumes considerable CPU resources as the CPU is often spent generating or verifying signatures. Mysticeti simplifies this process by adopting an uncertified DAG model, where validators propose blocks while bypassing the certification process. This approach significantly reduces CPU overhead, freeing up resources for more critical tasks like transaction execution, though it also leads to underutilized hardware—given Sui's minimum hardware requirements—as the demand for CPU-intensive operations has decreased considerably. Although the current hardware requirements remain unchanged, Mysticeti is paving the way for greater fairness for new validators by facilitating a future with reduced hardware demands.

Reducing the barrier to entry has been a significant request from the Sui community since its launch. Mysticeti, along with the newly proposed SIP, is just the start of enhancing fairness for potential validators and expanding the Sui committee.

For Clients​

Client fairness refers to the fair access a client's transaction has to the rest of the network [2]. Under this model, a fair network is one in which client orders are guaranteed to eventually be added to the network without significant delay. The stricter the fairness provided to clients, the more resistant the network becomes to censorship.

As detailed by Fox et al., censorship resistance is a fundamental requirement for any truly on-chain dApp; without it, validators have the potential to manipulate on-chain processes by censoring or delaying transactions, either entirely or partially.

On paper, Mysticeti appears to provide a slightly weaker³ level of client fairness compared to Sui Lutris [13] running Narwhal and Bullshark. This appearance arises due to Mysticeti's significant impact on the transaction lifecycle: a client only needs to send a transaction to a single validator for execution. In contrast with Sui's consensus v1, transactions are first sent to a quorum of validators before their signatures are aggregated into a certificate and sent back to all validators for inclusion and execution.

The transaction lifecycle of Sui Lutris

Figure 5: Transaction lifecycle within Sui Lutris [13].

This process of sending the transaction to all validators enhances client fairness, as it increases the likelihood that the transaction will be fairly appended to the DAG. With more validators aware of the transaction, the chances of its inclusion in a block are higher.

With Mysticeti, clients don't always achieve this same level of fairness as they only need to send transactions to a single validator. This method presents both a key benefit and a potential drawback in terms of client fairness:

  1. With Mysticeti's shift in requiring transactions to be sent to a minimum of one validator, clients can target their geographically nearest validator, thereby reducing latency and improving their transaction execution speed. This approach contrasts sharply with both leader-based, chain-based DLTs, where transactions must be propagated to the designated leader, and with Sui Lutris, where transactions need to be broadcast to a quorum of validators before being executed. Users who are geospatially distant from the network's closest quorum or lack stable access to the network will benefit from this approach.

  1. If a transaction is not committed within a certain timeframe, the client must resend it. This is contrasted by Sui Lutris, where transaction finality⁴ is obtained after sending the certificate to a quorum of validators.

    I mention this as a bad thing, however, in practice, Mysticeti can achieve fairness levels identical to Sui Lutris, as clients have the option to send their transactions to multiple validators. This can quickly lead to increased network spam and duplicated transactions, though, which are issues that may not notably affect the client. An optimal balance between client fairness and network utilization would involve sending transactions to 1 ≤ n < 2f + 1 validators.

What has been mentioned thus far is regarding the formal definition of Mysticeti as described by Babel et al. The current implementation of Mysticeti on Sui replaces the blackbox consensus engine of Sui Lutris with Mysticeti-C and therefore transactions follow the flow of being sent to a quorum of validators.⁵ This current implementation benefits from the increased client fairness as described for Sui Lutris.

There are several noteworthy aspects of Sui—not all specific to Mysticeti—that work together to provide users with a higher level of fairness:

  1. Sui's asynchronous execution model, combined with its object-centric data model, allows for parallel execution of transactions that involve disjoint sets of objects. Following consensus, transactions are placed into execution queues based on the objects they interact with, and execution is handled asynchronously. This design ensures that network congestion only affects "hot" objects, so other applications remain unaffected [10]. When interacting with an uncontested state, users' network access remains unaffected and ensures client fairness is not harmed.

  2. Private order flow via order flow auctions (OFAs) has emerged as a solution to the problems associated with public mempools. By bypassing the public mempool, private order flow simulates a private mempool, sending user orders directly to an auction where the right to access transaction details is sold, typically to a searcher or builder. Most OFAs aim to enhance user fairness, e.g., by redistributing MEV extraction back to their users or enabling a form of account abstraction.

    However, OFAs that are designed to mitigate or redistribute MEV can be a double-edged sword in terms of user fairness. While they generally offer a public good for their users, one could argue that they disproportionately benefit those who are well informed, particularly those who are aware of their existence. New users entering the ecosystem may not be aware of OFAs or understand why they are required, leaving them at a disadvantage with greater exposure to MEV extraction. Mysticeti's lack of a public mempool alleviates the necessity for OFAs designed around MEV mitigation or redistribution, creating a more equitable environment for both new and inexperienced users.

  3. Sui's block size is configurable and limited by both the maximum number of transactions and the total byte size of all transactions within the block. This limit contrasts sharply with other chains where block sizes are typically limited by the total gas consumed or a factor of the maximum permissable computation.

    A profit-maximizing validator will still prioritize transactions with higher gas fees, although their bound is now subject to the physical block size limits—bytes and transaction count. Importantly, transaction byte size does not always correlate with gas payments nor computational load; thus, transactions with lower gas price or higher computation are less likely to be penalized with higher inclusion times compared to chains whose block size is directly limited by these factors.

  4. One could argue that the fast path in Mysticeti-FPC enhances fairness for owned-object transactions. This mechanism acts as a shortcut for "simple" transactions—like transfers and certain types of payments—to bypass consensus, resulting in significantly shorter times for inclusion in the DAG. While fast path transactions are largely immune to MEV-related concerns, issues like delays and exclusion still apply to transaction fairness. The fast path mitigates these issues by sidestepping the delays associated with consensus and allowing the client to establish their transaction order.

The flexibility to send transactions to any subset of validators in Mysticeti promotes a more versatile form of client fairness. Users prioritizing swift inclusion may send to a supermajority, while those with less reliable connections may choose to only send their transactions to the validators closest to them. Additionally, Sui's architecture includes various features designed to enhance fairness in execution times and ensure users do not face delays.

Fairness in Consensus Ordering (Order-Fairness)​

Order-fairness is concerned with ensuring the integrity on how incoming transactions are ordered relative to one another. True fairness is achieved only when validators avoid reordering, prioritization, exclusion, or deliberately delaying transactions. By upholding order-fairness, the network can prevent harmful MEV extraction that occurs through ex post order manipulation, such as transaction censorship or sandwiching.

Before diving into the various notions of order-fairness, it's important to highlight a few properties of both Mysticeti and the Sui protocol that reduce the requirement for the strict application of or conformity to these notions:

  1. Mysticeti's lack of a public mempool eliminates the opportunity for searchers to prey on incoming transactions. Transactions are instead propagated to individual validators via private order flow channels, where each validator only receives a subset of the network's total transactions. This direct transaction flow minimizes the number of entities involved from submission to execution, significantly limiting the opportunities for harmful MEV extraction to the few in-path entities: client (typically a wallet), fullnode, validator. However, the risk of extraction is not eliminated, as these three actors could potentially act maliciously and attempt to extract MEV from transactions they observe before they are fully propagated and reach consensus.

  2. Unlike traditional monolithic chain-based DLTs, Mysticeti separates the data dissemination layer (DAG construction) from the consensus layer (DAG interpretation). This separation enables Mysticeti to achieve significantly higher system throughput [3], while eliminating the communication overhead typically required between validators during consensus. Validators observe their own local view of the DAG and deterministically group transactions into commits—the output of consensus. This determinism is fundamentally required to ensure that all validators receive the same committed transactions.

  3. Following consensus, transactions within the commit are ordered using a deterministic rule to maintain safety. In Sui, transactions are reordered based on decreasing gas price, giving priority to those who pay more for access. This underscores an important separation within Sui: the role of Consensus is to sequence a group of transactions together, ordering occurs ex post.

  4. Sui also employs a deterministic reordering of back references to prevent malicious validators from reordering their causal history in a way that benefits them.

Sui's design results in a system where unfairness in consensus ordering is minimized. With limited parties having access to incoming transactions and the requirement for deterministic ordering, the system inherently supports a higher baseline of order-fairness. On Sui, order-fairness can only be compromised through transaction censoring or manipulative practices like back-running and front-running⁶ [14], rather than from individual transaction reordering, which does not have the same negative impact to the protocol.

As outlined by Raikwar et al., there are two general directions of achieving order-fairness that could be further applied to Sui and Mysticeti to enhance its baseline level of fairness: time-based order-fairness and blind order-fairness.

Time-based Order-Fairness​

As the name implies, time-based order-fairness relies on timestamps to determine the order of transactions. In this approach, the system attempts to prioritize transactions that were initiated by clients the earliest. However, in decentralized, distributed systems, the concept of time can inherently be nondeterministic. As a result, various definitions of time-based order-fairness have emerged, each corresponding to different perceivable events, such as when a transaction was initially sent, when it was received, or approximations of these two events.

Sui does not directly implement a time-based order-fairness mechanism for transaction ordering. Furthermore, Sui's current method of ordering by decreasing gas price means that blocks may not always have a strict happened-before relationship.⁷ This can lead to scenarios where a transaction in a later block is ordered before a transaction in block preceding it, contradicting most notions of time-based order-fairness.

Mysticeti, however, can be modified slightly to accommodate time-based order-fairness. In Mysticeti, blocks are timestamped by validators, which in turn timestamps the contents of these blocks. While these timestamps could theoretically be used to enforce time-based order-fairness, they are vulnerable to manipulation by malicious validators seeking favorable transaction ordering. Timestamps would need be be obtained from a trusted source in order to utilize the block timestamps to provide such fairness.

In Mysticeti-FPC, validators explicitly vote for transactions containing at least one owned-object—a condition met by all user transactions due to the requirement of gas. This voting process could be further adapted to implement a time-based order-fairness mechanism within Mysticeti-FPC. This is even hinted at in the conclusion of [3]: "The structure of Mysticeti-FPC has all nodes timestamping transactions through their votes and may be useful for implementing MEV protections."

Blind Order-Fairness​

In this fairness model, proposers commit to transactions without knowing their contents, with transaction details only being revealed after the ordering has been finalized. This is achieved through a commit-reveal protocol, where the sequence of transactions is locked in before the transactions themselves are disclosed.

Sui and Mysticeti do not provide blind order-fairness; all transaction details, including involved objects, are fully visible to all parties throughout the transaction propagation path.

Fairness in Terms of DLT Components​

The DAG consists of interconnected blocks that each contain a payload of transactions. Both blocks and transactions share the objective of inclusion—blocks into the DAG, and transactions into blocks—but occupy different stages of the transaction lifecycle. As such, they face overlapping parties that can either support or compromise their fairness.

Block-level Fairness​

This notion of fairness seeks to ensure that every block has an equal opportunity to be appended to the DAG. Creating mechanisms that either improve a block's chances of inclusion or deter malicious validators from ignoring blocks leads to a more balanced and equitable environment where all blocks can be appended to the ledger.

Mysticeti's Universal Commit Rule inherently improves block-level fairness through its use of multiple leaders. By configuring more leaders per round, the rule increases the probability that each block will have the opportunity to be directly committed. Even in the case where a block B isn't directly committed, it has a high probability of being indirectly committed in a consecutive round. To demonstrate, consider this example: a validator creates a block B and forwards it to all other validators. All honest validators will include B in their references to the previous round but lets assume a malicious validator omits B in its references. Mysticeti's multi-leader commit rule increases the likelihood that an honest validator, who has included B, will be chosen as a leader and indirectly commit B.

In cases where a block B is proposed late or if there are network delays, Mysticeti's addition of weak links allows a block to reference blocks from all preceding rounds, not just the most recent one, thereby increasing the avenues for B's inclusion.

Let's also consider another scenario where a malicious validator attempts to compromise the fairness of their own block (e.g., by intentionally delaying when they propose it). Mysticeti, as it currently stands, does not impose any mechanism to force that validators propose the blocks they create. Instead, validators are indirectly incentivized to continue proposing their blocks due to socioeconomic factors. Adelie [7], a work-in-progress extension to Mysticeti, introduces the critical block rule to help address this issue, although it doesn't alleviate the problem altogether. This rule requires that for a block B to be valid, its critical block—the validator's latest block that precedes by at least 2 rounds—must be referenced by a quorum of stake. This mechanism ensures that validators must remain active in proposing their blocks in order to maintain their ability to create new ones.

The quorum of back references that forms the foundation of the DAG structure, combined with the multi-leader commit rule and the use of weak links, significantly boosts a block's chances of being appended to the DAG. Furthermore, Mysten Labs is already exploring future enhancements to further improve this fairness, particularly in scenarios involving malicious validators—the only entities capable of impeding block-level fairness.

Transaction-level Fairness​

Transaction fairness ensures that once a transaction is received by a validator, it will eventually be included in the DAG. 

Mysticeti does not directly implement a mechanism to enhance transaction-level fairness. Unlike Narwhal, which allowed transactions to be re-injected into the DAG if their block was garbage collected, Mysticeti has no concept of garbage collection.

Instead, Mysticeti indirectly provides transaction fairness by leveraging its focus on block-level fairness and the ability to disseminate transactions across multiple validators. Sending a transaction to multiple validators increases the chances that an honest validator will include it in their next block. The block-level fairness guarantees further ensure that the block, and thus the underlying transaction, have a higher probability of being committed to the ledger.

Discussion​

The multi-proposer architecture underpinning Mysticeti and earlier DAG-based protocols is gaining recognition as a viable solution to broader challenges regarding censorship resistance in blockchains. There are emerging proposals starting to advocate for Ethereum to incorporate some of these principles [15], [16]. Sui was live for over a year with a multi-proposer design and has since been upgraded to Mysticeti. I believe there is a lot to learn from Sui and its year of running a multi-proposer design in production.

Ordering​

Multi-proposer architectures that do not rely on a single leader for transaction ordering inherently require a deterministic rule to order the union of all transactions. This has sparked active discussions around Ethereum's potential multi-proposer roadmap, with early proposals including ordering by decreasing priority fees [17] and an execute as needed approach [15]. Sui⁸ currently adheres to an ordering rule similar to that proposed by Robinson et al., where transactions are ultimately ordered by decreasing gas price.

However, this approach only addresses part of the reordering challenge: both MCP and DAGs require a method to combine the blocks proposed during a single round or across multiple rounds. While ordering by gas price can be applied once you have a unified set of transactions, the question remains: how do you obtain the union of all proposed blocks?

The rule must include a degree of randomness; otherwise, a static ordering would enable certain proposers to always ensure their desired position within the final transaction order—such as always being at the top or bottom of the block, where "block" refers to output of the deterministic reordering rule mentioned above. On Sui, this is handled by: (1) ensuring transaction order follows round ordering when gas prices are identical for two transactions, and (2) applying a deterministic ordering rule to the back references of a block.

This leads to a scenario where no single validator controls the ordering of transactions. The only control a validator has is whether to:

  1. Include a transaction in their block. Since transactions are sent to multiple validators, excluding a transaction from one block has minimal impact.

  2. Include a reference to a block from a previous round, keeping in mind that a valid block must have 2f + 1 back references. If a malicious validator chooses to exclude a back reference, it only takes one honest validator to reference the excluded block for the malicious validator’s decision to be nullified.

  3. Back- or front-run a transaction from a previous round, while identifying such strategy within the time limits defined by Sui's block times, which currently range from 50ms (happy path) to 250ms (worst case). To guarantee profit, the block containing the malicious transaction must be the first directly committed leader of the round.

  4. Disseminate their block. Economically, there is little incentive for a validator to withhold their block.

Mysticeti’s multi-proposer architecture, coupled with the determinism underpinning Sui's transaction ordering, significantly reduces the potential for certain types of MEV on Sui and largely pushes MEV toward probabilistic opportunities.

Geographic Decentralization​

Geographic decentralization is a crucial property for achieving true decentralization [18]. A geographically distributed network mitigates regulatory risks, broadens global accessibility, leads to a more robust system, and increases the fairness across the network. These properties are tremendously important for maintaining adequate censorship resistance and can aid in alleviating the negative externalities of MEV.

As discussed in Fairness for Validators, DAG-based systems naturally foster greater geographic decentralization, and Mysticeti and Sui both have qualities that improve upon this.

  1. Mysticeti’s use of an uncertified DAG allows for greater geospatial decentralization by decreasing the validator-to-validator communication required to construct the DAG, as compared to previous DAG-based designs. In protocols like Narwhal and Bullshark, many rounds of back-and-forth communication were required to advance the DAG by a single round; geospatially distant validators would be at a disadvantage and could struggle to keep up with this process.

    Mysticeti minimizes this bandwidth overhead, requiring each validator to send a single packet–their proposed block–each round. This reduces the pressure on validators to optimize their networking latency (e.g., improving hardware or colocating with other validators or clients) in order to participate in the construction of the DAG.

  2. Decreasing communication overhead alone does not guarantee network decentralization. In many networks, a validator's dominant strategy involves being positioned within the network’s closest quorum to optimize average communication latency and maximize expected profit. Sui addresses this issue by decoupling PoS rewards from leader scores, ensuring that a validator's reward is not strictly based on their performance as a leader. This contrasts with PoS networks that tie rewards directly to block proposals.

    Rewards are instead accumulated and distributed to all validators at the end of an epoch. This mechanism further alleviates the benefit an individual validator will receive from optimizing their networking latency and also has the added benefit of removing the direct incentive to delay block proposals to propose more profitable blocks.

Validators in Sui are thus less incentivized to focus solely on latency improvements for personal gain, which is one of the largest inhibitors to fostering geographic decentralization. I would argue that the economic mechanisms mentioned above are an important property of a system that desires geographic decentralization and deserves further research. Additionally, more effort should be made by the Sui community to highlight the geographic location of validators and encourage directing stake toward those who promote a more diverse distribution.

Conclusion​

Sui is still very much in its infancy, and it's possible that the protocols with that will have the most significant impact on the network are yet to be released. Following the trends of other alt L1s, it's expected that popular protocols from other chains will also be forked to Sui. At the same time, Sui is continuing to pave the way for the creation of new and novel dApps. In both approaches, it is crucial to maintain the network's focus on fairness as Sui's dApp ecosystem continues to evolve. This focus will, in turn, support the creation of truly on-chain dApps that fundamentally require leveraging Sui's strengths, such as censorship resistance, low latency, and high throughput.

Sui is often praised for its improvements on developer experience and sub second e2e transaction latency. These are indeed tremendous feats that Sui has accomplished while still in its infancy, however, in my opinion, Mysten's heightened focus on creating a high utilization system that promotes fairness is often overlooked and will be one of the driving forces behind Sui's longevity.

Collaborate. If you would like to collaborate on research please reach out to kevin@concurrentresearch.xyz.

Footnotes​

¹ I will use the term proposer and validator interchangeably. ↩

² It's important to note that transaction execution isn't covered by Mysticeti's commit rule; the details of execution are left as an exercise for the reader. In all seriousness, Mysticeti can be adapted to support many different types of execution models [19]. ↩

³ I will show that in practice Mysticeti is able to provide a heightened level of fairness for its users. ↩

⁴ Sui differentiates between transaction finality and settlement finality. Settlement finality, or the guarantee around the execution outcome of your transaction, is only achieved after constructing an effects certificate from a quorum of validator responses (step 7 in Figure 5). ↩

⁵ Sui is set to migrate from this hybrid model to Mysticeti-FPC later this year. ↩

⁶ These types of order manipulation techniques are still hard to pull off successfully on Sui. As transactions are sent to multiple validators in unison, a singular validator censoring a transaction does not have a strong effect—the transaction will still be included by other, non-censoring validators. Similarly, due to Sui's quick block time, any delays in including a transaction (e.g., for finding a profitable sandwich) can lead to the user transaction being first included by another validator's block. ↩

⁷ Instead it is the role of consensus commits to maintain the happen-before relationship. That is, transactions across commits will always respect commit boundaries within their ordering. ↩

⁸ Mysticeti does not control how transactions are ordered; the transaction ordering discussed in this section is specific to the Sui protocol. ↩

Acknowledgements​

I would like to thank Alberto Sonnino and Mingwei Tian for reviewing this article and for always answering my seemingly sporadic questions. Similarly, I would like to thank Mark logan and (again) Alberto Sonnino and Mingwei Tian for joining our first MEVsticeti episode, where portions of this article were discussed.

Resources​

[1] Elijah Fox, Mallesh Pai, and Max Resnick. 2023. Censorship Resistance in On-Chain Auctions. arXiv preprint arXiv:2301.13321. Retrieved from https://arxiv.org/abs/2301.13321.

[2] Mayank Raikwar, Nikita Polyanskii, and Sebastian Müller. 2023. Fairness Notions in DAG-based DLTs. arXiv preprint arXiv:2308.04831. Retrieved from https://arxiv.org/abs/2308.04831.

[3] Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2024. Mysticeti: Reaching the Limits of Latency with Uncertified DAGs. arXiv preprint arXiv:2310.14821. Retrieved from https://arxiv.org/abs/2310.14821.

[4] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). Association for Computing Machinery, New York, NY, USA, 347–356. https://doi.org/10.1145/3293611.3331591.

[5] George Danezis, Eleftherios Kokoris Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus. arXiv preprint arXiv:2105.11827. Retrieved from https://arxiv.org/abs/2105.11827.

[6] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: DAG BFT Protocols Made Practical. arXiv preprint arXiv:2201.05677. Retrieved from https://arxiv.org/abs/2201.05677.

[7] Andrey Chursin. 2024. Adelie: Detection and Prevention of Byzantine Behaviour in DAG-based Consensus Protocols. arXiv preprint arXiv:2408.02000. Retrieved from https://arxiv.org/abs/2408.02000.

[8] Sui Foundation. 2024. Tokenomics. In Sui Documentation, Vol. 1, 1–17. Retrieved July 27, 2024, from https://docs.sui.io/assets/files/tokenomics-87c5e5545e70702a338016edee57dfd9.pdf.

[9] SuiVision. 2024. Validators. Retrieved August 2, 2024, from https://suivision.xyz/validators.

[10] Mark Logan. 2024. Sui Congestion Resilience. YouTube. Retrieved July 28, 2024, from https://www.youtube.com/watch?v=8SysLEpsXVE.

[11] Shashank Motepalli and Hans-Arno Jacobsen. 2023. Analyzing Geospatial Distribution in Blockchains. arXiv preprint arXiv:2305.17771. Retrieved from https://arxiv.org/abs/2305.17771.

[12] Sam Blackshear. 2024. SIP: Lowering the Validator Set Barrier to Entry. Sui Improvement Proposals Repository. Retrieved August 11, 2024, from https://github.com/sui-foundation/sips/pull/39.

[13] Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang. 2024. Sui Lutris: A Blockchain Combining Broadcast and Consensus. arXiv preprint arXiv:2310.18042. Retrieved from https://arxiv.org/abs/2310.18042.

[14] Rohan Shrothrium and Samuel Laferriere. 2024. MEV Meets DAG: Exploring MEV in DAG-based Blockchains. HackMD. Retrieved July 30, 2024, from https://hackmd.io/@0xtrojan/mev_meets_dag.

[15] Max Resnick. 2024. BRAID by Max Resnick - Paradigm Research Workshop. YouTube. Retrieved August 7, 2024, from https://www.youtube.com/watch?v=mJLERWmQ2uw.

[16] Max Resnick. 2024. Execution Consensus Separation. Retrieved August 7, 2024, from https://ethresear.ch/t/execution-consensus-separation/19964.

[17] Dan Robinson and Dave White. 2024. Priority Is All You Need. Paradigm. Retrieved August 27, 2024, from https://www.paradigm.xyz/2024/06/priority-is-all-you-need.

[18] Phil Daian. 2023. Decentralized crypto needs you: to be a geographical decentralization maxi. Flashbots. Retrieved August 28, 2024, from https://collective.flashbots.net/t/decentralized-crypto-needs-you-to-be-a-geographical-decentralization-maxi/1385.

[19] George Danezis and Dahlia Malkhi. 2022. Execution and Parallelism for DAG-Based BFT Consensus. Chainlink Blog. Retrieved August 2, 2024, from https://blog.chain.link/execution-and-parallelism-for-dag-based-bft-consensus/.