86 TxConfirmStats(
const std::vector<double>& defaultBuckets,
const std::map<double, unsigned int>& defaultBucketMap,
87 unsigned int maxPeriods,
double decay,
unsigned int scale);
98 void Record(
int blocksToConfirm,
double val);
101 unsigned int NewTx(
unsigned int nBlockHeight,
double val);
104 void removeTx(
unsigned int entryHeight,
unsigned int nBestSeenHeight,
105 unsigned int bucketIndex,
bool inBlock);
121 double minSuccess,
unsigned int nBlockHeight,
134 void Read(
CAutoFile& filein,
int nFileVersion,
size_t numBuckets);
139 const std::map<double, unsigned int>& defaultBucketMap,
140 unsigned int maxPeriods,
double _decay,
unsigned int _scale)
143 assert(_scale != 0 &&
"_scale must be non-zero");
146 for (
unsigned int i = 0; i < maxPeriods; i++) {
160 for (
unsigned int i = 0; i <
unconfTxs.size(); i++) {
169 for (
unsigned int j = 0; j <
buckets.size(); j++) {
179 if (blocksToConfirm < 1)
181 int periodsToConfirm = (blocksToConfirm +
scale - 1) /
scale;
182 unsigned int bucketindex =
bucketMap.lower_bound(feerate)->second;
183 for (
size_t i = periodsToConfirm; i <=
confAvg.size(); i++) {
193 for (
unsigned int j = 0; j <
buckets.size(); j++) {
194 for (
unsigned int i = 0; i <
confAvg.size(); i++) {
205 double successBreakPoint,
unsigned int nBlockHeight,
213 const int periodTarget = (confTarget +
scale - 1) /
scale;
214 const int maxbucketindex =
buckets.size() - 1;
221 unsigned int curNearBucket = maxbucketindex;
222 unsigned int bestNearBucket = maxbucketindex;
223 unsigned int curFarBucket = maxbucketindex;
224 unsigned int bestFarBucket = maxbucketindex;
226 bool foundAnswer =
false;
228 bool newBucketRange =
true;
234 for (
int bucket = maxbucketindex; bucket >= 0; --bucket) {
235 if (newBucketRange) {
236 curNearBucket = bucket;
237 newBucketRange =
false;
239 curFarBucket = bucket;
240 nConf +=
confAvg[periodTarget - 1][bucket];
242 failNum +=
failAvg[periodTarget - 1][bucket];
243 for (
unsigned int confct = confTarget; confct <
GetMaxConfirms(); confct++)
244 extraNum +=
unconfTxs[(nBlockHeight - confct) % bins][bucket];
250 if (totalNum >= sufficientTxVal / (1 -
decay)) {
251 double curPct = nConf / (totalNum + failNum + extraNum);
254 if (curPct < successBreakPoint) {
255 if (passing ==
true) {
257 unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
258 unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
259 failBucket.
start = failMinBucket ?
buckets[failMinBucket - 1] : 0;
283 bestNearBucket = curNearBucket;
284 bestFarBucket = curFarBucket;
285 newBucketRange =
true;
297 unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
298 unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
299 for (
unsigned int j = minBucket; j <= maxBucket; j++) {
302 if (foundAnswer && txSum != 0) {
304 for (
unsigned int j = minBucket; j <= maxBucket; j++) {
313 passBucket.
start = minBucket ?
buckets[minBucket-1] : 0;
318 if (passing && !newBucketRange) {
319 unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
320 unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
321 failBucket.
start = failMinBucket ?
buckets[failMinBucket - 1] : 0;
329 float passed_within_target_perc = 0.0;
330 float failed_within_target_perc = 0.0;
338 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",
339 confTarget, 100.0 * successBreakPoint,
decay,
340 median, passBucket.
start, passBucket.
end,
341 passed_within_target_perc,
344 failed_within_target_perc,
349 result->
pass = passBucket;
350 result->
fail = failBucket;
372 size_t maxConfirms, maxPeriods;
376 if (decay <= 0 || decay >= 1) {
377 throw std::runtime_error(
"Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
381 throw std::runtime_error(
"Corrupt estimates file. Scale must be non-zero");
385 if (m_feerate_avg.size() != numBuckets) {
386 throw std::runtime_error(
"Corrupt estimates file. Mismatch in feerate average bucket count");
389 if (txCtAvg.size() != numBuckets) {
390 throw std::runtime_error(
"Corrupt estimates file. Mismatch in tx count bucket count");
393 maxPeriods = confAvg.size();
394 maxConfirms = scale * maxPeriods;
396 if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) {
397 throw std::runtime_error(
"Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
399 for (
unsigned int i = 0; i < maxPeriods; i++) {
400 if (confAvg[i].size() != numBuckets) {
401 throw std::runtime_error(
"Corrupt estimates file. Mismatch in feerate conf average bucket count");
406 if (maxPeriods != failAvg.size()) {
407 throw std::runtime_error(
"Corrupt estimates file. Mismatch in confirms tracked for failures");
409 for (
unsigned int i = 0; i < maxPeriods; i++) {
410 if (failAvg[i].size() != numBuckets) {
411 throw std::runtime_error(
"Corrupt estimates file. Mismatch in one of failure average bucket counts");
420 numBuckets, maxConfirms);
425 unsigned int bucketindex =
bucketMap.lower_bound(val)->second;
426 unsigned int blockIndex = nBlockHeight %
unconfTxs.size();
434 int blocksAgo = nBestSeenHeight - entryHeight;
435 if (nBestSeenHeight == 0)
442 if (blocksAgo >= (
int)
unconfTxs.size()) {
451 unsigned int blockIndex = entryHeight %
unconfTxs.size();
452 if (
unconfTxs[blockIndex][bucketindex] > 0) {
456 blockIndex, bucketindex);
459 if (!inBlock && (
unsigned int)blocksAgo >=
scale) {
461 unsigned int periodsAgo = blocksAgo /
scale;
462 for (
size_t i = 0; i < periodsAgo && i <
failAvg.size(); i++) {
475 LOCK(m_cs_fee_estimator);
476 std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
477 if (pos != mapMemPoolTxs.end()) {
478 feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
479 shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
480 longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
481 mapMemPoolTxs.erase(hash);
489 : nBestSeenHeight(0), firstRecordedHeight(0), historicalFirst(0), historicalBest(0), trackedTxs(0), untrackedTxs(0)
492 size_t bucketIndex = 0;
495 buckets.push_back(bucketBoundary);
496 bucketMap[bucketBoundary] = bucketIndex;
500 assert(bucketMap.size() == buckets.size());
510 LogPrintf(
"Failed to read fee estimates from %s. Continue anyway.\n", est_filepath.string());
521 unsigned int txHeight = entry.
GetHeight();
523 if (mapMemPoolTxs.count(hash)) {
529 if (txHeight != nBestSeenHeight) {
539 if (!validFeeEstimate) {
548 mapMemPoolTxs[hash].blockHeight = txHeight;
549 unsigned int bucketIndex = feeStats->NewTx(txHeight, (
double)feeRate.GetFeePerK());
550 mapMemPoolTxs[hash].bucketIndex = bucketIndex;
551 unsigned int bucketIndex2 = shortStats->NewTx(txHeight, (
double)feeRate.GetFeePerK());
552 assert(bucketIndex == bucketIndex2);
553 unsigned int bucketIndex3 = longStats->NewTx(txHeight, (
double)feeRate.GetFeePerK());
554 assert(bucketIndex == bucketIndex3);
567 int blocksToConfirm = nBlockHeight - entry->
GetHeight();
568 if (blocksToConfirm <= 0) {
578 feeStats->Record(blocksToConfirm, (
double)feeRate.GetFeePerK());
579 shortStats->Record(blocksToConfirm, (
double)feeRate.GetFeePerK());
580 longStats->Record(blocksToConfirm, (
double)feeRate.GetFeePerK());
585 std::vector<const CTxMemPoolEntry*>& entries)
588 if (nBlockHeight <= nBestSeenHeight) {
600 nBestSeenHeight = nBlockHeight;
603 feeStats->ClearCurrent(nBlockHeight);
604 shortStats->ClearCurrent(nBlockHeight);
605 longStats->ClearCurrent(nBlockHeight);
608 feeStats->UpdateMovingAverages();
609 shortStats->UpdateMovingAverages();
610 longStats->UpdateMovingAverages();
612 unsigned int countedTxs = 0;
614 for (
const auto& entry : entries) {
619 if (firstRecordedHeight == 0 && countedTxs > 0) {
620 firstRecordedHeight = nBestSeenHeight;
625 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",
626 countedTxs, entries.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size(),
648 stats = shortStats.get();
653 stats = feeStats.get();
657 stats = longStats.get();
665 if (confTarget <= 0 || (
unsigned int)confTarget > stats->
GetMaxConfirms())
667 if (successThreshold > 1)
670 double median = stats->
EstimateMedianVal(confTarget, sufficientTxs, successThreshold, nBestSeenHeight, result);
683 return shortStats->GetMaxConfirms();
686 return feeStats->GetMaxConfirms();
689 return longStats->GetMaxConfirms();
697 if (firstRecordedHeight == 0)
return 0;
698 assert(nBestSeenHeight >= firstRecordedHeight);
700 return nBestSeenHeight - firstRecordedHeight;
705 if (historicalFirst == 0)
return 0;
706 assert(historicalBest >= historicalFirst);
710 return historicalBest - historicalFirst;
725 double estimate = -1;
726 if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
728 if (confTarget <= shortStats->GetMaxConfirms()) {
729 estimate = shortStats->EstimateMedianVal(confTarget,
SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, result);
731 else if (confTarget <= feeStats->GetMaxConfirms()) {
732 estimate = feeStats->EstimateMedianVal(confTarget,
SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
735 estimate = longStats->EstimateMedianVal(confTarget,
SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
737 if (checkShorterHorizon) {
740 if (confTarget > feeStats->GetMaxConfirms()) {
741 double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(),
SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, &tempResult);
742 if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
744 if (result) *result = tempResult;
747 if (confTarget > shortStats->GetMaxConfirms()) {
748 double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(),
SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, &tempResult);
749 if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
751 if (result) *result = tempResult;
764 double estimate = -1;
766 if (doubleTarget <= shortStats->GetMaxConfirms()) {
769 if (doubleTarget <= feeStats->GetMaxConfirms()) {
771 if (longEstimate > estimate) {
772 estimate = longEstimate;
773 if (result) *result = tempResult;
799 if (confTarget <= 0 || (
unsigned int)confTarget > longStats->GetMaxConfirms()) {
804 if (confTarget == 1) confTarget = 2;
807 if ((
unsigned int)confTarget > maxUsableEstimate) {
808 confTarget = maxUsableEstimate;
812 if (confTarget <= 1)
return CFeeRate(0);
827 feeCalc->
est = tempResult;
832 if (actualEst > median) {
835 feeCalc->
est = tempResult;
840 if (doubleEst > median) {
843 feeCalc->
est = tempResult;
848 if (conservative || median == -1) {
850 if (consEst > median) {
853 feeCalc->
est = tempResult;
870 LogPrintf(
"Failed to write fee estimates to %s. Continue anyway.\n", est_filepath.string());
880 fileout << nBestSeenHeight;
882 fileout << firstRecordedHeight << nBestSeenHeight;
885 fileout << historicalFirst << historicalBest;
888 feeStats->Write(fileout);
889 shortStats->Write(fileout);
890 longStats->Write(fileout);
892 catch (
const std::exception&) {
893 LogPrintf(
"CBlockPolicyEstimator::Write(): unable to write policy estimator data (non-fatal)\n");
903 int nVersionRequired, nVersionThatWrote;
904 filein >> nVersionRequired >> nVersionThatWrote;
906 throw std::runtime_error(
strprintf(
"up-version (%d) fee estimate file", nVersionRequired));
911 unsigned int nFileBestSeenHeight;
912 filein >> nFileBestSeenHeight;
914 if (nVersionRequired < 149900) {
915 LogPrintf(
"%s: incompatible old fee estimation data (non-fatal). Version: %d\n", __func__, nVersionRequired);
917 unsigned int nFileHistoricalFirst, nFileHistoricalBest;
918 filein >> nFileHistoricalFirst >> nFileHistoricalBest;
919 if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
920 throw std::runtime_error(
"Corrupt estimates file. Historical block range for estimates is invalid");
922 std::vector<double> fileBuckets;
923 filein >> fileBuckets;
924 size_t numBuckets = fileBuckets.size();
925 if (numBuckets <= 1 || numBuckets > 1000) {
926 throw std::runtime_error(
"Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
932 fileFeeStats->Read(filein, nVersionThatWrote, numBuckets);
933 fileShortStats->Read(filein, nVersionThatWrote, numBuckets);
934 fileLongStats->Read(filein, nVersionThatWrote, numBuckets);
938 buckets = fileBuckets;
940 for (
unsigned int i = 0; i < buckets.size(); i++) {
941 bucketMap[buckets[i]] = i;
945 feeStats = std::move(fileFeeStats);
946 shortStats = std::move(fileShortStats);
947 longStats = std::move(fileLongStats);
949 nBestSeenHeight = nFileBestSeenHeight;
950 historicalFirst = nFileHistoricalFirst;
951 historicalBest = nFileHistoricalBest;
954 catch (
const std::exception& e) {
955 LogPrintf(
"CBlockPolicyEstimator::Read(): unable to read policy estimator data (non-fatal): %s\n",e.what());
964 size_t num_entries = mapMemPoolTxs.size();
966 while (!mapMemPoolTxs.empty()) {
967 auto mi = mapMemPoolTxs.begin();
971 LogPrint(
BCLog::ESTIMATEFEE,
"Recorded %u unconfirmed txs from mempool in %gs\n", num_entries, (endclear - startclear)*0.000001);
978 for (
double bucketBoundary = minFeeLimit; bucketBoundary <= MAX_FILTER_FEERATE; bucketBoundary *= FEE_FILTER_SPACING) {
979 feeset.insert(bucketBoundary);
985 std::set<double>::iterator
it = feeset.lower_bound(currentMinFee);
986 if ((it != feeset.begin() && insecure_rand.rand32() % 3 != 0) || it == feeset.end()) {
989 return static_cast<CAmount>(*it);
static constexpr double MED_DECAY
Decay of .9952 is a half-life of 144 blocks or about 1 day.
std::vector< std::vector< double > > failAvg
std::deque< CInv >::iterator it
bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry *entry) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Process a transaction confirmed in a block.
#define LogPrint(category,...)
FILE * fopen(const fs::path &p, const char *mode)
static constexpr double MAX_BUCKET_FEERATE
static constexpr double HALF_SUCCESS_PCT
Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks.
static constexpr unsigned int MED_BLOCK_PERIODS
Track confirm delays up to 48 blocks for medium horizon.
bool removeTx(uint256 hash, bool inBlock)
Remove a transaction from the mempool tracking stats.
CBlockPolicyEstimator()
Create new BlockPolicyEstimator and initialize stats tracking classes with default values...
TxConfirmStats(const std::vector< double > &defaultBuckets, const std::map< double, unsigned int > &defaultBucketMap, unsigned int maxPeriods, double decay, unsigned int scale)
Create new TxConfirmStats.
double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Helper for estimateSmartFee.
bool Write(CAutoFile &fileout) const
Write estimation data to a file.
void FlushUnconfirmed()
Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool...
unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Number of blocks of recorded fee estimate data represented in saved data file.
We will instantiate an instance of this class to track transactions that were included in a block...
void Flush()
Drop still unconfirmed transactions and record current estimations, if the fee estimation file is pre...
static void LogPrintf(const char *fmt, const Args &... args)
std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
static constexpr double DOUBLE_SUCCESS_PCT
Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks.
static constexpr double FEE_SPACING
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.
unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Calculation of highest target that reasonable estimate can be provided for.
void Record(int blocksToConfirm, double val)
Record a new transaction data point in the current block stats.
static constexpr double MIN_BUCKET_FEERATE
Minimum and Maximum values for tracking feerates The MIN_BUCKET_FEERATE should just be set to the low...
void resizeInMemoryCounters(size_t newbuckets)
bool IsNull() const
Return true if the wrapped FILE* is nullptr, false otherwise.
void ClearCurrent(unsigned int nBlockHeight)
Roll the circular buffer for unconfirmed txs.
static constexpr double SUFFICIENT_TXS_SHORT
Require an avg of 0.5 tx when using short decay since there are fewer blocks considered.
CTxMemPoolEntry stores data about the corresponding transaction, as well as data about all in-mempool...
int64_t CAmount
Amount in satoshis (Can be negative)
static constexpr double SUCCESS_PCT
Require greater than 85% of X feerate transactions to be confirmed within Y blocks.
void Read(CAutoFile &filein, int nFileVersion, size_t numBuckets)
Read saved state of estimation data from a file and replace all internal data structures and variable...
double EstimateMedianVal(int confTarget, double sufficientTxVal, double minSuccess, unsigned int nBlockHeight, EstimationResult *result=nullptr) const
Calculate a feerate estimate.
const std::map< double, unsigned int > & bucketMap
static constexpr unsigned int SHORT_SCALE
static constexpr double LONG_DECAY
Decay of .99931 is a half-life of 1008 blocks or about 1 week.
static const char * FEE_ESTIMATES_FILENAME
std::vector< std::vector< double > > confAvg
unsigned int NewTx(unsigned int nBlockHeight, double val)
Record a new transaction entering the mempool.
unsigned int GetHeight() const
CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult *result=nullptr) const
Return a specific fee estimate calculation with a given success threshold and time horizon...
void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketIndex, bool inBlock)
Remove a transaction from mempool tracking stats.
const uint256 & GetHash() const
const CAmount & GetFee() const
CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
Estimate feerate needed to get be included in a block within confTarget blocks.
const fs::path & GetDataDir(bool fNetSpecific)
const std::vector< double > & buckets
unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Number of blocks of data recorded while fee estimates have been running.
double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Helper for estimateSmartFee.
std::string ToString() const
FeeFilterRounder(const CFeeRate &minIncrementalFee)
Create new FeeFilterRounder.
CFeeRate estimateFee(int confTarget) const
DEPRECATED.
static constexpr unsigned int LONG_SCALE
int64_t GetTimeMicros()
Returns the system time (not mockable)
std::vector< std::vector< int > > unconfTxs
unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
Calculation of highest target that estimates are tracked for.
static constexpr unsigned int MED_SCALE
static const unsigned int OLDEST_ESTIMATE_HISTORY
Historical estimates that are older than this aren't valid.
std::vector< int > oldUnconfTxs
void processBlock(unsigned int nBlockHeight, std::vector< const CTxMemPoolEntry *> &entries)
Process all the transactions that have been included in a block.
const CTransaction & GetTx() const
bool Read(CAutoFile &filein)
Read estimation data from a file.
unsigned int GetMaxConfirms() const
Return the max number of confirms we're tracking.
static constexpr unsigned int LONG_BLOCK_PERIODS
Track confirm delays up to 1008 blocks for long horizon.
Fee rate in satoshis per kilobyte: CAmount / kB.
RecursiveMutex m_cs_fee_estimator
static constexpr unsigned int SHORT_BLOCK_PERIODS
Track confirm delays up to 12 blocks for short horizon.
static constexpr double INF_FEERATE
static constexpr double SUFFICIENT_FEETXS
Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance.
std::vector< double > m_feerate_avg
CAmount round(CAmount currentMinFee)
Quantize a minimum fee for privacy purpose before broadcast.
static constexpr double SHORT_DECAY
Decay of .962 is a half-life of 18 blocks or about 3 hours.
void Write(CAutoFile &fileout) const
Write state of estimation data to a file.
std::vector< double > txCtAvg
void UpdateMovingAverages()
Update our estimates by decaying our historical moving average and updating with the data gathered fr...
static const int CLIENT_VERSION
bitcoind-res.rc includes this file, but it cannot cope with real c++ code.
CAmount GetFeePerK() const
Return the fee in satoshis for a size of 1000 bytes.
Non-refcounted RAII wrapper for FILE*.
void processTransaction(const CTxMemPoolEntry &entry, bool validFeeEstimate)
Process a transaction accepted to the mempool.