Moving average filters

Euler builds upon Uniswap’s time-weighted average price (TWAP) oracles to allow users to lend and borrow almost any fungible token. This is part 2 of a series of articles (see Part 1) in which we describe how TWAP oracles work and the advantages they bring to users of our decentralised lending protocol.

Moving averages

A time-weighted average price is a form of moving average, which is a way to dampen temporary deviations in a sequence of data. Imagine we are monitoring the price of an asset, and there is no movement for some time. Then, there is a single trade that spikes the price up, and another that spikes it back down, so that the spiked price is only available momentarily:

This is known as an “impulse” and illustrates a spike in price for the smallest possible time interval. Let’s suppose we’re working with discrete time, and our smallest granularity is 1 second. In this case, the impulse lasts for exactly 1 second, after which the price returns to the original value.

What a moving average does is “smear” this impulse over a certain window of time, leaving what is called the impulse response:

Suppose the window is 10 seconds in length. Once the impulse occurs, each point in the response is now the average of 9 prices at the original level, and 1 price at the new level.

Here are a few observations about this impulse response (assuming arithmetic averaging for now):

• The response includes the effect of the impulse incorporated over the duration of the 10 second window.
• The maximum height of the response is 1/10th the height of the impulse.
• After the window passes, the price level returns to precisely the base level, and there is no residual effect from the impulse (this makes it a “Finite Impulse Response”, or FIR).

The impulse response is a description of a digital filter (such as a moving average). Surprisingly it also embeds all the information necessary to understand how a filter behaves. There are other illustrations possible, but they are just different renderings of the information available in the impulse response.

As well as the impulse response, it is often helpful to talk about the step response of a filter. In this case, imagine that a price is steady for a while, and then there is a trade that increases the price to a new level, after which it remains steady at this new level:

Here is a moving average’s response to a step:

Because the first point in the moving average window after the step is the average of 9 points pre-step and one point post-step, it is 1/10th the height of the step.

The second point contains 8 pre-step and 2 post-step, so it is 2/10th the height, and so forth:

• Abrupt changes in the input take some time to be fully reflected in the response.
• After the window elapses, the response output precisely matches the new level.

As we said, the step response of a filter doesn’t provide any extra information over the impulse response. You may have noticed that the step response is the discrete integral of the impulse response, which is just a way of saying that if you keep a running sum of all the values in the impulse response and plot it over time, you’ll have the step response.

Moving average filters are excellent at smoothing data in time-domain plots like above. Unfortunately they are miserable performers when trying to build low-pass filters, the reasons for which are beyond the scope of this article (but intuitively, a moving average filter will leave sharp edges as seen in the boxcar’s corners, which are higher order harmonics in the output signal).

Recursive updates

So why are moving averages so commonly used instead of other types of convolution? It’s because they have one major advantage: They can be computed recursively, which is very efficient. In this sense, recursion means taking the result of a previous iteration and performing some minor update on it to get the next result.

Suppose you have the sum of a window from points 10 through 20, and now you receive point 21. Rather than summing up all the points 11 through 21, you can simply take the previous sum, subtract the oldest point (10), and add in the new point (21):

Running sums like this are called accumulators.

Note that we only needed to do one subtraction and one addition to maintain this accumulator (and then a division when we actually need an average). Most other FIR filters can not be computed using an accumulator, and they must be re-calculated from scratch over the whole window for every new point received.

Uniswap TWAP

Moving averages form the basis of how TWAP price oracles are built on Uniswap. In order to prevent short-term price spikes from drastically affecting the observed price, the price should be smeared over time.

When a big trade happens, it moves the price far from the market value. Under the assumptions of a live blockchain (anybody can submit transactions) and the efficient market hypothesis (rational actors will quickly arbitrage price differences away for profit), the price will soon return to near the original value if it is consistent with the wider market. In this case, a moving average protects observers of the price oracle from being overly impacted by any temporary off-market prices.

If the Uniswap contract had the entire history of prices available, the trivial way to compute a moving average would be to loop over every second in the desired interval, sum up the prices, and divide by the interval’s duration. However, this would require a prohibitive amount of gas, both to store the previous values and to compute the sum.

Instead, Uniswap 2 stores a running sum of the prices since the pair was created as an accumulator: Every second the running sum is increased by the value of the price at that time (Uniswap 3 is slightly different — see below).

The contract obviously can’t wake up every second to add the current price to the sum so a bit of bookkeeping needs to happen whenever a trade occurs (and whenever the running sum is queried). Since the contract knows how long it’s been since the previous trade, and that the price level has been unchanged during that time, it’s just a matter of multiplying this duration by the price level and adding that product onto the running sum.

Doesn’t keeping a running sum like this result in big numbers? Well, yes, but the EVM word size of 256 bits can represent very big numbers.

Price averages from TWAP

If we compare it to a conventional moving average, Uniswap’s ever-increasing running sums represent a window from the beginning of time up to the present. In most cases that is not useful. In order to get price averages over shorter windows, we need to use a similar method to the recursive technique described above.

