Ethereum Has Issues

I first wrote about the problem of bots front-running transactions a year and a half ago in The Order Flow, citing Dan Robinson and Georgios Konstantopoulos' Ethereum is a Dark Forest from August 2020 and samczsun's Escaping the Dark Forest. But I should have paid more attention. It turns out that front-running is the tip of an iceberg of fundamental problems that Ethereum and similar systems suffer. In replicating the functions of Wall Street they have replicated, and in some ways enhanced, its pathologies, Below the fold I survey these and related issues.

Daian et al

The reason I should have paid more attention was that I failed to follow Dan Robinson and Georgios Konstantopoulos' link to Philip Daian et al's Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability (also here) from 3 months earlier. This seminal paper introduced the concept of Miner Extractable Value (MEV) and the various ways it could be extracted. Their abstract reads:

Blockchains, and specifically smart contracts, have promised to create fair and transparent trading ecosystems.

Unfortunately, we show that this promise has not been met. We document and quantify the widespread and rising deployment of arbitrage bots in blockchain systems, specifically in decentralized exchanges (or “DEXes”). Like high-frequency traders on Wall Street, these bots exploit inefficiencies in DEXes, paying high transaction fees and optimizing network latency to frontrun, i.e., anticipate and exploit, ordinary users’ DEX trades.

We study the breadth of DEX arbitrage bots in a subset of transactions that yield quantifiable revenue to these bots. We also study bots’ profit-making strategies, with a focus on blockchain specific elements. We observe bots engage in what we call priority gas auctions (PGAs), competitively bidding up transaction fees in order to obtain priority ordering, i.e., early block position and execution, for their transactions. PGAs present an interesting and complex new continuous-time, partial-information, gametheoretic model that we formalize and study. We release an interactive web portal, frontrun.me, to provide the community with real-time data on PGAs.

We additionally show that high fees paid for priority transaction ordering poses a systemic risk to consensus-layer security. We explain that such fees are just one form of a general phenomenon in DEXes and beyond—what we call miner extractable value (MEV)—that poses concrete, measurable, consensus-layer security risks. We show empirically that MEV poses a realistic threat to Ethereum today.

Our work highlights the large, complex risks created by transaction-ordering dependencies in smart contracts and the ways in which traditional forms of financial-market exploitation are adapting to and penetrating blockchain economies

Their starting point was the observation that Ethereum "smart contract" execution is order-dependent within a block, unlike transaction execution in Bitcoin and similar systems:

First, they identify a concrete difference between the consensus-layer security model required for blockchain protocols securing simple payments and those securing smart contracts. In a payment system such as Bitcoin, all independent transactions in a block can be seen as executing atomically, making ordering generally unprofitable to manipulate. Our work shows that analyses of Bitcoin miner economics fail to extend to smart contract systems like Ethereum, and may even require modification once second-layer smart contract systems that depend on Bitcoin miners go live [23].

The reason that bots engage in PGAs is that they can extract value despite paying for "Order Optimization" (OO) by front-running other transactions in the block:

Second, our analysis of PGA games underscores that protocol details (such as miner selection criteria, P2P network composition, and more) can directly impact application-layer security and the fairness properties that smart contracts offer users. Smart contract security is often studied purely at the application layer, abstracting away low-level details like miner selection and P2P relayers’ behavior in order to make analysis tractable .... Our work shows that serious blind spots result. Low-level protocol behaviors pose fundamental challenges to developing robust smart contracts that protect users against exploitation by profit-maximizing miners and P2P relayers that may game contracts to subsidize attacks.

Thie led to the discovery that:

OO fees represent one case of a more general quantifiable value we call miner-extractable value (MEV). MEV refers to the total amount of Ether miners can extract from manipulation of transactions within a given timeframe, which may include multiple blocks’ worth of transactions. In systems with high MEV, the profit available from optimizing for MEV extraction can subsidize forking attacks of two different forms. The first is a previously shown undercutting attack [11] that forks a block with significant MEV. The second is a novel attack, called a time-bandit attack, that forks the blockchain retroactively based on past MEV.

Source

Their discovery was important, first because:

Undercutting attacks were previously considered a risk primarily in the distant future, when block rewards in Bitcoin are expected diminish below transaction fees. By measuring the significance and magnitude of OO fees, our work shows that undercutting attacks are a present threat.
...
Our study shows that OO fees are a form of value that sometimes dominates explicit transaction fees today. The tail of our OO fee distribution, including all of the example blocks in Figure 11 represent such opportunities. In other words, undercutting attacks represent a present threat in Ethereum, and one that will grow with the success of smart contracts that attract OO fees.

