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)
141 : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_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");
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");
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++) {
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);
979 feeset.insert(bucketBoundary);
985 std::set<double>::iterator
it =
feeset.lower_bound(currentMinFee);
989 return static_cast<CAmount>(*it);