fix: inconsistencies in tick to price and price to tick conversions

[p0mvn]

Background

If we have tick X and call TickTiSqrtPrice and get Y. Then, by calling PriceToTick(Y.Power(2)), we should be able to get X back.

Currently, this is not the case. Probably because of the ApproxSqrt function here:

osmosis/x/concentrated-liquidity/math/tick.go

Lines 86 to 90 in 97c9be1

	// Determine the sqrtPrice from the price
	sqrtPrice, err := price.ApproxSqrt()
	if err != nil {
	return sdk.Dec{}, err
	}

Suggested Design

Add the call to PriceToTick at the end of this test:

osmosis/x/concentrated-liquidity/math/tick_test.go

Lines 162 to 171 in 97c9be1

	}
	func (suite *ConcentratedMathTestSuite) TestPriceToTick() {
	testCases := map[string]struct {
	price sdk.Dec
	exponentAtPriceOne sdk.Int
	tickExpected string
	expectedError error
	}{
	"50000 to tick with -4 k at price one": {

Then, you will be able to reproduce the problem

Acceptance Criteria

• modify TestTickToSqrtPricePriceToTick_InverseRelationship to call PriceToTick second time
• test passes
• confirm mapping in both directions works correctly

[p0mvn]

Conclusion on this from the call to pursue in #4965:

• Improve test to better understand the magnitude of the problem
• Increase the number of iterations
• Compare against sage / sympy / Wolfram
• If does not help, use Chebyshev approximation exp2 tricks to compute power^(1/2)
• If doesn't help, implement square root with a better method

[p0mvn]

Improve test to better understand the magnitude of the problem

Added a variety of test cases at our default exponent of price 6, going from the smallest possible price upwards.

The steps followed:

• Compute tick from price
• Compute price from tick inversePrice
• Confirm inversePrice matches original price
• Internally get sqrt price from inversePrice inverseSqrtPrice
• Take inverseSqrtPrice^2 to get priceFromSqrtPrice
• Compute tick from inversePrice and get the same tick
• Compute tick from priceFromSqrtPrice and get a different tick

Consider these 3 cases:

1. Smallest price

   • price: 0.000000000000000001
   • tick expected: -162000000
   • actual match expected with inverse relationship

2. Smallest price * 2

   • price: 0.000000000000000002
   • tick expected: -161000000
   • actual matches expected

3. Smallest price * 10

   • price: 0.000000000000000010
   • tick expected: -153000000
   • actual tick: -154000000

4. Smallest price * 10 - 1

   • price: 0.000000000000000009
   • tick expected: -154000000
   • actual matches expected

Note from test case 3 that the magnitude of the difference is quite large. However, this is only because of our tick spacing model. The core of the problem is that when we compute the inverse, we end up getting a smaller price and a lower tick due to losing precision.

To be continued / draft section

For test case 3, when we compute priceFromSqrtPrice, we end up getting price 0.000000000000000009 when it should be 0.000000000000000010

>>> price = Decimal("0.000000000000000010")
>>> price.sqrt()
Decimal('3.162277660168379331998893544E-9')
>>> math.pow(price.sqrt(), 2)
1e-17

[p0mvn]

The scope of this work keeps changing and increasing.

There are too many suspicious behaviors that keep having me go in circles.

As a result, I'm going to start splitting the investigations into separate PRs and document them here.

My initial investigations that lead to the discovery of this problem: #4965

After #4965, ApproxSqrt was under suspicion. Upon more investigations, I realized that the major problems where stemming from varying exponents at price one that were limited to just -6, ref: #4957

Additionally, there were off-by-one errors stemming from rounding that got fixed in: #4998

As a drive-by change, I removed the use of a broken Power function here: #5000

Next, I attempted to mitigate the risk of incorrect rounding when squaring during swaps: #5002

[p0mvn]

Latest state on this.

Price to tick conversion summary.

We have: price to tick conversion and dynamic tick spacing at human readable increments.
Pros:

• human readable, ability to place limit orders at values that make sense
• dynamic (there is a con of thj)
  Cons:
• losing capital efficiency at large price ranges
• Some edge cases around rounding.

Uniswap:
Pros:

• Can have a function between tick and sqrt price because human readability is not a concern, removing the requirement on price to tick conversion.
• Greater precision: The logarithmic scale allows for greater precision at both low and high prices, which enables more accurate representation of price changes across a wide range.
• Uniform distribution/simplicity: The logarithmic scale allows for a uniform distribution of ticks across the entire price range, which means that the same percentage change in price is represented by the same number of ticks, regardless of the price level.
  Cons:
• Cannot place limit orders at human readable increments

The core of our problem is that the conversion occurs between price and tick, and not square root price and tick.
At the same time, internal calculations in swap and LP logic are performed in terms of square root price. We end
up having to convert from sqrt price to price and then to tick to get the current tick corresponding to the
current square root price. In these conversions, we lose some precision. However, the latest soft conclusion is that
the precision loss is negligeble and is mitigated by performing rounding in the right places.

For context, the reason why we track square root price and not price is because it allows us to have a simple math relationship
between liquidity, token amounts and price. Operating in the price space would require us to perform a lot of complex math.

Since we want to support dynamic price granularity, we ended up breaking
up the price range into ticks as opposed to breaking up square root price range into ticks.

To show the consequences, let's take an extreme example where at price 10_000_000, our price increments are in the order of magnitude of 1.

That is, the only possible prices are 10_000_000, 10_000_010, 10_000_020 etc.

So, say that I end up on current square root price 3162.2784507376955 as I perform the swap.
Note, that squaring this yields 10_000_005.
At the end of the swap, I must translate this to a current tick.
The problem that there is no price that corresponds to this square root price.

As a result, I must truncate the price to the nearest one that can be mapped to a tick. Using banker's rounding,
this would be 10_000_000.

However, what do I do with the excess amounts? Do I swap them back?
It seems that I should not be able to reach the square root price corresponding to
10_000_005. However, that's not how it works right now.

There are a few solutions:

1. Refactor swap logic to disallow square root price from reaching a point where it cannot be translated to a tick. Decrease exponent at price one to -8.
   At this exponent at price one, at price level of 100_000_000, our price increments are in the order of magnitude of 0.

Pros:

• We keep our dynamic tick spacing. We have solid price granularity at large price levels with buffer.

Risks:

• Additional complexity in swaps that needs to be refactored
• Need to make sure that decreaseing exponent at price one does not cause any rounding errors in other parts of the system.

2. Always perform math in terms of prices

Pros

• Works wih the dynamic granular tick spacing

Risks:

• We will end up with complex math operations in swaps and LP logic, potentially leading to rounding errors in other
  parts of the system.
• A lot of logic and tests to refactor.

3. Always perform math in terms of square root prices while removing dynamic tick spacing.

Pros:

• Capital efficiency at every price level due to uniform logarithmic tick spacing

Problems:

• Cannot make tick spacing human-readable
• Going back to Uniswap
• Large refactor that might lead to other problems.

[p0mvn]

Had some more discussions after writing up the above. To summarize the next 3 actions:

• Refactor swap logic to disallow square root price from reaching a point where it cannot be translated to a tick.
• Handle tick spacing during the above refactor
• Remove banker's rounding of ticks and make it more deterministic
• Ensure that we do not repeatedly do square root price to tick conversions during low-level swap calculations as we lose precision. It should be fine to square the square root price to determine if we reached the right tick or not
• Keep exponent at price one of -6, we should not need a granularity of -8.

[p0mvn]

This is closed by the latest change: #5019