Better fee estimates

morcos commented at 5:18 pm on April 12, 2017: member

This is a substantial improvement of fee estimation code built off #9942. Although in many cases the estimates will not appear to differ by much from previous estimates, they will handle some situations much better.

A longer writeup of the original algorithm and the changes in this PR can be found here: https://gist.github.com/morcos/d3637f015bc4e607e1fd10d8351e9f41

A summary of major changes:

Estimates can now be given for up to a 1008 block target.
Estimates are tracked on 3 different time horizons which allows for both the longer targets and lets the estimates adjust more quickly to changes in conditions.
estimatefee is deprecated in favor of using only estimatesmartfee (already used by the GUI)
estimateSmartFee now requires a 60% success rate at target/2, an 85% rate at target and a 95% rate at 2*target.
estimates are by default conservative which requires the 95% rate for 2*target to be met at longer time horizons as well, but by choosing non-conservative estimates, the estimates are drastically reduced during periods of less transaction activity (such as the weekend).
estimates are smarter about making sure enough data has been gathered in order to return a valid estimate (at least twice the number of blocks as the requested target much have been recorded)
Fee rate buckets are half as big leading to a bit more precision.
estimaterawfee is added so that customized logic can be implemented to analyze the raw data and calculate estimates.
Transactions which leave the mempool due to eviction or other non-confirmed reasons now count as failures. These are also saved at shutdown.

A summary of open issues:

Estimates are not backwards compatible. Currently when updating to this patch, any old fee estimates will be discarded and your node will have to be running for a while to provide new estimates. It is a possibility to add logic to return the old estimates for targets 2-25 until the new estimates have gathered enough data.
estimatefee is probably a roughly similar calculation to what it used to be, but I’ve made no effort to make sure the quality of the estimates it gives have not degraded, so infrastructure which doesn’t support estimatesmartfee should update.
The GUI needs to be updated to access the new range of estimates. I would suggest providing options for targets of: 2,4,6,12,24,48,144,504,1008

fanquake added the label TX fees and policy on Apr 12, 2017

jonasschnelli commented at 11:58 am on April 13, 2017: contributor

Great! Concept ACK.

The GUI needs to be updated to access the new range of estimates. I would suggest providing options for targets of: 2,4,6,12,24,48,144,504,1008

I’ll have a look at this soon.

jonasschnelli commented at 5:03 pm on April 19, 2017: contributor

ping @crwatkins (he presented some fee estimation overview at the wallet standards group meeting in Berlin this month).

in src/rpc/mining.cpp:883 in 7306590db9 outdated

