Add Parameters to Base Fee Mechanism

[guy-goren]

Discussion: Add Parameters to Base Fee Mechanism

Our goal is to start a discussion (before proposing a FIP) about incentive misalignments in EIP1559 base fee mechanism, and suggest improvements.

Simple Summary

For simplicity purposes we will describe the problem (and proposed improvements) in the simplified Ethereum model of a single chain of blocks. While Filecoin has multiple blocks in a single epoch, the same principles apply.

The current formula for setting the base fee follows the original EIP1559:
$$b[i+1]\triangleq b[i] \cdot\left( 1+\frac{1}{8}\cdot\frac{s[i]-s^* }{s^* } \right)$$ where $i$ enumerates the epoch, ${s^* }$ is a predetermined block size (the "desired" size), $b[i]$ is the base fee at epoch $i$, and $s[i]$ is the block size at epoch $i$. This formula only considers the last block size $s[i]$, and, in addition, uses a constant learning rate ($\phi=\frac{1}{8}$) regardless of the distance ($s[i]-s^*$). This mechanism might lead to incentives for users to bribe miners in order to reduce the base fee, or (in analogous manner) for miners to initiate a collusion with sophisticated users for the benefit of both. (See next section.)

As a mitigation idea to discuss we suggest two complementing changes. First, we propose to consider the history of block sizes via a weighted average with a geometric sequence as the weights. In addition, we suggest to use an adaptive function for the learning rate based on Additive Increase and Additive Decrease (AIAD). In particular, we suggest the following update rule:
$$b[i+1]\triangleq b[i] \cdot \left( 1+\phi[i] \cdot \frac{s_{\textit{avg}}[i]-s^* }{s^* }\right)$$ where $s_{\textit{avg}}[i]$ is defined by
$$s_{\textit{avg}}[i] \triangleq \frac{1-q}{q}\sum_{k=1}^{\infty } q^k\cdot s[i-k+1], \hspace{1cm} q\in (0,1)$$ and $\phi[i]$ is a function of $s_{\textit{avg}}[i]$ which follows AIAD update rule (specified here).

Background and Motivation

With the increased network activity following the FVM launch and as this activity ramps up, we expect to see even more competition for block space. This may lead to previously negligible incentive misalignments becoming more significant.

For determining which messages enter a block, Filecoin uses a mechanism that was proposed in EIP-1559. This mechanism introduced a base fee, which is a portion of the transaction fee that is burned and not awarded to miners, and which varies according to the fill rate of blocks. A target block size is defined, such that if a block is fuller than the target size, the base fee increases and if it is emptier, the base fee reduces.

Research on the subject (focused on Ethereum) have revealed issues with this transaction fee mechanism. It has been shown to be unstable in cases. Moreover, it has been shown that the dynamic nature of the base fee, which is influenced by the fill rate of blocks, opens the door for manipulation by miners and users. The desired behavior of the system under a stable high demand, is for it to reach an equilibrium where the base fee -- $b$ -- is the significant part of the gas fee, and the tip is relatively small -- denoted $\varepsilon$ (for reference, Ethereum often has $\frac{b}{\varepsilon }\approx 20$). According to Roughgarden this is a rational equilibrium under the assumption that miners do not think ahead. However, we expect a miner to optimize its behavior by also considering its future payoffs. In essence, since neither the miner nor the user are getting the burnt fee, by colluding they can both tap into the burnt fee for a win-win situation for them both.

