2023-04-11 Audit Report - Skip Mev Tendermint

Security Audit Report

Skip: mev-tendermint

Authors: Manuel Bravo, Mirel Dalcekovic

Table of Contents Audit Overview ............................................................................................................ 1 Scope of this report 1 Conducted work 1 Conclusions 1 Disclaimer 1 System Overview......................................................................................................... 3 Synopsis 3 Content 3 Limitations of the Specification 3 Further Reading 3 Motivation and Basic Concepts 4 System Model and Properties 5 Technical Specification 7 Properties Analysis 18 Findings ..................................................................................................................... 22 v1 Tendermint's mempool isn't safe 23 Failing consensus commit due to error updating mempools 24 Sidecar mempool is not locked on Commit() 25 Redundant bundle metadata in sidecar mempool 26 Inefficient code in ReapMaxTxs 28 Suboptimal reaping due to CombineSidecarAndMempoolTxs 29 Suboptimal reaping due to maxBundleId 30 Weak guarantees for traders 31 List of minor comments in diff PR 32 © 2023 Informal Systems Skip: mev-tendermint

Audit Overview Scope of this report This is a report on the code review audit of Skip’s mev-tendermint https://github.com/skip-mev/mev-tendermint/ releases/tag/v0.34.24-mev.14 The audit took place from February 3, 2023 through March 14, 2023 by Informal Systems by the following personnel: • Manuel Bravo • Mirel Dalcekovic The scope of this audit was limited to manual code review and manual analysis and reconstruction of the protocols.

Conducted work The audit team started its work on February 3rd. We have had weekly meetings with the Skip team to ask questions, confirm our understanding and present findings. The development team gave us all the necessary documentation (videos and documents) to ease the understanding of the Skip protocol. The audit team engaged in reviewing the changes made by Skip to two main components of Tendermint: • Changes made to the p2p package to allow Skip validators to register with their bundle relayer (the sentinel), receive bundles of transactions that are treated atomically, and reconnect if they lose connection. • Changes made to the mempool and the reaping functions to allow validators to reap Skip bundles at the top of their block. We have also written an English specification of the protocol. This work included formalizing assumptions and formulating desired properties, as well as analyzing which of these properties are guaranteed by the protocol. The sentinel’s code was not audited.

Conclusions Overall, we found the codebase to be of good quality: the code is well-structured and easy to follow. Our main concern was to check whether there was a chance that consensus is delayed in any way due to changes introduced to both the p2p and the mempool layers. We concluded that it is not the case at the cost of weakening traders’ guarantees. In the current design, these two desired properties are in tension. Despite the general good quality, we found some details that should be addressed in order to raise the quality of the code, although none critical.

Disclaimer This report is subject to the terms and conditions (including without limitation, description of services, confidentiality, disclaimer and limitation of liability, etc.) set forth in the associated Services Agreement. This report provided in connection with the Services set forth in the Services Agreement shall be used by the Company only to the extent permitted under the terms and conditions set forth in the Agreement. This audit report is provided on an “as is” basis, with no guarantee of the completeness, accuracy, timeliness or of the results obtained by use of the information provided. Informal has relied upon information and data provided by the client, and is not responsible for any errors or omissions in such information and data or results obtained from the use of that information or conclusions in this report. Informal makes no warranty of any kind, express or implied, regarding the accuracy, adequacy, validity, reliability, availability or completeness of this report. This report should not be considered or utilized as a complete assessment of the overall utility, security or bugfree status of the code.

This audit report contains confidential information and is only intended for use by the client. Reuse or republication of the audit report other than as authorized by the client is prohibited. This report is not, nor should it be considered, an “endorsement”, “approval” or “disapproval” of any particular project or team. This report is not, nor should it be considered, an indication of the economics or value of any “product” or “asset” created by any team or project that contracts with Informal to perform a security assessment. This report does not provide any warranty or guarantee regarding the absolute bug-free nature of the technology analyzed, nor does it provide any indication of the client’s business, business model or legal compliance. This report should not be used in any way to make decisions around investment or involvement with any particular project. This report in no way provides investment advice, nor should it be leveraged as investment advice of any sort. Blockchain technology and cryptographic assets in general and by definition present a high level of ongoing risk. Client is responsible for its own due diligence and continuing security in this regard.

