Merge tag 'branch-0.13' into bugfix_gitdir

6 files changed, 1211 insertions, 0 deletions

diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp
new file mode 100644
index 0000000000..7b0e8b7d08
--- /dev/null
+++ b/src/policy/fees.cpp
@@ -0,0 +1,601 @@
+// 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 "policy/policy.h"
+
+#include "amount.h"
+#include "primitives/transaction.h"
+#include "random.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 successively
+    // 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", 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 because 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");
+    }
+    LogPrint("estimatefee", "\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);
+}
+
+CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool)
+{
+    if (answerFoundAtTarget)
+        *answerFoundAtTarget = 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 = -1;
+    while (median < 0 && (unsigned int)confTarget <= feeStats.GetMaxConfirms()) {
+        median = feeStats.EstimateMedianVal(confTarget++, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+    }
+
+    if (answerFoundAtTarget)
+        *answerFoundAtTarget = confTarget - 1;
+
+    // If mempool is limiting txs , return at least the min fee from the mempool
+    CAmount minPoolFee = pool.GetMinFee(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000).GetFeePerK();
+    if (minPoolFee > 0 && minPoolFee > median)
+        return CFeeRate(minPoolFee);
+
+    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);
+}
+
+double CBlockPolicyEstimator::estimateSmartPriority(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool)
+{
+    if (answerFoundAtTarget)
+        *answerFoundAtTarget = confTarget;
+    // Return failure if trying to analyze a target we're not tracking
+    if (confTarget <= 0 || (unsigned int)confTarget > priStats.GetMaxConfirms())
+        return -1;
+
+    // If mempool is limiting txs, no priority txs are allowed
+    CAmount minPoolFee = pool.GetMinFee(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000).GetFeePerK();
+    if (minPoolFee > 0)
+        return INF_PRIORITY;
+
+    double median = -1;
+    while (median < 0 && (unsigned int)confTarget <= priStats.GetMaxConfirms()) {
+        median = priStats.EstimateMedianVal(confTarget++, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+    }
+
+    if (answerFoundAtTarget)
+        *answerFoundAtTarget = confTarget - 1;
+
+    return median;
+}
+
+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;
+}
+
+FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee)
+{
+    CAmount minFeeLimit = minIncrementalFee.GetFeePerK() / 2;
+    feeset.insert(0);
+    for (double bucketBoundary = minFeeLimit; bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) {
+        feeset.insert(bucketBoundary);
+    }
+}
+
+CAmount FeeFilterRounder::round(CAmount currentMinFee)
+{
+    std::set<double>::iterator it = feeset.lower_bound(currentMinFee);
+    if ((it != feeset.begin() && insecure_rand() % 3 != 0) || it == feeset.end()) {
+        it--;
+    }
+    return *it;
+}
diff --git a/src/policy/fees.h b/src/policy/fees.h
new file mode 100644
index 0000000000..463f62f710
--- /dev/null
+++ b/src/policy/fees.h
@@ -0,0 +1,302 @@
+// 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 CTxMemPool;
+
+/** \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 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 calculate 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 calculate 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 boundaries
+     * @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 95% of X fee transactions to be confirmed within Y blocks for X to be big enough */
+static const double MIN_SUCCESS_PCT = .95;
+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);
+
+    /** Estimate fee rate needed to get be included in a block within
+     *  confTarget blocks. If no answer can be given at confTarget, return an
+     *  estimate at the lowest target where one can be given.
+     */
+    CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool);
+
+    /** Return a priority estimate */
+    double estimatePriority(int confTarget);
+
+    /** Estimate priority needed to get be included in a block within
+     *  confTarget blocks. If no answer can be given at confTarget, return an
+     *  estimate at the lowest target where one can be given.
+     */
+    double estimateSmartPriority(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool);
+
+    /** 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;
+};
+
+class FeeFilterRounder
+{
+public:
+    /** Create new FeeFilterRounder */
+    FeeFilterRounder(const CFeeRate& minIncrementalFee);
+
+    /** Quantize a minimum fee for privacy purpose before broadcast **/
+    CAmount round(CAmount currentMinFee);
+
+private:
+    std::set<double> feeset;
+};
+#endif /*BITCOIN_POLICYESTIMATOR_H */
diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
new file mode 100644
index 0000000000..f2148bfe10
--- /dev/null
+++ b/src/policy/policy.cpp
@@ -0,0 +1,162 @@
+// 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.
+
+// NOTE: This file is intended to be customised by the end user, and includes only local node policy logic
+
+#include "policy/policy.h"
+
+#include "main.h"
+#include "tinyformat.h"
+#include "util.h"
+#include "utilstrencodings.h"
+
+#include <boost/foreach.hpp>
+
+    /**
+     * Check transaction inputs to mitigate two
+     * potential denial-of-service attacks:
+     * 
+     * 1. scriptSigs with extra data stuffed into them,
+     *    not consumed by scriptPubKey (or P2SH script)
+     * 2. P2SH scripts with a crazy number of expensive
+     *    CHECKSIG/CHECKMULTISIG operations
+     *
+     * Why bother? To avoid denial-of-service attacks; an attacker
+     * can submit a standard HASH... OP_EQUAL transaction,
+     * which will get accepted into blocks. The redemption
+     * script can be anything; an attacker could use a very
+     * expensive-to-check-upon-redemption script like:
+     *   DUP CHECKSIG DROP ... repeated 100 times... OP_1
+     */
+
+bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType)
+{
+    std::vector<std::vector<unsigned char> > vSolutions;
+    if (!Solver(scriptPubKey, whichType, vSolutions))
+        return false;
+
+    if (whichType == TX_MULTISIG)
+    {
+        unsigned char m = vSolutions.front()[0];
+        unsigned char n = vSolutions.back()[0];
+        // Support up to x-of-3 multisig txns as standard
+        if (n < 1 || n > 3)
+            return false;
+        if (m < 1 || m > n)
+            return false;
+    } else if (whichType == TX_NULL_DATA &&
+               (!fAcceptDatacarrier || scriptPubKey.size() > nMaxDatacarrierBytes))
+          return false;
+
+    return whichType != TX_NONSTANDARD;
+}
+
+bool IsStandardTx(const CTransaction& tx, std::string& reason)
+{
+    if (tx.nVersion > CTransaction::MAX_STANDARD_VERSION || tx.nVersion < 1) {
+        reason = "version";
+        return false;
+    }
+
+    // Extremely large transactions with lots of inputs can cost the network
+    // almost as much to process as they cost the sender in fees, because
+    // computing signature hashes is O(ninputs*txsize). Limiting transactions
+    // to MAX_STANDARD_TX_SIZE mitigates CPU exhaustion attacks.
+    unsigned int sz = GetTransactionCost(tx);
+    if (sz >= MAX_STANDARD_TX_COST) {
+        reason = "tx-size";
+        return false;
+    }
+
+    BOOST_FOREACH(const CTxIn& txin, tx.vin)
+    {
+        // Biggest 'standard' txin is a 15-of-15 P2SH multisig with compressed
+        // keys (remember the 520 byte limit on redeemScript size). That works
+        // out to a (15*(33+1))+3=513 byte redeemScript, 513+1+15*(73+1)+3=1627
+        // bytes of scriptSig, which we round off to 1650 bytes for some minor
+        // future-proofing. That's also enough to spend a 20-of-20
+        // CHECKMULTISIG scriptPubKey, though such a scriptPubKey is not
+        // considered standard.
+        if (txin.scriptSig.size() > 1650) {
+            reason = "scriptsig-size";
+            return false;
+        }
+        if (!txin.scriptSig.IsPushOnly()) {
+            reason = "scriptsig-not-pushonly";
+            return false;
+        }
+    }
+
+    unsigned int nDataOut = 0;
+    txnouttype whichType;
+    BOOST_FOREACH(const CTxOut& txout, tx.vout) {
+        if (!::IsStandard(txout.scriptPubKey, whichType)) {
+            reason = "scriptpubkey";
+            return false;
+        }
+
+        if (whichType == TX_NULL_DATA)
+            nDataOut++;
+        else if ((whichType == TX_MULTISIG) && (!fIsBareMultisigStd)) {
+            reason = "bare-multisig";
+            return false;
+        } else if (txout.IsDust(::minRelayTxFee)) {
+            reason = "dust";
+            return false;
+        }
+    }
+
+    // only one OP_RETURN txout is permitted
+    if (nDataOut > 1) {
+        reason = "multi-op-return";
+        return false;
+    }
+
+    return true;
+}
+
+bool AreInputsStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
+{
+    if (tx.IsCoinBase())
+        return true; // Coinbases don't use vin normally
+
+    for (unsigned int i = 0; i < tx.vin.size(); i++)
+    {
+        const CTxOut& prev = mapInputs.GetOutputFor(tx.vin[i]);
+
+        std::vector<std::vector<unsigned char> > vSolutions;
+        txnouttype whichType;
+        // get the scriptPubKey corresponding to this input:
+        const CScript& prevScript = prev.scriptPubKey;
+        if (!Solver(prevScript, whichType, vSolutions))
+            return false;
+
+        if (whichType == TX_SCRIPTHASH)
+        {
+            std::vector<std::vector<unsigned char> > stack;
+            // convert the scriptSig into a stack, so we can inspect the redeemScript
+            if (!EvalScript(stack, tx.vin[i].scriptSig, SCRIPT_VERIFY_NONE, BaseSignatureChecker(), SIGVERSION_BASE))
+                return false;
+            if (stack.empty())
+                return false;
+            CScript subscript(stack.back().begin(), stack.back().end());
+            if (subscript.GetSigOpCount(true) > MAX_P2SH_SIGOPS) {
+                return false;
+            }
+        }
+    }
+
+    return true;
+}
+
+int64_t GetVirtualTransactionSize(int64_t nCost)
+{
+    return (nCost + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR;
+}
+
+int64_t GetVirtualTransactionSize(const CTransaction& tx)
+{
+    return GetVirtualTransactionSize(GetTransactionCost(tx));
+}
diff --git a/src/policy/policy.h b/src/policy/policy.h
new file mode 100644
index 0000000000..29a8cc57c2
--- /dev/null
+++ b/src/policy/policy.h
@@ -0,0 +1,73 @@
+// 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_POLICY_POLICY_H
+#define BITCOIN_POLICY_POLICY_H
+
+#include "consensus/consensus.h"
+#include "script/interpreter.h"
+#include "script/standard.h"
+
+#include <string>
+
+class CCoinsViewCache;
+
+/** Default for -blockmaxsize, which controls the maximum size of block the mining code will create **/
+static const unsigned int DEFAULT_BLOCK_MAX_SIZE = 750000;
+/** Default for -blockprioritysize, maximum space for zero/low-fee transactions **/
+static const unsigned int DEFAULT_BLOCK_PRIORITY_SIZE = 0;
+/** Default for -blockmaxcost, which control the range of block costs the mining code will create **/
+static const unsigned int DEFAULT_BLOCK_MAX_COST = 3000000;
+/** The maximum size for transactions we're willing to relay/mine */
+static const unsigned int MAX_STANDARD_TX_COST = 400000;
+/** Maximum number of signature check operations in an IsStandard() P2SH script */
+static const unsigned int MAX_P2SH_SIGOPS = 15;
+/** The maximum number of sigops we're willing to relay/mine in a single tx */
+static const unsigned int MAX_STANDARD_TX_SIGOPS_COST = MAX_BLOCK_SIGOPS_COST/5;
+/** Default for -maxmempool, maximum megabytes of mempool memory usage */
+static const unsigned int DEFAULT_MAX_MEMPOOL_SIZE = 300;
+/**
+ * Standard script verification flags that standard transactions will comply
+ * with. However scripts violating these flags may still be present in valid
+ * blocks and we must accept those blocks.
+ */
+static const unsigned int STANDARD_SCRIPT_VERIFY_FLAGS = MANDATORY_SCRIPT_VERIFY_FLAGS |
+                                                         SCRIPT_VERIFY_DERSIG |
+                                                         SCRIPT_VERIFY_STRICTENC |
+                                                         SCRIPT_VERIFY_MINIMALDATA |
+                                                         SCRIPT_VERIFY_NULLDUMMY |
+                                                         SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS |
+                                                         SCRIPT_VERIFY_CLEANSTACK |
+                                                         SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY |
+                                                         SCRIPT_VERIFY_CHECKSEQUENCEVERIFY |
+                                                         SCRIPT_VERIFY_LOW_S |
+                                                         SCRIPT_VERIFY_WITNESS |
+                                                         SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM;
+
+/** For convenience, standard but not mandatory verify flags. */
+static const unsigned int STANDARD_NOT_MANDATORY_VERIFY_FLAGS = STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS;
+
+/** Used as the flags parameter to sequence and nLocktime checks in non-consensus code. */
+static const unsigned int STANDARD_LOCKTIME_VERIFY_FLAGS = LOCKTIME_VERIFY_SEQUENCE |
+                                                           LOCKTIME_MEDIAN_TIME_PAST;
+
+bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType);
+    /**
+     * Check for standard transaction types
+     * @return True if all outputs (scriptPubKeys) use only standard transaction forms
+     */
+bool IsStandardTx(const CTransaction& tx, std::string& reason);
+    /**
+     * Check for standard transaction types
+     * @param[in] mapInputs    Map of previous transactions that have outputs we're spending
+     * @return True if all inputs (scriptSigs) use only standard transaction forms
+     */
+bool AreInputsStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs);
+
+/** Compute the virtual transaction size (cost reinterpreted as bytes). */
+int64_t GetVirtualTransactionSize(int64_t nCost);
+int64_t GetVirtualTransactionSize(const CTransaction& tx);
+
+#endif // BITCOIN_POLICY_POLICY_H
diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp
new file mode 100644
index 0000000000..133cff611d
--- /dev/null
+++ b/src/policy/rbf.cpp
@@ -0,0 +1,47 @@
+// Copyright (c) 2016 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/rbf.h"
+
+bool SignalsOptInRBF(const CTransaction &tx)
+{
+    BOOST_FOREACH(const CTxIn &txin, tx.vin) {
+        if (txin.nSequence < std::numeric_limits<unsigned int>::max()-1) {
+            return true;
+        }
+    }
+    return false;
+}
+
+RBFTransactionState IsRBFOptIn(const CTransaction &tx, CTxMemPool &pool)
+{
+    AssertLockHeld(pool.cs);
+
+    CTxMemPool::setEntries setAncestors;
+
+    // First check the transaction itself.
+    if (SignalsOptInRBF(tx)) {
+        return RBF_TRANSACTIONSTATE_REPLACEABLE_BIP125;
+    }
+
+    // If this transaction is not in our mempool, then we can't be sure
+    // we will know about all its inputs.
+    if (!pool.exists(tx.GetHash())) {
+        return RBF_TRANSACTIONSTATE_UNKNOWN;
+    }
+
+    // If all the inputs have nSequence >= maxint-1, it still might be
+    // signaled for RBF if any unconfirmed parents have signaled.
+    uint64_t noLimit = std::numeric_limits<uint64_t>::max();
+    std::string dummy;
+    CTxMemPoolEntry entry = *pool.mapTx.find(tx.GetHash());
+    pool.CalculateMemPoolAncestors(entry, setAncestors, noLimit, noLimit, noLimit, noLimit, dummy, false);
+
+    BOOST_FOREACH(CTxMemPool::txiter it, setAncestors) {
+        if (SignalsOptInRBF(it->GetTx())) {
+            return RBF_TRANSACTIONSTATE_REPLACEABLE_BIP125;
+        }
+    }
+    return RBF_TRANSACTIONSTATE_FINAL;
+}
diff --git a/src/policy/rbf.h b/src/policy/rbf.h
new file mode 100644
index 0000000000..5a711dba07
--- /dev/null
+++ b/src/policy/rbf.h
@@ -0,0 +1,26 @@
+// Copyright (c) 2016 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_POLICY_RBF_H
+#define BITCOIN_POLICY_RBF_H
+
+#include "txmempool.h"
+
+enum RBFTransactionState {
+    RBF_TRANSACTIONSTATE_UNKNOWN,
+    RBF_TRANSACTIONSTATE_REPLACEABLE_BIP125,
+    RBF_TRANSACTIONSTATE_FINAL
+};
+
+// Check whether the sequence numbers on this transaction are signaling
+// opt-in to replace-by-fee, according to BIP 125
+bool SignalsOptInRBF(const CTransaction &tx);
+
+// Determine whether an in-mempool transaction is signaling opt-in to RBF
+// according to BIP 125
+// This involves checking sequence numbers of the transaction, as well
+// as the sequence numbers of all in-mempool ancestors.
+RBFTransactionState IsRBFOptIn(const CTransaction &tx, CTxMemPool &pool);
+
+#endif // BITCOIN_POLICY_RBF_H