1// Copyright (c) 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#ifndef BITCOIN_POLICY_FEES_MEMPOOL_ESTIMATOR_H
6#define BITCOIN_POLICY_FEES_MEMPOOL_ESTIMATOR_H
7
8#include <primitives/transaction.h>
9#include <sync.h>
10#include <threadsafety.h>
11#include <uint256.h>
12#include <util/expected.h>
13#include <util/feefrac.h>
14#include <util/fees.h>
15#include <util/fs.h>
16#include <util/time.h>
17
18#include <chrono>
19#include <memory>
20#include <optional>
21#include <span>
22#include <vector>
23
24class CBlock;
25class AutoFile;
26class ChainstateManager;
27class CTxMemPool;
28
29struct RemovedMempoolTransactionInfo;
30
31// Fee rate estimate for confirmation target above this is not reliable,
32// as mempool conditions are likely to change.
33constexpr int MEMPOOL_FEE_ESTIMATOR_MAX_TARGET{2};
34constexpr std::chrono::seconds CACHE_LIFE{7};
35
36// Constants for mempool sanity checks.
37constexpr size_t MEMPOOL_HEALTH_WINDOW_BLOCKS = 6;
38constexpr double MEMPOOL_REPRESENTATION_THRESHOLD = 0.75;
39
40//! Weight statistics for a recently mined block, used to assess mempool coverage.
41struct MinedBlockStats {
42    //! Block height.
43    uint64_t m_height{0};
44    //! Weight of mempool transactions removed for this block (excluding coinbase).
45    uint64_t m_removed_block_txs_weight{0};
46    //! Total non-coinbase transaction weight in the block.
47    uint64_t m_block_weight{0};
48};
49
50/**
51 * MemPoolFeeRateEstimatorCache holds a cache of recent fee rate estimates.
52 * A cached fee rate is only provided while it is not older than CACHE_LIFE
53 * and the chain tip has not changed.
54 */
55class MemPoolFeeRateEstimatorCache
56{
57public:
58    MemPoolFeeRateEstimatorCache() = default;
59    MemPoolFeeRateEstimatorCache(const MemPoolFeeRateEstimatorCache&) = delete;
60    MemPoolFeeRateEstimatorCache& operator=(const MemPoolFeeRateEstimatorCache&) = delete;
61    /** Returns true if the cache is empty or older than CACHE_LIFE. */
62    bool IsStale() const;
63    struct FeeRateEstimate {
64        FeePerVSize m_conservative;
65        FeePerVSize m_economical;
66    };
67    /** Returns cached estimates if not stale and computed on tip_hash, nullopt otherwise. */
68    std::optional<FeeRateEstimate> GetCachedEstimate(const uint256& tip_hash) const;
69    /** Update the cache with new estimates computed on tip_hash. */
70    void Update(FeePerVSize conservative, FeePerVSize economical, const uint256& tip_hash);
71    /** Clear cached fee rate estimates. */
72    void Clear();
73
74private:
75    std::optional<FeeRateEstimate> m_fee_rate_estimation;
76    uint256 m_tip_hash;
77    NodeClock::time_point m_last_updated{};
78};
79
80/**
81 * Estimate the fee rate required for a transaction to be included in the next block.
82 *
83 * Uses Bitcoin Core's block-building algorithm to generate a block template from the mempool,
84 * then calculates percentile fee rates from the selected chunks: the 75th percentile is returned
85 * as the economical estimate and the 50th percentile as the conservative estimate.
86 */
87class MemPoolFeeRateEstimator
88{
89public:
90    // Block percentiles fee rate (in sat/vB).
91    struct Percentiles {
92        FeePerVSize p50;
93        FeePerVSize p75;
94    };
95
96    MemPoolFeeRateEstimator(fs::path mempool_estimator_file_path,
97                            const CTxMemPool& mempool,
98                            ChainstateManager& chainman);
99    ~MemPoolFeeRateEstimator() = default;
100    /**
101     * Calculate the 50th and 75th percentile fee rates from block template chunks,
102     * sorted in descending mining-score order. A percentile is left empty when the
103     * chunks cannot cover the corresponding fraction of a block.
104     *
105     * @param[in] chunk_feerates Block template chunk fee rates sorted by descending mining score.
106     */
107    static Percentiles CalculateMaxWeightPercentiles(std::span<const FeePerVSize> chunk_feerates);
108    util::Expected<FeeRateEstimation, FeeRateEstimationError> EstimateFeeRate(bool conservative) const
109        EXCLUSIVE_LOCKS_REQUIRED(!cs);
110    unsigned int MaximumTarget() const
111    {
112        return MEMPOOL_FEE_ESTIMATOR_MAX_TARGET;
113    }
114
115    std::vector<MinedBlockStats> GetPrevBlockData() const EXCLUSIVE_LOCKS_REQUIRED(!cs)
116    {
117        LOCK(cs);
118        return m_prev_mined_blocks;
119    }
120
121    void MempoolTxsRemovedForBlock(const std::shared_ptr<const CBlock>& block,
122                                   const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block,
123                                   unsigned int block_height)
124        EXCLUSIVE_LOCKS_REQUIRED(!cs);
125    //! Health of the recent mined-block window for fee rate estimation.
126    enum class MempoolHealth {
127        //! Recent blocks represent the mempool well enough to estimate a fee rate.
128        HEALTHY,
129        //! Too few recent mined blocks to estimate a fee rate.
130        INSUFFICIENT_DATA,
131        //! Recent blocks include too few mempool transactions to estimate a fee rate.
132        LOW_COVERAGE,
133    };
134    MempoolHealth GetMempoolHealth() const EXCLUSIVE_LOCKS_REQUIRED(!cs);
135    //! Checks if recent mined blocks indicate a healthy mempool state.
136    bool IsMempoolHealthy() const EXCLUSIVE_LOCKS_REQUIRED(!cs) { return GetMempoolHealth() == MempoolHealth::HEALTHY; }
137    void FlushMinedBlockStats() EXCLUSIVE_LOCKS_REQUIRED(!cs);
138    void MempoolLoadFailed() EXCLUSIVE_LOCKS_REQUIRED(!cs);
139    //! Deserialize mined-block stats without taking ownership of file.
140    bool Read(AutoFile& file) EXCLUSIVE_LOCKS_REQUIRED(!cs);
141    //! Serialize mined-block stats without taking ownership of file.
142    //! Callers must explicitly close file and check for errors after writing.
143    bool Write(AutoFile& file) const EXCLUSIVE_LOCKS_REQUIRED(!cs);
144
145private:
146    void ReadFromDisk() EXCLUSIVE_LOCKS_REQUIRED(!cs);
147    //! Tracks weight statistics for the last MEMPOOL_HEALTH_WINDOW_BLOCKS mined blocks.
148    std::vector<MinedBlockStats> m_prev_mined_blocks GUARDED_BY(cs);
149    uint256 m_mined_blocks_tip_hash GUARDED_BY(cs);
150
151    const CTxMemPool& m_mempool;
152    ChainstateManager& m_chainman;
153    mutable Mutex cs;
154    mutable MemPoolFeeRateEstimatorCache m_cache GUARDED_BY(cs);
155    const fs::path m_mempool_estimator_file_path;
156};
157
158#endif // BITCOIN_POLICY_FEES_MEMPOOL_ESTIMATOR_H
159