Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks
by Orestis Alpos (University of Bern), Ignacio Amores-Sesar (University of Bern, IC3), Christian Cachin (University of Bern, IC3), Michelle Yeo (National University of Singapore)
The problems of maximal-extractable value (MEV) and front-running attacks have plagued decentralized finance (DeFi) in the recent years. We tackle the problem of sandwich attacks in general and introduce a protocol to transform any blockchain consensus algorithm into a new one that has the same security, but in which sandwich attacks are no longer profitable. Our protocol is fully decentralized with no trusted third parties or heavy cryptographic primitives. It makes existing blockchains resilient to such attacks in exchange for increased latency until consensus becomes final and by adding a small computational overhead.
Sandwich attacks
Sandwich attacks account for a loss of 1.1 M USD over the last 30 days for users of Ethereum as reported by Eigenphi.
In most blockchain networks, validators have access to incoming transactions at the moment they enter the network and before consensus on them is reached. Transactions are usually disseminated with a gossip protocol among the peers. Some validators play a special role in consensus and may select the transactions for a particular block and determine their order within the block. In a sandwich attack, such validators exploit this power to gain an unfair advantage.
Consider an honest transaction that swaps one asset X for another asset Y in a decentralized exchange. Many trustless DeFi exchanges compute the relevant rates automatically based on a fixed algorithm and the current reserves they hold; a typical example are constant-function market makers such as Uniswap.
Suppose a profit-seeking validator observes such an X-to-Y swap transaction tx* issued by an unsuspecting client. To maximize its own advantage, the validator can exploit this knowledge and insert its own X-to-Y exchange transaction tx₁ before tx*. This is an example of front-running due to insider knowledge, such insider trading may also occur in traditional finance, where elaborate regulations and preventing methods aimed to prevent that. The validator will use the computed exchange rate and sell, say, k units of X to get units of Y. All other things being equal, the client’s transaction tx* will subsequently execute at a slightly worse exchange rate than if tx₁ were not there. To finish off the attack, the validator back-runs the client’s swap with another transaction tx₂ of its own that exchanges units of Y back to X. The validator again manipulates the transactions landing in the block to its own advantage. Typically, it will obtain more than k units of X at the end. This shows how consensus validators may profit from their privileged position and their insider knowledge. These and related attacks have had significant economic impact on DeFi markets.
Randomizing the order
An important technique to mitigate this problem is thus to remove the control over the positioning of the transactions in the block from the validators. Assume a random order is imposed within a block В and let us focus on three transactions in В: the client’s transaction tx*, the front-running transaction tx₁, and the back-running transaction tx₂. Since any relative ordering of these three transactions is equally likely, tx₁ will be ordered before tx₂ with the same probability as tx₂ before tx₁, hence, the validator will win or lose with the same probability.
We achieve a random order without a third party by introducing the Partitioned and Permuted Protocol, abbreviated Π³, a novel efficient decentralized algorithm that does not rely on external resources and that counters sandwich attacks effectively. Protocol Π³ determines the final order of transactions in a block В created by a validator Vᵢ a randomly chosen permutation, denoted by Σ.
Obviously, one cannot trust a single validator or a third party to pick this randomness in a fair way. Instead, Π³ lets a set of leaders select a fresh, random permutation Σ for each block. These leaders are the validators that created the most recent blocks in the chain. But note that the permutation Σ for the current block В must not be known until after В has been created, otherwise the validator V creating В would have the option to use Σ̄ ¹, the inverse of Σ, to initially order the transactions in В, so that the final order is the one that benefits V. Protocol Π³ overcomes this by making Σ known only after В has been fixed some δ bocks later. But this introduces another problem because Σ could be influenced after creating В by a coalition of such leaders that bias it to result in a more profitable outcome for themselves. For these reasons, Π³ has the leaders (1) commit to their contributions before (2) В becomes known and thereby produce unbiased randomness. To incentivize leaders to open their commitments during a period of τ blocks (4) Π³ employs a delayed reward release mechanism that only releases the block reward to leaders when they have generated and opened all commitments (5) after an additional delay of δ blocks. The waiting period (3) is inserted before the opening of the commitments to prevent that the validators rewrite block В. These five steps are shown in the figure below.
Increasing the randomness
In some cases, however, performing a sandwich attack might still be more profitable than gaining the block reward, and hence a leader might nevertheless choose to not reveal their commitment and thereby bias the resulting permutation. In general, a coalition of k leaders can choose among 2ᵏ permutations out of the ℓ! possible ones (ℓ! means ℓ factorial, which is of exponential size in ℓ), where a block is formed by ℓ transactions. It turns out that the probability that tx₁, tx*, and tx₂ appear in that order in one of the 2ᵏ permutations is 1/6 .
Protocol Π³ mitigates this by dividing each transaction into m chunks which lowers the probability of a profitable permutation in two ways. First, the number of possible permutations is much larger, (ℓm)! instead of ℓ!. Second, a permutation is now profitable if the majority of chunks of tx₁ appear before the chunks of tx*, and vice versa for the chunks of tx₂. The probability of a profitable permutation approaches zero rapidly as the number of chunks m increases. Protocol Π³ is summarized in the diagram below.
For more information we refer to our research paper that has been presented at the OPODIS 2023 conference.
Editor: Bria Han (IC3, jh2584@cornell.edu)
Stay ahead of the curve with the latest IC3 research! Subscribe now to our mailing list!
