A Tale of Gas and Approximation (part 3)

The final chapter of our gas exploration ending with the analysis of Uniswap V3 and a few words on generalized gas functions

Chapter 3 - Concentrated liquidity is not cheap

Introduction

In this third and final article we will analyse concentrated liquidity implementation with Ekubo and MySwap CL. Both of them have their own challenges, but we will see that we can still approximate their behaviors quite accurately. Another very interesting aspect of this analysis is that we do not have access to the latest version of the code, so we treat both implementation as black box, trying to infer what is happening based on the observed simulations.

---

Ekubo

So far, the cases we've considered have had quite trivial functions as expected due to the fact that Uniswap V2 and Stable Curve are computationally simple models, which is no longer the case with the Uniswap V3-V4 implementation. Let's start by considering a few properties of the Ekubo exchange.

Concentrated liquidity may divide a swap into several steps depending on the current pool state. As a result, we expect our approximation to be a function of the number of steps or, more precisely, the number of ticks crossed during the swap.

Now, before we dive into the data analysis, there is the concept of a lock that is interesting to consider. Essentially, it works as follows: before doing anything on Ekubo, you need to return the lock to the core. Once this is done, you can use the different pools to perform swaps. However, these swaps are not immediately executed against the corresponding ERC20. Once you're done, you need to lock back the core, and to do so, you need to perform all the relevant transfers on the different ERC20. Now, what this means is that if during your swap sequence you zeroed out a change in one of the ERC20, you don't have to perform the transfer on that specific ERC20. Let's take an example.

Suppose you do a swap USDC → ETH → USDT starting with an amount X. Swapping on the first pool gives you Y ETH tokens out, which you immediately use again to get Z USDT tokens. The change of balance of the ETH would be zeroed out, and you would not have to perform any ETH transfers.

We've seen so far that transfers can be quite costly, so an interesting question to ask is: how much gas can be saved by optimizing the lock usage? Let's write the function for a direct swap on Ekubo, including the balance updates in full (i.e., counting the modified contracts). The first term is for the ERC20 balance updates, the second term accounts for any storage slot update on Ekubo's core, and the final term accounts for the computational part.

$$\begin{equation} G_{Ekubo}(pool) = (2_{ERC20}+2^{ERC20}_{Reserves})C+kC+f_{computation}(pool) \end{equation}$$

Now let’s generalize that function for swaps of the form $T_1 \rightarrow T_2 \rightarrow ... \rightarrow T_n$. We get the following inequality which is tight if all the pools we cross are distinct.

$$\begin{equation} G_{Ekubo}((pool_i)_{i \in \N})\leq(2_{T_1+T_2}+2^{T_1+T_2}_{Reserves})C+C_{lock}+\sum_{i \in \N}kC+f_{computation}(pool_i) \end{equation}$$

Let's now write the function where we assume that we don't have a lock mechanism (i.e., assume we lock after every trade). The inequality below is tight if the sequence of ERC20 and pools are all distinct.

$$\begin{equation} \begin{split} G_{Ekubo}((pool_i)_{i \in \N}) &\leq (1_{T_1}+1^{T_1}_{Reserves})C \\ &+ \sum_{i \in \N}C_{lock}+(1_{T_{i+1}}+1^{T_{i+1}}_{Reserves})C + kC+f_{computation}(pool_i) \end{split} \end{equation}$$

Consequently, in the worst case scenario where we have a route with N consecutive Ekubo pools, which are all distinct and each for a different ERC20 token, we might end up adding 2N additional storage slot updates.

However, the attentive reader might notice that there is a "catch" with this formula, and they would be absolutely right! Remember in the preliminaries we had a very similar case without a lock, where we stated that if two consecutive pools are not distinct from the perspective of the ERC20 token, then no state changes are induced in the ERC20 token joining the two pools. The reason for this is that since we are consuming the entire amount to transfer it to the next pool, the resulting balance would be zeroed out and no state update would occur.

Now, in general, this does not happen because AVNU does not allow a sequence of the form $P \rightarrow P$ because it doesn't make sense. However, with AMM that uses a singleton architecture, the pool is different from the point of view of the AMM, but the same address is used from the point of view of the ERC20. Therefore, in our sequence of tokens, the amount resulting from the swap on pool $P_i$ is fully consumed and swapped through the pool $P_{i+1}$. This means that the delta induced on the balance of the out token of the first pool is compensated by the fact that we reinject that same delta into Ekubo. Therefore, the real formula for a sequence of trades on Ekubo is the following.

$$\begin{equation} G_{Ekubo}((pool_i)_{i \in \N})\leq (2_{T_1}+2^{T_1}_{Reserves})C+\sum_{i \in \N}C_{lock}+kC+f_{computation}(pool_i) \end{equation}$$

Which, assuming that $C_{lock}$ is small, is approximately equal to the one where we lock after each step. We ran a few experiments with different routes and with/without the lock mechanism, and the gas cost used increased by roughly 50 units of gas per lock.

Consequently, we think that there is no optimization to be gained in using the lock mechanism, at least for swap operations. Additionally, in cases where the next hop uses something different from Ekubo, we will have to lock the core anyway.

Contrary to the other implementation, we state that we expect the computation cost to be tied to the number of ticks crossed, so we directly plot our data based on that observation. The data presented below has been generated by executing trades of different sizes on different pools. For each trade, we recorded the number of ticks crossed along with the gas used, from which we subtracted the usual base cost induced by a transaction.

