Improved fee estimation

[kantai]

The current fee estimator looks at mined blocks, and ranks the transactions in the block by their fee rate, taking the 5th, 50th, and 95th percentiles, and uses those three values as fee rate estimates.

This can lead to some problems -- it seems like very high fee estimates can be commonly obtained when STX transfers are broadcasted with fee amounts around 1 STX (STX transfers are much cheaper operations than contract-calls, like 50-100x cheaper, so when most transfers use fees around 1 STX, they imply that contract-calls should be 50-100 STX).

[timstackblock]

From todays meeting, here are some of the Test contracts from the test app. It would be great if these could returned some fee estimate data on testnet

Test Contract call
ST1X6M947Z7E58CNE0H8YJVJTVKS9VW0PHEG3NHN3.faker
Test NFT
ST9VQ21ZEGG54JDFE39B99ZBTSFSWMEC323MENFG.animal
Test BNS
ST000000000000000000002AMW42H.bns
website
https://btc-website.tintashlabs.com/
Test stell transfer
ST6G7N19FKNW24XH5JQ5P5WR1DN10QWMKQSPSTK7.stella-the-cat
Rocket tokens
ST1X6M947Z7E58CNE0H8YJVJTVKS9VW0PHEG3NHN3.dull-sapphire-bird

In Prod we test with the following coins:
USDC
MIA
DIKA
WMNO8
STX

When needed we also puchase NFTs in prod but wit the price isn't something we do frequently unless an issue calls for it.

[Eshwari007]

The list above is quite right and with that QA does another round of extensive testing with the use case(s) below:

Testnet:

Contract deployment which we test via Testnet demo app https://stacks-wallet-web.vercel.app/
Sandbox functions and contracts via Explorer.
/BNS functions included/

Mainnet
Similar use cases as above in Sandbox for various contracts and functions via Explorer

Integrated app(s)
Testing Mainnet on:
Arkadiko,
Bitcoin Bulls
Stackspunks
Megapont
STXNFT

cc @timstackblock @kantai

[kantai]

This is a graph of data from a stacks-node over the last two days. It shows the median fee rate (measured as ustx per 1/60kth of the block limit) in each Stacks block in blue, and the corresponding "middle" estimate in the node in purple.

Looking at this data, it seems like there's a couple of things happening. First, there's massive outlier blocks -- you can see three or four peaks in that graph, two of which approach 1m ustx per 1/60kth of the block limit. Such a fee rate would lead to normal contract-calls costing 50s to 100s of STX in fees. For STX transfers, it implies a cost of just 1-3 STX. These outlier blocks swing the estimate dramatically, and the estimate remains high for a long period of time after the outlier. Second, these outlier blocks appear to be mostly caused by blocks that have exclusively STX transfers (which tend to be large fee rate outliers):

0x94cd4829829efe814c0555681f0e6f9911b612609f88e04d8e74bb3c0f4fc

I'm not 100% sure what this all tells us about solving this problem, but I think there's a couple noteworthy things:

1. The way that we are integrating the new block information is very sensitive to blocks which are outliers
2. The way that STX transfers interact with fee rates can create outliers
3. Blocks which are far from full are more likely to be outliers
4. Using data from mined blocks, as opposed to data from the mempool can create a ratching fees situation for users (not born out yet in the data, but a point raised by @obycode and @gregorycoppola).

It seems like solving (1) would be the most readily achievable -- altering the update function from a simple exponential windowing to something that's much "stickier" like median of a window could solve this issue. Solving (2) and (3) also seems readily achievable, but wouldn't eliminate the possibility of outliers entirely. Solving (4) seems like the trickiest of the bunch: the current implementation assumes a lot about using a mined block as input rather than the mempool, and beyond that, the structure of our mempool makes deciding what's "in" or "out" of the mempool tricky.

[obycode]

When blocks are not full, a fee of 0 for the percentage of the block which was left unused should be factored into the estimation.

[kantai]

After looking at some of the data more, and talking through possible approaches with @jcnelson, I think the best approach is something like the following:

