[feature]: sweep: implement alternative fee functions

[morehouse]

The current LinearFeeFunction is reasonable for short deadlines (e.g., < 10 blocks) where it is critical to confirm things quickly, but it may be overly aggressive for longer deadlines (e.g., 80+ blocks).

By implementing other fee curves we can optimize for different deadlines and save fees. See @yyforyongyu's thorough evaluation of several curves.

[feelancer21]

Hello Matt,
would like to hijack the issue, as I also have methodological concerns about the LinearFeeFunction, which I have illustrated below with another alternative.

I'd be interested in feedback from those reading along on the alternative. If there are no objections, I would like to start a first implementation draft in the coming weeks.

Btw: Regardless of the methodology, there still seems to be an issue with calling the fee function. Otherwise it is not possible to explain why this pleb ended up at 1000 sat/vb although he was permanently online and onchain fees were low.

https://mempool.space/tx/2a5b92a5be69799f9eb919e54426248c6fcb9c85e44692711761e34b1b1b2068

Downsides of the LinearFeeFunction

The LinearFeeFunction is initialized with a maxFeeRate, which is set by default to 1000 sat/vbyte, and can be adjusted via configuration down to 100 sat/vbyte. I see some downsides. If I have misunderstood something, don't hesitate to correct me.

• When using the default setting, the function becomes very steep depending on CLTV. With a CLTV of 40 blocks, the linear fee function increases by about 25 sats/vbyte per block. At 144 blocks, the increase is around 7 sats/vbyte per block.

• The function becomes steeper if it is initialized at a later stage, such as when a node comes back online after an extended downtime. In the extreme case where we need to sweep a pending HTLC that has already exceeded its deadline, we are forced to pay the maxFeeRate.

• This also means that two fee functions that were initialized with the same absolute deadline but at different times due to different CLTVs have different values and steepnesses for the same conf_target.

• Node runners can only control the steepness of the function by lowering the maxFeeRate via configuration. While they may do so, with a 100 sat/vbyte floor, people risk losing their funds in a high-fee environment because the linear fee function is capped at this value. But people are more likely to forget.

Alternatives

endingFeeRate depending on on-chain fees

We could make the endingFeeRate dynamic by using the current on-chain fee rate for a conf_target of 1 or 2. However, this approach risks a sweep not getting confirmed if on-chain fee rates increase very slowly.

Model with a limited exponential fee function

We define a function $g(x)$, which depends on the current conf_target $x$. The actual fee function is min(maxFeeRate; g(x)).

For the definition of $g$, we need the following parameters:

• $\lambda \in [0;1]$
• $m \geq 0$
• The current on-chain fee $f(x)$ at the time the function is called
  Edit: With “current on-chain fee” I meant the current return value of the estimator for the number of blocks until deadline

Now we can define:

$$ g(x):=(m\lambda^{x-1} + 1)\cdot f(x) $$

This function has the following properties:

• $g(x) \geq f(x)$, meaning it always returns values at or above the current on-chain fees.
• $g(x) \leq (m+1)\cdot f(x)$ and $g(1)=(1+m)\cdot f(1)$, which means our fee function has an upper limit with a safety buffer capped at $m\cdot f(x)$. This buffer is dynamic and scales with the current on-chain fees.
• $\lambda$ allows us to control the speed at which we approach the maximum of $(m+1)\cdot f(x)$.

Let's examine how the factors $m\lambda^{x-1} + 1$ behave for different scenarios of conf_targets $x$ and various $\lambda$ values. We assume $m=1$, meaning we pay a maximum of twice the current on-chain fees.

	0.9	0.95	0.975	0.99
1	2	2	2	2
6	1.59	1.77	1.88	1.95
40	1.02	1.14	1.37	1.68
144	1	1	1.03	1.24

With $\lambda=0.975$, we see a surcharge of 37% on top of the on-chain fees 40 blocks before the deadline, making it less likely that confirmation will not occur before this time. If $m=2$, the surcharge is doubled.

