Great Artists Steal. And Optimize: TWAMM Gas 💰⬇️

Introduction

Previous articles in this series focused on Time-Weighted Average Market Maker (TWAMM) gas usage relating to operational parameters [1] and an efficient algorithmic approximation [2].

This article presents gas and reserve measurements for low-level design optimizations of the reference TWAMM design [3], including a significant TWAMM specific storage optimization alluded to in [2]. It concludes with a comparison to FRAX’s current mainnet TWAMM implementation [4].

The results of combining the TWAMM approximation discussed in [2] and the TWAMM specific storage optimization quantified herein, offers gas savings nearly 25% on average and over 40% for some peak measures.

Optimizations

It is shown in [2] that optimal computational efficiency for TWAMM is when the FRAX approximation is used over the original Paradigm TWAMM algorithm. Thus the original reference TWAMM design [3] was modified to use the FRAX approximation, greatly simplifying arithmetic and allowing the removal of PRB Math [5] fromInt and toInt scaling calls in much of the design. This modified design is referred to throughout this article as the updated reference design.

Eight phases of gas reduction optimizations were then applied to the updated reference design:

  • Optimization 1
    • Replacing the PRB Math UD60x18 [5] number format with the UQ112.112 format [6] throughout the design.
    • This alters the numerical range and resolution of variables in the design, notably the reserves, from the properties of the PRBMathUD60x18 to the UQ112.112 number format shown in Table 1 below:
Table 1: Properties of the PRBMathUD60x18 and UQ112.112 number formats.
Table 1: Properties of the PRBMathUD60x18 and UQ112.112 number formats.
  • Optimization 2
    • Replace multiplication and division with arithmetic shifts where possible.
  • Optimization 3
    • TWAMM specific storage optimization.
    • This optimization significantly reduces TWAMM’s storage of state for every block interval. Gas savings increase as the number of intervals between calls implying virtual order execution increases.
    • This imposes new restrictions in specific contexts, requiring numerical analysis and tuning to be presented in a forthcoming article.
  • Optimization 4
    • Bit-packing of swap-direction and order ID into one 256-bit data-word.
    • This reduces the maximum order ID from 2^256 - 1 to 2^255 - 1.
  • Optimization 5
    • Replace reserve value map with a reserve struct.
    • Refactor optimization 3 operations into functions.
  • Optimization 6
    • Bit-packing of Order Block Interval (OBI) with reserves.
    • Remove redundant OBI and token address storage from LongTermOrdersLib.
    • This limits OBI from 1 to 65535 blocks.
  • Optimization 7
    • Convert LongTermOrder and OrderPool from “storage” to “memory” in execute virtual orders loop.
  • Optimization 8
    • Remove unnecessary type casts from optimization 3.

Numerous additional optimization possibilities were explored, but measurements revealed that they degraded gas performance unacceptably.

Gas Measurements

Tables 2, 3, and 4 below present the measured minimum, average, and maximum gas usage, respectively, for designs implementing each of the numbered optimizations applied incrementally (i.e. the optimization phase 3 design also contains optimizations 1 and 2). The incremental gas savings is presented between phases (for phase 1, the updated reference design is the comparison baseline).

The gas measurement methodology is described in Appendix A; it has been updated to correct an error discovered in [2]. The benchmark design configuration is identical to the one presented in Appendix B of [2]. Contracts compiled with Solidity Compiler 0.8.10 and pool OBI set to 10.

Table 2: Minimum measured gas use for contract methods with incremental percentage savings from previous optimization phase.
Table 2: Minimum measured gas use for contract methods with incremental percentage savings from previous optimization phase.
Table 3: Average measured gas use for contract methods with incremental percentage savings from previous optimization phase.
Table 3: Average measured gas use for contract methods with incremental percentage savings from previous optimization phase.
Table 4: Maximum measured gas use for contract methods with incremental percentage savings from previous optimization phase.
Table 4: Maximum measured gas use for contract methods with incremental percentage savings from previous optimization phase.

Tables 5, 6, and 7 below show net gas savings (instead of incremental savings shown in tables 2-4) of the updated and optimized designs compared to the original reference design. Comparing the measurements of the original and updated reference design shows the effect of removing scaling calls and applying the TWAMM algorithm approximation.

Table 5: Minimum measured gas use for contract methods with net gas savings over original reference design.
Table 5: Minimum measured gas use for contract methods with net gas savings over original reference design.
Table 6: Average measured gas use for contract methods with net gas savings over original reference design.
Table 6: Average measured gas use for contract methods with net gas savings over original reference design.
Table 6: Maximum measured gas use for contract methods with net gas savings over original reference design.
Table 6: Maximum measured gas use for contract methods with net gas savings over original reference design.

Table 8 shows the total gas used for all design method calls and presents the savings as a percentage of the gas reduced from that used by the original reference design:

Table 8: Total gas used for all design method calls (* excludes approvals and transfers) with percent savings of the updated and optimized designs relative to the reference design.
Table 8: Total gas used for all design method calls (* excludes approvals and transfers) with percent savings of the updated and optimized designs relative to the reference design.

