Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2015 The Bitcoin 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_POLICYESTIMATOR_H
6 : #define BITCOIN_POLICYESTIMATOR_H
7 :
8 : #include "amount.h"
9 : #include "uint256.h"
10 :
11 : #include <map>
12 : #include <string>
13 : #include <vector>
14 :
15 : class CAutoFile;
16 : class CFeeRate;
17 : class CTxMemPoolEntry;
18 :
19 : /** \class CBlockPolicyEstimator
20 : * The BlockPolicyEstimator is used for estimating the fee or priority needed
21 : * for a transaction to be included in a block within a certain number of
22 : * blocks.
23 : *
24 : * At a high level the algorithm works by grouping transactions into buckets
25 : * based on having similar priorities or fees and then tracking how long it
26 : * takes transactions in the various buckets to be mined. It operates under
27 : * the assumption that in general transactions of higher fee/priority will be
28 : * included in blocks before transactions of lower fee/priority. So for
29 : * example if you wanted to know what fee you should put on a transaction to
30 : * be included in a block within the next 5 blocks, you would start by looking
31 : * at the bucket with with the highest fee transactions and verifying that a
32 : * sufficiently high percentage of them were confirmed within 5 blocks and
33 : * then you would look at the next highest fee bucket, and so on, stopping at
34 : * the last bucket to pass the test. The average fee of transactions in this
35 : * bucket will give you an indication of the lowest fee you can put on a
36 : * transaction and still have a sufficiently high chance of being confirmed
37 : * within your desired 5 blocks.
38 : *
39 : * When a transaction enters the mempool or is included within a block we
40 : * decide whether it can be used as a data point for fee estimation, priority
41 : * estimation or neither. If the value of exactly one of those properties was
42 : * below the required minimum it can be used to estimate the other. In
43 : * addition, if a priori our estimation code would indicate that the
44 : * transaction would be much more quickly included in a block because of one
45 : * of the properties compared to the other, we can also decide to use it as
46 : * an estimate for that property.
47 : *
48 : * Here is a brief description of the implementation for fee estimation.
49 : * When a transaction that counts for fee estimation enters the mempool, we
50 : * track the height of the block chain at entry. Whenever a block comes in,
51 : * we count the number of transactions in each bucket and the total amount of fee
52 : * paid in each bucket. Then we calculate how many blocks Y it took each
53 : * transaction to be mined and we track an array of counters in each bucket
54 : * for how long it to took transactions to get confirmed from 1 to a max of 25
55 : * and we increment all the counters from Y up to 25. This is because for any
56 : * number Z>=Y the transaction was successfully mined within Z blocks. We
57 : * want to save a history of this information, so at any time we have a
58 : * counter of the total number of transactions that happened in a given fee
59 : * bucket and the total number that were confirmed in each number 1-25 blocks
60 : * or less for any bucket. We save this history by keeping an exponentially
61 : * decaying moving average of each one of these stats. Furthermore we also
62 : * keep track of the number unmined (in mempool) transactions in each bucket
63 : * and for how many blocks they have been outstanding and use that to increase
64 : * the number of transactions we've seen in that fee bucket when calculating
65 : * an estimate for any number of confirmations below the number of blocks
66 : * they've been outstanding.
67 : */
68 :
69 : /**
70 : * We will instantiate two instances of this class, one to track transactions
71 : * that were included in a block due to fee, and one for tx's included due to
72 : * priority. We will lump transactions into a bucket according to their approximate
73 : * fee or priority and then track how long it took for those txs to be included in a block
74 : *
75 : * The tracking of unconfirmed (mempool) transactions is completely independent of the
76 : * historical tracking of transactions that have been confirmed in a block.
77 : */
78 4158 : class TxConfirmStats
79 : {
80 : private:
81 : //Define the buckets we will group transactions into (both fee buckets and priority buckets)
82 : std::vector<double> buckets; // The upper-bound of the range for the bucket (inclusive)
83 : std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
84 :
85 : // For each bucket X:
86 : // Count the total # of txs in each bucket
87 : // Track the historical moving average of this total over blocks
88 : std::vector<double> txCtAvg;
89 : // and calcuate the total for the current block to update the moving average
90 : std::vector<int> curBlockTxCt;
91 :
92 : // Count the total # of txs confirmed within Y blocks in each bucket
93 : // Track the historical moving average of theses totals over blocks
94 : std::vector<std::vector<double> > confAvg; // confAvg[Y][X]
95 : // and calcuate the totals for the current block to update the moving averages
96 : std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X]
97 :
98 : // Sum the total priority/fee of all tx's in each bucket
99 : // Track the historical moving average of this total over blocks
100 : std::vector<double> avg;
101 : // and calculate the total for the current block to update the moving average
102 : std::vector<double> curBlockVal;
103 :
104 : // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
105 : // Combine the total value with the tx counts to calculate the avg fee/priority per bucket
106 :
107 : std::string dataTypeString;
108 : double decay;
109 :
110 : // Mempool counts of outstanding transactions
111 : // For each bucket X, track the number of transactions in the mempool
112 : // that are unconfirmed for each possible confirmation value Y
113 : std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
114 : // transactions still unconfirmed after MAX_CONFIRMS for each bucket
115 : std::vector<int> oldUnconfTxs;
116 :
117 : public:
118 : /**
119 : * Initialize the data structures. This is called by BlockPolicyEstimator's
120 : * constructor with default values.
121 : * @param defaultBuckets contains the upper limits for the bucket boundaries
122 : * @param maxConfirms max number of confirms to track
123 : * @param decay how much to decay the historical moving average per block
124 : * @param dataTypeString for logging purposes
125 : */
126 : void Initialize(std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay, std::string dataTypeString);
127 :
128 : /** Clear the state of the curBlock variables to start counting for the new block */
129 : void ClearCurrent(unsigned int nBlockHeight);
130 :
131 : /**
132 : * Record a new transaction data point in the current block stats
133 : * @param blocksToConfirm the number of blocks it took this transaction to confirm
134 : * @param val either the fee or the priority when entered of the transaction
135 : * @warning blocksToConfirm is 1-based and has to be >= 1
136 : */
137 : void Record(int blocksToConfirm, double val);
138 :
139 : /** Record a new transaction entering the mempool*/
140 : unsigned int NewTx(unsigned int nBlockHeight, double val);
141 :
142 : /** Remove a transaction from mempool tracking stats*/
143 : void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
144 : unsigned int bucketIndex);
145 :
146 : /** Update our estimates by decaying our historical moving average and updating
147 : with the data gathered from the current block */
148 : void UpdateMovingAverages();
149 :
150 : /**
151 : * Calculate a fee or priority estimate. Find the lowest value bucket (or range of buckets
152 : * to make sure we have enough data points) whose transactions still have sufficient likelihood
153 : * of being confirmed within the target number of confirmations
154 : * @param confTarget target number of confirmations
155 : * @param sufficientTxVal required average number of transactions per block in a bucket range
156 : * @param minSuccess the success probability we require
157 : * @param requireGreater return the lowest fee/pri such that all higher values pass minSuccess OR
158 : * return the highest fee/pri such that all lower values fail minSuccess
159 : * @param nBlockHeight the current block height
160 : */
161 : double EstimateMedianVal(int confTarget, double sufficientTxVal,
162 : double minSuccess, bool requireGreater, unsigned int nBlockHeight);
163 :
164 : /** Return the max number of confirms we're tracking */
165 44377238 : unsigned int GetMaxConfirms() { return confAvg.size(); }
166 :
167 : /** Write state of estimation data to a file*/
168 : void Write(CAutoFile& fileout);
169 :
170 : /**
171 : * Read saved state of estimation data from a file and replace all internal data structures and
172 : * variables with this state.
173 : */
174 : void Read(CAutoFile& filein);
175 : };
176 :
177 :
178 :
179 : /** Track confirm delays up to 25 blocks, can't estimate beyond that */
180 : static const unsigned int MAX_BLOCK_CONFIRMS = 25;
181 :
182 : /** Decay of .998 is a half-life of 346 blocks or about 2.4 days */
183 : static const double DEFAULT_DECAY = .998;
184 :
185 : /** Require greater than 85% of X fee transactions to be confirmed within Y blocks for X to be big enough */
186 : static const double MIN_SUCCESS_PCT = .85;
187 : static const double UNLIKELY_PCT = .5;
188 :
189 : /** Require an avg of 1 tx in the combined fee bucket per block to have stat significance */
190 : static const double SUFFICIENT_FEETXS = 1;
191 :
192 : /** Require only an avg of 1 tx every 5 blocks in the combined pri bucket (way less pri txs) */
193 : static const double SUFFICIENT_PRITXS = .2;
194 :
195 : // Minimum and Maximum values for tracking fees and priorities
196 : static const double MIN_FEERATE = 10;
197 : static const double MAX_FEERATE = 1e7;
198 : static const double INF_FEERATE = MAX_MONEY;
199 : static const double MIN_PRIORITY = 10;
200 : static const double MAX_PRIORITY = 1e16;
201 : static const double INF_PRIORITY = 1e9 * MAX_MONEY;
202 :
203 : // We have to lump transactions into buckets based on fee or priority, but we want to be able
204 : // to give accurate estimates over a large range of potential fees and priorities
205 : // Therefore it makes sense to exponentially space the buckets
206 : /** Spacing of FeeRate buckets */
207 : static const double FEE_SPACING = 1.1;
208 :
209 : /** Spacing of Priority buckets */
210 : static const double PRI_SPACING = 2;
211 :
212 : /**
213 : * We want to be able to estimate fees or priorities that are needed on tx's to be included in
214 : * a certain number of blocks. Every time a block is added to the best chain, this class records
215 : * stats on the transactions included in that block
216 : */
217 198 : class CBlockPolicyEstimator
218 : {
219 : public:
220 : /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
221 : CBlockPolicyEstimator(const CFeeRate& minRelayFee);
222 :
223 : /** Process all the transactions that have been included in a block */
224 : void processBlock(unsigned int nBlockHeight,
225 : std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate);
226 :
227 : /** Process a transaction confirmed in a block*/
228 : void processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry);
229 :
230 : /** Process a transaction accepted to the mempool*/
231 : void processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate);
232 :
233 : /** Remove a transaction from the mempool tracking stats*/
234 : void removeTx(uint256 hash);
235 :
236 : /** Is this transaction likely included in a block because of its fee?*/
237 : bool isFeeDataPoint(const CFeeRate &fee, double pri);
238 :
239 : /** Is this transaction likely included in a block because of its priority?*/
240 : bool isPriDataPoint(const CFeeRate &fee, double pri);
241 :
242 : /** Return a fee estimate */
243 : CFeeRate estimateFee(int confTarget);
244 :
245 : /** Return a priority estimate */
246 : double estimatePriority(int confTarget);
247 :
248 : /** Write estimation data to a file */
249 : void Write(CAutoFile& fileout);
250 :
251 : /** Read estimation data from a file */
252 : void Read(CAutoFile& filein);
253 :
254 : private:
255 : CFeeRate minTrackedFee; //! Passed to constructor to avoid dependency on main
256 : double minTrackedPriority; //! Set to AllowFreeThreshold
257 : unsigned int nBestSeenHeight;
258 : struct TxStatsInfo
259 : {
260 : TxConfirmStats *stats;
261 : unsigned int blockHeight;
262 : unsigned int bucketIndex;
263 0 : TxStatsInfo() : stats(NULL), blockHeight(0), bucketIndex(0) {}
264 : };
265 :
266 : // map of txids to information about that transaction
267 : std::map<uint256, TxStatsInfo> mapMemPoolTxs;
268 :
269 : /** Classes to track historical data on transaction confirmations */
270 : TxConfirmStats feeStats, priStats;
271 :
272 : /** Breakpoints to help determine whether a transaction was confirmed by priority or Fee */
273 : CFeeRate feeLikely, feeUnlikely;
274 : double priLikely, priUnlikely;
275 : };
276 : #endif /*BITCOIN_POLICYESTIMATOR_H */
|
