lip-0016.md

LIP: 0016
Title: Implement fee estimation algorithm for dynamic fee system
Author: Iker Alustiza <iker@lightcurve.io>
Discussions-To: https://research.lisk.com/t/implement-fee-estimation-algorithm-for-dynamic-fee-system/
Status: Active
Type: Standards Track
Created: 2019-04-11
Updated: 2021-12-01
Requires: 0013

Abstract

This LIP proposes a fee estimation algorithm that suggests a fee depending on the priority of the transaction for the user and the blockchain’s recent history. The algorithm is based on an Exponential Moving Average (EMA). It is implemented in a node of the Lisk network and the wallet queries its output to get the transaction fee estimation for the user.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

With the proposed dynamic fee system for Lisk (refer to the LIP-0013 for the complete proposal), there will be a minimum fee required by the protocol, and the users will be able to spend any fee between this minimum fee and the top limit permitted by their account balance. This has two implications for the users:

1. The users have to know the exact minimum fee for their transactions (depending on the type and size) so that they can assign a valid fee for their transactions.

2. The users need certain guidance about what fee to spend in their transactions depending on their priority. This way the users minimize their transactions’ processing cost. This entails benefits for the Lisk network in terms of usability. Arguably, one can say that a good guidance for the user in this respect allows to fully attain the advantages of a dynamic fee system.

In this proposal we assume that 1. is already given and accessible for the user (in any Lisk wallet or other third party wallets). In fact, it is straightforward to implement given the minimum required fee per byte and the type and size of the transaction. However, 2. implies a deeper technical study, mathematical modeling and definition of this guidance for the user.

Rationale

We propose a fee estimation algorithm to leverage the features of the dynamic fee system and attain its advantages for the Lisk network. This fee estimation algorithm provides an estimation of what transaction fee should be used depending on the priority of the transaction for the user and the blockchain’s recent history (i.e., the guidance for the user). To achieve this objective, the fee estimation algorithm proposed in this document has the following properties:

• The output is correlated to the information in the blockchain, i.e., the fee spent by the confirmed transactions.
• The algorithm considers as much data in the past as possible for better accuracy.
• The newer this data is, the greater its importance is in the estimation.
• If the last blocks have space for additional transactions, the minimum required fee is recommended.
• It provides different estimates depending on the priority the users give to their transactions.
• The output cannot be higher than the static fees in the current protocol.

On top of all these properties, the user should understand that the output of the algorithm (the fee estimation) is only a recommendation or a suggestion. It is just a guidance to help the user, not a rule given by the protocol.

Taking the properties above into account, the proposed fee estimation algorithm is based on an Exponential Moving Average (EMA), also referred to as exponential smoothing in the literature. With the EMA, the data considered can theoretically expand infinitely in the past while its weight decreases exponentially with time. In signal processing literature (where the technique is addressed as exponential smoothing), several studies are available about how to tune the weight of the data depending on its age.

For the mentioned idea of transaction priority, we assume that the economic interest of the delegates is to choose the transactions with highest fees per byte to be included first into blocks. This way, the higher the fees per byte of a transaction are, the higher its priority is (faster inclusion in the blockchain)^[1]. For this proposal, we consider three different transaction priorities with respect to the fee. The notion behind these three transaction priorities is:

• Low priority transaction fee: Fee estimation considering the transactions with the lowest fees per byte in the past blocks.
• Medium priority transaction fee: Fee estimation considering the transactions with approximately average fees per byte in the last blocks.
• High priority transaction fee: Fee estimation considering the transactions with highest fees per byte in the past blocks.

With the previous rationale in mind, it is important to note that the algorithm is conceptually simple and does not attempt to predict future conditions, but assumes that these conditions are correlated to the recent past. Mathematically, it considers some recent history of transactions in the blockchain and outputs a certain fee per byte such that in this recent history a considerable amount of transactions with that fee (or higher) were confirmed in the blockchain.

This proposal takes inspiration from estimateSmartFee function in Bitcoin Core in terms of philosophy and objectives. However the proposed approach defines a different mathematical model and fee estimation methodology.

