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

8 files changed, 1039 insertions, 363 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 37184b6286..9d9934618e 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -105,6 +105,7 @@ BITCOIN_CORE_H = \
   netbase.h \
   net.h \
   noui.h \
+  policy/fees.h \
   pow.h \
   primitives/block.h \
   primitives/transaction.h \
@@ -181,6 +182,7 @@ libbitcoin_server_a_SOURCES = \
   miner.cpp \
   net.cpp \
   noui.cpp \
+  policy/fees.cpp \
   pow.cpp \
   rest.cpp \
   rpcblockchain.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 52ff3f224f..6c14859d3c 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -56,6 +56,7 @@ BITCOIN_TESTS =\
   test/multisig_tests.cpp \
   test/netbase_tests.cpp \
   test/pmt_tests.cpp \
+  test/policyestimator_tests.cpp \
   test/pow_tests.cpp \
   test/rpc_tests.cpp \
   test/sanity_tests.cpp \
diff --git a/src/main.cpp b/src/main.cpp
index 4352c719a1..45e6e4d25d 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -974,7 +974,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         CAmount nFees = nValueIn-nValueOut;
         double dPriority = view.GetPriority(tx, chainActive.Height());
 
-        CTxMemPoolEntry entry(tx, nFees, GetTime(), dPriority, chainActive.Height());
+        CTxMemPoolEntry entry(tx, nFees, GetTime(), dPriority, chainActive.Height(), mempool.HasNoInputsOf(tx));
         unsigned int nSize = entry.GetTxSize();
 
         // Don't accept it if it can't get into a block
@@ -1040,7 +1040,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         }
 
         // Store transaction in memory
-        pool.addUnchecked(hash, entry);
+        pool.addUnchecked(hash, entry, !IsInitialBlockDownload());
     }
 
     SyncWithWallets(tx, NULL);
