Merge pull request #6134

e304432 Pass reference to estimateSmartFee and cleanup whitespace (Suhas Daftuar)
56106a3 Expose RPC calls for estimatesmart functions (Alex Morcos)
e93a236 add estimateSmartFee to the unit test (Alex Morcos)
6303051 EstimateSmart functions consider mempool min fee (Alex Morcos)
f22ac4a Increase success threshold for fee estimation to 95% (Alex Morcos)
4fe2823 Change wallet and GUI code to use new smart fee estimation calls. (Alex Morcos)
22eca7d Add smart fee estimation functions (Alex Morcos)

16 files changed, 261 insertions, 66 deletions

diff --git a/qa/rpc-tests/smartfees.py b/qa/rpc-tests/smartfees.py
index c15c5fda09..ecfffc1b45 100755
--- a/qa/rpc-tests/smartfees.py
+++ b/qa/rpc-tests/smartfees.py
@@ -120,15 +120,26 @@ def check_estimates(node, fees_seen, max_invalid, print_estimates = True):
         last_e = e
     valid_estimate = False
     invalid_estimates = 0
-    for e in all_estimates:
+    for i,e in enumerate(all_estimates): # estimate is for i+1
         if e >= 0:
             valid_estimate = True
+            # estimatesmartfee should return the same result
+            assert_equal(node.estimatesmartfee(i+1)["feerate"], e)
+
         else:
             invalid_estimates += 1
-        # Once we're at a high enough confirmation count that we can give an estimate
-        # We should have estimates for all higher confirmation counts
-        if valid_estimate and e < 0:
-            raise AssertionError("Invalid estimate appears at higher confirm count than valid estimate")
+
+            # estimatesmartfee should still be valid
+            approx_estimate = node.estimatesmartfee(i+1)["feerate"]
+            answer_found = node.estimatesmartfee(i+1)["blocks"]
+            assert(approx_estimate > 0)
+            assert(answer_found > i+1)
+
+            # Once we're at a high enough confirmation count that we can give an estimate
+            # We should have estimates for all higher confirmation counts
+            if valid_estimate:
+                raise AssertionError("Invalid estimate appears at higher confirm count than valid estimate")
+
     # Check on the expected number of different confirmation counts
     # that we might not have valid estimates for
     if invalid_estimates > max_invalid:
@@ -184,13 +195,13 @@ class EstimateFeeTest(BitcoinTestFramework):
         # NOTE: the CreateNewBlock code starts counting block size at 1,000 bytes,
         # (17k is room enough for 110 or so transactions)
         self.nodes.append(start_node(1, self.options.tmpdir,
-                                     ["-blockprioritysize=1500", "-blockmaxsize=18000",
+                                     ["-blockprioritysize=1500", "-blockmaxsize=17000",
                                       "-maxorphantx=1000", "-relaypriority=0", "-debug=estimatefee"]))
         connect_nodes(self.nodes[1], 0)
 
         # Node2 is a stingy miner, that
-        # produces too small blocks (room for only 70 or so transactions)
-        node2args = ["-blockprioritysize=0", "-blockmaxsize=12000", "-maxorphantx=1000", "-relaypriority=0"]
+        # produces too small blocks (room for only 55 or so transactions)
+        node2args = ["-blockprioritysize=0", "-blockmaxsize=8000", "-maxorphantx=1000", "-relaypriority=0"]
 
         self.nodes.append(start_node(2, self.options.tmpdir, node2args))
         connect_nodes(self.nodes[0], 2)
@@ -229,22 +240,19 @@ class EstimateFeeTest(BitcoinTestFramework):
         self.fees_per_kb = []
         self.memutxo = []
         self.confutxo = self.txouts # Start with the set of confirmed txouts after splitting
-        print("Checking estimates for 1/2/3/6/15/25 blocks")
-        print("Creating transactions and mining them with a huge block size")
-        # Create transactions and mine 20 big blocks with node 0 such that the mempool is always emptied
-        self.transact_and_mine(30, self.nodes[0])
-        check_estimates(self.nodes[1], self.fees_per_kb, 1)
+        print("Will output estimates for 1/2/3/6/15/25 blocks")
 
-        print("Creating transactions and mining them with a block size that can't keep up")
-        # Create transactions and mine 30 small blocks with node 2, but create txs faster than we can mine
-        self.transact_and_mine(20, self.nodes[2])
-        check_estimates(self.nodes[1], self.fees_per_kb, 3)
+        for i in xrange(2):
+            print("Creating transactions and mining them with a block size that can't keep up")
+            # Create transactions and mine 10 small blocks with node 2, but create txs faster than we can mine
+            self.transact_and_mine(10, self.nodes[2])
+            check_estimates(self.nodes[1], self.fees_per_kb, 14)
 
-        print("Creating transactions and mining them at a block size that is just big enough")
-        # Generate transactions while mining 40 more blocks, this time with node1
-        # which mines blocks with capacity just above the rate that transactions are being created
-        self.transact_and_mine(40, self.nodes[1])
-        check_estimates(self.nodes[1], self.fees_per_kb, 2)
+            print("Creating transactions and mining them at a block size that is just big enough")
+            # Generate transactions while mining 10 more blocks, this time with node1
+            # which mines blocks with capacity just above the rate that transactions are being created
+            self.transact_and_mine(10, self.nodes[1])
+            check_estimates(self.nodes[1], self.fees_per_kb, 2)
 
         # Finish by mining a normal-sized block:
         while len(self.nodes[1].getrawmempool()) > 0:
diff --git a/src/main.h b/src/main.h
index eb61ff9570..347624c520 100644
--- a/src/main.h
+++ b/src/main.h
@@ -56,8 +56,6 @@ static const unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT = 101;
 static const unsigned int DEFAULT_DESCENDANT_LIMIT = 25;
 /** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */
 static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 101;
-/** Default for -maxmempool, maximum megabytes of mempool memory usage */
-static const unsigned int DEFAULT_MAX_MEMPOOL_SIZE = 300;
 /** Default for -mempoolexpiry, expiration time for mempool transactions in hours */
 static const unsigned int DEFAULT_MEMPOOL_EXPIRY = 72;
 /** The maximum size of a blk?????.dat file (since 0.8) */
diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp
index ffe31d1942..980ecf10df 100644
--- a/src/policy/fees.cpp
+++ b/src/policy/fees.cpp
@@ -4,6 +4,7 @@
 // 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"
@@ -504,6 +505,33 @@ CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
     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
@@ -513,6 +541,30 @@ double CBlockPolicyEstimator::estimatePriority(int confTarget)
     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;
diff --git a/src/policy/fees.h b/src/policy/fees.h
index 15577d128a..7a293267d4 100644
--- a/src/policy/fees.h
+++ b/src/policy/fees.h
@@ -15,6 +15,7 @@
 class CAutoFile;
 class CFeeRate;
 class CTxMemPoolEntry;
+class CTxMemPool;
 
 /** \class CBlockPolicyEstimator
  * The BlockPolicyEstimator is used for estimating the fee or priority needed
@@ -182,8 +183,8 @@ 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;
+/** 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 */
@@ -242,9 +243,21 @@ public:
     /** 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);
 
diff --git a/src/policy/policy.h b/src/policy/policy.h
index f269e8d476..c8d2c1a924 100644
--- a/src/policy/policy.h
+++ b/src/policy/policy.h
@@ -25,6 +25,8 @@ static const unsigned int MAX_STANDARD_TX_SIZE = 100000;
 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 = MAX_BLOCK_SIGOPS/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
diff --git a/src/qt/coincontroldialog.cpp b/src/qt/coincontroldialog.cpp
index 81b2597c3b..cbc41f3416 100644
--- a/src/qt/coincontroldialog.cpp
+++ b/src/qt/coincontroldialog.cpp
@@ -538,7 +538,7 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
         nBytes = nBytesInputs + ((CoinControlDialog::payAmounts.size() > 0 ? CoinControlDialog::payAmounts.size() + 1 : 2) * 34) + 10; // always assume +1 output for change here
 
         // Priority
-        double mempoolEstimatePriority = mempool.estimatePriority(nTxConfirmTarget);
+        double mempoolEstimatePriority = mempool.estimateSmartPriority(nTxConfirmTarget);
         dPriority = dPriorityInputs / (nBytes - nBytesInputs + (nQuantityUncompressed * 29)); // 29 = 180 - 151 (uncompressed public keys are over the limit. max 151 bytes of the input are ignored for priority)
         sPriorityLabel = CoinControlDialog::getPriorityLabel(dPriority, mempoolEstimatePriority);
 
@@ -550,10 +550,8 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
         // Fee
         nPayFee = CWallet::GetMinimumFee(nBytes, nTxConfirmTarget, mempool);
 
-        // Allow free?
-        double dPriorityNeeded = mempoolEstimatePriority;
-        if (dPriorityNeeded <= 0)
-            dPriorityNeeded = AllowFreeThreshold(); // not enough data, back to hard-coded
+        // Allow free? (require at least hard-coded threshold and default to that if no estimate)
+        double dPriorityNeeded = std::max(mempoolEstimatePriority, AllowFreeThreshold());
         fAllowFree = (dPriority >= dPriorityNeeded);
 
         if (fSendFreeTransactions)
@@ -649,8 +647,9 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
     double dFeeVary;
     if (payTxFee.GetFeePerK() > 0)
         dFeeVary = (double)std::max(CWallet::GetRequiredFee(1000), payTxFee.GetFeePerK()) / 1000;
-    else
-        dFeeVary = (double)std::max(CWallet::GetRequiredFee(1000), mempool.estimateFee(nTxConfirmTarget).GetFeePerK()) / 1000;
+    else {
+        dFeeVary = (double)std::max(CWallet::GetRequiredFee(1000), mempool.estimateSmartFee(nTxConfirmTarget).GetFeePerK()) / 1000;
+    }
     QString toolTip4 = tr("Can vary +/- %1 satoshi(s) per input.").arg(dFeeVary);
 
     l3->setToolTip(toolTip4);
@@ -686,7 +685,7 @@ void CoinControlDialog::updateView()
     QFlags<Qt::ItemFlag> flgTristate = Qt::ItemIsSelectable | Qt::ItemIsEnabled | Qt::ItemIsUserCheckable | Qt::ItemIsTristate;
 
     int nDisplayUnit = model->getOptionsModel()->getDisplayUnit();
-    double mempoolEstimatePriority = mempool.estimatePriority(nTxConfirmTarget);
+    double mempoolEstimatePriority = mempool.estimateSmartPriority(nTxConfirmTarget);
 
     std::map<QString, std::vector<COutput> > mapCoins;
     model->listCoins(mapCoins);
diff --git a/src/qt/sendcoinsdialog.cpp b/src/qt/sendcoinsdialog.cpp
index 4b030fdaa0..7b714be5b1 100644
--- a/src/qt/sendcoinsdialog.cpp
+++ b/src/qt/sendcoinsdialog.cpp
@@ -633,7 +633,8 @@ void SendCoinsDialog::updateSmartFeeLabel()
         return;
 
     int nBlocksToConfirm = defaultConfirmTarget - ui->sliderSmartFee->value();
-    CFeeRate feeRate = mempool.estimateFee(nBlocksToConfirm);
+    int estimateFoundAtBlocks = nBlocksToConfirm;
+    CFeeRate feeRate = mempool.estimateSmartFee(nBlocksToConfirm, &estimateFoundAtBlocks);
     if (feeRate <= CFeeRate(0)) // not enough data => minfee
     {
         ui->labelSmartFee->setText(BitcoinUnits::formatWithUnit(model->getOptionsModel()->getDisplayUnit(), CWallet::GetRequiredFee(1000)) + "/kB");
@@ -644,7 +645,7 @@ void SendCoinsDialog::updateSmartFeeLabel()
     {
         ui->labelSmartFee->setText(BitcoinUnits::formatWithUnit(model->getOptionsModel()->getDisplayUnit(), feeRate.GetFeePerK()) + "/kB");
         ui->labelSmartFee2->hide();
-        ui->labelFeeEstimation->setText(tr("Estimated to begin confirmation within %n block(s).", "", nBlocksToConfirm));
+        ui->labelFeeEstimation->setText(tr("Estimated to begin confirmation within %n block(s).", "", estimateFoundAtBlocks));
     }
 
     updateFeeMinimizedLabel();
diff --git a/src/rpcblockchain.cpp b/src/rpcblockchain.cpp
index 012370ed10..c80838e1f1 100644
--- a/src/rpcblockchain.cpp
+++ b/src/rpcblockchain.cpp
@@ -10,6 +10,7 @@
 #include "coins.h"
 #include "consensus/validation.h"
 #include "main.h"
+#include "policy/policy.h"
 #include "primitives/transaction.h"
 #include "rpcserver.h"
 #include "streams.h"
diff --git a/src/rpcclient.cpp b/src/rpcclient.cpp
index 343b6234d4..cab5819017 100644
--- a/src/rpcclient.cpp
+++ b/src/rpcclient.cpp
@@ -96,6 +96,8 @@ static const CRPCConvertParam vRPCConvertParams[] =
     { "getrawmempool", 0 },
     { "estimatefee", 0 },
     { "estimatepriority", 0 },
+    { "estimatesmartfee", 0 },
+    { "estimatesmartpriority", 0 },
     { "prioritisetransaction", 1 },
     { "prioritisetransaction", 2 },
     { "setban", 2 },
diff --git a/src/rpcmining.cpp b/src/rpcmining.cpp
index 3fd07fc374..19b031b860 100644
--- a/src/rpcmining.cpp
+++ b/src/rpcmining.cpp
@@ -726,3 +726,75 @@ UniValue estimatepriority(const UniValue& params, bool fHelp)
 
     return mempool.estimatePriority(nBlocks);
 }
+
+UniValue estimatesmartfee(const UniValue& params, bool fHelp)
+{
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "estimatesmartfee nblocks\n"
+            "\nWARNING: This interface is unstable and may disappear or change!\n"
+            "\nEstimates the approximate fee per kilobyte needed for a transaction to begin\n"
+            "confirmation within nblocks blocks if possible and return the number of blocks\n"
+            "for which the estimate is valid.\n"
+            "\nArguments:\n"
+            "1. nblocks     (numeric)\n"
+            "\nResult:\n"
+            "{\n"
+            "  \"feerate\" : x.x,     (numeric) estimate fee-per-kilobyte (in BTC)\n"
+            "  \"blocks\" : n         (numeric) block number where estimate was found\n"
+            "}\n"
+            "\n"
+            "A negative value is returned if not enough transactions and blocks\n"
+            "have been observed to make an estimate for any number of blocks.\n"
+            "However it will not return a value below the mempool reject fee.\n"
+            "\nExample:\n"
+            + HelpExampleCli("estimatesmartfee", "6")
+            );
+
+    RPCTypeCheck(params, boost::assign::list_of(UniValue::VNUM));
+
+    int nBlocks = params[0].get_int();
+
+    UniValue result(UniValue::VOBJ);
+    int answerFound;
+    CFeeRate feeRate = mempool.estimateSmartFee(nBlocks, &answerFound);
+    result.push_back(Pair("feerate", feeRate == CFeeRate(0) ? -1.0 : ValueFromAmount(feeRate.GetFeePerK())));
+    result.push_back(Pair("blocks", answerFound));
+    return result;
+}
+
+UniValue estimatesmartpriority(const UniValue& params, bool fHelp)
+{
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "estimatesmartpriority nblocks\n"
+            "\nWARNING: This interface is unstable and may disappear or change!\n"
+            "\nEstimates the approximate priority a zero-fee transaction needs to begin\n"
+            "confirmation within nblocks blocks if possible and return the number of blocks\n"
+            "for which the estimate is valid.\n"
+            "\nArguments:\n"
+            "1. nblocks     (numeric)\n"
+            "\nResult:\n"
+            "{\n"
+            "  \"priority\" : x.x,    (numeric) estimated priority\n"
+            "  \"blocks\" : n         (numeric) block number where estimate was found\n"
+            "}\n"
+            "\n"
+            "A negative value is returned if not enough transactions and blocks\n"
+            "have been observed to make an estimate for any number of blocks.\n"
+            "However if the mempool reject fee is set it will return 1e9 * MAX_MONEY.\n"
+            "\nExample:\n"
+            + HelpExampleCli("estimatesmartpriority", "6")
+            );
+
+    RPCTypeCheck(params, boost::assign::list_of(UniValue::VNUM));
+
+    int nBlocks = params[0].get_int();
+
+    UniValue result(UniValue::VOBJ);
+    int answerFound;
+    double priority = mempool.estimateSmartPriority(nBlocks, &answerFound);
+    result.push_back(Pair("priority", priority));
+    result.push_back(Pair("blocks", answerFound));
+    return result;
+}
diff --git a/src/rpcserver.cpp b/src/rpcserver.cpp
index 8bda5a0373..83d2c2d503 100644
--- a/src/rpcserver.cpp
+++ b/src/rpcserver.cpp
@@ -319,6 +319,8 @@ static const CRPCCommand vRPCCommands[] =
     { "util",               "verifymessage",          &verifymessage,          true  },
     { "util",               "estimatefee",            &estimatefee,            true  },
     { "util",               "estimatepriority",       &estimatepriority,       true  },
+    { "util",               "estimatesmartfee",       &estimatesmartfee,       true  },
+    { "util",               "estimatesmartpriority",  &estimatesmartpriority,  true  },
 
     /* Not shown in help */
     { "hidden",             "invalidateblock",        &invalidateblock,        true  },
diff --git a/src/rpcserver.h b/src/rpcserver.h
index dde8dfdcc3..fc88f82be8 100644
--- a/src/rpcserver.h
+++ b/src/rpcserver.h
@@ -193,6 +193,8 @@ extern UniValue getblocktemplate(const UniValue& params, bool fHelp);
 extern UniValue submitblock(const UniValue& params, bool fHelp);
 extern UniValue estimatefee(const UniValue& params, bool fHelp);
 extern UniValue estimatepriority(const UniValue& params, bool fHelp);
+extern UniValue estimatesmartfee(const UniValue& params, bool fHelp);
+extern UniValue estimatesmartpriority(const UniValue& params, bool fHelp);
 
 extern UniValue getnewaddress(const UniValue& params, bool fHelp); // in rpcwallet.cpp
 extern UniValue getaccountaddress(const UniValue& params, bool fHelp);
diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp
index c4f6660f6a..1315146f10 100644
--- a/src/test/policyestimator_tests.cpp
+++ b/src/test/policyestimator_tests.cpp
@@ -84,11 +84,18 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
         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
+            // So estimateFee(1,2,3) should fail and estimateFee(4) should return somewhere around
+            // 8*baserate.  estimateFee(4) %'s are 100,100,100,100,90 = average 98%
             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);
