Add FIP: Premium Percentile Ratio

[ThatGuyLLC]

FIP PR: #1233
Author: https://github.com/wjmelements

Simple Summary
Replacing the utilization-based base fee adjustment with a premium-based target will stabilize gas markets and improve tipset efficiency.

Abstract
Instead of targeting 50% gas limit utilization, which is unreliable for multiple block proposers, congestion is detected by considering the ratio between the effective priority fee, called the premium, and the base fee.
When this ratio exceeds 1/8, the base fee increases; when it falls below this threshold (or if the blocks are sufficiently empty), the base fee decreases.
This approach aligns base fee adjustments with congestion signals, which should improve the predictability of gas markets, thereby reduce proposer duplications.

[wjmelements]

We had a side discussion on slack about whether we can abolish the 100 attoFIL base fee minimum with this change. I think we can, but there were some objections:

@magik6k:

I'd think we want to make it higher for faster response
100aFil is basically zero

@Kubuxu:

The lower you set it, the slower the response from sitting at the floor. IMO no reason to set it to 8.

I don't think we'll be sitting at the floor after this change. We're stuck on the floor because it is much harder to increase the base fee than to decrease it, even under congestion, as discussed here and in the FIP motivation.

I proposed that if we think the base fee adjusts too slowly, we can decrease the BaseFeeMaxChangeDenom, which could be reasonable because our block time is longer than Ethereum's, for whom 8 was configured.

[Kubuxu]

The lower you set it, the slower the response from sitting at the floor.

I didn't mean it as "now we have to walk from 8 to 100," but rather that the walk is slower than it should be due to loss of precision and rounding behaviours. Let's say we are on the floor, and the fee keeps increasing by half the available adjustment. If the floor is 8, the fee will stay at the floor due to rounding.

[wjmelements]

We could round up instead of down.

[wjmelements]

Per our discussions I have made the following changes (f2947f4):

• change adjustment from floor to ceil
• restore 100 base fee minimum

[wjmelements]

A weighted quickselect algorithm such as wselect0 can find the percentile premium in average linear time without sorting. It doesn't seem anyone's been able to get the worst case down to linear for weighted percentiles, but median-of-medians quickselect can get there for unweighted. It seems advanced pivot selection is not used in practice because it is much slower on average.

[wjmelements]

I found a bug in the protocol's current deduping logic for base fee. We only dedupe by Cid, not by sender+nonce, so it is possible for a griefer to drive up the base fee at no cost by sending conflicting messages to the proposers.

This change is a good chance to consider whether base fee calculation should dedupe by sender+nonce instead. I think it should, because such duplicates pay zero for their gas limit. I will update the FIP to clarify this change and make it explicit.

[wjmelements]

git blame says @Kubuxu might know if it was intentional

[Kubuxu]

Yeah, I think you are right that it is a bug.

[wjmelements]

Cool. I verified that all clients do it so we'll just fix it in the next network version.

[wjmelements]

Created Lotus PR

[wjmelements]

Today I ran some simulations with the new premium recommendation algorithm and I think the mempool based approach should not default to nblocksincl=10. The mempool approach might be more suited to lower nblocksincl. I am also deciding how recommendation should behave when the mempool is empty.