System Overview Synopsis This section specifies the data structures and subprotocols of the Skip protocol. The Skip protocol implements an auction system that allows Cosmos users to capture maximal extractable value (MEV) across a variety of chains in the ecosystem.

Content • Motivation and Basic Concepts • System Model and Properties • Technical Specification • Properties Analysis

Limitations of the Specification • The implementation maintains a legacy sidecar channel. This is not detailed in this specification. • Metrics and logging systems are omitted from the specification. • The logic around notifyTxsAvailable is omitted from the specification. • The API of SyncMap (this spec) and sync.map (the implementation) is slightly different. For instance, sync.map offers a LoadOrStore method that SyncMap does not. If relevant, this could be added in the future.

Further Reading • Skip's white paper • About Tendermint's timeout_commit • About cross-block transaction duplication

Motivation and Basic Concepts

Motivation Maximal extractable value (MEV) refers to a strategy to include, omit, or reorder transactions when creating a block to attempt to maximize profit. For instance, a block proposer can trivially censor, reshuffle, or inject their own transactions to maximize its own profit as far as the block includes valid transactions. A second, more disturbing, example of MEV attacks in the Cosmos ecosystem are orchestrated by users (aka traders). Currently, Cosmos chains like Juno, Terra and Osmosis have a first-come-first-serve mempool. Users exploit this fact to win arbitrage opportunities by locating their arbitrage bots as close to as many validators and full nodes as possible and spam them with transactions. This has many negative effects such as centralization of profits and chain halting risk. See this for more information about the negative effects. Due to the limitations of the current ABCI interface, preventing block proposers to capture MEV is very challenging. The Skip protocol instead is concerned with protecting users from the harmful effects of MEV in the second scenario. Skip's goal is to allow traders to compete in a fair auction system and eliminate forms of MEV that are toxic, such as sandwiching and spam.

Definitions A mev-validator is a validator running the skip protocol.

A bundle is an ordered set of transactions.

A mev-transaction is a transaction received from a sentinel node. Each mev-transaction must belong to a bundle.

The sidecar is a mempool for bundle instantiated by mev-validators.

A bundle is complete at a mev-validator when its sidecar mempool stores all its containing transactions.

We use mempool to refer to Tendermint's mempool.

A trader (aka searcher) is a participant of an auction. Traders participate in auctions by submitting bundles to sentinel nodes.

Sentinel nodes are p2p nodes that run the auction. Sentinel nodes receive bundles from traders, append a payment transaction to the bundle and forward them to validators in an order that respects the associated fees. There is a single sentinel node per chain. We use chain sentinel to refer to the sentinel of a given chain.

System Model and Properties

Assumptions

Assumption 1: Sentinel nodes are trustworthy Validators assume that sentinel nodes follow the protocol. This implies that: • Sentinel nodes do not censor or reshuffle transactions in the bundles submitted by traders.

Assumption 2: Weak network guarantees Validators do not expect any guarantee from the network. This means that messages sent from the sentinel may take indefinitely long, get lost or be reordered.

Desired Properties

Property 1 [No-disruption]: Minimal consensus disturbance This rules out designs that require synchronous communication with an external component during consensus operation (aka pull-based models) in favor of designs that distribute bundles in the background, out of consensus operation critical path (aka push-based models). For instance, if the proposer of a block engages into a synchronous communication with its sentinel node to retrieve a set bundles during block creation, the property would be violated. This is because block creation would be delayed which may affect the correct operation of consensus: timer management would need to account for the block creation delay.

Property 2 [Atomicity]: Atomicity for bundles of transactions Bundles are an indivisible and irreducible set of transactions such that when a bundle is included in a block either all transactions are executed or none.

