Dynamic Multidimensional Fees for P-chain and X-chain

[abi87]

Abstract

Introduce a dynamic and multidimensional fees scheme for both P-chain and X-chain.
A dynamic fee scheme helps to preserve the stability of the chains as it provides an economic incentive for users to hold their transactions issuance in times of high load.
A multidimensional fee scheme ensures that different resources consumed during transaction processing, like bandwidth, chain state occupation and cpu needed to verify cryptographic signatures, are metered and priced differently, according to their different capacities. When network resources are independently metered, they can be granularly priced and thus optimally utilized by the network participants.

Motivation

P-chain and X-chain fees have currently fixed values and in some cases they are zero.
This makes transaction issuance very predictable but it does not help preserving stability of the chains in high load situations. In fact, users do not have any economic incentive to delay their transaction issuances when chains are loaded, thus contributing to sustaining the load.
The C-chain is the Primary Network chain with the heaviest traffic, and it already has a dynamic fees scheme. We should introduce a dynamic fees scheme for P-chain and X-chain as well to improve Primary Network stability in anticipation of an increase in the network activity.
Unlike the C-chain, however, we propose a multidimensional fee scheme with exponential updates. A multidimensional fee scheme with optional priority fees is already in use in our HyperSDK and its efficiency is backed by academic research. We propose to adopt the same scheme for the P-chain and X-chain with a single change: the use of an exponential update scheme which is proven to have nicer stability properties than the scheme currently used by the HyperSDK.

Specification

First a few definitions:
We define four fee dimensions, Bandwidth, UXTOsReads, UTXOsWrites, Compute, along which metering transactions impact over the P-chain and X-chain. In more details:

• Bandwidth measures the transaction size in bytes, a proxy for the network resources needed to disseminate the transaction.
• UXTOsReads measures the number of UTXOs referenced as inputs of the transactions, a proxy for the chain state reads needed to verify the transaction.
• UTXOsWrites measures the number of UTXOs generated as outputs of the transactions, a proxy for the chain state writes needed to store the transaction.
• Compute meters the complexity of signatures verifications, both UTXOs ones and those related to authorization of specific operations.

For each fee dimension $i$, we define a fee rate $r_i$ as the price, denominated in Avax, to be paid if the transaction consumed a unit $u_i$ of fee dimension $i$.
We define the base fee needed to accept a transaction as $$fee = \sum_{i=0}^3 r_i \times u_i$$ where $u_i$ is the number of units metered for dimension $i$.
We define as priority fee an optional fee paid on top of the base fee to allow speeding up the transaction inclusion in a block.
Finally, for each fee dimension $i$, we define:

• A block minimal complexity $L_i$ as the minimum number of units consumed cumulatively by all transactions included in the block, along fee dimension $i$.
• A block maximal complexity $U_i$ as the maximum number of units consumed cumulatively by all transactions included in the block, along fee dimension $i$.
• A block target complexity $T_i$ as the ideal number of units consumed cumulatively by all transactions included in the block, along fee dimension $i$. We require $L_i \leq T_i \leq U_i$.

The dynamic fee algorithm will try to modify fee rates to steer units consumed towards the block target complexity.

Upon activation of the dynamic multidimensional fees scheme we modify block processing as follows:

• Bound block complexity. When verifying each block transaction, we meter the transaction units consumed along the four fee dimensions. We accept a block only if, for each dimension $i$, the cumulated units consumed by block transactions are within the block minimal and maximal complexity.
• Verify transaction fee. When verifying each block transaction, we check that it can pay for its own dynamic fees. Note that both base fee and optional priority fees are burned.
• Update fee rates. Once we accept a block, we update the fee rates expected to be paid for the subsequent blocks. For each dimension $i$, we update the fee rate as follows: $$r_{i,t+1} = r_{i,t} e^{k \frac{u_i-T_i}{T_i}}$$ where $e$ is Euler’s constant and $k$ is a parameter controlling speed of fee rates changes. This formula has been proved to have nice stability properties here.

Backwards Compatibility

Modifying the fee scheme for P-chain and X-chain requires a mandatory upgrade for activation.
Wallet implementations must be modified to handle the new fee scheme to be able to properly finance transactions once the upgrade is activated.

Reference Implementation

For AvalancheGo:

• P-chain work is tracked in this issue: P-chain - Dynamic Fees ava-labs/avalanchego#2707
• X-chain work is tracked in this issue: X-chain - Dynamic Fees ava-labs/avalanchego#2708

Security Considerations

The new fee scheme is expected to help network stability as it offers economic incentives to users to hold transactions issuance in times of high load. While fees are expected to remain generally low when the system is not loaded, a sudden load increase, with fuller blocks, would push the dynamic fees algo to increase fee rates. The increase is expected to continue until the load is reduced. Load reduction happens by both dropping unconfirmed transactions whose fee-rate is not sufficient anymore and by pushing users that optimize their transactions costs to delay transaction issuance until the fee rate goes down to an acceptable level.
Note finally that the exponential fee update mechanism detailed above is proven to be robust against strategic behaviors of users delaying transactions issuance and then suddenly push a bulk of transactions once the fee rate is low enough.

Open Questions

How will the wallets estimate the fees?

AvalancheGo nodes will provide new APIs exposing the current fee rates, as they are likely to change block by block. Wallets can then use the fees rates to select UTXOs to pay the transaction fees. Moreover Avalanchego implementation proposed above offers a fees.Calculator struct that can be reused by wallets and downstreams to evaluate calculate fees