@@ -2042,7 +2042,7 @@ bool static ConnectTip(CValidationState &state, CBlockIndex *pindexNew, CBlock *
     LogPrint("bench", "  - Writing chainstate: %.2fms [%.2fs]\n", (nTime5 - nTime4) * 0.001, nTimeChainState * 0.000001);
     // Remove conflicting transactions from the mempool.
     list<CTransaction> txConflicted;
-    mempool.removeForBlock(pblock->vtx, pindexNew->nHeight, txConflicted);
+    mempool.removeForBlock(pblock->vtx, pindexNew->nHeight, txConflicted, !IsInitialBlockDownload());
     mempool.check(pcoinsTip);
     // Update chainActive & related variables.
     UpdateTip(pindexNew);
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 */
diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp
new file mode 100644
index 0000000000..cb64ee7c69
--- /dev/null
+++ b/src/test/policyestimator_tests.cpp
@@ -0,0 +1,186 @@
+// Copyright (c) 2011-2015 The Bitcoin Core 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 "txmempool.h"
+#include "uint256.h"
+#include "util.h"
+
+#include "test/test_bitcoin.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, BasicTestingSetup)
+
+BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
+{
+    CTxMemPool mpool(CFeeRate(1000));
+    CAmount basefee(2000);
+    double basepri = 1e6;
+    CAmount deltaFee(100);
+    double deltaPri=5e5;
+    std::vector<CAmount> feeV[2];
+    std::vector<double> priV[2];
+
+    // Populate vectors of increasing fees or priorities
+    for (int j = 0; j < 10; j++) {
+        //V[0] is for fee transactions
+        feeV[0].push_back(basefee * (j+1));
+        priV[0].push_back(0);
+        //V[1] is for priority transactions
+        feeV[1].push_back(CAmount(0));
+        priV[1].push_back(basepri * pow(10, j+1));
+    }
+
+    // Store the hashes of transactions that have been
+    // added to the mempool by their associate fee/pri
+    // txHashes[j] is populated with transactions either of
+    // fee = basefee * (j+1)  OR  pri = 10^6 * 10^(j+1)
+    std::vector<uint256> txHashes[10];
+
+    // Create a transaction template
+    CScript garbage;
+    for (unsigned int i = 0; i < 128; i++)
+        garbage.push_back('X');
+    CMutableTransaction tx;
+    std::list<CTransaction> dummyConflicted;
+    tx.vin.resize(1);
+    tx.vin[0].scriptSig = garbage;
+    tx.vout.resize(1);
+    tx.vout[0].nValue=0LL;
+    CFeeRate baseRate(basefee, ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION));
+
+    // Create a fake block
+    std::vector<CTransaction> block;
+    int blocknum = 0;
+
+    // Loop through 200 blocks
+    // At a decay .998 and 4 fee transactions per block
+    // This makes the tx count about 1.33 per bucket, above the 1 threshold
+    while (blocknum < 200) {
+        for (int j = 0; j < 10; j++) { // For each fee/pri multiple
+            for (int k = 0; k < 5; k++) { // add 4 fee txs for every priority tx
+                tx.vin[0].prevout.n = 10000*blocknum+100*j+k; // make transaction unique
+                uint256 hash = tx.GetHash();
+                mpool.addUnchecked(hash, CTxMemPoolEntry(tx, feeV[k/4][j], GetTime(), priV[k/4][j], blocknum, mpool.HasNoInputsOf(tx)));
+                txHashes[j].push_back(hash);
+            }
+        }
+        //Create blocks where higher fee/pri txs are included more often
+        for (int h = 0; h <= blocknum%10; h++) {
+            // 10/10 blocks add highest fee/pri transactions
+            // 9/10 blocks add 2nd highest and so on until ...
+            // 1/10 blocks add lowest fee/pri transactions
+            while (txHashes[9-h].size()) {
+                CTransaction btx;
+                if (mpool.lookup(txHashes[9-h].back(), btx))
+                    block.push_back(btx);
+                txHashes[9-h].pop_back();
+            }
+        }
+        mpool.removeForBlock(block, ++blocknum, dummyConflicted);
+        block.clear();
+        if (blocknum == 30) {
+            // At this point we should need to combine 5 buckets to get enough data points
+            // So estimateFee(1) should fail and estimateFee(2) should return somewhere around
+            // 8*baserate
+            BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(0));
+            BOOST_CHECK(mpool.estimateFee(2).GetFeePerK() < 8*baseRate.GetFeePerK() + deltaFee);
+            BOOST_CHECK(mpool.estimateFee(2).GetFeePerK() > 8*baseRate.GetFeePerK() - deltaFee);
+        }
+    }
+
+    std::vector<CAmount> origFeeEst;
+    std::vector<double> origPriEst;
+    // Highest feerate is 10*baseRate and gets in all blocks,
+    // second highest feerate is 9*baseRate and gets in 9/10 blocks = 90%,
+    // third highest feerate is 8*base rate, and gets in 8/10 blocks = 80%,
+    // so estimateFee(1) should return 9*baseRate.
+    // Third highest feerate has 90% chance of being included by 2 blocks,
+    // so estimateFee(2) should return 8*baseRate etc...
+    for (int i = 1; i < 10;i++) {
+        origFeeEst.push_back(mpool.estimateFee(i).GetFeePerK());
+        origPriEst.push_back(mpool.estimatePriority(i));
+        if (i > 1) { // Fee estimates should be monotonically decreasing
+            BOOST_CHECK(origFeeEst[i-1] <= origFeeEst[i-2]);
+            BOOST_CHECK(origPriEst[i-1] <= origPriEst[i-2]);
+        }
+        BOOST_CHECK(origFeeEst[i-1] < (10-i)*baseRate.GetFeePerK() + deltaFee);
+        BOOST_CHECK(origFeeEst[i-1] > (10-i)*baseRate.GetFeePerK() - deltaFee);
+        BOOST_CHECK(origPriEst[i-1] < pow(10,10-i) * basepri + deltaPri);
+        BOOST_CHECK(origPriEst[i-1] > pow(10,10-i) * basepri - deltaPri);
+    }
+
+    // Mine 50 more blocks with no transactions happening, estimates shouldn't change
+    // We haven't decayed the moving average enough so we still have enough data points in every bucket
+    while (blocknum < 250)
+        mpool.removeForBlock(block, ++blocknum, dummyConflicted);
+
+    for (int i = 1; i < 10;i++) {
+        BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < origFeeEst[i-1] + deltaFee);
+        BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(mpool.estimatePriority(i) < origPriEst[i-1] + deltaPri);
+        BOOST_CHECK(mpool.estimatePriority(i) > origPriEst[i-1] - deltaPri);
+    }
+
+
+    // Mine 15 more blocks with lots of transactions happening and not getting mined
+    // Estimates should go up
+    while (blocknum < 265) {
+        for (int j = 0; j < 10; j++) { // For each fee/pri multiple
+            for (int k = 0; k < 5; k++) { // add 4 fee txs for every priority tx
+                tx.vin[0].prevout.n = 10000*blocknum+100*j+k;
+                uint256 hash = tx.GetHash();
+                mpool.addUnchecked(hash, CTxMemPoolEntry(tx, feeV[k/4][j], GetTime(), priV[k/4][j], blocknum, mpool.HasNoInputsOf(tx)));
+                txHashes[j].push_back(hash);
+            }
+        }
+        mpool.removeForBlock(block, ++blocknum, dummyConflicted);
+    }
+
+    for (int i = 1; i < 10;i++) {
+        BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(mpool.estimatePriority(i) > origPriEst[i-1] - deltaPri);
+    }
+
+    // Mine all those transactions
+    // Estimates should still not be below original
+    for (int j = 0; j < 10; j++) {
+        while(txHashes[j].size()) {
+            CTransaction btx;
+            if (mpool.lookup(txHashes[j].back(), btx))
+                block.push_back(btx);
+            txHashes[j].pop_back();
+        }
+    }
+    mpool.removeForBlock(block, 265, dummyConflicted);
+    block.clear();
+    for (int i = 1; i < 10;i++) {
+        BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(mpool.estimatePriority(i) > origPriEst[i-1] - deltaPri);
+    }
+
+    // Mine 100 more blocks where everything is mined every block
+    // Estimates should be below original estimates (not possible for last estimate)
+    while (blocknum < 365) {
+        for (int j = 0; j < 10; j++) { // For each fee/pri multiple
+            for (int k = 0; k < 5; k++) { // add 4 fee txs for every priority tx
+                tx.vin[0].prevout.n = 10000*blocknum+100*j+k;
+                uint256 hash = tx.GetHash();
+                mpool.addUnchecked(hash, CTxMemPoolEntry(tx, feeV[k/4][j], GetTime(), priV[k/4][j], blocknum, mpool.HasNoInputsOf(tx)));
+                CTransaction btx;
+                if (mpool.lookup(hash, btx))
+                    block.push_back(btx);
+            }
+        }
+        mpool.removeForBlock(block, ++blocknum, dummyConflicted);
+        block.clear();
+    }
+    for (int i = 1; i < 9; i++) {
+        BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(mpool.estimatePriority(i) < origPriEst[i-1] - deltaPri);
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 85ea3f77b5..53992b80da 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -7,28 +7,27 @@
 
 #include "clientversion.h"
 #include "main.h"
+#include "policy/fees.h"
 #include "streams.h"
 #include "util.h"
 #include "utilmoneystr.h"
 #include "version.h"
 
-#include <boost/circular_buffer.hpp>
-
 using namespace std;
 
 CTxMemPoolEntry::CTxMemPoolEntry():
-    nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0)
+    nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0), hadNoDependencies(false)
 {
     nHeight = MEMPOOL_HEIGHT;
 }
 
 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
                                  int64_t _nTime, double _dPriority,