+            BOOST_CHECK(mpool.estimateFee(2) == CFeeRate(0));
+            BOOST_CHECK(mpool.estimateFee(3) == CFeeRate(0));
+            BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() < 8*baseRate.GetFeePerK() + deltaFee);
+            BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() > 8*baseRate.GetFeePerK() - deltaFee);
+            int answerFound;
+            BOOST_CHECK(mpool.estimateSmartFee(1, &answerFound) == mpool.estimateFee(4) && answerFound == 4);
+            BOOST_CHECK(mpool.estimateSmartFee(3, &answerFound) == mpool.estimateFee(4) && answerFound == 4);
+            BOOST_CHECK(mpool.estimateSmartFee(4, &answerFound) == mpool.estimateFee(4) && answerFound == 4);
+            BOOST_CHECK(mpool.estimateSmartFee(8, &answerFound) == mpool.estimateFee(8) && answerFound == 8);
         }
     }
 
@@ -97,9 +104,9 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
     // 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...
+    // so estimateFee(1) should return 10*baseRate.
+    // Second highest feerate has 100% chance of being included by 2 blocks,
+    // so estimateFee(2) should return 9*baseRate etc...
     for (int i = 1; i < 10;i++) {
         origFeeEst.push_back(mpool.estimateFee(i).GetFeePerK());
         origPriEst.push_back(mpool.estimatePriority(i));
@@ -107,10 +114,11 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
             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);