Let’s consider an example. Suppose the following is a plot of the price on a Uniswap pair over time:

Notice that the graph is a series of steps: When a trade happens, the price immediately jumps to the new price, and in between nothing is happening so the price is flat.

If we take the integral (sum up the price over time), we get the following:

The sum is always increasing (prices are always positive), and the slope (how fast it’s increasing) depends on the price at that point in time. So at every point this running sum represents the area of the entire prices summed up since the beginning of time (well, pair creation).

To find the area over an interval, we can take two points of the running sum and subtract them:

By taking two points of the running sum and subtracting them, we get the area of the price graph between the two corresponding points in time, called a window. Since this area is the sum of the price for every second during that window, dividing by the number of seconds gives us the average price within that window, which is the moving average we desire.

Flash loans

Moving averages smear out temporary blips in data. In some situations this is quite desirable: Smart contracts that access prices should not see price spikes caused by large trades if they are quickly returned to the prior level by the force of arbitrage.

As described in the previous article, flash loans are large uncollateralised loans that must be repaid within the same transaction they are issued. If a contract simply uses the current price of Uniswap as an oracle, it is simple to use a flash loan (or in fact any other source of capital) to manipulate this price: An attacker takes out a flash loan, which is used to move the Uniswap price significantly, and then calls into the victim contract. The contract then reads the manipulated price and performs some action beneficial to the attacker. After the victim contract’s execution finishes, but before the transaction completes, a trade in the opposite direction is made, allowing the flash loan to be paid back at minimal expense.

In a sense, you can think of a price blip caused by a flash loan as being an impulse that lasts for 0 seconds. Since it has a width of 0, it contributes nothing to the moving average, which means that flash loans cannot be used to manipulate TWAP-based pricing oracles.

Window Sizes

Once we’ve decided to use a moving average to smooth out prices, the next decision to be made is how long the averaging window should be.

Too short a window and arbitrageurs may have insufficient time to smooth out price blips. Too long a window and the prices will take too long to reflect long-term “legitimate” market movements.

Uniswap’s accumulator design allows us to use TWAP windows of any duration which is necessary because different applications and/or pairs may need their own custom window sizes. Furthermore, the appropriate window sizes may change over time.

Geometric moving averages

Up until now we’ve been using the conventional definition of “average” that uses the sum of the prices: the arithmetic mean. However, Uniswap 3 uses a slightly different averaging method known as the geometric mean. If the window size in seconds is N, then instead of summing up the prices at each second and dividing by N, the geometric mean multiplies together the prices at each second and takes the Nth root.

The most important reason to use the geometric mean is because it has the nice property where the average of the inverses is equal to the inverse of the average.

In Uniswap 2, which used the conventional arithmetic mean, separate accumulators had to be maintained for the two trading pairs serviced by a pool (tokenA denominated in tokenB and vice versa). With Uniswap 3, it is enough to maintain just one accumulator, cutting down the number of storage writes needed and saving users gas.

Best of all, geometric moving averages are also FIR filters that can be computed recursively, using multiplication and division instead of addition and subtraction.

The geometric mean does, however, have properties that are different from the arithmetic mean.

Suppose you have 20 meters of fencing. What shape should you build in order to maximise the area of a rectangular enclosure?

Naturally you would build a square. Any deviation from that would result in a smaller area.

When all the prices are equal in a window, then the arithmetic and geometric averages are equivalent. However, in any other case the geometric mean will be less than the arithmetic mean.

That said, in most cases the difference is minor. For example, the 4 by 6 meter fence has an area of 24, which isn’t too far from the maximum of 25.

To see how this impacts real world pricing data, we downloaded the trading history for the DAI/WETH pair on Uniswap 2, and plotted both the arithmetic and geometric 30 minute moving averages:

The arithmetic mean line isn’t visible because the geometric line is drawn over top of it. To actually see the difference, we need to zoom in to periods with rapid price movements:

Although Uniswap 3 has some other differences that may affect this plot, such as less granular tick sizing, it doesn’t appear as though the change to geometric averaging itself will have a substantial impact on TWAPs.

Conclusion

Euler builds upon Uniswap’s time-weighted average price (TWAP) oracles to allow users to lend and borrow almost any fungible token. TWAP oracles help to smooth out abrupt price movements and always converge on the long-running average price after a period of time. On a decentralised lending protocol such as Euler, this has the positive effect of limiting users from being liquidated in the event of sudden shocks to the price that are later corrected through arbitrage. This includes protection against extreme temporary price movements enabled by flash loans, which have famously been used to attack other DeFi protocols.

About Euler

Euler is a capital-efficient permissionless lending protocol that helps users to earn interest on their crypto assets or hedge against volatile markets without the need for a trusted third-party. Euler features a number of innovations not seen before in DeFi, including permissionless lending markets, reactive interest rates, protected collateral, MEV-resistant liquidations, multi-collateral stability pools, sub-accounts, risk-adjusted loans, and much more. For more information, visit euler.finance.

Join the Community

Follow us on Twitter. Join our Discord. Keep in touch on Telegram (community, announcements). Check out our website.