-                                 unsigned int _nHeight):
-    tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight)
+                                 unsigned int _nHeight, bool poolHasNoInputsOf):
+    tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight),
+    hadNoDependencies(poolHasNoInputsOf)
 {
     nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
-
     nModSize = tx.CalculateModifiedSize(nTxSize);
 }
 
@@ -46,346 +45,15 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
     return dResult;
 }
 
-/**
- * Keep track of fee/priority for transactions confirmed within N blocks
- */
-class CBlockAverage
-{
-private:
-    boost::circular_buffer<CFeeRate> feeSamples;
-    boost::circular_buffer<double> prioritySamples;
-
-    template<typename T> std::vector<T> buf2vec(boost::circular_buffer<T> buf) const
-    {
-        std::vector<T> vec(buf.begin(), buf.end());
-        return vec;
-    }
-
-public:
-    CBlockAverage() : feeSamples(100), prioritySamples(100) { }
-
-    void RecordFee(const CFeeRate& feeRate) {
-        feeSamples.push_back(feeRate);
-    }
-
-    void RecordPriority(double priority) {
-        prioritySamples.push_back(priority);
-    }
-
-    size_t FeeSamples() const { return feeSamples.size(); }
-    size_t GetFeeSamples(std::vector<CFeeRate>& insertInto) const
-    {
-        BOOST_FOREACH(const CFeeRate& f, feeSamples)
-            insertInto.push_back(f);
-        return feeSamples.size();
-    }
-    size_t PrioritySamples() const { return prioritySamples.size(); }
-    size_t GetPrioritySamples(std::vector<double>& insertInto) const
-    {
-        BOOST_FOREACH(double d, prioritySamples)
-            insertInto.push_back(d);
-        return prioritySamples.size();
-    }
-
-    /**
-     * Used as belt-and-suspenders check when reading to detect
-     * file corruption
-     */
-    static bool AreSane(const CFeeRate fee, const CFeeRate& minRelayFee)
-    {
-        if (fee < CFeeRate(0))
-            return false;
-        if (fee.GetFeePerK() > minRelayFee.GetFeePerK() * 10000)
-            return false;
-        return true;
-    }
-    static bool AreSane(const std::vector<CFeeRate>& vecFee, const CFeeRate& minRelayFee)
-    {
-        BOOST_FOREACH(CFeeRate fee, vecFee)
-        {
-            if (!AreSane(fee, minRelayFee))
-                return false;
-        }
-        return true;
-    }
-    static bool AreSane(const double priority)
-    {
-        return priority >= 0;
-    }
-    static bool AreSane(const std::vector<double> vecPriority)
-    {
-        BOOST_FOREACH(double priority, vecPriority)
-        {
-            if (!AreSane(priority))
-                return false;
-        }
-        return true;
-    }
-
-    void Write(CAutoFile& fileout) const
-    {
-        std::vector<CFeeRate> vecFee = buf2vec(feeSamples);
-        fileout << vecFee;
-        std::vector<double> vecPriority = buf2vec(prioritySamples);
-        fileout << vecPriority;
-    }
-
-    void Read(CAutoFile& filein, const CFeeRate& minRelayFee) {
-        std::vector<CFeeRate> vecFee;
-        filein >> vecFee;
-        if (AreSane(vecFee, minRelayFee))
-            feeSamples.insert(feeSamples.end(), vecFee.begin(), vecFee.end());
-        else
-            throw runtime_error("Corrupt fee value in estimates file.");
-        std::vector<double> vecPriority;
-        filein >> vecPriority;
-        if (AreSane(vecPriority))
-            prioritySamples.insert(prioritySamples.end(), vecPriority.begin(), vecPriority.end());
-        else
-            throw runtime_error("Corrupt priority value in estimates file.");
-        if (feeSamples.size() + prioritySamples.size() > 0)
-            LogPrint("estimatefee", "Read %d fee samples and %d priority samples\n",
-                     feeSamples.size(), prioritySamples.size());
-    }
-};
-
-class CMinerPolicyEstimator
-{
-private:
-    /**
-     * Records observed averages transactions that confirmed within one block, two blocks,
-     * three blocks etc.
-     */
-    std::vector<CBlockAverage> history;
-    std::vector<CFeeRate> sortedFeeSamples;
-    std::vector<double> sortedPrioritySamples;
-
-    int nBestSeenHeight;
-
-    /**
-     * nBlocksAgo is 0 based, i.e. transactions that confirmed in the highest seen block are
-     * nBlocksAgo == 0, transactions in the block before that are nBlocksAgo == 1 etc.
-     */
-    void seenTxConfirm(const CFeeRate& feeRate, const CFeeRate& minRelayFee, double dPriority, int nBlocksAgo)
-    {
-        // Last entry records "everything else".
-        int nBlocksTruncated = min(nBlocksAgo, (int) history.size() - 1);
-        assert(nBlocksTruncated >= 0);
-
-        // We need to guess why the transaction was included in a block-- either
-        // because it is high-priority or because it has sufficient fees.
-        bool sufficientFee = (feeRate > minRelayFee);
-        bool sufficientPriority = AllowFree(dPriority);
-        const char* assignedTo = "unassigned";
-        if (sufficientFee && !sufficientPriority && CBlockAverage::AreSane(feeRate, minRelayFee))
-        {
-            history[nBlocksTruncated].RecordFee(feeRate);
-            assignedTo = "fee";
-        }
-        else if (sufficientPriority && !sufficientFee && CBlockAverage::AreSane(dPriority))
-        {
-            history[nBlocksTruncated].RecordPriority(dPriority);
-            assignedTo = "priority";
-        }
-        else
-        {
-            // Neither or both fee and priority sufficient to get confirmed:
-            // don't know why they got confirmed.
-        }
-        LogPrint("estimatefee", "Seen TX confirm: %s: %s fee/%g priority, took %d blocks\n",
-                 assignedTo, feeRate.ToString(), dPriority, nBlocksAgo);
-    }
-
-public:
-    CMinerPolicyEstimator(int nEntries) : nBestSeenHeight(0)
-    {
-        history.resize(nEntries);
-    }
-
-    void seenBlock(const std::vector<CTxMemPoolEntry>& entries, int nBlockHeight, const CFeeRate minRelayFee)
-    {
-        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;
-
-        // Fill up the history buckets based on how long transactions took
-        // to confirm.
-        std::vector<std::vector<const CTxMemPoolEntry*> > entriesByConfirmations;
-        entriesByConfirmations.resize(history.size());
-        BOOST_FOREACH(const CTxMemPoolEntry& entry, entries)
-        {
-            // How many blocks did it take for miners to include this transaction?
-            int delta = nBlockHeight - entry.GetHeight();
-            if (delta <= 0)
-            {
-                // Re-org made us lose height, this should only happen if we happen
-                // to re-org on a difficulty transition point: very rare!
-                continue;
-            }
-            if ((delta-1) >= (int)history.size())
-                delta = history.size(); // Last bucket is catch-all
-            entriesByConfirmations.at(delta-1).push_back(&entry);
-        }
-        for (size_t i = 0; i < entriesByConfirmations.size(); i++)
-        {
-            std::vector<const CTxMemPoolEntry*> &e = entriesByConfirmations.at(i);
-            // Insert at most 10 random entries per bucket, otherwise a single block
-            // can dominate an estimate:
-            if (e.size() > 10) {
-                std::random_shuffle(e.begin(), e.end());
-                e.resize(10);
-            }
-            BOOST_FOREACH(const CTxMemPoolEntry* entry, e)
-            {
-                // Fees are stored and reported as BTC-per-kb:
-                CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
-                double dPriority = entry->GetPriority(entry->GetHeight()); // Want priority when it went IN
-                seenTxConfirm(feeRate, minRelayFee, dPriority, i);
-            }
-        }
-
-        // After new samples are added, we have to clear the sorted lists,
-        // so they'll be resorted the next time someone asks for an estimate
-        sortedFeeSamples.clear();
-        sortedPrioritySamples.clear();
-
-        for (size_t i = 0; i < history.size(); i++) {
-            if (history[i].FeeSamples() + history[i].PrioritySamples() > 0)
-                LogPrint("estimatefee", "estimates: for confirming within %d blocks based on %d/%d samples, fee=%s, prio=%g\n", 
-                         i,
-                         history[i].FeeSamples(), history[i].PrioritySamples(),
-                         estimateFee(i+1).ToString(), estimatePriority(i+1));
-        }
-    }
-
-    /**
-     * Can return CFeeRate(0) if we don't have any data for that many blocks back. nBlocksToConfirm is 1 based.
-     */
-    CFeeRate estimateFee(int nBlocksToConfirm)
-    {
-        nBlocksToConfirm--;
-
-        if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
-            return CFeeRate(0);
-
-        if (sortedFeeSamples.size() == 0)
-        {
-            for (size_t i = 0; i < history.size(); i++)
-                history.at(i).GetFeeSamples(sortedFeeSamples);
-            std::sort(sortedFeeSamples.begin(), sortedFeeSamples.end(),
-                      std::greater<CFeeRate>());
-        }
-        if (sortedFeeSamples.size() < 11)
-        {
-            // Eleven is Gavin's Favorite Number
-            // ... but we also take a maximum of 10 samples per block so eleven means
-            // we're getting samples from at least two different blocks
-            return CFeeRate(0);
-        }
-
-        int nBucketSize = history.at(nBlocksToConfirm).FeeSamples();
-
-        // Estimates should not increase as number of confirmations goes up,
-        // but the estimates are noisy because confirmations happen discretely
-        // in blocks. To smooth out the estimates, use all samples in the history
-        // and use the nth highest where n is (number of samples in previous bucket +
-        // half the samples in nBlocksToConfirm bucket):
-        size_t nPrevSize = 0;
-        for (int i = 0; i < nBlocksToConfirm; i++)
-            nPrevSize += history.at(i).FeeSamples();
-        size_t index = min(nPrevSize + nBucketSize/2, sortedFeeSamples.size()-1);
-        return sortedFeeSamples[index];
-    }
-    double estimatePriority(int nBlocksToConfirm)
-    {
-        nBlocksToConfirm--;
-
-        if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
-            return -1;
-
-        if (sortedPrioritySamples.size() == 0)
-        {
-            for (size_t i = 0; i < history.size(); i++)
-                history.at(i).GetPrioritySamples(sortedPrioritySamples);
-            std::sort(sortedPrioritySamples.begin(), sortedPrioritySamples.end(),
-                      std::greater<double>());
-        }
-        if (sortedPrioritySamples.size() < 11)
-            return -1.0;
-
-        int nBucketSize = history.at(nBlocksToConfirm).PrioritySamples();
-
-        // Estimates should not increase as number of confirmations needed goes up,
-        // but the estimates are noisy because confirmations happen discretely
-        // in blocks. To smooth out the estimates, use all samples in the history
-        // and use the nth highest where n is (number of samples in previous buckets +
-        // half the samples in nBlocksToConfirm bucket).
-        size_t nPrevSize = 0;
-        for (int i = 0; i < nBlocksToConfirm; i++)
-            nPrevSize += history.at(i).PrioritySamples();
-        size_t index = min(nPrevSize + nBucketSize/2, sortedPrioritySamples.size()-1);
-        return sortedPrioritySamples[index];
-    }
-
-    void Write(CAutoFile& fileout) const
-    {
-        fileout << nBestSeenHeight;
-        fileout << (uint32_t)history.size();
-        BOOST_FOREACH(const CBlockAverage& entry, history)
-        {
-            entry.Write(fileout);
-        }
-    }
-
-    void Read(CAutoFile& filein, const CFeeRate& minRelayFee)
-    {
-        int nFileBestSeenHeight;
-        filein >> nFileBestSeenHeight;
-        uint32_t numEntries;
-        filein >> numEntries;
-        if (numEntries <= 0 || numEntries > 10000)
-            throw runtime_error("Corrupt estimates file. Must have between 1 and 10k entries.");
-
-        std::vector<CBlockAverage> fileHistory;
-        
-        for (size_t i = 0; i < numEntries; i++)
-        {
-            CBlockAverage entry;
-            entry.Read(filein, minRelayFee);
-            fileHistory.push_back(entry);
-        }
-
-        // Now that we've processed the entire fee estimate data file and not
-        // thrown any errors, we can copy it to our history
-        nBestSeenHeight = nFileBestSeenHeight;
-        history = fileHistory;
-        assert(history.size() > 0);
-    }
-};
-
-
 CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
