Improve fee estimation #9138

morcos commented at 9:29 PM on November 11, 2016: member

This PR is partly a refactor, partly bug fix, and partly improved robustness in edge cases. Outside of the edge cases (when your node is behind) the results are unchanged.

Explanations of the changes in the individual commits.

fanquake added the label Mempool on Nov 12, 2016

fanquake added the label TX fees and policy on Nov 12, 2016

in src/main.cpp:None in 989a2c4579 outdated

1179 | +        return false;
1180 | +    if (chainActive.Tip()->GetBlockTime() < (GetTime() - MAX_FEE_ESTIMATION_TIP_AGE))
1181 | +        return false;
1182 | +    if (chainActive.Height() < pindexBestHeader->nHeight - 1)
1183 | +        return false;
1184 | +    return true;

rebroad commented at 3:37 AM on November 13, 2016:

nit - usually a blank line before this line (but probably not a standard)

in src/policy/fees.cpp:None in 989a2c4579 outdated

 352 |  
 353 |      // How many blocks did it take for miners to include this transaction?
 354 |      // blocksToConfirm is 1-based, so a transaction included in the earliest
 355 |      // possible block has confirmation count of 1
 356 | -    int blocksToConfirm = nBlockHeight - entry.GetHeight();
 357 | +    int blocksToConfirm = nBlockHeight - entry->GetHeight();

rebroad commented at 3:39 AM on November 13, 2016:

what did this fix please?

morcos commented at 4:59 PM on November 13, 2016:

Please see commit message "Pass pointers to existing CTxMemPoolEntries to fee estimation" The idea is this would save unnecessary copying.

morcos force-pushed on Nov 14, 2016

morcos force-pushed on Nov 21, 2016

morcos commented at 8:11 PM on November 21, 2016: member

rebased

gmaxwell commented at 10:40 PM on November 23, 2016: contributor

Concept ACK.

jonasschnelli commented at 7:55 AM on November 25, 2016: contributor

Ran this code on top of master on one of my nodes. Just compared it to the node running master (same network but independent mempool), see below. The differences for a conf. target of 2 blocks are quite large.

Next step would be to run master and this PR with the same mempool and maybe dump 2,4,8,20 target every ~10mins.

masternode ~/node/bitcoin $ ./src/bitcoin-cli getmempoolinfo
{
  "size": 22022,
  "bytes": 133099706,
  "usage": 252978016,
  "maxmempool": 300000000,
  "mempoolminfee": 0.00001014
}
masternode ~/node/bitcoin $ ./src/bitcoin-cli estimatesmartfee 2
{
  "feerate": 0.00761447,
  "blocks": 2
}
masternode ~/node/bitcoin $ ./src/bitcoin-cli estimatesmartfee 3
{
  "feerate": 0.00069881,
  "blocks": 3
}
masternode ~/node/bitcoin $ ./src/bitcoin-cli estimatesmartfee 8
{
  "feerate": 0.00069881,
  "blocks": 8
}

thisprnode ~/bitcoin/bitcoin $ ./src/bitcoin-cli getmempoolinfo
{
  "size": 24593,
  "bytes": 140534928,
  "usage": 268029424,
  "maxmempool": 300000000,
  "mempoolminfee": 0.00001000
}
thisprnode ~/bitcoin/bitcoin $ ./src/bitcoin-cli estimatesmartfee 2
{
  "feerate": 0.00083575,
  "blocks": 2
}
thisprnode ~/bitcoin/bitcoin $ ./src/bitcoin-cli estimatesmartfee 3
{
  "feerate": 0.00077770,
  "blocks": 3
}
thisprnode ~/bitcoin/bitcoin $ ./src/bitcoin-cli estimatesmartfee 8
{
  "feerate": 0.00069872,
  "blocks": 8
}

morcos commented at 10:08 PM on November 25, 2016: member

@jonasschnelli I simulated this PR's code against master and the differences were very slight. If your testing setups were identical (started with the same fee estimates and started the nodes at the same time), then the way you might see substantial differences is if your testing nodes have to catch up a little bit when you start them, then this code will decay your old estimates and the old code wouldn't. So this code will more quickly reflect current conditions instead of still having a heavy weight for old fee estimates. Furthermore if you started this code after being down for more than a few weeks, you might even start seeing messages about fee estimates need to warm up as the historical data will have decayed so much.