+        int mult = 11-i;
+        BOOST_CHECK(origFeeEst[i-1] < mult*baseRate.GetFeePerK() + deltaFee);
+        BOOST_CHECK(origFeeEst[i-1] > mult*baseRate.GetFeePerK() - deltaFee);
+        BOOST_CHECK(origPriEst[i-1] < pow(10,mult) * basepri + deltaPri);
+        BOOST_CHECK(origPriEst[i-1] > pow(10,mult) * basepri - deltaPri);
     }
 
     // Mine 50 more blocks with no transactions happening, estimates shouldn't change
@@ -140,9 +148,12 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
         mpool.removeForBlock(block, ++blocknum, dummyConflicted);
     }
 
+    int answerFound;
     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);
+        BOOST_CHECK(mpool.estimateFee(i) == CFeeRate(0) || mpool.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(mpool.estimateSmartFee(i, &answerFound).GetFeePerK() > origFeeEst[answerFound-1] - deltaFee);
+        BOOST_CHECK(mpool.estimatePriority(i) == -1 || mpool.estimatePriority(i) > origPriEst[i-1] - deltaPri);
+        BOOST_CHECK(mpool.estimateSmartPriority(i, &answerFound) > origPriEst[answerFound-1] - deltaPri);
     }
 
     // Mine all those transactions
