🔍Algorithm Analysis

Update 5/7/2022

Unfortunately, a measurement error methodology was discovered for the non-isolating gas measurement in this article (approval and transfer figures were mixed in with contract function data). Please refer only to the isolating methodology measurements in this article. For more information consult Appendix A of the article Great Artists Steal. And Optimize: TWAMM Gas 💰⬇️, which addresses the issue and presents an improved methodology. The incorrect data is labeled “Ignore, consult update 5/7/2022” below.

An exciting new TWAMM algorithm approximation has been released by FRAX in [1]. The original TWAMM algorithm published by @FrankieIsLost in [2] and its optimizations of it are compared to the FRAX approximation herein, focusing on gas usage with a preliminary look at numerical differences.

The approximation gas usage results in isolation are nearly an order of magnitude improvement, both estimated and measured. This post lays the groundwork for an upcoming post of work that builds upon the FRAX approximation with a novel TWAMM-specific optimization that may reduce gas usage a further 30% (relative to a coarse analysis of the original contract’s iteration gas usage).

Background

TWAMM Algorithm in this context refers specifically to computation in a TWAMM pair with active Long-Term (LT) swaps in opposing directions (Tokens A to B and vice-versa). Refer to [3], specifically Figure 3.0 and the section “Long-Term (LT) Swap Scenarios” for a detailed explanation.

The original TWAMM Algorithm [4] has been numerically compared by the FRAX team using Desmos in [5] to their approximation. The original TWAMM algorithm in that comparison is:

The FRAX approximation presented in that comparison is:

Examining equations 4-5, immediate intuition about the system operation can be developed:

The TWAMM pool’s next Token B reserves are computed by multiplying the amount of current Token A reserves, by the ratio of updated reserves of Token B to Token A after executing a TWAMM iteration. The updated reserve values are obtained by adding the current reserve values of Token A and Token B to a_in and b_in, respectively. (Values a_in and b_in represent the amount of each token being sold into the pool at the current iteration.)

TWAMM Approximation Explanation

The TWAMM approximation of equations 4-5 is much simpler than the original algorithm, equations 1-3, especially to those familiar with update equations for a Constant Product Automated Market Maker (CPAMM). While it is unknown how this approximation was arrived at or derived by the team at FRAX, it might be explained as follows (for simplicity, fees are ignored).

In a given AMM, the token price can be expressed as a ratio of the token reserves. Consider a pool containing 100 token A and 1000 token B, the price of token A in units of token B is:

The FRAX approximation appears to be using the token price equation to compute new reserve prices for two or more concurrent long-term swaps that have changed token A and token B reserves simultaneously. This is very similar to CPAMM reserve update calculations, except in this case both reserve values are changed in the price equation simultaneously. This differs from CPAMM, where only a single reserve value is changed in the price equation. To illustrate this, consider the CPAMM update equations for a swap from A to B tokens:

Equation 9, above, features the token price equation, equation 6, with only one of the reserve amounts changed from the start of the swap (sequence index n+1):

If the scenario is now changed to allow both token A and B to be swapped simultaneously, then it is possible to derive the FRAX approximation (equations 14-15) by re-applying the token price equation with both reserve values changing to account for both token A and B selling into the pool:

Estimating Gas Use

Comparing equations 1-3 and 4-5, shows the approximation has far fewer arithmetic operations. Even applying simple common factor optimizations to equations 1-3 as shown below, will not bring the number of arithmetic operations significantly closer to the approximation:

A coarse estimate of the gas used by all three algorithms can be obtained by counting the individual arithmetic operations and multiplying them by the average gas used for each. For comparison purposes, measurements for average gas per operation are obtained from the numeric library PRBMath [6]. The estimate is presented below in Table 1:

Table 1 estimates that the FRAX approximation offers nearly an order of magnitude in gas savings!

Approximation Tradeoffs?

The investigation in [5] uses Desmos to compare the results of the original algorithm and approximation for different initial reserve amounts and LT swap amounts. Figure 1 below was adapted from [5]; it compares resulting reserves using both computation methods for 100 token A and B initial reserves and a constant 10 token B sold, while a sweep of 0 to 100 of token A is sold:

In Figure 1 it appears that the approximation tracks the original TWAMM algorithm closely, deviating the most as the largest amounts of token A are traded. Note that selling 100 of token A to the pool in a single iteration when the reserve is about 100 token A is an unusual scenario with high slippage. In practice, it is expected that the amount sold to the pool each iteration would be a small fraction of the reserve, and slippage would be mitigated with arbitrage.

However, the extreme case is useful to illustrate that the approximation appears to retain more token A than the original algorithm and less token B. This implies that LT swaps from B-A will net fewer tokens in pools using the approximation; conversely, LT swaps from A-B will net slightly more tokens in pools using the approximation (the amount each swap user receives is a difference from the previous reserve, hence the disparity).

