New fee estimation code

morcos commented at 7:32 pm on October 28, 2014: member

I reworked the fee and priority estimation code to gather statistics by binning transactions of various fee rates and tracking how many blocks they took to get confirmed. See post to mailing list.

laanwj added the label TX fees on Oct 29, 2014

bmos commented at 5:37 pm on October 30, 2014: none

Ooh, that sounds like a pretty slick improvement!

laanwj commented at 12:36 pm on November 3, 2014: member

@gavinandresen can you have a look here?

gavinandresen commented at 7:41 pm on November 3, 2014: contributor

@laanwj : yes, I’ll review, but that might not happen until next week (I’m headed to Dublin tomorrow).

morcos commented at 8:27 pm on November 3, 2014: member

Thanks. I really like the new GUI in #5200. I think we should also change txconfirmtarget to default to 2 or higher for non QT usage. 1 is just dangerous given the fact that it’s often impossible to be reliably confirmed in 1 transaction. Separately, #4082 is a somewhat substantial problem though. Is anyone working on the fixes @gavinandresen and @gmaxwell suggested? I just want to be sure we tie all these changes together to work well.

laanwj commented at 9:08 am on November 4, 2014: member

@morcos best to ask @cozz there I think

gavinandresen commented at 3:50 pm on November 4, 2014: contributor

Code review mostly ACK, apart from a couple of nits.

I’ll try to get a node up and running, generating estimates over time, to see how this behaves compared to the existing estimation code.

morcos commented at 8:18 pm on November 5, 2014: member

OK, I moved the dependency checking logic to main.cpp. It was a pretty clean change I think, and is more efficient because it saves us looping through all the inputs again. If that code ever gets moved out of main, I think it makes sense for those two checks on inputs to stay together. However if you don’t like that, I can revert back to putting the logic inside CTxMemPoolEntry and I’ll just call the constructor with a reference to the mempool itself. In both cases it now checks to be sure inputs aren’t in the mempool as you suggest, as opposed to checking that they are in the chain as in my original version. I renamed the variable and also fixed the portability issue I think.

gavinandresen commented at 10:20 pm on November 11, 2014: contributor

Node running this code and generating graphs at: http://core2.bitcoincore.org/smartfee/

(current HEAD code is running at http://bitcoincore.org/smartfee/ )

rebroad commented at 4:01 am on November 14, 2014: contributor

@gavinandresen How come the fee for 3 confirmation txs has stayed constant over the entire period. That can’t be right, can it?

morcos commented at 12:01 pm on November 14, 2014: member

@rebroad The reason that happens is there aren’t enough data points for transactions with lower fee rates. As people start placing transactions with lower fees, there will be more data points in the lower fee rate ranges and the estimate will get lower. I believe it makes sense for all of the 3+ confirmation estimates to be the same, because basically any fee will be confirmed within 3 confirms right now, so its just a matter of how low an estimate can you accurately give.

rebroad commented at 0:11 am on December 11, 2014: contributor

This doesn’t seem to work well with #5200 currently. Even after leaving the node running for a while, the fee estimation doesn’t kick in for anything other than 2 confirms. So sliding the slider to 20 gives the same fee as sliding it to 2, and then sliding it to 1 makes it say it needs longer to calculate (which then never happens).

morcos commented at 1:36 am on December 11, 2014: member

I’m curious what fee its returning for you and how long it’s been running. You can see by Gavin’s charts linked above what the estimates are over time. But I do agree that if/when this is going to be merged, the GUI could be slightly modified to better handle the case where 1 doesn’t give an estimate. It’s not always a matter of not having enough data, but sometimes there really is no answer to the question, because there is no fee that is high enough that you’ll reliably (> 85%) get confirmed within 1 block. In any case, I was operating under the assumption that this wasn’t making it in for 0.10, so I was planning on waiting for that and then rebasing. I also have a couple small improvements to make.

morcos force-pushed on Dec 11, 2014

morcos commented at 10:08 pm on December 11, 2014: member

OK I rebased off 0.10 (so the first 3 commits should still be what you reviewed Gavin). But then the 4th commit is new. It’s addressing your comments above in a better way than I had previously done.

morcos force-pushed on Mar 13, 2015

morcos commented at 8:47 pm on March 13, 2015: member

@gavinandresen, I’ve rebased this and added a couple of improvements, most notably, doing some tracking of transactions that are in the mempool and haven’t been mined yet. So in particular the are code changes from what you reviewed before.

gavinandresen commented at 2:39 pm on March 17, 2015: contributor

My compiler is unhappy. Compiler:

0Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)

