/
rebalance.go
420 lines (357 loc) · 15.7 KB
/
rebalance.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
package keeper
import (
sdk "github.com/cosmos/cosmos-sdk/types"
"github.com/osmosis-labs/osmosis/osmomath"
poolmanagertypes "github.com/fury-labs/furya/v20/x/poolmanager/types"
"github.com/fury-labs/furya/v20/x/protorev/types"
)
// IterateRoutes checks the profitability of every single route that is passed in
// and returns the optimal route if there is one
func (k Keeper) IterateRoutes(ctx sdk.Context, routes []RouteMetaData, remainingTxPoolPoints, remainingBlockPoolPoints *uint64) (sdk.Coin, osmomath.Int, poolmanagertypes.SwapAmountInRoutes) {
var optimalRoute poolmanagertypes.SwapAmountInRoutes
var maxProfitInputCoin sdk.Coin
maxProfit := osmomath.ZeroInt()
// Iterate through the routes and find the optimal route for the given swap
for index := 0; index < len(routes) && *remainingTxPoolPoints > 0; index++ {
// If the route consumes more pool points than we have remaining then we skip it
if routes[index].PoolPoints > *remainingTxPoolPoints {
continue
}
// Find the max profit for the route if it exists
inputCoin, profit, err := k.FindMaxProfitForRoute(ctx, routes[index], remainingTxPoolPoints, remainingBlockPoolPoints)
if err != nil {
k.Logger(ctx).Error("Error finding max profit for route: " + err.Error())
continue
}
// If the profit is greater than zero, then we convert the profits to ufury and compare profits in terms of ufury
if profit.GT(osmomath.ZeroInt()) {
profit, err := k.ConvertProfits(ctx, inputCoin, profit)
if err != nil {
k.Logger(ctx).Error("Error converting profits: " + err.Error())
continue
}
// Select the optimal route King of the Hill style (route with the highest profit will be executed)
if profit.GT(maxProfit) {
optimalRoute = routes[index].Route
maxProfit = profit
maxProfitInputCoin = inputCoin
}
}
}
return maxProfitInputCoin, maxProfit, optimalRoute
}
// ConvertProfits converts the profit denom to ufury to allow for a fair comparison of profits
//
// NOTE: This does not check the underlying pool before swapping so this may go over the MaxTicksCrossed.
func (k Keeper) ConvertProfits(ctx sdk.Context, inputCoin sdk.Coin, profit osmomath.Int) (osmomath.Int, error) {
if inputCoin.Denom == types.FuryaDenomination {
return profit, nil
}
// Get highest liquidity pool ID for the input coin and ufury
conversionPoolID, err := k.GetPoolForDenomPair(ctx, types.FuryaDenomination, inputCoin.Denom)
if err != nil {
return profit, err
}
// Get the pool
conversionPool, err := k.poolmanagerKeeper.GetPool(ctx, conversionPoolID)
if err != nil {
return profit, err
}
swapModule, err := k.poolmanagerKeeper.GetPoolModule(ctx, conversionPoolID)
if err != nil {
return profit, err
}
// Calculate the amount of ufury that we can get if we swapped the
// profited amount of the orignal asset through the highest ufury liquidity pool
conversionTokenOut, err := swapModule.CalcOutAmtGivenIn(
ctx,
conversionPool,
sdk.NewCoin(inputCoin.Denom, profit),
types.FuryaDenomination,
conversionPool.GetSpreadFactor(ctx),
)
if err != nil {
return profit, err
}
// return the profit denominated in ufury
return conversionTokenOut.Amount, nil
}
// EstimateMultihopProfit estimates the profit for a given route
// by estimating the amount out given the amount in for the first pool in the route
// and then subtracting the amount in from the amount out to get the profit
func (k Keeper) EstimateMultihopProfit(ctx sdk.Context, inputDenom string, amount osmomath.Int, route poolmanagertypes.SwapAmountInRoutes) (sdk.Coin, osmomath.Int, error) {
tokenIn := sdk.NewCoin(inputDenom, amount)
amtOut, err := k.poolmanagerKeeper.MultihopEstimateOutGivenExactAmountIn(ctx, route, tokenIn)
if err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
}
profit := amtOut.Sub(tokenIn.Amount)
return tokenIn, profit, nil
}
// FindMaxProfitRoute runs a binary search to find the max profit for a given route
func (k Keeper) FindMaxProfitForRoute(ctx sdk.Context, route RouteMetaData, remainingTxPoolPoints, remainingBlockPoolPoints *uint64) (sdk.Coin, osmomath.Int, error) {
// Track the tokenIn amount/denom and the profit
tokenIn := sdk.Coin{}
profit := osmomath.ZeroInt()
// Track the left and right bounds of the binary search
curLeft := osmomath.OneInt()
curRight := types.MaxInputAmount
// Input denom used for cyclic arbitrage
inputDenom := route.Route[route.Route.Length()-1].TokenOutDenom
// If a cyclic arb exists with an optimal amount in above our minimum amount in,
// then inputting the minimum amount in will result in a profit. So we check for that first.
// If there is no profit, then we can return early and not run the binary search.
_, minInProfit, err := k.EstimateMultihopProfit(ctx, inputDenom, curLeft.Mul(route.StepSize), route.Route)
if err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
} else if minInProfit.LTE(osmomath.ZeroInt()) {
return sdk.Coin{}, osmomath.ZeroInt(), nil
}
// Decrement the number of pool points remaining since we know this route will be profitable
*remainingTxPoolPoints -= route.PoolPoints
*remainingBlockPoolPoints -= route.PoolPoints
// Increment the number of pool points consumed since we know this route will be profitable
if err := k.IncrementPointCountForBlock(ctx, route.PoolPoints); err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
}
// Update the search range if the max input amount is too small/large
curLeft, curRight, err = k.UpdateSearchRangeIfNeeded(ctx, route, inputDenom, curLeft, curRight)
if err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
}
// Binary search to find the max profit
for iteration := 0; curLeft.LT(curRight) && iteration < types.MaxIterations; iteration++ {
curMid := (curLeft.Add(curRight)).Quo(osmomath.NewInt(2))
curMidPlusOne := curMid.Add(osmomath.OneInt())
// Short circuit profit searching if there is an error in the GAMM module
tokenInMid, profitMid, err := k.EstimateMultihopProfit(ctx, inputDenom, curMid.Mul(route.StepSize), route.Route)
if err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
}
// Short circuit profit searching if there is an error in the GAMM module
tokenInMidPlusOne, profitMidPlusOne, err := k.EstimateMultihopProfit(ctx, inputDenom, curMidPlusOne.Mul(route.StepSize), route.Route)
if err != nil {
return sdk.Coin{}, osmomath.ZeroInt(), err
}
// Reduce subspace to search for max profit
if profitMid.LTE(profitMidPlusOne) {
curLeft = curMidPlusOne
tokenIn = tokenInMidPlusOne
profit = profitMidPlusOne
} else {
curRight = curMid
tokenIn = tokenInMid
profit = profitMid
}
}
return tokenIn, profit, nil
}
// UpdateSearchRangeIfNeeded updates the search range for the binary search. First, we check if there are any
// concentrated liquidity pools in the route. If there are, then we may need to reduce the upper bound of the
// binary search since it is gas intensive to move across several ticks. Next, we determine if the current bound
// includes the optimal amount in. If it does not, then we can extend the search range to capture more profits.
func (k Keeper) UpdateSearchRangeIfNeeded(
ctx sdk.Context,
route RouteMetaData,
inputDenom string,
curLeft, curRight osmomath.Int,
) (osmomath.Int, osmomath.Int, error) {
// If there are concentrated liquidity pools in the route, then we may need to reduce the upper bound of the binary search.
updatedMax, err := k.CalculateUpperBoundForSearch(ctx, route, inputDenom)
if err != nil {
return osmomath.ZeroInt(), osmomath.ZeroInt(), err
}
// In the case where the updated upper bound is less than the current upper bound, we know we will not extend
// the search range so we can short-circuit return.
if updatedMax.LT(curRight) {
return curLeft, updatedMax, nil
}
return k.ExtendSearchRangeIfNeeded(ctx, route, inputDenom, curLeft, curRight, updatedMax)
}
// CalculateUpperBoundForSearch returns the max amount in that can be used for the binary search
// respecting the max ticks moved across all concentrated liquidity pools in the route.
func (k Keeper) CalculateUpperBoundForSearch(
ctx sdk.Context,
route RouteMetaData,
inputDenom string,
) (osmomath.Int, error) {
var intermidiateCoin sdk.Coin
poolInfo := k.GetInfoByPoolType(ctx)
// Iterate through all CL pools and determine the maximal amount of input that can be used
// respecting the max ticks moved.
for index := route.Route.Length() - 1; index >= 0; index-- {
hop := route.Route[index]
pool, err := k.poolmanagerKeeper.GetPool(ctx, hop.PoolId)
if err != nil {
return osmomath.ZeroInt(), err
}
tokenInDenom := inputDenom
if index > 0 {
tokenInDenom = route.Route[index-1].TokenOutDenom
}
switch {
case pool.GetType() == poolmanagertypes.Concentrated:
// If the pool is a concentrated liquidity pool, then check the maximum amount in that can be used
// and determine what this amount is as an input at the previous pool (working all the way up to the
// beginning of the route).
maxTokenIn, maxTokenOut, err := k.concentratedLiquidityKeeper.ComputeMaxInAmtGivenMaxTicksCrossed(
ctx,
pool.GetId(),
tokenInDenom,
poolInfo.Concentrated.MaxTicksCrossed,
)
if err != nil {
return osmomath.ZeroInt(), err
}
// if there have been no other CL pools in the route, then we can set the intermediate coin to the max input amount.
// Additionally, if the amount of the previous token is greater than the possible amount from this pool, then we
// can set the intermediate coin to the max input amount (from the current pool). Otherwise we have to do a
// safe swap given the previous max amount.
if intermidiateCoin.IsNil() || maxTokenOut.Amount.LT(intermidiateCoin.Amount) {
intermidiateCoin = maxTokenIn
continue
}
// In the scenario where there are multiple CL pools in a route, we select the one that inputs
// the smaller amount to ensure we do not overstep the max ticks moved.
intermidiateCoin, err = k.executeSafeSwap(ctx, pool.GetId(), intermidiateCoin, tokenInDenom)
if err != nil {
return osmomath.ZeroInt(), err
}
case !intermidiateCoin.IsNil():
// If we have already seen a CL pool in the route, then simply propagate the intermediate coin up
// the route.
intermidiateCoin, err = k.executeSafeSwap(ctx, pool.GetId(), intermidiateCoin, tokenInDenom)
if err != nil {
return osmomath.ZeroInt(), err
}
}
}
// In the case where there are no CL pools, we want to return the extended max input amount
if intermidiateCoin.IsNil() {
return types.ExtendedMaxInputAmount, nil
}
// Ensure that the normalized upper bound is not greater than the extended max input amount
upperBound := intermidiateCoin.Amount.Quo(route.StepSize)
if upperBound.GT(types.ExtendedMaxInputAmount) {
return types.ExtendedMaxInputAmount, nil
}
return upperBound, nil
}
// executeSafeSwap executes a safe swap by first ensuring the swap amount is less than the
// amount of total liquidity in the pool.
func (k Keeper) executeSafeSwap(
ctx sdk.Context,
poolID uint64,
outputCoin sdk.Coin,
tokenInDenom string,
) (sdk.Coin, error) {
liquidity, err := k.poolmanagerKeeper.GetTotalPoolLiquidity(ctx, poolID)
if err != nil {
return sdk.NewCoin(tokenInDenom, osmomath.ZeroInt()), err
}
// At most we can swap half of the liquidity in the pool
liquidTokenAmt := liquidity.AmountOf(outputCoin.Denom).Quo(osmomath.NewInt(4))
if liquidTokenAmt.LT(outputCoin.Amount) {
outputCoin.Amount = liquidTokenAmt
}
amt, err := k.poolmanagerKeeper.MultihopEstimateInGivenExactAmountOut(
ctx,
poolmanagertypes.SwapAmountOutRoutes{
{
PoolId: poolID,
TokenInDenom: tokenInDenom,
},
},
outputCoin,
)
if err != nil {
return sdk.NewCoin(tokenInDenom, osmomath.ZeroInt()), err
}
return sdk.NewCoin(tokenInDenom, amt), nil
}
// Determine if the binary search range needs to be extended
func (k Keeper) ExtendSearchRangeIfNeeded(
ctx sdk.Context,
route RouteMetaData,
inputDenom string,
curLeft, curRight, updatedMax osmomath.Int,
) (osmomath.Int, osmomath.Int, error) {
// Get the profit for the maximum amount in
_, maxInProfit, err := k.EstimateMultihopProfit(ctx, inputDenom, curRight.Mul(route.StepSize), route.Route)
if err != nil {
return osmomath.ZeroInt(), osmomath.ZeroInt(), err
}
// If the profit for the maximum amount in is still increasing, then we can increase the range of the binary search
if maxInProfit.GTE(osmomath.ZeroInt()) {
// Get the profit for the maximum amount in + 1
_, maxInProfitPlusOne, err := k.EstimateMultihopProfit(ctx, inputDenom, curRight.Add(osmomath.OneInt()).Mul(route.StepSize), route.Route)
if err != nil {
return osmomath.ZeroInt(), osmomath.ZeroInt(), err
}
// Change the range of the binary search if the profit is still increasing
if maxInProfitPlusOne.GT(maxInProfit) {
curLeft = curRight
curRight = updatedMax
}
}
return curLeft, curRight, nil
}
// ExecuteTrade inputs a route, amount in, and rebalances the pool
func (k Keeper) ExecuteTrade(ctx sdk.Context, route poolmanagertypes.SwapAmountInRoutes, inputCoin sdk.Coin, pool SwapToBackrun, remainingTxPoolPoints, remainingBlockPoolPoints uint64) error {
// Get the module address which will execute the trade
protorevModuleAddress := k.accountKeeper.GetModuleAddress(types.ModuleName)
// Mint the module account the input coin to trade
if err := k.bankKeeper.MintCoins(ctx, types.ModuleName, sdk.NewCoins(inputCoin)); err != nil {
return err
}
// Use the inputCoin.Amount as the min amount out to ensure profitability
tokenOutAmount, err := k.poolmanagerKeeper.RouteExactAmountIn(ctx, protorevModuleAddress, route, inputCoin, inputCoin.Amount)
if err != nil {
return err
}
// Burn the coins from the module account after the trade and leave all remaining coins in the module account
if err := k.bankKeeper.BurnCoins(ctx, types.ModuleName, sdk.NewCoins(inputCoin)); err != nil {
return err
}
// Profit from the trade
profit := tokenOutAmount.Sub(inputCoin.Amount)
// Update the module statistics stores
if err = k.UpdateStatistics(ctx, route, inputCoin.Denom, profit); err != nil {
return err
}
// Send the developer fee to the developer address
if err := k.SendDeveloperFee(ctx, sdk.NewCoin(inputCoin.Denom, profit)); err != nil {
ctx.Logger().Error("failed to send developer fee: " + err.Error())
}
// Create and emit the backrun event and add it to the context
EmitBackrunEvent(ctx, pool, inputCoin, profit, tokenOutAmount, remainingTxPoolPoints, remainingBlockPoolPoints)
return nil
}
// RemainingPoolPointsForTx calculates the number of pool points that can be consumed in the transaction and block.
// When the remaining pool points for the block is less than the remaining pool points for the transaction, then both
// returned values will be the same, which will be the remaining pool points for the block.
func (k Keeper) GetRemainingPoolPoints(ctx sdk.Context) (uint64, uint64, error) {
maxPoolPointsPerTx, err := k.GetMaxPointsPerTx(ctx)
if err != nil {
return 0, 0, err
}
maxPoolPointsPerBlock, err := k.GetMaxPointsPerBlock(ctx)
if err != nil {
return 0, 0, err
}
currentPoolPointsUsedForBlock, err := k.GetPointCountForBlock(ctx)
if err != nil {
return 0, 0, err
}
// Edge case where the number of pool points consumed in the current block is greater than the max number of routes per block
// This should never happen, but we need to handle it just in case (deal with overflow)
if currentPoolPointsUsedForBlock >= maxPoolPointsPerBlock {
return 0, 0, nil
}
// Calculate the number of pool points that can be iterated over
numberOfAvailablePoolPointsForBlock := maxPoolPointsPerBlock - currentPoolPointsUsedForBlock
if numberOfAvailablePoolPointsForBlock > maxPoolPointsPerTx {
return maxPoolPointsPerTx, numberOfAvailablePoolPointsForBlock, nil
}
return numberOfAvailablePoolPointsForBlock, numberOfAvailablePoolPointsForBlock, nil
}