Add utility function getMinFee to lisk-transactions library

[shuse2]

Description

Add utility function calculateMinFee and getMinFee to the lisk-transactions library, which can be used by UI/Service to calculate the minimum fee required to be shown to the end-users.

Motivation

Currently, lisk-transactions has no utility function to calculate minimum fee for a given transaction with fee set to 0.

Acceptance Criteria

• When transaction is initialised with fee 0 and called getMinFee should return transaction with fee set to minimum fee requirement

[janhack]

One utility function could be a function that enables computing the required minimum fee for a transaction where the fee property is not set. The challenge here is that the minimum required fee of a transaction depends on the transaction size, which again depends on the value of the fee property of the transaction. Therefore, it is not straightforward to precompute the exact minimum required fee.

Current Approach

We overestimate the size of the fee property and use this approximation to find a sufficient minimum fee, which can be slightly above the minimum required transaction fee. More precisely, we do the following:

1. Let trs be the transaction for which the minimum fee has to be computed.
2. Let k be the number of signatures required by the transaction (k=1 for non-multisignature accounts and k=numberOfSignaturesfor multisignature account). Then set the signatures property of trs to an array of k bytes of size 64 (e.g., zero bytes).
3. Set the fee property of trs to 2^64-1 (max unsigned int64)
4. Compute trs.size()*minFeePerByte+trs.getNameFee() where trs.size() is the size of the transaction with the changed fee and signatures property.

Main shortcomings

• We overestimate the required fee and users overpay for 7 Bytes for most transactions (more than 5 % for balance transfers with 1 signatures) .
• The UI cannot give a precise minimum required fee for users that want to choose a customizable fee.

Technical Details

• 2^64-1 requires 10 bytes in varint encoding as only 7 bits per byte are used to encode the number (see https://github.com/LiskHQ/lips/blob/master/proposals/lip-0027.md#base-128-varints )
• The suggested minFeePerByte value in LIP 13 is 1000, a balance transfer is about 125 bytes so the minimum fee for a balance transfer would be 125,000. Note that 2^21 = 2,097,152 so that the minimum fee for all transactions up to around 2 kB can be encoded in 3 Bytes.

Alternative approach

We compute the exact minimum required fee. One approach is the following:

Do 1. and 2. as above

3. Call the function findRequiredMinFee on the transaction with trs.fee initialized with 0.

computeMinFee(trs):
    return trs.size()*minFeePerByte+trs.getNameFee()

findRequiredMinFee(trs):
    minFee=trs.computeMinFee()
    while minFee > trs.getFee():
        trs.setFee(minFee)
        minFee=trs.computeMinFee()

The idea is to use an iteration that iteratively computes the transaction size and then sets the fee of the transaction using that size. Note that both the transaction size and minimum fee are monotonically increasing in the function. Observe the following:

• In the first iteration of the while loop the fee is initialized with a first best-guess, using the transaction size without the fee property. The new transaction size is computed.
• In the second iteration, the next slightly larger fee value is based on the transaction size with a reasonable fee property value.
• Only if the increase in the fee value from iteration 2 compared to iteration 1 requires to use one additional byte for the encoding, the transaction size increases and a third iteration is required. The fee value is increased again. But this increase cannot be so large that another Byte is required for encoding it. Thus, the loop always terminates after at most 3 iterations.

[ManuGowda]

getMinFee(
  trx: Record<string, unknown>, 
  assetSchema: Schema, 
  { minFeePerByte: number, baseFees: [{moduleId: number, assetId: number, baseFee: string}]}
): bigint