[Feature]: Simplify code to handle out-of-order external TWAP points

[wwestgarth]

Feature Overview

At face value the calculation of the TWAP's for perpetual funding payments seems like it should be straight forward -- we take the ordered points, multiple the time intervals by the prices and divide by the total period and we are done.

Unfortunately life is never that straight forward.

The difficulties come from following three requirements:

• we need to report via the API the current funding rate at each block
• we have to exclude auction periods from the TWAP calculations
• we need to handle external data points arriving out-of-order since we are not in control of how they are placed in blocks

The first points means we have to cache the TWAP calulations as we go along. Recalculating the entire TWAP each block will be too slow. We currently do this by saving the sum-product we calculated at time t and as time moves forward we only need to add the contribution to the sum-product for the period t + delta(t).

The difficulty is what do we do with the cache when a data point comes in out-of-order say at time t-1. In this case we need to unwind the cached sum-product we have at time t until we get back to t-1. We do this by subtracting the contribution for the interval (t-1, t) and then recalculating the sum-product forward again until we are at time t again.

This is fiddly especially when you need to unwind through multiple existing data-point. In then gets more fiddly again when we have to unwind through auction periods.

The result very much relies on the symmetry in calculations between incrementing the TWAP and winding back the TWAP as any asymmetries can cause discrepancies that are hard to track down. The current implementation has so far caused bugs every time this code is changed.

HOW CAN WE DO BETTER

Instead of only storing the sum-product at the last calculated point t we can also store the sum-product at every data-point received. This means we can avoid having to do any calculations to unwind any intervals.

For example if we are at time t and a data-point comes in at time t-1 all we have to do is to walk backwards through our data-points until we find the one whose time is < t-1. We can grab the sum-product at that point, and then start recalculate forwards from that point.

Doing it this way means that there is no risk of mis-calculation when trying to travel backwards in time as we already have the state saved for historic points in time.