Use fee/priority estimates in wallet CreateTransaction

The wallet now uses the mempool fee estimator with a new
command-line option: -txconfirmtarget (default: 1) instead
of using hard-coded fees or priorities.

A new bitcoind that hasn't seen enough transactions to estimate
will fall back to the old hard-coded minimum priority or
transaction fee.

-paytxfee option overrides -txconfirmtarget.

Relaying and mining code isn't changed.

For Qt, the coin control dialog now uses priority estimates to
label transaction priority (instead of hard-coded constants);
unspent outputs were consistently labeled with a much higher
priority than is justified by the free transactions actually
being accepted into blocks.

I did not implement any GUI for setting -txconfirmtarget; I would
suggest getting rid of the "Pay transaction fee" GUI and replace
it with either "target number of confirmations" or maybe
a "faster confirmation <--> lower fee" slider or select box.

8 files changed, 85 insertions, 47 deletions

diff --git a/src/core.h b/src/core.h
index 8606831575..d6e7ab870d 100644
--- a/src/core.h
+++ b/src/core.h
@@ -131,7 +131,8 @@ public:
     friend bool operator<(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK < b.nSatoshisPerK; }
     friend bool operator>(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK > b.nSatoshisPerK; }
     friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK == b.nSatoshisPerK; }
-
+    friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK <= b.nSatoshisPerK; }
+    friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK >= b.nSatoshisPerK; }
     std::string ToString() const;
 
     IMPLEMENT_SERIALIZE( READWRITE(nSatoshisPerK); )
diff --git a/src/init.cpp b/src/init.cpp
index 2dd141a735..3ee0f2aa39 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -254,6 +254,7 @@ std::string HelpMessage(HelpMessageMode mode)
     strUsage += "\n" + _("Wallet options:") + "\n";
     strUsage += "  -disablewallet         " + _("Do not load the wallet and disable wallet RPC calls") + "\n";
     strUsage += "  -paytxfee=<amt>        " + strprintf(_("Fee (in BTC/kB) to add to transactions you send (default: %s)"), FormatMoney(payTxFee.GetFeePerK())) + "\n";
+    strUsage += "  -txconfirmtarget=<n>   " + _("If paytxfee is not set, include enough fee so transactions are confirmed on average within n blocks (default: 1)") + "\n";
     strUsage += "  -rescan                " + _("Rescan the block chain for missing wallet transactions") + " " + _("on startup") + "\n";
     strUsage += "  -salvagewallet         " + _("Attempt to recover private keys from a corrupt wallet.dat") + " " + _("on startup") + "\n";
     strUsage += "  -spendzeroconfchange   " + _("Spend unconfirmed change when sending transactions (default: 1)") + "\n";
@@ -635,7 +636,13 @@ bool AppInit2(boost::thread_group& threadGroup)
         if (nFeePerK > nHighTransactionFeeWarning)
             InitWarning(_("Warning: -paytxfee is set very high! This is the transaction fee you will pay if you send a transaction."));
         payTxFee = CFeeRate(nFeePerK, 1000);
+        if (payTxFee < CTransaction::minRelayTxFee)
+        {
+            return InitError(strprintf(_("Invalid amount for -paytxfee=<amount>: '%s' (must be at least %s)"),
+                                       mapArgs["-paytxfee"], CTransaction::minRelayTxFee.ToString()));
+        }
     }
+    nTxConfirmTarget = GetArg("-txconfirmtarget", 1);
     bSpendZeroConfChange = GetArg("-spendzeroconfchange", true);
 
     std::string strWalletFile = GetArg("-wallet", "wallet.dat");
diff --git a/src/main.cpp b/src/main.cpp
index 04d9523e26..6be1a29c6c 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -858,7 +858,7 @@ bool CheckTransaction(const CTransaction& tx, CValidationState &state)
     return true;
 }
 