First, let's consider the intercept. We see that there is a base cost of roughly 8k gas, which we can partly explain if we assume that at each swap, we update the current tick, the price, and potentially the liquidity (which might also explain why we have multiple values without any crossings). Additionally, it would be fair to assume that variables related to the reserves and the fees are updated since we can find the functions returning these values in the ABI.

However, what's more interesting is the linear relationship between the number of tick crossed and the gas used, as well as the asymptotic behavior we see in some cases. Starting with the linear increase, we see that it roughly corresponds to 2 storage slots updated plus some computation. If we think about the discussion we had about the lock, we see that crossing ticks are quite expensive compare to the rest ! We can also conclude that pools with more liquidity should be cheaper to use.

Regarding the asymptotic behavior, if we contrast the increase with the typical increase coming from crossing a tick, we see that this is probably only a computational cost. These patterns might be due to giving a price limit or a skip_ahead value too large, which are both swap parameters specific to Ekubo. There is a clear trade-off between slippage and the value of the price limit, and there are some optimization concerns when choosing the skip_ahead, but this does not matter for our task at hand.

In light of the preceding discussion, we see that our Ekubo function should take the following form:

$$\begin{equation} G_{Ekubo}(pool) = (1_{Ekubo}+5^{Ekubo}_{Variables})C+A+2Cf(pool)) \end{equation}$$

We can optimize the parameters by fitting the above function to the data, which gives us the following predictions once plotted.

---

MySwapCL

We have now reached our final implementation, and we hope you have enjoyed the journey so far!

MySwap CL is also a concentrated liquidity AMM with the same single contract approach as Ekubo, but they do not have the locking mechanism, and they do not expose a "skip ahead" parameter in the swap function. With that in mind, let us directly plot the simulation data.

Immediately, we see some interesting patterns. First, like Ekubo, we observe a linear relationship between the number of ticks crossed and the same asymptotic behavior when there is no reachable liquidity. However, unlike Ekubo, there appear to be two distinct patterns that could be described by two affine functions with the same intercept but different slopes. Looking at the token pairs involved does not help us understand why the AMM behaves differently. If we were to estimate the difference in slopes, we would find a delta of approximately one storage slot update. We investigated a few hypotheses, such as it being related to the number of initialized positions and this having an impact because the next tick was found using a version of binary search, or that the tick spacing was involved, but nothing was very conclusive.

Consequently, we decided to see if we could still find a good fit for our parameters using a similar form to the function used for Ekubo, and this is the result of our approximation model, which is quite satisfactory for a first model.

---

Evaluation

The goal of this article was to cover an approach to gas estimation and to shed light on some of the details that go into computing the resources used by the execution of a contract. However, for the sake of completeness, here is the result of our full approximation model. The values shown on the graph are the gas cost in dollars, simulated versus predicted. The blue dots are the values predicted by our old model while the new model predictions are represented by the orange dots.

---

Conclusion - Generalized Gas Functions

In the preceding sections, we took a deep dive into the gas usage of different contracts and tried to derive an approximation function for the gas used by the swap methods. We have seen that for these implementations, two terms are weighted in the balance: one related to the induced state update and one related to computation. We have also noticed that most often, the cost is dominated by the pricing of the state change and not the computational ones. Throughout this article, we have built intuition about the gas model of Starknet and have managed to closely approximate the real gas cost using a simple function. However, we have also seen that doing this work required a lot of data analysis, manual manipulations, and intuition, and there are more complex scenarios where this approach might be very difficult to implement.

Gas is ubiquitous to any blockchain, and even if L2 promises are to be cheaper than L1, it still remains expensive, which means that it is important for dApps to minimize the gas required by their contracts. Unfortunately, developers do not have access to tools that help them in this endeavor.

However, let's take a step back and consider what we have been doing in this article. Once we understood the different aspects playing a role in the pricing, we proceeded by deriving a mathematical model using our intuitions that we have refined by simulating the code and fitting our model to these observations. We claim that this approach can be automated.

Wouldn't it be awesome to have a tool capable of deriving such a function based on an implementation? It would open up a whole new world of possibilities for blockchain developers. For example, one could derive the characteristic function for the current implementation to see the current gas usage. Then, it could try to reduce the gas cost by changing the code and regenerating the new characteristic function, checking if it lower-bounds the original one. As we have seen with Ekubo, these functions give a lot of insight into understanding the complexity of a contract and the major factors driving the gas cost.

Additionally, it could also directly be part of the ABI so that developers know what to expect when calling a given contract. They could for example, depending on the inputs, decide to use one method or another depending on the approximated gas cost. Finally, that same function could be exported in an off-chain backend to improve the user experience when deciding on the best execution flow (for ex. executing intent).

Using a combination of SAT solvers and program flow analysis, we claim that such functions could be automatically derived, as it has been done for network functions in the PhD thesis “Latency Interface for Systems Code”. Note that in general, this type of automated analysis are not suited for Turing-Complete language, however, computation on Starknet are naturally bounded by the gas cost which is a property the Sierra IR takes advantage of to make every program provable. Therefore, we think that for the same reasons automated analysis could be amenable to Cairo program. This would bring gas cost directly into the realm of Cairo programmers, supporting a new form of gas-aware development that, we think, would drive down the overall gas cost of using dApps.