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