A theoretical work describes how both miners and users can initiate an attack. For example, we can imagine that users who wish to pay lower costs will coordinate the attack. Roughly, a user (or group of users) that has transactions with a total $g$ amount of gas bribes the miner of the current block (no matter the miner's power) to propose an empty block instead. The cost of such a bribe is only $\varepsilon \times {s^* }$ -- the tip times the target block size. Consequently, the base fee reduces in the next block. If we accept that EIP1559 reaches its goals, e.g., users would typically use a simple and honest bidding strategy of reporting their maximal willingness to pay plus adding a small tip ($\varepsilon$), then in the honest users' steady state, gas proposals leave the miners with an $\varepsilon$ tip. Given that other users are nai"ve (or slow to react), our bribing user will include its transactions with any tip larger than $\varepsilon$ -- making the attack profitable whenever $g\frac{b^* }{8} >{s^* }\varepsilon$.

Change Motivation

Mainly, to reduce bribe motivation in case the demand for blockspace actually becomes high due to FVM. Additionally, to reduce oscillations and have a more stable fee setting mechanism.

Specification

The following equation describes the main part of the change, that is, replacing $s[i]$ by $s_{\textit{avg}}[i]$. For $q\in (0,1)$,

$$s_{\textit{avg}}[i] \triangleq \frac{1-q}{q}\sum_{k=1}^{\infty } q^k\cdot s[i-k+1]$$

which simplifies to the recursive form
$$s_{\textit{avg}}[i] = (1-q)\cdot s[i] + q\cdot s_{\textit{avg} }[i-1].$$

The change to the learning rate $\phi$ (from constant to adaptive), is defined by the following rule with parameters $\alpha$ and $\gamma$, and is bounded to be within $[\phi_{\min},\phi_{\max}]$.
$$\text{if } (1-\gamma){s^* } \le s_{\textit{avg}}[i]\le (1+\gamma){s^* } \text{ \hspace{0.5cm} then \hspace{0.5cm} } \phi[i+1] \gets \max \left( \phi[i]-\alpha, \phi_\min \right) $$
$$\text{ else \hspace{0.5cm} } \phi[i+1] \gets \min \left( \phi[i]+\alpha, \phi_\max \right) .$$

This scheme provides us with multiple knobs that can be adjusted:

• $q$ - which determines the concentration of the average. Roughly, smaller $q$ values result in $s_\textit{avg}$ resembling the very last block sizes, while larger $q$ values smoothen the average over a longer history.
• $\alpha$ - the additive term used to increase and decrease the learning rate. Larger $\alpha$ values result in faster adjustments to changes in demand but might lead to instability.
• $\gamma\in(0,1)$ - the threshold for deciding if the average is "close" or "far" from the desired block size. A "far from desired" average results in an increase of the learning rate while a "close" results in reducing the learning rate.
• $\phi_\min\in(0,\phi_\max)$ - the minimum learning rate. Roughly, the smaller $\phi_\min$ is, the more stable the system is in case of an approximately stable demand. However, small $\phi_\min$ values make it longer to adapt to changes in demand.
• $\phi_\max\in(\phi_\min,1)$ - the maximal learning rate. Roughly, the larger $\phi_\max$ is, the faster the system can adapt to sudden changes in demand. However, large $\phi_\max$ values can lead to cases of instability of the base fee even when the demand barely changes.

Parameter setting

Setting the right parameters is a work of art more than science, and it depends on the particular characteristics of the system. Therefore, tuning these parameters will require extensive data and experiments after Filecoin launches FVM and demand patterns emerge. Nonetheless, leaving the update rule unchanged is also a choice with unforeseeable consequences.

Below is a possible option for the initial parameter setting (which is based only the honeymoon data from Ethereum --- blocks 12935000 to 13079999).

• $q = 0.5$
• $\alpha = 0.025$
• $\gamma = 0.25$
• $\phi_\min = 0.0125$
• $\phi_\max = 0.75$

Additional info

EIP-1559 allows for a variable block size, but a valid block size must be in the range $s[i]\in[0,2s^*]$.

Unlike in Ethereum, in Filecoin the value $s[i]$ is determined not by a single block's size but by the average size of a block in the previous tipset. This affects the issue from both sides. On the positive side, the averaging reduces the profitability of bribing a single miner. On the negative side, given the possibility to choose different tipsets to build ontop, a rational miner might be incentivized to choose the "emptier" tipset in order to reduce the base fee for its current block, thus affecting the present and not just the future.

Design Rationale

An intuitive option for the Transaction Fee Mechanism (TFM) that adjusts supply and demand economically is First price auction, which is well known and studied. Nevertheless, in Filecoin the choice was to use EIP-1559 for the TFM. In this proposal, our design goal is to improve the TFM (of EIP-1559) by mitigating known problems that it raises. It is important to note that these problems do not yet impact the Filecoin network. If Filecoin gains traction, however, they are expected to rise. We may want to prepare for this beforehand.

The suggestion is composed of two parts: (i) using a weighted average over epochs of block sizes rather than only the latest, and (ii) using an adaptive learning rate. The first part is the basis of the proposal. The second is an additional improvement (that depends on the first part being implemented). We therefore discuss them separately.

$s_\textit{avg}[i]$ instead of $s[i]$

The change is based on this work that described a rational strategy in which bribes are profitable. Choosing to average based on a geometric series weights results in two desired properties: (i) the computation and space complexity are both in O(1), and (ii) the average gradually phases out the impact of a single outlier block without causing significant fluctuations in the base fee.

Having an adaptive learning rate instead of $\phi=1/8$

This suggestion is based on a research work dealing with the learning rate in Ethereum, which was arbitrarily set to $\phi=1/8$. Intuitively, a hige value of $\phi$ leads to more instability, while a low value of $\phi$ leads to slow adaptations to changes in demand. Having $\phi$ adaptive rather than constant seems like a good way to go. In particular, Additive Increase and Multiplicative Decrease (AIMD) was considered in this paper. AIMD has the benefit of reducing larger $\phi$ values faster than smaller $\phi$ values, but requires the tuning of an extra parameter -- $\beta\in(0,1)$ -- which determines the Multiplicative Decrease rate. For their suggested parameters of $\alpha=0.025$ and $\beta=0.95$, however, the difference between AIMD and AIAD does not appear to be significant. Therefore, we suggest to first consider the simpler Additive Increase Additive Decrease method.

Backwards Compatibility

This change requires a hard fork since the base fee is enforced (for blocks to be considerd valid).

Test Cases

Too early to say

Security Considerations

The more complicated a mechanism is, the more it is vulnerable to unforeseen security threats. The case of EIP1559 is just one example of it. We hope to mitigate those risks, however, discussions might show us differently.

Incentive Considerations

The proposal is designed to improve the incentive compatibility of the TFM. A game theoretic analysys shows that a TFM based on EIP-1559 encourages bribes. Roughly, because the base fee in the next block depends on the size of the the current block, a miner that creates an empty block reduces the base fee of the next block by a factor of $\phi$. The opportunity cost for mining an empty block instead of a normal block is only the tips it contains. Thus, the cost of bribing a miner is only compensating it for the lost tips. In case the base fee is significantly larger than the tips, the bribing user gains a significant reduction in the base fees of the next block, making the bribe profitable.

One of the main goals of EIP-1559 was to simplify the bidding for users. It was articulated theoretically by Roughgarden as users bidding their honest valuations being an optimal strategy. In contrast, when using first price auctions for the TFM (as done by Bitcoin and previously in Ethereum), it is typically sub-optimal for a user to bid its honest valuation. In other words, a TFM that encourages users to not fully reveal their preferences is considered less good. However, our opinion is that a TFM that encourages bribes is worse than a TFM that encourages not revealing one's full preferences.

We believe that a first price auction is the best way to go regarding TFMs, however, Filecoin chooses to use EIP-1559 and burn transaction fees (perhaps for reasons other than game-theoretic ones). We therefore suggest to mitigate the current incentives for bribes using the above proposal.

Product Considerations

Beside mitigating the incentives for bribes, we see two other potential benefits from a product perspective.

• The new averaging mechanism would reduce spikes and extreme oscillations of the base fee.
• The AIAD would adapt faster to significant changes in persistent demand (not a momentary peak).

The above should lead to a better user experience. For example, with this proposal, it would be less likely for an SP to be surprised by an outrageous base fee exactly when it wants to post its proofs.

Implementation

None currently.

Copyright

Copyright and related rights waived via CC0.

[matejpavlovic]

Nicely written. Just a few typos and other nits pointed out here (as comments) - HackMD was the fastest way of adding comments to this markdown.
One more comment (not on HackMD): Sometimes you mention just "average" in the text, where I would prefer "weighted average". Even though it is quite clear from the context what you mean, I still need to consciously convince my brain about it each time I read "average", as that is a well-defined term.

[guy-goren]

Thanks!
Regarding setting the parameters (and the AIAD in general) I think Even Miyazano might have some background in control theory that could be useful. @miyazono?

[miyazono]

if you're looking for a background in control theory, you're probably thinking of @jsoares

[juanpmcianci]

Hi Guy,

This is an interesting (and well-presented ;)) idea. Here are some thoughts:

