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