-    nTransactionsUpdated(0),
-    minRelayFee(_minRelayFee)
+    nTransactionsUpdated(0)
 {
     // Sanity checks off by default for performance, because otherwise
     // accepting transactions becomes O(N^2) where N is the number
     // of transactions in the pool
     fSanityCheck = false;
 
-    // 25 blocks is a compromise between using a lot of disk/memory and
-    // trying to give accurate estimates to people who might be willing
-    // to wait a day or two to save a fraction of a penny in fees.
-    // Confirmation times for very-low-fee transactions that take more
-    // than an hour or three to confirm are highly variable.
-    minerPolicyEstimator = new CMinerPolicyEstimator(25);
+    minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
 }
 
 CTxMemPool::~CTxMemPool()
@@ -419,20 +87,20 @@ void CTxMemPool::AddTransactionsUpdated(unsigned int n)
 }
 
 
-bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry)
+bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
 {
     // Add to memory pool without checking anything.
     // Used by main.cpp AcceptToMemoryPool(), which DOES do
     // all the appropriate checks.
     LOCK(cs);
-    {
-        mapTx[hash] = entry;
-        const CTransaction& tx = mapTx[hash].GetTx();
-        for (unsigned int i = 0; i < tx.vin.size(); i++)
-            mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
-        nTransactionsUpdated++;
-        totalTxSize += entry.GetTxSize();
-    }
+    mapTx[hash] = entry;
+    const CTransaction& tx = mapTx[hash].GetTx();
+    for (unsigned int i = 0; i < tx.vin.size(); i++)
+        mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
+    nTransactionsUpdated++;
+    totalTxSize += entry.GetTxSize();
+    minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
+
     return true;
 }
 
