diff --git a/src/feerate.h b/src/feerate.h --- a/src/feerate.h +++ b/src/feerate.h @@ -84,6 +84,9 @@ nSatoshisPerK += a.nSatoshisPerK; return *this; } + CFeeRate operator+(const CFeeRate &a) { + return CFeeRate(nSatoshisPerK + a.nSatoshisPerK); + } std::string ToString() const; ADD_SERIALIZE_METHODS; diff --git a/src/policy/fees.h b/src/policy/fees.h --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -14,6 +14,37 @@ #include class CFeeRate; +class CTxMemPoolEntry; +class CTxMemPool; + +/** \class MempoolFeeEstimator + * The MempoolFeeEstimator is used for estimating the feerate needed for a + * transaction to be included in a block within a certain number of blocks. + */ +class MempoolFeeEstimator { +private: + std::vector m_minHeap; + std::vector m_maxHeap; + +public: + MempoolFeeEstimator() {} + + /** + * Clear the state of the curBlock variables to start counting for after a + * block is received. + */ + void clear(); + + /** + * Record a new fee data point in the current block stats + */ + void addFee(CFeeRate fee); + + /** + * Calculate a feerate estimate. + */ + CFeeRate estimateMedian(); +}; // Minimum and Maximum values for tracking feerates static constexpr Amount MIN_FEERATE(10 * SATOSHI); diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp --- a/src/policy/fees.cpp +++ b/src/policy/fees.cpp @@ -8,6 +8,63 @@ #include "amount.h" #include "feerate.h" +#include +#include + +void MempoolFeeEstimator::clear() { + m_maxHeap.resize(0); + m_minHeap.resize(0); +} + +static bool maxComparor(const CFeeRate &a, const CFeeRate &b) { + return a < b; +} + +static bool minComparor(const CFeeRate &a, const CFeeRate &b) { + return a >= b; +} + +void MempoolFeeEstimator::addFee(CFeeRate fee) { + auto maxHeapSize = m_maxHeap.size(); + auto minHeapSize = m_minHeap.size(); + + // Add the fee to the appropriate half + if (maxHeapSize == 0 || fee < m_maxHeap.front()) { + m_maxHeap.push_back(fee); + std::push_heap(m_maxHeap.begin(), m_maxHeap.end(), maxComparor); + maxHeapSize++; + } else { + m_minHeap.push_back(fee); + std::push_heap(m_minHeap.begin(), m_minHeap.end(), minComparor); + minHeapSize++; + } + + // Rebalance if one heap is too large + if (maxHeapSize + 1 < minHeapSize) { + m_maxHeap.push_back(m_minHeap.front()); + std::push_heap(m_maxHeap.begin(), m_maxHeap.end(), maxComparor); + std::pop_heap(m_minHeap.begin(), m_minHeap.end(), minComparor); + m_minHeap.pop_back(); + } else if (minHeapSize + 1 < maxHeapSize) { + m_minHeap.push_back(m_maxHeap.front()); + std::push_heap(m_minHeap.begin(), m_minHeap.end(), minComparor); + std::pop_heap(m_maxHeap.begin(), m_maxHeap.end(), maxComparor); + m_maxHeap.pop_back(); + } +} + +CFeeRate MempoolFeeEstimator::estimateMedian() { + if (m_maxHeap.size() == m_minHeap.size()) { + return CFeeRate( + (m_minHeap.front().GetFeePerK() + m_maxHeap.front().GetFeePerK()) / + 2); + } else if (m_maxHeap.size() > m_minHeap.size()) { + return m_maxHeap.front(); + } else { + return m_minHeap.front(); + } +} + FeeFilterRounder::FeeFilterRounder(const CFeeRate &minIncrementalFee) { Amount minFeeLimit = std::max(SATOSHI, minIncrementalFee.GetFeePerK() / 2); feeset.insert(Amount::zero()); diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp --- a/src/test/policyestimator_tests.cpp +++ b/src/test/policyestimator_tests.cpp @@ -10,10 +10,87 @@ #include "test/test_bitcoin.h" +#include + #include BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, BasicTestingSetup) +BOOST_AUTO_TEST_CASE(test_MempoolFeeEstimator) { + MempoolFeeEstimator estimator; + + // Setup test vectors + const std::vector, int64_t>> testVectors = + // clang-format off + { + // 100 + { + { + 2803191610, 1665259296, 3017721833, 2986207249, 12454561, 429909583, 2172418177, 3220092313, 797263256, 3102522623, 3619233345, 78337883, 3594798568, 2997954776, 3960188831, 3286386618, 372739268, 3310148178, 3575803112, 4015112868, 2894877168, 2114112480, 3719646217, 2300990239, 2763682419, 2988504717, 2002818567, 348806867, 4164134681, 2012678115, 1779699165, 2426435851, 2919389731, 1276955815, 3021648373, 1856132185, 1159622780, 3010916025, 1179487843, 1750459207, 3404485044, 1178347823, 3591978718, 1673890834, 3301517967, 1240031029, 3112365468, 2765214987, 3578294215, 4035939883, 1191268086, 1242285546, 3982233965, 3198355589, 1891914350, 1895176869, 2487346689, 2052048796, 3687204252, 798590048, 3193410049, 97729384, 2113406599, 3066614345, 3217861756, 700205360, 336277470, 2529225594, 1990070335, 2030807376, 3123781083, 3270138815, 322266393, 4216198057, 3579688796, 3826329749, 135728282, 806765104, 702763782, 1319682355, 3774201367, 2255447957, 357276514, 182568023, 1279395821, 1688862045, 2476311018, 3867613167, 1186711074, 3902141265, 3695644243, 3559679440, 1674006868, 296422900, 2051587262, 597578992, 3072594335, 1672969621, 3056418633, 2807888856 + }, + 2451373434 + }, + // 100 + { + { + 1886853320, 759137998, 1189835, 2825329433, 2990370939, 1167415865, 1753399129, 1764354820, 4274916472, 1506634436, 3170208666, 4121579022, 688576472, 1616748988, 962033256, 3565817581, 2886784062, 2655237279, 1075960042, 26911887, 1301912191, 2405243999, 3418091441, 3686924124, 2093800780, 2999239665, 990527032, 3781190154, 2385514298, 4025662835, 1621761989, 2901738150, 3020546474, 1171629821, 324611086, 4135097116, 3800239918, 55402626, 1166240389, 2185095000, 1537162355, 1937903695, 3746488405, 3554853116, 1826576824, 2628701043, 4108745040, 47679851, 521329357, 3025901899, 1439101319, 1301152463, 2903114131, 1489646076, 4163382302, 2600746334, 3048725169, 447774589, 3013196650, 3852348628, 1455722408, 1632464215, 3261964241, 1734571161, 596959378, 2548681538, 1987430571, 125863769, 3205803129, 12978770, 3687283485, 1748723017, 232679838, 274884694, 1176092819, 1487618344, 2343556342, 1654968740, 42185361, 874405878, 2098296175, 1475475605, 264422511, 3020745792, 68431218, 1981266123, 981272837, 4258129953, 112200758, 1794571291, 1280919148, 4047060293, 2789725239, 2286645422, 2318191267, 1151514983, 2502548757, 1471923925, 3712664609, 3857051409 + }, + 1912378507, + }, + // 11 + { + { + 3245925615, 710806425, 342895753, 3436344501, 1363278844, 2302386106, 2403976233, 527112335, 2154790945, 3476243629, 3837337380 + }, + 2302386106, + }, + // 31 + { + { + 76041705, 1548827089, 231187450, 1917666974, 4027464785, 4192368635, 69182757, 2785868328, 4155029516, 4750985, 3592956779, 1711240444, 3313617757, 3240394598, 3288314664, 2411234787, 256112255, 1751261088, 1794998187, 2723044871, 227705520, 2615829424, 1449906786, 3369104649, 2777604714, 943465134, 3562496141, 3869696247, 1209325557, 2899262386, 3027458358 + }, + 2615829424, + }, + // 9 + { + { + 38, 224, 10, 54, 120, 178, 79, 89, 62 + }, + 79, + }, + // 9 Order doesn't matter + { + { + 10, 38, 54, 62, 79, 89, 120, 178, 224 + }, + 79, + }, + // 10 + { + { + 130, 166, 65, 154, 11, 164, 74, 242, 50, 157 + }, + 142, + }, + }; + // clang-format on + + for (auto entry : testVectors) { + std::vector feeRates; + int64_t median; + std::tie(feeRates, median) = entry; + for (auto &&feeRate : feeRates) { + estimator.addFee(CFeeRate(feeRate * SATOSHI)); + } + BOOST_CHECK_MESSAGE( + estimator.estimateMedian() == CFeeRate(median * SATOSHI), + "Median is incorrect: " + << estimator.estimateMedian().ToString() << " should be: " + << CFeeRate(int64_t(median) * SATOSHI).ToString()); + estimator.clear(); + } +} + BOOST_AUTO_TEST_CASE(MempoolMinimumFeeEstimate) { CTxMemPool mpool; TestMemPoolEntryHelper entry;