Improve Protorev Binary Search Range Bounding For Concentrated Liquidity Pools

[NotJeremyLiu]

Background

• This issue describes the ideal APIs the Concentrated Liquidity (CL) module can provide ProtoRev to perform successful pool rebalancing, without running into spurious out of gas issues related to crossing ticks in CL pool swaps.

• The context behind this issue is that after the v16 upgrade, it was discovered that when a CL pool has low liquidity and a sizable number of ticks (at the time of the discovery, that being ~$1k of total liquidity and ~28k ticks), when attempting determine the optimal input size to rebalance pools via a binary search approach in protorev, a single call to k.poolmanagerKeeper.MultihopEstimateOutGivenExactAmountIn with a tokenIn that crosses over 10k ticks takes more than 50 million gas to compute.

• The three main relevant APIs that Protorev uses as part of its rebalancing logic are:

  1. poolmanagerKeeper.MultihopEstimateOutGivenExactAmountIn
  2. swapModule.CalcOutAmtGivenIn
  3. poolmanagerKeeper.RouteExactAmountIn

• Currently, none of these methods provide an easy way to bound the number of ticks crossed or gas used.

• At the heart of the problem is trying to swap in too large of an amount through a route, causing too many ticks to be crossed. The reason this is the case today is because ProtoRev determines the optimal input amount by performing a binary search process that tests different input amounts to see which one results in the largest profit. For example, the parameters set for the OSMO backrunning opportunities is set to perform a binary search between 1 and 16,384 OSMO (extending up to 131,072 OSMO if an opportunity needs more than ~16k to fully capture the opportunity).

• To solve this issue then is to have more intelligent binary search bounds calculations, decreasing the upper bound if it crosses too many ticks on a concentrated liquidity pool(s) based on the acceptable gas usage and compute time of the module.

Suggested Design

Concentrated Liquidity Changes To Improve Situation

• Implementing a ComputeMaxInAmtGivenMaxTicksCrossed for the CL module

// Returns the maxmimum amount of the tokenInDenom that can be swapped into the pool
// to swap through all the liquidity from the current tick through the maxTicksCrossed tick,
// but not exceed it.
//
// The protorev use case for this will be to call this method to X number of ticks based
// on what is acceptable gas-wise and use the maxTokenIn as the upper bound for the binary
// search if it's less than the default protorev binary search upper bound. This will then
// allow the module to intelligently limit the gas-usage and compute time for assessing the 
// backrunning opportunities of routes that contain a concetrated liquidity pool(s).
func (k Keeper) ComputeMaxInAmtGivenMaxTicksCrossed(
  ctx sdk.Context,
  poolId uint64,
  tokenInDenom string,
  maxTicksCrossed uint64,
) (maxTokenIn sdk.Coin, err error)

would be useful so that protorev can determine the max amount that can be put in while still respecting the tick boundaries. This will then be used to decide the protorev binary search upper bound, taking the min of MaxInAmtGivenMaxTicksCrossed from this method and the const 2^14 bound from the module.

ProtoRev Changes To Improve Situation

• Once ComputeMaxInAmtGivenMaxTicksCrossed (or something similar) is implemented, update the ExtendSearchRangeIfNeeded method in rebalance.go (

  osmosis/x/protorev/keeper/rebalance.go

  Line 171 in 4aeaaa5

  func (k Keeper) ExtendSearchRangeIfNeeded(ctx sdk.Context, route RouteMetaData, inputDenom string, curLeft, curRight sdk.Int) (sdk.Int, sdk.Int) {

  ) to be a more general UpdateSearchRangeIfNeeded method that also can decrease the search range.
• The case decreasing the search range in this method will be if the route has a CL pool in it and choosing the min beween ComputeMaxInAmtGivenMaxTicksCrossed and the default upper bound.

[NotJeremyLiu]

@stackman27 Can you take a look at this issue when you get a chance and let me know if exploring creating this method is feasible, thanks!

[NotJeremyLiu]

Re-opening this issue to also track protorev's side of changes to support this

[davidterpay]

Addressing this here: #5884