@@ -478,6 +146,7 @@ void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& rem
             totalTxSize -= mapTx[hash].GetTxSize();
             mapTx.erase(hash);
             nTransactionsUpdated++;
+            minerPolicyEstimator->removeTx(hash);
         }
     }
 }
@@ -528,7 +197,7 @@ void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>
  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
  */
 void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
-                                std::list<CTransaction>& conflicts)
+                                std::list<CTransaction>& conflicts, bool fCurrentEstimate)
 {
     LOCK(cs);
     std::vector<CTxMemPoolEntry> entries;
@@ -538,7 +207,6 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
         if (mapTx.count(hash))
             entries.push_back(mapTx[hash]);
     }
-    minerPolicyEstimator->seenBlock(entries, nBlockHeight, minRelayFee);
     BOOST_FOREACH(const CTransaction& tx, vtx)
     {
         std::list<CTransaction> dummy;
@@ -546,9 +214,10 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
         removeConflicts(tx, conflicts);
         ClearPrioritisation(tx.GetHash());
     }
+    // After the txs in the new block have been removed from the mempool, update policy estimates
+    minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
 }
 
-
 void CTxMemPool::clear()
 {
     LOCK(cs);
@@ -665,7 +334,7 @@ CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
 {
     try {
         LOCK(cs);
-        fileout << 99900; // version required to read: 0.9.99 or later
+        fileout << 109900; // version required to read: 0.10.99 or later
         fileout << CLIENT_VERSION; // version that wrote the file
         minerPolicyEstimator->Write(fileout);
     }
@@ -686,7 +355,7 @@ CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
             return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
 
         LOCK(cs);
-        minerPolicyEstimator->Read(filein, minRelayFee);
+        minerPolicyEstimator->Read(filein);
     }
     catch (const std::exception&) {
         LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)");
@@ -723,6 +392,13 @@ void CTxMemPool::ClearPrioritisation(const uint256 hash)
     mapDeltas.erase(hash);
 }
 
+bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
+{
+    for (unsigned int i = 0; i < tx.vin.size(); i++)
+        if (exists(tx.vin[i].prevout.hash))
+            return false;
+    return true;
+}
 
 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 
diff --git a/src/txmempool.h b/src/txmempool.h
index 0732af67e6..7271a5f603 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -43,10 +43,11 @@ private:
     int64_t nTime; //! Local time when entering the mempool
     double dPriority; //! Priority when entering the mempool
     unsigned int nHeight; //! Chain height when entering the mempool
+    bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool
 
 public:
     CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
-                    int64_t _nTime, double _dPriority, unsigned int _nHeight);
+                    int64_t _nTime, double _dPriority, unsigned int _nHeight, bool poolHasNoInputsOf = false);
     CTxMemPoolEntry();
     CTxMemPoolEntry(const CTxMemPoolEntry& other);
 
@@ -56,9 +57,10 @@ public:
     size_t GetTxSize() const { return nTxSize; }
     int64_t GetTime() const { return nTime; }
     unsigned int GetHeight() const { return nHeight; }
+    bool WasClearAtEntry() const { return hadNoDependencies; }
 };
 
-class CMinerPolicyEstimator;
+class CBlockPolicyEstimator;
 
 /** An inpoint - a combination of a transaction and an index n into its vin */
 class CInPoint
