When calculating a median fee for a confirmation target at a particular threshold, we analyse buckets in ranges rather than individually in case some buckets have very little data. This patch ensures the breaks between ranges are independent of the the confirmation target.
Fixes #20725
This is currently giving me somewhat lower feerate estimates on mainnet – 173sat/vb becomes 142sat/vb for 4 blocks, 82sat/vb becomes 65sat/vb for 25 blocks. Not sure if that’s fixing a bug, or introducing a bug though – I don’t think it’s noise, because I’m also seeing a reduction when running the estimates against the fixed fee_estimates dat I had in #13990.
EDIT: at first glance looks like these fee differences were due to the mishandling of fail buckets morcos describes below
Nice find on the bug and I think you’ve more or less identified the problem (I think I recapped it below)
However I believe there are 2 issues with your potential fix.
I think there is a new quadratic behavior now where if there are consistently not enough transactions in the buckets, you’ll count up all the buckets to determine that, and then again all the buckets except the top one and so on… Or some lesser variation on that if there are enough transactions at some point. Not sure if thats actually a problem.
I believe in your code you now only extend bucket ranges to achieve the required number of transactions, whereas the old code extended bucket ranges for that reason OR if the current buckets were failing. It’s that second condition that caused the bug because the bucket ranges didn’t always match between targets, BUT I believe its important not to just eliminate that. The reason the search for passing buckets continues even after you find a failing bucket is that you don’t want to allow for the possibility that a small number of stuck transactions at a high feerate can peg fee estimates to be stuck at a high level. Your code still solves for that, but it now completely ignores those failed transactions which I fear could lead to a different type of manipulation where a very low bucket of just enough transactions could be confirmed and it would cause the estimator to return artificially low estimates even if the vast majority of transactions at higher fee rates were not being confirmed.
I’ll try to check IRC over the next few days if you want to ping me to discuss further. A solution is not immediately apparent to me. It’s possible that the best solution is to just relax the requirement that fee rates have to be monotonically decreasing as confirmation target increases. These are edge cases where it’s not clear which answer would be better anyway. I think the monotonic requirement was good as a QA check, but at this point may be causing more harm than good.
Problem recap:
Imagine only 2 buckets and an 85% threshold:
feerate: 100 sat/vb has 2/2 transactions confirmed within a target of 3 blocks (same within a target of 4 blocks.)
feerate: 150 sat/vb has 84/100 transactions confirmed within a target of 3 blocks and 85/100 transactions within 4 blocks.
The estimate for 3-block target fails at 150 sat/vb but passes when you add in the 100 sat/vb bucket, so it returns a median fee somewhere in the middle of those 2 buckets.
On the other hand the estimate for the 4-block target passes at 150 sat/vb, but then does not have enough data at 100 sat/vb alone and fails. So it returns a median fee in the 150 sat/vb bucket (HIGHER than the rate for the 3-block target)
@morcos Yes, that makes sense! I think I’m only looking at each bucket once (bucket is always what I’m looking at, and it’s only decremented never reset/incremented), so there shouldn’t be quadratic behaviour – though it was getting late so what was in my head may not match what was in my editor…
Agree that the new code is ignoring high feerate failures now and that that is wrong; I think I’ve got an idea how to fix that, will see about updating the PR over the weekend.
Problem recap: Imagine only 2 buckets and an 85% threshold: feerate: 100 sat/vb has 2/2 transactions confirmed within a target of 3 blocks (same within a target of 4 blocks.) feerate: 150 sat/vb has 84/100 transactions confirmed within a target of 3 blocks and 85/100 transactions within 4 blocks.
The estimate for 3-block target fails at 150 sat/vb but passes when you add in the 100 sat/vb bucket, so it returns a median fee somewhere in the middle of those 2 buckets.
I think in this case the 4-block target would calculate:
2 < 0.5/(1-0.962) ~= 26.3]and 3-block target would say:
but that just gives a higher fee to the lower target which is correct.
I think the actual bug needs more than 2 buckets, so that you get:
at which point they start locking at separate bucket sets, and get:
at which point 3-blocks is locking for a median in 180-250 sat/vb while 4 blocks is looking for a median in 190-250 sat/vb and the higher target can get a higher fee rate.
test/functional/feature_fee_estimation.py --randomseed 108574360997204915 passes with this patch. I need to study this code more.
Ah, perhaps I misread on the quadratic issues.
Not that it really matters, but I think both of our recaps of the problem were not quite right. In the first part of your recap, the count for sufficient number of transactions resets when a passing bucket is found so 100 sat/vb would not be passing for a 4-block target. but you are right that in my version the 3-block target would find the median fee in the 150 bucket which would still be ok. So yeah something like your more complicated scenario is probably what happens.
What you’ve done with a5e33d3b782d33dc71653912e2d370f9a06b79e4 looks like it should work. I’d be a little worried there is some unintended consequence though. What I would have done in the past with a change like this is to run the fee estimator through historical transaction and block data and then look at places where the new and old differed and make sure that I thought the difference made sense. Not sure how easy that is for anyone to do right now.
Don’t have historical data but i’ve been running an estimatesmartfee (on 1, 3, 6, 12, 24, 48 and 100) every 15 seconds on both this branch and master for some time (~15 hours).
Here are my findings so far, this branch seems to give constantly increasing and higher estimates and i believe there is definitely something wrong with estimates for large targets.
Github won’t let me upload a csv, so here:
222@@ -223,6 +223,11 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
223 unsigned int curFarBucket = maxbucketindex;
224 unsigned int bestFarBucket = maxbucketindex;
225
226+ // We'll always group buckets into sets tha meets sufficientTxVal --
that meet
When calculating a median fee for a confirmation target at a particular
threshold, we analyse buckets in ranges rather than individually in
case some buckets have very little data. This patch ensures the breaks
between ranges are independent of the the confirmation target.
There hasn’t been much activity lately. What is the status here?
Finding reviewers may take time. However, if the patch is no longer relevant, please close this pull request. If the author lost interest or time to work on this, please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.
I don’t have a ton of background on the fee estimator but understanding here is:
EstimateMedianVal we group buckets together until they meet sufficientTxVal i.e. have enough data before we check if this range meets success rate or not. We accumulate the total txns for the current range into totalNum and check if there’s enough.sufficientTxVal.
totalNum depends on whether success rate is met.Here are my findings so far, this branch seems to give constantly increasing and higher estimates and i believe there is definitely something wrong with estimates for large targets.
I’m not seeing the behaviour you did (and what you saw doesn’t make sense to me). For me, duplicating node state, and starting two nodes, one with this pr, and one without it, I see fee rates tracking each other pretty precisely.
Fwiw I hacked together a branch that implements both EstimateMedianVals (i.e. master and this branch) and returns feerates using both implementations from estimatesmartfee, to eliminate differences from having slightly different mempools, timing, etc. They are giving me the same feerates every time. I cleared fee_estimates.dat, same thing. I could have implemented it wrong, but I also don’t see how the huge differences could happen based on my understanding of the code.
I don’t have a ton of background but if this doesn’t have a significant impact on fee estimates in practice, it seems worth trying. The test still fails semi-regularly (#25179, #20725, #23165).
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For detailed information about the code coverage, see the test coverage report.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | glozow, jonatack, ismaelsadeeq |
| Concept ACK | darosior, meshcollider |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
The issue this is solving occurs intermittently. The test failed on recent master c325f0f with seed from @mzumsande and passed on this PR rebased on master head c325f0f.
Reading through to understand the patch in progress
Approach ACK
What I understand from the discussion and the code, the issue this PR is solving is that intermittently CBlockPolicyEstimator returns higher fee estimates for higher confirmation targets, but as confirmation target increases the fee estimate suppose to decrease.
This occurs because of the way the CBlockPolicyEstimator estimateMedianVal works.
estimateMedianVal keeps accumulating fee rate buckets until the total fee rates in the accumulated buckets reaches the sufficientTxVal (number of fee rates enough to make a valid fee estimate)
i) If number of fee rates in the range of the buckets after the accumulations did not meet the success threshold we keep accumulating fee rate buckets until we reach the success threshold, then reset the number of fee rates we have and go to step 1.
ii)Else if number the fee rates in the range of the accumulated bucket met the success threshold, we reset the number of fee rates we have go to step 1.
Hence the the number of fee rates (bucket ranges) that we use to determine the success threshold sometimes overlaps the sufficientTxVal which means bucket ranges are not consistent for some confirmation targets.
We end up having a high fee for a higher confirmation target.
I will expand on the example @ajtowns gave to show how this occurs
Assuming
Success threshold = 85%
sufficientTxVal = 40 fee rates
| Feerate Bucket | Txs | 3 Conf target Conf Txs | 4 Conf target Conf Txs |
|---|---|---|---|
| 200-250 s/vb | 40 | 32 | 32 |
| 190-199 s/vb | 30 | 25 | 28 |
| 180-189 s/vb | 38 | 35 | 35 |
| 170-179 s/vb | 0 | 0 | 0 |
| 160-169 s/vb | 0 | 0 | 0 |
| Feerate Bucket | Txs | Conf Txs | Success Rate Calculation | Result |
|---|---|---|---|---|
| 200-250 s/vb | 40 | 32 | 32/40 = 80% | Failed - Does not meet threshold |
| 190-199 s/vb | 30 | 25 | (32+25) / (40+30) = 81.4% | Failed - Does not meet threshold |
| 180-189 s/vb | 38 | 35 | (32 + 25 + 35) / (40 + 30 + 38) = 85.1% | Passed |
| 170-179 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
| 160-169 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
Median Fee: 180-250 Fee rate bucket
| Feerate Bucket | Txs | Conf Txs | Success Rate Calculation | Result |
|---|---|---|---|---|
| 200-250 s/vb | 40 | 32 | 32/ 40 = 80% | Failed - Does not meet threshold |
| 190-199 s/vb | 30 | 28 | (32 + 28) / (40 + 30) = 85.7% | Passed |
| 180-189 s/vb | 38 | 35 | Failed Does not reach sufficientTxVal |
Failed |
| 170-179 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
| 160-169 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
Median Fee: 190-250 Fee rate bucket
Confirmation target 4 fee rate will end up being higher than 3.
With this PR
Buckets ranges are consistent i.e. once we reach the sufficientTxVal of 40 and did not meet success rate we dont keep accumulating we start counting a new sufficientTxVal.
| Feerate Bucket | Txs | Conf Txs | Success Rate Calculation | Result |
|---|---|---|---|---|
| 200-250 s/vb | 40 | 32 | 32/40 = 80% | Failed - Does not meet threshold |
| 190-199 s/vb | 30 | 25 | Does not reach sufficientTxVal |
Failed |
| 180-189 s/vb | 38 | 35 | (25 + 35) / (30 + 38) = 88.2% | Passed |
| 170-179 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
| 160-169 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
Median Fee: 180-199
| Feerate Bucket | Txs | Conf Txs | Success Rate Calculation | Result |
|---|---|---|---|---|
| 200-250 s/vb | 40 | 32 | 32/40 = 80% | Failed - Does not meet threshold |
| 190-199 s/vb | 30 | 28 | Does not reach sufficientTxVal |
Failed |
| 180-189 s/vb | 38 | 35 | (28 + 35) / (30 + 38) = 92.6% | Passed |
| 170-179 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
| 160-169 s/vb | 0 | 0 | Does not reach sufficientTxVal |
Failed |
Median Fee: 180-199 Fee rate bucket
Hence it is will not be higher because.
These bucket ranges are consistent regardless of what the target is, since the total number of transactions isn’t different.
The above example also indicates that the number of transactions will not change [Txs column] irrespective of confirmation target, the bucket range and the data points are the same and will not overlap.
Also originally for e.g given a bucket range of 200-250 with 40 transactions, the confirmed transactions of target 2 is 32, then the number of confirmed transactions for target 3 above must be 32 above.
This PR ensures the fee estimate will decrease monotonically as the confirmation target increases.
I will test the fee estimate in this branch against the fee estimate on master to see if there is much difference, but I don’t think this will bring any unintended results though given this extensive test
288@@ -283,7 +289,14 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
289 // we can test for success
290 // (Only count the confirmed data points, so that each confirmation count
291 // will be looking at the same amount of data and same bucket breaks)
partialNum conditional that is replacing the previous totalNum one.
Initial ACK a5e39d325da4eeb9273fb7c919fcbfbc721ed75d
Running both of these locally
./test/functional/feature_fee_estimation.py --randomseed 7288975409214300634
./test/functional/feature_fee_estimation.py --randomseed 5585159971690227248
fails for me on master and works with this branch rebased to master.
The test itself looks correct and the issue appears to involve the code in question here.
Per the test output with the following diff, it looks like the only feerates changed in the test with this PR (rebased to master) compared to master are related to the failing fee estimate cases. And also that the fee reasons remain the same.
0diff --git a/src/rpc/fees.cpp b/src/rpc/fees.cpp
1index 62396d4c589..d8d82921210 100644
2--- a/src/rpc/fees.cpp
3+++ b/src/rpc/fees.cpp
4@@ -47,6 +47,7 @@ static RPCHelpMan estimatesmartfee()
5 RPCResult::Type::OBJ, "", "",
6 {
7 {RPCResult::Type::NUM, "feerate", /*optional=*/true, "estimate fee rate in " + CURRENCY_UNIT + "/kvB (only present if no errors were encountered)"},
8+ {RPCResult::Type::STR, "fee_reason", /*optional=*/true, "fee reason returned by estimator (only present if no errors were encountered)"},
9 {RPCResult::Type::ARR, "errors", /*optional=*/true, "Errors encountered during processing (if there are any)",
10 {
11 {RPCResult::Type::STR, "", "error"},
12@@ -91,6 +92,7 @@ static RPCHelpMan estimatesmartfee()
13 errors.push_back("Insufficient data or no feerate found");
14 result.pushKV("errors", errors);
15 }
16+ result.pushKV("fee_reason", StringForFeeReason(feeCalc.reason));
17 result.pushKV("blocks", feeCalc.returnedTarget);
18 return result;
19 },
20diff --git a/test/functional/feature_fee_estimation.py b/test/functional/feature_fee_estimation.py
21index 4f56d585d3f..47b86704740 100755
22--- a/test/functional/feature_fee_estimation.py
23+++ b/test/functional/feature_fee_estimation.py
24@@ -95,6 +95,7 @@ def check_smart_estimates(node, fees_seen):
25 mempoolMinFee = node.getmempoolinfo()["mempoolminfee"]
26 minRelaytxFee = node.getmempoolinfo()["minrelaytxfee"]
27 for i, e in enumerate(all_smart_estimates): # estimate is for i+1
28+ print(e)
29 feerate = float(e["feerate"])
30 assert_greater_than(feerate, 0)
31 assert_greater_than_or_equal(feerate, float(mempoolMinFee))
estimatesmartfeecons that uses consistent bucket ranges, that is a5e39d325da4eeb9273fb7c919fcbfbc721ed75d version of estimatemedianval I made sure thats the only diff between estimatesmartfeecons and estimatesmartfee (which uses the default master estimatemedianval).
I then run a script that gets the fee estimates with the two rpc’s after every 10 minutes from block 811834 to 811844.
Fee estimates are pretty much the same and consistent. see here
Labels
TX fees and policy
Milestone
27.0