in src/policy/fees.cpp:None in 4495113d24 outdated

 381 | @@ -392,6 +382,9 @@ void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
 382 |      for (unsigned int i = 0; i < entries.size(); i++)
 383 |          processBlockTx(nBlockHeight, entries[i]);
 384 |  
 385 | +    // Update best seen height after removals so they find the right mempool txs

sdaftuar commented at 1:14 AM on November 29, 2016:

Can you clarify this comment? I have been staring at this for a while and can't figure out what you meant.

in src/main.h:None in 89e6dab820 outdated

 127 | @@ -128,6 +128,8 @@ static const int64_t BLOCK_DOWNLOAD_TIMEOUT_PER_PEER = 500000;
 128 |  static const unsigned int DEFAULT_LIMITFREERELAY = 0;
 129 |  static const bool DEFAULT_RELAYPRIORITY = true;
 130 |  static const int64_t DEFAULT_MAX_TIP_AGE = 24 * 60 * 60;
 131 | +/** Maximum age of our tip for us to be considered current for fee estimation */

sdaftuar commented at 1:41 AM on November 29, 2016:

nit: Can you update the comment to include the unit (ie seconds)?

sdaftuar commented at 1:45 AM on November 29, 2016: member

Code review ACK. Will test.

in src/policy/fees.cpp:None in 4495113d24 outdated

 335 | @@ -343,10 +336,8 @@ void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, boo
 336 |  
 337 |  void CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry)
 338 |  {
 339 | -    if (!entry.WasClearAtEntry()) {
 340 | -        // This transaction depended on other transactions in the mempool to
 341 | -        // be included in a block before it was able to be included, so
 342 | -        // we shouldn't include it in our calculations
 343 | +    if (!removeTx(entry.GetTx().GetHash())) {

sdaftuar commented at 1:51 PM on November 29, 2016:

Does calling this here result in one extra call to removeTx() for each in-mempool, in-block transaction? It looks like we also will call this in CTxMempool::removeUnchecked, which I guess is harmless, but worth commenting.

morcos commented at 8:59 PM on November 29, 2016: member

Addressed @sdaftuar's comment requests.
Fixed a pre-existing rare edge case which would print errors and make estimates slightly off.
Fixed a bug in this PR. @gmaxwell once you see the BUGFIX commit, I'll squash just that one into the right place in the history.

in src/main.cpp:None in 89e6dab820 outdated

1172 | @@ -1173,6 +1173,17 @@ std::string FormatStateMessage(const CValidationState &state)
1173 |          state.GetRejectCode());
1174 |  }
1175 |  
1176 | +static bool IsCurrentForFeeEstimation()
1177 | +{
1178 | +    if (IsInitialBlockDownload())
1179 | +        return false;
1180 | +    if (chainActive.Tip()->GetBlockTime() < (GetTime() - MAX_FEE_ESTIMATION_TIP_AGE))

sdaftuar commented at 5:59 PM on November 30, 2016:

nit: I think we should AssertLockHeld(cs_main) here.

sdaftuar commented at 7:55 PM on November 30, 2016: member

Tested this code in simulation on 10 days in July, comparing the transactions tracked and the fee estimates returned before and after this PR. ACK apart from the AssertLockHeld nit above.

morcos force-pushed on Dec 3, 2016

morcos commented at 2:03 PM on December 3, 2016: member

dancing again on the grave of main.cpp

This was a clean rebase and I added @sdaftuar's AssertLockHeld.

In a couple days I'll squash the last two commits...

morcos force-pushed on Dec 5, 2016

morcos commented at 7:52 PM on December 5, 2016: member

rebased (and squashed in the bugfix and assert) @fanquake please milestone for 0.14.0

MarcoFalke added this to the milestone 0.14.0 on Dec 5, 2016

sdaftuar commented at 6:18 PM on December 9, 2016: member

re-ACK 98fffcb

morcos force-pushed on Dec 10, 2016

morcos commented at 3:22 PM on December 10, 2016: member

Simple rebase due to expected conflict on function signature of CTxMemPool:removeForBlock

sdaftuar commented at 7:11 PM on December 10, 2016: member

re-ACK 761a9be

in src/policy/fees.cpp:None in a8c1c64ac8 outdated

 292 | +    if (pos != mapMemPoolTxs.end()) {
 293 | +        feeStats.removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex);
 294 | +        mapMemPoolTxs.erase(hash);
 295 | +        return true;
 296 | +    }
 297 | +    else {

sipa commented at 7:12 PM on December 10, 2016:

Coding style nit: else on the same line.

in src/txmempool.cpp:None in 60f163c128 outdated

 601 |          uint256 hash = tx->GetHash();
 602 |  
 603 |          indexed_transaction_set::iterator i = mapTx.find(hash);
 604 |          if (i != mapTx.end())
 605 | -            entries.push_back(*i);
 606 | +            entries.push_back(&(*i));

sipa commented at 7:35 PM on December 10, 2016:

Parentheses aren't needed here.

sipa commented at 7:37 PM on December 10, 2016: member

Code review ACK. I don't understand the fee estimation code enough to judge the changes to the semantics.

morcos force-pushed on Dec 30, 2016

morcos commented at 2:04 PM on December 30, 2016: member

Rebased to fix a silent merge conflict (the change in wallet.cpp) Also fixed @sipa's nits, otherwise unchanged from reviewed code.

gmaxwell commented at 3:44 PM on January 4, 2017: contributor

reviewed and tested this before it got conflicted ACK. needs rebase.

Remove extraneous LogPrint from fee estimation

Once priority estimation was removed, not all transactions in the mempool are tracked in the fee estimation mempool tracking.  So there is no error if a transaction is not found for removal.

4df44794c9

Don't track transactions at all during IBD.

This was an oversight, where blocks and mempool tracking were ignored during IBD, but transactions that arrived during IBD but were included in blocks after IBD were not ignored.

60ac00de85

Remove member variable hadNoDependencies from CTxMemPoolEntry

Fee estimation can just check its own mapMemPoolTxs to determine the same information.  Note that now fee estimation for block processing must happen before those transactions are removed, but this shoudl be a speedup.

84f7ab08d2

rename bool to validFeeEstimate 6f06b268c1

Always update fee estimates on new blocks.

All decisions about whether the transactions are valid data points are made at the time the transaction arrives. Updating on blocks all the time will now cause stale fee estimates to decay quickly when we restart a node.

d825838e64

Pass pointers to existing CTxMemPoolEntries to fee estimation ebafdcabb1

Add IsCurrentForFeeEstimatation

Make a more conservative notion of whether the node is caught up to the rest of the network and only count transactions as fee estimation data points if the node is caught up.

dc008c462f

Add extra logging to processBlock in fee estimation. 5fe0f47aa7

Add clarifying comments to fee estimation 78ae62d264

Fix edge case with stale fee estimates 44b64b933d

morcos force-pushed on Jan 4, 2017

morcos commented at 5:35 PM on January 4, 2017: member

rebased

sdaftuar commented at 10:04 PM on January 5, 2017: member

re-ACK 44b64b933dec10f5ffcd7f34e7bf5e4ed97f671e

sipa commented at 10:14 PM on January 5, 2017: member

utACK 44b64b933dec10f5ffcd7f34e7bf5e4ed97f671e

sipa merged this on Jan 5, 2017

sipa closed this on Jan 5, 2017

sipa referenced this in commit f646275b90 on Jan 5, 2017

codablock referenced this in commit 0bd9056899 on Jan 18, 2018

andvgal referenced this in commit ef5528d0c8 on Jan 6, 2019

CryptoCentric referenced this in commit d4fc4231ee on Feb 26, 2019

CryptoCentric referenced this in commit 41fe5ce452 on Feb 26, 2019

furszy referenced this in commit b554c29785 on Jul 14, 2021

MarcoFalke locked this on Sep 8, 2021