• My biggest concern here is about the tradeoff between smoothing/variance reduction and responsiveness. Indeed, by taking the average operator you make the base fee more stable and less susceptible to sudden changes, which in turn makes it less responsive. This is a not ideal scenario when, e.g., the base fee is too high (as it has been lately), as it would take a significant amount of (almost) empty blocks to lower it. This might not be an issue in the future, but given recent levels of base fee, it probably is now.
• The theoretical argument depends on some threshold parameters that take things like miner tips into account. We should try to estimate these threshold for Filecoin before moving forwards.
• Another comment is that we should investigate the suggested choice of parameters in more detail.

I'd be happy to collaborate on understanding these two points a bit better. As for the second part, I'd also be happy to work together in figuring out an adaptive rate mechanism --I don't have an extensive background on control theory, but I have done some work in optimisation and inference, which are closely related.

[guy-goren]

Thanks for the review JP!

Regarding the tradeoff, it is definitely there albeit not very severe (because of the weights used in the averaging process). You can see in the figure below that the effect on the responsiveness is mild.

Therefore, if "it would take a significant amount of (almost) empty blocks to lower it", then the same holds in the current state of the system.
I hope this eases your concern, since, in this sense, we do no (significant) harm ;-)

[guy-goren]

Regarding the required tips-to-base fee ratio, indeed, I do not see it as an immediate threat to FIlecoin (I wish we had a demand similar to Ethereum where it is already a threat). Hence, I would not call it an "urgent fix" rather a "nice to have" one. Due to its simplicity, I think it is still worth doing.

