aboutsummaryrefslogtreecommitdiff
path: root/src/policy/fees.h
blob: 1c24b8c7c3725c44a265a4c40f134fd7850dc57d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#ifndef BITCOIN_POLICY_FEES_H
#define BITCOIN_POLICY_FEES_H

#include <consensus/amount.h>
#include <fs.h>
#include <policy/feerate.h>
#include <random.h>
#include <sync.h>
#include <threadsafety.h>
#include <uint256.h>

#include <array>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <vector>

class AutoFile;
class CTxMemPoolEntry;
class TxConfirmStats;

/* Identifier for each of the 3 different TxConfirmStats which will track
 * history over different time horizons. */
enum class FeeEstimateHorizon {
    SHORT_HALFLIFE,
    MED_HALFLIFE,
    LONG_HALFLIFE,
};

static constexpr auto ALL_FEE_ESTIMATE_HORIZONS = std::array{
    FeeEstimateHorizon::SHORT_HALFLIFE,
    FeeEstimateHorizon::MED_HALFLIFE,
    FeeEstimateHorizon::LONG_HALFLIFE,
};

std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);

/* Enumeration of reason for returned fee estimate */
enum class FeeReason {
    NONE,
    HALF_ESTIMATE,
    FULL_ESTIMATE,
    DOUBLE_ESTIMATE,
    CONSERVATIVE,
    MEMPOOL_MIN,
    PAYTXFEE,
    FALLBACK,
    REQUIRED,
};

/* Used to return detailed information about a feerate bucket */
struct EstimatorBucket
{
    double start = -1;
    double end = -1;
    double withinTarget = 0;
    double totalConfirmed = 0;
    double inMempool = 0;
    double leftMempool = 0;
};

/* Used to return detailed information about a fee estimate calculation */
struct EstimationResult
{
    EstimatorBucket pass;
    EstimatorBucket fail;
    double decay = 0;
    unsigned int scale = 0;
};

struct FeeCalculation
{
    EstimationResult est;
    FeeReason reason = FeeReason::NONE;
    int desiredTarget = 0;
    int returnedTarget = 0;
};

/** \class CBlockPolicyEstimator
 * The BlockPolicyEstimator is used for estimating the feerate needed
 * for a transaction to be included in a block within a certain number of
 * blocks.
 *
 * At a high level the algorithm works by grouping transactions into buckets
 * based on having similar feerates and then tracking how long it
 * takes transactions in the various buckets to be mined.  It operates under
 * the assumption that in general transactions of higher feerate will be
 * included in blocks before transactions of lower feerate.   So for
 * example if you wanted to know what feerate you should put on a transaction to
 * be included in a block within the next 5 blocks, you would start by looking
 * at the bucket with the highest feerate transactions and verifying that a
 * sufficiently high percentage of them were confirmed within 5 blocks and
 * then you would look at the next highest feerate bucket, and so on, stopping at
 * the last bucket to pass the test.   The average feerate of transactions in this
 * bucket will give you an indication of the lowest feerate you can put on a
 * transaction and still have a sufficiently high chance of being confirmed
 * within your desired 5 blocks.
 *
 * Here is a brief description of the implementation:
 * When a transaction enters the mempool, we track the height of the block chain
 * at entry.  All further calculations are conducted only on this set of "seen"
 * transactions. Whenever a block comes in, we count the number of transactions
 * in each bucket and the total amount of feerate paid in each bucket. Then we
 * calculate how many blocks Y it took each transaction to be mined.  We convert
 * from a number of blocks to a number of periods Y' each encompassing "scale"
 * blocks.  This is tracked in 3 different data sets each up to a maximum
 * number of periods. Within each data set we have an array of counters in each
 * feerate bucket and we increment all the counters from Y' up to max periods
 * representing that a tx was successfully confirmed in less than or equal to
 * that many periods. We want to save a history of this information, so at any
 * time we have a counter of the total number of transactions that happened in a
 * given feerate bucket and the total number that were confirmed in each of the
 * periods or less for any bucket.  We save this history by keeping an
 * exponentially decaying moving average of each one of these stats.  This is
 * done for a different decay in each of the 3 data sets to keep relevant data
 * from different time horizons.  Furthermore we also keep track of the number
 * unmined (in mempool or left mempool without being included in a block)
 * transactions in each bucket and for how many blocks they have been
 * outstanding and use both of these numbers to increase the number of transactions
 * we've seen in that feerate bucket when calculating an estimate for any number
 * of confirmations below the number of blocks they've been outstanding.
 *
 *  We want to be able to estimate feerates that are needed on tx's to be included in
 * a certain number of blocks.  Every time a block is added to the best chain, this class records
 * stats on the transactions included in that block
 */
class CBlockPolicyEstimator
{
private:
    /** Track confirm delays up to 12 blocks for short horizon */
    static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
    static constexpr unsigned int SHORT_SCALE = 1;
    /** Track confirm delays up to 48 blocks for medium horizon */
    static constexpr unsigned int MED_BLOCK_PERIODS = 24;
    static constexpr unsigned int MED_SCALE = 2;
    /** Track confirm delays up to 1008 blocks for long horizon */
    static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
    static constexpr unsigned int LONG_SCALE = 24;
    /** Historical estimates that are older than this aren't valid */
    static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;

    /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
    static constexpr double SHORT_DECAY = .962;
    /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
    static constexpr double MED_DECAY = .9952;
    /** Decay of .99931 is a half-life of 1008 blocks or about 1 week */
    static constexpr double LONG_DECAY = .99931;