A significant improvement in gas usage is demonstrated in the results of tables 2-4, with an average savings approaching 25% as shown in table 8. The largest improvements occur in the maximum measured gas figures for each function. Optimization phase 3, the TWAMM specific storage optimization, contributes the largest improvements to average and maximum measured figures, followed by the order ID bit-packing of optimization 4.

The measured figures heavily depend on stimulus from the benchmark test configuration, specifically the Long Term (LT) Swap scenario of the TWAMM Pool (see [1] for definition and explanation), blocks of pool inactivity prior to calling contract functions, and the OBI value. As presented in [1], pool inactivity and OBI directly impact the execution of virtual orders, which all methods undergoing measurement depend upon.

Different benchmark configurations will yield different results and can be manipulated to present advantageous figures. The benchmark configuration used in this test tries to approximate reasonable expected market activity in a 2000 block period while exercising all contract functions. While real world activity will differ, the results here are sufficient to demonstrate that the optimizations can be expected to generally improve gas use with some minor exceptions (see phase 5 and 7 of table 3).

Optimizations 3 and 7 offer increased gas savings with increasing pool inactivity, however optimization 3 is still beneficial when this is not the case--this is borne out by its improved savings figures for minimum measurements not seen with optimization 7. An improved understanding of realistic market activity for TWAMM will help drive future decisions around optimization phase 7, which the data shows to be detrimental for minimum measured gas use, specifically the regular swap and withdraw methods. At this juncture, the improvements seen in the average and maximum measurements for these methods and this optimization have resulted in optimization 7 being retained.

The total gas use figures presented in Table 8 show that the optimized design reduces gas use nearly 25% on average, largely due to optimizing data stored on chain by the TWAMM algorithm. This differs from the FRAX TWAMM algorithm approximation, which reduces gas use by optimizing computational efficiencies.

Numerical Measurements

As noted for optimization 3, detailed numerical analysis, tuning, and handling of limitations is required prior to deploying this solution. However, a comparison of the difference between the measured reserves for the benchmark test can be used to quickly gauge any egregious effects to the behavior of the pools resulting from the optimizations.

Figure 1: Measured reserve value differences from the reference design for the updated reference and optimized designs.
Figure 1: Measured reserve value differences from the reference design for the updated reference and optimized designs.

Figure 1 shows the optimized design more closely tracks the original reference design until simulation block offset 900. The differences in results for both the updated and optimized designs likely arise from the untuned use of the TWAMM algorithm approximation. However the optimized design likely achieves a closer result until block offset 900 because of the higher fractional fidelity of the UQ112.112 number format it uses (see resolution comparison in Table 1). Between block offset 900 and 1750, the optimized design differences become larger than the updated reference design, improving again after block 1750. This is likely due to optimization 3 and will require further numerical analysis and tuning. Additionally, it should be noted that updated reference design results of Figure 1 suggest that numerical analysis and tuning of the TWAMM algorithm approximation is also required.

Figure 2 plots the price of pool token B in terms of token A, providing a more intuitive perspective of the numerical effects of the optimized design. The optimized deviates more than the updated reference design between block offset 950 until around 1700 where it begins to more closely follow the original reference design.

Figure 2: Measured Token B price comparison for original reference, updated reference and optimized designs.
Figure 2: Measured Token B price comparison for original reference, updated reference and optimized designs.

Further analysis and tuning is needed with a longer simulation which showcases the longterm effects of any errors introduced. Unlike a closed system, arbitrage will likely correct the error introduced, however it is important to minimize this error to preserve the advantages of TWAMM over a Constant Product Automated Market Maker (CPAMM) for large swaps and in an environment with insufficient arbitrage.

Mainnet FRAX TWAMM Comparison

The comparisons in the previous section are academic as none of the contracts are live on mainnet. Fortunately, FRAX has deployed a TWAMM contract on mainnet that can be compared against.

FRAX TWAMM Contract Differences

The FRAX TWAMM contract [4] significantly differs from the other designs discussed in this article, particularly in the following respects:

  1. It does not use block intervals, but instead uses time intervals of 3600s, 1 hour. Assuming average Ethereum block times of 14s, the approximate OBI is 257.
  2. It uses the UQ112.112 number format, but truncates the 112 fractional bits to efficiently store two reserve values in a single 256-bit data-word.
  3. It is built atop a Uniswap V2 Automated Market Maker (AMM) [7], implementing ancillary functionality of that AMM, not featured in the designs discussed in this article. For example it implements a Time Weighted Average Price (TWAP) feature.
  4. The interaction model for providing liquidity and swaps differs from the designs discussed in this article, requiring users or interfacing software and contracts to perform transfers and then invoke contract methods.

These design differences will result in significant gas use differences. The purpose of any comparison is to get a sense of where the optimized design herein stands relative to a live contract regarding gas usage and numerical accuracy.

Benchmark Test Setup

The benchmark test was modified to operate on the original reference and optimized designs with their OBI set to 257, accounting for the 3600s virtual order execution interval used by the mainnet FRAX contract.

