BlindPerm: Efficient MEV Mitigation with an Encrypted Mempool and Permutation

The contributions of this work are as follows.

1. 1.

   We introduce BlindPerm, a framework that combines an encrypted mempool with permutation to provide enhanced MEV mitigation for BFT style consensus. Particularly noteworthy is that our permutation-based enhancement is generic and can come at essentially no additional cost in comparison to regular blind ordering without shuffling.

2. 2.

   We present several optimizations that might be of independent interest, including selective encryption which enables users to only protect their MEV-potential transactions through encryption, thereby offering efficiency gains over a fully encrypted mempool. As a side contribution, in Appendix C we show how to extend our permutation techniques to Layer-2 blockchain protocols where instead of a BFT committee a single coordinator/sequencer conducts verifiable permutation.

3. 3.

   We demonstrate the effectiveness of our methods via simulating MEV extraction using the Ethereum historical data. We deploy the heuristics proposed in the literature [40] to detect arbitrage and sandwich attacks in the blocks over a one-year period and compare with the existing opportunities after applying our methods.

Although shuffling is a powerful technique, a block producer may try to get around it. In an extreme scenario, they can just put a single transaction in the block to surely capture an opportunity, say a front-running arbitrage. They can also reduce the effect of permutation by congestion, e.g., including too many of their own transactions in the block. We argue that they should give up on a large portion of the transaction fees in both cases though the revenue from MEV extraction can be nevertheless higher. It is interesting to see how to sidestep such an ability, with an intuitive solution being to make the block preparation decentralized [50]. Our constructions rely on threshold cryptosystems that might be a hurdle to implement in settings with a large population of parties and dynamic participation. Recent attempts in the literature proposed constructions for realizing threshold cryptosystems without an interactive setup phase (known as silent setup [26]) that could provide flexibility for supporting dynamic fault-tolerance and participation.

Several works in the literature separate the issue of transaction censorship from the common types of MEV that suffer user experience [29, 40, 48]. Following this thread we can make some bandwidth optimization in our BlindPerm constructions, particularly the one with users’ contributions towards the seed (Section 4.2). That is, only those users owning an MEV-potential transaction encrypt and let others send their transactions in plaintext. This stems from doing the shuffling after the commit, providing protection against possible front-running, back-running, and sandwich attack against any encrypted transactions. Observe that this does not affect the security of the permutation seed for the following reason. In order for the attacker to make a profit from a victim’s transaction tx (which we assume is encrypted) via the aforementioned strategies, they need to ensure it is indeed included in the committed block. This consequently guarantees that the corresponding key tx-key will be considered in the computation of the seed seed, guaranteeing uniform randomness. In fact, even if the validator only includes one encrypted transaction (i.e., victim’s transaction) in the block it is sufficient to ensure the security of the permutation. However, one caveat arises when there is no encrypted transaction included in the committed block. It basically implies there is no MEV-potential transaction in the block and thus there is no permutation seed, paving the way for the block producer to insert their transaction at their desired spot (refer to Section 3).

The concept of timelock encryption or timed encryption [42] allows encrypting a message that is decryptable only after passing some determined time. In other words, it features “encrypting to the future”. To provide a guaranteed delay, traditional schemes rely on sequential computation that is unparallizable. Recently, Gaily et al. [25] presented a construction that offers the same functionality without requiring any sequential computation. In fact, it relies on an existing committee (i.e., threshold network) that produces BLS signatures on time intervals (i.e., discrete view numbers). With the use of an identity-based encryption scheme [10], anyone can encrypt a message to the future under the view number as the identity that can be decrypted only after the release of the corresponding threshold signature as the private key. Given that we already have such threshold network producing BLS signatures in our BlindPerm construction thanks to the validators (Section 4.1), one may leverage it to enable users encrypt their transactions tx to any future view number of their choice. Also, this can pose a considerable boost in communication overhead compared to the typical threshold cryptography paradigm, as the permutation seed and the decryption key for a given view number is only a single BLS signature. By separating the role of validators from the threshold network the privacy of transactions lasts even against a dishonest majority of colluding validators. However, an immediate issue that arises with a naive implementation is the possibility of decrypting a transaction tx at view $r$ without having it included in the committed block by the block producer, making it vulnerable to MEV extraction afterwards. Very recently, Choudhuri et al. [18] proposed the notion of batched threshold encryption that fixes the aforementioned issue by providing pending transaction privacy to only decrypt the batch of transactions made it to block while the partial decryption key still being independent of the batch size. An intriguing research question is how to use secure randomness both for decryption and permutation (as in [25]), while preserving privacy for pending transactions (as in [18]).