@@ -88,9 +90,8 @@ class CTxMemPool
 private:
     bool fSanityCheck; //! Normally false, true if -checkmempool or -regtest
     unsigned int nTransactionsUpdated;
-    CMinerPolicyEstimator* minerPolicyEstimator;
+    CBlockPolicyEstimator* minerPolicyEstimator;
 
-    CFeeRate minRelayFee; //! Passed to constructor to avoid dependency on main
     uint64_t totalTxSize; //! sum of all mempool tx' byte sizes
 
 public:
@@ -111,17 +112,22 @@ public:
     void check(const CCoinsViewCache *pcoins) const;
     void setSanityCheck(bool _fSanityCheck) { fSanityCheck = _fSanityCheck; }
 
-    bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry);
+    bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true);
     void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
     void removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight);
     void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
     void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
-                        std::list<CTransaction>& conflicts);
+                        std::list<CTransaction>& conflicts, bool fCurrentEstimate = true);
     void clear();
     void queryHashes(std::vector<uint256>& vtxid);
     void pruneSpent(const uint256& hash, CCoins &coins);
     unsigned int GetTransactionsUpdated() const;
     void AddTransactionsUpdated(unsigned int n);
+    /**
+     * Check that none of this transactions inputs are in the mempool, and thus
+     * the tx is not dependent on other mempool transactions to be included in a block.
+     */
+    bool HasNoInputsOf(const CTransaction& tx) const;
 
     /** Affect CreateNewBlock prioritisation of transactions */
     void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta);
@@ -139,7 +145,7 @@ public:
         return totalTxSize;
     }
 
-    bool exists(uint256 hash)
+    bool exists(uint256 hash) const
     {
         LOCK(cs);
         return (mapTx.count(hash) != 0);