Branch data     Line data    Source code

       1                 :            : // Copyright (c) 2011-2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #include <policy/fees.h>
       6                 :            : #include <policy/policy.h>
       7                 :            : #include <test/util/txmempool.h>
       8                 :            : #include <txmempool.h>
       9                 :            : #include <uint256.h>
      10                 :            : #include <util/time.h>
      11                 :            : 
      12                 :            : #include <test/util/setup_common.h>
      13                 :            : 
      14                 :            : #include <boost/test/unit_test.hpp>
      15                 :            : 
      16                 :          0 : BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, ChainTestingSetup)
      17                 :          0 : 
      18                 :          0 : BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
      19                 :            : {
      20                 :          0 :     CBlockPolicyEstimator& feeEst = *Assert(m_node.fee_estimator);
      21                 :          0 :     CTxMemPool& mpool = *Assert(m_node.mempool);
      22                 :          0 :     LOCK2(cs_main, mpool.cs);
      23                 :          0 :     TestMemPoolEntryHelper entry;
      24                 :          0 :     CAmount basefee(2000);
      25                 :          0 :     CAmount deltaFee(100);
      26                 :          0 :     std::vector<CAmount> feeV;
      27                 :          0 :     feeV.reserve(10);
      28                 :            : 
      29                 :            :     // Populate vectors of increasing fees
      30                 :          0 :     for (int j = 0; j < 10; j++) {
      31                 :          0 :         feeV.push_back(basefee * (j+1));
      32                 :          0 :     }
      33                 :            : 
      34                 :            :     // Store the hashes of transactions that have been
      35                 :            :     // added to the mempool by their associate fee
      36                 :            :     // txHashes[j] is populated with transactions either of
      37                 :            :     // fee = basefee * (j+1)
      38                 :          0 :     std::vector<uint256> txHashes[10];
      39                 :            : 
      40                 :            :     // Create a transaction template
      41                 :          0 :     CScript garbage;
      42                 :          0 :     for (unsigned int i = 0; i < 128; i++)
      43                 :          0 :         garbage.push_back('X');
      44                 :          0 :     CMutableTransaction tx;
      45                 :          0 :     tx.vin.resize(1);
      46                 :          0 :     tx.vin[0].scriptSig = garbage;
      47                 :          0 :     tx.vout.resize(1);
      48                 :          0 :     tx.vout[0].nValue=0LL;
      49                 :          0 :     CFeeRate baseRate(basefee, GetVirtualTransactionSize(CTransaction(tx)));
      50                 :            : 
      51                 :            :     // Create a fake block
      52                 :          0 :     std::vector<CTransactionRef> block;
      53                 :          0 :     int blocknum = 0;
      54                 :            : 
      55                 :            :     // Loop through 200 blocks
      56                 :            :     // At a decay .9952 and 4 fee transactions per block
      57                 :            :     // This makes the tx count about 2.5 per bucket, well above the 0.1 threshold
      58                 :          0 :     while (blocknum < 200) {
      59                 :          0 :         for (int j = 0; j < 10; j++) { // For each fee
      60                 :          0 :             for (int k = 0; k < 4; k++) { // add 4 fee txs
      61                 :          0 :                 tx.vin[0].prevout.n = 10000*blocknum+100*j+k; // make transaction unique
      62                 :          0 :                 uint256 hash = tx.GetHash();
      63                 :          0 :                 mpool.addUnchecked(entry.Fee(feeV[j]).Time(Now<NodeSeconds>()).Height(blocknum).FromTx(tx));
      64                 :          0 :                 txHashes[j].push_back(hash);
      65                 :          0 :             }
      66                 :          0 :         }
      67                 :            :         //Create blocks where higher fee txs are included more often
      68                 :          0 :         for (int h = 0; h <= blocknum%10; h++) {
      69                 :            :             // 10/10 blocks add highest fee transactions
      70                 :            :             // 9/10 blocks add 2nd highest and so on until ...
      71                 :            :             // 1/10 blocks add lowest fee transactions
      72                 :          0 :             while (txHashes[9-h].size()) {
      73                 :          0 :                 CTransactionRef ptx = mpool.get(txHashes[9-h].back());
      74                 :          0 :                 if (ptx)
      75                 :          0 :                     block.push_back(ptx);
      76                 :          0 :                 txHashes[9-h].pop_back();
      77                 :          0 :             }
      78                 :          0 :         }
      79                 :          0 :         mpool.removeForBlock(block, ++blocknum);
      80                 :          0 :         block.clear();
      81                 :            :         // Check after just a few txs that combining buckets works as expected
      82                 :          0 :         if (blocknum == 3) {
      83                 :            :             // At this point we should need to combine 3 buckets to get enough data points
      84                 :            :             // So estimateFee(1) should fail and estimateFee(2) should return somewhere around
      85                 :            :             // 9*baserate.  estimateFee(2) %'s are 100,100,90 = average 97%
      86                 :          0 :             BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
      87                 :          0 :             BOOST_CHECK(feeEst.estimateFee(2).GetFeePerK() < 9*baseRate.GetFeePerK() + deltaFee);
      88                 :          0 :             BOOST_CHECK(feeEst.estimateFee(2).GetFeePerK() > 9*baseRate.GetFeePerK() - deltaFee);
      89                 :          0 :         }
      90                 :            :     }
      91                 :            : 
      92                 :          0 :     std::vector<CAmount> origFeeEst;
      93                 :            :     // Highest feerate is 10*baseRate and gets in all blocks,
      94                 :            :     // second highest feerate is 9*baseRate and gets in 9/10 blocks = 90%,
      95                 :            :     // third highest feerate is 8*base rate, and gets in 8/10 blocks = 80%,
      96                 :            :     // so estimateFee(1) would return 10*baseRate but is hardcoded to return failure
      97                 :            :     // Second highest feerate has 100% chance of being included by 2 blocks,
      98                 :            :     // so estimateFee(2) should return 9*baseRate etc...
      99                 :          0 :     for (int i = 1; i < 10;i++) {
     100                 :          0 :         origFeeEst.push_back(feeEst.estimateFee(i).GetFeePerK());
     101                 :          0 :         if (i > 2) { // Fee estimates should be monotonically decreasing
     102                 :          0 :             BOOST_CHECK(origFeeEst[i-1] <= origFeeEst[i-2]);
     103                 :          0 :         }
     104                 :          0 :         int mult = 11-i;
     105                 :          0 :         if (i % 2 == 0) { //At scale 2, test logic is only correct for even targets
     106                 :          0 :             BOOST_CHECK(origFeeEst[i-1] < mult*baseRate.GetFeePerK() + deltaFee);
     107                 :          0 :             BOOST_CHECK(origFeeEst[i-1] > mult*baseRate.GetFeePerK() - deltaFee);
     108                 :          0 :         }
     109                 :          0 :     }
     110                 :            :     // Fill out rest of the original estimates
     111                 :          0 :     for (int i = 10; i <= 48; i++) {
     112                 :          0 :         origFeeEst.push_back(feeEst.estimateFee(i).GetFeePerK());
     113                 :          0 :     }
     114                 :            : 
     115                 :            :     // Mine 50 more blocks with no transactions happening, estimates shouldn't change
     116                 :            :     // We haven't decayed the moving average enough so we still have enough data points in every bucket
     117                 :          0 :     while (blocknum < 250)
     118                 :          0 :         mpool.removeForBlock(block, ++blocknum);
     119                 :            : 
     120                 :          0 :     BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
     121                 :          0 :     for (int i = 2; i < 10;i++) {
     122                 :          0 :         BOOST_CHECK(feeEst.estimateFee(i).GetFeePerK() < origFeeEst[i-1] + deltaFee);
     123                 :          0 :         BOOST_CHECK(feeEst.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
     124                 :          0 :     }
     125                 :            : 
     126                 :            : 
     127                 :            :     // Mine 15 more blocks with lots of transactions happening and not getting mined
     128                 :            :     // Estimates should go up
     129                 :          0 :     while (blocknum < 265) {
     130                 :          0 :         for (int j = 0; j < 10; j++) { // For each fee multiple
     131                 :          0 :             for (int k = 0; k < 4; k++) { // add 4 fee txs
     132                 :          0 :                 tx.vin[0].prevout.n = 10000*blocknum+100*j+k;
     133                 :          0 :                 uint256 hash = tx.GetHash();
     134                 :          0 :                 mpool.addUnchecked(entry.Fee(feeV[j]).Time(Now<NodeSeconds>()).Height(blocknum).FromTx(tx));
     135                 :          0 :                 txHashes[j].push_back(hash);
     136                 :          0 :             }
     137                 :          0 :         }
     138                 :          0 :         mpool.removeForBlock(block, ++blocknum);
     139                 :            :     }
     140                 :            : 
     141                 :          0 :     for (int i = 1; i < 10;i++) {
     142                 :          0 :         BOOST_CHECK(feeEst.estimateFee(i) == CFeeRate(0) || feeEst.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
     143                 :          0 :     }
     144                 :            : 
     145                 :            :     // Mine all those transactions
     146                 :            :     // Estimates should still not be below original
     147                 :          0 :     for (int j = 0; j < 10; j++) {
     148                 :          0 :         while(txHashes[j].size()) {
     149                 :          0 :             CTransactionRef ptx = mpool.get(txHashes[j].back());
     150                 :          0 :             if (ptx)
     151                 :          0 :                 block.push_back(ptx);
     152                 :          0 :             txHashes[j].pop_back();
     153                 :          0 :         }
     154                 :          0 :     }
     155                 :          0 :     mpool.removeForBlock(block, 266);
     156                 :          0 :     block.clear();
     157                 :          0 :     BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
     158                 :          0 :     for (int i = 2; i < 10;i++) {
     159                 :          0 :         BOOST_CHECK(feeEst.estimateFee(i) == CFeeRate(0) || feeEst.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
     160                 :          0 :     }
     161                 :            : 
     162                 :            :     // Mine 400 more blocks where everything is mined every block
     163                 :            :     // Estimates should be below original estimates
     164                 :          0 :     while (blocknum < 665) {
     165                 :          0 :         for (int j = 0; j < 10; j++) { // For each fee multiple
     166                 :          0 :             for (int k = 0; k < 4; k++) { // add 4 fee txs
     167                 :          0 :                 tx.vin[0].prevout.n = 10000*blocknum+100*j+k;
     168                 :          0 :                 uint256 hash = tx.GetHash();
     169                 :          0 :                 mpool.addUnchecked(entry.Fee(feeV[j]).Time(Now<NodeSeconds>()).Height(blocknum).FromTx(tx));
     170                 :          0 :                 CTransactionRef ptx = mpool.get(hash);
     171                 :          0 :                 if (ptx)
     172                 :          0 :                     block.push_back(ptx);
     173                 :            : 
     174                 :          0 :             }
     175                 :          0 :         }
     176                 :          0 :         mpool.removeForBlock(block, ++blocknum);
     177                 :          0 :         block.clear();
     178                 :            :     }
     179                 :          0 :     BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
     180                 :          0 :     for (int i = 2; i < 9; i++) { // At 9, the original estimate was already at the bottom (b/c scale = 2)
     181                 :          0 :         BOOST_CHECK(feeEst.estimateFee(i).GetFeePerK() < origFeeEst[i-1] - deltaFee);
     182                 :          0 :     }
     183                 :          0 : }
     184                 :            : 
     185                 :          0 : BOOST_AUTO_TEST_SUITE_END()