SCRAPE [15] is a state-of-the-art PVSS with the following sharing procedure PVSS.Share. The dealer samples a uniform value $s\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$, sets the secret as a group element of form $S=h^s$, splits $s$ into shares ${\{s_i\}}_{i\in [n]}$ using Shamir secret sharing, and computes the encrypted shares under parties’ public keys ${\{{\widehat{s}}_i=pk_i^{}{}_{}{}^{s_i}\}}_{i\in [n]}$. The dealer also publishes commitment to shares and $O(n)$-sized NIZK proofs ${\pi }_s$ with individual shares as their witnesses, enabling anyone to check the correctness of sharing with a linear cost. Cascudo et al. [16] introduce efficiency optimizations over SCRAPE to reduce its communication and computation complexities. In particular, the dealer needs to send just $O(1)$-sized proof of correctness with no public commitments, making the overhead close to optimum [16]. They managed to achieve these efficiencies thanks to making two modifications in the usual model of PVSS, including assigning key pairs to the dealer and doing secret sharing in a group. Fortunately, we can use such PVSS in our BlindPerm construction by accommodating both modifications as the users are equipped with such key-pairs⁷⁷7Such key-pairs are nevertheless needed, either ephemeral (for wallets) or registered (for authentication). and symmetric key tx-key to share could be a random group element. We now briefly discuss the high-level idea behind the PVSS proposed in [16]. The authors initially observe that it is possible to check the correctness of sharing in SCRAPE without the involvement of the shareholders’ key-pairs. To do so, each encrypted share should be of form ${\widehat{S}}_i=S_i\cdot pk_i^{}{}_{}{}^{s{k}_D}$, establishing a shared Diffie-Hellman key between the dealer and each shareholder to communicate the share. This then turns out to be useful in allowing the dealer to produce one NIZK proof with its secret key $s{k}_D$ being the witness (instead of individual shares as in SCRAPE) to ensure the correctness of sharing as a whole. We refer the reader to [16] for more details.

We consider two scenarios to conduct our simulations. The first scenario follows the heuristics used to detect perfect sandwich attacks where front-running, victim, and backrunning transactions are ordered immediately with no intermediaries. We measure how much revenue could have been extracted if we applied a random permutation on the list of transactions in a block before execution. We find that the revenue is reduced from a total of $31,749.59$ ETH for the historical data to $1.74$ ETH, showing almost a complete mitigation success as the attacks are no longer profitable.

Further, we relax the constraint and consider a (worst-case) scenario where the relative ordering of the involved transactions after permutation still holds but they are separated by multiple transactions, leading to imperfect profitable sandwich attacks.¹⁰¹⁰10It is shown that over 80% of profitable sandwich attacks are perfect and also no intermediate transaction is found in almost 99.6% of privately relayed sandwich attacks [40]. To measure the expected amount of MEV extraction we find the indices of the front-running and back-running transactions, say $i$ and $j$ respectively in the historical block. If $i\le j$ holds after the permutation, we consider win to be the event that the attack still is profitable, i.e., the victim transaction appears somewhere in the middle. So, due to the uniform distribution we have Pr[win] = $\frac{|i-j|}{|\text{B}|}$, where $|\text{B}|$ denotes the number of transactions in the block.¹¹¹¹11Concretely, we noticed that the average number of transactions in a block is 231 with the minimum and maximum being 3 and 1386, respectively. Thus, we find that the revenue is reduced from a total of $31,749.59$ ETH for the historical data to $4,837.54$ ETH after doing the permutation, showing almost 85% of mitigation success. The numerical results are presented in Figure 2.

We separately run our simulations for front-running and back-running arbitrage to give a better insight on the potential impact of a random permutation in both cases. We remark that arbitrage is not inherently harmful and is usually considered benign as it allows for market sustainability, e.g., by synchronizing the price of assets across different exchanges [47]. The goal here is to reduce the sole power of the block producer (i.e., sequencer or validator) in MEV extraction and provide a rather fair chance for others to do so. Therefore, in Figure 3 we report the total MEV extraction (possibly by the block producer [39]) with and without doing permutation. We proceed with a brief description of our analysis that leads to the reported results.