    /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
    static constexpr double HALF_SUCCESS_PCT = .6;
    /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
    static constexpr double SUCCESS_PCT = .85;
    /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
    static constexpr double DOUBLE_SUCCESS_PCT = .95;

    /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
    static constexpr double SUFFICIENT_FEETXS = 0.1;
    /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
    static constexpr double SUFFICIENT_TXS_SHORT = 0.5;

    /** Minimum and Maximum values for tracking feerates
     * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
     * might ever want to track.  Historically this has been 1000 since it was
     * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
     * invalidates old estimates files. So leave it at 1000 unless it becomes
     * necessary to lower it, and then lower it substantially.
     */
    static constexpr double MIN_BUCKET_FEERATE = 1000;
    static constexpr double MAX_BUCKET_FEERATE = 1e7;

    /** Spacing of FeeRate buckets
     * We have to lump transactions into buckets based on feerate, but we want to be able
     * to give accurate estimates over a large range of potential feerates
     * Therefore it makes sense to exponentially space the buckets
     */
    static constexpr double FEE_SPACING = 1.05;

    const fs::path m_estimation_filepath;
public:
    /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
    CBlockPolicyEstimator(const fs::path& estimation_filepath);
    ~CBlockPolicyEstimator();

    /** Process all the transactions that have been included in a block */
    void processBlock(unsigned int nBlockHeight,
                      std::vector<const CTxMemPoolEntry*>& entries)
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Process a transaction accepted to the mempool*/
    void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Remove a transaction from the mempool tracking stats*/
    bool removeTx(uint256 hash, bool inBlock)
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** DEPRECATED. Return a feerate estimate */
    CFeeRate estimateFee(int confTarget) const
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Estimate feerate needed to get be included in a block within confTarget
     *  blocks. If no answer can be given at confTarget, return an estimate at
     *  the closest target where one can be given.  'conservative' estimates are
     *  valid over longer time horizons also.
     */
    CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Return a specific fee estimate calculation with a given success
     * threshold and time horizon, and optionally return detailed data about
     * calculation
     */
    CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon,
                            EstimationResult* result = nullptr) const
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Write estimation data to a file */
    bool Write(AutoFile& fileout) const
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Read estimation data from a file */
    bool Read(AutoFile& filein)
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
    void FlushUnconfirmed()
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Calculation of highest target that estimates are tracked for */
    unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

    /** Drop still unconfirmed transactions and record current estimations, if the fee estimation file is present. */
    void Flush()
        EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);

private:
    mutable Mutex m_cs_fee_estimator;

    unsigned int nBestSeenHeight GUARDED_BY(m_cs_fee_estimator){0};
    unsigned int firstRecordedHeight GUARDED_BY(m_cs_fee_estimator){0};
    unsigned int historicalFirst GUARDED_BY(m_cs_fee_estimator){0};
    unsigned int historicalBest GUARDED_BY(m_cs_fee_estimator){0};

    struct TxStatsInfo
    {
        unsigned int blockHeight{0};
        unsigned int bucketIndex{0};
        TxStatsInfo() {}
    };

    // map of txids to information about that transaction
    std::map<uint256, TxStatsInfo> mapMemPoolTxs GUARDED_BY(m_cs_fee_estimator);

    /** Classes to track historical data on transaction confirmations */
    std::unique_ptr<TxConfirmStats> feeStats PT_GUARDED_BY(m_cs_fee_estimator);
    std::unique_ptr<TxConfirmStats> shortStats PT_GUARDED_BY(m_cs_fee_estimator);
    std::unique_ptr<TxConfirmStats> longStats PT_GUARDED_BY(m_cs_fee_estimator);

    unsigned int trackedTxs GUARDED_BY(m_cs_fee_estimator){0};
    unsigned int untrackedTxs GUARDED_BY(m_cs_fee_estimator){0};

    std::vector<double> buckets GUARDED_BY(m_cs_fee_estimator); // The upper-bound of the range for the bucket (inclusive)
    std::map<double, unsigned int> bucketMap GUARDED_BY(m_cs_fee_estimator); // Map of bucket upper-bound to index into all vectors by bucket

    /** Process a transaction confirmed in a block*/
    bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);

    /** Helper for estimateSmartFee */
    double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
    /** Helper for estimateSmartFee */
    double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
    /** Number of blocks of data recorded while fee estimates have been running */
    unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
    /** Number of blocks of recorded fee estimate data represented in saved data file */
    unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
    /** Calculation of highest target that reasonable estimate can be provided for */
    unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);

    /** A non-thread-safe helper for the removeTx function */
    bool _removeTx(const uint256& hash, bool inBlock)
        EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
};

class FeeFilterRounder
{
private:
    static constexpr double MAX_FILTER_FEERATE = 1e7;
    /** FEE_FILTER_SPACING is just used to provide some quantization of fee
     * filter results.  Historically it reused FEE_SPACING, but it is completely
     * unrelated, and was made a separate constant so the two concepts are not
     * tied together */
    static constexpr double FEE_FILTER_SPACING = 1.1;

public:
    /** Create new FeeFilterRounder */
    explicit FeeFilterRounder(const CFeeRate& min_incremental_fee);

    /** Quantize a minimum fee for privacy purpose before broadcast. */
    CAmount round(CAmount currentMinFee) EXCLUSIVE_LOCKS_REQUIRED(!m_insecure_rand_mutex);

private:
    const std::set<double> m_fee_set;
    Mutex m_insecure_rand_mutex;
    FastRandomContext insecure_rand GUARDED_BY(m_insecure_rand_mutex);
};

#endif // BITCOIN_POLICY_FEES_H