Fee estimate patch #6618

Fee estimation uses a threshold for the fraction of recent transactions of a given fee rate that must have been confirmed within the target number of blocks in order for that fee rate to be considered high enough such that a new transaction with that fee rate will be likely to be confirmed within the target.

This patch changes the threshold to 95% (from 85%) for all targets other than 1 block.

85% was previously used because higher thresholds were too hard to meet for a target of 1. However the recent stress test has shown that 85% is not conservative enough, so a target of 1 is special cased and a higher threshold is used. This is a simple change that is meant to be backported to 0.11. Further improvements for fee estimation will hopefully be possible for 0.12.

EDIT: Please note that this will in general cause higher fee estimates to be returned.

oops, was trying to bump travis

the recent stress test has shown that 85% is not conservative enough

Are you aware of anyone reporting missed targets? (Haven't searched, excuse my laziness)

@MarcoFalke Yes. During the mid-July stress tests I had several reports of people placing transactions in accordance with fees returned by the estimation algo and waiting much longer than the expected number of blocks. This patch is not going to completely solve the problem that the current fee estimation logic can only provide a rough answer of what has happened historically, but its actually a very simple change and is worth it for the improvement. Better logic is waiting for a sorted mempool (and ideas about what to do with it).

concept ACK if some data can be provided to demonstrate tip-over points

@dcousens sorry, what's a tip-over point?

@morcos good question!

I meant to ask if you had any data related to the quote:

Yes. During the mid-July stress tests I had several reports of people placing transactions in accordance with fees returned by the estimation algo and waiting much longer than the expected number of blocks.

@dcousens This is the kind of data analysis I've looked at. Here's some data showing fee estimates in early July when one of the spam attacks started. The green line represents a much more recent history of transaction confirmation times (half-life of 36 blocks or so). You can see from the green line that once the attack starts around block 364130, you pretty immediately need a significantly higher fee to be confirmed within 5 blocks. However the old fee estimates don't really start increasing for about 50 blocks. The new fee estimates react much quicker. This is because if, historically, close to 100% of your transactions were being confirmed within the target, even if the number all of a sudden becomes 0%, it can take some time for the moving history to drop below 85% over the time horizon we use. Dropping below 95% happens much more quickly. I experimented with using a shorter time horizon but there was a lot of noise in the data. In the absence of this effect, I think its kind of an arbitrary choice as to what percentage of recent transactions should have been confirmed within the target number of blocks is the right answer to the fee estimate question.

I assume the bottom axis is the block height, and the left is the fee estimate? Why is the new 95% fee estimate higher before the peak (assumed peak at ~364140)? Or is there a subset of the data that I am not aware of?

edit: thanks for going into detail on this

Concept ACK.

@dcousens Correct on the axes. It's not surprising that the estimate can be higher even in the "steady state". It's answering a slightly different question. It may be that at block 364050 about 86% of transactions of feerate around 14K are being confirmed within 2 blocks. Passes the old test and not the new.

@morcos thanks for the explanation. However I feel the "steady state" being higher to start with doesn't agree with the statement you made earlier:

I think its kind of an arbitrary choice as to what percentage of recent transactions should have been confirmed

I don't necessarily have a strong opinion on this, as the intent seems to be to improve UX, but noticeably at the cost of higher fees by default.

@dcousens Fair enough, perhaps that is worth pointing out. I edited the initial PR comment. By arbitrary I just meant it's not clear what more closely maps to what people expect the answer for fee estimation to mean.

I'd like this to be merged, but I'm going to include it in a new and improved #6134