@@ -162,9 +173,9 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
         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) {
+    // Mine 200 more blocks where everything is mined every block
+    // Estimates should be below original estimates
+    while (blocknum < 465) {
         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;
@@ -178,10 +189,22 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
         mpool.removeForBlock(block, ++blocknum, dummyConflicted);
         block.clear();
     }
-    for (int i = 1; i < 9; i++) {
+    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);
     }
+
+    // Test that if the mempool is limited, estimateSmartFee won't return a value below the mempool min fee
+    // and that estimateSmartPriority returns essentially an infinite value
+    mpool.addUnchecked(tx.GetHash(),  CTxMemPoolEntry(tx, feeV[0][5], GetTime(), priV[1][5], blocknum, mpool.HasNoInputsOf(tx)));
+    // evict that transaction which should set a mempool min fee of minRelayTxFee + feeV[0][5]
+    mpool.TrimToSize(1);
+    BOOST_CHECK(mpool.GetMinFee(1).GetFeePerK() > feeV[0][5]);
+    for (int i = 1; i < 10; i++) {
+        BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= mpool.estimateFee(i).GetFeePerK());
+        BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= mpool.GetMinFee(1).GetFeePerK());
+        BOOST_CHECK(mpool.estimateSmartPriority(i) == INF_PRIORITY);
+    }
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index a772e7adea..ec7971c2f1 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -701,11 +701,21 @@ CFeeRate CTxMemPool::estimateFee(int nBlocks) const
     LOCK(cs);
     return minerPolicyEstimator->estimateFee(nBlocks);
 }