-int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree, enum GetMinFee_mode mode)
+int64_t GetMinRelayFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree)
 {
     {
         LOCK(mempool.cs);
@@ -870,10 +870,7 @@ int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree,
             return 0;
     }
 
-    // Base fee is either minTxFee or minRelayTxFee
-    CFeeRate baseFeeRate = (mode == GMF_RELAY) ? tx.minRelayTxFee : tx.minTxFee;
-
-    int64_t nMinFee = baseFeeRate.GetFee(nBytes);
+    int64_t nMinFee = tx.minRelayTxFee.GetFee(nBytes);
 
     if (fAllowFree)
     {
@@ -881,9 +878,7 @@ int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree,
         // * If we are relaying we allow transactions up to DEFAULT_BLOCK_PRIORITY_SIZE - 1000
         //   to be considered to fall into this category. We don't want to encourage sending
         //   multiple transactions instead of one big transaction to avoid fees.
-        // * If we are creating a transaction we allow transactions up to 1,000 bytes
-        //   to be considered safe and assume they can likely make it into this section.
-        if (nBytes < (mode == GMF_SEND ? 1000 : (DEFAULT_BLOCK_PRIORITY_SIZE - 1000)))
+        if (nBytes < (DEFAULT_BLOCK_PRIORITY_SIZE - 1000))
             nMinFee = 0;
     }
 
@@ -1005,7 +1000,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         unsigned int nSize = entry.GetTxSize();
 
         // Don't accept it if it can't get into a block
-        int64_t txMinFee = GetMinFee(tx, nSize, true, GMF_RELAY);
+        int64_t txMinFee = GetMinRelayFee(tx, nSize, true);
         if (fLimitFree && nFees < txMinFee)
             return state.DoS(0, error("AcceptToMemoryPool : not enough fees %s, %d < %d",
                                       hash.ToString(), nFees, txMinFee),
diff --git a/src/main.h b/src/main.h
index 19f4469008..e8df17dda0 100644
--- a/src/main.h
+++ b/src/main.h
@@ -245,14 +245,7 @@ struct CDiskTxPos : public CDiskBlockPos
 };
 
 
-
-enum GetMinFee_mode
-{
-    GMF_RELAY,
-    GMF_SEND,
-};
-
-int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree, enum GetMinFee_mode mode);
+int64_t GetMinRelayFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree);
 
 //
 // Check transaction inputs, and make sure any
diff --git a/src/qt/coincontroldialog.cpp b/src/qt/coincontroldialog.cpp
index c6a6150392..73494f52ea 100644
--- a/src/qt/coincontroldialog.cpp
+++ b/src/qt/coincontroldialog.cpp
@@ -16,6 +16,8 @@
 #include "main.h"
 #include "wallet.h"
 
+#include <boost/assign/list_of.hpp> // for 'map_list_of()'
+
 #include <QApplication>
 #include <QCheckBox>
 #include <QCursor>
@@ -400,23 +402,24 @@ void CoinControlDialog::viewItemChanged(QTreeWidgetItem* item, int column)
 }
 
 // return human readable label for priority number
-QString CoinControlDialog::getPriorityLabel(double dPriority)
+QString CoinControlDialog::getPriorityLabel(const CTxMemPool& pool, double dPriority)
 {
-    if (AllowFree(dPriority)) // at least medium
+    // confirmations -> textual description
+    typedef std::map<unsigned int, QString> PriorityDescription;
+    static PriorityDescription priorityDescriptions = boost::assign::map_list_of
+        (1, tr("highest"))(2, tr("higher"))(3, tr("high"))
+        (5, tr("medium-high"))(6, tr("medium"))
+        (10, tr("low-medium"))(15, tr("low"))
+        (20, tr("lower"));
+
+    BOOST_FOREACH(const PriorityDescription::value_type& i, priorityDescriptions)
     {
-        if      (AllowFree(dPriority / 1000000))  return tr("highest");
-        else if (AllowFree(dPriority / 100000))   return tr("higher");
-        else if (AllowFree(dPriority / 10000))    return tr("high");
-        else if (AllowFree(dPriority / 1000))     return tr("medium-high");
-        else                                      return tr("medium");
-    }
-    else
-    {
-        if      (AllowFree(dPriority * 10))   return tr("low-medium");
-        else if (AllowFree(dPriority * 100))  return tr("low");
-        else if (AllowFree(dPriority * 1000)) return tr("lower");
-        else                                  return tr("lowest");
+        double p = mempool.estimatePriority(i.first);
+        if (p > 0 && dPriority >= p) return i.second;
     }
+    // Note: if mempool hasn't accumulated enough history (estimatePriority
+    // returns -1) we're conservative and classify as "lowest"
+    return tr("lowest");
 }
 
 // shows count of locked unspent outputs