Additionally, the benchmark test driver was adapted to work with the FRAX TWAMM contracts differing function names, signatures, and use models.

Gas Measurements

The table below shows the optimized design gas use is on the order of the FRAX TWAMM contract, consuming 20% - 50% less gas in the benchmark test.

Disclaimer: It is important to note that these measurements in no way take away from the FRAX TWAMM implementation; as noted it is performing operations beyond those TWAMM operations being measured implicitly, (i.e. TWAP oracle etc.).

Table 9: Gas comparison for contract functions of optimized design and FRAX TWAMM contract [4] driven by benchmark design.
Table 9: Gas comparison for contract functions of optimized design and FRAX TWAMM contract [4] driven by benchmark design.

The optimized design gas usage measured will likely increase as it is readied for production, due to the planned contract modifications in the below section on future work.

Numerical Measurements

Figure 3 and 4 compare the FRAX design and optimized design reserves and token B price, respectively, to the original reference design with OBI set to 257.

Figure 3: Measured differences between the reserve values of the FRAX TWAMM and optimized designs with the original reference design with OBI set to 257.
Figure 3: Measured differences between the reserve values of the FRAX TWAMM and optimized designs with the original reference design with OBI set to 257.
Figure 4: Measured Token B price comparison of FRAX TWAMM and optimized designs with original reference design with OBI set to 257.
Figure 4: Measured Token B price comparison of FRAX TWAMM and optimized designs with original reference design with OBI set to 257.

The figures reveal that the FRAX contract tracks the behavior of the original reference design more closely, especially after block 800. Notably, the FRAX implementation introduces additional scaling that might be related to the differences seen in the updated reference and optimized designs from the original reference design. These comparisons highlight the need for analysis of the numerical performance and accuracy of the optimized design in coming development cycles.

Conclusion

Design optimizations beyond the FRAX TWAMM algorithm approximation were applied to the reference design and demonstrated a significant reduction in gas use, averaging gas savings of nearly 25%.

A comparison with the production FRAX TWAMM contract showed that while gas use of the optimized design was favorable, additional work on numerical accuracy and performance is required to ensure the optimized design tracks the reference TWAMM implementation more closely, ensuring the slippage advantage over CPAMM is maximized.

Future Work

  • Numerical analysis and tuning of the TWAMM specific storage optimization and TWAMM approximation algorithm.
  • Adapting the design to use an underlying Balancer Vault CPAMM.
  • Conversion of the system from block-based intervals to time-based intervals will be considered, exchanging increased design complexity and possible gas usage for the following benefits:
    • Cross-chain compatibility
    • Intuitive contract interface (humans think in time, not blocks).

References

  1. “Time Weighted Average Market Maker Operational Parameters vs. Gas Usage Analysis”, March 2022. Online. Available: mirror.xyz/0slippage.eth/5zKJW4Zx9zYHpB4jNln16HuU8d8EtawmA17usNfIje4. Accessed: May 1, 2022.
  2. “TWAMM Algorithm Optimization & Approximation Analysis“, April 2022. Online. Available: mirror.xyz/0slippage.eth/5zKJW4Zx9zYHpB4jNln16HuU8d8EtawmA17usNfIje4. Accessed: May 1, 2022.
  3. TWAMM (2021). Online. Available: github.com/FrankieIsLost/TWAMM. Accessed: May 1, 2022.
  4. frax-solidity Uniswap_V2_TWAMM (2022). Online. Available: github.com/FraxFinance/frax-solidity/tree/master/src/hardhat/contracts/Uniswap_V2_TWAMM. Accessed: May 1, 2022.
  5. Paul R. Berg, PRBMath (2021). Online. Available: github.com/paulrberg/prb-math. Accessed: May 1, 2022.
  6. Q (number format) (2022). Online. Available: en.wikipedia.org/wiki/Q_(number_format). Accessed: May 1, 2022.
  7. H. Adams, N. Zinsmeister, and D. Robinson, “Uniswap v2 Core”, March 2020. Online. Available: uniswap.org/whitepaper.pdf. Accessed: March 9, 2022.

Appendix A: Gas Measurement Methodology

Two measurement methodologies are presented in [2], a high-level and isolating methodology.

Unfortunately The high-level methodology suffered from a bug where the gas from transfers and approvals related to a transaction were each counted as the type of transaction. For example for “i” swap transactions, the average gas computed would be:

Equation 1: Incorrect Average Gas Computation for Tested Swaps.
Equation 1: Incorrect Average Gas Computation for Tested Swaps.

One way to correct the bug would be to remove the multiplication by 3 in the denominator; this would result in the average gas for a swap including the gas used for related transfers and approvals. However, the high-level measurements in this post exclude the transfer and swap gas use to isolate the swap call gas usage:

Equation 2: Average Gas Computation for Tested Swaps, Excluding Transfer and Approval Gas Usage.
Equation 2: Average Gas Computation for Tested Swaps, Excluding Transfer and Approval Gas Usage.
Subscribe to 0slippage
Receive the latest updates directly to your inbox.
Verification
This entry has been permanently stored onchain and signed by its creator.