876+        throw std::runtime_error(
877+            "estimaterawfee nblocks\n"
878+            "\nWARNING: This interface is unstable and may disappear or change!\n"
879+            "\nWARNING: This is an advanced API call that is tightly coupled to the specific\n"
880+            "         implementation of fee estimation. The parameters it can be called with\n"
881+            "         and the results it returns will change if the internal implementaion changes.\n"

jlopp commented at 7:22 pm on April 19, 2017:

Nit: implementation

jlopp commented at 7:23 pm on April 19, 2017: contributor

I’m not sure if this is a problem specific to your code, though requiring a leading 0 seems like a bug:

0bitcoin-cli estimaterawfee 10 .85 0
1error: Error parsing JSON:.85

sipa commented at 7:49 pm on April 19, 2017: member

@jlopp .85 is not valid JSON.

Change file format for fee estimates.

Move buckets and bucketMap to be stored as part of overall serialization of estimator.
Add some placeholder data so file format is only changed once.
Maintain 3 different TxConfirmStats with potential for different decays and scales.

c0a273f4c8

in src/rpc/mining.cpp:919 in 7306590db9 outdated

912+    RPCTypeCheck(request.params, boost::assign::list_of(UniValue::VNUM)(UniValue::VNUM)(UniValue::VNUM), true);
913+    RPCTypeCheckArgument(request.params[0], UniValue::VNUM);
914+    int nBlocks = request.params[0].get_int();
915+    double threshold = 0.95;
916+    if (!request.params[1].isNull())
917+        threshold = request.params[1].get_real();

jlopp commented at 8:18 pm on April 19, 2017:

Would prefer more explicit range bounding on the threshold with an “Invalid threshold” error response; it currently allows numbers < 0 and > 1 and just returns a -1 feerate.

morcos commented at 0:42 am on April 20, 2017:

The reason I didn’t bother with that is I felt estimaterawfee should be a very low level feature that doesn’t need all the user friendly bells and whistles.. But it could certainly be cleaned up to add that either in this PR or a follow on..

morcos force-pushed on Apr 20, 2017

morcos commented at 8:10 pm on April 20, 2017: member

clean rebase after #9942 was merged

laanwj added this to the milestone 0.15.0 on Apr 20, 2017

crwatkins commented at 11:13 pm on April 24, 2017: none

Thanks @jonasschnelli. In Berlin, I noted that at least 50% of the wallets listed on bitcoin.org use Core as a fee estimation source directly or through other servers based on Core and any statistical or algorithmic biases might compound over time because of the large number of clients using the single source. I presented some anecdotal, non-scientific observations about fees and some reasons that they might be artificially high. Some of my concerns about the current esitmatefee were

Slow to respond (2.5 day half life)
Too high confidence (95%)
No long term estimates (only 25 blocks)

I believe that the changes in this PR mitigate some of those concerns, and thus I am in favor of these changes. Nice work!

I’m still a little concerned about so many wallets “competing” using the same identical algorithm. @morcos do you envision some devs (wallets) would use estimaterawfee to tweak the algorithm for their users?

jlopp commented at 0:33 am on April 25, 2017: contributor

@crwatkins I can only speak for BitGo, but we run custom compiled versions of Core with our own half life and confidence values. We then use the output as a baseline for a more complex fee algorithm that we adjust upward and downward based upon other data sources. I’m already working on transitioning us to using the estimaterawfee functionality.

morcos commented at 5:05 pm on April 25, 2017: member

@crwatkins Yes that was the basic idea of including estimaterawfee (that and it’s useful for debugging). The exact strategy you use for determining what fee you want to put on a transaction depends on so many factors that its hard to have a one size fits all solution, but thats exactly what Bitcoin Core has to try to ship. So rather than attempt to defend why the algorithm I picked is the one algorithm to rule them all, I thought it would also make sense to expose a way to examine all the collected data and let people build their own algorithms if they’d like to.

crwatkins commented at 5:08 pm on April 25, 2017: none

@morcos Exclellent. Thanks!

Leviathn commented at 6:05 pm on April 25, 2017: none

Reviewing

in src/policy/fees.cpp:237 in d2c4bc787b outdated

213@@ -214,9 +214,14 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
214 
215     bool foundAnswer = false;
216     unsigned int bins = unconfTxs.size();
217+    bool newBucketRange = true;
218 
219     // Start counting from highest(default) or lowest feerate transactions
220     for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) {
221+        if (newBucketRange) {

TheBlueMatt commented at 6:51 pm on April 25, 2017:

Can you update the commit message from “Track start of new bucket range more carefully” to something more descriptive.

in src/rpc/mining.cpp:906 in 57e71c819d outdated

902+            "  \"totalconfirmed\" : x.x, (numeric) number of txs over history horizon in the feerate range total\n"
903+            "  \"inmempool\" : x.x,      (numeric) current number of txs in mempool in the feerate range unconfirmed for at least target blocks\n"
904+            "  \"leftmempool\" : x.x,    (numeric) number of txs over history horizon in the feerate range that left mempool unconfirmed after target\n"
905+            "}\n"
906+            "\n"
907+            "A negative value is returned if no answer can be given.\n"

TheBlueMatt commented at 7:37 pm on April 25, 2017:

nit: “A negative feerate is returned” (other values are zero, so might as well just specify feerate here).

in src/policy/fees.cpp:318 in 57e71c819d outdated

317-             confTarget, requireGreater ? ">" : "<", successBreakPoint,
318-             requireGreater ? ">" : "<", median, buckets[minBucket], buckets[maxBucket],
319-             100 * nConf / (totalNum + extraNum), nConf, totalNum, extraNum);
320+    // If we were passing until we reached last few buckets with insufficient data, then report those as failed
321+    if (passing && !newBucketRange) {
322+        unsigned int failMinBucket = curNearBucket < curFarBucket ? curNearBucket : curFarBucket;

TheBlueMatt commented at 10:58 pm on April 25, 2017:

nit: std::min/max here like you did above?

in src/policy/fees.cpp:43 in 57e71c819d outdated

45-    std::vector<std::vector<double> > confAvg; // confAvg[Y][X]
46-    // and calculate the totals for the current block to update the moving averages
47-    std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X]
48+    std::vector<std::vector<double>> confAvg; // confAvg[Y][X]
49+
50+    std::vector<std::vector<double>> failAvg; // future use

TheBlueMatt commented at 11:10 pm on April 25, 2017:

Should probably update this comment in the commit that puts failAvg to use.

in src/policy/fees.cpp:638 in c0a273f4c8 outdated

637+                throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
638+
639+            std::map<double, unsigned int> tempMap;
640+
641+            std::unique_ptr<TxConfirmStats> tempFeeStats(new TxConfirmStats(tempBuckets, tempMap, MAX_BLOCK_CONFIRMS, tempDecay));
642+            tempFeeStats->Read(filein, nVersionThatWrote, tempNum);

TheBlueMatt commented at 6:03 pm on April 27, 2017:

As discussed it’d be nice to use this chunk and tempFeeStats to just generate one fee estimate, cache that, and then start fresh (as you do) but use the cached fee estimate while our new buckets fill.

morcos commented at 3:48 pm on May 9, 2017:

leaving for a later improvement

in src/policy/fees.cpp:472 in b2222ced4f outdated

468@@ -465,6 +469,8 @@ void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, boo
469 
470     mapMemPoolTxs[hash].blockHeight = txHeight;
471     mapMemPoolTxs[hash].bucketIndex = feeStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
472+    shortStats->NewTx(txHeight, (double)feeRate.GetFeePerK());

TheBlueMatt commented at 6:08 pm on April 27, 2017:

nit: might be nice to assert that the bucketIndex is the same across all three calls here?

in src/policy/fees.h:190 in 57e71c819d outdated

191 
192     /** Read estimation data from a file */
193     bool Read(CAutoFile& filein);
194 
195+    /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
196+    void ClearInMempool(CTxMemPool& pool);

TheBlueMatt commented at 6:52 pm on April 27, 2017:

nit: maybe a better name for this would be FlushFailedPreShutdown()?

laanwj added this to the "Blockers" column in a project

in src/txmempool.cpp:451 in 57e71c819d outdated

447@@ -448,7 +448,7 @@ void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
448     mapLinks.erase(it);
449     mapTx.erase(it);
450     nTransactionsUpdated++;
451-    if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash);}
452+    if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}