Unhappiness:

0./streams.h:406:9: error: call to 'Serialize' is ambiguous
1        ::Serialize(*this, obj, nType, nVersion);
2        ^~~~~~~~~~~
3policyestimator.cpp:175:13: note: in instantiation of function template specialization 'CAutoFile::operator<<<unsigned long>' requested here
4    fileout << confAvg.size();
5            ^

… and:

0./serialize.h:555:6: error: member reference base type 'unsigned long' is not a structure or union
1    a.Unserialize(is, (int)nType, nVersion);
2    ~^~~~~~~~~~~~
3./streams.h:416:11: note: in instantiation of function template specialization 'Unserialize<CAutoFile, unsigned long>' requested here
4        ::Unserialize(*this, obj, nType, nVersion);
5          ^
6policyestimator.cpp:197:12: note: in instantiation of function template specialization 'CAutoFile::operator>><unsigned long>' requested here
7    filein >> maxConfirms;
8           ^

gavinandresen commented at 2:46 pm on March 17, 2015: contributor

Since the format of fee_estimates.dat will change, CTxMemPool::WriteFeeEstimates should change:

0fileout << 99900; // version required to read: 0.9.99 or later
1 .... should be
2fileout << 109900; // version required to read: 0.10.99 or later

morcos commented at 2:58 pm on March 17, 2015: member

ah sorry, pushed too fast, i’d noticed that compilation problem, not sure why it was a problem, but i think i just pushed a fix… will wait for more comments before adding more fixes.

gavinandresen commented at 4:34 pm on March 19, 2015: contributor

Been running this at home for a couple of days, estimates look reasonable.

I’ve updated the bitcoind on core2.bitcoincore.org; as soon as it catches up with the chain it will start generating new fee/priority estimate charts again.

morcos commented at 8:52 pm on April 6, 2015: member

Any thoughts on whether this is something we’d like to merge? I’d like to get it in early enough in the 0.11 release cycle that it gets some usage. I realize its a lot of complicated code, but it really only affects fee and priority estimates. I think the increased accuracy of the estimates makes it worthwhile. Compare (core2.) and bitcoincore.org/smartfee/fee_graph.html.

gavinandresen commented at 10:13 pm on April 6, 2015: contributor

I’d like to see this in the 0.11 release.

jtimon commented at 10:29 pm on April 8, 2015: contributor

Could you rename src/policyestimator.o to src/policy/estimator.o ? I was planning on doing such a code movement and this seems like a perfect opportunity. A later step would be to take the policy estimator out of the txmempool object, but this movement already helps with that independently of what you’re doing inside the the estimator itself which I haven’t reviewed. This is what I had in mind after the movement: https://github.com/jtimon/bitcoin/commit/ba88aa141985bfba94a67289cf176e3a562971da

It will obviously have to change after this PR, but maybe you can get some ideas from there as well, and hopefully make the “rebase/rewrite” of that encapsulation easier. If you manage to incorporate the essence of that commit in your PR, I would love you for it, but that’s probably too much to ask at this point. In any case, I would already be happy with the file rename.

morcos commented at 1:59 am on April 9, 2015: member

I’d be happy to give it shot. I’ll ping you when I get around to it.

morcos force-pushed on Apr 20, 2015

