A Tale of Gas and Approximation (part 1)

Embark on a journey exploring Gas on Starknet to build the AVNU gas approximation model

Foreword

At AVNU, as we strive to offer the best execution, gas optimization is of utmost importance. Until now, our solvers have been using a simple approximation model to find the best route that maximizes the output while minimizing the gas cost. Today, we have decided to refine this model, and we have chosen to publish our approach publicly because we think that it might give ideas to blockchain developers on how to deal with this fickle resource that is gas.

In order to make the content easier to digest we decided to split our journey into a series of three articles. In the first, we will dive into the Starknet gas pricing equation and use it to understand how ERC20 transfers and approves are priced. We will also try to derive a formal model of AVNU that characterize a swap which will be used in the subsequent articles.

In the second article we will use the knowledge we've gathered to develop our gas approximation model, studying first Uniswap V2 and Stable Curve implementation with MySwap, JediSwap and SithSwap.

In the third and final article, we will finalize our model with the analysis of Ekubo and MySwap CL which are based on the Uniswap V3 model, allowing us to put all the pieces together to get the new AVNU gas approximation model.

Chapter 1 - Understanding Starknet Gas Pricing Equation

Introduction

Gas is at the core of any blockchain but remains mostly misunderstood. This is unfortunate, because it negatively impacts the experience users have with dApps and slows down the adoption of blockchains. It has an even bigger impact in DeFi where you might end up paying more in gas than the amount you traded for.

Today, on Starknet, the only way to know how much a transaction is going to cost you is through the RPC call “simulateTransaction” which will simulate your transaction and return the amount of gas used. Additionally, you can also access tracing information using the RPC call “traceTransaction” which will give you the computational cost of each internal calls. Unfortunately, neither of them allow you to easily understand what are the main drivers causing the gas usage to increase.

In the context of AVNU, we have solvers that are tasked to find the best execution possible for any given trade submitted by our users. In order to do that, they have to make a lot of decisions, for example to decide to user MySwap or JediSwap for a given trade and each decision they make incur a different gas cost, so it’s important that they have access to an oracle giving them the expected gas cost of each possible choice.

At first, it seems that we do have access to that oracle, because we said that one could get the gas used by a transaction using the appropriate RPC call. However, this will unfortunately not work for the following reasons. First, making such an RPC call will take approximately 2-3seconds before we get back the gas used. AVNU receives thousands of query every minute and our solvers are ran for thousands of iterations each where they try different combination of choices to get the best solution. To achieve the best UX possible, we have the constraint that the entire optimisation process shouldn’t take longer than 100ms on average (300ms being the upper limit), so it should be clear that using the RPC as the oracle in infeasible.

Actually, even if we had the ability to avoid the network calls and perform the simulation locally on a node, it would not be feasible in that time window and this is why we need another solution. We need an off-chain oracle with a near-constant query time that we can access thousands of time without increasing the time it takes our optimisation to execute. Therefore, we now turn our attention towards approximation model.

---

The “Not-So-Famous” Starknet Gas Function

The first step to understanding how computation is priced on Starknet is to consider the gas function given in the official documentation. [1]

$$\begin{equation} F = gas\_price * (\max_kv_kw_k+2c_w(n+m)+(3t+\sum^t_{i=1}q_i+2l)) \end{equation}$$

Where $\max_{k}v_kw_k$ prices the computation, $2c_w(n+m)$ prices the storage updates where $n$ is the number of contracts modified while $m$ is the number of storage slots updated. Finally, the quantity $3t+\sum^t_{i=1}q_i+2l$ prices L1↔L2 communication

In the context of AVNU, only the first two quantities are of interest as we do not perform any communication between layers. An important observation to make is that the storage update induced is priced according to the number of distinct contracts updated, as well as the number of distinct storage cells updated. To familiarize ourselves with the formula, we will start off easy-peasy by studying ERC20 approves and transfers because AVNU heavily relies on them.

---

The Price of ERC20

Let's start with the easy part, deriving the cost of an "approve" and a "transfer" on ERC20. The first question one may ask is - Are all ERC20 tokens comparable in terms of gas, i.e. do they cost roughly the same?