1. Address outlier block sensitivity by using a median of a window, rather than exponential windowing.
2. Address impact of STX transfers by using percentiles weighted by the proportion of the block limit consumed rather than 5th, 50th, and 95th percentiles. See weighted percentiles.
3. Address impact of non-full blocks by treating the non-full proportion of the block as a transaction at the relay fee minimum (a fee of 0 is too low for admission to the mempool).
4. Because of the difficulties related to using the mempool for fee rate estimation (it's hard for non-miners to know which transactions in the mempool are valid candidates for the next block without trying to simulate mining them), we should address fee changes in the face of congestion using a strategy of "fuzzing" the estimated fee rate: when queried, nodes will add some random noise to the estimated fee rate. In periods of congestion, clients that used the higher fee would be included in the next block, pushing the fee estimate for the next block up. As congestion clears, lower fee transactions would be included in blocks (and blocks would become less full), reducing the fee rate estimate again.

The above approach gives us a relatively straight-forward way to fix the issues we see with the estimator now, but other approaches may be necessary long term: ultimately, fee estimation should use information gleamed from the mempool. We can test how well the above approach works with the existing block data for solving problems 1-3, but we will need to do more testing for problem 4-- we can implement an integration test that uses the fee rate estimator and tests behavior during congestion, but we should also perform some explicit tests on testnet as well.

[kantai]

Okay -- some data from some initial experimentation:

This graph plots the "middle" estimate for each block from 39,485 to 39,685, calculated with three different methods. The blue line computes the middle the same way the current stacks-node does: simple median of the block's fee rates. The yellow line computes the middle using the weighted median. The red line uses a weighted median and simulates filling the block with rate=1 transactions.

You can see that the weighted median lowers the estimates (which is expected: weighted medians will down-weight stacks transfers, which typically have the highest fee rate), but it does not eliminate the outlier blocks. That is because the big outlier blocks are usually very nearly empty -- their fee rate is determined by one or two transactions, which won't change when the fee rates are just weighted. Adding block fill eliminates these outliers and reduces the estimate a lot in empty-ish blocks.

The next set of experiments was intended to test the fee rate estimates as the blocks are processed. These graphs show two different tests: first, using the weighted medians and block fill to compute each block's stats and, second, using the unweighted median (i.e., current implementation). In each graph, two methods for estimating over a window are used: the current exponential windowing method and then the median of a 5-block window.

You can see that median windowing does indeed deal with outliers much more smoothly. However, with the better processed block metrics, it isn't quite as sharp of a difference (because there are fewer outliers).

If you're interested in playing with these methods and data, the scripts I used for generating the underlying data is available in kantai/stacks-block-fee-metrics

[314159265359879]

Suggesting to default to the network minimum fee for the "low" option instead of an arbitrary max.

I am adding a copy to this here because it has already gotten some thumbs up here: leather-io/extension#2086

[falkonprods]

My question is (and pardon my late entrance): how can we rely on historical rates if we have never had accurate estimation? We are pushing things through at 0.75 STX due to current wallet defaults, but in my discussion with Clarity devs and other members of the Stacks community, it seems that many transactions go through (anecdotally) for .005 or .001. Shouldn't we at least use this as the minimum/baseline? Also, if the network goes through a period of instability (ie Megapont Robot drop), then the historicals will be high even though the network has since recovered. Wouldn't we be better off looking at mempool levels or some other performance metric - if not solely, then in addition to these estimates?

Additionally, I have had issues with contract calls like mint-many where the smart contract is, in fact, performing multiple transactions and thus requires more gas. We perhaps need a methodology for developers to be able to either flag these types of calls to be recognized by the wallet, or to override defaults.

If this work is already done, that's great, but I do think it deserves further discussion, perhaps in a new issue.

[gregorycoppola]

@314159265359879 That would be an interesting idea. Keep in mind that there are different levels to what is going on behind the scenes. So, we could return the 5th percentile at one level, and then minimum fee at another level.

[gregorycoppola]

@falkonprods That is a good point. We are using these past-data estimates as a kind of "85% solution", because it might be harder to use the mempool to make the estimates.

I think discussion can continue on how to use the mempool instead.

[falkonprods]

@gregorycoppola to be fair, I think this is a good long term solution, the question is how do we first normalize the gas fees to accurate levels.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[314159265359879]

lets keep this active. MattySTX mentioned in the SIP call today that his latest report on Stacking and Mining indicates there isn't a functioning fee market yet:

The number of transactions has increased while the total fees payed has decreased. Likely because blocks are not fully utilized yet. As the network grows and the number of transactions increases, improved fee estimations will be important for a functioning fee market to establish.

When the speed of L1 blocks goes up by a lot (as looked into by the working group), it may be more important to use the mempool as the basis for the estimations?

[jcnelson]

Assigning to @kantai for now. Please re-assign as you see fit.

[kantai]

I think this should be converted to a discussion: "improving fee estimation" is a path, not a destination. The fee rate estimator did improve since this issue opened, but more improvements can be done. However, specific improvements should get specific issues, and specific issue reports should get specific issues. The behaviors that spawned this particular issue have been addressed (spiking fee estimations).

Unless someone feels strongly that this should remain an issue rather than a discussion, I'll hit that convert button on Monday.

[badonyx]

I have done some work exploring this here: https://stacksonchain.com/dashboards/Gas-Fees-Mempool/186

I assume miners prioritize by fee rate per tx size, but I have not checked if or how this is actually done in the node software. For simplicity I estimate the fees for a standard STX transfer which is around 180 bytes.

I reproduce the existing fee estimate like this:

-- https://www.hiro.so/blog/improved-fee-estimations-in-the-hiro-wallet-and-stacks-api
-- Fee estimates for STX transfers (180 bytes) via the method used by Stacks/Hiro API.
-- Hiro wallet uses these values but with an artificial lower bound at 0.003 or 0.0025.

select to_char(PERCENTILE_CONT(0.05) within group (order by fee_rate/length(raw_tx)) * 180/1e6,'990D999999') as "Low"
     , to_char(PERCENTILE_CONT(0.50) within group (order by fee_rate/length(raw_tx)) * 180/1e6,'990D999999') as "Standard"
     , to_char(PERCENTILE_CONT(0.95) within group (order by fee_rate/length(raw_tx)) * 180/1e6,'990D999999') as "High"
from txs
where block_height > get_max_block() - 5

I created an alternative heuristic fee estimate based on mempool analysis like this:

-- Fee estimates for STX transfers (180 bytes), by mempool analysis.

with const as (
select min(fee_rate/length(raw_tx)) as min_fee_rate
from txs
where block_height > get_max_block() - 10
and fee_rate > 0
)

, last_tx as (
select distinct on (sender_address) sender_address, nonce
from transactions tx
where exists (
    select * from mempool where sender_address = tx.sender_address
)
order by sender_address, nonce desc
)

select to_char(min_fee_rate * 180/1e6, '990D999999') as "Casual"
, to_char( PERCENTILE_CONT(0.10) within group (order by fee_rate/pg_column_size(payload)) * 180/1e6
    , '990D999999') as "Normal"
, to_char( PERCENTILE_CONT(0.50) within group (order by fee_rate/pg_column_size(payload)) * 180/1e6
    , '990D999999') as "Fast"
, to_char(avg(fee_rate/pg_column_size(payload)) * 180/1e6, '990D999999') as "Rush"
from mempool mem
left join last_tx last using (sender_address)
cross join const
where receipt_time > now() - interval '6 hours'
and fee_rate > 0
and ((last.nonce is not null and mem.nonce > last.nonce) or (last.nonce is null and mem.nonce = 0))
group by min_fee_rate

In summary, this does the following:

• Estimate the bare minimum fee from the minimum fee rate in the last 10 blocks.
• Filters the mempool by receipt time (last 6 hours) and nonce validity (not previously used), then makes various suggestions based on statistics for the fee rates.

Caveats:

• Not sure if miners actually prioritize by fee rate per byte or absolute fee.
• Seems like there is a minimum absolute fee setting so that should be accounted for rather than minimum fee rate per byte.
• The mempool probably could be filtered more since it seems like there are always some dead transactions not going through for various other reasons than previously used nonce, e.g. distant future nonce without a series of mempool transactions leading to it.

At time of writing this is the result for the existing estimate:

Low	Standard	High
0.000180	0.001800	0.249840

And this is the result for the new estimate:

Casual	Normal	Fast	Rush
0.000180	0.000000	0.001800	0.036069

(Sometimes the "normal" result comes out as zero and I'm not really sure why.)