+CFeeRate CTxMemPool::estimateSmartFee(int nBlocks, int *answerFoundAtBlocks) const
+{
+    LOCK(cs);
+    return minerPolicyEstimator->estimateSmartFee(nBlocks, answerFoundAtBlocks, *this);
+}
 double CTxMemPool::estimatePriority(int nBlocks) const
 {
     LOCK(cs);
     return minerPolicyEstimator->estimatePriority(nBlocks);
 }
+double CTxMemPool::estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks) const
+{
+    LOCK(cs);
+    return minerPolicyEstimator->estimateSmartPriority(nBlocks, answerFoundAtBlocks, *this);
+}
 
 bool
 CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
diff --git a/src/txmempool.h b/src/txmempool.h
index 7b5843a8d0..5d8231fb77 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -454,9 +454,21 @@ public:
 
     bool lookup(uint256 hash, CTransaction& result) const;
 
+    /** Estimate fee rate needed to get into the next nBlocks
+     *  If no answer can be given at nBlocks, return an estimate
+     *  at the lowest number of blocks where one can be given
+     */
+    CFeeRate estimateSmartFee(int nBlocks, int *answerFoundAtBlocks = NULL) const;
+
     /** Estimate fee rate needed to get into the next nBlocks */
     CFeeRate estimateFee(int nBlocks) const;
 
