(This is an update on my Ethereum Protocol Fellowship. More updates can be found here ).


Extracting value from Uniswap transactions

In this post, I will outline a way in which the equilibrium analysis from the Open Game engine can be used to come up with profitable strategies for a block proposer on the Ethereum blockchain, either by re-ordering the transactions in the block, or by inserting their own. I will consider two sources of MEV here, inspired by the Clockwork Finance paper. First, I will consider transactions to a Uniswap-like exchange, that exchanges two tokens according to the constant product rule. By ordering such transactions, the block proposer can profitably manipulate the price of the tokens. Second, such price manipulation can be made even more profitable by placing a bet on the exchange rate offered by the Uniswap contract. To be able to analyse both these scenarios, I will model a blockchain with just two player accounts, $p_0$ and $p_1$, and two contract accounts: Uniswap and Bet. Most of the complexity will be captured in Haskell functions, and the Open Game engine is only used to search for profitable strategies for the block proposer $p_0$.


Let’s first define some useful data types. I assume there exist only two tokens: A and B, both of which can be held in fractional amounts. An Account has an integer AccountID, and can hold amounts of both tokens. A transaction Tx specifies a sender and receiver ID, and how much of which token is sent. A block is simply modelled as a list of transactions:


data Token = A | B
  deriving (Eq,Ord,Show)
type TokenAmount = Double
type AccountID = Int

-- ID, amount A, amount B
type Account = (AccountID, TokenAmount, TokenAmount)

type AccountStates = [Account]

-- Sender, Receiver, Token, Amount
-- Should this also have a data field?
type Tx = (AccountID, AccountID, Token, TokenAmount)

type TxBlock = [Tx]


Let’s further define useful functions to find the recipient of a transaction and to set and get an account’s balance:


getReceiver :: Tx -> AccountID
getReceiver (_,receiver, _, _) = receiver

balance :: Account -> Token -> TokenAmount
balance (userID, amountA, amountB) token
    | token==A = amountA
    | otherwise =  amountB

updateAccount :: Account -> Token -> TokenAmount -> Account
updateAccount (acID, bA, bB) token amount
   | token == A = (acID, bA + amount, bB)
   | otherwise = (acID, bA, bB + amount)


A call to the Uniswap contract is a map from the current state and a transaction to a new state. To generate the new state from the old one, I use a lens on the list, imported from Control.Lens. When a user has insufficient funds, they are charged a small (gas) fee.


uniSwapExchange :: AccountStates -> Tx -> AccountStates
-- Old state -> transaction -> new state
-- Use lenses to 'modify' account states
-- If the user does not have sufficient funds, fine the user (a gas fee?) propagate the old state
uniSwapExchange accountStates (userID, uniSwapID, token, tokenAmount)
   | userbalanceInsufficient = accountStates & (ix userID) .~ userFined
   | otherwise = accountStates & (ix userID) .~ userUpdate & (ix uniSwapID) .~ uniswapUpdate
  where
   user_bal = balance (accountStates!!userID)
   userbalanceInsufficient = user_bal token < tokenAmount
   userFined = 
      if token ==A
      then (userID, minimum [0, user_bal A - 0.1] , user_bal B)
      else (userID, user_bal A ,  minimum [0, user_bal B - 0.1])
   uniSwap_bal = balance (accountStates!!uniSwapID)
   dA = uniSwap_bal A * tokenAmount / (uniSwap_bal B + tokenAmount) 
   dB = uniSwap_bal B * tokenAmount / (uniSwap_bal A + tokenAmount) 
   userUpdate = 
      if token == A
      then (userID, user_bal A - tokenAmount, user_bal B + dB)
      else (userID, user_bal A + dA, user_bal B - tokenAmount)
   uniswapUpdate = 
      if token == A
      then (uniSwapID, uniSwap_bal A + tokenAmount, uniSwap_bal B - dB)
      else (uniSwapID, uniSwap_bal A - dA, uniSwap_bal B + tokenAmount)


Similarly, a call to the Bet contract transforms an old state into a new one, but it also needs an AccountID that specifies which contract should be used as a price oracle. It further needs the price that would trigger a win for the better. Crucially, both of these are a property of the contract, and not set by the transaction that actually places a bet of a certain amount. I’ve implemented it so that when the user wins a bet in token T, they receive the full T-balance of the betting contract.


