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

1 files changed, 29 insertions, 353 deletions

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) { }