Overall, the likelihood of not getting a confirmation with the model is very unlikely. This is actually only possible if the fees increase faster from block to block than the risk buffer at the time.

Edit:

• durign implementation we have to think about the case $\lambda=0$, because it leads to a $0^0$ situation

[yyforyongyu]

The LinearFeeFunction is initialized with a maxFeeRate, which is set by default to 1000 sat/vbyte

This is incorrect. A fee func is always initialized with an ending feerate derived from the budget. Only when the budget feerate exceeds the maxFeeRate will the default 1000 sat/vb be used. This is detailed in the readme.

As for the budget, you can already configure it as detailed in this section.

The whole point of the budget-based design is to move away from fee estimators, instead, we want to limit how much fees we want to pay in sats, as it's more accurate than using fee rate to restrict the onchain cost.

I do think the fee func can be expanded, this is why there's this report as a starting point. If we want to implement more algorithms, I think we need to update the report, run the simulations, and update our knowledge about the effects of the different algorithms.

[feelancer21]

The LinearFeeFunction is initialized with a maxFeeRate, which is set by default to 1000 sat/vbyte

This is incorrect. A fee func is always initialized with an ending feerate derived from the budget. Only when the budget feerate exceeds the maxFeeRate will the default 1000 sat/vb be used. This is detailed in the readme.

Sorry, it was not my intention to portray anything as incorrect. With the usual htlc sizes and with the default settings of the budgets, however, it will usually always run out to 1000 sat/vb as initial param. An HTLC of 300k is completely sufficient.

I also think a budget-based approach is very good. However, I would only see a budget as a final cap on the output and not as a target value for the algorithm. The cap should be preceded by a function that returns a very risk-averse value based on the current on-chain fee estimates. I have described a possible model approach above.

[yyforyongyu]

however, it will usually always run out to 1000 sat/vb as initial param. An HTLC of 300k is completely sufficient.

Suppose we are sweeping an incoming HTLC in a tx, the estimated weight is 1142 wu, given the max fee rate of 1000 sat/vb, which is 250 sat/wu, and a default budget conf of 50%, the HTLC must be greater than 571k sats to reach the max fee rate, since the ending fee rate is calculated using 571000 * 0.5 / 1142.

For outgoing it's a similar value, around 533k. But due to a temp issue this is 4x smaller until #7683 is fixed.

On the other hand, if the HTLC has a large value, it's recommended to cap the budget using --sweeper.budget.deadlinehtlc to a desired value.

The cap should be preceded by a function that returns a very risk-averse value based on the current on-chain fee estimates.

Aside from being budget-based, the sweeper is also deadline-based, which means it has already considered the timeout risk. For every block the tx is unconfirmed, there's always a tradeoff - spend more to wait for fewer blocks, or spend less but wait a few more blocks. And the idea here is, the user specifies the max fees he/she is willing to pay to get it confirmed before the deadline hits.

As for the model, the important question is, given the current reliability of fee estimators, how do you know "the current on-chain fees"? If the fee estimators can accurately tell us the network feerate, we don't even need the fee function.

[feelancer21]

For outgoing it's a similar value, around 533k. But due to a temp issue this is 4x smaller until #7683 is fixed.

I had this example in my mind. Maybe the issue was the reason that 315k were enough
https://mempool.space/address/bc1qsqdgl7kh5krwrh0jfncjgd93uxmeuapf7p403asxrwlseyvxwswqfm5l7f

As for the model, the important question is, given the current reliability of fee estimators, how do you know "the current on-chain fees"? If the fee estimators can accurately tell us the network feerate, we don't even need the fee function.

By “current on-chain fees” I meant the current return values of the estimator for the number of blocks until deadline. However, this can only be a lower limit on which a multiplier must be applied as a risk buffer in order to be really safe. To determine the multiplier, the noderunner can surgically analyze the historical on-chain data or simply make a conservative expert estimate.