[EPIC][x/twap] Geometric TWAP

[p0mvn]

Background

While the arithmetic mean TWAPs are much more widely used, they should theoretically be less accurate in measuring a geometric Brownian motion process (which is how price movements are usually modeled)

Arithmetic TWAP tends to overweight higher prices relative to lower ones.

Therefore, we should implement Geometric TWAP.

Suggested Design

The geometric mean can be expressed as the exponential of the arithmetic mean of logarithms.

Ultimately, we would like to calculate:

Therefore, we should be able to utilize our existing arithmetic accumulator system in the log scale.

As the first step, I propose finalizing the logarithm implementation: #2788

Next, integrate the geometric TWAP into the twap module by utilizing the log-average relationship described above.

Core Progress

• feat(x/twap): Geometric Mean TWAP POC #3420
• feat(scripts): polynomial and rational approximations #3620
• feat(osmomath): BigDec power function with integer exponent, overflow tests at max spot price #3676
• test(x/twap): split up TestComputeArithmeticTwap_ThreeAsset into arithmetic and geometric #3443
• feat(x/twap): implement reusable TWAP API #3514
• test(twap): add overflow tests for geometric TWAP #3540
• test(twap): edge case tests for geometric twap #3541
• feat(app/upgrades): implement twap record migrations for geometric logic #3542
• test(twap): ensure test coverage for twapLog and twapPow #3543
• test(e2e): basic geometric twap test #3728
• test(twap): revisit err tolerance in geometric twap with high scaling factor stableswap pool  #3770
• test(x/twap): final manual geometric twap CLI test on v14.x branch #3941

Acceptance Criteria

• Geometric TWAP is implemented using log-average
• Logarithm implementation is efficient and accurate
• The log-average rounding is insignificant
• Integration into the existing TWAP module is sound

Sources

• https://en.wikipedia.org/wiki/Geometric_mean#Relationship_with_logarithms
• https://en.wikipedia.org/wiki/Geometric_Brownian_motion#Use_in_finance
• https://uniswap.org/whitepaper-v3.pdf

[p0mvn]

Some notes on the investigations so far:

The naive approach to computing a geometric weighted average is not desirable. First, it is computationally expensive. Second, it causes overflows when attempting to exponentiate spot price with the time weight denominated in milliseconds. Using seconds instead would make us lose precision.

The proposed approach requires using Power() function that takes a decimal exponent.

We already have a Taylor series approximation for bases <= 2 here.

One approach is to implement Power() for decimal bases > 2 by following this blogpost: https://xn--2-umb.com/22/exp-ln/

Earlier I suggested using Euler's number (that is > 2) as the base and natural log as the exponent. However, there is no particular reason for that.

Therefore, we can follow the Uniswap v3 choice of base 1.0001 that is within the bounds for the existing Power function to compute:
$$GeometricTwap(P) = 1.0001^{ArithmeticTwap(log_{1.0001}{P})}$$