betOnExchange :: AccountStates -> AccountID -> Double -> Tx -> AccountStates
-- Old state, price oracle, bet threshold, bet amount, new state
-- Use lenses to 'modify' account states
betOnExchange accountStates oracleID ratio (userID, betID, betToken, betAmount)
   | (userbalanceInsufficient || betAmount<0) = accountStates & (ix userID) .~ userFined
   | ((uniSwap_bal A)/(uniSwap_bal B) >= ratio) = accountStates & (ix userID) .~ userUpdate_userWin & (ix betID) .~ betUpdate_userWin
   | ((uniSwap_bal A)/(uniSwap_bal B) <  ratio) = accountStates & (ix userID) .~ userUpdate_userLose & (ix betID) .~ betUpdate_userLose
  where
   uniSwap_bal = balance (accountStates!!oracleID)
   bet_bal = balance (accountStates!!betID)
   user_bal = balance (accountStates!!userID)
   userbalanceInsufficient = user_bal betToken < betAmount
   userFined = 
      if betToken ==A
      then (userID, minimum [0, user_bal A - 0.1] , user_bal B)
      else (userID, user_bal A ,  minimum [0, user_bal B - 0.1])
   -- The prize is either the amount bet, or the remaining balance if that is less
   prize = minimum [betAmount, balance (accountStates!!betID) betToken]
   userUpdate_userWin = updateAccount (accountStates!!userID) betToken prize
   betUpdate_userWin =  updateAccount (accountStates!!betID) betToken (-prize)
   userUpdate_userLose = updateAccount (accountStates!!userID) betToken (-prize)
   betUpdate_userLose = updateAccount (accountStates!!betID) betToken betAmount


That is all the needed contract complexity. The only thing needed now is to initialise the accounts and make sure the right internal code gets triggered when a transaction is made to a contract account (in fact, I will only worry about contract-calling transactions here). Let’s initialise the accounts of two players and the two contracts with the following balances:


p0_ac = (0, 10, 10)
p1_ac = (1, 10, 10)
uniswap_ac = (2, 100, 100)
bet_ac = (3, 100, 100)

initAccounts :: AccountStates
initAccounts = [p0_ac, p1_ac, uniswap_ac, bet_ac]


I will interpret $p_0$ as the block proposer. Since, in this limited example, $p_0$ does not actually care who makes the other contract calls, one other player, $p_1$, should be sufficient. I then specify how each contract call should be executed, specifying the account with index 2 (the Uniswap account) as the price oracle for the betting contract, and setting the winning threshold at a token ratio of 1.1.


executeTx :: AccountStates -> Tx -> AccountStates
executeTx states tx
   | getReceiver tx == 2 = uniSwapExchange states tx
   | getReceiver tx == 3 = betOnExchange states 2 1.1 tx
   | otherwise = states


Executing a whole block of transactions is then simply a foldl of executing each transaction, since the accounts get updated each time:


executeBlock :: AccountStates -> TxBlock -> AccountStates
executeBlock accountStates_init block = foldl executeTx accountStates_init block


There are many definitions of MEV, and people still disagree on the right definition. Here, I will simply choose Token A as the relevant holder of value (also called the numéraire), so the final A balance determines the payoff, which is equal to the MEV:


blockPayoff :: AccountStates -> TxBlock -> AccountID -> Payoff
-- Old state, block, payoff for user "userID"
blockPayoff initStates block userID = newBalance - oldBalance
  where
   newBalance = balance ((executeBlock initStates block)!!userID) A
   oldBalance = balance (initStates!!userID) A


To analyse the extractable value by the proposer $p_0$, let’s imagine a mempool with transactions in which both players exchange tokens A and B in both directions.


tx1 = (getAccountID p0_ac, getAccountID uniswap_ac, A, 2.0)
tx2 = (getAccountID p1_ac, getAccountID uniswap_ac, A, 3.0)
tx3 = (getAccountID p0_ac, getAccountID uniswap_ac, B, 2.0)
tx4 = (getAccountID p1_ac, getAccountID uniswap_ac, B, 3.0)

block1 :: TxBlock
block1 = [tx1, tx2, tx3, tx4]