+    /** Estimate priority needed to get into the next nBlocks
+     *  If no answer can be given at nBlocks, return an estimate
+     *  at the lowest number of blocks where one can be given
+     */
+    double estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks = NULL) const;
+
     /** Estimate priority needed to get into the next nBlocks */
     double estimatePriority(int nBlocks) const;
     
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 1b152f4192..c5246d909e 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2010,13 +2010,9 @@ bool CWallet::CreateTransaction(const vector<CRecipient>& vecSend, CWalletTx& wt
                 if (fSendFreeTransactions && nBytes <= MAX_FREE_TRANSACTION_CREATE_SIZE)
                 {
                     // Not enough fee: enough priority?
-                    double dPriorityNeeded = mempool.estimatePriority(nTxConfirmTarget);
-                    // Not enough mempool history to estimate: use hard-coded AllowFree.
-                    if (dPriorityNeeded <= 0 && AllowFree(dPriority))
-                        break;
-
-                    // Small enough, and priority high enough, to send for free
-                    if (dPriorityNeeded > 0 && dPriority >= dPriorityNeeded)
+                    double dPriorityNeeded = mempool.estimateSmartPriority(nTxConfirmTarget);
+                    // Require at least hard-coded AllowFree.
+                    if (dPriority >= dPriorityNeeded && AllowFree(dPriority))
                         break;
                 }
 
@@ -2120,12 +2116,14 @@ CAmount CWallet::GetMinimumFee(unsigned int nTxBytes, unsigned int nConfirmTarge
     if (fPayAtLeastCustomFee && nFeeNeeded > 0 && nFeeNeeded < payTxFee.GetFeePerK())
         nFeeNeeded = payTxFee.GetFeePerK();
     // User didn't set: use -txconfirmtarget to estimate...
-    if (nFeeNeeded == 0)
-        nFeeNeeded = pool.estimateFee(nConfirmTarget).GetFee(nTxBytes);
-    // ... unless we don't have enough mempool data, in which case fall
-    // back to the required fee
-    if (nFeeNeeded == 0)
-        nFeeNeeded = GetRequiredFee(nTxBytes);
+    if (nFeeNeeded == 0) {
+        int estimateFoundTarget = nConfirmTarget;
+        nFeeNeeded = pool.estimateSmartFee(nConfirmTarget, &estimateFoundTarget).GetFee(nTxBytes);
+        // ... unless we don't have enough mempool data for our desired target
+        // so we make sure we're paying at least minTxFee
+        if (nFeeNeeded == 0 || (unsigned int)estimateFoundTarget > nConfirmTarget)
+            nFeeNeeded = std::max(nFeeNeeded, GetRequiredFee(nTxBytes));
+    }
     // prevent user from paying a non-sense fee (like 1 satoshi): 0 < fee < minRelayFee
     if (nFeeNeeded < ::minRelayTxFee.GetFee(nTxBytes))
         nFeeNeeded = ::minRelayTxFee.GetFee(nTxBytes);