morcos commented at 7:40 pm on April 20, 2015: member

Rebased, cleaned up and squashed original commits.

Added 3 new commits. This is ready for more review. @jtimon I made the move you asked for but held off for now on the other changes until I know what the right way to couple the mempool to the estimator is. There are now 3 interface points instead of the previous 1 that the old code had.

laanwj added this to the milestone 0.11.0 on Apr 20, 2015

jtimon commented at 9:51 am on April 22, 2015: contributor

I had more time to review this. I don’t understand what you mean by the 3 interface points but BlockPolicyEstimator is already decoupled from CTxMemPool with your current code. You made the mistake of coupling CTxMemPoolEntry with CTxMemPool in https://github.com/morcos/bitcoin/commit/ff34d782517f9cabed87772db96a7e7a76ac5db0 and although you fix it in https://github.com/morcos/bitcoin/commit/64bf2bbe4400d1c4da23f56ebb8dee595f5055fe that mistake should never reach the history. I’m not sure if you planned to squash that commit or leave it separate.

So to decouple BlockPolicyEstimator from txmempool.o you just need to also take AllowFreeThreshold and AllowFree with you, and separate CTxMemPoolEntry to a different file. At that point, maybe something like policy/fees makes more sense than policy/estimator, we can put more fee-related stuff there later (like CFeeRate, once CTxOut gets decoupled from it).

Also, why couple CBlockPolicyEstimator to the minRelayTxFee global when it can take CTxMemPool::minRelayFee (which is only used to pass it to CBlockPolicyEstimator::Read which ends up not using it) ??

You have some good opportunities to reduce dependency on boost or at least not increase it (I’m talking about the foreach loops), but if you don’t want to do it you can at least explicitly include the dependency in the new file.

I have created a branch with my many suggestions in form of code:

https://github.com/jtimon/bitcoin/commits/morcos_new-estimates

The last commit doesn’t pass the tests because mempool.HasNoInputsOf(tx) is always called when creating a new entry: CTxMemPoolEntry::hadNoDependencies is never set to false by default. The rest of the commits compile individually although some of them would increase your total diff to master more than others (some are “free” in that sense, like the file rename one) so it’s up which one you include. Feel free to squash, edit, reword, kill or reorder the commits as you think it’s best.

morcos commented at 5:28 pm on April 23, 2015: member

Thanks @jtimon. I included several of your commits in an all purpose SQUASHME fixup. I also changed my move commit to yours. My original commit and 2 recent additions are unchanged. I think we can PR your other changes separately afterwards. I have them rebased on top of this here: https://github.com/morcos/bitcoin/commits/new-estimates_jtimon @gavinandresen, if you wouldn’t mind reviewing the new commits. The first commit should be what you reviewed already (rebased and tidied a little).

morcos force-pushed on Apr 23, 2015

in src/txmempool.cpp: in a992a72aad outdated

105-        for (unsigned int i = 0; i < tx.vin.size(); i++)
106-            mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
107-        nTransactionsUpdated++;
108-        totalTxSize += entry.GetTxSize();
109-    }
110+    mapTx[hash] = entry;

morcos commented at 5:33 pm on April 23, 2015:

The transaction being added to the mempool has actually been copied twice at this point. The first time when the CTxMemPoolEntry was created, and now again when its copied into the map, which will be its permanent home. This was not introduced by this PR, but a further PR should consider eliminating one of the copy operations.

jtimon commented at 9:30 pm on April 23, 2015: contributor

Thanks for incorporating some of my suggestions, I’m specially happy about not using the minRelayTxFee global inside the estimator which was the most important nit. I agree all the suggestions not incorporated can wait and it’s better not to slow this down.

in src/txmempool.cpp: in a992a72aad outdated

57@@ -385,7 +58,7 @@ CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
58     // to wait a day or two to save a fraction of a penny in fees.
59     // Confirmation times for very-low-fee transactions that take more
60     // than an hour or three to confirm are highly variable.
61-    minerPolicyEstimator = new CMinerPolicyEstimator(25);
62+    minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);