And second because:

Time-bandit attacks are also a present and even larger threat. They can leverage not just OO fees, but any forms of miner-extractable value obtained by rewinding a blockchain. Time-bandit attacks’ existence implies that DEXes and many other contracts are inherent threats to the stability of PoW blockchains, and the larger they grow, the bigger the threat.
...
Of course, a time-bandit attack relies on real-time access to massive mining resources. As noted in [5], however, "rental attacks" are feasible using cloud resources, particularly for systems such as Ethereum that rely heavily on GPUs, which are standard cloud commodities. Sites such as http://crypto51.app/ estimate the costs.
...
We posit that the OO fees alone that we have described threaten the security of today’s Ethereum network. As Figure 11 shows, blocks with high OO fees and/or arbitrage opportunities can already enable such attacks.

More generally and alarmingly, time-bandit attacks can be subsidized by a malicious miner’s ability to rewrite profitable trades retroactively, stealing profits from arbitrageurs and users while still claiming gas fees on failed transactions that attempt execution. The resulting MEV is potentially massive, suggesting a possibly serious threat in Ethereum today.

They illustrate the threat with a simplified hypothetical example:

Consider a price spike from 1 USD to 3 USD in a token that trades on an on-chain automated market maker ... A miner performing a time-bandit attack can now rewrite history such that it is on the buy side of every trade, accruing a substantial balance in such a token at below market rate—before the price spike.7

For example, if the attacker wishes to rewrite 24 hours of history, and 1M USD of volume occurred in exchanges with rewritable history in that token, then the attacker can obtain a MEV gross profit of 1 M × (3 USD - 1 USD) = 2M USD.8

At the time of writing (March 2019), http://crypto51.app/ estimates a 24-hour 51% rental-attack cost on Ethereum of about 1.78M USD, implying a net profit of around 220K USD.

This is an important paper worthy of detailed study.

Piet et al

Now it is two years later and in Extracting Godl [sic] from the Salt Mines: Ethereum Miners Extracting Value Julien Piet, Jaiden Fairoze and Nicholas Weaver reveal how the pathologies identified by Daian et al have become endemic in Ethereum's ecosystem:

In this work, we develop an algorithm to detect MEV exploitation present in previously mined blocks. We use our implementation of the detector to analyze MEV usage and profit redistribution, finding that miners make the lion's share of the profits, rather than independent users of the private relays. More specifically, (i) 73% of private transactions hide trading activity or re-distribute miner rewards, and 87.6% of MEV collection is accomplished with privately submitted transactions, (ii) our algorithm finds more than $6M worth of MEV profit in a period of 12 days, two thirds of which go directly to miners, and (iii) MEV represents 9.2% of miners' profit from transaction fees.

Furthermore, in those 12 days, we also identify four blocks that contain enough MEV profits to make time-bandit forking attacks economically viable for large miners, undermining the security and stability of Ethereum as a whole.

Both Robinson and Konstantopoulos and samczsun stress the importance of avoiding the public mempool, and so do Piet et al:

To avoid detection by bots, users can opt to send transaction data directly to miners, bypassing the public memory pool entirely. This method would also be useful for bots seeking to avoid competition with other bots. Transacting directly requires having a private communication channel with a miner, something most users do not have. Flashbots Auctions [6] pioneered such a service to enable private MEV extraction, creating a private link between a user or bot and a participating miner. The authors claim Flashbots removes the burden of MEV extraction traffic from the public memory pool and mitigates MEV’s negative externalities, allowing for fair access to MEV opportunities.

Since eliminating MEV was out of the question, Daian and colleagues attempted to mitigate the problem by setting up Flashbots:

a research and development organization working on mitigating the negative externalities of Maximal Extractable Value (MEV) extraction techniques and avoiding the existential risks MEV could cause to stateful blockchains like Ethereum. Our primary focus is to enable a permissionless, transparent, and fair ecosystem for MEV extraction. This falls under three goals: Bringing Transparency to MEV Activity, Democratizing Access to MEV Revenue and Enabling Fair Redistribution of MEV Revenue.

They developed and deployed Flashbot Auction:

a permissionless, transparent, and fair ecosystem for efficient MEV extraction and frontrunning protection which preserves the ideals of Ethereum. Flashbots Auction provides a private communication channel between Ethereum users and miners for efficiently communicating preferred transaction order within a block.

Alas, it didn't turn out quite as hoped.

Piet et al explain their methodology thus:

In order to study historical MEV extraction through private transactions, we implement a custom Ethereum node that captures transaction-related data in real-time and checks every transaction against the memory pool before tagging it as private. Previously, MEV detection used point-wise heuristics on historical data or graph methods to find arbitrages in decentralized exchanges (DEXs). We develop a generic arbitrage detection technique that, to the best of our knowledge, is the first method to identify generic MEV opportunities in historical data. By finding specific cycles in cryptocurrency transfer graphs across blocks, our algorithm can detect arbitrage, backrunning, and frontrunning, even across multiple transactions.

They summarize their findings in three areas:

• Private transaction analysis.

  Private transaction usage is inconsistent across miners. Most private transactions are used for miner profit redistribution, and more importantly, MEV exploitation. In fact, in our data, over 85% of MEV is extracted using private transactions. Flashbots accounts for under 50% of private transactions—the rest are either owned by the miner or submitted through covert channels.

• Miner profit analysis.

  Despite Flashbots’ claim to a fair MEV opportunity redistribution, miners dominate the market: they make up two thirds of all MEV-related profits, and most likely control many bots themselves. In our data, this represents on average 9.2% of their total transaction fee income and 22.7% of their income from decentralized finance applications. As for private transactions, MEV extraction is inconsistent among miners—the top five miners earn more from MEV than all bots combined, but 40% of miners do not partake in MEV extraction.

• Concrete time-bandit attack opportunities.

  Previous work has warned of the risk for time-bandit attacks if MEV profits were to rise, where major miners are incentivized not to add new transactions but instead, attempt to rewrite old history to capture the present MEV for themselves. Some even found hypothetical opportunities that would have yielded enough profit to warrant an attack. Using game-theoretic models developed in [15], we found four blocks in 12 days that earned enough to warrant an attack from miners with a hash rate superior to 10%.

The 10% number is concerning. Piet et al's source is reference 35, On the Just-In-Time Discovery of Profit-Generating Transactions in DeFi Protocols by Liyi Zhou et al (also here). They cite it thus:

In fact, [35] used a Markov Decision Process to model this probability. They found that with the current stale block rate, miners with a hash rate greater than 10% of the total Ethereum hash rate had positive profit expectation if they produced more than four times the block reward. In our data, we found two miners with a hash rate greater than 10%: Ethermine at 35%, and F2Pool at 14%. Both these miners have a history of profiting from MEV opportunities. Ethermine made 190 ETH in a week in our data, representing 3.8% of its profits from gas, and F2Pool made 300 ETH, or 13.6% or its profits from gas.

We found two blocks in our 12 day span, 14,217,123 and 14,241,282, for which miner profits from MEV exceeded four times the block reward. The block reward here is the sum of the static block reward (2 ETH) and the fees from all non-MEV transactions. Forking these blocks would have simply required mining them without changing their content, since the miner fees from MEV alone exceeded four block rewards. Furthermore, we found four blocks for which the total MEV profit (not simply the part shared with the miner) exceeded four block rewards. These could have been forked as well, with the additional constraint of replacing MEV transactions with the miner’s own transactions. We did not find traces of fork attacks in our data; however, it is only a matter of time before they start happening, since there are multiple opportunities for forking every week. This represents an existential threat to the stability of Ethereum, and to the trust users hold in its potential.

Two years after it was identified, Piet et al conclude that MEV:

presents serious risks to the stability of the blockchain. On average, one block every week contains enough MEV profit in transfer fees alone to make a time-bandit attack economically viable for miners with a hash rate above 10%. The top two miners, Ethermine and F2Pool, both have a hash rate above 10% and have a history of exploiting MEV. In particular, F2Pool is the largest single entity in terms of MEV profits, making 300 ETH of profit in 12 days, which accounts for 13.6% of its total transaction profit.

Today’s MEV mitigation solutions are not sufficient to address the issue. We believe a random transaction ordering system could potentially make MEV extraction prohibitively hard, however this remains to be investigated. Without a proper solution, Ethereum remains an impractical blockchain for real-world use. Regular Ethereum users will continue to pay high gas fees because of bots, lose money to MEV schemes when trading tokens, and most importantly, face the risk of time-bandit attacks.

Source

This is in addition to the long-standing concentration of Ethereum mining power, with normally three and sometimes only two mining pools controlling over 50% of the mining power. (The screengrab shows that on 7^th November 2021 the top two pools controlled 53.9%). This is not a safe basis for the vast financial bubbles that have been erected above the Ethereum blockchain. The extreme Gini coefficients of cryptocurrencies mean that Ethereum's eventual transition to Proof-of-Stake fixes none of these problems. As Piet et al point out:

