You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

fees.h 12KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297
  1. // Copyright (c) 2009-2010 Satoshi Nakamoto
  2. // Copyright (c) 2009-2016 The Starwels developers
  3. // Distributed under the MIT software license, see the accompanying
  4. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5. #ifndef STARWELS_POLICYESTIMATOR_H
  6. #define STARWELS_POLICYESTIMATOR_H
  7. #include "amount.h"
  8. #include "feerate.h"
  9. #include "uint256.h"
  10. #include "random.h"
  11. #include "sync.h"
  12. #include <map>
  13. #include <string>
  14. #include <vector>
  15. class CAutoFile;
  16. class CFeeRate;
  17. class CTxMemPoolEntry;
  18. class CTxMemPool;
  19. class TxConfirmStats;
  20. /** \class CBlockPolicyEstimator
  21. * The BlockPolicyEstimator is used for estimating the feerate needed
  22. * for a transaction to be included in a block within a certain number of
  23. * blocks.
  24. *
  25. * At a high level the algorithm works by grouping transactions into buckets
  26. * based on having similar feerates and then tracking how long it
  27. * takes transactions in the various buckets to be mined. It operates under
  28. * the assumption that in general transactions of higher feerate will be
  29. * included in blocks before transactions of lower feerate. So for
  30. * example if you wanted to know what feerate you should put on a transaction to
  31. * be included in a block within the next 5 blocks, you would start by looking
  32. * at the bucket with the highest feerate transactions and verifying that a
  33. * sufficiently high percentage of them were confirmed within 5 blocks and
  34. * then you would look at the next highest feerate bucket, and so on, stopping at
  35. * the last bucket to pass the test. The average feerate of transactions in this
  36. * bucket will give you an indication of the lowest feerate you can put on a
  37. * transaction and still have a sufficiently high chance of being confirmed
  38. * within your desired 5 blocks.
  39. *
  40. * Here is a brief description of the implementation:
  41. * When a transaction enters the mempool, we track the height of the block chain
  42. * at entry. All further calculations are conducted only on this set of "seen"
  43. * transactions. Whenever a block comes in, we count the number of transactions
  44. * in each bucket and the total amount of feerate paid in each bucket. Then we
  45. * calculate how many blocks Y it took each transaction to be mined. We convert
  46. * from a number of blocks to a number of periods Y' each encompassing "scale"
  47. * blocks. This is tracked in 3 different data sets each up to a maximum
  48. * number of periods. Within each data set we have an array of counters in each
  49. * feerate bucket and we increment all the counters from Y' up to max periods
  50. * representing that a tx was successfully confirmed in less than or equal to
  51. * that many periods. We want to save a history of this information, so at any
  52. * time we have a counter of the total number of transactions that happened in a
  53. * given feerate bucket and the total number that were confirmed in each of the
  54. * periods or less for any bucket. We save this history by keeping an
  55. * exponentially decaying moving average of each one of these stats. This is
  56. * done for a different decay in each of the 3 data sets to keep relevant data
  57. * from different time horizons. Furthermore we also keep track of the number
  58. * unmined (in mempool or left mempool without being included in a block)
  59. * transactions in each bucket and for how many blocks they have been
  60. * outstanding and use both of these numbers to increase the number of transactions
  61. * we've seen in that feerate bucket when calculating an estimate for any number
  62. * of confirmations below the number of blocks they've been outstanding.
  63. */
  64. /* Identifier for each of the 3 different TxConfirmStats which will track
  65. * history over different time horizons. */
  66. enum FeeEstimateHorizon {
  67. SHORT_HALFLIFE = 0,
  68. MED_HALFLIFE = 1,
  69. LONG_HALFLIFE = 2
  70. };
  71. std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);
  72. /* Enumeration of reason for returned fee estimate */
  73. enum class FeeReason {
  74. NONE,
  75. HALF_ESTIMATE,
  76. FULL_ESTIMATE,
  77. DOUBLE_ESTIMATE,
  78. CONSERVATIVE,
  79. MEMPOOL_MIN,
  80. PAYTXFEE,
  81. FALLBACK,
  82. REQUIRED,
  83. MAXTXFEE,
  84. };
  85. std::string StringForFeeReason(FeeReason reason);
  86. /* Used to determine type of fee estimation requested */
  87. enum class FeeEstimateMode {
  88. UNSET, //! Use default settings based on other criteria
  89. ECONOMICAL, //! Force estimateSmartFee to use non-conservative estimates
  90. CONSERVATIVE, //! Force estimateSmartFee to use conservative estimates
  91. };
  92. bool FeeModeFromString(const std::string& mode_string, FeeEstimateMode& fee_estimate_mode);
  93. /* Used to return detailed information about a feerate bucket */
  94. struct EstimatorBucket
  95. {
  96. double start = -1;
  97. double end = -1;
  98. double withinTarget = 0;
  99. double totalConfirmed = 0;
  100. double inMempool = 0;
  101. double leftMempool = 0;
  102. };
  103. /* Used to return detailed information about a fee estimate calculation */
  104. struct EstimationResult
  105. {
  106. EstimatorBucket pass;
  107. EstimatorBucket fail;
  108. double decay = 0;
  109. unsigned int scale = 0;
  110. };
  111. struct FeeCalculation
  112. {
  113. EstimationResult est;
  114. FeeReason reason = FeeReason::NONE;
  115. int desiredTarget = 0;
  116. int returnedTarget = 0;
  117. };
  118. /**
  119. * We want to be able to estimate feerates that are needed on tx's to be included in
  120. * a certain number of blocks. Every time a block is added to the best chain, this class records
  121. * stats on the transactions included in that block
  122. */
  123. class CBlockPolicyEstimator
  124. {
  125. private:
  126. /** Track confirm delays up to 12 blocks for short horizon */
  127. static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
  128. static constexpr unsigned int SHORT_SCALE = 1;
  129. /** Track confirm delays up to 48 blocks for medium horizon */
  130. static constexpr unsigned int MED_BLOCK_PERIODS = 24;
  131. static constexpr unsigned int MED_SCALE = 2;
  132. /** Track confirm delays up to 1008 blocks for long horizon */
  133. static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
  134. static constexpr unsigned int LONG_SCALE = 24;
  135. /** Historical estimates that are older than this aren't valid */
  136. static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
  137. /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
  138. static constexpr double SHORT_DECAY = .962;
  139. /** Decay of .998 is a half-life of 144 blocks or about 1 day */
  140. static constexpr double MED_DECAY = .9952;
  141. /** Decay of .9995 is a half-life of 1008 blocks or about 1 week */
  142. static constexpr double LONG_DECAY = .99931;
  143. /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
  144. static constexpr double HALF_SUCCESS_PCT = .6;
  145. /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
  146. static constexpr double SUCCESS_PCT = .85;
  147. /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
  148. static constexpr double DOUBLE_SUCCESS_PCT = .95;
  149. /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
  150. static constexpr double SUFFICIENT_FEETXS = 0.1;
  151. /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
  152. static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
  153. /** Minimum and Maximum values for tracking feerates
  154. * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
  155. * might ever want to track. Historically this has been 1000 since it was
  156. * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
  157. * invalidates old estimates files. So leave it at 1000 unless it becomes
  158. * necessary to lower it, and then lower it substantially.
  159. */
  160. static constexpr double MIN_BUCKET_FEERATE = 1000;
  161. static constexpr double MAX_BUCKET_FEERATE = 1e7;
  162. /** Spacing of FeeRate buckets
  163. * We have to lump transactions into buckets based on feerate, but we want to be able
  164. * to give accurate estimates over a large range of potential feerates
  165. * Therefore it makes sense to exponentially space the buckets
  166. */
  167. static constexpr double FEE_SPACING = 1.05;
  168. public:
  169. /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
  170. CBlockPolicyEstimator();
  171. ~CBlockPolicyEstimator();
  172. /** Process all the transactions that have been included in a block */
  173. void processBlock(unsigned int nBlockHeight,
  174. std::vector<const CTxMemPoolEntry*>& entries);
  175. /** Process a transaction accepted to the mempool*/
  176. void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate);
  177. /** Remove a transaction from the mempool tracking stats*/
  178. bool removeTx(uint256 hash, bool inBlock);
  179. /** DEPRECATED. Return a feerate estimate */
  180. CFeeRate estimateFee(int confTarget) const;
  181. /** Estimate feerate needed to get be included in a block within confTarget
  182. * blocks. If no answer can be given at confTarget, return an estimate at
  183. * the closest target where one can be given. 'conservative' estimates are
  184. * valid over longer time horizons also.
  185. */
  186. CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const;
  187. /** Return a specific fee estimate calculation with a given success
  188. * threshold and time horizon, and optionally return detailed data about
  189. * calculation
  190. */
  191. CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult *result = nullptr) const;
  192. /** Write estimation data to a file */
  193. bool Write(CAutoFile& fileout) const;
  194. /** Read estimation data from a file */
  195. bool Read(CAutoFile& filein);
  196. /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
  197. void FlushUnconfirmed(CTxMemPool& pool);
  198. /** Calculation of highest target that estimates are tracked for */
  199. unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const;
  200. private:
  201. unsigned int nBestSeenHeight;
  202. unsigned int firstRecordedHeight;
  203. unsigned int historicalFirst;
  204. unsigned int historicalBest;
  205. struct TxStatsInfo
  206. {
  207. unsigned int blockHeight;
  208. unsigned int bucketIndex;
  209. TxStatsInfo() : blockHeight(0), bucketIndex(0) {}
  210. };
  211. // map of txids to information about that transaction
  212. std::map<uint256, TxStatsInfo> mapMemPoolTxs;
  213. /** Classes to track historical data on transaction confirmations */
  214. TxConfirmStats* feeStats;
  215. TxConfirmStats* shortStats;
  216. TxConfirmStats* longStats;
  217. unsigned int trackedTxs;
  218. unsigned int untrackedTxs;
  219. std::vector<double> buckets; // The upper-bound of the range for the bucket (inclusive)
  220. std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
  221. mutable CCriticalSection cs_feeEstimator;
  222. /** Process a transaction confirmed in a block*/
  223. bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry);
  224. /** Helper for estimateSmartFee */
  225. double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const;
  226. /** Helper for estimateSmartFee */
  227. double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const;
  228. /** Number of blocks of data recorded while fee estimates have been running */
  229. unsigned int BlockSpan() const;
  230. /** Number of blocks of recorded fee estimate data represented in saved data file */
  231. unsigned int HistoricalBlockSpan() const;
  232. /** Calculation of highest target that reasonable estimate can be provided for */
  233. unsigned int MaxUsableEstimate() const;
  234. };
  235. class FeeFilterRounder
  236. {
  237. private:
  238. static constexpr double MAX_FILTER_FEERATE = 1e7;
  239. /** FEE_FILTER_SPACING is just used to provide some quantization of fee
  240. * filter results. Historically it reused FEE_SPACING, but it is completely
  241. * unrelated, and was made a separate constant so the two concepts are not
  242. * tied together */
  243. static constexpr double FEE_FILTER_SPACING = 1.1;
  244. public:
  245. /** Create new FeeFilterRounder */
  246. FeeFilterRounder(const CFeeRate& minIncrementalFee);
  247. /** Quantize a minimum fee for privacy purpose before broadcast **/
  248. CAmount round(CAmount currentMinFee);
  249. private:
  250. std::set<double> feeset;
  251. FastRandomContext insecure_rand;
  252. };
  253. #endif /*STARWELS_POLICYESTIMATOR_H */