Property 3 [Order]: The transactions within a bundle are executed in order The set of transactions within a bundle are totally ordered and must be executed in that order.

Property 4 [At-most-once]: A block should not include duplicates Transactions are not always idempotent, thus including duplicated transactions in a block should be prevented. Bundles typically include transactions from the mempool. Thus, when blocks include transactions from both the mempool and the sidecar, it is likely to have duplicates. To satisfy this property, one has to remove duplicates.

Property 5 [Priority]: Priority guaranteed for highest paying bundles Assume that for a given action the sentinel has received two bundles b1 and b2 such that the trader that submitted b1 is willing to pay a higher fee. By this property, the protocol should guarantee that if only one bundle is included in the auctioned block, then it has to be b1 : b1 has priority over b2 . The property also allows both bundles to be included or none.

Property 6 [Optimal-reaping]: A proposer includes in as block as many bundles as possible The protocol must guarantee that a block proposer reaps as many bundles from the sidecar mempool as possible, given the constraints of other properties such as Priority and Atomicity. This is important to maximize profit.

Property 7 [Privacy]: Privacy for users submitting bundles It is important that transactions submitted by traders and the fees they are willing to pay are not visible to other traders or validators until the transactions are committed, e.g., this is important to minimize front-running.

Property 8 [Accountability]: Cheater traders are ejected If a trader submits a front-running or a sandwich bundle it must be ejected.

Technical Specification

General Design The Skip protocol integrates two main components: the sidecar mempool and the sentinel. Each mev-validator instantiates the sidecar mempool locally and connects to the sentinel of the chain it validates through the p2p layer. The protocol takes the following steps:

Traders submit bundles to the sentinel. Submitted bundles are typically composed of two transactions: a transaction that the trader has seen in its local Tendermint mempool and a second transaction that must be executed after the first. Traders have access to the Tendermint mempool because they usually run a full node. Together with each bundle, the trader submits two key pieces of data: • A height desiredHeight that indicates the height at which the bundle must be included in the chain. When the trader sets desiredHeight to 0 , this indicates the sentinel that the bundle should be included in the next height. • A fee that the trader is willing to pay if the bundle makes it to the block at the desired height.
The sentinel accepts bundles for a given height until 400ms before the first proposer of that height starts creating the block. At that point, we say that the sentinel closes the auction for that height. The sentinel infers this time by starting a timer when it learns that the previous height has been decided based on Tendermint's timeout_commit : how long we wait after committing a block, before starting on the new height. Of course, this is not perfectly synchronized: the time that the first proposer of the height starts its timeout_commit is not necessarily the time when the sentinel learns about the previous decision.
Once the auction for a height is closed, the sentinel starts sending bundles to the first proposer of that height in descending fee ordered: first those bundles with higher fees. The sentinel sends bundles in parts, each including a single transaction called SidecarTx . This is a limitation of the p2p layer of Tendermint: it is designed to include a single transaction per p2p message. It is worth noting that the sentinel appends a transaction to each of the bundles with a payment transaction.
When a mev-validators receives a SidecarTx calls the AddTx function, which after some safety checks, adds the transaction to its sidecar mempool.
When a mew-validator becomes the block proposer, it reaps both the sidecar mempool and Tendermint's mempool to create the block. It first reaps the sidecar mempool looking for fully received bundles, respecting the order fixed by the sentinel. Then if there is room for more transactions in the block, it includes transactions from Tendermint's mempool.
After a block is committed, the mev-validator updates the sidecar mempool by calling the Update function. This function removes from the sidecar mempool any sidecarTx belonging to a bundle whose desired height has already passed.

Data Structures The protocol does not assume any specific transaction format. It assumes that a transaction Tx is a byte array byte[] of any size. Transactions are uniquely identified by a key TxKey , a byte array byte[] of fixed size. Typically, the key of a transaction is its hash. We assume that a function Key(tx: Tx) returns the transaction's key. Throughout the specification, we use a few data types that are not standard and have not been introduced:

• SyncMap is a thread-safe Map . • SyncArray is a thread-safe Array . We assume that there is a method delete(elem) that removes elem from the array and shifts its elements accordingly.

• Cache implements a cache for transactions. The cache defines a maximum size. Once the maximum is reached, elements are dropped when new elements are added. The cache offers the following API: • Reset() : resets the cache to an empty state. • Push(tx: Tx) : checks if the transaction is in the cache. If it is already, it returns false . Otherwise, it adds the transaction and returns true . • Remove(tx: Tx) : removes the transaction from the cache. • Has(tx: Tx) : reports whether the transaction is present in the cache or not. • Mutex and RWMutex are self-explanatory. • Error is left undefined intentionally. The error variable name should be self-explanatory.

A SidecarTx is a transaction that belongs to a bundle. Mev-validators store these in their local sidecar mempool.

interface SidecarTx { tx: Tx // tx bytes desiredHeight: int bundleId: int bundleOrder: int bundleSize: int gasWanted: int senders: SyncMap<int, bool> }

• tx is the transaction. • bundleOrder defines the order of the transaction within the associated bundle. • desiredHeight and bundleId are as defined above. • bundleSize is the same than enforcedSize for bundles. • gasWanted determines the amount of gas executing the transaction would require. • senders is a thread-safe map that tracks from which peers the transactions has been received. It goal is to avoid broadcasting transactions to peers that already have them. Bundle is defined as follows.

interface Bundle { orderedTxsMap: SyncMap<int, SidecarTx> desiredHeight: int bundleId: int currentSize: int enforcedSize: int }

• orderedTxsMap stores the set of transactions that belong to the bundle that have been received. • The desiredHeight determines the height at which the bundle must be included in a block. • For a given height, bundleId defines the order of this bundle relative to all the bundles received by the sentinel during the auction for desiredHeight . • currentSize determines the total number of transactions stored in orderedTxsMap . • enforcedSize defines the total size of the bundle.

Bundles are uniquely identified by an integer id bundleId and its desired height desiredHeight . It is the sentinel who is in charge of enforcing the uniqueness of bundle ids.

interface BundleKey { desiredHeight: int bundleId: int }

The Sidecar is defined as follows:

interface Sidecar { height: int heightForFiringAuction: int txsBytes: int lastBundleHeight: int txs: SyncArray txsMap: SyncMap<TxKey, Tx> bundles: SyncMap<BundleKey, Bundle> maxBundleID: int updateMtx: RWMutex maxBundleIDMtx: Mutex bundleSizeMtx: Mutex cache: Cache }

• height is the latest committed height. • heightForFiringAuction is the next height to be committed. • txsBytes is the total size of sidecar in bytes. • lastBundleHeight is height of last accepted bundle. • txs is a threat-safe ordered list. It is primarily used by the p2p layer to broadcast SidecarTx to other peers. • txsMap stores SidecarTx transactions in a thread-safe map for fast access. • bundles stores bundles in a thread-safe map. Each bundle then stores the set of SidecarTx that compose it in its orderedTxsMap map. • updateMtx , maxBundleIDMtx and bundleSizeMtx are mutexes to manage the concurrent access to the sidecar mempool. • cache keeps a cache of already-seen txs.

Finally, ReapedTxs is a pair including a list of transactions and one mapping the gas estimation required to execute each of the transactions. This is used by CombineSidecarAndMempoolTxs and ReapMaxTxs .

interface ReapedTxs { txs: Tx[] gasWanteds: int[] }

The P2P Layer Protocols This section describes how the main components of the Skip protocol fit within the p2p layer. We assume the most common case in which mev-validators are not reachable directly from sentinels: this is a common deployment where validators are shielded from attacks, e.g., DoS attacks, by an infrastructure of sentry nodes. In the case that there is no sentry nodes infrastructure, the mev-validator will

Excerpt (19997 of 58358 characters). Read the whole page on informalsystems/audits ↗

← Back to Documentation