1. 1.

   Front-running: A front-running arbitrage transaction should be profitable if it gets executed at the top of the block (i.e., the state change is due to the previous block). So, we find the index of the (front-running) arbitrage transaction in the historical block $i$ and then check if its index after the permutation is lower than or equal.¹²¹²12Note that top of the block does not necessarily refer to the position with the lowest index as we detected an arbitrage transaction that is positioned at index 7 while being profitable. See https://etherscan.io/tx/0xcfd6f698657dd2851bea4b748723ed6ffb5503641f5ffbd8122ae120f148b034. If not, the arbitrage transaction could still be profitable with a weight of at most Pr[win] = $1-\frac{|i-j|}{|\text{B}|}$, where $j$ is the index of the original arbitrage transaction after the permutation. Note that we consider a (worst-case) scenario where there is only one competitive arbitrage transaction in the block. However, given that arbitrage can be safely performed by anyone observing the latest state [47], the probability of win event may be considerably lower in practice. We find the revenue is reduced from a total of $1,483.18$ ETH for the historical data to $780.74$ ETH after doing the permutation, showing almost 50% of mitigation success. This actually is in line with our expectation that the chance of a sole MEV extraction reduces by half.

2. 2.

   Back-running: Using the heuristics we are only able to find the (back-running) arbitrage transaction and do not infer the relative position of the arbitrage transaction with the victim/opportunity transaction in the historical block. So, we rely on a common assumption that the (back-running) arbitrage transaction is ordered immediately after the victim transaction. Let $i$, and $j$ be the indices of the victim and arbitrage transactions in the original block. If $i\le j$ holds after the permutation, the arbitrage transaction could still be profitable with a weight of at most Pr[win] = $1-\frac{|i-j|}{|\text{B}|}$. We find that the revenue is reduced from a total of $410,112.07$ ETH for the historical data to $133,613.02$ ETH after doing the permutation, showing almost 67% of mitigation success.

Finally, we present the last simulation result in Figure 4 where we report the cumulative MEV revenue including arbitrage and sandwich attacks for the historical data and BlindPerm. An Encrypted mempool helps with mitigating the strategies that mainly depend on the content of the (victim) transactions such as back-running arbitrage and sandwich attacks. Given that our solution provides permutation enhancement with almost no cost than building up an encrypted mempool, we refrain from a direct comparison between MEV extraction with only encryption and BlindPerm. We find that the revenue is reduced from a total of $443,866.13$ ETH for the historical data to $634.88$ ETH for BlindPerm.

Permuting the list of transactions in a committed block before execution can also be realized in the longest-chain setting. In a proof-of-work (PoW) blockchain, the miner needs to find a solution (i.e., nonce) to a puzzle to be eligible as the block producer. Our idea is to use this nonce together with the Merkle root of the transactions (and possibly some auxiliary data) as the seed for the permutation. So, the state change occurs with regard to the permuted block. Should a miner decide to modify the ordering of transactions in the block after learning the seed, they face the threat of loss due to the difficulty rule of the puzzle. Therefore, this method enhances the recent efforts in leveraging trusted execution environments (TEEs), such as SGX [9], to provide privacy for transactions up to a point where their inclusion in the block is ensured. TEEs can be thought of as a replacement for the committee to generate a key-pair, with the public key being used for encryption. The procedure operates as follows: Encrypted transactions are initially received and decrypted within the SGX, where they are then ordered into a block. The block header, generated by the SGX, is transmitted to the miner, who begins the process of solving the associated cryptographic puzzle. Upon submission of a valid nonce, the miner is granted access to the full transaction body. Subsequently, any alteration in the transaction order within the block necessitates solving a new cryptographic puzzle. In a recent work, Alpos et al. [2] presented a construction that utilizes permutation to prevent sandwich attacks in the (PoW) longest-chain setting. At a high level, a set of previous leaders contribute towards permutation seed using a commit-reveal mechanism. They use slashing techniques to protect against biasing and splitting the transactions into chunks to increase the permutation space and thus protect against a possible collusion of leaders. Consequently, the system incurs a considerable latency and is also limited in applicability.

The consensus problem at the core of blockchain protocols known as SMR traditionally does not aim at getting parties agree on a specific ordering, but a total ordering where all the honest parties are guaranteed to end up with the same sequence of transactions. One way to deal with this is to augment its requirements with an order fairness property. It was shown by two concurrent works of [33, 31] that arguably the most natural definition of fairness known as receive/relative order fairness is impossible to achieve. This notion essentially states that for any two transactions tx and tx’, if some majority of nodes receive the former sooner than the latter, tx should be ordered before tx’. The impossibility result is due to the so-called Condorcet’s cycle/paradox [27], preventing parties to agree on a fair ordering of transactions even when all behave honestly [31].¹³¹³13Such a cycle shows up intransitivity in the majoritarian relations, yielding a paradox in selecting a single winner. The impossibility result necessitates the adoption of other variants of timed-order fairness. Kelkar et al. [31] relaxed their definition to capture batch order fairness by making “before” to “no later”, treating such transactions in batches with relative ordering. In fact, the batch order fairness sidesteps the impossibility result by allowing output transactions in batches and ignoring the possible unfairness resulting from the cycles in each batch. Kelkar et al. [31] introduced Aequitas protocols that order a transaction tx no later than tx’ if some fraction $\gamma$ of parties receive tx before tx’, known as $\gamma$-batch order fairness. Apart from necessitating a relaxed definition of order fairness, it turns out Condorcet cycles may become larger arbitrarily and also negatively affect the liveness of [31], motivating the design of a follow-up protocol called Themis [30] with a similar spirit. Cachin et al. [14] revisits the notion of order fairness by changing the relative measure of batch order fairness to differential order fairness, taking into account the difference between the number of correct parties that receive a tx before tx’ compared to that of vice versa. They argue about the usefulness of such modification to tolerate higher fault tolerance compared to that of batch order fairness [31, 30] with a reasonable value for parameter $\gamma$, where in their treatment only counts the honest parties.