^[1] Note that when we say here “higher fees per byte”, we are referring to the fees paid on top of the minimum fee of a transaction, namely feePriority in the LIP-0013.

Mathematical description

As mentioned above, the algorithm internally is modelled as an EMA, which in general can be described as the following recursive formula:

feeEst₀ = offset,

feeEst_h = α fee_h + (1- α) feeEst_h-1,   for h > 0,

where:

• α is the smoothing factor or exponential decay. This parameter, between 0 and 1, defines how fast the weight of past information decays in the EMA. For example, if α ≈ 1, then fee_h is given a large weight, while all other weights are almost zero. On the contrary, if α is close to 0 then older estimates are given a significant weight for the current estimation. Given a number d between 0 and 1, and a positive integer B, such that the weight of the information B blocks in the past has a decay of d, then α is determined by:

  (1-α)^B = 1 - d

• offset is the parameter to signify the past fees prior the initial estimate.

• feeEst_h is the estimation of the fee computed at height h.

• fee_h is the fee per byte derived from the block at height h. It is given in terms of the fee per byte paid on top of the minimum fee for a transaction. In particular, it is based on the feePriority concept defined in the LIP-0013 as:

  feePriority(trs) = (trs.fee - trs.minFee) / sizeof(trs)

  where sizeof(trs) is the size in bytes of the transaction trs, trs.minFee is the minimum fee required for trs and trs.fee is the fee of trs. Refer to the LIP-0013 for the definition of trs.minFee.

Note that, in this proposal, offset, feeEst_h and fee_h are given in Beddows per byte. In the Lisk protocol, every amount of LSK is given in terms of Beddows (10^-8 LSK).

Specification

The fee estimation algorithm is implemented in a node of the Lisk network, where the values of the estimation for every new block are calculated and kept. Locally, a wallet (i.e., Lisk Hub or Lisk Mobile) can then query a node for a fee estimation and output the suggested transaction fee to the user. Other alternative implementation considered initially can be found in Appendix A. In the following, we present the specification details:

At the node

At the node, two functions implement the fee estimation, i.e. getEstimateFeeByte and EMAcalc. The first function returns the fee estimation every time it is called via the API. It is defined as follows:

FeeEstPerByte = getEstimateFeeByte(EMAoutput)

where FeeEstPerByte and EMAoutput are objects containing the following properties:

FeeEstPerByte:{
  Low,
  Med,
  High,
}

EMAoutput:{
  FeeEstLow,
  FeeEstMed,
  FeeEstHigh,
}

Note that three properties are defined for each object, which corresponds to the three fee transaction priorities (low, medium and high) defined in the previous section.

getEstimateFeeByte implements a check for filled block space. If past blocks are not filled up to a certain threshold, then the minimum fee of the transaction should be recommended:

if(wavg(sizes of 20 last blocks)) > 12.5 KB || sizeof(last block) > 14.8 KB)
  FeeEstPerByte.Low = EMAoutput.FeeEstLow
  FeeEstPerByte.Med = EMAoutput.FeeEstMed
  FeeEstPerByte.High = EMAoutput.FeeEstHigh
else
  FeeEstPerByte.Low = 0
  FeeEstPerByte.Med = 0
  FeeEstPerByte.High = 0

where wavg() stands for the weighted average. In this case, the last block has a weight equal to 1 and the weights decrease by 10% when iterating towards the genesis block.

As shown in the pseudo-code above, two thresholds affect the output of the function:

1. The weighted average size of the last 20 blocks is larger than 12.5 KB, which is roughly the maximum size of block (15 KB) minus a full vote transaction.

2. The size of the last block received is larger than 14.8 KB, which implies that, with high probability, there are unconfirmed transactions waiting in the transaction pool.

The object EMAoutput is the output of the mentioned EMAcalc function that computes the EMA estimation. This function calculates a new fee estimation every time a new block is received (or generated by the node) and stores it. Based on the model shown in the Mathematical description section, it takes as an input this last block and the set of estimates previously stored. The used parameters are described in the following subsection.

Parametrization of the EMA estimation function