We would expect this fact to be true, at least for an "approve" and a "transfer," because the computational term in the gas function should be dominated by the state update term. In essence, there shouldn't be thousands of different ways to check that an "approve" or a "transfer" is valid before the state of the contract is mutated so we expect very little computation steps made by any ERC20.

Let's test that assumption and see what the real data tells us. The table below shows the gas used by an "approve" and a "transfer" for different tokens. Note that this is the gas used and not the gas price, which means that this value does not change between blocks. We also note that this value has been found by simulating these operations for amounts ranging from 0.1 to 70 ETH to see if the gas used remained constant, which it did !

ERC20	Approve	Transfer
ETH	3737	3737
USDC	4961	6191
USDT	4961	6191
DAI	4961	6191
WBTC	4961	6191
LORDS	4961	6191

First of all, apart from ETH, we can see that all the other tokens have very similar costs, which raises the question - Which tokens are using the same class? Using the above table, our hypothesis is that USDC, USDT, and WBTC probably use the same implementation, while the remaining three tokens use different implementations. We can validate our hypothesis by going on any block explorer and checking their class hash to confirm that this is indeed the case.

As a second observation, we notice that the ETH contract seems to cost much less than the others. There is actually a very simple explanation that relates to how the gas fees are paid, as we will see later. But first, let's see if we can find the cost of modifying a storage slot.

To do that, let's consider the original gas formula again. We can see that the state update term depends on the number of distinct contracts and storage slots updated. If we assume that the gas cost of both "approve" and "transfer" is negligible, we can create a transaction that bundles either two approves or two transfers with two different recipients to determine the cost of a single storage slot update. The reason is that, by doing so, we only increase $n$ by one in the gas formula, leaving the rest untouched as seen below.

Let’s introduce a function $f_{computation}$ which abstracts the gas used by the computation made by the ERC20.

$$\begin{equation} Gas(approve) = f_{computation}(approve)+(1_{ERC20} + 1_{StorageSlot})C \end{equation}$$ $$\begin{equation} Gas(approve + approve) = 2f_{computation}(approve)+(1_{ERC20}+2_{StorageSlot})C \end{equation}$$

Therefore, subtracting both values should give us roughly the value of $C$. In the table below, we show the gas used by performing each operation twice, and we display the difference between this new value and the original value where we only had a single operation.

Token	Approve + Approve	$\Delta$	Transfer + Transfer	$\Delta$
ETH	4993	1256	4999	1262
USDC	7440	1249	7447	1256
USDT	7440	1249	7447	1256
DAI	7425	1241	7432	1241
WBTC	7440	1249	7447	1256
LORDS	7431	1244	7438	1251

We see that in both cases and for every token, the values are roughly the same. If we extend our experiment to any combination of transfers and approves, we always observe that the added cost is a multiple of approximately $1249$. We can actually cross-check this value with the value used by the Blockifier, and we find that the exact value used is $2c_w=1224$. So, we see that the computational cost is indeed negligible.

In our model we decided to use the value $1249$ that we found to amortize the computational cost of the different ERC20 implementations as well as simplifying the computation of the gas used by the interacting with the ERC20. In the end this does not really matter as we will see in the next chapters.

Lemma: The cost of a storage slot update is approximately $C = 1249$.

As a corollary, we can define the functions pricing multiple transfers or approves initiated by the same account in multiple ERC20 in the same transaction. Let’s denote $recipients$ as the set of all recipients regardless of the ERC20, and $recipients_{ERC20} \subset recipients$ as the subset of recipients for the given ERC20.

Corollary (Approve Function)

$$\begin{equation} \begin{split} Gas_{Approve}(recipients) &= 1249 \cdot (1_{Nonce}+1^{ETH}_{User}) \\ & + 1249\sum_{T \in ERC20}(1_{T \neq ETH} + |recipients_T|) \end{split} \end{equation}$$

Corollary (Transfer Function)

$$\begin{equation} \begin{split} Gas_{Transfer}(recipients) &= 1249 \cdot 1_{Nonce} \\ &+ 1249\sum_{T \in ERC20 \cup \{ ETH \}}(1_{T \neq ETH}+|recipients_{T} \cup \{ User \}|) \end{split} \end{equation}$$

