Permuting Transactions in Ethereum Blocks: An Empirical Study

Several recent proposals implicitly or explicitly suggest making use of randomized transaction ordering within a block to mitigate centralization effects and to improve fairness in the Ethereum ecosystem. However, transactions and blocks are subject to gas limits and protocol rules. In a randomized transaction order, the behavior of transactions may change depending on other transactions in the same block, leading to invalid blocks and varying gas consumptions. In this paper, we quantify and characterize protocol violations, execution errors and deviations in gas consumption of blocks and transactions to examine technical deployability. For that, we permute and execute the transactions of over 335,000 Ethereum Mainnet blocks multiple times. About 22% of block permutations are invalid due to protocol violations caused by privately mined transactions or blocks close to their gas limit. Also, almost all transactions which show execution errors under permutation but not in the original order are privately mined transactions. Only 6% of transactions show deviations in gas consumption and 98% of block permutations deviate at most 10% from their original gas consumption. From a technical perspective, these results suggest that randomized transaction ordering may be feasible if transaction selection is handled carefully.