Menu

Subscribe

How to break on-chain exchanges

I don't believe in on-chain exchanges. They're like good jobs, or comfortable shoes. Wonderful at first, but always sour eventually. Every decentralized exchange has a breaking issue. For Etherdelta, there's miner frontrunning. To see the problem, we need to understand a bit more about Etherdelta, Solidity, and the EVM.

Etherdelta

Etherdelta is a pretty normal exchange. Users ("Makers") place orders. Orders sit on the orderbook. Other users ("Takers") fill orders from the book. You can find the code on their github.

Makers place orders using the order function (code here). They specify the tokens and amounts they want to trade. The hash of the order is recorded on chain, and an Order event is fired to log the details of the order. The order is referenced in the contract by its hash, and in function calls by its full details.

Takers find orders via the transaction logs. When a taker wants to fill an order, she calls the trade function (code here). She specifies the exact order she wants to trade against, by providing the full details of the order. She also specifies the amount of the order she'd like to fill.

Orders that are partially filled are recorded in the orderFills mapping, indexed by their user and hash. Trades, even partially filled ones, may be canceled by the user that placed them using the cancelOrder function (code here).

Transaction fees

Typically, the fee paid by a transaction is a function of the EVM instructions executed. Each instruction has a cost, in gas. The sum of the instruction costs is multiplied by the transaction's gas price to calculate the fee in Ether. The network enforces the refund of unused gas.

When the contract is called, it checks that the order has enough unfilled capacity. If it does not, the contract will throw. When the contract throws, the transaction fails. The failed transaction is included in the chain. When a transaction throws, all the gas is consumed rather than being refunded.

I'll repeat myself: all the gas is consumed. And when we say "consumed" we mean "paid to the miner of the transaction." This occurs whenever a contract throws, regardless of the work performed. Therefore, when a contract throws, the miner is guaranteed a transaction fee higher than she would receive if the transaction completed successfully. This provides a perverse incentive. Miners get more money when contracts error, so miners will try to make contracts throw.

The problematic code

Etherdelta's problem is in the trade function.

if (!(  
  (orders[user][hash] || ecrecover(sha3("\x19Ethereum Signed Message:\n32", hash),v,r,s) == user) &&
  block.number <= expires &&
  safeAdd(orderFills[user][hash], amount) <= amountGet
)) throw;

First, the smart contract checks that the order is valid. It checks that either the hash of the order is recorded in the orderbook, or the order is accompanied by the user's signature. Then it checks that the order has not expired, and that the order has enough capacity remaining to cover the incoming trade. If any of these conditions are not met, the function throws, and stops. The order is not filled, and the trade is not executed.

On the surface, this makes sense. The smart contract must enforce the rules of the exchange. All of these conditions are necessary to the function of the order book. However, it leaves incoming trades vulnerable to an attack by miners. Here's the problem:

safeAdd(orderFills[user][hash], amount) <= amountGet

Frontrunning to force throws

The miner of a block can always cause this condition to fail. She does this by inspecting incoming transactions for calls to the trade function. When she finds a trade transaction, she creates a new transaction that causes the in-flight transaction to overfill the standing order. Miners control transaction order in blocks, effectively do not pay transaction fees, and can ensure that their trade executes before the in-flight trade. In this way, the miner can guarantee the maximum transaction fee from the in-flight trade transaction.

For example:

  1. Alice places an order selling 5 indivisible tokens.
  2. Bob broadcasts a trade transaction to purchase 3 of those tokens.
  3. Eve, a miner, sees Bob's transaction, and creates her own transaction, which purchases 3 of those tokens.
  4. Eve does not broadcast her transaction.
  5. Eve orders transactions in her candidate blocks such that her transaction will execute before Bob's.
  6. Eve mines as normal
  7. If Eve does not find a block before Bob's transaction confirms, Bob purchases 3 tokens, and Eve discards her transaction.
  8. If Eve finds a block before Bob's transaction confirms, Eve purchases 3 tokens.
  9. If Eve purchased tokens, Bob's transaction throws, and Eve takes all of Bob's gas.

The net effect is that Eve can acquire tokens on the Etherdelta exchange below the current market price in every block that she mines. By purchasing tokens, Eve improves the expected value of mining Bob's transactions. Therefore, her purchase of tokens is subsidized by the additional fee that Bob pays when his transaction throws. Eve also saves any computation she would have spent making the state transitions associated with Bob's transaction.

If Eve maintains tokens in an exchange account at a centralized exchange, she can treat this as a risk-free, semi-permanent arbitrage opportunity. She always acquires tokens below market price, no matter what that price is, and thus can always profit at Bob's expense.

Mitigations aren't enough

The throw keyword will be deprecated in future versions of Solidity. Its replacement, revert(), will undo state changes made by its caller, bubble up an error, and refund unused gas. Refunding gas is a pretty good mitigation, but doesn't fully address the problem. Eve can still use her privileged position as a miner to trade more efficiently on the Etherdelta market than others.

Eve, in effect, gets advance information. She gets the first opportunity to fill new orders, and limited control over market movements. Even when not trading on the exchange, she gets to order transactions to maximize the number of throws and revert()s and thus maximize her transaction fees. Anywhere that she can cause a contract to predictably error, she should. Anywhere she can affect the latest market price by reordering transactions, she should. Anywhere she can arbitrage manual orders, she should.

Broken by default

To put it bluntly: Miners and pool operators can tax users of Etherdelta. They can extract value from the Etherdelta ecosystem by manipulating the order and outcome of the underlying transactions. In the long run, once other optimization channels are exhausted, miners will pursue attacks like this. Users of vulnerable systems will suffer.

There is no negative consequence to the miner. There's no minimum hashpower to execute these attacks. The attacks are easy to implement. Most pooled miners see only block headers, so pool operators can perform these attacks without the knowledge of the pool members. It is difficult to distinguish these attacks from normal operation of the exchange. Miners get free money.

There is no known model for an on-chain order book that is not vulnerable to a variation of these attacks. On-chain exchanges are broken by default.

For more info on these types of attacks, and discussion of some of the tradeoffs, read: The Cost of Decentalization by Hacking Distributed.