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 : :
6 : : #include <policy/fees.h>
7 : :
8 : : #include <clientversion.h>
9 : : #include <common/system.h>
10 : : #include <consensus/amount.h>
11 : : #include <kernel/mempool_entry.h>
12 : : #include <logging.h>
13 : : #include <policy/feerate.h>
14 : : #include <primitives/transaction.h>
15 : : #include <random.h>
16 : : #include <serialize.h>
17 : : #include <streams.h>
18 : : #include <sync.h>
19 : : #include <tinyformat.h>
20 : : #include <uint256.h>
21 : : #include <util/fs.h>
22 : : #include <util/serfloat.h>
23 : : #include <util/time.h>
24 : :
25 : : #include <algorithm>
26 : : #include <cassert>
27 : : #include <chrono>
28 : : #include <cmath>
29 : : #include <cstddef>
30 : : #include <cstdint>
31 : : #include <exception>
32 : : #include <stdexcept>
33 : : #include <utility>
34 : :
35 : : static constexpr double INF_FEERATE = 1e99;
36 : :
37 : 92 : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
38 : : {
39 [ - + + + ]: 92 : switch (horizon) {
40 [ + - ]: 42 : case FeeEstimateHorizon::SHORT_HALFLIFE: return "short";
41 [ + - ]: 18 : case FeeEstimateHorizon::MED_HALFLIFE: return "medium";
42 [ + - ]: 32 : case FeeEstimateHorizon::LONG_HALFLIFE: return "long";
43 : : } // no default case, so the compiler can warn about missing cases
44 : 0 : assert(false);
45 : 92 : }
46 : :
47 : : namespace {
48 : :
49 : : struct EncodedDoubleFormatter
50 : : {
51 : 905520 : template<typename Stream> void Ser(Stream &s, double v)
52 : : {
53 : 905520 : s << EncodeDouble(v);
54 : 905520 : }
55 : :
56 : 1966562 : template<typename Stream> void Unser(Stream& s, double& v)
57 : : {
58 : 1966562 : uint64_t encoded;
59 : 1966562 : s >> encoded;
60 : 1966562 : v = DecodeDouble(encoded);
61 : 1966562 : }
62 : : };
63 : :
64 : : } // namespace
65 : :
66 : : /**
67 : : * We will instantiate an instance of this class to track transactions that were
68 : : * included in a block. We will lump transactions into a bucket according to their
69 : : * approximate feerate and then track how long it took for those txs to be included in a block
70 : : *
71 : : * The tracking of unconfirmed (mempool) transactions is completely independent of the
72 : : * historical tracking of transactions that have been confirmed in a block.
73 : : */
74 : : class TxConfirmStats
75 : : {
76 : : private:
77 : : //Define the buckets we will group transactions into
78 : : const std::vector<double>& buckets; // The upper-bound of the range for the bucket (inclusive)
79 : : const std::map<double, unsigned int>& bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
80 : :
81 : : // For each bucket X:
82 : : // Count the total # of txs in each bucket
83 : : // Track the historical moving average of this total over blocks
84 : : std::vector<double> txCtAvg;
85 : :
86 : : // Count the total # of txs confirmed within Y blocks in each bucket
87 : : // Track the historical moving average of these totals over blocks
88 : : std::vector<std::vector<double>> confAvg; // confAvg[Y][X]
89 : :
90 : : // Track moving avg of txs which have been evicted from the mempool
91 : : // after failing to be confirmed within Y blocks
92 : : std::vector<std::vector<double>> failAvg; // failAvg[Y][X]
93 : :
94 : : // Sum the total feerate of all tx's in each bucket
95 : : // Track the historical moving average of this total over blocks
96 : : std::vector<double> m_feerate_avg;
97 : :
98 : : // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
99 : : // Combine the total value with the tx counts to calculate the avg feerate per bucket
100 : :
101 : : double decay;
102 : :
103 : : // Resolution (# of blocks) with which confirmations are tracked
104 : : unsigned int scale;
105 : :
106 : : // Mempool counts of outstanding transactions
107 : : // For each bucket X, track the number of transactions in the mempool
108 : : // that are unconfirmed for each possible confirmation value Y
109 : : std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
110 : : // transactions still unconfirmed after GetMaxConfirms for each bucket
111 : : std::vector<int> oldUnconfTxs;
112 : :
113 : : void resizeInMemoryCounters(size_t newbuckets);
114 : :
115 : : public:
116 : : /**
117 : : * Create new TxConfirmStats. This is called by BlockPolicyEstimator's
118 : : * constructor with default values.
119 : : * @param defaultBuckets contains the upper limits for the bucket boundaries
120 : : * @param maxPeriods max number of periods to track
121 : : * @param decay how much to decay the historical moving average per block
122 : : */
123 : : TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,
124 : : unsigned int maxPeriods, double decay, unsigned int scale);
125 : :
126 : : /** Roll the circular buffer for unconfirmed txs*/
127 : : void ClearCurrent(unsigned int nBlockHeight);
128 : :
129 : : /**
130 : : * Record a new transaction data point in the current block stats
131 : : * @param blocksToConfirm the number of blocks it took this transaction to confirm
132 : : * @param val the feerate of the transaction
133 : : * @warning blocksToConfirm is 1-based and has to be >= 1
134 : : */
135 : : void Record(int blocksToConfirm, double val);
136 : :
137 : : /** Record a new transaction entering the mempool*/
138 : : unsigned int NewTx(unsigned int nBlockHeight, double val);
139 : :
140 : : /** Remove a transaction from mempool tracking stats*/
141 : : void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
142 : : unsigned int bucketIndex, bool inBlock);
143 : :
144 : : /** Update our estimates by decaying our historical moving average and updating
145 : : with the data gathered from the current block */
146 : : void UpdateMovingAverages();
147 : :
148 : : /**
149 : : * Calculate a feerate estimate. Find the lowest value bucket (or range of buckets
150 : : * to make sure we have enough data points) whose transactions still have sufficient likelihood
151 : : * of being confirmed within the target number of confirmations
152 : : * @param confTarget target number of confirmations
153 : : * @param sufficientTxVal required average number of transactions per block in a bucket range
154 : : * @param minSuccess the success probability we require
155 : : * @param nBlockHeight the current block height
156 : : */
157 : : double EstimateMedianVal(int confTarget, double sufficientTxVal,
158 : : double minSuccess, unsigned int nBlockHeight,
159 : : EstimationResult *result = nullptr) const;
160 : :
161 : : /** Return the max number of confirms we're tracking */
162 : 754062675 : unsigned int GetMaxConfirms() const { return scale * confAvg.size(); }
163 : :
164 : : /** Write state of estimation data to a file*/
165 : : void Write(AutoFile& fileout) const;
166 : :
167 : : /**
168 : : * Read saved state of estimation data from a file and replace all internal data structures and
169 : : * variables with this state.
170 : : */
171 : : void Read(AutoFile& filein, int nFileVersion, size_t numBuckets);
172 : : };
173 : :
174 : :
175 : 15939 : TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
176 : : const std::map<double, unsigned int>& defaultBucketMap,
177 : : unsigned int maxPeriods, double _decay, unsigned int _scale)
178 : 10626 : : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_scale)
179 : : {
180 [ - + + - ]: 10626 : assert(_scale != 0 && "_scale must be non-zero");
181 [ + - ]: 5313 : confAvg.resize(maxPeriods);
182 [ + - ]: 5313 : failAvg.resize(maxPeriods);
183 [ + + ]: 143451 : for (unsigned int i = 0; i < maxPeriods; i++) {
184 [ + - ]: 138138 : confAvg[i].resize(buckets.size());
185 [ + - ]: 138138 : failAvg[i].resize(buckets.size());
186 : 138138 : }
187 : :
188 [ + - ]: 5313 : txCtAvg.resize(buckets.size());
189 [ + - ]: 5313 : m_feerate_avg.resize(buckets.size());
190 : :
191 [ + - ]: 5313 : resizeInMemoryCounters(buckets.size());
192 : 5313 : }
193 : :
194 : 5854 : void TxConfirmStats::resizeInMemoryCounters(size_t newbuckets) {
195 : : // newbuckets must be passed in because the buckets referred to during Read have not been updated yet.
196 : 5854 : unconfTxs.resize(GetMaxConfirms());
197 [ + + ]: 2035018 : for (unsigned int i = 0; i < unconfTxs.size(); i++) {
198 : 2029164 : unconfTxs[i].resize(newbuckets);
199 : 2029164 : }
200 : 5854 : oldUnconfTxs.resize(newbuckets);
201 : 5854 : }
202 : :
203 : : // Roll the unconfirmed txs circular buffer
204 : 2973 : void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
205 : : {
206 [ + + ]: 567843 : for (unsigned int j = 0; j < buckets.size(); j++) {
207 : 564870 : oldUnconfTxs[j] += unconfTxs[nBlockHeight % unconfTxs.size()][j];
208 : 564870 : unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
209 : 564870 : }
210 : 2973 : }
211 : :
212 : :
213 : 4125 : void TxConfirmStats::Record(int blocksToConfirm, double feerate)
214 : : {
215 : : // blocksToConfirm is 1-based
216 [ + - ]: 4125 : if (blocksToConfirm < 1)
217 : 0 : return;
218 : 4125 : int periodsToConfirm = (blocksToConfirm + scale - 1) / scale;
219 : 4125 : unsigned int bucketindex = bucketMap.lower_bound(feerate)->second;
220 [ + + ]: 13600 : for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
221 : 9475 : confAvg[i - 1][bucketindex]++;
222 : 9475 : }
223 : 4125 : txCtAvg[bucketindex]++;
224 : 4125 : m_feerate_avg[bucketindex] += feerate;
225 : 4125 : }
226 : :
227 : 2973 : void TxConfirmStats::UpdateMovingAverages()
228 : : {
229 [ + - ]: 2973 : assert(confAvg.size() == failAvg.size());
230 [ + + ]: 567843 : for (unsigned int j = 0; j < buckets.size(); j++) {
231 [ + + ]: 15251490 : for (unsigned int i = 0; i < confAvg.size(); i++) {
232 : 14686620 : confAvg[i][j] *= decay;
233 : 14686620 : failAvg[i][j] *= decay;
234 : 14686620 : }
235 : 564870 : m_feerate_avg[j] *= decay;
236 : 564870 : txCtAvg[j] *= decay;
237 : 564870 : }
238 : 2973 : }
239 : :
240 : : // returns -1 on error conditions
241 : 18228 : double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
242 : : double successBreakPoint, unsigned int nBlockHeight,
243 : : EstimationResult *result) const
244 : : {
245 : : // Counters for a bucket (or range of buckets)
246 : 18228 : double nConf = 0; // Number of tx's confirmed within the confTarget
247 : 18228 : double totalNum = 0; // Total number of tx's that were ever confirmed
248 : 18228 : int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
249 : 18228 : double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
250 : 18228 : const int periodTarget = (confTarget + scale - 1) / scale;
251 : 18228 : const int maxbucketindex = buckets.size() - 1;
252 : :
253 : : // We'll combine buckets until we have enough samples.
254 : : // The near and far variables will define the range we've combined
255 : : // The best variables are the last range we saw which still had a high
256 : : // enough confirmation rate to count as success.
257 : : // The cur variables are the current range we're counting.
258 : 18228 : unsigned int curNearBucket = maxbucketindex;
259 : 18228 : unsigned int bestNearBucket = maxbucketindex;
260 : 18228 : unsigned int curFarBucket = maxbucketindex;
261 : 18228 : unsigned int bestFarBucket = maxbucketindex;
262 : :
263 : : // We'll always group buckets into sets that meet sufficientTxVal --
264 : : // this ensures that we're using consistent groups between different
265 : : // confirmation targets.
266 : 18228 : double partialNum = 0;
267 : :
268 : 18228 : bool foundAnswer = false;
269 : 18228 : unsigned int bins = unconfTxs.size();
270 : 18228 : bool newBucketRange = true;
271 : 18228 : bool passing = true;
272 : 18228 : EstimatorBucket passBucket;
273 : 18228 : EstimatorBucket failBucket;
274 : :
275 : : // Start counting from highest feerate transactions
276 [ + + ]: 3481548 : for (int bucket = maxbucketindex; bucket >= 0; --bucket) {
277 [ + + ]: 3463320 : if (newBucketRange) {
278 : 18372 : curNearBucket = bucket;
279 : 18372 : newBucketRange = false;
280 : 18372 : }
281 : 3463320 : curFarBucket = bucket;
282 : 3463320 : nConf += confAvg[periodTarget - 1][bucket];
283 : 3463320 : partialNum += txCtAvg[bucket];
284 : 3463320 : totalNum += txCtAvg[bucket];
285 : 3463320 : failNum += failAvg[periodTarget - 1][bucket];
286 [ + + ]: 753868130 : for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
287 : 750404810 : extraNum += unconfTxs[(nBlockHeight - confct) % bins][bucket];
288 : 3463320 : extraNum += oldUnconfTxs[bucket];
289 : : // If we have enough transaction data points in this range of buckets,
290 : : // we can test for success
291 : : // (Only count the confirmed data points, so that each confirmation count
292 : : // will be looking at the same amount of data and same bucket breaks)
293 : :
294 [ + + ]: 3463320 : if (partialNum < sufficientTxVal / (1 - decay)) {
295 : : // the buckets we've added in this round aren't sufficient
296 : : // so keep adding
297 : 3462301 : continue;
298 : : } else {
299 : 1019 : partialNum = 0; // reset for the next range we'll add
300 : :
301 : 1019 : double curPct = nConf / (totalNum + failNum + extraNum);
302 : :
303 : : // Check to see if we are no longer getting confirmed at the success rate
304 [ + + ]: 1019 : if (curPct < successBreakPoint) {
305 [ - + ]: 845 : if (passing == true) {
306 : : // First time we hit a failure record the failed bucket
307 : 845 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
308 : 845 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
309 [ + + ]: 845 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
310 : 845 : failBucket.end = buckets[failMaxBucket];
311 : 845 : failBucket.withinTarget = nConf;
312 : 845 : failBucket.totalConfirmed = totalNum;
313 : 845 : failBucket.inMempool = extraNum;
314 : 845 : failBucket.leftMempool = failNum;
315 : 845 : passing = false;
316 : 845 : }
317 : 845 : continue;
318 : : }
319 : : // Otherwise update the cumulative stats, and the bucket variables
320 : : // and reset the counters
321 : : else {
322 : 174 : failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
323 : 174 : foundAnswer = true;
324 : 174 : passing = true;
325 : 174 : passBucket.withinTarget = nConf;
326 : 174 : nConf = 0;
327 : 174 : passBucket.totalConfirmed = totalNum;
328 : 174 : totalNum = 0;
329 : 174 : passBucket.inMempool = extraNum;
330 : 174 : passBucket.leftMempool = failNum;
331 : 174 : failNum = 0;
332 : 174 : extraNum = 0;
333 : 174 : bestNearBucket = curNearBucket;
334 : 174 : bestFarBucket = curFarBucket;
335 : 174 : newBucketRange = true;
336 : : }
337 [ - + + ]: 1019 : }
338 : 174 : }
339 : :
340 : 18228 : double median = -1;
341 : 18228 : double txSum = 0;
342 : :
343 : : // Calculate the "average" feerate of the best bucket range that met success conditions
344 : : // Find the bucket with the median transaction and then report the average feerate from that bucket
345 : : // This is a compromise between finding the median which we can't since we don't save all tx's
346 : : // and reporting the average which is less accurate
347 : 18228 : unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
348 : 18228 : unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
349 [ + + ]: 42411 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
350 : 24183 : txSum += txCtAvg[j];
351 : 24183 : }
352 [ + + - + ]: 18228 : if (foundAnswer && txSum != 0) {
353 : 174 : txSum = txSum / 2;
354 [ + - ]: 6303 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
355 [ + + ]: 6129 : if (txCtAvg[j] < txSum)
356 : 5955 : txSum -= txCtAvg[j];
357 : : else { // we're in the right bucket
358 : 174 : median = m_feerate_avg[j] / txCtAvg[j];
359 : 174 : break;
360 : : }
361 : 5955 : }
362 : :
363 [ + + ]: 174 : passBucket.start = minBucket ? buckets[minBucket-1] : 0;
364 : 174 : passBucket.end = buckets[maxBucket];
365 : 174 : }
366 : :
367 : : // If we were passing until we reached last few buckets with insufficient data, then report those as failed
368 [ + + + + ]: 18228 : if (passing && !newBucketRange) {
369 : 17353 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
370 : 17353 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
371 [ - + ]: 17353 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
372 : 17353 : failBucket.end = buckets[failMaxBucket];
373 : 17353 : failBucket.withinTarget = nConf;
374 : 17353 : failBucket.totalConfirmed = totalNum;
375 : 17353 : failBucket.inMempool = extraNum;
376 : 17353 : failBucket.leftMempool = failNum;
377 : 17353 : }
378 : :
379 : 18228 : float passed_within_target_perc = 0.0;
380 : 18228 : float failed_within_target_perc = 0.0;
381 [ + + ]: 18228 : if ((passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool)) {
382 : 174 : passed_within_target_perc = 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool);
383 : 174 : }
384 [ + + ]: 18228 : if ((failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool)) {
385 : 16777 : failed_within_target_perc = 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool);
386 : 16777 : }
387 : :
388 [ + - ]: 18228 : LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
389 : : confTarget, 100.0 * successBreakPoint, decay,
390 : : median, passBucket.start, passBucket.end,
391 : : passed_within_target_perc,
392 : : passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool,
393 : : failBucket.start, failBucket.end,
394 : : failed_within_target_perc,
395 : : failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool);
396 : :
397 : :
398 [ + + ]: 18228 : if (result) {
399 : 17071 : result->pass = passBucket;
400 : 17071 : result->fail = failBucket;
401 : 17071 : result->decay = decay;
402 : 17071 : result->scale = scale;
403 : 17071 : }
404 : 36456 : return median;
405 : 18228 : }
406 : :
407 : 448 : void TxConfirmStats::Write(AutoFile& fileout) const
408 : : {
409 : 448 : fileout << Using<EncodedDoubleFormatter>(decay);
410 : 448 : fileout << scale;
411 : 448 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
412 : 448 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
413 : 448 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
414 : 448 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
415 : 448 : }
416 : :
417 : 651 : void TxConfirmStats::Read(AutoFile& filein, int nFileVersion, size_t numBuckets)
418 : : {
419 : : // Read data file and do some very basic sanity checking
420 : : // buckets and bucketMap are not updated yet, so don't access them
421 : : // If there is a read failure, we'll just discard this entire object anyway
422 : 651 : size_t maxConfirms, maxPeriods;
423 : :
424 : : // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
425 : 651 : filein >> Using<EncodedDoubleFormatter>(decay);
426 [ + + ]: 651 : if (decay <= 0 || decay >= 1) {
427 [ + - ]: 13 : throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
428 : : }
429 : 638 : filein >> scale;
430 [ + + ]: 638 : if (scale == 0) {
431 [ + - ]: 3 : throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
432 : : }
433 : :
434 : 635 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
435 [ + + ]: 635 : if (m_feerate_avg.size() != numBuckets) {
436 [ + - ]: 11 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
437 : : }
438 : 624 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
439 [ + + ]: 624 : if (txCtAvg.size() != numBuckets) {
440 [ + - ]: 16 : throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
441 : : }
442 : 608 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
443 : 608 : maxPeriods = confAvg.size();
444 : 608 : maxConfirms = scale * maxPeriods;
445 : :
446 [ + + ]: 608 : if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
447 [ + - ]: 23 : throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
448 : : }
449 [ + + ]: 3941 : for (unsigned int i = 0; i < maxPeriods; i++) {
450 [ + + ]: 3371 : if (confAvg[i].size() != numBuckets) {
451 [ + - ]: 15 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
452 : : }
453 : 3356 : }
454 : :
455 : 570 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
456 [ + + ]: 570 : if (maxPeriods != failAvg.size()) {
457 [ + - ]: 17 : throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
458 : : }
459 [ + + ]: 2356 : for (unsigned int i = 0; i < maxPeriods; i++) {
460 [ + + ]: 1815 : if (failAvg[i].size() != numBuckets) {
461 [ + - ]: 12 : throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
462 : : }
463 : 1803 : }
464 : :
465 : : // Resize the current block variables which aren't stored in the data file
466 : : // to match the number of confirms and buckets
467 : 541 : resizeInMemoryCounters(numBuckets);
468 : :
469 [ + - ]: 541 : LogPrint(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
470 : : numBuckets, maxConfirms);
471 : 541 : }
472 : :
473 : 24207 : unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
474 : : {
475 : 24207 : unsigned int bucketindex = bucketMap.lower_bound(val)->second;
476 : 24207 : unsigned int blockIndex = nBlockHeight % unconfTxs.size();
477 : 24207 : unconfTxs[blockIndex][bucketindex]++;
478 : 48414 : return bucketindex;
479 : 24207 : }
480 : :
481 : 22428 : void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex, bool inBlock)
482 : : {
483 : : //nBestSeenHeight is not updated yet for the new block
484 : 22428 : int blocksAgo = nBestSeenHeight - entryHeight;
485 [ + + ]: 22428 : if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
486 : 204 : blocksAgo = 0;
487 [ + + ]: 22428 : if (blocksAgo < 0) {
488 [ + - ]: 3033 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, blocks ago is negative for mempool tx\n");
489 : 3033 : return; //This can't happen because we call this with our best seen height, no entries can have higher
490 : : }
491 : :
492 [ + + ]: 19395 : if (blocksAgo >= (int)unconfTxs.size()) {
493 [ + + ]: 5056 : if (oldUnconfTxs[bucketindex] > 0) {
494 : 361 : oldUnconfTxs[bucketindex]--;
495 : 361 : } else {
496 [ + - ]: 4695 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
497 : : bucketindex);
498 : : }
499 : 5056 : }
500 : : else {
501 : 14339 : unsigned int blockIndex = entryHeight % unconfTxs.size();
502 [ + - ]: 14339 : if (unconfTxs[blockIndex][bucketindex] > 0) {
503 : 14339 : unconfTxs[blockIndex][bucketindex]--;
504 : 14339 : } else {
505 [ # # ]: 0 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
506 : : blockIndex, bucketindex);
507 : : }
508 : 14339 : }
509 [ + + + + ]: 19395 : if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
510 [ + - ]: 1599 : assert(scale != 0);
511 : 1599 : unsigned int periodsAgo = blocksAgo / scale;
512 [ + + + + ]: 37273 : for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
513 : 35674 : failAvg[i][bucketindex]++;
514 : 35674 : }
515 : 1599 : }
516 [ - + ]: 22428 : }
517 : :
518 : 9177 : bool CBlockPolicyEstimator::removeTx(uint256 hash)
519 : : {
520 : 9177 : LOCK(m_cs_fee_estimator);
521 [ + - ]: 9177 : return _removeTx(hash, /*inBlock=*/false);
522 : 9177 : }
523 : :
524 : 21951 : bool CBlockPolicyEstimator::_removeTx(const uint256& hash, bool inBlock)
525 : : {
526 : 21951 : AssertLockHeld(m_cs_fee_estimator);
527 : 21951 : std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
528 [ + + ]: 21951 : if (pos != mapMemPoolTxs.end()) {
529 : 7476 : feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
530 : 7476 : shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
531 : 7476 : longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
532 : 7476 : mapMemPoolTxs.erase(hash);
533 : 7476 : return true;
534 : : } else {
535 : 14475 : return false;
536 : : }
537 : 21951 : }
538 : :
539 : 2506 : CBlockPolicyEstimator::CBlockPolicyEstimator(const fs::path& estimation_filepath, const bool read_stale_estimates)
540 : 1253 : : m_estimation_filepath{estimation_filepath}
541 : 1253 : {
542 : : static_assert(MIN_BUCKET_FEERATE > 0, "Min feerate must be nonzero");
543 : 1253 : size_t bucketIndex = 0;
544 : :
545 [ + + ]: 238070 : for (double bucketBoundary = MIN_BUCKET_FEERATE; bucketBoundary <= MAX_BUCKET_FEERATE; bucketBoundary *= FEE_SPACING, bucketIndex++) {
546 [ + - ]: 236817 : buckets.push_back(bucketBoundary);
547 [ + - ]: 236817 : bucketMap[bucketBoundary] = bucketIndex;
548 : 236817 : }
549 [ + - ]: 1253 : buckets.push_back(INF_FEERATE);
550 [ + - ]: 1253 : bucketMap[INF_FEERATE] = bucketIndex;
551 [ + - ]: 1253 : assert(bucketMap.size() == buckets.size());
552 : :
553 [ + - + - ]: 1253 : feeStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
554 [ + - + - ]: 1253 : shortStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
555 [ + - + - ]: 1253 : longStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
556 : :
557 [ + - + - ]: 1253 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "rb")};
558 : :
559 [ + - + - ]: 1253 : if (est_file.IsNull()) {
560 [ + - + - ]: 1253 : LogPrintf("%s is not found. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
561 : 1253 : return;
562 : : }
563 : :
564 [ # # ]: 0 : std::chrono::hours file_age = GetFeeEstimatorFileAge();
565 [ # # # # : 0 : if (file_age > MAX_FILE_AGE && !read_stale_estimates) {
# # ]
566 [ # # # # : 0 : LogPrintf("Fee estimation file %s too old (age=%lld > %lld hours) and will not be used to avoid serving stale estimates.\n", fs::PathToString(m_estimation_filepath), Ticks<std::chrono::hours>(file_age), Ticks<std::chrono::hours>(MAX_FILE_AGE));
# # # # ]
567 : 0 : return;
568 : : }
569 : :
570 [ # # # # ]: 0 : if (!Read(est_file)) {
571 [ # # # # ]: 0 : LogPrintf("Failed to read fee estimates from %s. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
572 : 0 : }
573 : 0 : }
574 : :
575 : 1253 : CBlockPolicyEstimator::~CBlockPolicyEstimator() = default;
576 : :
577 : 0 : void CBlockPolicyEstimator::TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /*unused*/)
578 : : {
579 : 0 : processTransaction(tx);
580 : 0 : }
581 : :
582 : 0 : void CBlockPolicyEstimator::TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason /*unused*/, uint64_t /*unused*/)
583 : : {
584 : 0 : removeTx(tx->GetHash());
585 : 0 : }
586 : :
587 : 0 : void CBlockPolicyEstimator::MempoolTransactionsRemovedForBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block, unsigned int nBlockHeight)
588 : : {
589 : 0 : processBlock(txs_removed_for_block, nBlockHeight);
590 : 0 : }
591 : :
592 : 24220 : void CBlockPolicyEstimator::processTransaction(const NewMempoolTransactionInfo& tx)
593 : : {
594 : 24220 : LOCK(m_cs_fee_estimator);
595 : 24220 : const unsigned int txHeight = tx.info.txHeight;
596 [ + - ]: 24220 : const auto& hash = tx.info.m_tx->GetHash();
597 [ + - + - : 24220 : if (mapMemPoolTxs.count(hash)) {
+ + ]
598 [ + - + - : 5994 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error mempool tx %s already being tracked\n",
# # # # ]
599 : : hash.ToString());
600 : 5994 : return;
601 : : }
602 : :
603 [ + + ]: 18226 : if (txHeight != nBestSeenHeight) {
604 : : // Ignore side chains and re-orgs; assuming they are random they don't
605 : : // affect the estimate. We'll potentially double count transactions in 1-block reorgs.
606 : : // Ignore txs if BlockPolicyEstimator is not in sync with ActiveChain().Tip().
607 : : // It will be synced next time a block is processed.
608 : 9567 : return;
609 : : }
610 : : // This transaction should only count for fee estimation if:
611 : : // - it's not being re-added during a reorg which bypasses typical mempool fee limits
612 : : // - the node is not behind
613 : : // - the transaction is not dependent on any other transactions in the mempool
614 : : // - it's not part of a package.
615 [ + - + + : 8659 : const bool validForFeeEstimation = !tx.m_mempool_limit_bypassed && !tx.m_submitted_in_package && tx.m_chainstate_is_current && tx.m_has_no_mempool_parents;
- + ]
616 : :
617 : : // Only want to be updating estimates when our blockchain is synced,
618 : : // otherwise we'll miscalculate how many blocks its taking to get included.
619 [ + + ]: 8659 : if (!validForFeeEstimation) {
620 : 590 : untrackedTxs++;
621 : 590 : return;
622 : : }
623 : 8069 : trackedTxs++;
624 : :
625 : : // Feerates are stored and reported as BTC-per-kb:
626 [ + - ]: 8069 : const CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
627 : :
628 [ + - + - ]: 8069 : mapMemPoolTxs[hash].blockHeight = txHeight;
629 [ + - + - ]: 8069 : unsigned int bucketIndex = feeStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
630 [ + - + - ]: 8069 : mapMemPoolTxs[hash].bucketIndex = bucketIndex;
631 [ + - + - ]: 8069 : unsigned int bucketIndex2 = shortStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
632 [ + - ]: 8069 : assert(bucketIndex == bucketIndex2);
633 [ + - + - ]: 8069 : unsigned int bucketIndex3 = longStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
634 [ + - ]: 8069 : assert(bucketIndex == bucketIndex3);
635 [ - + ]: 24220 : }
636 : :
637 : 9698 : bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const RemovedMempoolTransactionInfo& tx)
638 : : {
639 : 9698 : AssertLockHeld(m_cs_fee_estimator);
640 [ + + ]: 9698 : if (!_removeTx(tx.info.m_tx->GetHash(), true)) {
641 : : // This transaction wasn't being tracked for fee estimation
642 : 8032 : return false;
643 : : }
644 : :
645 : : // How many blocks did it take for miners to include this transaction?
646 : : // blocksToConfirm is 1-based, so a transaction included in the earliest
647 : : // possible block has confirmation count of 1
648 : 1666 : int blocksToConfirm = nBlockHeight - tx.info.txHeight;
649 [ + + ]: 1666 : if (blocksToConfirm <= 0) {
650 : : // This can't happen because we don't process transactions from a block with a height
651 : : // lower than our greatest seen height
652 [ + - ]: 291 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error Transaction had negative blocksToConfirm\n");
653 : 291 : return false;
654 : : }
655 : :
656 : : // Feerates are stored and reported as BTC-per-kb:
657 : 1375 : CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
658 : :
659 : 1375 : feeStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
660 : 1375 : shortStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
661 : 1375 : longStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
662 : 1375 : return true;
663 : 9698 : }
664 : :
665 : 8352 : void CBlockPolicyEstimator::processBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block,
666 : : unsigned int nBlockHeight)
667 : : {
668 : 8352 : LOCK(m_cs_fee_estimator);
669 [ + + ]: 8352 : if (nBlockHeight <= nBestSeenHeight) {
670 : : // Ignore side chains and re-orgs; assuming they are random
671 : : // they don't affect the estimate.
672 : : // And if an attacker can re-org the chain at will, then
673 : : // you've got much bigger problems than "attacker can influence
674 : : // transaction fees."
675 : 7361 : return;
676 : : }
677 : :
678 : : // Must update nBestSeenHeight in sync with ClearCurrent so that
679 : : // calls to removeTx (via processBlockTx) correctly calculate age
680 : : // of unconfirmed txs to remove from tracking.
681 : 991 : nBestSeenHeight = nBlockHeight;
682 : :
683 : : // Update unconfirmed circular buffer
684 : 991 : feeStats->ClearCurrent(nBlockHeight);
685 : 991 : shortStats->ClearCurrent(nBlockHeight);
686 : 991 : longStats->ClearCurrent(nBlockHeight);
687 : :
688 : : // Decay all exponential averages
689 : 991 : feeStats->UpdateMovingAverages();
690 : 991 : shortStats->UpdateMovingAverages();
691 : 991 : longStats->UpdateMovingAverages();
692 : :
693 : 991 : unsigned int countedTxs = 0;
694 : : // Update averages with data points from current block
695 [ + + ]: 10689 : for (const auto& tx : txs_removed_for_block) {
696 [ + - + + ]: 9698 : if (processBlockTx(nBlockHeight, tx))
697 : 1375 : countedTxs++;
698 : 9698 : }
699 : :
700 [ + + + + ]: 991 : if (firstRecordedHeight == 0 && countedTxs > 0) {
701 : 261 : firstRecordedHeight = nBestSeenHeight;
702 [ + - - + : 261 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy first recorded height %u\n", firstRecordedHeight);
# # ]
703 : 261 : }
704 : :
705 : :
706 [ + - + - : 991 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy estimates updated by %u of %u block txs, since last block %u of %u tracked, mempool map size %u, max target %u from %s\n",
# # # # #
# # # ]
707 : : countedTxs, txs_removed_for_block.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size(),
708 : : MaxUsableEstimate(), HistoricalBlockSpan() > BlockSpan() ? "historical" : "current");
709 : :
710 : 991 : trackedTxs = 0;
711 : 991 : untrackedTxs = 0;
712 [ - + ]: 8352 : }
713 : :
714 : 72978 : CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) const
715 : : {
716 : : // It's not possible to get reasonable estimates for confTarget of 1
717 [ + + ]: 72978 : if (confTarget <= 1)
718 : 52028 : return CFeeRate(0);
719 : :
720 : 20950 : return estimateRawFee(confTarget, DOUBLE_SUCCESS_PCT, FeeEstimateHorizon::MED_HALFLIFE);
721 : 72978 : }
722 : :
723 : 93928 : CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult* result) const
724 : : {
725 : 93928 : TxConfirmStats* stats = nullptr;
726 : 93928 : double sufficientTxs = SUFFICIENT_FEETXS;
727 [ + - + + ]: 93928 : switch (horizon) {
728 : : case FeeEstimateHorizon::SHORT_HALFLIFE: {
729 : 21321 : stats = shortStats.get();
730 : 21321 : sufficientTxs = SUFFICIENT_TXS_SHORT;
731 : 21321 : break;
732 : : }
733 : : case FeeEstimateHorizon::MED_HALFLIFE: {
734 : 62521 : stats = feeStats.get();
735 : 62521 : break;
736 : : }
737 : : case FeeEstimateHorizon::LONG_HALFLIFE: {
738 : 10086 : stats = longStats.get();
739 : 10086 : break;
740 : : }
741 : : } // no default case, so the compiler can warn about missing cases
742 [ + - ]: 93928 : assert(stats);
743 : :
744 : 93928 : LOCK(m_cs_fee_estimator);
745 : : // Return failure if trying to analyze a target we're not tracking
746 [ + + + - : 93928 : if (confTarget <= 0 || (unsigned int)confTarget > stats->GetMaxConfirms())
+ + ]
747 [ + - ]: 92228 : return CFeeRate(0);
748 [ + + ]: 1700 : if (successThreshold > 1)
749 [ + - ]: 34 : return CFeeRate(0);
750 : :
751 [ + - ]: 1666 : double median = stats->EstimateMedianVal(confTarget, sufficientTxs, successThreshold, nBestSeenHeight, result);
752 : :
753 [ + + ]: 1666 : if (median < 0)
754 [ + - ]: 1492 : return CFeeRate(0);
755 : :
756 [ + - ]: 174 : return CFeeRate(llround(median));
757 : 93928 : }
758 : :
759 : 72978 : unsigned int CBlockPolicyEstimator::HighestTargetTracked(FeeEstimateHorizon horizon) const
760 : : {
761 : 72978 : LOCK(m_cs_fee_estimator);
762 [ + + - + ]: 72978 : switch (horizon) {
763 : : case FeeEstimateHorizon::SHORT_HALFLIFE: {
764 [ + - ]: 21370 : return shortStats->GetMaxConfirms();
765 : : }
766 : : case FeeEstimateHorizon::MED_HALFLIFE: {
767 [ + - ]: 22424 : return feeStats->GetMaxConfirms();
768 : : }
769 : : case FeeEstimateHorizon::LONG_HALFLIFE: {
770 [ + - ]: 29184 : return longStats->GetMaxConfirms();
771 : : }
772 : : } // no default case, so the compiler can warn about missing cases
773 : 0 : assert(false);
774 : 72978 : }
775 : :
776 : 3924 : unsigned int CBlockPolicyEstimator::BlockSpan() const
777 : : {
778 [ + + ]: 3924 : if (firstRecordedHeight == 0) return 0;
779 [ + - ]: 2924 : assert(nBestSeenHeight >= firstRecordedHeight);
780 : :
781 : 2924 : return nBestSeenHeight - firstRecordedHeight;
782 : 3924 : }
783 : :
784 : 3924 : unsigned int CBlockPolicyEstimator::HistoricalBlockSpan() const
785 : : {
786 [ + + ]: 3924 : if (historicalFirst == 0) return 0;
787 [ + - ]: 66 : assert(historicalBest >= historicalFirst);
788 : :
789 [ + + ]: 66 : if (nBestSeenHeight - historicalBest > OLDEST_ESTIMATE_HISTORY) return 0;
790 : :
791 : 19 : return historicalBest - historicalFirst;
792 : 3924 : }
793 : :
794 : 3678 : unsigned int CBlockPolicyEstimator::MaxUsableEstimate() const
795 : : {
796 : : // Block spans are divided by 2 to make sure there are enough potential failing data points for the estimate
797 : 3678 : return std::min(longStats->GetMaxConfirms(), std::max(BlockSpan(), HistoricalBlockSpan()) / 2);
798 : : }
799 : :
800 : : /** Return a fee estimate at the required successThreshold from the shortest
801 : : * time horizon which tracks confirmations up to the desired target. If
802 : : * checkShorterHorizon is requested, also allow short time horizon estimates
803 : : * for a lower target to reduce the given answer */
804 : 8559 : double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const
805 : : {
806 : 8559 : double estimate = -1;
807 [ + - + + ]: 8559 : if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
808 : : // Find estimate from shortest time horizon possible
809 [ + + ]: 8423 : if (confTarget <= shortStats->GetMaxConfirms()) { // short horizon
810 : 3229 : estimate = shortStats->EstimateMedianVal(confTarget, SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, result);
811 : 3229 : }
812 [ + + ]: 5194 : else if (confTarget <= feeStats->GetMaxConfirms()) { // medium horizon
813 : 2635 : estimate = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
814 : 2635 : }
815 : : else { // long horizon
816 : 2559 : estimate = longStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
817 : : }
818 [ + + ]: 8423 : if (checkShorterHorizon) {
819 : 6690 : EstimationResult tempResult;
820 : : // If a lower confTarget from a more recent horizon returns a lower answer use it.
821 [ + + ]: 6690 : if (confTarget > feeStats->GetMaxConfirms()) {
822 : 1917 : double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, &tempResult);
823 [ - + # # : 1917 : if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
# # ]
824 : 0 : estimate = medMax;
825 [ # # ]: 0 : if (result) *result = tempResult;
826 : 0 : }
827 : 1917 : }
828 [ + + ]: 6690 : if (confTarget > shortStats->GetMaxConfirms()) {
829 : 4052 : double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(), SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, &tempResult);
830 [ - + # # : 4052 : if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
# # ]
831 : 0 : estimate = shortMax;
832 [ # # ]: 0 : if (result) *result = tempResult;
833 : 0 : }
834 : 4052 : }
835 : 6690 : }
836 : 8423 : }
837 : 17118 : return estimate;
838 : 8559 : }
839 : :
840 : : /** Ensure that for a conservative estimate, the DOUBLE_SUCCESS_PCT is also met
841 : : * at 2 * target for any longer time horizons.
842 : : */
843 : 2853 : double CBlockPolicyEstimator::estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const
844 : : {
845 : 2853 : double estimate = -1;
846 : 2853 : EstimationResult tempResult;
847 [ + + ]: 2853 : if (doubleTarget <= shortStats->GetMaxConfirms()) {
848 : 832 : estimate = feeStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, result);
849 : 832 : }
850 [ + + ]: 2853 : if (doubleTarget <= feeStats->GetMaxConfirms()) {
851 : 1338 : double longEstimate = longStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, &tempResult);
852 [ + - ]: 1338 : if (longEstimate > estimate) {
853 : 0 : estimate = longEstimate;
854 [ # # ]: 0 : if (result) *result = tempResult;
855 : 0 : }
856 : 1338 : }
857 : 5706 : return estimate;
858 : 2853 : }
859 : :
860 : : /** estimateSmartFee returns the max of the feerates calculated with a 60%
861 : : * threshold required at target / 2, an 85% threshold required at target and a
862 : : * 95% threshold required at 2 * target. Each calculation is performed at the
863 : : * shortest time horizon which tracks the required target. Conservative
864 : : * estimates, however, required the 95% threshold at 2 * target be met for any
865 : : * longer time horizons also.
866 : : */
867 : 72978 : CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
868 : : {
869 : 72978 : LOCK(m_cs_fee_estimator);
870 : :
871 [ + + ]: 72978 : if (feeCalc) {
872 : 52801 : feeCalc->desiredTarget = confTarget;
873 : 52801 : feeCalc->returnedTarget = confTarget;
874 : 52801 : }
875 : :
876 : 72978 : double median = -1;
877 : 72978 : EstimationResult tempResult;
878 : :
879 : : // Return failure if trying to analyze a target we're not tracking
880 [ + + + - : 72978 : if (confTarget <= 0 || (unsigned int)confTarget > longStats->GetMaxConfirms()) {
+ + ]
881 [ + - ]: 69300 : return CFeeRate(0); // error condition
882 : : }
883 : :
884 : : // It's not possible to get reasonable estimates for confTarget of 1
885 [ + + ]: 3678 : if (confTarget == 1) confTarget = 2;
886 : :
887 [ + - ]: 3678 : unsigned int maxUsableEstimate = MaxUsableEstimate();
888 [ + + ]: 3678 : if ((unsigned int)confTarget > maxUsableEstimate) {
889 : 826 : confTarget = maxUsableEstimate;
890 : 826 : }
891 [ + + ]: 3678 : if (feeCalc) feeCalc->returnedTarget = confTarget;
892 : :
893 [ + + + - ]: 3678 : if (confTarget <= 1) return CFeeRate(0); // error condition
894 : :
895 [ + - ]: 2853 : assert(confTarget > 0); //estimateCombinedFee and estimateConservativeFee take unsigned ints
896 : : /** true is passed to estimateCombined fee for target/2 and target so
897 : : * that we check the max confirms for shorter time horizons as well.
898 : : * This is necessary to preserve monotonically increasing estimates.
899 : : * For non-conservative estimates we do the same thing for 2*target, but
900 : : * for conservative estimates we want to skip these shorter horizons
901 : : * checks for 2*target because we are taking the max over all time
902 : : * horizons so we already have monotonically increasing estimates and
903 : : * the purpose of conservative estimates is not to let short term
904 : : * fluctuations lower our estimates by too much.
905 : : */
906 [ + - ]: 2853 : double halfEst = estimateCombinedFee(confTarget/2, HALF_SUCCESS_PCT, true, &tempResult);
907 [ + + ]: 2853 : if (feeCalc) {
908 : 1774 : feeCalc->est = tempResult;
909 : 1774 : feeCalc->reason = FeeReason::HALF_ESTIMATE;
910 : 1774 : }
911 : 2853 : median = halfEst;
912 [ + - ]: 2853 : double actualEst = estimateCombinedFee(confTarget, SUCCESS_PCT, true, &tempResult);
913 [ + - ]: 2853 : if (actualEst > median) {
914 : 0 : median = actualEst;
915 [ # # ]: 0 : if (feeCalc) {
916 : 0 : feeCalc->est = tempResult;
917 : 0 : feeCalc->reason = FeeReason::FULL_ESTIMATE;
918 : 0 : }
919 : 0 : }
920 [ + - ]: 2853 : double doubleEst = estimateCombinedFee(2 * confTarget, DOUBLE_SUCCESS_PCT, !conservative, &tempResult);
921 [ + - ]: 2853 : if (doubleEst > median) {
922 : 0 : median = doubleEst;
923 [ # # ]: 0 : if (feeCalc) {
924 : 0 : feeCalc->est = tempResult;
925 : 0 : feeCalc->reason = FeeReason::DOUBLE_ESTIMATE;
926 : 0 : }
927 : 0 : }
928 : :
929 [ + + + - ]: 2853 : if (conservative || median == -1) {
930 [ + - ]: 2853 : double consEst = estimateConservativeFee(2 * confTarget, &tempResult);
931 [ + - ]: 2853 : if (consEst > median) {
932 : 0 : median = consEst;
933 [ # # ]: 0 : if (feeCalc) {
934 : 0 : feeCalc->est = tempResult;
935 : 0 : feeCalc->reason = FeeReason::CONSERVATIVE;
936 : 0 : }
937 : 0 : }
938 : 2853 : }
939 : :
940 [ + - + - ]: 2853 : if (median < 0) return CFeeRate(0); // error condition
941 : :
942 [ # # ]: 0 : return CFeeRate(llround(median));
943 : 72978 : }
944 : :
945 : 0 : void CBlockPolicyEstimator::Flush() {
946 : 0 : FlushUnconfirmed();
947 : 0 : FlushFeeEstimates();
948 : 0 : }
949 : :
950 : 0 : void CBlockPolicyEstimator::FlushFeeEstimates()
951 : : {
952 [ # # ]: 0 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "wb")};
953 [ # # # # : 0 : if (est_file.IsNull() || !Write(est_file)) {
# # # # ]
954 [ # # # # ]: 0 : LogPrintf("Failed to write fee estimates to %s. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
955 : 0 : } else {
956 [ # # # # : 0 : LogPrintf("Flushed fee estimates to %s.\n", fs::PathToString(m_estimation_filepath.filename()));
# # ]
957 : : }
958 : 0 : }
959 : :
960 : 1357 : bool CBlockPolicyEstimator::Write(AutoFile& fileout) const
961 : : {
962 : : try {
963 [ + - + - ]: 1357 : LOCK(m_cs_fee_estimator);
964 [ + + ]: 1357 : fileout << 149900; // version required to read: 0.14.99 or later
965 [ + - ]: 246 : fileout << CLIENT_VERSION; // version that wrote the file
966 [ + - ]: 246 : fileout << nBestSeenHeight;
967 [ + + ]: 246 : if (BlockSpan() > HistoricalBlockSpan()/2) {
968 [ + - + - ]: 23 : fileout << firstRecordedHeight << nBestSeenHeight;
969 : 23 : }
970 : : else {
971 [ + - + - ]: 223 : fileout << historicalFirst << historicalBest;
972 : : }
973 [ + - + - ]: 246 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(buckets);
974 [ + + ]: 246 : feeStats->Write(fileout);
975 [ + + ]: 105 : shortStats->Write(fileout);
976 [ + + ]: 97 : longStats->Write(fileout);
977 [ - + ]: 1357 : }
978 : : catch (const std::exception&) {
979 [ + - ]: 1285 : LogPrintf("CBlockPolicyEstimator::Write(): unable to write policy estimator data (non-fatal)\n");
980 : 1285 : return false;
981 [ # # ]: 1285 : }
982 : 72 : return true;
983 : 2642 : }
984 : :
985 : 1614 : bool CBlockPolicyEstimator::Read(AutoFile& filein)
986 : : {
987 : : try {
988 [ + - + - ]: 1614 : LOCK(m_cs_fee_estimator);
989 : 1614 : int nVersionRequired, nVersionThatWrote;
990 [ + + + + ]: 1614 : filein >> nVersionRequired >> nVersionThatWrote;
991 [ + + ]: 658 : if (nVersionRequired > CLIENT_VERSION) {
992 [ + - + - : 33 : throw std::runtime_error(strprintf("up-version (%d) fee estimate file", nVersionRequired));
+ - + - ]
993 : : }
994 : :
995 : : // Read fee estimates file into temporary variables so existing data
996 : : // structures aren't corrupted if there is an exception.
997 : 625 : unsigned int nFileBestSeenHeight;
998 [ + + ]: 625 : filein >> nFileBestSeenHeight;
999 : :
1000 [ + + ]: 619 : if (nVersionRequired < 149900) {
1001 [ + - ]: 45 : LogPrintf("%s: incompatible old fee estimation data (non-fatal). Version: %d\n", __func__, nVersionRequired);
1002 : 45 : } else { // New format introduced in 149900
1003 : 574 : unsigned int nFileHistoricalFirst, nFileHistoricalBest;
1004 [ + + + - ]: 574 : filein >> nFileHistoricalFirst >> nFileHistoricalBest;
1005 [ + + ]: 572 : if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
1006 [ + - ]: 14 : throw std::runtime_error("Corrupt estimates file. Historical block range for estimates is invalid");
1007 : : }
1008 : 558 : std::vector<double> fileBuckets;
1009 [ + - + + ]: 558 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(fileBuckets);
1010 : 529 : size_t numBuckets = fileBuckets.size();
1011 [ + + ]: 529 : if (numBuckets <= 1 || numBuckets > 1000) {
1012 [ + - ]: 11 : throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
1013 : : }
1014 : :
1015 [ + - + - ]: 518 : std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
1016 [ + - + - ]: 518 : std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
1017 [ + - + - ]: 518 : std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
1018 [ + + ]: 518 : fileFeeStats->Read(filein, nVersionThatWrote, numBuckets);
1019 [ + + ]: 283 : fileShortStats->Read(filein, nVersionThatWrote, numBuckets);
1020 [ + + ]: 146 : fileLongStats->Read(filein, nVersionThatWrote, numBuckets);
1021 : :
1022 : : // Fee estimates file parsed correctly
1023 : : // Copy buckets from file and refresh our bucketmap
1024 [ + - ]: 112 : buckets = fileBuckets;
1025 : 112 : bucketMap.clear();
1026 [ + + ]: 469 : for (unsigned int i = 0; i < buckets.size(); i++) {
1027 [ + - ]: 357 : bucketMap[buckets[i]] = i;
1028 : 357 : }
1029 : :
1030 : : // Destroy old TxConfirmStats and point to new ones that already reference buckets and bucketMap
1031 : 112 : feeStats = std::move(fileFeeStats);
1032 : 112 : shortStats = std::move(fileShortStats);
1033 : 112 : longStats = std::move(fileLongStats);
1034 : :
1035 : 112 : nBestSeenHeight = nFileBestSeenHeight;
1036 : 112 : historicalFirst = nFileHistoricalFirst;
1037 : 112 : historicalBest = nFileHistoricalBest;
1038 : 574 : }
1039 [ - + ]: 1614 : }
1040 : : catch (const std::exception& e) {
1041 [ + - ]: 1457 : LogPrintf("CBlockPolicyEstimator::Read(): unable to read policy estimator data (non-fatal): %s\n",e.what());
1042 : 1457 : return false;
1043 [ # # ]: 1457 : }
1044 : 157 : return true;
1045 : 3071 : }
1046 : :
1047 : 38761 : void CBlockPolicyEstimator::FlushUnconfirmed()
1048 : : {
1049 : 38761 : const auto startclear{SteadyClock::now()};
1050 : 38761 : LOCK(m_cs_fee_estimator);
1051 : 38761 : size_t num_entries = mapMemPoolTxs.size();
1052 : : // Remove every entry in mapMemPoolTxs
1053 [ + + ]: 41837 : while (!mapMemPoolTxs.empty()) {
1054 : 3076 : auto mi = mapMemPoolTxs.begin();
1055 [ + - ]: 3076 : _removeTx(mi->first, false); // this calls erase() on mapMemPoolTxs
1056 : 3076 : }
1057 : 38761 : const auto endclear{SteadyClock::now()};
1058 [ + - + - : 38761 : LogPrint(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %.3fs\n", num_entries, Ticks<SecondsDouble>(endclear - startclear));
# # # # #
# ]
1059 : 38761 : }
1060 : :
1061 : 0 : std::chrono::hours CBlockPolicyEstimator::GetFeeEstimatorFileAge()
1062 : : {
1063 : 0 : auto file_time{fs::last_write_time(m_estimation_filepath)};
1064 : 0 : auto now{fs::file_time_type::clock::now()};
1065 : 0 : return std::chrono::duration_cast<std::chrono::hours>(now - file_time);
1066 : 0 : }
1067 : :
1068 : 1346 : static std::set<double> MakeFeeSet(const CFeeRate& min_incremental_fee,
1069 : : double max_filter_fee_rate,
1070 : : double fee_filter_spacing)
1071 : : {
1072 : 1346 : std::set<double> fee_set;
1073 : :
1074 [ + - ]: 1346 : const CAmount min_fee_limit{std::max(CAmount(1), min_incremental_fee.GetFeePerK() / 2)};
1075 [ + - ]: 1346 : fee_set.insert(0);
1076 [ + + ]: 138271 : for (double bucket_boundary = min_fee_limit;
1077 : 138271 : bucket_boundary <= max_filter_fee_rate;
1078 : 136925 : bucket_boundary *= fee_filter_spacing) {
1079 : :
1080 [ + - ]: 136925 : fee_set.insert(bucket_boundary);
1081 : 136925 : }
1082 : :
1083 : 1346 : return fee_set;
1084 [ + - ]: 1346 : }
1085 : :
1086 : 2692 : FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee, FastRandomContext& rng)
1087 : 1346 : : m_fee_set{MakeFeeSet(minIncrementalFee, MAX_FILTER_FEERATE, FEE_FILTER_SPACING)},
1088 : 1346 : insecure_rand{rng}
1089 : : {
1090 : 1346 : }
1091 : :
1092 : 105433 : CAmount FeeFilterRounder::round(CAmount currentMinFee)
1093 : : {
1094 : 105433 : AssertLockNotHeld(m_insecure_rand_mutex);
1095 : 105433 : std::set<double>::iterator it = m_fee_set.lower_bound(currentMinFee);
1096 [ + + + + ]: 188746 : if (it == m_fee_set.end() ||
1097 [ + + ]: 83313 : (it != m_fee_set.begin() &&
1098 : 128708 : WITH_LOCK(m_insecure_rand_mutex, return insecure_rand.rand32()) % 3 != 0)) {
1099 : 65479 : --it;
1100 : 65479 : }
1101 : 210866 : return static_cast<CAmount>(*it);
1102 : 105433 : }
|