TheBlueMatt commented at 8:32 pm on April 27, 2017:

nit: it seems kinda strange that the “inBlock” flag is always set to false, even though it is sometimes called when the transaction was, indeed, in a block. Not a bug because it is a dummy call in fees.cpp, but maybe the API should stay the same and have the flag filled in inside of fees.cpp.

morcos commented at 4:04 pm on May 9, 2017:

This will eventually be cleaned up when fee estimation listens to CValidationInterface

in src/policy/fees.cpp:779 in 57e71c819d outdated

787+        unsigned int maxUsableEstimate = MaxUsableEstimate();
788+        if (maxUsableEstimate <= 1)
789+            return CFeeRate(0);
790+
791+        if ((unsigned int)confTarget > maxUsableEstimate) {
792+            confTarget = maxUsableEstimate;

TheBlueMatt commented at 11:25 pm on April 27, 2017:

This seems strange to me. Most of our APIs will already gracefully fail if you pass in too high a conf target, I’d rather we do the same here (same in GUI).

morcos commented at 5:10 pm on May 4, 2017:

The design of estimateSmartFee is to be used by the wallet to intelligently as possible automatically put a fee on a transaction being sent. In the GUI, the slider clearly indicates what target the fee is being returned for. For the RPC call estimatesmartfee, this is also clearly returned. The difficulty comes with automatic estimation that happens from a sendtoaddress or sendmany RPC call. If in the future we add a way to select a transaction confirm target with the desired RPC call, perhaps it would make sense to fail, but for now it seems to me that its more important for the transaction to go out, even if its paying a fee for a much faster target.

in src/policy/fees.cpp:835 in 57e71c819d outdated

819         LOCK(cs_feeEstimator);
820-        fileout << 139900; // version required to read: 0.13.99 or later
821+        fileout << 149900; // version required to read: 0.14.99 or later
822         fileout << CLIENT_VERSION; // version that wrote the file
823         fileout << nBestSeenHeight;
824+        if (BlockSpan() > HistoricalBlockSpan()/2) {

TheBlueMatt commented at 11:32 pm on April 27, 2017:

This seems like a sharp edge - you can restart a node and end up getting a fee estimate much higher than 30 seconds ago before you shut down. Maybe change the /2 to historicalBest more recent than OLDEST_ESTIMATE_HISTORY*3/4 or so? Would still have the issue but at least its less likely to be hit for those who regularly run a node just during the day or so?

morcos commented at 5:11 pm on May 4, 2017:

After discussion, I agree that this logic could be more intelligent, but I think that can be left for a later improvement.

TheBlueMatt commented at 1:22 am on April 28, 2017: member

Looks good. With the exception of the fallback during upgrade and the one strange sharp edge LGTM. Needs testing because the code being correct isnt really enough, but no doubt better than today’s estimates.

in src/policy/fees.cpp:58 in c0a273f4c8 outdated

54@@ -53,13 +55,17 @@ class TxConfirmStats
55 
56     double decay;
57 
58+    unsigned int scale;

instagibbs commented at 12:54 pm on May 1, 2017:

Add description?

in src/policy/fees.cpp:77 in c0a273f4c8 outdated

73@@ -68,7 +74,8 @@ class TxConfirmStats
74      * @param maxConfirms max number of confirms to track
75      * @param decay how much to decay the historical moving average per block
76      */
77-    TxConfirmStats(const std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay);
78+    TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,

instagibbs commented at 12:55 pm on May 1, 2017:

add description above?

in src/policy/fees.h:173 in 57e71c819d outdated

173-     *  confTarget blocks. If no answer can be given at confTarget, return an
174-     *  estimate at the lowest target where one can be given.
175+    /** Estimate feerate needed to get be included in a block within confTarget
176+     *  blocks. If no answer can be given at confTarget, return an estimate at
177+     *  the closest target where one can be given.  'conservative' estimates are
178+     *  valid over longer time horizons also.

instagibbs commented at 1:45 pm on May 1, 2017:

teeny nit: “also” unneeded

in src/policy/fees.cpp:782 in 57e71c819d outdated

790+
791+        if ((unsigned int)confTarget > maxUsableEstimate) {
792+            confTarget = maxUsableEstimate;
793+        }
794+
795+        assert(confTarget > 0); //estimateCombinedFee and estimateConservativeFee take unsigned ints

instagibbs commented at 1:54 pm on May 1, 2017:

I think this is impossible to hit, due to confTarget <= 0 check and maxUsableEstimate <= 1 check. (though this might make sense as belt and suspenders)

in src/rpc/mining.cpp:841 in 57e71c819d outdated

839             "for which the estimate is valid. Uses virtual transaction size as defined\n"
840             "in BIP 141 (witness data is discounted).\n"
841             "\nArguments:\n"
842-            "1. nblocks     (numeric)\n"
843+            "1. nblocks       (numeric)\n"
844+            "2. conservative  (bool, optional, default=true) Whether to return a more conservative estimate calculated from a longer history\n"

instagibbs commented at 2:07 pm on May 1, 2017:

It’s not clear to me as the API reader what “conservative” means here, depending on if I’m worrying about over-paying or waiting too long, or being conservative in the amount of data I’m using to estimate.

suggested: “Whether to return a possibly higher feerate estimate calculated from a longer history”

in src/rpc/mining.cpp:892 in 57e71c819d outdated

885+            "\nArguments:\n"
886+            "1. nblocks     (numeric)\n"
887+            "2. threshold   (numeric, optional) The proportion of transactions in a given feerate range that must have been\n"
888+            "               confirmed within nblocks in order to consider those feerates as high enough and proceed to check\n"
889+            "               lower buckets.  Default: 0.95\n"
890+            "3. horizon     (numeric, optional) How long a history of estimates to consider. 0=short, 1=medium, 2=long.\n"

instagibbs commented at 2:32 pm on May 1, 2017:

perhaps mention how long each history is

in src/rpc/mining.cpp:897 in 57e71c819d outdated

893+            "{\n"
894+            "  \"feerate\" : x.x,        (numeric) estimate fee-per-kilobyte (in BTC)\n"
895+            "  \"decay\" : x.x,          (numeric) exponential decay for historical moving average of confirmation data\n"
896+            "  \"scale\" : x,            (numeric) The resolution of confirmation targets at this time horizon\n"
897+            "  \"pass.\"                 information about the last range of feerates to succeed in meeting the threshold\n"
898+            "  \"fail.\"                 information about the first range of feerates to fail to meet the threshold\n"

instagibbs commented at 2:36 pm on May 1, 2017:

nit: s/first/highest/

in src/rpc/mining.cpp:896 in 57e71c819d outdated

892+            "\nResult:\n"
893+            "{\n"
894+            "  \"feerate\" : x.x,        (numeric) estimate fee-per-kilobyte (in BTC)\n"
895+            "  \"decay\" : x.x,          (numeric) exponential decay for historical moving average of confirmation data\n"
896+            "  \"scale\" : x,            (numeric) The resolution of confirmation targets at this time horizon\n"
897+            "  \"pass.\"                 information about the last range of feerates to succeed in meeting the threshold\n"

instagibbs commented at 2:36 pm on May 1, 2017:

nit: s/last/lowest/

in src/rpc/mining.cpp:901 in 57e71c819d outdated

897+            "  \"pass.\"                 information about the last range of feerates to succeed in meeting the threshold\n"
898+            "  \"fail.\"                 information about the first range of feerates to fail to meet the threshold\n"
899+            "  \"startrange\" : x.x,     (numeric) start of feerate range\n"
900+            "  \"endrange\" : x.x,       (numeric) end of feerate range\n"
901+            "  \"withintarget\" : x.x,   (numeric) number of txs over history horizon in the feerate range that were confirmed within target\n"
902+            "  \"totalconfirmed\" : x.x, (numeric) number of txs over history horizon in the feerate range total\n"

instagibbs commented at 2:40 pm on May 1, 2017:

s/total/that were confirmed at any point/

in test/functional/smartfees.py:120 in 57e71c819d outdated

115@@ -116,8 +116,8 @@ def check_estimates(node, fees_seen, max_invalid, print_estimates = True):
116     for i,e in enumerate(all_estimates): # estimate is for i+1
117         if e >= 0:
118             valid_estimate = True
119-            # estimatesmartfee should return the same result
120-            assert_equal(node.estimatesmartfee(i+1)["feerate"], e)
121+            if i >= 13:  # for n>=14 estimatesmartfee(n/2) should be at least as high as estimatefee(n)
122+                assert(node.estimatesmartfee((i+1)//2)["feerate"] > float(e) - delta)

instagibbs commented at 2:42 pm on May 1, 2017:

could also do a quick check that the transitive property is true for conservative estimates

in src/policy/fees.h:132 in 57e71c819d outdated

127+    /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
128+    static constexpr double DOUBLE_SUCCESS_PCT = .95;
129+
130+    /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
131+    static constexpr double SUFFICIENT_FEETXS = 0.1;
132+    /** Require an avg of 0.5 tx when using short decay since there are less blocks considered*/

instagibbs commented at 2:53 pm on May 1, 2017:

grammar nit: s/less/fewer/

instagibbs approved

instagibbs commented at 2:57 pm on May 1, 2017: member

utACK 57e71c819d7653555b048288eee717d53d493924 provided conservative is defined to the user

If I find the time I’ll do some real-world testing once the buckets fill up.

in src/rpc/mining.cpp:876 in 57e71c819d outdated

872 
873+UniValue estimaterawfee(const JSONRPCRequest& request)
874+{
875+    if (request.fHelp || request.params.size() < 1|| request.params.size() > 3)
876+        throw std::runtime_error(
877+            "estimaterawfee nblocks\n"

instagibbs commented at 3:06 pm on May 1, 2017:

missing threshold

in src/policy/fees.cpp:799 in 57e71c819d outdated

802+        }
803+        if (doubleEst > median) {
804+            median = doubleEst;
805+        }
806+
807+        if (conservative) {

TheBlueMatt commented at 3:47 pm on May 1, 2017:

I believe we may want to add a check that the previous code actually got a result here. And, generally, that all of the four estimate*Fee calls here actually succeed. It seems super strange to accept only one result as fine if the rest fail (eg on startup you may get a response from short horizon on SUFFICIENT_TXS_SHORT, but not on medium/long, also @sdaftuar saw a case this morning where he had an offline node for a while which succeeded in getting a result for conservative but not for non-conservative for a 3 conftarget, I believe because estimateConservativeFee gave a result from the medium/long horizons when the short horizon could not).

morcos commented at 6:34 pm on May 3, 2017:

After offline discussion, it appears the bigger issue is what to do when the short time horizon estimates have decayed to not being able to give you an answer. It seems like what happens in conservative mode is probably the right thing where you take advantage of the fact that the longer time horizon estimates have not decayed yet. We probably want the ability to utilize this as a fall back in non-conservative mode as well. This can happen either from shutting down a node for a couple of days which means the short time horizon will decay too much, or even just from losing network activity from something like a laptop over the weekend. As it is, I think its probably still a strict improvement to existing estimates, but could use further refinement.

in src/policy/fees.cpp:723 in 57e71c819d outdated

722+            }
723+            else {
724+                if (!conservative) {
725+                    // When we aren't using conservative estimates, if a lower confTarget from a more recent horizon returns a lower answer use it.
726+                    double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, true, nBestSeenHeight);
727+                    if (estimate == -1 ||  medMax < estimate) {

morcos commented at 6:39 pm on May 3, 2017:

in all 3 of these replacement evaluations (also line 709 and line 722), we probably don’t want to do the replacement if the new estimate is -1, should be rare.

morcos force-pushed on May 9, 2017

morcos commented at 5:46 pm on May 9, 2017: member

Addressed the comments in fixup commmits e95eca7 (smarterfee.ver5) and then squashed –> 9a34419 (smarterfee.ver5.squash)

in src/policy/fees.cpp:590 in c0a273f4c8 outdated

586@@ -580,10 +587,15 @@ bool CBlockPolicyEstimator::Write(CAutoFile& fileout) const
587 {
588     try {
589         LOCK(cs_feeEstimator);
590-        fileout << 139900; // version required to read: 0.13.99 or later
591+        fileout << 149900; // version required to read: 0.14.99 or later

sipa commented at 5:48 pm on May 9, 2017:

Any reason to keep this number tied to client versions instead of just an independent “fee estimates file version number”?

morcos commented at 7:18 pm on May 9, 2017:

no reason…, but this also seems simple enough?

in src/policy/fees.h:210 in 9a34419f98 outdated

206@@ -141,19 +207,38 @@ class CBlockPolicyEstimator
207 
208     /** Classes to track historical data on transaction confirmations */
209     TxConfirmStats* feeStats;
210+    TxConfirmStats* shortStats;

sipa commented at 5:49 pm on May 9, 2017:

Convert these to std::unique_ptrs?

morcos commented at 7:21 pm on May 9, 2017:

This was the change made in #9942, and I couldn’t get unique_ptrs to work while also moving the code to the cpp file. I now also have other ideas how to clean up the wonky design of TxConfirmStats inside CBlockPolicyEstimator, but I don’t want to do it now and churn this PR.

in src/policy/fees.h:244 in 280e244eb3 outdated

170@@ -159,6 +171,10 @@ class CBlockPolicyEstimator
171 
172 class FeeFilterRounder
173 {
174+private:
175+    static constexpr double MAX_FILTER_FEERATE = 1e7;
176+    static constexpr double FEE_FILTER_SPACING = 1.1;

sipa commented at 6:05 pm on May 9, 2017:

Can you add a comment to explain the relation with the CBlockPolicyEstimator::FEE_SPACE constant?

morcos commented at 7:19 pm on May 9, 2017:

yeah, there is no relation. when I made the filter spacing, I just copied the other one arbitrarily, but then I decided if I was changing the estimate spacing, there was no reason to also make a change to the filter spacing. I can add a comment.

in src/rpc/mining.cpp:883 in 9a34419f98 outdated

879+        throw std::runtime_error(
880+            "estimaterawfee nblocks (threshold horizon)\n"
881+            "\nWARNING: This interface is unstable and may disappear or change!\n"
882+            "\nWARNING: This is an advanced API call that is tightly coupled to the specific\n"
883+            "         implementation of fee estimation. The parameters it can be called with\n"
884+            "         and the results it returns will change if the internal implementaion changes.\n"

sipa commented at 6:14 pm on May 9, 2017:

@jlopp’s comment hasn’t been addressed yet: “nit: Implementation”.

morcos commented at 7:22 pm on May 9, 2017:

oops

in src/rpc/mining.cpp:915 in 116ab2abae outdated

910+    if (!request.params[2].isNull()) {
911+        int horizonInt = request.params[2].get_int();
912+        if (horizonInt < 0 || horizonInt > 2) {
913+            throw JSONRPCError(RPC_TYPE_ERROR, "Invalid horizon for fee estimates");
914+        }
915+        else {

sipa commented at 6:16 pm on May 9, 2017:

Style nit: else on the same line as }

morcos commented at 7:22 pm on May 9, 2017:

kk

in src/rpc/mining.cpp:892 in 116ab2abae outdated

878+            "\nArguments:\n"
879+            "1. nblocks     (numeric)\n"
880+            "2. threshold   (numeric, optional) The proportion of transactions in a given feerate range that must have been\n"
881+            "               confirmed within nblocks in order to consider those feerates as high enough and proceed to check\n"
882+            "               lower buckets.  Default: 0.95\n"
883+            "3. horizon     (numeric, optional) How long a history of estimates to consider. 0=short, 1=medium, 2=long.\n"

sipa commented at 6:18 pm on May 9, 2017:

To make the RPC interface less dependent on the specific implementation, perhaps don’t make horizon a parameter, and just return information for all applicable horizons for the given value of nblocks?

morcos commented at 7:22 pm on May 9, 2017:

slightly prefer existing, but I could change it if prevailing opinion is otherwise.. estimaterawfee is meant to be implementation dependent

sipa commented at 10:41 pm on May 16, 2017:

The reason for asking is that while the output of this RPC may be implementation dependent, it would be nice if (to the extent possible), its arguments aren’t. The specific buckets used seem much more likely to change in other revisions.

Just a nit.

in src/policy/fees.cpp:703 in d6918d281a outdated

657@@ -658,31 +658,97 @@ CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThr
658     return CFeeRate(median);
659 }
660 
661-CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool) const
662+
663+double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool conservative) const
664+{
665+    double estimate = -1;

sipa commented at 6:25 pm on May 9, 2017:

Can you write this function as a loop over the 3 horizons, instead of a cascaded if/then/else?

morcos commented at 7:17 pm on May 9, 2017:

I can take a pass at rewriting the logic to be a bit clearer, but I’m not sure a loop is the right thing. There are basically 6 different combinations of estimates you might want to check depending on what range your target is in and whether or not you want to check shorter horizons. But the logic might be cleaner if those are just spelled out.

in src/policy/fees.h:195 in 1313cc7b2b outdated

172@@ -173,6 +173,10 @@ class CBlockPolicyEstimator
173 private:
174     CFeeRate minTrackedFee;    //!< Passed to constructor to avoid dependency on main
175     unsigned int nBestSeenHeight;
176+    unsigned int firstRecordedHeight;
177+    unsigned int historicalFirst;

sipa commented at 6:27 pm on May 9, 2017:

Nit: unused until 2 commits later.

morcos commented at 7:23 pm on May 9, 2017:

I wanted to get the file format change over and done with…

in src/policy/fees.cpp:694 in 13cb482888 outdated

683+}
684+
685+unsigned int CBlockPolicyEstimator::MaxUsableEstimate() const
686+{
687+    // Block spans are divided by 2 to make sure there are enough potential failing data points for the estimate
688+    return std::min(longStats->GetMaxConfirms(), std::max(BlockSpan(), HistoricalBlockSpan()) / 2);

sipa commented at 6:38 pm on May 9, 2017:

Nit: If you’d return which of the two BlockSpans was chosen in a pair or a bool, you wouldn’t need to repeat the decision logic in the debug print statement of processBlock.

morcos commented at 7:17 pm on May 9, 2017:

ok

morcos commented at 2:32 pm on May 10, 2017:

after actually doing this, it seemed uglier, so leaving it as is

sipa commented at 6:52 pm on May 9, 2017: member

Code review ACK, with some nits. I haven’t reviewed the changes to the estimation algorithm itself.

Change parameters for fee estimation and estimates on all 3 time horizons.

Make feerate buckets smaller (5% instead of 10%) and make the 3 different horizons have half lifes of 3 hours, 1 day and 1 week respectively.

e5007bae35

Refactor to update moving average on fly d3e30bca1b

Make EstimateMedianVal smarter about small failures.

Instead of stopping if it encounters a "sufficient" number of transactions which don't meet the threshold for being confirmed within the target, it keeps looking to add more transactions to see if there is a temporary blip in the data.  This allows a smaller number of required data points.

1ba43cc0ec

minor refactor: explicitly track start of new bucket range and don't update curNearBucket on final loop. 2681153af3

Expose estimaterawfee

Track information the ranges of fee rates that were used to calculate the fee estimates (the last range of fee rates in which the data points met the threshold and the first to fail) and provide an RPC call to return this information.

4186d3fdfd

Track failures in fee estimation.

Start tracking transactions which fail to confirm within the target and are then evicted or otherwise leave mempool.

Fix slight error in unit test.

c7447ec303

Rewrite estimateSmartFee

Change the logic of estimateSmartFee to check a 60% threshold at half the target, a 85% threshold at the target and a 95% threshold at double the target. Always check the shortest time horizon possible and ensure that estimates are monotonically decreasing.  Add a conservative mode, which makes sure that the 95% threshold is also met at longer time horizons as well.

3810e976d6

Track first recorded height

Track the first time we seen txs in a block that we have been tracking in our mempool. Used to evaluate validity of fee estimates for different targets.

10f7cbd247

Clean up fee estimate debug printing aa19b8ea44

Historical block span

Store in fee estimate file the block span for which we were tracking estimates, so we know what targets we can successfully evaluate with the data in the file. When restarting use either this historical block span to set valid range of targets until our current span of tracking estimates is just as long.

5f1f0c6490

Introduce a scale factor

For the per confirmation number tracking of data, introduce a scale factor so that in the longer horizones confirmations are bucketed together at a resolution of the scale.  (instead of 1008 individual data points for each fee bucket, have 42 data points each covering 24 different confirmation values.. (1-24), (25-48), etc.. )

3ee76d6de5

minor cleanup: remove unnecessary variable ef589f8d40

Comments and improved documentation 2d2e17052c

morcos force-pushed on May 10, 2017

morcos commented at 3:54 pm on May 10, 2017: member

OK. I think I addressed remaining comments. I also tried to clean up the logic of estimateCombinedFee to be a bit clearer (although still not a loop) I also changed the logic to be smarter about returning an answer if one can be found on any horizon, instead of returning -1.
Fixup commits are squashed.

abe88e4 (smarterfee.ver7) –> 2d2e170 (smarterfee.ver7.squash)

instagibbs commented at 4:46 pm on May 12, 2017: member

re-utACK https://github.com/bitcoin/bitcoin/pull/10199/commits/2d2e17052c389948c511d2b5d41c4cc243cdc145

in src/rpc/mining.cpp:925 in 4186d3fdfd outdated

920+    EstimationResult buckets;
921+    feeRate = ::feeEstimator.estimateRawFee(nBlocks, threshold, horizon, &buckets);
922+
923+    result.push_back(Pair("feerate", feeRate == CFeeRate(0) ? -1.0 : ValueFromAmount(feeRate.GetFeePerK())));
924+    result.push_back(Pair("decay", buckets.decay));
925+    result.push_back(Pair("pass.startrange", round(buckets.pass.start)));

sipa commented at 10:40 pm on May 16, 2017:

I haven’t seen a ‘.’ inside RPC output field names. Why not bundle these into a pass and fail Object? That’s probably easier to parse for external libraries too.

morcos commented at 6:01 pm on May 17, 2017:

ah, that makes sense. i will make this change

sipa commented at 1:43 am on May 17, 2017: member

utACK

gmaxwell approved

gmaxwell commented at 3:37 pm on May 17, 2017: contributor

ACK.

Make more json-like output from estimaterawfee 38bc1ec4a4

morcos force-pushed on May 17, 2017

morcos commented at 7:48 pm on May 17, 2017: member

Added an extra commit to improve JSON output as per @sipa. Was kind of annoying to squash, so will leave it if that’s ok? @laanwj I think this is reviewed enough that we’d be better off merging and getting some more experimentation with the estimates.. It takes 2 full weeks for the longest estimates to even be exposed.

The biggest open questions are whether I should add an ability to use old estimates during transition and whether we are going to build in GUI support.

The tests could also use some improvement but I don’t think they’re notably worse than they were.

sipa commented at 7:58 pm on May 17, 2017: member

utACK 38bc1ec4a473b5bd9b7bbce7b20a11e8edfe4b4c

instagibbs commented at 8:01 pm on May 17, 2017: member

utACK https://github.com/bitcoin/bitcoin/pull/10199/commits/38bc1ec4a473b5bd9b7bbce7b20a11e8edfe4b4c

sipa merged this on May 17, 2017

sipa closed this on May 17, 2017

sipa referenced this in commit 318ea50a1c on May 17, 2017

RHavar commented at 0:18 am on May 18, 2017: contributor

I tried reading the description from help, and I don’t really understand this:

[the rpc command also returns] the number of blocks for which the estimate is valid.

but from the actual return:

“blocks” : n (numeric) block number where estimate was found

Without reading the code, it’s not clear what blocks means. Is it the block height when you called estimatestartfee or is it how long it’s valid for?

instagibbs commented at 2:14 am on May 18, 2017: member

@RHavar without actually looking at the code, I believe this refers to the “cheapest bucket” block which that feerate was found.

RHavar commented at 2:39 am on May 18, 2017: contributor

@instagibbs Yeah, you seem right. But I don’t think that was inferable from the help information :P

What’s the motivation for estimatefee returning a different value than estimatesmartfee ?

0$ bitcoin-cli estimatefee 6
10.00254275

0$ bitcoin-cli estimatesmartfee 6
1{
2  "feerate": 0.00208824,
3  "blocks": 6
4}

?

Anyway, fantastic work. This is a huge improvement, something that has been long needed. Well done @morcos

RHavar commented at 2:55 am on May 18, 2017: contributor

I’ve updated https://estimatefee.com/ to now use estimatesmartfee $n so if you’re interested you can take a look there.

The bitcoin node has only been up a few hours, so it’ll probably take a while to collect enough information.

P.S. you kinda broke my domain name lol

laanwj removed this from the "Blockers" column in a project

morcos commented at 5:08 pm on May 18, 2017: member

@Rhavar you might be right that the description is not the clearest. blocks refers to the target for which you are getting an estimate, which is an expected number of blocks within which you will be confirmed. Occasionally you ask for an estimate at one target but it returns you an estimate for a different target (b/c it is unable to give you an estimate for the target you asked for)

RHavar commented at 6:42 pm on May 18, 2017: contributor

@morcos In that case I’d suggest renaming it from “blocks” to “target” and changing the description to what you wrote above :P

karelbilek commented at 8:29 pm on September 2, 2017: contributor

Not sure where to put it, but just FYI

I made a simple tool that looks up smart fees once per 10 minutes and puts it here

https://estimatesmartfee.com/html.html

or

https://estimatesmartfee.com/json.json

If you want to use it for testing or something

jb55 commented at 6:37 am on October 26, 2017: member

also FYIs, I put together a small bash script that uses this for quickly grabbing fees from the command line: https://bitcoin.stackexchange.com/a/61348/1235

thanks!

PastaPastaPasta referenced this in commit 85c583c159 on Jun 10, 2019

PastaPastaPasta referenced this in commit e4eff32b86 on Jul 13, 2019

PastaPastaPasta referenced this in commit 29e0bfdb29 on Jul 17, 2019

PastaPastaPasta referenced this in commit 40a19a76a7 on Jul 23, 2019

PastaPastaPasta referenced this in commit b430366dd9 on Jul 24, 2019

barrystyle referenced this in commit a769b945f8 on Jan 22, 2020

DrahtBot locked this on Dec 16, 2021

Better fee estimates #10199