The strategy of the proposer is simply a choice of an ordering of these four transactions, which can be implemented as the (trivial) open game as follows:


txOrderingGame  = [opengame|
   inputs    :      ;
   feedback  :      ;

   :----------------------------:
   inputs    :      ;
   feedback  :      ;
   operation : dependentDecision "proposer" (const actionSpace);
   outputs   : ordering ;
   returns   : blockPayoff initAccounts (blockPerm ordering) 0     ;
   :----------------------------:

   outputs   :      ;
   returns   :      ;
  |]
  where
   actionSpace = [0..(product [1..4]-1)]
   blockPerm = \x -> ((permutations block1)!!x)

analyseTxOrderingGame strat = generateIsEq $ evaluate txOrderingGame strat void


What if the proposer decides to put their interactions first, i.e. order the block as [tx1, tx3, tx2, tx4]? This corresponds to the fifth permutation, so can be analysed as follows:


λ: analyseTxOrderingGame $ choosePerm 5

----Analytics begin----
 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 1
Current Strategy: fromFreqs [(5,1.0)]
Optimal Payoff: 0.15964740450538706
Current Payoff: 0.03920031360250853
 --other game-- 
 --No more information--
 NEWGAME: 
----Analytics end----


It can be seen that there is a bit of ‘profit’ using this ordering, though not a lot. Using the first permutation, i.e. [tx2, tx1, tx3, tx4], yields more than four times as much profit. This is because if both players first exchange A to B, then the price of A decreases, which means you get more A for your B, and so changing 2 B for A with tx3 leaves the proposer with more A in total. This means that even though the engine suggests 1 as the optimal permutation, the identity permutation with index 0 should also be optimal, which indeed it is:


λ: analyseTxOrderingGame $ choosePerm 0

----Analytics begin----
 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


In fact, permutation 0 might be considered slightly better because it leaves the proposer (indexed with !!0) with slightly more B:


λ: (executeBlock initAccounts [tx2, tx1, tx3, tx4])!!0
(0,10.159647404505387,9.849283402681461)
λ: (executeBlock initAccounts [tx1, tx2, tx3, tx4])!!0
(0,10.159647404505387,9.96078431372549)


However, since B is deemed irrelevant for the total MEV, this is not considered a profitable deviation.


Betting on Uniswap as a price oracle

Now consider the possible insertion of a transaction to the betting account. I will make this transaction a function that bets a certain amount, so that


blockWithbet :: TokenAmount -> TxBlock
blockWithbet amount = [tx1, tx2, tx3, txBet amount]


Letting the player bet multiples of 0.1 of a full token, the full game simply becomes the composition of two choices: what to bet, and how to order, as follows



txOrderingGame_withBet  = [opengame|
   inputs    :      ;
   feedback  :      ;

   :----------------------------:

   inputs    :      ;
   feedback  :      ;
   operation : dependentDecision "proposer" (const betAmounts);
   outputs   : betAmount ;
   returns   :  0   ;

   inputs    :      ;
   feedback  :      ;
   operation : dependentDecision "proposer" (const actionSpace);
   outputs   : ordering ;
   returns   : blockPayoff initAccounts (blockPerm ordering betAmount) 0  ;
   :----------------------------:

   outputs   :      ;
   returns   :      ;
  |]
  where
   betAmounts = [0,0.1..(balance (initAccounts!!0) A)]
   actionSpace = [0..(product [1..4]-1)]
   blockPerm = \orderChoice betAmount -> ((permutations $ blockWithbet betAmount)!!orderChoice)


which then also requires two separate strategies:


betAndOrderStrat :: Double -> Int -> List '[Kleisli Stochastic () Double,
   Kleisli Stochastic () Int]
betAndOrderStrat amount orderChoice = Kleisli (\x -> playDeterministically amount) ::- Kleisli (\x -> playDeterministically orderChoice) ::- Nil

analyseTxOrderingGame_withBet strat = generateIsEq $ evaluate txOrderingGame_withBet strat void


To analyse this game, let’s first consider the strategy of betting 4A, and not doing any reordering:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 4 0

----Analytics begin----
 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 0.0