How will wallets be able to re-issue TXs at a higher fee?

Wallets should be able to simply re-issue the transaction since current AvalancheGo implementation drops mempool transactions whose fee rate is lower than current one. More specifically a transaction may be valid the moment it enters the mempool and it won’t be re-verified as long as it stays in there. However as soon as the transaction is selected to be included in the next block, it is re-verified against the latest preferred tip. If fees are not enough by this time, the transaction is dropped and the wallet can simply re-issue it at a higher fee, or wait for the fee rate to go down. Note that priority fees offer an edge against fee rate spike. A transaction paying just the base fee will be evicted from the mempool in thel face of a fee rate increase, while a transaction paying some extra priority fee may pay enough overall fees to still be accepted despite the fee rate increase.

How does priority fees guarantee a faster block inclusion?

AvalancheGo mempool will be restructured to order transactions by priority fees. Transactions paying priority fees will be selected for block inclusion first, without violating any spend dependency.

[abi87]

The update fee rates formula outlined above has a flaw: it does not account for a time elapsed among parent and child blocks.

We'd expect that the largest the time elapsed among them, the less should be the effect of parent block complexity in setting the child block fee rates. This does not happen above, since only block complexity is considered, not the elapsed time.

We consider the following improvement over the formula:

$$r_{i,t+ \Delta T} = max(mr_i, r_{i,t} e^{k_i \frac{pc_i- tc_i * \Delta T}{tc_i * \Delta T}})$$

where:

• $mr_i$ is the minimum fee rate for dimension $i$
• $k_i$ is the update coefficient for dimension $i$
• $pc_i$ is the parent block complexity for dimension $i$
• $tc_i$ is the target complexity rate for dimension $i$, i.e. the amont of complexity per unit of time that the algorithm tries to converge to.
• $\Delta T$ is the time elapsed among parent block and child block, as measured by block timestamps.

Note that technically two consecutive blocks can have the same timestamp. In such a case we may consider $max(1, \Delta T)$ seconds.

I'll comment later on about sizing these parameters.

[abi87]

I propose here a few following principles to size the fee update parameters.
The basic idea is to measure the complexity of blocks already accepted and derive the parameters from it.
To simplify the exposition I am purposefully ignoring chain specifities (like P-chain proposal blocks). We can account for chain specificities while processing the historical data.

• Target block complexity rate: consider the median block complexity and stretch in up say 20%.
• Max block complexity: this is probably the trickiest parameter to set.
  Historically we had pretty big transactions (more than $1.000$ referenced utxos). Setting a max block complexity so high that these big transactions are allowed is akin to setting no complexity cap.
  On the other side, we still want to allow, even encourage, utxos consolidation, so we may want to allow transactions like this.
  A principled way to set max block complexity may be the following:
  • come up with the target block complexity rate (see previous point)
  • come up with the median time elapsed among consecutive blocks
  • The product of these two quantities should gives us something like a median block complexity.
  • Set the max block complexity to $\times 10$ or $\times 20$ that median value.
• Update coefficient: this is the $k_i$ parameter in the exponential fee update. I suggest we size it as follows:
  • Find the largest historical peak, i.e. the sequence of consecutive blocks which contained the most complexity in the shortest period of time
  • Tune $k_i$ so that it would cause a $\times 100$ increase in the fee rate for such a peak.
• Initial fee rates : this are the rate to be used as soon as dynamic fees activate.
  We could size them so that transactions fees won't change very much with respect to currently fixes values.
  Note that we do currently support zero fees transactions, which are not allowed a dynamic fees world. Zero fees transaction would immediately see the largest increase when dynamic fees kick in. Still we could make the change as small as possible
• Minimal fee rates : these are required since we cannot have zero fee rates in our dynamic fees proposal.
  We update fee rates via a multiplicative process so as soon as a fee rate is zero all sequent fee rates would be zero.
  We could set minimal fee rates to equal to initial fee rates or to a fraction of them.

[abi87]

We proposed above the following formula to update fees:

$$r_{i,t+ \Delta T} = max(mr_i, r_{i,t} e^{k_i \frac{pc_i- tc_i * \Delta T}{tc_i * \Delta T}})$$

The main features of the exponential update are:

• Monotonicity: fee rates increase with $pc_i$ if $pc_i > tc_i$
• Stability: fee rates do not change if block complexity oscillates around target complexity. In other words, if block complexity increase and decrease of the same amount in consecutive blocks, fee rates will go back to the original value.

From an implementation standpoint, we would like to implement the update formula using only integer math.
It's tricky to approximate the exponential with interger math over the interval we are interested in. So I propose the following approximation to the exponential:

$$ \begin{align*} r_{i,t+ \Delta T} = 1 + k_i * delta^2 \quad if\ delta \geq 0 \\ r_{i,t+ \Delta T} = \frac{1}{1 + k_i * delta^2} \quad if\ delta < 0 \end{align*} $$

where $delta = \frac{pc_i- tc_i * \Delta T}{tc_i * \Delta T}$

The approximation keeps the two properties listed above and it's much easier to implement with interger math

[abi87]

P-chain_complexities.tar.gz collects the historical complexities of P-chain blocks as measure by the current implementation.
The file is a CSV file structured as follows:

• BlkID, BlkHeight, BlkTimestamp, Bandwidth_Complexity, UTXOsRead_Complexity, UTXOsWrite_Complexity, Compute_Complexity

This data can be used to tune the dynamic fees parameters.
Note that some heighs are missing. Those heights correspond to option blocks (Commit/Abort) which are empty and carries no complexity.