Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fee estimation: extend bucket ranges consistently #21161

Merged
merged 1 commit into from Nov 2, 2023

Conversation

ajtowns
Copy link
Contributor

@ajtowns ajtowns commented Feb 12, 2021

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

@ajtowns
Copy link
Contributor Author

ajtowns commented Feb 12, 2021

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

Copy link
Member

@darosior darosior left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK

@morcos
Copy link
Member

morcos commented Feb 12, 2021

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.

  1. 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.

  2. 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)

@ajtowns
Copy link
Contributor Author

ajtowns commented Feb 13, 2021

@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.

@ajtowns ajtowns force-pushed the 202102-fee-bug-medianval branch 2 times, most recently from f7d5e9c to a5e33d3 Compare February 13, 2021 07:41
@ajtowns
Copy link
Contributor Author

ajtowns commented Feb 13, 2021

Updated -- I traded in my hatchet for a scalpel; think this should exactly fix the problem.

@ajtowns ajtowns changed the title Fee estimation: don't extend bucket ranges Fee estimation: extend bucket ranges consistently Feb 13, 2021
@ajtowns
Copy link
Contributor Author

ajtowns commented Feb 13, 2021

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:

  • 150 sat/vb has 85/100 -- passing, 150sat/vb is good
  • 100 sat/vb has 2/2 -- also passing, 100sat/vb is good [EDIT: fails because 2 < 0.5/(1-0.962) ~= 26.3]
  • median value is in the 100 sat/vb bucket

and 3-block target would say:

  • 150 sat/vb has 84/100 -- not passing, extend
  • 100 sat/vb has (84+2)/(100+2) -- passing
  • median fee is in the 150 sat/vb bucket

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:

  • 200-250 sat/vb buckets; 3-block / 4-block: failing
  • 190-250 sat/vb buckets: 3-block failing, 4-block: passing

at which point they start locking at separate bucket sets, and get:

  • 3-blocks: 180-250 sat/vb buckets: 3-block passing
  • 3-blocks: 0-170 sat/vb: not enough info
  • 4-blocks: 0-190 sat/vb: not enough info

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.

@jonatack
Copy link
Contributor

Concept ACK on initial, non-expert look and test/functional/feature_fee_estimation.py --randomseed 108574360997204915 passes with this patch. I need to study this code more.

@morcos
Copy link
Member

morcos commented Feb 15, 2021

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 a5e33d3 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.

Copy link

@Softaljokar Softaljokar left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

good gob

@darosior
Copy link
Member

darosior commented Feb 20, 2021

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.

1 block target

1_block

3 blocks target

3_blocks

6 blocks

6_blocks

12 blocks

12_blocks

24 blocks

24_blocks

48 blocks

48_blocks

100 blocks

100_blocks

points

Github won't let me upload a csv, so here:

Copy link
Contributor

@meshcollider meshcollider left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK!

src/policy/fees.cpp Outdated Show resolved Hide resolved
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.
@ajtowns
Copy link
Contributor Author

ajtowns commented Sep 2, 2022

Rebased so tests can update.

@darosior 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. I've put my data in a google sheet (the pr21161 log has ~12 less entries than the master one, so they're up to 10 minutes out of sync by the end).

@DrahtBot
Copy link
Contributor

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.

Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't have a ton of background on the fee estimator but understanding here is:

  • In 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.
  • Before, we would reset the stats if we did meet the success rate. Now, we reset every time we meet sufficientTxVal.
    • Past bucket ranges would be dependent on what the confirmation target is because resetting totalNum depends on whether success rate is met.
    • These bucket ranges are consistent regardless of what the target is, since the total number of transactions isn't different.

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).

@DrahtBot
Copy link
Contributor

DrahtBot commented Mar 21, 2023

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

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.

Copy link
Member

@ismaelsadeeq ismaelsadeeq left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@ismaelsadeeq
Copy link
Member

ismaelsadeeq commented Oct 2, 2023

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.

  1. 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)

  2. 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

Our fee rate buckets data points are:
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
On Master
Confirmation Target: 3
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

Confirmation Target: 4
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.

Confirmation Target 3 will then be
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

Confirmation Target 4 will also be
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

Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

btw what I meant by this was ACK a5e39d3

Copy link
Contributor

@jonatack jonatack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Initial ACK a5e39d3

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.

diff --git a/src/rpc/fees.cpp b/src/rpc/fees.cpp
index 62396d4c589..d8d82921210 100644
--- a/src/rpc/fees.cpp
+++ b/src/rpc/fees.cpp
@@ -47,6 +47,7 @@ static RPCHelpMan estimatesmartfee()
             RPCResult::Type::OBJ, "", "",
             {
                 {RPCResult::Type::NUM, "feerate", /*optional=*/true, "estimate fee rate in " + CURRENCY_UNIT + "/kvB (only present if no errors were encountered)"},
+                {RPCResult::Type::STR, "fee_reason", /*optional=*/true, "fee reason returned by estimator (only present if no errors were encountered)"},
                 {RPCResult::Type::ARR, "errors", /*optional=*/true, "Errors encountered during processing (if there are any)",
                     {
                         {RPCResult::Type::STR, "", "error"},
@@ -91,6 +92,7 @@ static RPCHelpMan estimatesmartfee()
                 errors.push_back("Insufficient data or no feerate found");
                 result.pushKV("errors", errors);
             }
+            result.pushKV("fee_reason", StringForFeeReason(feeCalc.reason));
             result.pushKV("blocks", feeCalc.returnedTarget);
             return result;
         },
diff --git a/test/functional/feature_fee_estimation.py b/test/functional/feature_fee_estimation.py
index 4f56d585d3f..47b86704740 100755
--- a/test/functional/feature_fee_estimation.py
+++ b/test/functional/feature_fee_estimation.py
@@ -95,6 +95,7 @@ def check_smart_estimates(node, fees_seen):
     mempoolMinFee = node.getmempoolinfo()["mempoolminfee"]
     minRelaytxFee = node.getmempoolinfo()["minrelaytxfee"]
     for i, e in enumerate(all_smart_estimates):  # estimate is for i+1
+        print(e)
         feerate = float(e["feerate"])
         assert_greater_than(feerate, 0)
         assert_greater_than_or_equal(feerate, float(mempoolMinFee))

@@ -283,7 +289,14 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
// we can test for success
// (Only count the confirmed data points, so that each confirmation count
// will be looking at the same amount of data and same bucket breaks)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It looks like this comment could be updated to be more clear as an introduction to the partialNum conditional that is replacing the previous totalNum one.

@DrahtBot DrahtBot requested review from meshcollider and removed request for meshcollider October 12, 2023 00:12
@ismaelsadeeq
Copy link
Member

Code review ACK a5e39d3
To test this PR I have created another rpc estimatesmartfeecons that uses consistent bucket ranges, that is a5e39d3 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

@DrahtBot DrahtBot requested review from meshcollider and removed request for ismaelsadeeq and meshcollider October 12, 2023 16:38
@fanquake fanquake added this to the 27.0 milestone Oct 13, 2023
@glozow glozow merged commit 2e9454a into bitcoin:master Nov 2, 2023
16 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

EstimateMedianVal returns higher fee for higher confTarget
10 participants