We are now ready to explain the difference in cost between ETH and the other tokens, which we said is related to how gas fees are paid. Indeed, for each transaction, gas fees are actually paid through a transfer injected by the StarknetOS on the ETH contract from the user to the sequencer. However, in the preceding section, we mentioned the property that the user does not pay for the change in balance of the sequencer nor the modification of the ETH contract as it is amortized across the block. So let's calculate the cost of a transfer in ETH and a transfer in USDC using our model.

$$\begin{equation} \begin{split} Transfer(A \xrightarrow{ETH} B) &= Gas(\{ B_{ETH} \}) \\ &= 1249 \cdot 1_{Nonce} + 1249|\{ B_{ETH} \}| \\ &= 3 \cdot 1249=3737 \end{split} \end{equation}$$ $$\begin{equation} \begin{split} Transfer(A \xrightarrow{USDC} B) &= Gas(\{ B_{USDC} \}) \\ &= 1249 \cdot 1_{Nonce}+1249|\{ A \}|+1249(1_{USDC}+|\{ B_{USDC}, A \}|) \\ &= 1249 \cdot 5=6245 \end{split} \end{equation}$$

Observe how in the first case, the balance of the user is only accounted for once. This reflects the fact that Starknet only cares about the final value of a given storage slot and not all the changes happening when executing the contract. We see that the difference comes from the fact that in the case of ETH, we don't count the contract as modified, and we also modify the same user balance twice, thus yielding a smaller cost than for other transfers. The same reasoning applies to "approves," and we get the same cost as a transfer in the case of the ETH ERC20, as we can see by writing the explicit formula.

$$\begin{equation} \begin{split} Approve(A \xrightarrow{ETH} B) &= Gas({ B_{ETH} }) \\ &= 1249 \cdot (1_{Nonce} + 1^{ETH}_{A})+1249|\{ B_{ETH} \}| \\ &= 3 \cdot 1249=3737 \end{split} \end{equation}$$

Another experiment we can do is to simulate a transaction with no calldata, which yields a cost of 2488 units of gas, which also agrees with our functions.

According to our model, we also see that the cost of an "approve" or a "transfer" is coming almost only from the cost of updating the storage slots. If the reader is interested, it can run two consecutive transfers on the same ERC20 with the same recipient to observe that the gas used barely increases. Indeed, in this experiment, we update twice the same storage slot so the added cost will only come from the computational aspect which allow us to conclude that our model is accurate.

Throughout this section, we’ve always considered the gas used without computing what is represented in terms of dollar. Obviously, the gas cost fluctuate throughout the day but we just wanted to have a rough idea, so we took the gas cost at block 457’686 and we computed that the cost of updating a storage slot is approximately ~0.14$.

A Formal model of AVNU

Now that we understand what will impact the gas price of a swap, we will build a formal model of an AVNU swap that we can relate to the original gas formula to understand how it will be priced. However, before diving in, we just define precisely define a few terms that we use to describe what AVNU does and that will appear throughout this article.

Definition (Pool): A pool is a contract that references two ERC20 tokens A, B and that support a method "swap" which allow anyone that own some amount of token A (resp. token B) to exchange it for some amount of token B (resp. token A) at a rate determined by the pool contract.