A closer inspection of regions of the graph between more reasonable values for the amount of token A sold is consistent with the observation above for the benefits to users swapping in one direction over the other. It is left to the reader to interact with the investigation in [5] to evidence this.

Measuring the Differences

To complement the preceding estimations and analysis, the TWAMM approximation algorithm has been integrated into the contract implementation in [2]. This facilitates gas and numerical measurements in isolation, eliminating other differences from FRAX’s TWAMM contract implementation.

The common factor optimization is omitted from further discussion and measurement because the gas savings it offers are far less than the approximation algorithm.

Gas Measurement Methodology

High-level gas measurements of public contract methods are made using the methodology described in [3]. This method has been improved upon to feature a constant length pool deployment and configuration phase, preventing any measurement discrepancies from the previous auto-mining configuration used (start block affects calculations within execute virtual orders).

A second gas measurement methodology to isolate the TWAMM algorithms is also employed in the data presented below; this method computes the difference between cumulative gas used at the end and start of algorithm execution.

Regression Test Results

As a safety net, the tests from [2] have been used to qualify each implementation. The approximation implementation shows an additional ~0.5% error in one of the LT swap assertions:

This may be related to scaling or other implementation tuning facets, beyond the scope of this paper. The code for the approximation algorithm implementation appears in Appendix A.

Benchmark Test Results

A tool for creating benchmark tests was created for this project. The configurable tool generates repeatable event test vectors, allowing details as high as the overall test length and as low as the standard deviation of swap amounts to be configured. Further discussion of this tool is out of the scope of this paper, however, the benchmark configuration appears in Appendix B.

Gas Measurements

The measured minimum, maximum, and average gas use appear in table 2. These measurements confirm that the TWAMM approximation consistently improves gas usage in varying conditions over the original algorithm.

To compare the measured results to the estimates of table 1, the isolating gas measurement methodology must be applied. The measured results using the isolating method for the benchmark test appear in table 3, confirming earlier estimations presented in table 1, clearly showing the approximation reduces gas use by nearly an order of magnitude.

Numerical Measurements

A large-scale numerical analysis of the different implementations is beyond the scope of this paper. However, it is possible to perform a simple comparison using the reserve numbers of each of the different algorithm’s TWAMM pools, captured after each block’s transactions are executed.

Figure 3 shows the measured error between the reserves produced using the TWAMM original and the approximation algorithm integrated into [2]. The error is measured in tokens with 18 decimal places of precision.

Disclaimer: The results in figure 3, in no way reflect the performance of the actual FRAX TWAMM contract implementation. It is vastly different from the contract used in this study (see Notes section below for significant differences).

In figure 3, the error is very low until block offset 108, where the error starts to rise. At this point, there are three active LT swaps with one in the opposing direction, B → A. Another LT swap from B → A at block offset 141. The bumps that appear between block offset 148 to 154 are the addition and removal of liquidity--similar events can be seen further along the simulation near block offsets 293, 429, and 770. The simulation proceeds with an error of around 100 tokens until block 1089 when a series of LT swaps occur:

LT Swap B → A, block offset 1089
LT Swap A → B, block offset 1135
LT Swap A → B, block offset 1181

Many other events occur, but of interest are two provide liquidity events, which are not matched with nearby removals of liquidity; these occur at the following offsets and seem to cause acceleration in the growth of the error:

1184
1533
1672

It’s important to note that the error is the difference between two fixed precision implementations of an algorithm and an approximation; it’s unclear which is the source of error after so many transactions. More analysis is needed. These results do seem consistent with an aggregation of the difference shown in figure 1 between the original and approximation over many transactions.

It’s possible that these differences might be arbitraged out in practice and wouldn’t lead to the large growth in error seen towards the end of the simulation in figure 3. An arbitrageur’s perspective can be illustrated by viewing the price difference between the algorithms; figure 4 shows the price of token B measured in token A for each pool:

Conclusion

The FRAX approximation of the original TWAMM algorithm offers significant reductions in gas use while operating similarly numerically. Nearly an order of magnitude gas reduction and the elimination of costly square root operations makes the approximation extremely compelling. This became evident when trying to apply larger trade size scenarios to the original algorithm implementation, wherein the numerator in equation 1 needed to have the terms in the square root operation separated out to prevent exceeding the PRBMathSD59x18 precision, which led to transaction failures.

Future work includes integrating the approximation in our solution and combining it with a novel TWAMM-specific optimization that offers a slight tradeoff restricting LT swap orders in exchange for considerable gas use reduction. Look for a presentation of that work along with a more comprehensive numerical analysis using contracts closer to production readiness in the coming months.

Notes

The FRAX TWAMM implementation in [1] has numerous significant differences that were not explored in this paper, beyond optimizations, these include:

Implementation using UQ112.112 number format (see [7]), not the PRBMathUD60x18/PRBMathSD59x18 formats of [6] used herein.
Order block intervals converted into units of time, not blocks. Currently 3600 seconds per interval, approximately 250 blocks.
Underlying Uniswap V2 AMM implementation.