1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2022 The Limenka 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 LIMENKA_POLICY_FEES_H
6 #define LIMENKA_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 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 public:
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 private:
161 /** Historical estimates that are older than this aren't valid */
162 static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
163 164 /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
165 static constexpr double SHORT_DECAY = .962;
166 /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
167 static constexpr double MED_DECAY = .9952;
168 /** Decay of .99931 is a half-life of 1008 blocks or about 1 week */
169 static constexpr double LONG_DECAY = .99931;
170 171 /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
172 static constexpr double HALF_SUCCESS_PCT = .6;
173 /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
174 static constexpr double SUCCESS_PCT = .85;
175 /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
176 static constexpr double DOUBLE_SUCCESS_PCT = .95;
177 178 /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
179 static constexpr double SUFFICIENT_FEETXS = 0.1;
180 /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
181 static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
182 183 /** Minimum and Maximum values for tracking feerates
184 * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
185 * might ever want to track. Historically this has been 1000 since it was
186 * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
187 * invalidates old estimates files. So leave it at 1000 unless it becomes
188 * necessary to lower it, and then lower it substantially.
189 */
190 static constexpr double MIN_BUCKET_FEERATE = 1000;
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, const 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(uint256 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 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 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 bool FlushFeeEstimates() const
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<uint256, 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 uint256& 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 // LIMENKA_POLICY_FEES_H
347