Definition (Path): A path is an ordered sequence of pools $(P^{T_i \rightarrow T'_i}_i)_{i \in \N}, T_i, T'_i \in Tokens$ such that for any two consecutive pools, we have $T'_i = T_{i+1}$. Furthermore, in the context of AVNU, a path cannot contain twice the same pool because it would not be efficient.

Definition (Route): A route is a collection of path $Path_1, Path_2,... Path_N$ such that for all paths the first pool start with the same token and the last pool end with the same token. Note that while a path cannot contain twice the same pool, a route can contain two paths with the same pool.

With these definitions in mind, suppose that a user wants to swap an amount X of token A for token B. The first step taken by AVNU is to find an optimal solution S for that trade, i.e., a route that maximizes the amount of token B received. A transaction will then be compiled based on the solution, ready to be sent to the chain for execution.

The execution is roughly performed as follows.

1. User “approve” X token A to be spent by the AVNU contract
2. Call “multi_swap” on AVNU contract.
  2.1 AVNU calls “approve” X token A to be spent by AMM contract
  2.2 AMM call “transfer_from” token A from AVNU to itself
  2.3. AMM call “transfer” token A’ to AVNU
  2.4. If  then repeat 2.1 with the amount A’ received
3. Call “transfer” token B from AVNU to User.

The AVNU contract iteratively applies the swaps specified by the solution to obtain an amount Y of token B, which is then transferred back to the user, completing the call.

If we now relate this behavior to the original gas formula, we can identify three components that will impact the gas price. The first component is the approval, the second component is the computational cost of executing the different swaps on the different AMMs, and the final component is the different ERC20 tokens that will be used by the AMM throughout the exchange.

To clarify the last points, let's consider the following scenario: the user trades some ETH for some DAI, and the optimal path is ETH → USDC → DAI. In this case, three ERC20 tokens will be modified.

Formally, let's define the following objects

• $A^{ERC20}_{owner,spender}$ gives the gas used of the approval of a spender by the owner in a ERC20.
• $T^{ERC20}_{from \rightarrow to}$ gives the gas used by a transfer from “from” to “to” on a ERC20
• $Nonce_{user}$ gives the gas used by incrementing the user nonce

Additionally, we define two functions, $f^{avnu}_{method}(amount),f^{pool}_{method}(amount)$ that gives the gas used by calling a given method on the AVNU contract (respectively the pool contract) with the given amount.

Let’s write a direct trade from USDC to USDT through AVNU using our definition.

$$\begin{equation} \begin{split} Gas^{avnu}_{swap}(amount) &= A^{usdc}_{user, avnu} + T^{usdc}_{user \rightarrow avnu} \\ &\quad + A^{usdc}_{avnu, pool} + T^{usdc}_{avnu \rightarrow pool} + T^{usdt}_{pool \rightarrow avnu} \\ &\quad + T^{usdt}_{avnu \rightarrow user} + T^{eth}_{user \rightarrow sequencer} \\ &\quad + f^{avnu}_{swap}(amount) + f^{pool}_{swap}(amount) + Nonce_{user} \end{split} \end{equation}$$

This is quite a mouthful, but it contains all the details we've mentioned so far. The first two terms corresponds to the initial approval, followed by the call to "transferFrom" from the user to AVNU. The third, fourth and fifth terms are the approval, followed by the "transferFrom" from AVNU to the pool, and then the result if transferred back to AVNU. The third line is the result of the swap result being transferred to the user and then back to the user along with the payment of the fee to the sequencer by the user. Finally, the very last line contains the gas used by the call to AVNU and the call to the pool along with the gas usage induced by incrementing the nonce.

Now let's introduce three important concepts from Starknet gas pricing.

Property 1: A storage slot whose value is the same at the end of the execution as it was before the execution does not count as an update since it is not contained in the state update posted on L1.

Property 2: Fees are paid by the user executing the transaction, and they are sent through an ERC20 transfer to the sequencer using the ETH contract. However, the user does not pay for the change in the balance of the sequencer, nor the fact that the ETH contract is modified because it is amortized for the whole block.

Property 3: Nonce updates are only counted once as a modified contract. More specifically, user have a nonce value associated to their account. For each transaction initiated by the user, the nonce is incremented which incur a storage slot update. However. instead of counting this update twice, both as a new contract and a new storage slot being modified, Starknet only counts it as a new contract being modified.

Aside from the fact that this is nice, we can observe that it allows us to reduce our original formula. Indeed, all the storage updates due to approvals cancel each other because the call to "transferFrom" consumes them. The first and last balance changes for AVNU also disappear because these amounts are entirely forwarded either to the pools or to the user. We can also remove the nonce update, but we will have to increase the number of contracts updated by one. Lastly, we can remove the second term in the last line due to the second property, and we won't count the ETH contract as modified.

With all that in mind, we are now ready to write the first version of the function characterizing the gas used by a direct swap on AVNU.

$$\begin{equation} \begin{split} Gas^{avnu}_{swap}(amount) &= (2_{ERC20}+1_{Nonce}+2^{ERC20}_{User})C+(2^{ERC20}_{Pool}+f^{pool}_{swap,storage}(amount))C \\ &+ f^{pool}_{swap,computation}(amount) + f^{avnu}_{swap}(amount) \end{split} \end{equation}$$

The first term represents the fact that we modify 2 ERC20 tokens, changing the user's balance for the In token and the Out token along with the nonce update. The second term represents the fact that we modify the balance of the pool in those same 2 ERC20 tokens (so we don't count them again as modified contracts) along with the potential storage slot modified on the pool contract. The last two terms account for the computational cost of calling the pool and calling AVNU. The constant $C \in \R^+$ is the gas cost of a storage cell update as defined in the preceding section.

The next step is now to find a general formula where we don't restrict ourselves to direct trade because in the end, AVNU supports multi-hops routing (i.e., crossing several pools in a single swap). However, before moving on, there is one interesting observation we can make if we consider direct trade from or to ETH. Indeed, since the ETH contract is not counted when computing the gas according to property 2, we get 3 modified contracts instead of 4, which will yield a reduced overall cost. However, in the rest of the discussion, we won't consider this case to avoid making the whole argument too verbose.

The generalization is quite simple, but we need to take into account one property of an AVNU swap, which is that the same pool can appear multiple times in the same route. The consequence of that is that we will potentially modify the same cell multiple times without increasing the overall gas cost due to property 2 above. To represent that, we will not give an exact formula for the gas used, but instead, we will give an upper bound that will be tight if our route contains only distinct pools with distinct addresses for the ERC20 tokens involved.

$$\begin{equation} \begin{split} Gas^{avnu}_{swap}((Pool_i)_{i \in \N}) &\leq (2_{ERC20}+1_{Nonce}+2^{ERC20}_{User})C \\ &\quad + \sum_{i \in \N}C(1_{ERC20}+2^{ERC20}_{Pool_i}+f_{storage}(pool_i)+f_{computation}(pool_i)) \end{split} \end{equation}$$

The gas function takes as input a sequence of pools $(Pool_i)_{i \in \N}$ that we will route through. The upper bound is composed of two terms: the first one corresponds to the update of the user contract's nonce along with the updates of its ETH balance to pay for the fee and the balances of the token In and Out. The second term is the sum of gas induced by routing through each pool.

Wrapping Up

We now have a much better understanding of how Starknet prices transactions, and we've managed to build the AVNU mathematical model. We've also made a few interesting observations along the ways that we summarise below.

• The cost of a storage slot update is 1224 gas unit which correspond to ~0.14$.
• ERC20 "transfers" and "approves" cost are dominated by the cost of updating the necessary storage slots.
• The first operation on the ETH - ERC20 costs less than for other ERC20 because Starknet amortized part of the cost on the whole block.
• The fee transfer to the sequencer count only as a single storage slot update corresponding to the user balance being modified.
• Nonce increase does not count as both a new contract and a new storage slot being modified but just as a new contract being modified

Our goal in the subsequent chapter is to derive an approximation model based on the mathematical characterisation we've made of AVNU and to do that we will analyse our first set of AMM which correspond to Uniswap V2 and Stable curve implementations. However, before leaving we will offer you a glimpse into the results we've obtained with our approach and the resulting model.

First, here is the evaluation of the prediction made by our old model, in blue and our new model, in orange against the real simulated value. The blue line indicates what would be a perfect prediction, i.e. prediction == simulation so the closer the dots are to this line, the better is the model. As you can see, there is a huge difference between the old model which was based on a much simpler analysis and the new model we are building here. Furthermore, we see that the prediction are very satisfactory.

We can even go a step further and see how the model perform live ! While we've made the official announcement a few days ago, our model has been in production since the 29th of November, and we've carefully monitored it, recording our prediction and the actual fee paid for every transaction made on AVNU. All this data allow us to plot the average of our estimate against the average of the actual gas fees paid by the user in dollar and this is the result.