Line data    Source code

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