src/test/policyestimator_tests.cpp

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