ProtoRev
Abstract
ProtoRev is a module that:
- Runs during the Posthandler (core trading execution) and Epoch Hook (keeper store updating)
- In the posthandler of a tx, checks if that tx swaps (has SwapExactAmountIn or SwapExactAmountOut as Msgs)
- If a tx swaps, generates routes related to the pool swapped against that may contain cyclic arbitrage opportunities after the user’s swap
- For each route, determines the optimal amount of the asset to swap in that results in maximum amount of the same asset out (profit)
- Compares profits and selects the route that generates the most profit and is greater than 0
- Mints the optimal amount of asset to swap in from the Bank module (as determined previously)
- Executes the MultiHopSwapExactAmountIn with the optimal input amount for the route
- Burns the same amount of asset previously minted to execute the swap
- Redistributes the profit captured back to the Osmosis ecosystem based on Governance.
For the conceptual overview, see ProtoRev in the Learn section.
Concepts
Cyclic Arbitrage
Cyclic arbitrage is a series of swaps that results in more of the same asset that was initially swapped in. An example of this is as follows:
Assume there exist three pools with the following asset pairs:
1. A/B
2. B/C
3. C/A
A user executes a multi-hop swap that swaps between pools 1, 2, and 3 with the following outcome (user inputs 10A into pool 1, and receives 15A from pool 3):
User -> 10A -> Pool 1 -> 5B -> Pool 2 -> 20C -> Pool 3 -> 15A -> User
This series of swaps is known as a cyclic swap because it starts and ends in the same asset. A cyclic swap is known as a cyclic arbitrage swap when the output amount is greater than the input amount, for the same asset.
Cyclic Arbitrage Route
A Cyclic Arbitrage Route describes an ordered set of pools that need to be swapped through in consecutive order to capture a cyclic arbitrage opportunity. A Cyclic Route can be determined without knowing current reserve ratios of pools by assessing if one can swap in an asset into the series of pools and receive the same asset out.
So for the same pools as the example above, an exhaustive list of Cyclic Routes are as follows:
1. A/B
2. B/C
3. C/A
(1,2,3) # Asset A in, Asset A Out
(3,2,1) # Asset A in, Asset A Out
(3,1,2) # Asset C in, Asset C Out
(2,1,3) # Asset C in, Asset C Out
(2,3,1) # Asset B in, Asset B Out
(1,3,2) # Asset B in, Asset B Out
What determines if a Cyclic Route is a Cyclic Arbitrage Route at any given state of the chain (state of pool reserves) is if there exists an amount of an asset to be swapped into the route that results in more of the same asset out (10A in, 10A+ Out).
Optimal Amount In to Swap
When given an ordered route against a specific chain state (state of pool reserves) where a cyclic arbitrage opportunity exists, one must then determine how much to swap in to capture maximum profits (where profits is defined as Asset Out Amount - Asset In Amount).
ProtoRev uses a binary search algorithm to determine the optimal amount in to swap, using functions from the PoolManager module for calculations and swap execution.
State
State Object
The x/protorev module keeps the following objects in state:
| State Object | Description | Key | Values | Store |
|---|---|---|---|---|
| TokenPairArbRoutes | TokenPairRoutes tracks cyclic arb routes that can be used to create a MultiHopSwap given two denoms | []byte{1} + []byte{inputDenom} +[]byte{outputDenom} | []byte{TokenPairArbRoutes} | KV |
| DenomPairToPool | Tracks the pool ids of the highest liquidity pools matched with a given denom | []byte{2} + []byte{baseDenom} + []byte{denomToMatch} | []byte{poolID} | KV |
| BaseDenoms (deprecated) | Superseded by prefix 19. Retained so historical state remains decodable | []byte{3} | []byte{[]BaseDenom{}} | KV |
| NumberOfTrades | Tracks the number of trades protorev has executed | []byte{4} | []byte{numberOfTrades} | KV |
| ProfitsByDenom | Tracks the profits protorev has made | []byte{5} + []byte{tokenDenom} | []byte{sdk.Coin} | KV |
| TradesByRoute | Tracks the number of trades the module has executed on a given route | []byte{6} + []byte{route} | []byte{numberOfTrades} | KV |
| ProfitsByRoute | Tracks the profits the module has accumulated after trading on a given route | []byte{7} + []byte{route} | []byte{sdk.Coin} | KV |
| DeveloperAccount | Tracks the developer account for protorev | []byte{8} | []byte{sdk.AccAddress} | KV |
| DaysSinceModuleGenesis | Tracks the number of days since the module was initialized. Used to track profits that can be withdrawn by the developer account | []byte{9} | []byte{uint} | KV |
| DeveloperFees (deprecated in v16) | Tracks the profits that the developer account can withdraw | []byte{10} + []byte{tokenDenom} | []byte{sdk.Coin} | KV |
| MaxPoolPointsPerTx | Tracks the maximum number of pool points that can be consumed per tx | []byte{11} | []byte{uint64} | KV |
| MaxPoolPointsPerBlock | Tracks the maximum number of pool points that can be consumed per block | []byte{12} | []byte{uint64} | KV |
| PoolPointCountForBlock | Tracks the number of pool points that have been consumed in this block | []byte{13} | []byte{uint64} | KV |
| LatestBlockHeight | Tracks the latest recorded block height | []byte{14} | []byte{uint64} | KV |
| InfoByPoolType | Tracks the execution information (pool points and, for concentrated pools, max ticks crossed) for each pool type | []byte{15} | []byte{InfoByPoolType} | KV |
| SwapsToBackrun | Tracks the swaps that need to be backrun for a given tx. Accumulated via swap hooks during transaction processing and discarded at the end of the block, so it is not persisted | []byte{16} | []byte{Route} | Transient |
| CyclicArbTracker | Tracks the profits made by cyclic arbitrage | []byte{17} | []byte{sdk.Coins} | KV |
| CyclicArbTrackerStartHeight | Tracks the height at which cyclic arbitrage tracking began | []byte{18} | []byte{uint64} | KV |
| BaseDenoms | Tracks all of the base denominations that will be used to construct arbitrage routes | []byte{19} | []byte{[]BaseDenom{}} | KV |
TokenPairArbRoutes
TokenPairArbRoutes are cyclic arbitrage routes that are not going to be captured by the highest liquidity method (described in state transitions below). If there is a cyclic arbitrage route that is frequently being utilized by searchers, x/protorev can manually enter this route - through the admin account - and allow it to be used for trading. Each TokenPairArbRoutes object tracks a directional swap of two assets, and associates the swap with cyclic routes. When the module sees a swap of (token_in, token_out), it will extract the arb_routes that should be used and will simulate trades and execute them if profitable.
// TokenPairArbRoutes tracks all of the hot routes for a given pair of tokens
message TokenPairArbRoutes {
option (gogoproto.equal) = true;
// Stores all of the possible hot paths for a given pair of tokens
repeated Route arb_routes = 1;
// Token denomination of the first asset
string token_in = 2;
// Token denomination of the second asset
string token_out = 3;
}
// Route is a hot route for a given pair of tokens
message Route {
option (gogoproto.equal) = true;
// The pool IDs that are traversed in the directed cyclic graph (traversed left
// -> right)
repeated Trade trades = 1;
// The step size that will be used to find the optimal swap amount in the
// binary search
string step_size = 2 [
(gogoproto.customtype) = "github.com/cosmos/cosmos-sdk/types.Int",
(gogoproto.nullable) = true
];
}
// Trade is a single trade in a route
message Trade {
option (gogoproto.equal) = true;
// The pool IDs that are traversed in the directed cyclic graph (traversed left
// -> right)
uint64 pool = 1;
// The denom of token A that is traded
string token_in = 2;
// The denom of token B that is traded
string token_out = 3;
}
DenomPairToPool
DenomPairToPool takes in a base denomination (read below), the denom that is used to build routes (ex. osmo, atom, usdc), and a denom to match (akash, juno), and returns the highest liquidity pool id between the pair of denominations. For example, an input might look like (osmo, juno) -> poolID: 5. This store is directly tied to the highest liquidity method (described in state transitions below). Each base denomination is going to have its own set of denominations it maps to.
BaseDenoms
BaseDenoms are the denominations that are used to build the highest liquidity routes. This will be configurable by the admin account, but will always maintain at least uosmo as a base denom. A base denom just means the denomination that will be used to start and end a cyclic arbitrage route. Base denoms can be added on as needed basis.
NOTE: BaseDenoms do have a priority that is directly tied down to the order in the list of base denoms that are used i.e. BaseDenoms that are closer to the front of the list will likely be simulated and executed more often than those later in the list. This is done by design so that we can prioritize certain denoms over others in order to simulate and execute the most profitable trades.
NumberOfTrades
This will store the total number of arbitrage trades that x/protorev has executed since genesis. This gets incremented every time the module executes a trade.
ProfitsByDenom
This will store the profits x/protorev has accumulated for a given denom.
TradesByRoute & ProfitsByRoute
These stores allow users and researchers to query the number of cyclic arbitrage trades that have been executed by x/protorev on an cyclic arbitrage route as well as all of the profits captured on that same route. Routes are denoted by the pool ids in the route i.e. []uint643.
ProtoRevEnabled
x/protorev can be enabled or disabled through governance. As a proposal is a stateful change, we store whether the module is currently enabled or disabled in the module.
AdminAccount
The admin account is set through governance and has permissions to set hot routes, the maximum number of pool points per transaction, maximum number of pool points per block, pool type weights, base denoms and the developer account. On genesis, the admin account is set to a trusted address that is stored on a ledger - currently configured to be the Skip dev team's address. Note that governance has full ability to change this live onchain, and this admin can at most prevent x/protorev from working. All the admin account's controls have limits, so it can't lead to a chain halt, excess processing time or prevention of swaps.
DeveloperAccount
The developer account is set through a MsgSetDeveloperAccount tx. This is the account that will be able to withdraw a portion of the profits from x/protorev as specified by the Osmosis ↔ Skip proposal. Only the admin account has permission to make this message.
DaysSinceModuleGenesis
x/protorev will distribute 20% of profits to the developer account in year 1, 10% of profits in year 2, and 5% thereafter. To track how much profit can be distributed to the developer account at any given moment, we store the amount of days since module genesis.
DeveloperFees (DEPRECATED IN v16)
DeveloperFees tracks the total amount of profit that can be withdrawn by the developer account. These fees are sent to the developer account, if set, every week through the epoch hook. If unset, the funds are held in the module account. All x/protorev profits are going to be stored on the module account.
MaxPoolPointsPerTx
A pool point roughly corresponds to a millisecond of trading simulation and execution time. In order to bound the compute time of x/protorev , we set a maximum number of pool points (execution time) per transaction and per block. MaxPoolPointsPerTx tracks the maximum number of pool points that can be consumed in a given transaction. This is configurable (but bounded) by the admin account. We limit the number of pool points per transaction so that all x/protorev execution is not limited to the top of the block.
MaxPoolPointsPerBlock
MaxPoolPointsPerBlock tracks the maximum number of pool points that can be consumed in a given block. This is configurable (but bounded) by the admin account. We limit the number of pool points per block so that the execution time of the x/protorev posthandler is reasonably bounded to ensure that block time remains as is.
PoolPointCountForBlock
PoolPointCountForBlock tracks the number of pool points that have been consumed in the current block. Used to ensure that the module is not slowing down block speed.
LatestBlockHeight
LatestBlockHeight tracks the latest recorded block height. This is used to update and reset the pool point count within a block and after new blocks are proposed.
InfoByPoolType
InfoByPoolType records the cost assumptions used when ProtoRev simulates and
executes routes. Stable and balancer pools each have a weight. Concentrated
pools have a weight and a maximum number of ticks that may be crossed.
CosmWasm pools use contract-address-to-weight mappings because different pool
contracts can have different execution costs.
The old PoolWeights type is retained only for genesis and historical block
decoding. Active state and APIs use InfoByPoolType.
GenesisState
There is only one configurable parameter for the genesis state -> whether protorev is enabled or not.
// GenesisState defines the protorev module's genesis state.
type GenesisState struct {
// Module Parameters
Params Params `protobuf:"bytes,1,opt,name=params,proto3" json:"params"`
}
State Transitions
The protorev module triggers state transitions in the postHandler , governance proposals, and admin account transactions. After each sdk.Tx, the postHandler will determine whether there were any MsgSwapExactAmountIn or MsgSwapExactAmountOut in the transaction. If so, the module gets all of the pools that were used in the swap(s), temporarily stores the pool ids accessed along with their respective tokenIn/tokenOut denoms, and then builds cyclic arbitrage routes for each pool swapped against.
Route Generation
There are two primary methods for route generation: Highest Liquidity Pools and Hot Routes.
Highest Liquidity Pool Method
The highest liquidity pool method will always create cyclic arbitrage routes that have three pools. The routes that are created will always start and end with one of the denominations that are stored in BaseDenoms. The pool swapped against that the postHandler processes will always be the 2nd pool in the three-pool cyclic arbitrage route.
Highest Liquidity Pools: Updated via the daily epoch, the module iterates through all the pools and stores the highest liquidity pool for every asset that pairs with any of the base denominations the module stores (for example, the osmo/juno key will have a single pool id stored, that pool id having the most liquidity out of all the osmo/juno pools). New base denominations can be added or removed on an as needed basis by the admin account. A base denomination is just another way of describing the denomination we want to use for cyclic arbitrage. This store is then used to create routes at runtime after analyzing a swap. This store is updated through the epoch hook and when the admin account submits a MsgSetBaseDenoms tx.
The simplest way to conceptualize how the route is generated is by the following example. Assume we have two base denominations that x/protorev is currently tracking.
BaseDenoms
- Osmosis
- Atom
Lets say the postHandler receives a transaction that contains a swap of Juno -> Akash on pool 4. In this case, the module will attempt to create three-pool route where a base denomination is on either side of the route. For example, a route that it might create is
- Osmosis -> Akash (on pool 1), Akash -> Juno (on pool 4), Juno -> Osmosis (on pool 2)
It does so by finding the highest liquidity pool between (Osmosis, Akash) -> pool 1 and the highest liquidity pool between (Osmosis, Juno) -> pool 2. If there is no highest liquidity pool pair between (Osmosis, Juno) or (Osmosis, Akash), no route will be generated.
NOTE: Cyclic arbitrage routes will always go in the opposite direction of the original swap i.e. in this case we see Juno -> Akash so we know that the route must include a swap of Akash -> Juno.
The same line of reasoning exists for Atom. x/protorev will attempt to find the highest liquidity pool between (Atom, Akash) and (Atom, Juno). If these pools exist, they will be added to the list of routes that can be simulated later in the pipeline. If not, the route is discarded.
In both cases, the route that is built will always surround the pool of the original swap that was made. However, we allow for more flexibility in route generation as the highest liquidity method may not be optimal, hence the additional of hot routes.
Hot Route Method
Populated through the admin account, the module’s keeper holds a KV store that associates token pairs (for example, osmo/juno) to the routes that result in a high percentage of arbitrage profit on Osmosis (as determined by external analysis).
The purpose of storing Hot Routes is a recognition that the Highest Liquidity Pool method may not present the best arbitrage routes. As such, hot routes can be configured by the admin account to store additional routes that may be more effective at capturing arbitrage opportunities. Each hot route will store a placeholder for where the current swapped pool will fit into the trade.
Pool Rebalancing
Now that we have a list of cyclic routes for each pool swapped by the user’s tx, we then determine if any of the routes are profitable. We determine this using a binary search algorithm that finds the amount of the asset to swap in that results in the most of that same asset out. We then calculate profits by taking the difference between the amount of the asset out and amount of the asset in. By iterating through the routes and storing the route, optimal input amount, and profit of the route with the highest profit > 0, we are left with the route and amount to execute the MultiHopSwap against.
Each swap will generate its own set of routes and x/protorev will execute only the most profitable route.
The module mints the optimal input amount of the coin to swap in from the bankkeeper to the x/protorev module account, executes the MultiHopSwap by interacting with the x/poolmanager module, burns the optimal input amount of the coin minted to execute the MultiHopSwap, and sends subsequent profits to the module account.
PostHandler
The postHandler extracts pools that were swapped in a transaction and determines if there is a cyclic arbitrage opportunity. If so, the handler will find an optimal route and execute it - rebalancing the pool and returning arbitrage profits to the module account.
- Check if the module is enabled.
- If the module is disabled, nothing happens.
- Extract all pools that were traded on in the transaction (
ExtractSwappedPools) as well as the direction of the trade. - Create cyclic arbitrage routes for each of the swaps above (
BuildRoutes) - For each feasible route, determine if there is a cyclic arbitrage opportunity (
IterateRoutes)- Determine the optimal amount to swap in and its respective profits via binary search over range of potential input amounts (
FindMaxProfitForRoute) - Compare profits of each route, keep the best route and input amount with the highest profit
- Determine the optimal amount to swap in and its respective profits via binary search over range of potential input amounts (
- If the best route and input amount has a profit > 0, execute the trade (
ExecuteTrade) and rebalance the pools on-behalf of the chain through thepoolmanagerkeeper(MultiHopSwapExactAmountIn) - Keep the profits in the module’s account for subsequent distribution.
ExtractSwappedPools
Checks if there were any swaps made on pools in a transaction, returning the pool ids and input/output denoms for each pool that was traded on.
BuildRoutes
BuildRoutes takes a token pair (input and output denom) as well as the pool id and returns a list of routes for that token pair that potentially contain a cyclic arbitrage opportunity, populated via the Hot Route and Highest Liquidity Pools method as described above.
IterateRoutes
IterateRoutes iterates through a list of routes, determining the route and input amount that results in the highest cyclic arbitrage profits..