Create new BlockPolicyEstimator for fee estimates

This class groups transactions that have been confirmed in blocks into buckets, based on either their fee or their priority.  Then for each bucket, the class calculates what percentage of the transactions were confirmed within various numbers of blocks.  It does this by keeping an exponentially decaying moving history for each bucket and confirm block count of the percentage of transactions in that bucket that were confirmed within that number of blocks.

-Eliminate txs which didn't have all inputs available at entry from fee/pri calcs

-Add dynamic breakpoints and tracking of confirmation delays in mempool transactions

-Remove old CMinerPolicyEstimator and CBlockAverage code

-New smartfees.py

-Pass a flag to the estimation code, using IsInitialBlockDownload as a proxy for when we are still catching up and we shouldn't be counting how many blocks it takes for transactions to be included.

-Add a policyestimator unit test

2 files changed, 805 insertions, 0 deletions

diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp
new file mode 100644
index 0000000000..b1491cec01
--- /dev/null
+++ b/src/policy/fees.cpp
@@ -0,0 +1,529 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2015 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "policy/fees.h"
+
+#include "amount.h"
+#include "primitives/transaction.h"
+#include "streams.h"
+#include "txmempool.h"
+#include "util.h"
+
+void TxConfirmStats::Initialize(std::vector<double>& defaultBuckets,
+                                unsigned int maxConfirms, double _decay, std::string _dataTypeString)
+{
+    decay = _decay;
+    dataTypeString = _dataTypeString;
+    for (unsigned int i = 0; i < defaultBuckets.size(); i++) {
+        buckets.push_back(defaultBuckets[i]);
+        bucketMap[defaultBuckets[i]] = i;
+    }
+    confAvg.resize(maxConfirms);
+    curBlockConf.resize(maxConfirms);
+    unconfTxs.resize(maxConfirms);
+    for (unsigned int i = 0; i < maxConfirms; i++) {
+        confAvg[i].resize(buckets.size());
+        curBlockConf[i].resize(buckets.size());
+        unconfTxs[i].resize(buckets.size());
+    }
+
+    oldUnconfTxs.resize(buckets.size());
+    curBlockTxCt.resize(buckets.size());
+    txCtAvg.resize(buckets.size());
+    curBlockVal.resize(buckets.size());
+    avg.resize(buckets.size());
+}
+
+// Zero out the data for the current block
+void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
+{
+    for (unsigned int j = 0; j < buckets.size(); j++) {
+        oldUnconfTxs[j] += unconfTxs[nBlockHeight%unconfTxs.size()][j];
+        unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
+        for (unsigned int i = 0; i < curBlockConf.size(); i++)
+            curBlockConf[i][j] = 0;
+        curBlockTxCt[j] = 0;
+        curBlockVal[j] = 0;
+    }
+}
+
+
+void TxConfirmStats::Record(int blocksToConfirm, double val)
+{
+    // blocksToConfirm is 1-based
+    if (blocksToConfirm < 1)
+        return;
+    unsigned int bucketindex = bucketMap.lower_bound(val)->second;
+    for (size_t i = blocksToConfirm; i <= curBlockConf.size(); i++) {
+        curBlockConf[i - 1][bucketindex]++;
+    }
+    curBlockTxCt[bucketindex]++;
+    curBlockVal[bucketindex] += val;
+}
+
+void TxConfirmStats::UpdateMovingAverages()
+{
+    for (unsigned int j = 0; j < buckets.size(); j++) {
+        for (unsigned int i = 0; i < confAvg.size(); i++)
+            confAvg[i][j] = confAvg[i][j] * decay + curBlockConf[i][j];
+        avg[j] = avg[j] * decay + curBlockVal[j];
+        txCtAvg[j] = txCtAvg[j] * decay + curBlockTxCt[j];
+    }
+}
+
+// returns -1 on error conditions
+double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
+                                         double successBreakPoint, bool requireGreater,
+                                         unsigned int nBlockHeight)
+{
+    // Counters for a bucket (or range of buckets)
+    double nConf = 0; // Number of tx's confirmed within the confTarget
+    double totalNum = 0; // Total number of tx's that were ever confirmed
+    int extraNum = 0;  // Number of tx's still in mempool for confTarget or longer
+
+    int maxbucketindex = buckets.size() - 1;
+
+    // requireGreater means we are looking for the lowest fee/priority such that all higher
+    // values pass, so we start at maxbucketindex (highest fee) and look at succesively
+    // smaller buckets until we reach failure.  Otherwise, we are looking for the highest
+    // fee/priority such that all lower values fail, and we go in the opposite direction.
+    unsigned int startbucket = requireGreater ? maxbucketindex : 0;
+    int step = requireGreater ? -1 : 1;
+
+    // We'll combine buckets until we have enough samples.
+    // The near and far variables will define the range we've combined
+    // The best variables are the last range we saw which still had a high
+    // enough confirmation rate to count as success.
+    // The cur variables are the current range we're counting.
+    unsigned int curNearBucket = startbucket;
+    unsigned int bestNearBucket = startbucket;
+    unsigned int curFarBucket = startbucket;
+    unsigned int bestFarBucket = startbucket;
+
+    bool foundAnswer = false;
+    unsigned int bins = unconfTxs.size();
+
+    // Start counting from highest(default) or lowest fee/pri transactions
+    for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) {
+        curFarBucket = bucket;
+        nConf += confAvg[confTarget - 1][bucket];
+        totalNum += txCtAvg[bucket];
+        for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
+            extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket];
+        extraNum += oldUnconfTxs[bucket];
+        // If we have enough transaction data points in this range of buckets,
+        // we can test for success
+        // (Only count the confirmed data points, so that each confirmation count
+        // will be looking at the same amount of data and same bucket breaks)
+        if (totalNum >= sufficientTxVal / (1 - decay)) {
+            double curPct = nConf / (totalNum + extraNum);
+
+            // Check to see if we are no longer getting confirmed at the success rate
+            if (requireGreater && curPct < successBreakPoint)
+                break;
+            if (!requireGreater && curPct > successBreakPoint)
+                break;
+
+            // Otherwise update the cumulative stats, and the bucket variables
+            // and reset the counters
+            else {
+                foundAnswer = true;
+                nConf = 0;
+                totalNum = 0;
+                extraNum = 0;
+                bestNearBucket = curNearBucket;
+                bestFarBucket = curFarBucket;
+                curNearBucket = bucket + step;
+            }
+        }
+    }
+
+    double median = -1;
+    double txSum = 0;
+
+    // Calculate the "average" fee of the best bucket range that met success conditions
+    // Find the bucket with the median transaction and then report the average fee from that bucket
+    // This is a compromise between finding the median which we can't since we don't save all tx's
+    // and reporting the average which is less accurate
+    unsigned int minBucket = bestNearBucket < bestFarBucket ? bestNearBucket : bestFarBucket;
+    unsigned int maxBucket = bestNearBucket > bestFarBucket ? bestNearBucket : bestFarBucket;
+    for (unsigned int j = minBucket; j <= maxBucket; j++) {
+        txSum += txCtAvg[j];
+    }
+    if (foundAnswer && txSum != 0) {
+        txSum = txSum / 2;
+        for (unsigned int j = minBucket; j <= maxBucket; j++) {
+            if (txCtAvg[j] < txSum)
+                txSum -= txCtAvg[j];
+            else { // we're in the right bucket
+                median = avg[j] / txCtAvg[j];
+                break;
+            }
+        }
+    }
+
+    LogPrint("estimatefee", "%3d: For conf success %s %4.2f need %s %s: %12.5g from buckets %8g - %8g  Cur Bucket stats %6.2f%%  %8.1f/(%.1f+%d mempool)\n",
+             confTarget, requireGreater ? ">" : "<", successBreakPoint, dataTypeString,
+             requireGreater ? ">" : "<", median, buckets[minBucket], buckets[maxBucket],
+             100 * nConf / (totalNum + extraNum), nConf, totalNum, extraNum);
+
+    return median;
+}
+
+void TxConfirmStats::Write(CAutoFile& fileout)
+{
+    fileout << decay;
+    fileout << buckets;
+    fileout << avg;
+    fileout << txCtAvg;
+    fileout << confAvg;
+}
+
+void TxConfirmStats::Read(CAutoFile& filein)
+{
+    // Read data file into temporary variables and do some very basic sanity checking
+    std::vector<double> fileBuckets;
+    std::vector<double> fileAvg;
+    std::vector<std::vector<double> > fileConfAvg;
+    std::vector<double> fileTxCtAvg;
+    double fileDecay;
+    size_t maxConfirms;
+    size_t numBuckets;
+
+    filein >> fileDecay;
+    if (fileDecay <= 0 || fileDecay >= 1)
+        throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
+    filein >> fileBuckets;
+    numBuckets = fileBuckets.size();
+    if (numBuckets <= 1 || numBuckets > 1000)
+        throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 fee/pri buckets");
+    filein >> fileAvg;
+    if (fileAvg.size() != numBuckets)
+        throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri average bucket count");
+    filein >> fileTxCtAvg;
+    if (fileTxCtAvg.size() != numBuckets)
+        throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
+    filein >> fileConfAvg;
+    maxConfirms = fileConfAvg.size();
+    if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) // one week
+        throw std::runtime_error("Corrupt estimates file.  Must maintain estimates for between 1 and 1008 (one week) confirms");
+    for (unsigned int i = 0; i < maxConfirms; i++) {
+        if (fileConfAvg[i].size() != numBuckets)
+            throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri conf average bucket count");
+    }
+    // Now that we've processed the entire fee estimate data file and not
+    // thrown any errors, we can copy it to our data structures
+    decay = fileDecay;
+    buckets = fileBuckets;
+    avg = fileAvg;
+    confAvg = fileConfAvg;
+    txCtAvg = fileTxCtAvg;
+    bucketMap.clear();
+
+    // Resize the current block variables which aren't stored in the data file
+    // to match the number of confirms and buckets
+    curBlockConf.resize(maxConfirms);
+    for (unsigned int i = 0; i < maxConfirms; i++) {
+        curBlockConf[i].resize(buckets.size());
+    }
+    curBlockTxCt.resize(buckets.size());
+    curBlockVal.resize(buckets.size());
+
+    unconfTxs.resize(maxConfirms);
+    for (unsigned int i = 0; i < maxConfirms; i++) {
+        unconfTxs[i].resize(buckets.size());
+    }
+    oldUnconfTxs.resize(buckets.size());
+
+    for (unsigned int i = 0; i < buckets.size(); i++)
+        bucketMap[buckets[i]] = i;
+
+    LogPrint("estimatefee", "Reading estimates: %u %s buckets counting confirms up to %u blocks\n",
+             numBuckets, dataTypeString, maxConfirms);
+}
+
+unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
+{
+    unsigned int bucketindex = bucketMap.lower_bound(val)->second;
+    unsigned int blockIndex = nBlockHeight % unconfTxs.size();
+    unconfTxs[blockIndex][bucketindex]++;
+    LogPrint("estimatefee", "adding to %s\n", dataTypeString);
+    return bucketindex;
+}
+
+void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex)
+{
+    //nBestSeenHeight is not updated yet for the new block
+    int blocksAgo = nBestSeenHeight - entryHeight;
+    if (nBestSeenHeight == 0)  // the BlockPolicyEstimator hasn't seen any blocks yet
+        blocksAgo = 0;
+    if (blocksAgo < 0) {
+        LogPrint("estimatefee", "Blockpolicy error, blocks ago is negative for mempool tx\n");
+        return;  //This can't happen becasue we call this with our best seen height, no entries can have higher
+    }
+
+    if (blocksAgo >= (int)unconfTxs.size()) {
+        if (oldUnconfTxs[bucketindex] > 0)
+            oldUnconfTxs[bucketindex]--;
+        else
+            LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
+                     bucketindex);
+    }
+    else {
+        unsigned int blockIndex = entryHeight % unconfTxs.size();
+        if (unconfTxs[blockIndex][bucketindex] > 0)
+            unconfTxs[blockIndex][bucketindex]--;
+        else
+            LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
+                     blockIndex, bucketindex);
+    }
+}
+
+void CBlockPolicyEstimator::removeTx(uint256 hash)
+{
+    std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
+    if (pos == mapMemPoolTxs.end()) {
+        LogPrint("estimatefee", "Blockpolicy error mempool tx %s not found for removeTx\n",
+                 hash.ToString().c_str());
+        return;
+    }
+    TxConfirmStats *stats = pos->second.stats;
+    unsigned int entryHeight = pos->second.blockHeight;
+    unsigned int bucketIndex = pos->second.bucketIndex;
+
+    if (stats != NULL)
+        stats->removeTx(entryHeight, nBestSeenHeight, bucketIndex);
+    mapMemPoolTxs.erase(hash);
+}
+
+CBlockPolicyEstimator::CBlockPolicyEstimator(const CFeeRate& _minRelayFee)
+    : nBestSeenHeight(0)
+{
+    minTrackedFee = _minRelayFee < CFeeRate(MIN_FEERATE) ? CFeeRate(MIN_FEERATE) : _minRelayFee;
+    std::vector<double> vfeelist;
+    for (double bucketBoundary = minTrackedFee.GetFeePerK(); bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) {
+        vfeelist.push_back(bucketBoundary);
+    }
+    vfeelist.push_back(INF_FEERATE);
+    feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "FeeRate");
+
+    minTrackedPriority = AllowFreeThreshold() < MIN_PRIORITY ? MIN_PRIORITY : AllowFreeThreshold();
+    std::vector<double> vprilist;
+    for (double bucketBoundary = minTrackedPriority; bucketBoundary <= MAX_PRIORITY; bucketBoundary *= PRI_SPACING) {
+        vprilist.push_back(bucketBoundary);
+    }
+    vprilist.push_back(INF_PRIORITY);
+    priStats.Initialize(vprilist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "Priority");
+
+    feeUnlikely = CFeeRate(0);
+    feeLikely = CFeeRate(INF_FEERATE);
+    priUnlikely = 0;
+    priLikely = INF_PRIORITY;
+}
+
+bool CBlockPolicyEstimator::isFeeDataPoint(const CFeeRate &fee, double pri)
+{
+    if ((pri < minTrackedPriority && fee >= minTrackedFee) ||
+        (pri < priUnlikely && fee > feeLikely)) {
+        return true;
+    }
+    return false;
+}
+
+bool CBlockPolicyEstimator::isPriDataPoint(const CFeeRate &fee, double pri)
+{
+    if ((fee < minTrackedFee && pri >= minTrackedPriority) ||
+        (fee < feeUnlikely && pri > priLikely)) {
+        return true;
+    }
+    return false;
+}
+
+void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate)
+{
+    unsigned int txHeight = entry.GetHeight();
+    uint256 hash = entry.GetTx().GetHash();
+    if (mapMemPoolTxs[hash].stats != NULL) {
+        LogPrint("estimatefee", "Blockpolicy error mempool tx %s already being tracked\n",
+                 hash.ToString().c_str());
+	return;
+    }
+
+    if (txHeight < nBestSeenHeight) {
+        // Ignore side chains and re-orgs; assuming they are random they don't
+        // affect the estimate.  We'll potentially double count transactions in 1-block reorgs.
+        return;
+    }
+
+    // Only want to be updating estimates when our blockchain is synced,
+    // otherwise we'll miscalculate how many blocks its taking to get included.
+    if (!fCurrentEstimate)
+        return;
+
+    if (!entry.WasClearAtEntry()) {
+        // This transaction depends on other transactions in the mempool to
+        // be included in a block before it will be able to be included, so
+        // we shouldn't include it in our calculations
+        return;
+    }
+
+    // Fees are stored and reported as BTC-per-kb:
+    CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
+
+    // Want the priority of the tx at confirmation. However we don't know
+    // what that will be and its too hard to continue updating it
+    // so use starting priority as a proxy
+    double curPri = entry.GetPriority(txHeight);
+    mapMemPoolTxs[hash].blockHeight = txHeight;
+
+    LogPrint("estimatefee", "Blockpolicy mempool tx %s ", hash.ToString().substr(0,10));
+    // Record this as a priority estimate
+    if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) {
+        mapMemPoolTxs[hash].stats = &priStats;
+        mapMemPoolTxs[hash].bucketIndex =  priStats.NewTx(txHeight, curPri);
+    }
+    // Record this as a fee estimate
+    else if (isFeeDataPoint(feeRate, curPri)) {
+        mapMemPoolTxs[hash].stats = &feeStats;
+        mapMemPoolTxs[hash].bucketIndex = feeStats.NewTx(txHeight, (double)feeRate.GetFeePerK());
+    }
+    else {
+        LogPrint("estimatefee", "not adding\n");
+    }
+}
+
+void CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry)
+{
+    if (!entry.WasClearAtEntry()) {
+        // This transaction depended on other transactions in the mempool to
+        // be included in a block before it was able to be included, so
+        // we shouldn't include it in our calculations
+        return;
+    }
+
+    // How many blocks did it take for miners to include this transaction?
+    // blocksToConfirm is 1-based, so a transaction included in the earliest
+    // possible block has confirmation count of 1
+    int blocksToConfirm = nBlockHeight - entry.GetHeight();
+    if (blocksToConfirm <= 0) {
+        // This can't happen because we don't process transactions from a block with a height
+        // lower than our greatest seen height
+        LogPrint("estimatefee", "Blockpolicy error Transaction had negative blocksToConfirm\n");
+        return;
+    }
+
+    // Fees are stored and reported as BTC-per-kb:
+    CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
+
+    // Want the priority of the tx at confirmation.  The priority when it
+    // entered the mempool could easily be very small and change quickly
+    double curPri = entry.GetPriority(nBlockHeight);
+
+    // Record this as a priority estimate
+    if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) {
+        priStats.Record(blocksToConfirm, curPri);
+    }
+    // Record this as a fee estimate
+    else if (isFeeDataPoint(feeRate, curPri)) {
+        feeStats.Record(blocksToConfirm, (double)feeRate.GetFeePerK());
+    }
+}
+
+void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
+                                         std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate)
+{
+    if (nBlockHeight <= nBestSeenHeight) {
+        // Ignore side chains and re-orgs; assuming they are random
+        // they don't affect the estimate.
+        // And if an attacker can re-org the chain at will, then
+        // you've got much bigger problems than "attacker can influence
+        // transaction fees."
+        return;
+    }
+    nBestSeenHeight = nBlockHeight;
+
+    // Only want to be updating estimates when our blockchain is synced,
+    // otherwise we'll miscalculate how many blocks its taking to get included.
+    if (!fCurrentEstimate)
+        return;
+
+    // Update the dynamic cutoffs
+    // a fee/priority is "likely" the reason your tx was included in a block if >85% of such tx's
+    // were confirmed in 2 blocks and is "unlikely" if <50% were confirmed in 10 blocks
+    LogPrint("estimatefee", "Blockpolicy recalculating dynamic cutoffs:\n");
+    priLikely = priStats.EstimateMedianVal(2, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBlockHeight);
+    if (priLikely == -1)
+        priLikely = INF_PRIORITY;
+
+    double feeLikelyEst = feeStats.EstimateMedianVal(2, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBlockHeight);
+    if (feeLikelyEst == -1)
+        feeLikely = CFeeRate(INF_FEERATE);
+    else
+        feeLikely = CFeeRate(feeLikelyEst);
+
+    priUnlikely = priStats.EstimateMedianVal(10, SUFFICIENT_PRITXS, UNLIKELY_PCT, false, nBlockHeight);
+    if (priUnlikely == -1)
+        priUnlikely = 0;
+
+    double feeUnlikelyEst = feeStats.EstimateMedianVal(10, SUFFICIENT_FEETXS, UNLIKELY_PCT, false, nBlockHeight);
+    if (feeUnlikelyEst == -1)
+        feeUnlikely = CFeeRate(0);
+    else
+        feeUnlikely = CFeeRate(feeUnlikelyEst);
+
+    // Clear the current block states
+    feeStats.ClearCurrent(nBlockHeight);
+    priStats.ClearCurrent(nBlockHeight);
+
+    // Repopulate the current block states
+    for (unsigned int i = 0; i < entries.size(); i++)
+        processBlockTx(nBlockHeight, entries[i]);
+
+    // Update all exponential averages with the current block states
+    feeStats.UpdateMovingAverages();
+    priStats.UpdateMovingAverages();
+
+    LogPrint("estimatefee", "Blockpolicy after updating estimates for %u confirmed entries, new mempool map size %u\n",
+             entries.size(), mapMemPoolTxs.size());
+}
+
+CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
+{
+    // Return failure if trying to analyze a target we're not tracking
+    if (confTarget <= 0 || (unsigned int)confTarget > feeStats.GetMaxConfirms())
+        return CFeeRate(0);
+
+    double median = feeStats.EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+
+    if (median < 0)
+        return CFeeRate(0);
+
+    return CFeeRate(median);
+}
+
+double CBlockPolicyEstimator::estimatePriority(int confTarget)
+{
+    // Return failure if trying to analyze a target we're not tracking
+    if (confTarget <= 0 || (unsigned int)confTarget > priStats.GetMaxConfirms())
+        return -1;
+
+    return priStats.EstimateMedianVal(confTarget, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+}
+
+void CBlockPolicyEstimator::Write(CAutoFile& fileout)
+{
+    fileout << nBestSeenHeight;
+    feeStats.Write(fileout);
+    priStats.Write(fileout);
+}
+
+void CBlockPolicyEstimator::Read(CAutoFile& filein)
+{
+    int nFileBestSeenHeight;
+    filein >> nFileBestSeenHeight;
+    feeStats.Read(filein);
+    priStats.Read(filein);
+    nBestSeenHeight = nFileBestSeenHeight;
+}
diff --git a/src/policy/fees.h b/src/policy/fees.h
new file mode 100644
index 0000000000..ce4d782566
--- /dev/null
+++ b/src/policy/fees.h
@@ -0,0 +1,276 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2015 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#ifndef BITCOIN_POLICYESTIMATOR_H
+#define BITCOIN_POLICYESTIMATOR_H
+
+#include "amount.h"
+#include "uint256.h"
+
+#include <map>
+#include <string>
+#include <vector>
+
+class CAutoFile;
+class CFeeRate;
+class CTxMemPoolEntry;
+
+/** \class CBlockPolicyEstimator
+ * The BlockPolicyEstimator is used for estimating the fee or priority 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 priorities or fees 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 fee/priority will be
+ * included in blocks before transactions of lower fee/priority.   So for
+ * example if you wanted to know what fee 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 with the highest fee transactions and verifying that a
+ * sufficiently high percentage of them were confirmed within 5 blocks and
+ * then you would look at the next highest fee bucket, and so on, stopping at
+ * the last bucket to pass the test.   The average fee of transactions in this
+ * bucket will give you an indication of the lowest fee you can put on a
+ * transaction and still have a sufficiently high chance of being confirmed
+ * within your desired 5 blocks.
+ *
+ * When a transaction enters the mempool or is included within a block we
+ * decide whether it can be used as a data point for fee estimation, priority
+ * estimation or neither.  If the value of exactly one of those properties was
+ * below the required minimum it can be used to estimate the other.  In
+ * addition, if a priori our estimation code would indicate that the
+ * transaction would be much more quickly included in a block because of one
+ * of the properties compared to the other, we can also decide to use it as
+ * an estimate for that property.
+ *
+ * Here is a brief description of the implementation for fee estimation.
+ * When a transaction that counts for fee estimation enters the mempool, we
+ * track the height of the block chain at entry.  Whenever a block comes in,
+ * we count the number of transactions in each bucket and the total amount of fee
+ * paid in each bucket. Then we calculate how many blocks Y it took each
+ * transaction to be mined and we track an array of counters in each bucket
+ * for how long it to took transactions to get confirmed from 1 to a max of 25
+ * and we increment all the counters from Y up to 25. This is because for any
+ * number Z>=Y the transaction was successfully mined within Z blocks.  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 fee
+ * bucket and the total number that were confirmed in each number 1-25 blocks
+ * or less for any bucket.   We save this history by keeping an exponentially
+ * decaying moving average of each one of these stats.  Furthermore we also
+ * keep track of the number unmined (in mempool) transactions in each bucket
+ * and for how many blocks they have been outstanding and use that to increase
+ * the number of transactions we've seen in that fee bucket when calculating
+ * an estimate for any number of confirmations below the number of blocks
+ * they've been outstanding.
+ */
+
+/**
+ * We will instantiate two instances of this class, one to track transactions
+ * that were included in a block due to fee, and one for tx's included due to
+ * priority.  We will lump transactions into a bucket according to their approximate
+ * fee or priority and then track how long it took for those txs to be included in a block
+ *
+ * The tracking of unconfirmed (mempool) transactions is completely independent of the
+ * historical tracking of transactions that have been confirmed in a block.
+ */
+class TxConfirmStats
+{
+private:
+    //Define the buckets we will group transactions into (both fee buckets and priority buckets)
+    std::vector<double> buckets;              // The upper-bound of the range for the bucket (inclusive)
+    std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
+
+    // For each bucket X:
+    // Count the total # of txs in each bucket
+    // Track the historical moving average of this total over blocks
+    std::vector<double> txCtAvg;
+    // and calcuate the total for the current block to update the moving average
+    std::vector<int> curBlockTxCt;
+
+    // Count the total # of txs confirmed within Y blocks in each bucket
+    // Track the historical moving average of theses totals over blocks
+    std::vector<std::vector<double> > confAvg; // confAvg[Y][X]
+    // and calcuate the totals for the current block to update the moving averages
+    std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X]
+
+    // Sum the total priority/fee of all tx's in each bucket
+    // Track the historical moving average of this total over blocks
+    std::vector<double> avg;
+    // and calculate the total for the current block to update the moving average
+    std::vector<double> curBlockVal;
+
+    // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
+    // Combine the total value with the tx counts to calculate the avg fee/priority per bucket
+
+    std::string dataTypeString;
+    double decay;
+
+    // Mempool counts of outstanding transactions
+    // For each bucket X, track the number of transactions in the mempool
+    // that are unconfirmed for each possible confirmation value Y
+    std::vector<std::vector<int> > unconfTxs;  //unconfTxs[Y][X]
+    // transactions still unconfirmed after MAX_CONFIRMS for each bucket
+    std::vector<int> oldUnconfTxs;
+
+public:
+    /**
+     * Initialize the data structures.  This is called by BlockPolicyEstimator's
+     * constructor with default values.
+     * @param defaultBuckets contains the upper limits for the bucket boundries
+     * @param maxConfirms max number of confirms to track
+     * @param decay how much to decay the historical moving average per block
+     * @param dataTypeString for logging purposes
+     */
+    void Initialize(std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay, std::string dataTypeString);
+
+    /** Clear the state of the curBlock variables to start counting for the new block */
+    void ClearCurrent(unsigned int nBlockHeight);
+
+    /**
+     * Record a new transaction data point in the current block stats
+     * @param blocksToConfirm the number of blocks it took this transaction to confirm
+     * @param val either the fee or the priority when entered of the transaction
+     * @warning blocksToConfirm is 1-based and has to be >= 1
+     */
+    void Record(int blocksToConfirm, double val);
+
+    /** Record a new transaction entering the mempool*/
+    unsigned int NewTx(unsigned int nBlockHeight, double val);
+
+    /** Remove a transaction from mempool tracking stats*/
+    void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
+                  unsigned int bucketIndex);
+
+    /** Update our estimates by decaying our historical moving average and updating
+        with the data gathered from the current block */
+    void UpdateMovingAverages();
+
+    /**
+     * Calculate a fee or priority estimate.  Find the lowest value bucket (or range of buckets
+     * to make sure we have enough data points) whose transactions still have sufficient likelihood
+     * of being confirmed within the target number of confirmations
+     * @param confTarget target number of confirmations
+     * @param sufficientTxVal required average number of transactions per block in a bucket range
+     * @param minSuccess the success probability we require
+     * @param requireGreater return the lowest fee/pri such that all higher values pass minSuccess OR
+     *        return the highest fee/pri such that all lower values fail minSuccess
+     * @param nBlockHeight the current block height
+     */
+    double EstimateMedianVal(int confTarget, double sufficientTxVal,
+                             double minSuccess, bool requireGreater, unsigned int nBlockHeight);
+
+    /** Return the max number of confirms we're tracking */
+    unsigned int GetMaxConfirms() { return confAvg.size(); }
+
+    /** Write state of estimation data to a file*/
+    void Write(CAutoFile& fileout);
+
+    /**
+     * Read saved state of estimation data from a file and replace all internal data structures and
+     * variables with this state.
+     */
+    void Read(CAutoFile& filein);
+};
+
+
+
+/** Track confirm delays up to 25 blocks, can't estimate beyond that */
+static const unsigned int MAX_BLOCK_CONFIRMS = 25;
+
+/** Decay of .998 is a half-life of 346 blocks or about 2.4 days */
+static const double DEFAULT_DECAY = .998;
+
+/** Require greater than 85% of X fee transactions to be confirmed within Y blocks for X to be big enough */
+static const double MIN_SUCCESS_PCT = .85;
+static const double UNLIKELY_PCT = .5;
+
+/** Require an avg of 1 tx in the combined fee bucket per block to have stat significance */
+static const double SUFFICIENT_FEETXS = 1;
+
+/** Require only an avg of 1 tx every 5 blocks in the combined pri bucket (way less pri txs) */
+static const double SUFFICIENT_PRITXS = .2;
+
+// Minimum and Maximum values for tracking fees and priorities
+static const double MIN_FEERATE = 10;
+static const double MAX_FEERATE = 1e7;
+static const double INF_FEERATE = MAX_MONEY;
+static const double MIN_PRIORITY = 10;
+static const double MAX_PRIORITY = 1e16;
+static const double INF_PRIORITY = 1e9 * MAX_MONEY;
+
+// We have to lump transactions into buckets based on fee or priority, but we want to be able
+// to give accurate estimates over a large range of potential fees and priorities
+// Therefore it makes sense to exponentially space the buckets
+/** Spacing of FeeRate buckets */
+static const double FEE_SPACING = 1.1;
+
+/** Spacing of Priority buckets */
+static const double PRI_SPACING = 2;
+
+/**
+ *  We want to be able to estimate fees or priorities 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
+{
+public:
+    /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
+    CBlockPolicyEstimator(const CFeeRate& minRelayFee);
+
+    /** Process all the transactions that have been included in a block */
+    void processBlock(unsigned int nBlockHeight,
+                      std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate);
+
+    /** Process a transaction confirmed in a block*/
+    void processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry);
+
+    /** Process a transaction accepted to the mempool*/
+    void processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate);
+
+    /** Remove a transaction from the mempool tracking stats*/
+    void removeTx(uint256 hash);
+
+    /** Is this transaction likely included in a block because of its fee?*/
+    bool isFeeDataPoint(const CFeeRate &fee, double pri);
+
+    /** Is this transaction likely included in a block because of its priority?*/
+    bool isPriDataPoint(const CFeeRate &fee, double pri);
+
+    /** Return a fee estimate */
+    CFeeRate estimateFee(int confTarget);
+
+    /** Return a priority estimate */
+    double estimatePriority(int confTarget);
+
+    /** Write estimation data to a file */
+    void Write(CAutoFile& fileout);
+
+    /** Read estimation data from a file */
+    void Read(CAutoFile& filein);
+
+private:
+    CFeeRate minTrackedFee; //! Passed to constructor to avoid dependency on main
+    double minTrackedPriority; //! Set to AllowFreeThreshold
+    unsigned int nBestSeenHeight;
+    struct TxStatsInfo
+    {
+        TxConfirmStats *stats;
+        unsigned int blockHeight;
+        unsigned int bucketIndex;
+        TxStatsInfo() : stats(NULL), blockHeight(0), bucketIndex(0) {}
+    };
+
+    // map of txids to information about that transaction
+    std::map<uint256, TxStatsInfo> mapMemPoolTxs;
+
+    /** Classes to track historical data on transaction confirmations */
+    TxConfirmStats feeStats, priStats;
+
+    /** Breakpoints to help determine whether a transaction was confirmed by priority or Fee */
+    CFeeRate feeLikely, feeUnlikely;
+    double priLikely, priUnlikely;
+};
+#endif /*BITCOIN_POLICYESTIMATOR_H */