• offset : The node has to keep in its database its last set of estimates, EMAoutput. If the node crashes or is restarted, it uses this set of estimates as offset and proceeds to compute the estimates until the last block during the synchronization process.

• α: We set α = 0.03406, which implies a half-life decay (d = 0.5) in the estimation after 20 blocks (B = 20).

• fee_h: Considering that the last block was received at height h, fee_h is computed differently to calculate the three estimates contained in EMAoutput:

  • For FeeEstLow, fee_h is equal to 0 if the size of the last block is less than 12.5 KB. Otherwise, it is equal to the minimum feePriority of all the transactions in this block.
  • For FeeEstMed, fee_h is the average of the feePriority per byte of all the bytes^[2] in the last block over the 25th percentile and below or equal the 75th percentile of the maximum block payload (15 KB).
  • For FeeEstHigh, fee_h is the maximum of two values:
    • The average of the feePriority per byte of all the bytes^[2] in the last block above the 80th percentile of the maximum block payload (15 KB)
    • (1.3* FeeEstMed + 1) Beddows per byte.

Note that this implies to have three parallel and independent EMA computations to get the three priority estimates.

Refer to the Appendix B for a numerical example of the calculation of EMAoutput with the mentioned parameters.

^[2] Assuming that the transactions in the block are descendingly ordered by feePriority, each byte in the maximum block payload will have an associated feePriority. We assume feePriority = 0 for the cases of unused bytes or bytes used by transactions paying exactly the minimum fee.

Locally: User's wallet

As said before, the wallet queries the fee estimation information from the connected node (the FeeEstPerByte object described before) to output the estimated transaction fee.

A function computes the estimated transaction fee taking three input arguments:

1. The FeeEstPerByte object received from a connected node.
2. A parameter, priority, to specify the fee priority requested by the user.
3. The transaction object, trs, to be transmitted.

The priority parameter can take three values, one for each of the fee priorities. Then, the function outputs the estimated transaction fee as:

if(priority = Low priority)
  output = trs.minFee + FeeEstPerByte.Low * sizeof(trs)
else if(priority  = Med priority)
  output = trs.minFee + FeeEstPerByte.Med * sizeof(trs) + minFeePerByte * IsNonZero(FeeEstPerByte.Med) * rand()
else if(priority  = High priority)
  output = trs.minFee + FeeEstPerByte.High * sizeof(trs) + minFeePerByte * IsNonZero(FeeEstPerByte.High) * rand()

output = ceil(output)

where minFeePerByte is the minimum fee per byte required by the protocol and rand() is a pseudo-random number in the range [0,1]. This function can be implemented with the Math.random() method. The third summand in the medium and high priority cases is used to introduce a tie-break when the estimation of the fee is flat (only applies when IsNonZero() = true).

Moreover, the output of the function is capped by the currently defined static fees (except for the dapp transaction type), namely:

fees: {
  send: 10000000,
  vote: 100000000,
  secondsignature: 500000000,
  delegate: 2500000000,
  multisignature: 500000000,
  dapp: 5000000000
}

Backwards Compatibility

This change is backwards compatible both for the nodes and the wallet. However, nodes should be encouraged to update to the algorithm implementation version for usability reasons.

If a client queries a node without the algorithm implemented, the node will send back an “invalid request” response. In this case, users will have to connect to a different node, or in the worst case, they will need to guess the fee to spend without any guidance.

Reference Implementation

Implement fee estimation service

Acknowledgements

I would like to thank Jan Hackfeld for the valuable feedback regarding the definition of the parameter fee_h.

Appendix

A: Alternative way of implementing the algorithm

Another considered possibility is to implement the whole algorithm locally as a function that pulls all the required data from the blockchain every time a fee needs to be estimated.

In this case the mathematical model is:

feeEst_h = α [fee_h + (1- α) fee_h-1 + (1- α)² fee_h-2 ... + (1- α)^k-1 fee_h-k-1] + (1- α)^koffset

where each of the fee_i parameters in the equation signifies the fees at the block at height i, as defined for the different priorities in the Parametrization of the EMA estimation function subsection.