[guy-goren]

Regarding the choice of parameters, I fully agree!
I suggest to first implement the weighted averaging part and do the adaptive learning rate in a later FIP -- when we'll have more data. The weighted averaging requires a single parameter so it is simpler than the AIAD which requires the calibration of 4 parameters. I would appreciate you "jumping on board" in investigating that! I'll send you a meeting invite to get things started 📧

[Kubuxu]

This looks great as far as the base fee itself goes. As I wrote shortly on Slack, I have some concerns about how to make it interface with our imperfect implementation of the base fee system.

Due to Filecoin consensus using tipsets and deferred execution, our implementation of the base fee contains non-trivial changes from the state of the art. These changes were made to adapt the base fee on a best-effort basis before Filecoin was deployed.

Deferred execution

Because Filecoin uses deferred execution, where messages land at epoch A and are executed at epoch A+1. The block space limiting works on GasLimit and not GasUsed as in other blockchains.

Multiple blocks in Tipset

Filecoin uses Tipsets, where multiple blocks at one epoch combine into a single tipset. Each Block proposes its list of messages to execute. Due to no coordination between block producers within one epoch, blocks within the tipset will contain duplicate messages.
After the Tipset is established at epoch A+1, blocks are ordered according to their VRF ticket, and messages are deduplicated among them. All messages from the first block are executed, then messages that were not yet executed are executed from 2nd block and so on.

On expectation, there are five blocks in the tipset, distributed according to Poisson distribution. Message selection run by SPs considers the "quality" of their VRF ticket when selecting messages to be included. It runs a heuristic algorithm where SP computes their probability of executing at a given order in the tipset and selects messages according to the expected value of being the one to execute a given message.

This means that each block individually carried messages corresponding to BlockGasLimit = 2*BlockGasTarget. It is after the deduplication process that the "used" GasLimit corresponds to roughly 5*BlockGasTarget.

The base fee update rule today is as follows:

$$b[i+1]\triangleq b[i] \cdot\left( 1+\frac{1}{8}\cdot\frac{\frac{\textrm{deduplicated gas limit}[i]}{N_{\textrm{blocks}}[i]} - \textrm{BlockGasTarget} }{\textrm{BlockGasTarget} } \right)$$

After talking with @guy-goren I don't think averaging of the $\frac{\textrm{deduplicated gas limit}[i]}{N_{\textrm{blocks}}[i]}$ will make things worse, but it might be worth investigating how to make base fee behave more optimally in the tipset system.

Exponential Moving Average

Without a significant increase in implementation complexity, the EMA could be replaced by 1st Order IIR filter (or even a higher order filter with a slight increase in complexity). This would improve the rejection of high-frequency noise in chain usage while not decreasing the response time.
Attached are plots for 1st and 3rd-order Maxflat filters with the same 3db cutoff point as the a=0.5 EMA and their comparisons against EMA.

[Kubuxu]

A note on filters, we can also design a more specific filter for this purpose, it would increase complexity a bit, but IIR filters are pretty easy to implement, even in a consensus-stable way. The complexity mainly stems from the fact that during the design of such a filter, more design decisions have to be made.

[Tanisha-fil]

FIP 0064 was discussed on today’s Implementers call, and I’m creating this thread so we can easily coordinate here on spec details. 🧵👇

Following the discussion and to help the community better understand the implications of this proposal and prepare for implementation review, could you please clarify two things:

1. Are there any known or potential attack vectors that we should be aware of given the proposed change in base fee calculation? CC: @Parth Shah
2. Have there been any simulations or test use cases (even preliminary ones) to validate the effects of this change — especially in terms of stability, incentive alignment, or impact on fee volatility?