The requirement for maintaining causality in SMR systems was first put forth by [41]. They showed the importance of preserving the casual order of users/clients’ requests and proposed adding a confidentiality layer to the underlying atomic broadcast (i.e., SMR) to establish a secure causal atomic broadcast [22]. The recent efforts in literature for blind-order fairness are essentially an extension of this approach, realizing the confidentiality layer with a range of new cryptographic tools and techniques. In [52], validators just carry out the consensus to commit a block of encrypted transactions where a separate secret-management committee runs the decryption per transaction. Such separation could provide optimum fault tolerance of for the committee. Fino [35] integrates the blind-order fairness into DAG-based BFT systems that allow parallel dissemination of proposals by multiple validators, achieving high throughput [20, 46]. The proposed blind-order fairness has a hybrid structure, where the key for decryption is either obtained via a fast path using secret-sharing with post-verification or a slow path using threshold decryption. The authors in [37] develop a blind-order fairness system with minimal communication overhead, allowing users to encrypt their transactions to some future time (i.e., view number) with the corresponding private key being released by a committee then. FairPoS [17] introduces a similar notion to blind-order fairness for a longest-chain style consensus called input fairness. They rely on time-based cryptography [13] to hide the content of transactions under a single unknown key until block finalization, which consequently leads to achieving adaptive security. This is implied by the non-parallelizable sequential computation needed for decryption, preventing the leakage of sensitive information (i.e., key material) upon corrupting an honest party. Note that our proposed optimization using timelock encryption share the same rationale with [37, 17] in the sense that a single key (i.e., BLS signature) is enough for decrypting all the encrypted transactions in a committed block.

Malkhi and Szalachowski [35] present four approaches to building up an encrypted mempool with threshold security, including threshold cryptography, VSS, secret sharing with post-verification, and hybrid. In what follows, we briefly describe secret sharing with post-verification and hybrid that could be used in BlindPerm depending on the application.

1. 1.

   Secret Sharing with Post-verification: VSS aims at ensuring the uniqueness, meaning that invoking SS.Combine with any threshold number of shares results in the same outcome, and completeness, meaning that any honest party receives a (distinct) valid share from SS.Share. The authors in [35] adapt a technique introduced in [49] to relax the requirements and only offer uniqueness. To do so, the dealer runs SS.Share, combines all shares in a Merkle tree, certifies the root, and sends with each share a proof of membership, i.e., a Merkle tree path to the root. When a party receives a share, they should verify the Merkle tree proof against the certified root (that is already broadcast by the dealer) before acknowledging it. Moreover, after running SS.Combine, each party re-encodes the Merkle tree with the reconstructed secret and compares it with the data sent by the dealer. If the comparison fails, the dealer is faulty. Observe that here the signed Merkle root acts as a commitment to somewhat relax the use of polynomial commitment. This protocol is the fastest as it uses the efficient and trivial primitives. Note that the sharing completes for each transaction when there are $n-t$ acknowledgments to ensure $t+1$ honest validators have received consistent shares, incurring latency. Another issue mentioned in [35] is the possible impact of some specific subset of $t+1$ validators on the latency of SS.Combine. More precisely, since there is no guarantee that all honest validators receive their shares, SS.Combine may not be run by the fastest $t+1$ validators and depend on a specific subset.

2. 2.

   Hybrid: In order to address the dependency issue, a hybrid design is proposed where secret sharing with post-verification is augmented with threshold cryptography, enabling any subset of $t+1$ validators to perform the decryption. Moreover, to maintain safety the protocol requires the results recovered from the SS.Combine be equal to TE.Dec. To do so, each validator can make use of $t+1$ secret shares or partial decryptions to check both approaches have the same output. They just need to re-encrypt the key and re-encodes the Merkle tree and check with those originally sent by the dealer.