@@ -518,15 +521,20 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
 
         // Priority
         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);
+        sPriorityLabel = CoinControlDialog::getPriorityLabel(mempool, dPriority);
 
         // Fee
         int64_t nFee = payTxFee.GetFee(max((unsigned int)1000, nBytes));
 
         // Min Fee
-        int64_t nMinFee = GetMinFee(txDummy, nBytes, AllowFree(dPriority), GMF_SEND);
+        nPayFee = CWallet::GetMinimumFee(nBytes, nTxConfirmTarget, mempool);
+
+        double dPriorityNeeded = mempool.estimatePriority(nTxConfirmTarget);
+        if (dPriorityNeeded <= 0) // Not enough mempool history: never send free
+            dPriorityNeeded = std::numeric_limits<double>::max();
 
-        nPayFee = max(nFee, nMinFee);
+        if (nBytes <= MAX_FREE_TRANSACTION_CREATE_SIZE && dPriority >= dPriorityNeeded)
+            nPayFee = 0;
 
         if (nPayAmount > 0)
         {
@@ -591,7 +599,7 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
     }
 
     // turn labels "red"
-    l5->setStyleSheet((nBytes >= 1000) ? "color:red;" : "");                            // Bytes >= 1000
+    l5->setStyleSheet((nBytes >= MAX_FREE_TRANSACTION_CREATE_SIZE) ? "color:red;" : "");// Bytes >= 1000
     l6->setStyleSheet((dPriority > 0 && !AllowFree(dPriority)) ? "color:red;" : "");    // Priority < "medium"
     l7->setStyleSheet((fDust) ? "color:red;" : "");                                     // Dust = "yes"
 
@@ -732,7 +740,7 @@ void CoinControlDialog::updateView()
 
             // priority
             double dPriority = ((double)out.tx->vout[out.i].nValue  / (nInputSize + 78)) * (out.nDepth+1); // 78 = 2 * 34 + 10
-            itemOutput->setText(COLUMN_PRIORITY, CoinControlDialog::getPriorityLabel(dPriority));
+            itemOutput->setText(COLUMN_PRIORITY, CoinControlDialog::getPriorityLabel(mempool, dPriority));
             itemOutput->setText(COLUMN_PRIORITY_INT64, strPad(QString::number((int64_t)dPriority), 20, " "));
             dPrioritySum += (double)out.tx->vout[out.i].nValue  * (out.nDepth+1);
             nInputSum    += nInputSize;
@@ -765,7 +773,7 @@ void CoinControlDialog::updateView()
             itemWalletAddress->setText(COLUMN_CHECKBOX, "(" + QString::number(nChildren) + ")");
             itemWalletAddress->setText(COLUMN_AMOUNT, BitcoinUnits::format(nDisplayUnit, nSum));
             itemWalletAddress->setText(COLUMN_AMOUNT_INT64, strPad(QString::number(nSum), 15, " "));
-            itemWalletAddress->setText(COLUMN_PRIORITY, CoinControlDialog::getPriorityLabel(dPrioritySum));
+            itemWalletAddress->setText(COLUMN_PRIORITY, CoinControlDialog::getPriorityLabel(mempool, dPrioritySum));
             itemWalletAddress->setText(COLUMN_PRIORITY_INT64, strPad(QString::number((int64_t)dPrioritySum), 20, " "));
         }
     }
diff --git a/src/qt/coincontroldialog.h b/src/qt/coincontroldialog.h
index 465e2a009d..4f7422642f 100644
--- a/src/qt/coincontroldialog.h
+++ b/src/qt/coincontroldialog.h
@@ -19,6 +19,7 @@ namespace Ui {
 }
 class WalletModel;
 class CCoinControl;