Part of the reason MEV exploitation is rampant today is due to the centralization of mining power by a handful of miners: the top three mining pools hold over 50% of the hash rate. Centralization helps coordinate MEV extraction through private relays such as Flashbots. In this regard, proof-of-stake still concentrates validation powers in the hands of a few. Although it has a longer tail of validators, as of today, the top two staking pools hold over 50% of all stake, concentrating power in the hands of even fewer addresses.

There is much fascinating detail in Piet et al's paper, it will repay careful reading.

DataFinnovation

Now I turn to another aspect of the eventual Ethereum 2.0 system.

Why are transaction fees high enough to motivate all the shenanigans? In conventional systems fees are typically fixed, either flat or a percentage of transaction value. Because Ethereum transactions are programs, the halting problem means that it isn't possible to accurately predict the resources needed to execute them. This rules out flat or percentage of value fees, and requires transactions to set a limit on how much they are willing to spend on execution. The result is that when the fixed supply of transactions meets variable demand, transaction prices vary dramatically. High and variable fees have been an ongoing problem for Ethereum, leading to:

• Fiascos like the one Molly White documents in Collectors spend a cumulative $26 million on gas fees alone for "VaynerSports" NFT project—3× the amount made from the NFTs:
  

  Once the mint was over, 2411 ETH ($8.2 million) had been spent on mints, and 7652 ETH ($26.4 million) had been spent on gas fees. Some users lost thousands of dollars in gas fees on failed transactions.

• Attempts to move the bulk of transactions off-chain via, for example, bridges.
• The long-term effort to implement "sharding" in Ethereum 2.0, which in effect parallelizes the operation of the blockchain.

David Gerard writes:

To some extent, the Ethereum project has just given up on scaling the main blockchain. “For Ethereum to scale and keep up with demand, it has required rollups” — do the work somewhere else and send back the result. The blockchain is only usable if you work around actually using it. [ethereum.org]"

Now, David Gerard reports on a post from DataFinnovation entitled The Consequences of Scalable Blockchains which shows that there is very likely a fundamental problem with attempting to greatly increase the supply of transactions and thereby mitigate the problem of high fees.

What the DataFinnovation post shows is that implementing an Ethereum-like system whose performance in all cases is guaranteed to be faster than any single node in the network is equivalent to solving the great unsolved problem in the theory of computation, nicknamed P vs. NP:

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".

An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

Suppose P = NP, what could happen?:

An example of a field that could be upended by a solution showing P = NP is cryptography, which relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:

• Existing implementations of public-key cryptography, a foundation for many modern security applications such as secure financial transactions over the Internet.
• Symmetric ciphers such as AES or 3DES, used for the encryption of communications data.
• Cryptographic hashing, which underlies blockchain cryptocurrencies such as Bitcoin, and is used to authenticate software updates. For these applications, the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P = NP, then finding a pre-image M can be done in polynomial time, through reduction to SAT.

The DataFinnovation post shows that the problem of implementing an Ethereum-like system whose performance in all cases is guaranteed to be faster than any single node in the network can be reduced to 3-SAT, which is a canonical problem in class NP. They write:

What we are going to do here is pretty simple:

1. Describe some thing a scalable blockchain could do.
2. Prove that thing is NP-Complete.
3. Show how, if you have such a blockchain, you can right now break hash functions and public-key cryptography and constructively prove P=NP.

...
We are going to call something “scalable” when it can process more transactions per unit time than a single node on the network. If you always need to wait for some designated leader/verifier/miner/whatever to finalize transactions then you’re never going to run faster, in the worst-case, than that node.

This sounds bad, and it is, but there are some caveats:

• We don't know that P ≠ NP, we just strongly suspect that P ≠ NP. On the other hand, if P = NP, cryptocurrencies have a much bigger problem than scaling Ethereum.
• It might be the case that P = NP but there are no constructive, efficient algorithms based on the proof. But DataFinnovation show how a blockchain that met their criteria for scalability would be such a constructive algorithm.
• Their criterion for scalability is strong; it requires that the blockchain be faster in the worst case. A blockchain might be faster in the normal case, but slower in a rare worst-case.

Fees spike because demand for transactions exceeds supply. The worst case might be only a small fraction of the possible cases, but blockchains run in a adversarial environment, and the worst case is likely the result of an attack. Consider, for example, the possibility of a sudden drop in the "price" of ETH which causes a spike in demand for transactions which causes a spike in fees. Now an attacker causes the worst case to occur, which results in a sudden decrease in the supply of transactions, which causes fees to increase further, which causes panic and a further increase in demand for transactions. Thus it appears that any approach to "scalability" of this kind likely contains a built-in vulnerability.

There are comments from the Ethereum community here.