1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-present The Bitcoin Core 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 BITCOIN_POLICY_FEES_BLOCK_POLICY_ESTIMATOR_H
  6  #define BITCOIN_POLICY_FEES_BLOCK_POLICY_ESTIMATOR_H
  7  
  8  #include <consensus/amount.h>
  9  #include <policy/feerate.h>
 10  #include <random.h>
 11  #include <sync.h>
 12  #include <uint256.h>
 13  #include <util/fs.h>
 14  #include <validationinterface.h>
 15  
 16  #include <array>
 17  #include <chrono>
 18  #include <map>
 19  #include <memory>
 20  #include <set>
 21  #include <string>
 22  #include <vector>
 23  
 24  
 25  // How often to flush fee estimates to fee_estimates.dat.
 26  static constexpr std::chrono::hours FEE_FLUSH_INTERVAL{1};
 27  
 28  /** fee_estimates.dat that are more than 60 hours (2.5 days) old will not be read,
 29   * as fee estimates are based on historical data and may be inaccurate if
 30   * network activity has changed.
 31   */
 32  static constexpr std::chrono::hours MAX_FILE_AGE{60};
 33  
 34  // Whether we allow importing a fee_estimates file older than MAX_FILE_AGE.
 35  static constexpr bool DEFAULT_ACCEPT_STALE_FEE_ESTIMATES{false};
 36  
 37  class AutoFile;
 38  class TxConfirmStats;
 39  struct RemovedMempoolTransactionInfo;
 40  struct NewMempoolTransactionInfo;
 41  
 42  /* Identifier for each of the 3 different TxConfirmStats which will track
 43   * history over different time horizons. */
 44  enum class FeeEstimateHorizon {
 45      SHORT_HALFLIFE,
 46      MED_HALFLIFE,
 47      LONG_HALFLIFE,
 48  };
 49  
 50  static constexpr auto ALL_FEE_ESTIMATE_HORIZONS = std::array{
 51      FeeEstimateHorizon::SHORT_HALFLIFE,
 52      FeeEstimateHorizon::MED_HALFLIFE,
 53      FeeEstimateHorizon::LONG_HALFLIFE,
 54  };
 55  
 56  std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);
 57  
 58  /* Enumeration of reason for returned fee estimate */
 59  enum class FeeReason {
 60      NONE,
 61      HALF_ESTIMATE,
 62      FULL_ESTIMATE,
 63      DOUBLE_ESTIMATE,
 64      CONSERVATIVE,
 65      MEMPOOL_MIN,
 66      FALLBACK,
 67      REQUIRED,
 68  };
 69  
 70  /* Used to return detailed information about a feerate bucket */
 71  struct EstimatorBucket
 72  {
 73      double start = -1;
 74      double end = -1;
 75      double withinTarget = 0;
 76      double totalConfirmed = 0;
 77      double inMempool = 0;
 78      double leftMempool = 0;
 79  };
 80  
 81  /* Used to return detailed information about a fee estimate calculation */
 82  struct EstimationResult
 83  {
 84      EstimatorBucket pass;
 85      EstimatorBucket fail;
 86      double decay = 0;
 87      unsigned int scale = 0;
 88  };
 89  
 90  struct FeeCalculation
 91  {
 92      EstimationResult est;
 93      FeeReason reason = FeeReason::NONE;
 94      int desiredTarget = 0;
 95      int returnedTarget = 0;
 96      unsigned int best_height{0};
 97  };
 98  
 99  /** \class CBlockPolicyEstimator
100   * The BlockPolicyEstimator is used for estimating the feerate needed
101   * for a transaction to be included in a block within a certain number of
102   * blocks.
103   *
104   * At a high level the algorithm works by grouping transactions into buckets
105   * based on having similar feerates and then tracking how long it
106   * takes transactions in the various buckets to be mined.  It operates under
107   * the assumption that in general transactions of higher feerate will be
108   * included in blocks before transactions of lower feerate.   So for
109   * example if you wanted to know what feerate you should put on a transaction to
110   * be included in a block within the next 5 blocks, you would start by looking
111   * at the bucket with the highest feerate transactions and verifying that a
112   * sufficiently high percentage of them were confirmed within 5 blocks and
113   * then you would look at the next highest feerate bucket, and so on, stopping at
114   * the last bucket to pass the test.   The average feerate of transactions in this
115   * bucket will give you an indication of the lowest feerate you can put on a
116   * transaction and still have a sufficiently high chance of being confirmed
117   * within your desired 5 blocks.
118   *
119   * Here is a brief description of the implementation:
120   * When a transaction enters the mempool, we track the height of the block chain
121   * at entry.  All further calculations are conducted only on this set of "seen"
122   * transactions. Whenever a block comes in, we count the number of transactions
123   * in each bucket and the total amount of feerate paid in each bucket. Then we
124   * calculate how many blocks Y it took each transaction to be mined.  We convert
125   * from a number of blocks to a number of periods Y' each encompassing "scale"
126   * blocks.  This is tracked in 3 different data sets each up to a maximum
127   * number of periods. Within each data set we have an array of counters in each
128   * feerate bucket and we increment all the counters from Y' up to max periods
129   * representing that a tx was successfully confirmed in less than or equal to
130   * that many periods. We want to save a history of this information, so at any
131   * time we have a counter of the total number of transactions that happened in a
132   * given feerate bucket and the total number that were confirmed in each of the
133   * periods or less for any bucket.  We save this history by keeping an
134   * exponentially decaying moving average of each one of these stats.  This is
135   * done for a different decay in each of the 3 data sets to keep relevant data
136   * from different time horizons.  Furthermore we also keep track of the number
137   * unmined (in mempool or left mempool without being included in a block)
138   * transactions in each bucket and for how many blocks they have been
139   * outstanding and use both of these numbers to increase the number of transactions
140   * we've seen in that feerate bucket when calculating an estimate for any number
141   * of confirmations below the number of blocks they've been outstanding.
142   *
143   *  We want to be able to estimate feerates that are needed on tx's to be included in
144   * a certain number of blocks.  Every time a block is added to the best chain, this class records
145   * stats on the transactions included in that block
146   */
147  class CBlockPolicyEstimator : public CValidationInterface
148  {
149  private:
150      /** Track confirm delays up to 12 blocks for short horizon */
151      static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
152      static constexpr unsigned int SHORT_SCALE = 1;
153      /** Track confirm delays up to 48 blocks for medium horizon */
154      static constexpr unsigned int MED_BLOCK_PERIODS = 24;
155      static constexpr unsigned int MED_SCALE = 2;
156      /** Track confirm delays up to 1008 blocks for long horizon */
157      static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
158      static constexpr unsigned int LONG_SCALE = 24;
159      /** Historical estimates that are older than this aren't valid */
160      static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
161  
162      /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
163      static constexpr double SHORT_DECAY = .962;
164      /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
165      static constexpr double MED_DECAY = .9952;
166      /** Decay of .99931 is a half-life of 1008 blocks or about 1 week */
167      static constexpr double LONG_DECAY = .99931;
168  
169      /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
170      static constexpr double HALF_SUCCESS_PCT = .6;
171      /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
172      static constexpr double SUCCESS_PCT = .85;
173      /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
174      static constexpr double DOUBLE_SUCCESS_PCT = .95;
175  
176      /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
177      static constexpr double SUFFICIENT_FEETXS = 0.1;
178      /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
179      static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
180  
181      /** Minimum and Maximum values for tracking feerates
182       * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate.
183       * MIN_BUCKET_FEERATE has historically inherited DEFAULT_MIN_RELAY_TX_FEE.
184       * It is hardcoded because changing it is disruptive, as it invalidates existing fee
185       * estimate files.
186       *
187       * Whenever DEFAULT_MIN_RELAY_TX_FEE changes, this value should be updated
188       * accordingly. At the same time CURRENT_FEES_FILE_VERSION should be bumped.
189       */
190      static constexpr double MIN_BUCKET_FEERATE = 100;
191      static constexpr double MAX_BUCKET_FEERATE = 1e7;
192  
193      /** Spacing of FeeRate buckets
194       * We have to lump transactions into buckets based on feerate, but we want to be able
195       * to give accurate estimates over a large range of potential feerates
196       * Therefore it makes sense to exponentially space the buckets
197       */
198      static constexpr double FEE_SPACING = 1.05;
199  
200      const fs::path m_estimation_filepath;
201  public:
202      /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
203      CBlockPolicyEstimator(const fs::path& estimation_filepath, bool read_stale_estimates);
204      virtual ~CBlockPolicyEstimator();
205  
206      /** Process all the transactions that have been included in a block */
207      void processBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block,
208                        unsigned int nBlockHeight)
209          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
210  
211      /** Process a transaction accepted to the mempool*/
212      void processTransaction(const NewMempoolTransactionInfo& tx)
213          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
214  
215      /** Remove a transaction from the mempool tracking stats for non BLOCK removal reasons*/
216      bool removeTx(Txid hash)
217          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
218  
219      /** DEPRECATED. Return a feerate estimate */
220      CFeeRate estimateFee(int confTarget) const
221          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
222  
223      /** Estimate feerate needed to get be included in a block within confTarget
224       *  blocks. If no answer can be given at confTarget, return an estimate at
225       *  the closest target where one can be given.  'conservative' estimates are
226       *  valid over longer time horizons also.
227       */
228      virtual CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
229          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
230  
231      /** Return a specific fee estimate calculation with a given success
232       * threshold and time horizon, and optionally return detailed data about
233       * calculation
234       */
235      CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon,
236                              EstimationResult* result = nullptr) const
237          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
238  
239      /** Write estimation data to a file */
240      bool Write(AutoFile& fileout) const
241          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
242  
243      /** Read estimation data from a file */
244      bool Read(AutoFile& filein)
245          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
246  
247      /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
248      void FlushUnconfirmed()
249          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
250  
251      /** Calculation of highest target that estimates are tracked for */
252      virtual unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
253          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
254  
255      /** Drop still unconfirmed transactions and record current estimations, if the fee estimation file is present. */
256      void Flush()
257          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
258  
259      /** Record current fee estimations. */
260      void FlushFeeEstimates()
261          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
262  
263      /** Calculates the age of the file, since last modified */
264      std::chrono::hours GetFeeEstimatorFileAge();
265  
266  protected:
267      /** Overridden from CValidationInterface. */
268      void TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /*unused*/) override
269          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
270      void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason /*unused*/, uint64_t /*unused*/) override
271          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
272      void MempoolTransactionsRemovedForBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block, unsigned int nBlockHeight) override
273          EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
274  
275  private:
276      mutable Mutex m_cs_fee_estimator;
277  
278      unsigned int nBestSeenHeight GUARDED_BY(m_cs_fee_estimator){0};
279      unsigned int firstRecordedHeight GUARDED_BY(m_cs_fee_estimator){0};
280      unsigned int historicalFirst GUARDED_BY(m_cs_fee_estimator){0};
281      unsigned int historicalBest GUARDED_BY(m_cs_fee_estimator){0};
282  
283      struct TxStatsInfo
284      {
285          unsigned int blockHeight{0};
286          unsigned int bucketIndex{0};
287          TxStatsInfo() = default;
288      };
289  
290      // map of txids to information about that transaction
291      std::map<Txid, TxStatsInfo> mapMemPoolTxs GUARDED_BY(m_cs_fee_estimator);
292  
293      /** Classes to track historical data on transaction confirmations */
294      std::unique_ptr<TxConfirmStats> feeStats PT_GUARDED_BY(m_cs_fee_estimator);
295      std::unique_ptr<TxConfirmStats> shortStats PT_GUARDED_BY(m_cs_fee_estimator);
296      std::unique_ptr<TxConfirmStats> longStats PT_GUARDED_BY(m_cs_fee_estimator);
297  
298      unsigned int trackedTxs GUARDED_BY(m_cs_fee_estimator){0};
299      unsigned int untrackedTxs GUARDED_BY(m_cs_fee_estimator){0};
300  
301      std::vector<double> buckets GUARDED_BY(m_cs_fee_estimator); // The upper-bound of the range for the bucket (inclusive)
302      std::map<double, unsigned int> bucketMap GUARDED_BY(m_cs_fee_estimator); // Map of bucket upper-bound to index into all vectors by bucket
303  
304      /** Process a transaction confirmed in a block*/
305      bool processBlockTx(unsigned int nBlockHeight, const RemovedMempoolTransactionInfo& tx) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
306  
307      /** Helper for estimateSmartFee */
308      double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
309      /** Helper for estimateSmartFee */
310      double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
311      /** Number of blocks of data recorded while fee estimates have been running */
312      unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
313      /** Number of blocks of recorded fee estimate data represented in saved data file */
314      unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
315      /** Calculation of highest target that reasonable estimate can be provided for */
316      unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
317  
318      /** A non-thread-safe helper for the removeTx function */
319      bool _removeTx(const Txid& hash, bool inBlock)
320          EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
321  };
322  
323  class FeeFilterRounder
324  {
325  private:
326      static constexpr double MAX_FILTER_FEERATE = 1e7;
327      /** FEE_FILTER_SPACING is just used to provide some quantization of fee
328       * filter results.  Historically it reused FEE_SPACING, but it is completely
329       * unrelated, and was made a separate constant so the two concepts are not
330       * tied together */
331      static constexpr double FEE_FILTER_SPACING = 1.1;
332  
333  public:
334      /** Create new FeeFilterRounder */
335      explicit FeeFilterRounder(const CFeeRate& min_incremental_fee, FastRandomContext& rng);
336  
337      /** Quantize a minimum fee for privacy purpose before broadcast. */
338      CAmount round(CAmount currentMinFee) EXCLUSIVE_LOCKS_REQUIRED(!m_insecure_rand_mutex);
339  
340  private:
341      const std::set<double> m_fee_set;
342      Mutex m_insecure_rand_mutex;
343      FastRandomContext& insecure_rand GUARDED_BY(m_insecure_rand_mutex);
344  };
345  
346  #endif // BITCOIN_POLICY_FEES_BLOCK_POLICY_ESTIMATOR_H