+class CTxMemPool;
 
 class CoinControlDialog : public QDialog
 {
@@ -32,7 +33,7 @@ public:
 
     // static because also called from sendcoinsdialog
     static void updateLabels(WalletModel*, QDialog*);
-    static QString getPriorityLabel(double);
+    static QString getPriorityLabel(const CTxMemPool& pool, double);
 
     static QList<qint64> payAmounts;
     static CCoinControl *coinControl;
diff --git a/src/wallet.cpp b/src/wallet.cpp
index daca7ac04b..d9187e4be3 100644
--- a/src/wallet.cpp
+++ b/src/wallet.cpp
@@ -18,6 +18,7 @@ using namespace std;
 
 // Settings
 CFeeRate payTxFee(DEFAULT_TRANSACTION_FEE);
+unsigned int nTxConfirmTarget = 1;
 bool bSpendZeroConfChange = true;
 
 //////////////////////////////////////////////////////////////////////////////
@@ -1273,6 +1274,7 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
         return false;
     }
 
+    wtxNew.fTimeReceivedIsTxTime = true;
     wtxNew.BindWallet(this);
     CMutableTransaction txNew;
 
@@ -1393,19 +1395,31 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
                 }
                 dPriority = wtxNew.ComputePriority(dPriority, nBytes);
 
-                // Check that enough fee is included
-                int64_t nPayFee = payTxFee.GetFee(nBytes);
-                bool fAllowFree = AllowFree(dPriority);
-                int64_t nMinFee = GetMinFee(wtxNew, nBytes, fAllowFree, GMF_SEND);
-                if (nFeeRet < max(nPayFee, nMinFee))
+                int64_t nFeeNeeded = GetMinimumFee(nBytes, nTxConfirmTarget, mempool);
+
+                if (nFeeRet >= nFeeNeeded)
+                    break; // Done, enough fee included.
+
+                // Too big to send for free? Include more fee and try again:
+                if (nBytes > MAX_FREE_TRANSACTION_CREATE_SIZE)
                 {
-                    nFeeRet = max(nPayFee, nMinFee);
+                    nFeeRet = nFeeNeeded;
                     continue;
                 }
 
-                wtxNew.fTimeReceivedIsTxTime = true;
+                // 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;
 
-                break;
+                // Small enough, and priority high enough, to send for free
+                if (dPriority >= dPriorityNeeded)
+                    break;
+
+                // Include more fee and try again.
+                nFeeRet = nFeeNeeded;
+                continue;
             }
         }
     }
@@ -1513,6 +1527,20 @@ string CWallet::SendMoneyToDestination(const CTxDestination& address, int64_t nV
     return SendMoney(scriptPubKey, nValue, wtxNew);
 }
 
+int64_t CWallet::GetMinimumFee(unsigned int nTxBytes, unsigned int nConfirmTarget, const CTxMemPool& pool)
+{
+    // payTxFee is user-set "I want to pay this much"
+    int64_t nFeeNeeded = payTxFee.GetFee(nTxBytes);
+    // 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 a hard-coded fee
+    if (nFeeNeeded == 0)
+        nFeeNeeded = CTransaction::minTxFee.GetFee(nTxBytes);
+    return nFeeNeeded;
+}
+
 
 
 
diff --git a/src/wallet.h b/src/wallet.h
index 1c2512d678..19a1b18523 100644
--- a/src/wallet.h
+++ b/src/wallet.h
@@ -25,12 +25,15 @@
 
 // Settings
 extern CFeeRate payTxFee;
+extern unsigned int nTxConfirmTarget;
 extern bool bSpendZeroConfChange;
 
 // -paytxfee default
 static const int64_t DEFAULT_TRANSACTION_FEE = 0;
 // -paytxfee will warn if called with a higher fee than this amount (in satoshis) per KB
 static const int nHighTransactionFeeWarning = 0.01 * COIN;
+// Largest (in bytes) free transaction we're willing to create
+static const unsigned int MAX_FREE_TRANSACTION_CREATE_SIZE = 1000;
 
 class CAccountingEntry;
 class CCoinControl;
@@ -265,6 +268,8 @@ public:
     std::string SendMoney(CScript scriptPubKey, int64_t nValue, CWalletTx& wtxNew);
     std::string SendMoneyToDestination(const CTxDestination &address, int64_t nValue, CWalletTx& wtxNew);
 
+    static int64_t GetMinimumFee(unsigned int nTxBytes, unsigned int nConfirmTarget, const CTxMemPool& pool);
+
     bool NewKeyPool();
     bool TopUpKeyPool(unsigned int kpSize = 0);
     void ReserveKeyFromKeyPool(int64_t& nIndex, CKeyPool& keypool);