In this case, the function requests the fees of the previous k blocks. Every new call to the function is a new estimation of the fee.

Advantages:

• No need to rely on nodes to get the estimation.
• Easier to update and improve: No need to update the Lisk node.

Drawbacks:

• Accuracy: EMA has limited data, until k blocks in the past.
• Accuracy: offset may have a significant impact.
• Efficiency: It queries full blocks information from nodes every time someone wants to get an estimation. This may overload the queried node.

B: Numerical Example of the EMA Algorithm

Assume a node implementing the changes of this proposal which has been running (receiving and/or generating blocks) for a considerable amount of time. In its database, the output of the last EMA estimation function, EMAoutput_db, is stored as (in Beddows):

EMAoutput_db:{
  FeeEstLow = 0
  FeeEstMed = 1000
  FeeEstHigh = 2000
}

Assume the considered node receives a new valid block at height = h, with a total of 71 transactions ( trs₁, trs₂, trs₃, ..., trs₇₁) and a size of approximately 13.5 KB. For each of these transactions we have its corresponding size and feePriority value:

• Transactions from trs₁ to trs₆₀ are of type 0, 125 bytes of size, and feePriority = 0 Beddows/byte.
• Transactions from trs₆₁ to trs₆₃ are of type 0, 125 bytes of size, and feePriority = 1000 Beddows/byte.
• Transaction trs₆₄ is of type 3, 2334 bytes of size, and feePriority = 1000 Beddows/byte.
• Transaction trs₆₅ is of type 0, 189 bytes of size, and feePriority = 1200 Beddows/byte.
• Transaction trs₆₆ is of type 1, 153 bytes of size, and feePriority = 1200 Beddows/byte.
• Transaction trs₆₇ is of type 1, 125 bytes of size, and feePriority = 1500 Beddows/byte.
• Transaction trs₆₈ is of type 3, 2270 bytes of size, and feePriority = 1800 Beddows/byte.
• Transaction trs₆₉ is of type 0, 125 bytes of size, and feePriority = 2000 Beddows/byte.
• Transaction trs₇₀ is of type 0, 253 bytes of size, and feePriority = 4000 Beddows/byte.
• Transaction trs₇₁ is of type 0, 189 bytes of size, and feePriority = 8000 Beddows/byte.

As the node just received a new block, the EMA estimation function is called to calculate the new set of fee estimates. In particular, each of the estimates for the new EMAoutput are calculated as:

• For FeeEstLow, fee_h = 0, which is the minimum feePriority in the block. Then:

FeeEstLow = 0 Beddows/byte

• For FeeEstMed, we have to calculate fee_h, which is the average of the feePriority per byte of all the bytes above the 11250th byte (25th percentile) and below or equal the 3750th byte (75th percentile) of the maximum block payload. Note that the transactions are descendingly ordered by feePriority. These bytes correspond to the transactions from trs₂₀ to trs₆₄. Hence:

fee_h = (1889 * 1000 + 3 * 125 * 1000 + 41 * 125 * 0) / 7500 = 301.9 Beddows/byte

Note that only 1889 bytes of trs₆₄ fall below or equal the 75th percentile. Now we can compute FeeEstMed:

FeeEstMed = 0.03406 * 301.9 + (1 - 0.03406) * 1000 = 976.2 Beddows/byte

• For FeeEstHigh, we have to calculate the average of the feePriority per byte of all the bytes above 3000th byte (80th percentile). These bytes correspond to the transactions from trs₆₆ to trs₇₁. The average of their feePriority is:

fee_h = (189 * 8000 + 253 * 4000 + 125 * 2000 + 2270 * 1800 + 125 * 1500 + 38 * 1200) / 3000 = 2364.4 Beddows/byte

Note that only 38 bytes of trs₆₆ fall above the 80th percentile. Now we can compute FeeEstHigh:

FeeEstHigh = 0.03406 * 2364.4 + (1 - 0.03406) * 2000 = 2012.4 Beddows/byte

Hence, the new EMAoutput output is:

EMAoutput:{
  FeeEstLow = 0
  FeeEstMed = 976.2
  FeeEstHigh = 2012.4
}