sdaftuar commented at 2:20 pm on April 27, 2015:

The comment above is no longer relevant here.

in src/txmempool.h: in a992a72aad outdated

29@@ -30,6 +30,8 @@ inline bool AllowFree(double dPriority)
30 /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
31 static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;
32 
33+class CTxMemPool;

sdaftuar commented at 4:06 pm on April 27, 2015:

nit: this forward declaration doesn’t appear to be necessary

morcos commented at 1:56 pm on April 29, 2015: member

Addressed nits (above and offline) by @sdaftuar and improved the readability of the rpc test. @gavinandresen, I know there are a lot of small added commits here, and I’d like to squash them all down but just wanted to be sure you saw the changes in 64bf2bb. This slightly changes the startup behavior, but otherwise all other changes we just cleanups, and no change to behavior.

in src/policy/fees.cpp: in 17e8c84e8a outdated

162+                break;
163+            }
164+        }
165+    }
166+
167+    LogPrint("estimatefee", "%3d: For conf succeess %s %4.2f need %s %s: %12.5g from buckets %8g - %8g  Cur Bucket stats %6.2f%%  %8.1f/(%.1f+%d mempool)\n",

sdaftuar commented at 3:22 pm on April 29, 2015:

nit: succeess -> success

sdaftuar commented at 8:05 pm on April 29, 2015: member

I’ve reviewed the code (particularly to understand the details of the calculations in policy/fees.cpp), and I’ve tested by running a node with this code, and this looks good to me (and improves the estimates substantially). ACK.

jtimon commented at 9:12 pm on April 29, 2015: contributor

I’m going to make a summary of my review of this PR, hopefully it helps getting it merged soon. Although, I have not reviewed or tested the changes in the estimator itself, I have paid special attention on making sure that it only changed fee policy behavior, so I’m convinced that this is completely consensus and network safe, anything-non-fee-estimator-related safe. Reaching this conclusion was not hard because although coupled with txmempool, the estimator is encapsulated. Apart from the changes in the estimator, this is an improvement in modularity, and will open the door to further improvements in fee policy encapsulation (the min relay fee should stop being a global, all functions using it should be methods of the estimator class, but one step at a time). I repeated the moveonly part of this PR manually so if it had been separated in an individual commit I could have easily verified it, but then I git pruned that (I should have kept it).

In summary, still-untested-but-pretty-confident-ACK.

Diapolo commented at 6:13 am on April 30, 2015: none

I didn’t try to check or understand that code, but wanted to ask if the GUI (e.g. coincontrol and smart fees) is working with this without problems or if that needs to be verified.

morcos commented at 3:08 pm on April 30, 2015: member

@Diapolo Thanks for thinking about that. I think it could certainly use some more testing. There are two things in my mind that could use improving.

I think the default txConfirmTarget should be greater than 1. There are periods of time when 1 can be quite a high fee temporarily. I plan to open this discussion in a different PR at some point, because its a bit of a separate discussion. This doesn’t really affect the GUI, though since that uses a default of 25.
It’s also possible at times to not have an answer for estimatefee 1 but to have answer for all other estimates. This is a feature not a bug, but I think it would be possible to design a better UI experience in that case. Perhaps the slider bounces back to the first legitimate estimate, or gives you a helpful message such as “No amount of fee will get you reliably confirmed in the next block”.

bitcoinfees commented at 10:05 am on May 10, 2015: none

There are periods of time when 1 can be quite a high fee temporarily

A suggestion: if fractional arguments are allowed for estimatefee, it could avoid the need for MIN_SUCCESS_PCT, which in my view discards useful information, and perhaps is the reason for these kinds of problems (e.g. a fee bucket which for a given confTarget has a curPct that is close to the 0.85 threshold would result in unstable behavior, if I’ve understood properly).

With fractional confTarget, each fee bucket could be represented by its mean conf, and compared to confTarget directly to determine success. The default txConfirmTarget could then be set to fractional values, e.g. 1.2, which would perhaps result in greater stability.

bitcoinfees commented at 10:28 am on May 10, 2015: none

not have an answer for estimatefee 1

With regard to fee buckets clearing the MIN_SUCCESS_PCT hurdle of 0.85, I’ve found in my own studies that the main reason why transactions with relatively high fees don’t make it into the next block is because of the interval between miners updating their block transaction lists, which I believe is on the order of 30-60 seconds (source).

This means that if a transaction has been in the mempool for less than 60 seconds, there is a chance it won’t be considered for block inclusion at all by the miner, regardless of the tx fee. After removing these transactions from the estimation, I’ve found that the relative frequency of high-fee transactions being included in the next block is pretty high and consistent, typically > 95%.

morcos commented at 2:58 pm on May 11, 2015: member

@bitcoinfees, thanks for the comments. I think asking for the mean number of blocks to confirmation is a slightly different question than I answered. It’s not clear if one question is better than another, but the way I defined the question is what fee would you need to have a sufficiently high percentage chance of getting confirmed in the desired number of blocks, so it kind of requires a MIN_SUCCESS_PCT. But to your point, I do think that there could be a lot of improvements to this estimation algorithm, and hopefully they could build off the framework it provides.

I agree with your conclusion on why the success percentage has a ceiling around 90%. Hopefully with an improved transaction selection algorithm for mining in the future that will get better.

gavinandresen commented at 6:50 pm on May 12, 2015: contributor

Code review and lightly tested ACK.

I’m updating core2.bitcoincore.org to run this version of the code now.

morcos force-pushed on May 12, 2015

morcos commented at 7:13 pm on May 12, 2015: member

squashed to hopefully make it mergeable

Create new BlockPolicyEstimator for fee estimates

This class groups transactions that have been confirmed in blocks into buckets, based on either their fee or their priority.  Then for each bucket, the class calculates what percentage of the transactions were confirmed within various numbers of blocks.  It does this by keeping an exponentially decaying moving history for each bucket and confirm block count of the percentage of transactions in that bucket that were confirmed within that number of blocks.

-Eliminate txs which didn't have all inputs available at entry from fee/pri calcs

-Add dynamic breakpoints and tracking of confirmation delays in mempool transactions

-Remove old CMinerPolicyEstimator and CBlockAverage code

-New smartfees.py

-Pass a flag to the estimation code, using IsInitialBlockDownload as a proxy for when we are still catching up and we shouldn't be counting how many blocks it takes for transactions to be included.

-Add a policyestimator unit test

b649e03954

in src/policy/fees.cpp: in df623a549b outdated

0@@ -0,0 +1,529 @@
1+// Copyright (c) 2009-2010 Satoshi Nakamoto
2+// Copyright (c) 2009-2015 The Bitcoin developers
3+// Distributed under the MIT/X11 software license, see the accompanying

fanquake commented at 2:29 pm on May 13, 2015:

nit: just MIT

in src/policy/fees.h: in df623a549b outdated

0@@ -0,0 +1,276 @@
1+// Copyright (c) 2009-2010 Satoshi Nakamoto
2+// Copyright (c) 2009-2015 The Bitcoin developers
3+// Distributed under the MIT/X11 software license, see the accompanying

fanquake commented at 2:30 pm on May 13, 2015:

also here

morcos force-pushed on May 13, 2015

morcos commented at 2:43 pm on May 13, 2015: member

nits addressed

laanwj commented at 3:01 pm on May 13, 2015: member

utACK

laanwj merged this on May 13, 2015

laanwj closed this on May 13, 2015

laanwj referenced this in commit 2cc1372190 on May 13, 2015

furszy referenced this in commit 7c102142c7 on Jun 2, 2020

MarcoFalke locked this on Sep 8, 2021

New fee estimation code #5159