Fees: account for skipped blocks

[rphmeier]

After #157 , the blobs chain will not produce blocks unless there is anything meaningful to place into the block. Therefore, we need logic executed at the beginning of each block to adjust the fee multiplier according to any skipped blocks, treating these as empty.

Architecturally, this piece of code should be called in on_initialize of each block.

Skipped Blocks Update Formula

Refer to https://research.web3.foundation/Polkadot/overview/token-economics#2-slow-adjusting-mechanism alongside the next section.

The single update formula of c_traffic after an empty block is c_traffic = c_traffic * (1 + v(-target) + (1/2)(v^2)(-target)^2). This is actually an approximation of e^(-target*v) via the first three terms of its Taylor series expansion. V is an adjustment speed parameter.

A repeated application of c_traffic = c_traffic * e^(-target*v) N times yields c_traffic = c_traffic * e^(-target*v*n).

Therefore, the formula update after N empty blocks can be approximated in the same manner, by taking the first three terms of the Taylor series expansion. With large N, we may prefer to take more terms of the Taylor Series expansion, which is trivial.

c_traffic = c_traffic * (1 + v*n*(-target) + (1/2)(v^2)(n^2)(-target)^2)

Determining number of skipped blocks

We can use the difference between the current block's relay-parent number and the previous block's relay-parent number to estimate the number of blocks which have been skipped.

Currently, the chain is configured to author blocks once every 2 relay chain blocks.

If the difference is less than 4, no blocks have been skipped. If the difference is equal to 4, 1 block has been skipped. If the difference is equal to 6, 2 blocks have been skipped. This implies that the formula n_skipped_blocks = relay_parent_distance.saturating_sub(2)/2 is reasonable for our purposes.

With asynchronous backing, we can use the formula n_skipped_blocks = relay_parent_distance.saturating_sub(1).

Implementation Notes

• Beyond some maximum of skipped blocks, the fees are likely to be at the minimum. To avoid handling the possible overflow of large numbers, large amounts of skipped blocks should just default to the minimum.
• We would like to have this logic process prior to all pallet_transaction_payment runtime APIs, but currently cannot do so, as the "current" relay parent is not accessible. If blocks are missed for long periods of time, the estimated fees off-chain may diverge significantly from the actual fees. However, it is always an over-estimate.