Current Strategy: fromFreqs [(4.0,1.0)]
Optimal Payoff: 0.15964740450538706
Current Payoff: -3.840352595494613
 --other game-- 
 --No more information--
 NEWGAME: 

 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 17
Current Strategy: fromFreqs [(0,1.0)]
Optimal Payoff: 4.159647404505387
Current Payoff: -3.840352595494613
 --other game-- 
 --No more information--
 NEWGAME: 
----Analytics end----


The engine reports two profitable deviations: first of all, the proposer is better off not betting at all, since they don’t win with this reordering anyway. Second, there is a more profitable ordering, the permutation indexed by 17, which corresponds to [tx2, tx1, txBet, tx3]. Following both these suggestions: no betting and reordering, leads to the following:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 0 17

----Analytics begin----
 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 8.0
Current Strategy: fromFreqs [(0.0,1.0)]
Optimal Payoff: 8.159647404505385
Current Payoff: 0.15964740450538706
 --other game-- 
 --No more information--
 NEWGAME: 

 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


That is, the engine recognises that with this ordering, not only does the proposer extract the same reordering MEV as before, they can now also insert their own bet in the middle, and can profit maximally by betting everything they still have:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 8 17

----Analytics begin----
 Strategies are in equilibrium
 NEWGAME: 

 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


One advantage of this approach is that it makes clear that MEV not only depends on the transactions in the mempool, but also on the internal states of the contracts. When betting 4A in the current setup, it is even more profitable to bet 8A:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 4 14

----Analytics begin----
 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 8.0
Current Strategy: fromFreqs [(4.0,1.0)]
Optimal Payoff: 8.159647404505385
Current Payoff: 4.159647404505387
 --other game-- 
 --No more information--
 NEWGAME: 

 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


However, when the Uniswap contract is initialised as having 1000 of each token, rather than 100, then there is no longer enough liquidity in the mempool to manipulate the price of A enough to win the bet, so the 8.16A of MEV all but disappears, and the most profitable strategy is to not bet at all:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 4 14

----Analytics begin----
 Strategies are NOT in equilibrium. Consider the following profitable deviations: 

Player: proposer
Optimal Move: 0.0
Current Strategy: fromFreqs [(4.0,1.0)]
Optimal Payoff: 1.599784433289031e-2
Current Payoff: -3.984002155667109
 --other game-- 
 --No more information--
 NEWGAME: 

 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


Conclusion

It is satisfying to see MEV directly as the payoff of this block proposer game. However, it is a bit unfortunate that all compositional structure of the transaction execution is hidden in the foldl application, rather than explicit composition of Open Games. A logical next step would be to implement something similar, but model each contract call as an open game (potentially just a lifted function), so that player strategies and contract calls can be represented at the same level. Furthermore, because the betting and ordering are currently two different games, the engine cannot always identify a deviation of both strategies that is only jointly profitable. For example, it considers not betting and not reordering an equilibrium:


λ: analyseTxOrderingGame_withBet $ betAndOrderStrat 0 0

----Analytics begin----
 Strategies are in equilibrium
 NEWGAME: 

 Strategies are in equilibrium
 NEWGAME: 
----Analytics end----


Indeed, when not betting at all, the 0th permutation yields all possible MEV. However, there are better global deviations, as can be seen by comparing the final A balance of the proposer under either the ‘don’t bet don’t reorder’ strategy


λ: (executeBlock initAccounts $ (permutations $ blockWithbet 0)!!0)!!0
-- (ID, A balance, B balance)
(0,10.159647404505387,9.96078431372549)


with a bolder ‘bet 8 and choose ordering 17’ strategy


λ: (executeBlock initAccounts $ (permutations $ blockWithbet 8)!!17)!!0
-- (ID, A balance, B balance)
(0,18.159647404505385,9.849283402681461)


This shows that there is a total MEV of 8A, not found by the Open Game engine as a profitable deviation using this setup. This means that a different representation of this game might be better.

Another problem with this approach is that is does not scale well. Since the payoff of each ordering has to be calculated separately, the time complexity scales factorially in the number of transactions per block. Analysing a block with 7 Uniswap transactions and 1 Bet transaction already took around 45 seconds on my laptop. It perhaps makes more sense to come up with a set of reasonable strategies to shrink the action space to a more manageable size.