Merge pull request #3959

171ca77 estimatefee / estimatepriority RPC methods (Gavin Andresen)
0193fb8 Allow multiple regression tests to run at once (Gavin Andresen)
c6cb21d Type-safe CFeeRate class (Gavin Andresen)

26 files changed, 909 insertions, 158 deletions

diff --git a/doc/release-notes.md b/doc/release-notes.md
index f16eec32a2..9272d427cd 100644
--- a/doc/release-notes.md
+++ b/doc/release-notes.md
@@ -1,2 +1,21 @@
 (note: this is a temporary file, to be added-to by anybody, and moved to
 release-notes at release time)
+
+New RPC methods
+===============
+
+Fee/Priority estimation
+-----------------------
+
+estimatefee nblocks : Returns approximate fee-per-1,000-bytes needed for
+a transaction to be confirmed within nblocks. Returns -1 if not enough
+transactions have been observed to compute a good estimate.
+
+estimatepriority nblocks : Returns approximate priority needed for
+a zero-fee transaction to confirm within nblocks. Returns -1 if not
+enough free transactions have been observed to compute a good
+estimate.
+
+Statistics used to estimate fees and priorities are saved in the
+data directory in the 'fee_estimates.dat' file just before
+program shutdown, and are read in at startup.
diff --git a/qa/rpc-tests/smartfees.py b/qa/rpc-tests/smartfees.py
new file mode 100755
index 0000000000..e8abbfba19
--- /dev/null
+++ b/qa/rpc-tests/smartfees.py
@@ -0,0 +1,142 @@
+#!/usr/bin/env python
+
+#
+# Test fee estimation code
+#
+
+# Add python-bitcoinrpc to module search path:
+import os
+import sys
+sys.path.append(os.path.join(os.path.dirname(os.path.abspath(__file__)), "python-bitcoinrpc"))
+
+import json
+import random
+import shutil
+import subprocess
+import tempfile
+import traceback
+
+from bitcoinrpc.authproxy import AuthServiceProxy, JSONRPCException
+from util import *
+
+
+def run_test(nodes, test_dir):
+    nodes.append(start_node(0, test_dir,
+                            ["-debug=mempool", "-debug=estimatefee"]))
+    # Node1 mines small-but-not-tiny blocks, and allows free transactions.
+    # NOTE: the CreateNewBlock code starts counting block size at 1,000 bytes,
+    # so blockmaxsize of 2,000 is really just 1,000 bytes (room enough for
+    # 6 or 7 transactions)
+    nodes.append(start_node(1, test_dir,
+                            ["-blockprioritysize=1500", "-blockmaxsize=2000",
+                             "-debug=mempool", "-debug=estimatefee"]))
+    connect_nodes(nodes[1], 0)
+
+    # Node2 is a stingy miner, that
+    # produces very small blocks (room for only 3 or so transactions)
+    node2args = [ "-blockprioritysize=0", "-blockmaxsize=1500",
+                             "-debug=mempool", "-debug=estimatefee"]
+    nodes.append(start_node(2, test_dir, node2args))
+    connect_nodes(nodes[2], 0)
+
+    sync_blocks(nodes)
+
+    # Prime the memory pool with pairs of transactions
+    # (high-priority, random fee and zero-priority, random fee)
+    min_fee = Decimal("0.001")
+    fees_per_kb = [];
+    for i in range(12):
+        (txid, txhex, fee) = random_zeropri_transaction(nodes, Decimal("1.1"),
+                                                        min_fee, min_fee, 20)
+        tx_kbytes = (len(txhex)/2)/1000.0
+        fees_per_kb.append(float(fee)/tx_kbytes)
+
+    # Mine blocks with node2 until the memory pool clears:
+    count_start = nodes[2].getblockcount()
+    while len(nodes[2].getrawmempool()) > 0:
+        nodes[2].setgenerate(True, 1)
+        sync_blocks(nodes)
+
+    all_estimates = [ nodes[0].estimatefee(i) for i in range(1,20) ]
+    print("Fee estimates, super-stingy miner: "+str([str(e) for e in all_estimates]))
+
+    # Estimates should be within the bounds of what transactions fees actually were:
+    delta = 1.0e-6 # account for rounding error
+    for e in filter(lambda x: x >= 0, all_estimates):
+        if float(e)+delta < min(fees_per_kb) or float(e)-delta > max(fees_per_kb):
+            raise AssertionError("Estimated fee (%f) out of range (%f,%f)"%(float(e), min_fee_kb, max_fee_kb))
+
+    # Generate transactions while mining 30 more blocks, this time with node1:
+    for i in range(30):
+        for j in range(random.randrange(6-4,6+4)):
+            (txid, txhex, fee) = random_transaction(nodes, Decimal("1.1"),
+                                                    Decimal("0.0"), min_fee, 20)
+            tx_kbytes = (len(txhex)/2)/1000.0
+            fees_per_kb.append(float(fee)/tx_kbytes)
+        nodes[1].setgenerate(True, 1)
+        sync_blocks(nodes)
+
+    all_estimates = [ nodes[0].estimatefee(i) for i in range(1,20) ]
+    print("Fee estimates, more generous miner: "+str([ str(e) for e in all_estimates]))
+    for e in filter(lambda x: x >= 0, all_estimates):
+        if float(e)+delta < min(fees_per_kb) or float(e)-delta > max(fees_per_kb):
+            raise AssertionError("Estimated fee (%f) out of range (%f,%f)"%(float(e), min_fee_kb, max_fee_kb))
+
+    # Finish by mining a normal-sized block:
+    while len(nodes[0].getrawmempool()) > 0:
+        nodes[0].setgenerate(True, 1)
+        sync_blocks(nodes)
+
+    final_estimates = [ nodes[0].estimatefee(i) for i in range(1,20) ]
+    print("Final fee estimates: "+str([ str(e) for e in final_estimates]))
+
+def main():
+    import optparse
+
+    parser = optparse.OptionParser(usage="%prog [options]")
+    parser.add_option("--nocleanup", dest="nocleanup", default=False, action="store_true",
+                      help="Leave bitcoinds and test.* datadir on exit or error")
+    parser.add_option("--srcdir", dest="srcdir", default="../../src",
+                      help="Source directory containing bitcoind/bitcoin-cli (default: %default%)")
+    parser.add_option("--tmpdir", dest="tmpdir", default=tempfile.mkdtemp(prefix="test"),
+                      help="Root directory for datadirs")
+    (options, args) = parser.parse_args()
+
+    os.environ['PATH'] = options.srcdir+":"+os.environ['PATH']
+
+    check_json_precision()
+
+    success = False
+    nodes = []
+    try:
+        print("Initializing test directory "+options.tmpdir)
+        print("  node0 running at: 127.0.0.1:%d"%(p2p_port(0)))
+        if not os.path.isdir(options.tmpdir):
+            os.makedirs(options.tmpdir)
+        initialize_chain(options.tmpdir)
+
+        run_test(nodes, options.tmpdir)
+
+        success = True
+
+    except AssertionError as e:
+        print("Assertion failed: "+e.message)
+    except Exception as e:
+        print("Unexpected exception caught during testing: "+str(e))
+        traceback.print_tb(sys.exc_info()[2])
+
+    if not options.nocleanup:
+        print("Cleaning up")
+        stop_nodes(nodes)
+        wait_bitcoinds()
+        shutil.rmtree(options.tmpdir)
+
+    if success:
+        print("Tests successful")
+        sys.exit(0)
+    else:
+        print("Failed")
+        sys.exit(1)
+
+if __name__ == '__main__':
+    main()
diff --git a/qa/rpc-tests/util.py b/qa/rpc-tests/util.py
index 40f4a1458f..eded098c7c 100644
--- a/qa/rpc-tests/util.py
+++ b/qa/rpc-tests/util.py
@@ -12,6 +12,7 @@ sys.path.append(os.path.join(os.path.dirname(os.path.abspath(__file__)), "python
 
 from decimal import Decimal
 import json
+import random
 import shutil
 import subprocess
 import time
@@ -20,8 +21,10 @@ import re
 from bitcoinrpc.authproxy import AuthServiceProxy, JSONRPCException
 from util import *
 
-START_P2P_PORT=11000
-START_RPC_PORT=11100
+def p2p_port(n):
+    return 11000 + n + os.getpid()%999
+def rpc_port(n):
+    return 12000 + n + os.getpid()%999
 
 def check_json_precision():
     """Make sure json library being used does not lose precision converting BTC values"""
@@ -58,6 +61,18 @@ def sync_mempools(rpc_connections):
 
 bitcoind_processes = []
 
+def initialize_datadir(dir, n):
+    datadir = os.path.join(dir, "node"+str(n))
+    if not os.path.isdir(datadir):
+        os.makedirs(datadir)
+    with open(os.path.join(datadir, "bitcoin.conf"), 'w') as f:
+        f.write("regtest=1\n");
+        f.write("rpcuser=rt\n");
+        f.write("rpcpassword=rt\n");
+        f.write("port="+str(p2p_port(n))+"\n");
+        f.write("rpcport="+str(rpc_port(n))+"\n");
+    return datadir
+
 def initialize_chain(test_dir):
     """
     Create (or copy from cache) a 200-block-long chain and
@@ -69,17 +84,10 @@ def initialize_chain(test_dir):
         devnull = open("/dev/null", "w+")
         # Create cache directories, run bitcoinds:
         for i in range(4):
-            datadir = os.path.join("cache", "node"+str(i))
-            os.makedirs(datadir)
-            with open(os.path.join(datadir, "bitcoin.conf"), 'w') as f:
-                f.write("regtest=1\n");
-                f.write("rpcuser=rt\n");
-                f.write("rpcpassword=rt\n");
-                f.write("port="+str(START_P2P_PORT+i)+"\n");
-                f.write("rpcport="+str(START_RPC_PORT+i)+"\n");
+            datadir=initialize_datadir("cache", i)
             args = [ "bitcoind", "-keypool=1", "-datadir="+datadir ]
             if i > 0:
-                args.append("-connect=127.0.0.1:"+str(START_P2P_PORT))
+                args.append("-connect=127.0.0.1:"+str(p2p_port(0)))
             bitcoind_processes.append(subprocess.Popen(args))
             subprocess.check_call([ "bitcoin-cli", "-datadir="+datadir,
                                     "-rpcwait", "getblockcount"], stdout=devnull)
@@ -87,7 +95,7 @@ def initialize_chain(test_dir):
         rpcs = []
         for i in range(4):
             try:
-                url = "http://rt:rt@127.0.0.1:%d"%(START_RPC_PORT+i,)
+                url = "http://rt:rt@127.0.0.1:%d"%(rpc_port(i),)
                 rpcs.append(AuthServiceProxy(url))
             except:
                 sys.stderr.write("Error connecting to "+url+"\n")
@@ -112,6 +120,7 @@ def initialize_chain(test_dir):
         from_dir = os.path.join("cache", "node"+str(i))
         to_dir = os.path.join(test_dir,  "node"+str(i))
         shutil.copytree(from_dir, to_dir)
+        initialize_datadir(test_dir, i) # Overwrite port/rpcport in bitcoin.conf
 
 def _rpchost_to_args(rpchost):
     '''Convert optional IP:port spec to rpcconnect/rpcport args'''
@@ -133,25 +142,28 @@ def _rpchost_to_args(rpchost):
         rv += ['-rpcport=' + rpcport]
     return rv
 
-def start_nodes(num_nodes, dir, extra_args=None, rpchost=None):
-    # Start bitcoinds, and wait for RPC interface to be up and running:
+def start_node(i, dir, extra_args=None, rpchost=None):
+    """
+    Start a bitcoind and return RPC connection to it
+    """
+    datadir = os.path.join(dir, "node"+str(i))
+    args = [ "bitcoind", "-datadir="+datadir, "-keypool=1" ]
+    if extra_args is not None: args.extend(extra_args)
+    bitcoind_processes.append(subprocess.Popen(args))
     devnull = open("/dev/null", "w+")
-    for i in range(num_nodes):
-        datadir = os.path.join(dir, "node"+str(i))
-        args = [ "bitcoind", "-datadir="+datadir ]
-        if extra_args is not None:
-            args += extra_args[i]
-        bitcoind_processes.append(subprocess.Popen(args))
-        subprocess.check_call([ "bitcoin-cli", "-datadir="+datadir] +
-                                  _rpchost_to_args(rpchost)  +
-                                  ["-rpcwait", "getblockcount"], stdout=devnull)
+    subprocess.check_call([ "bitcoin-cli", "-datadir="+datadir] +
+                          _rpchost_to_args(rpchost)  +
+                          ["-rpcwait", "getblockcount"], stdout=devnull)
     devnull.close()
-    # Create&return JSON-RPC connections
-    rpc_connections = []
-    for i in range(num_nodes):
-        url = "http://rt:rt@%s:%d" % (rpchost or '127.0.0.1', START_RPC_PORT+i,)
-        rpc_connections.append(AuthServiceProxy(url))
-    return rpc_connections
+    url = "http://rt:rt@%s:%d" % (rpchost or '127.0.0.1', rpc_port(i))
+    return AuthServiceProxy(url)
+
+def start_nodes(num_nodes, dir, extra_args=None, rpchost=None):
+    """
+    Start multiple bitcoinds, return RPC connections to them
+    """
+    if extra_args is None: extra_args = [ None for i in range(num_nodes) ]
+    return [ start_node(i, dir, extra_args[i], rpchost) for i in range(num_nodes) ]
 
 def debug_log(dir, n_node):
     return os.path.join(dir, "node"+str(n_node), "regtest", "debug.log")
@@ -168,9 +180,111 @@ def wait_bitcoinds():
     del bitcoind_processes[:]
 
 def connect_nodes(from_connection, node_num):
-    ip_port = "127.0.0.1:"+str(START_P2P_PORT+node_num)
+    ip_port = "127.0.0.1:"+str(p2p_port(node_num))
     from_connection.addnode(ip_port, "onetry")
 
+def find_output(node, txid, amount):
+    """
+    Return index to output of txid with value amount
+    Raises exception if there is none.
+    """
+    txdata = node.getrawtransaction(txid, 1)
+    for i in range(len(txdata["vout"])):
+        if txdata["vout"][i]["value"] == amount:
+            return i
+    raise RuntimeError("find_output txid %s : %s not found"%(txid,str(amount)))
+
+def gather_inputs(from_node, amount_needed):
+    """
+    Return a random set of unspent txouts that are enough to pay amount_needed
+    """
+    utxo = from_node.listunspent(1)
+    random.shuffle(utxo)
+    inputs = []
+    total_in = Decimal("0.00000000")
+    while total_in < amount_needed and len(utxo) > 0:
+        t = utxo.pop()
+        total_in += t["amount"]
+        inputs.append({ "txid" : t["txid"], "vout" : t["vout"], "address" : t["address"] } )
+    if total_in < amount_needed:
+        raise RuntimeError("Insufficient funds: need %d, have %d"%(amount+fee*2, total_in))
+    return (total_in, inputs)
+
+def make_change(from_node, amount_in, amount_out, fee):
+    """
+    Create change output(s), return them
+    """
+    outputs = {}
+    amount = amount_out+fee
+    change = amount_in - amount
+    if change > amount*2:
+        # Create an extra change output to break up big inputs
+        outputs[from_node.getnewaddress()] = float(change/2)
+        change = change/2
+    if change > 0:
+        outputs[from_node.getnewaddress()] = float(change)
+    return outputs
+
+def send_zeropri_transaction(from_node, to_node, amount, fee):
+    """
+    Create&broadcast a zero-priority transaction.
+    Returns (txid, hex-encoded-txdata)
+    Ensures transaction is zero-priority by first creating a send-to-self,
+    then using it's output
+    """
+
+    # Create a send-to-self with confirmed inputs:
+    self_address = from_node.getnewaddress()
+    (total_in, inputs) = gather_inputs(from_node, amount+fee*2)
+    outputs = make_change(from_node, total_in, amount+fee, fee)
+    outputs[self_address] = float(amount+fee)
+
+    self_rawtx = from_node.createrawtransaction(inputs, outputs)
+    self_signresult = from_node.signrawtransaction(self_rawtx)
+    self_txid = from_node.sendrawtransaction(self_signresult["hex"], True)
+
+    vout = find_output(from_node, self_txid, amount+fee)
+    # Now immediately spend the output to create a 1-input, 1-output
+    # zero-priority transaction:
+    inputs = [ { "txid" : self_txid, "vout" : vout } ]
+    outputs = { to_node.getnewaddress() : float(amount) }
+
+    rawtx = from_node.createrawtransaction(inputs, outputs)
+    signresult = from_node.signrawtransaction(rawtx)
+    txid = from_node.sendrawtransaction(signresult["hex"], True)
+
+    return (txid, signresult["hex"])
+
+def random_zeropri_transaction(nodes, amount, min_fee, fee_increment, fee_variants):
+    """
+    Create a random zero-priority transaction.
+    Returns (txid, hex-encoded-transaction-data, fee)
+    """
+    from_node = random.choice(nodes)
+    to_node = random.choice(nodes)
+    fee = min_fee + fee_increment*random.randint(0,fee_variants)
+    (txid, txhex) = send_zeropri_transaction(from_node, to_node, amount, fee)
+    return (txid, txhex, fee)
+
+def random_transaction(nodes, amount, min_fee, fee_increment, fee_variants):
+    """
+    Create a random transaction.
+    Returns (txid, hex-encoded-transaction-data, fee)
+    """
+    from_node = random.choice(nodes)
+    to_node = random.choice(nodes)
+    fee = min_fee + fee_increment*random.randint(0,fee_variants)
+
+    (total_in, inputs) = gather_inputs(from_node, amount+fee)
+    outputs = make_change(from_node, total_in, amount, fee)
+    outputs[to_node.getnewaddress()] = float(amount)
+
+    rawtx = from_node.createrawtransaction(inputs, outputs)
+    signresult = from_node.signrawtransaction(rawtx)
+    txid = from_node.sendrawtransaction(signresult["hex"], True)
+
+    return (txid, signresult["hex"], fee)
+
 def assert_equal(thing1, thing2):
     if thing1 != thing2:
         raise AssertionError("%s != %s"%(str(thing1),str(thing2)))
diff --git a/src/core.cpp b/src/core.cpp
index aadcb44b98..6039986e6c 100644
--- a/src/core.cpp
+++ b/src/core.cpp
@@ -72,6 +72,25 @@ void CTxOut::print() const
     LogPrintf("%s\n", ToString());
 }
 
+CFeeRate::CFeeRate(int64_t nFeePaid, size_t nSize)
+{
+    if (nSize > 0)
+        nSatoshisPerK = nFeePaid*1000/nSize;
+    else
+        nSatoshisPerK = 0;
+}
+
+int64_t CFeeRate::GetFee(size_t nSize)
+{
+    return nSatoshisPerK*nSize / 1000;
+}
+
+std::string CFeeRate::ToString() const
+{
+    std::string result = FormatMoney(nSatoshisPerK) + " BTC/kB";
+    return result;
+}
+
 uint256 CTransaction::GetHash() const
 {
     return SerializeHash(*this);
diff --git a/src/core.h b/src/core.h
index ba7f691119..0e59129349 100644
--- a/src/core.h
+++ b/src/core.h
@@ -112,6 +112,31 @@ public:
 
 
 
+/** Type-safe wrapper class to for fee rates
+ * (how much to pay based on transaction size)
+ */
+class CFeeRate
+{
+private:
+    int64_t nSatoshisPerK; // unit is satoshis-per-1,000-bytes
+public:
+    CFeeRate() : nSatoshisPerK(0) { }
+    explicit CFeeRate(int64_t _nSatoshisPerK): nSatoshisPerK(_nSatoshisPerK) { }
+    CFeeRate(int64_t nFeePaid, size_t nSize);
+    CFeeRate(const CFeeRate& other) { nSatoshisPerK = other.nSatoshisPerK; }
+
+    int64_t GetFee(size_t size); // unit returned is satoshis
+    int64_t GetFeePerK() { return GetFee(1000); } // satoshis-per-1000-bytes
+
+    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); )
+};
+
 
 /** An output of a transaction.  It contains the public key that the next input
  * must be able to sign with to claim it.
@@ -148,17 +173,18 @@ public:
 
     uint256 GetHash() const;
 
-    bool IsDust(int64_t nMinRelayTxFee) const
+    bool IsDust(CFeeRate minRelayTxFee) const
     {
-        // "Dust" is defined in terms of CTransaction::nMinRelayTxFee,
+        // "Dust" is defined in terms of CTransaction::minRelayTxFee,
         // which has units satoshis-per-kilobyte.
         // If you'd pay more than 1/3 in fees
         // to spend something, then we consider it dust.
         // A typical txout is 34 bytes big, and will
-        // need a CTxIn of at least 148 bytes to spend,
+        // need a CTxIn of at least 148 bytes to spend:
         // so dust is a txout less than 546 satoshis 
-        // with default nMinRelayTxFee.
-        return ((nValue*1000)/(3*((int)GetSerializeSize(SER_DISK,0)+148)) < nMinRelayTxFee);
+        // with default minRelayTxFee.
+        size_t nSize = GetSerializeSize(SER_DISK,0)+148u;
+        return (nValue < 3*minRelayTxFee.GetFee(nSize));
     }
 
     friend bool operator==(const CTxOut& a, const CTxOut& b)
@@ -183,8 +209,8 @@ public:
 class CTransaction
 {
 public:
-    static int64_t nMinTxFee;
-    static int64_t nMinRelayTxFee;
+    static CFeeRate minTxFee;
+    static CFeeRate minRelayTxFee;
     static const int CURRENT_VERSION=1;
     int nVersion;
     std::vector<CTxIn> vin;
diff --git a/src/init.cpp b/src/init.cpp
index d924bd293b..aca5e0c9aa 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -59,6 +59,7 @@ enum BindFlags {
     BF_REPORT_ERROR = (1U << 1)
 };
 
+static const char* FEE_ESTIMATES_FILENAME="fee_estimates.dat";
 
 //////////////////////////////////////////////////////////////////////////////
 //
@@ -121,6 +122,14 @@ void Shutdown()
 #endif
     StopNode();
     UnregisterNodeSignals(GetNodeSignals());
+
+    boost::filesystem::path est_path = GetDataDir() / FEE_ESTIMATES_FILENAME;
+    CAutoFile est_fileout = CAutoFile(fopen(est_path.string().c_str(), "wb"), SER_DISK, CLIENT_VERSION);
+    if (est_fileout)
+        mempool.WriteFeeEstimates(est_fileout);
+    else
+        LogPrintf("failed to write fee estimates");
+
     {
         LOCK(cs_main);
 #ifdef ENABLE_WALLET
@@ -281,8 +290,8 @@ std::string HelpMessage(HelpMessageMode hmm)
         strUsage += "  -limitfreerelay=<n>    " + _("Continuously rate-limit free transactions to <n>*1000 bytes per minute (default:15)") + "\n";
         strUsage += "  -maxsigcachesize=<n>   " + _("Limit size of signature cache to <n> entries (default: 50000)") + "\n";
     }
-    strUsage += "  -mintxfee=<amt>        " + _("Fees smaller than this are considered zero fee (for transaction creation) (default:") + " " + FormatMoney(CTransaction::nMinTxFee) + ")" + "\n";
-    strUsage += "  -minrelaytxfee=<amt>   " + _("Fees smaller than this are considered zero fee (for relaying) (default:") + " " + FormatMoney(CTransaction::nMinRelayTxFee) + ")" + "\n";
+    strUsage += "  -mintxfee=<amt>        " + _("Fees smaller than this are considered zero fee (for transaction creation) (default:") + " " + FormatMoney(CTransaction::minTxFee.GetFeePerK()) + ")" + "\n";
+    strUsage += "  -minrelaytxfee=<amt>   " + _("Fees smaller than this are considered zero fee (for relaying) (default:") + " " + FormatMoney(CTransaction::minRelayTxFee.GetFeePerK()) + ")" + "\n";
     strUsage += "  -printtoconsole        " + _("Send trace/debug info to console instead of debug.log file") + "\n";
     if (GetBoolArg("-help-debug", false))
     {
@@ -560,7 +569,7 @@ bool AppInit2(boost::thread_group& threadGroup)
     {
         int64_t n = 0;
         if (ParseMoney(mapArgs["-mintxfee"], n) && n > 0)
-            CTransaction::nMinTxFee = n;
+            CTransaction::minTxFee = CFeeRate(n);
         else
             return InitError(strprintf(_("Invalid amount for -mintxfee=<amount>: '%s'"), mapArgs["-mintxfee"]));
     }
@@ -568,7 +577,7 @@ bool AppInit2(boost::thread_group& threadGroup)
     {
         int64_t n = 0;
         if (ParseMoney(mapArgs["-minrelaytxfee"], n) && n > 0)
-            CTransaction::nMinRelayTxFee = n;
+            CTransaction::minRelayTxFee = CFeeRate(n);
         else
             return InitError(strprintf(_("Invalid amount for -minrelaytxfee=<amount>: '%s'"), mapArgs["-minrelaytxfee"]));
     }
@@ -576,10 +585,12 @@ bool AppInit2(boost::thread_group& threadGroup)
 #ifdef ENABLE_WALLET
     if (mapArgs.count("-paytxfee"))
     {
-        if (!ParseMoney(mapArgs["-paytxfee"], nTransactionFee))
+        int64_t nFeePerK = 0;
+        if (!ParseMoney(mapArgs["-paytxfee"], nFeePerK))
             return InitError(strprintf(_("Invalid amount for -paytxfee=<amount>: '%s'"), mapArgs["-paytxfee"]));
-        if (nTransactionFee > nHighTransactionFeeWarning)
+        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);
     }
     bSpendZeroConfChange = GetArg("-spendzeroconfchange", true);
 
@@ -931,6 +942,11 @@ bool AppInit2(boost::thread_group& threadGroup)
         return false;
     }
 
+    boost::filesystem::path est_path = GetDataDir() / FEE_ESTIMATES_FILENAME;
+    CAutoFile est_filein = CAutoFile(fopen(est_path.string().c_str(), "rb"), SER_DISK, CLIENT_VERSION);
+    if (est_filein)
+        mempool.ReadFeeEstimates(est_filein);
+
     // ********************************************************* Step 8: load wallet
 #ifdef ENABLE_WALLET
     if (fDisableWallet) {
diff --git a/src/main.cpp b/src/main.cpp
index 8e63e4213f..429473d8f8 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -50,9 +50,9 @@ bool fTxIndex = false;
 unsigned int nCoinCacheSize = 5000;
 
 /** Fees smaller than this (in satoshi) are considered zero fee (for transaction creation) */
-int64_t CTransaction::nMinTxFee = 10000;  // Override with -mintxfee
+CFeeRate CTransaction::minTxFee = CFeeRate(10000);  // Override with -mintxfee
 /** Fees smaller than this (in satoshi) are considered zero fee (for relaying and mining) */
-int64_t CTransaction::nMinRelayTxFee = 1000;
+CFeeRate CTransaction::minRelayTxFee = CFeeRate(1000);
 
 struct COrphanBlock {
     uint256 hashBlock;
@@ -543,7 +543,7 @@ bool IsStandardTx(const CTransaction& tx, string& reason)
         }
         if (whichType == TX_NULL_DATA)
             nDataOut++;
-        else if (txout.IsDust(CTransaction::nMinRelayTxFee)) {
+        else if (txout.IsDust(CTransaction::minRelayTxFee)) {
             reason = "dust";
             return false;
         }
@@ -783,10 +783,10 @@ bool CheckTransaction(const CTransaction& tx, CValidationState &state)
 
 int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree, enum GetMinFee_mode mode)
 {
-    // Base fee is either nMinTxFee or nMinRelayTxFee
-    int64_t nBaseFee = (mode == GMF_RELAY) ? tx.nMinRelayTxFee : tx.nMinTxFee;
+    // Base fee is either minTxFee or minRelayTxFee
+    CFeeRate baseFeeRate = (mode == GMF_RELAY) ? tx.minRelayTxFee : tx.minTxFee;
 
-    int64_t nMinFee = (1 + (int64_t)nBytes / 1000) * nBaseFee;
+    int64_t nMinFee = baseFeeRate.GetFee(nBytes);
 
     if (fAllowFree)
     {
@@ -800,16 +800,6 @@ int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree,
             nMinFee = 0;
     }
 
-    // This code can be removed after enough miners have upgraded to version 0.9.
-    // Until then, be safe when sending and require a fee if any output
-    // is less than CENT:
-    if (nMinFee < nBaseFee && mode == GMF_SEND)
-    {
-        BOOST_FOREACH(const CTxOut& txout, tx.vout)
-            if (txout.nValue < CENT)
-                nMinFee = nBaseFee;
-    }
-
     if (!MoneyRange(nMinFee))
         nMinFee = MAX_MONEY;
     return nMinFee;
@@ -861,6 +851,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         CCoinsView dummy;
         CCoinsViewCache view(dummy);
 
+        int64_t nValueIn = 0;
         {
         LOCK(pool.cs);
         CCoinsViewMemPool viewMemPool(*pcoinsTip, pool);
@@ -889,6 +880,8 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         // Bring the best block into scope
         view.GetBestBlock();
 
+        nValueIn = view.GetValueIn(tx);
+
         // we have all inputs cached now, so switch back to dummy, so we don't need to keep lock on mempool
         view.SetBackend(dummy);
         }
@@ -901,7 +894,6 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         // you should add code here to check that the transaction does a
         // reasonable number of ECDSA signature verifications.
 
-        int64_t nValueIn = view.GetValueIn(tx);
         int64_t nValueOut = tx.GetValueOut();
         int64_t nFees = nValueIn-nValueOut;
         double dPriority = view.GetPriority(tx, chainActive.Height());
@@ -916,10 +908,10 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
                                       hash.ToString(), nFees, txMinFee),
                              REJECT_INSUFFICIENTFEE, "insufficient fee");
 
-        // Continuously rate-limit free transactions
+        // Continuously rate-limit free (really, very-low-fee)transactions
         // This mitigates 'penny-flooding' -- sending thousands of free transactions just to
         // be annoying or make others' transactions take longer to confirm.
-        if (fLimitFree && nFees < CTransaction::nMinRelayTxFee)
+        if (fLimitFree && nFees < CTransaction::minRelayTxFee.GetFee(nSize))
         {
             static CCriticalSection csFreeLimiter;
             static double dFreeCount;
@@ -940,10 +932,10 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
             dFreeCount += nSize;
         }
 
-        if (fRejectInsaneFee && nFees > CTransaction::nMinRelayTxFee * 10000)
+        if (fRejectInsaneFee && nFees > CTransaction::minRelayTxFee.GetFee(nSize) * 10000)
             return error("AcceptToMemoryPool: : insane fees %s, %d > %d",
                          hash.ToString(),
-                         nFees, CTransaction::nMinRelayTxFee * 10000);
+                         nFees, CTransaction::minRelayTxFee.GetFee(nSize) * 10000);
 
         // Check against previous transactions
         // This is done last to help prevent CPU exhaustion denial-of-service attacks.
@@ -2027,11 +2019,7 @@ bool static ConnectTip(CValidationState &state, CBlockIndex *pindexNew) {
         return false;
     // Remove conflicting transactions from the mempool.
     list<CTransaction> txConflicted;
-    BOOST_FOREACH(const CTransaction &tx, block.vtx) {
-        list<CTransaction> unused;
-        mempool.remove(tx, unused);
-        mempool.removeConflicts(tx, txConflicted);
-    }
+    mempool.removeForBlock(block.vtx, pindexNew->nHeight, txConflicted);
     mempool.check(pcoinsTip);
     // Update chainActive & related variables.
     UpdateTip(pindexNew);
diff --git a/src/main.h b/src/main.h
index 3fccd32a29..23c8660376 100644
--- a/src/main.h
+++ b/src/main.h
@@ -292,13 +292,6 @@ unsigned int GetLegacySigOpCount(const CTransaction& tx);
 unsigned int GetP2SHSigOpCount(const CTransaction& tx, CCoinsViewCache& mapInputs);
 
 
-inline bool AllowFree(double dPriority)
-{
-    // Large (in bytes) low-priority (new, small-coin) transactions
-    // need a fee.
-    return dPriority > COIN * 144 / 250;
-}
-
 // Check whether all inputs of this transaction are valid (no double spends, scripts & sigs, amounts)
 // This does not modify the UTXO set. If pvChecks is not NULL, script checks are pushed onto it
 // instead of being performed inline.
diff --git a/src/miner.cpp b/src/miner.cpp
index 94fc8e3888..4e131c088b 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -52,25 +52,30 @@ void SHA256Transform(void* pstate, void* pinput, const void* pinit)
         ((uint32_t*)pstate)[i] = ctx.h[i];
 }
 
-// Some explaining would be appreciated
+//
+// Unconfirmed transactions in the memory pool often depend on other
+// transactions in the memory pool. When we select transactions from the
+// pool, we select by highest priority or fee rate, so we might consider
+// transactions that depend on transactions that aren't yet in the block.
+// The COrphan class keeps track of these 'temporary orphans' while
+// CreateBlock is figuring out which transactions to include.
+//
 class COrphan
 {
 public:
     const CTransaction* ptx;
     set<uint256> setDependsOn;
     double dPriority;
-    double dFeePerKb;
+    CFeeRate feeRate;
 
-    COrphan(const CTransaction* ptxIn)
+    COrphan(const CTransaction* ptxIn) : ptx(ptxIn), feeRate(0), dPriority(0)
     {
-        ptx = ptxIn;
-        dPriority = dFeePerKb = 0;
     }
 
     void print() const
     {
-        LogPrintf("COrphan(hash=%s, dPriority=%.1f, dFeePerKb=%.1f)\n",
-               ptx->GetHash().ToString(), dPriority, dFeePerKb);
+        LogPrintf("COrphan(hash=%s, dPriority=%.1f, fee=%s)\n",
+                  ptx->GetHash().ToString(), dPriority, feeRate.ToString());
         BOOST_FOREACH(uint256 hash, setDependsOn)
             LogPrintf("   setDependsOn %s\n", hash.ToString());
     }
@@ -80,8 +85,8 @@ public:
 uint64_t nLastBlockTx = 0;
 uint64_t nLastBlockSize = 0;
 
-// We want to sort transactions by priority and fee, so:
-typedef boost::tuple<double, double, const CTransaction*> TxPriority;
+// We want to sort transactions by priority and fee rate, so:
+typedef boost::tuple<double, CFeeRate, const CTransaction*> TxPriority;
 class TxPriorityCompare
 {
     bool byFee;
@@ -210,18 +215,15 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
             unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
             dPriority = tx.ComputePriority(dPriority, nTxSize);
 
-            // This is a more accurate fee-per-kilobyte than is used by the client code, because the
-            // client code rounds up the size to the nearest 1K. That's good, because it gives an
-            // incentive to create smaller transactions.
-            double dFeePerKb =  double(nTotalIn-tx.GetValueOut()) / (double(nTxSize)/1000.0);
+            CFeeRate feeRate(nTotalIn-tx.GetValueOut(), nTxSize);
 
             if (porphan)
             {
                 porphan->dPriority = dPriority;
-                porphan->dFeePerKb = dFeePerKb;
+                porphan->feeRate = feeRate;
             }
             else
-                vecPriority.push_back(TxPriority(dPriority, dFeePerKb, &mi->second.GetTx()));
+                vecPriority.push_back(TxPriority(dPriority, feeRate, &mi->second.GetTx()));
         }
 
         // Collect transactions into block
@@ -237,7 +239,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
         {
             // Take highest priority transaction off the priority queue:
             double dPriority = vecPriority.front().get<0>();
-            double dFeePerKb = vecPriority.front().get<1>();
+            CFeeRate feeRate = vecPriority.front().get<1>();
             const CTransaction& tx = *(vecPriority.front().get<2>());
 
             std::pop_heap(vecPriority.begin(), vecPriority.end(), comparer);
@@ -254,7 +256,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
                 continue;
 
             // Skip free transactions if we're past the minimum block size:
-            if (fSortedByFee && (dFeePerKb < CTransaction::nMinRelayTxFee) && (nBlockSize + nTxSize >= nBlockMinSize))
+            if (fSortedByFee && (feeRate < CTransaction::minRelayTxFee) && (nBlockSize + nTxSize >= nBlockMinSize))
                 continue;
 
             // Prioritize by fee once past the priority size or we run out of high-priority
@@ -298,8 +300,8 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
 
             if (fPrintPriority)
             {
-                LogPrintf("priority %.1f feeperkb %.1f txid %s\n",
-                       dPriority, dFeePerKb, tx.GetHash().ToString());
+                LogPrintf("priority %.1f fee %s txid %s\n",
+                          dPriority, feeRate.ToString(), tx.GetHash().ToString());
             }
 
             // Add transactions that depend on this one to the priority queue
@@ -312,7 +314,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
                         porphan->setDependsOn.erase(hash);
                         if (porphan->setDependsOn.empty())
                         {
-                            vecPriority.push_back(TxPriority(porphan->dPriority, porphan->dFeePerKb, porphan->ptx));
+                            vecPriority.push_back(TxPriority(porphan->dPriority, porphan->feeRate, porphan->ptx));
                             std::push_heap(vecPriority.begin(), vecPriority.end(), comparer);
                         }
                     }
diff --git a/src/qt/coincontroldialog.cpp b/src/qt/coincontroldialog.cpp
index dc9d2afe27..e27f1bff97 100644
--- a/src/qt/coincontroldialog.cpp
+++ b/src/qt/coincontroldialog.cpp
@@ -453,7 +453,7 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
 
             CTxOut txout(amount, (CScript)vector<unsigned char>(24, 0));
             txDummy.vout.push_back(txout);
-            if (txout.IsDust(CTransaction::nMinRelayTxFee))
+            if (txout.IsDust(CTransaction::minRelayTxFee))
                fDust = true;
         }
     }
@@ -525,7 +525,7 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
         sPriorityLabel = CoinControlDialog::getPriorityLabel(dPriority);
 
         // Fee
-        int64_t nFee = nTransactionFee * (1 + (int64_t)nBytes / 1000);
+        int64_t nFee = payTxFee.GetFee(nBytes);
 
         // Min Fee
         int64_t nMinFee = GetMinFee(txDummy, nBytes, AllowFree(dPriority), GMF_SEND);
@@ -536,26 +536,11 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
         {
             nChange = nAmount - nPayFee - nPayAmount;
 
-            // if sub-cent change is required, the fee must be raised to at least CTransaction::nMinTxFee
-            if (nPayFee < CTransaction::nMinTxFee && nChange > 0 && nChange < CENT)
-            {
-                if (nChange < CTransaction::nMinTxFee) // change < 0.0001 => simply move all change to fees
-                {
-                    nPayFee += nChange;
-                    nChange = 0;
-                }
-                else
-                {
-                    nChange = nChange + nPayFee - CTransaction::nMinTxFee;
-                    nPayFee = CTransaction::nMinTxFee;
-                }
-            }
-
             // Never create dust outputs; if we would, just add the dust to the fee.
             if (nChange > 0 && nChange < CENT)
             {
                 CTxOut txout(nChange, (CScript)vector<unsigned char>(24, 0));
-                if (txout.IsDust(CTransaction::nMinRelayTxFee))
+                if (txout.IsDust(CTransaction::minRelayTxFee))
                 {
                     nPayFee += nChange;
                     nChange = 0;
@@ -610,19 +595,19 @@ void CoinControlDialog::updateLabels(WalletModel *model, QDialog* dialog)
 
     // tool tips
     QString toolTip1 = tr("This label turns red, if the transaction size is greater than 1000 bytes.") + "<br /><br />";
-    toolTip1 += tr("This means a fee of at least %1 per kB is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::nMinTxFee)) + "<br /><br />";
+    toolTip1 += tr("This means a fee of at least %1 per kB is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::minTxFee.GetFeePerK())) + "<br /><br />";
     toolTip1 += tr("Can vary +/- 1 byte per input.");
 
     QString toolTip2 = tr("Transactions with higher priority are more likely to get included into a block.") + "<br /><br />";
     toolTip2 += tr("This label turns red, if the priority is smaller than \"medium\".") + "<br /><br />";
-    toolTip2 += tr("This means a fee of at least %1 per kB is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::nMinTxFee));
+    toolTip2 += tr("This means a fee of at least %1 per kB is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::minTxFee.GetFeePerK()));
 
     QString toolTip3 = tr("This label turns red, if any recipient receives an amount smaller than %1.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CENT)) + "<br /><br />";
-    toolTip3 += tr("This means a fee of at least %1 is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::nMinTxFee)) + "<br /><br />";
+    toolTip3 += tr("This means a fee of at least %1 is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::minTxFee.GetFeePerK())) + "<br /><br />";
     toolTip3 += tr("Amounts below 0.546 times the minimum relay fee are shown as dust.");
 
     QString toolTip4 = tr("This label turns red, if the change is smaller than %1.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CENT)) + "<br /><br />";
-    toolTip4 += tr("This means a fee of at least %1 is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::nMinTxFee));
+    toolTip4 += tr("This means a fee of at least %1 is required.").arg(BitcoinUnits::formatWithUnit(nDisplayUnit, CTransaction::minTxFee.GetFeePerK()));
 
     l5->setToolTip(toolTip1);
     l6->setToolTip(toolTip2);
diff --git a/src/qt/guiutil.cpp b/src/qt/guiutil.cpp
index 1922d228c5..4fe98251d9 100644
--- a/src/qt/guiutil.cpp
+++ b/src/qt/guiutil.cpp
@@ -210,7 +210,7 @@ bool isDust(const QString& address, qint64 amount)
     CTxDestination dest = CBitcoinAddress(address.toStdString()).Get();
     CScript script; script.SetDestination(dest);
     CTxOut txOut(amount, script);
-    return txOut.IsDust(CTransaction::nMinRelayTxFee);
+    return txOut.IsDust(CTransaction::minRelayTxFee);
 }
 
 QString HtmlEscape(const QString& str, bool fMultiLine)
diff --git a/src/qt/optionsdialog.cpp b/src/qt/optionsdialog.cpp
index 96464d2cc0..1cbf5f8810 100644
--- a/src/qt/optionsdialog.cpp
+++ b/src/qt/optionsdialog.cpp
@@ -14,7 +14,7 @@
 #include "monitoreddatamapper.h"
 #include "optionsmodel.h"
 
-#include "main.h" // for CTransaction::nMinTxFee and MAX_SCRIPTCHECK_THREADS
+#include "main.h" // for CTransaction::minTxFee and MAX_SCRIPTCHECK_THREADS
 #include "netbase.h"
 #include "txdb.h" // for -dbcache defaults
 
@@ -101,7 +101,7 @@ OptionsDialog::OptionsDialog(QWidget *parent) :
 #endif
 
     ui->unit->setModel(new BitcoinUnits(this));
-    ui->transactionFee->setSingleStep(CTransaction::nMinTxFee);
+    ui->transactionFee->setSingleStep(CTransaction::minTxFee.GetFeePerK());
 
     /* Widget-to-option mapper */
     mapper = new MonitoredDataMapper(this);
diff --git a/src/qt/optionsmodel.cpp b/src/qt/optionsmodel.cpp
index 051098315d..f3a5f37bb3 100644
--- a/src/qt/optionsmodel.cpp
+++ b/src/qt/optionsmodel.cpp
@@ -94,7 +94,7 @@ void OptionsModel::Init()
 #ifdef ENABLE_WALLET
     if (!settings.contains("nTransactionFee"))
         settings.setValue("nTransactionFee", (qint64)DEFAULT_TRANSACTION_FEE);
-    nTransactionFee = settings.value("nTransactionFee").toLongLong(); // if -paytxfee is set, this will be overridden later in init.cpp
+    payTxFee = CFeeRate(settings.value("nTransactionFee").toLongLong()); // if -paytxfee is set, this will be overridden later in init.cpp
     if (mapArgs.count("-paytxfee"))
         addOverriddenOption("-paytxfee");
 
@@ -187,15 +187,16 @@ QVariant OptionsModel::data(const QModelIndex & index, int role) const
             return settings.value("nSocksVersion", 5);
 
 #ifdef ENABLE_WALLET
-        case Fee:
-            // Attention: Init() is called before nTransactionFee is set in AppInit2()!
+        case Fee: {
+            // Attention: Init() is called before payTxFee is set in AppInit2()!
             // To ensure we can change the fee on-the-fly update our QSetting when
             // opening OptionsDialog, which queries Fee via the mapper.
-            if (nTransactionFee != settings.value("nTransactionFee").toLongLong())
-                settings.setValue("nTransactionFee", (qint64)nTransactionFee);
-            // Todo: Consider to revert back to use just nTransactionFee here, if we don't want
+            if (!(payTxFee == CFeeRate(settings.value("nTransactionFee").toLongLong(), 1000)))
+                settings.setValue("nTransactionFee", (qint64)payTxFee.GetFeePerK());
+            // Todo: Consider to revert back to use just payTxFee here, if we don't want
             // -paytxfee to update our QSettings!
             return settings.value("nTransactionFee");
+        }
         case SpendZeroConfChange:
             return settings.value("bSpendZeroConfChange");
 #endif
@@ -284,12 +285,14 @@ bool OptionsModel::setData(const QModelIndex & index, const QVariant & value, in
         }
         break;
 #ifdef ENABLE_WALLET
-        case Fee: // core option - can be changed on-the-fly
+        case Fee: { // core option - can be changed on-the-fly
             // Todo: Add is valid check  and warn via message, if not
-            nTransactionFee = value.toLongLong();
-            settings.setValue("nTransactionFee", (qint64)nTransactionFee);
+            qint64 nTransactionFee = value.toLongLong();
+            payTxFee = CFeeRate(nTransactionFee, 1000);
+            settings.setValue("nTransactionFee", nTransactionFee);
             emit transactionFeeChanged(nTransactionFee);
             break;
+        }
         case SpendZeroConfChange:
             if (settings.value("bSpendZeroConfChange") != value) {
                 settings.setValue("bSpendZeroConfChange", value);
diff --git a/src/qt/paymentserver.cpp b/src/qt/paymentserver.cpp
index 4c45585685..6165731d22 100644
--- a/src/qt/paymentserver.cpp
+++ b/src/qt/paymentserver.cpp
@@ -551,7 +551,7 @@ bool PaymentServer::processPaymentRequest(PaymentRequestPlus& request, SendCoins
 
         // Extract and check amounts
         CTxOut txOut(sendingTo.second, sendingTo.first);
-        if (txOut.IsDust(CTransaction::nMinRelayTxFee)) {
+        if (txOut.IsDust(CTransaction::minRelayTxFee)) {
             emit message(tr("Payment request error"), tr("Requested payment amount of %1 is too small (considered dust).")
                 .arg(BitcoinUnits::formatWithUnit(optionsModel->getDisplayUnit(), sendingTo.second)),
                 CClientUIInterface::MSG_ERROR);
diff --git a/src/qt/walletmodel.cpp b/src/qt/walletmodel.cpp
index 37d82ec063..87ff3db584 100644
--- a/src/qt/walletmodel.cpp
+++ b/src/qt/walletmodel.cpp
@@ -231,12 +231,6 @@ WalletModel::SendCoinsReturn WalletModel::prepareTransaction(WalletModelTransact
         return AmountExceedsBalance;
     }
 
-    if((total + nTransactionFee) > nBalance)
-    {
-        transaction.setTransactionFee(nTransactionFee);
-        return SendCoinsReturn(AmountWithFeeExceedsBalance);
-    }
-
     {
         LOCK2(cs_main, wallet->cs_wallet);
 
diff --git a/src/rpcclient.cpp b/src/rpcclient.cpp
index 4f3c39ce9b..b89a95ad11 100644
--- a/src/rpcclient.cpp
+++ b/src/rpcclient.cpp
@@ -176,6 +176,8 @@ Array RPCConvertValues(const std::string &strMethod, const std::vector<std::stri
     if (strMethod == "verifychain"            && n > 1) ConvertTo<int64_t>(params[1]);
     if (strMethod == "keypoolrefill"          && n > 0) ConvertTo<int64_t>(params[0]);
     if (strMethod == "getrawmempool"          && n > 0) ConvertTo<bool>(params[0]);
+    if (strMethod == "estimatefee"            && n > 0) ConvertTo<boost::int64_t>(params[0]);
+    if (strMethod == "estimatepriority"       && n > 0) ConvertTo<boost::int64_t>(params[0]);
 
     return params;
 }
diff --git a/src/rpcmining.cpp b/src/rpcmining.cpp
index 23876c603d..dd148c6af1 100644
--- a/src/rpcmining.cpp
+++ b/src/rpcmining.cpp
@@ -15,6 +15,7 @@
 #endif
 #include <stdint.h>
 
+#include <boost/assign/list_of.hpp>
 #include "json/json_spirit_utils.h"
 #include "json/json_spirit_value.h"
 
@@ -626,3 +627,63 @@ Value submitblock(const Array& params, bool fHelp)
 
     return Value::null;
 }
+
+Value estimatefee(const Array& params, bool fHelp)
+{
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "estimatefee nblocks\n"
+            "\nEstimates the approximate fee per kilobyte\n"
+            "needed for a transaction to get confirmed\n"
+            "within nblocks blocks.\n"
+            "\nArguments:\n"
+            "1. nblocks     (numeric)\n"
+            "\nResult:\n"
+            "n :    (numeric) estimated fee-per-kilobyte\n"
+            "\n"
+            "-1.0 is returned if not enough transactions and\n"
+            "blocks have been observed to make an estimate.\n"
+            "\nExample:\n"
+            + HelpExampleCli("estimatefee", "6")
+            );
+
+    RPCTypeCheck(params, boost::assign::list_of(int_type));
+
+    int nBlocks = params[0].get_int();
+    if (nBlocks < 1)
+        nBlocks = 1;
+
+    CFeeRate feeRate = mempool.estimateFee(nBlocks);
+    if (feeRate == CFeeRate(0))
+        return -1.0;
+
+    return ValueFromAmount(feeRate.GetFeePerK());
+}
+
+Value estimatepriority(const Array& params, bool fHelp)
+{
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "estimatepriority nblocks\n"
+            "\nEstimates the approximate priority\n"
+            "a zero-fee transaction needs to get confirmed\n"
+            "within nblocks blocks.\n"
+            "\nArguments:\n"
+            "1. nblocks     (numeric)\n"
+            "\nResult:\n"
+            "n :    (numeric) estimated priority\n"
+            "\n"
+            "-1.0 is returned if not enough transactions and\n"
+            "blocks have been observed to make an estimate.\n"
+            "\nExample:\n"
+            + HelpExampleCli("estimatepriority", "6")
+            );
+
+    RPCTypeCheck(params, boost::assign::list_of(int_type));
+
+    int nBlocks = params[0].get_int();
+    if (nBlocks < 1)
+        nBlocks = 1;
+
+    return mempool.estimatePriority(nBlocks);
+}
diff --git a/src/rpcmisc.cpp b/src/rpcmisc.cpp
index 27d6d61a36..9802445fcb 100644
--- a/src/rpcmisc.cpp
+++ b/src/rpcmisc.cpp
@@ -81,9 +81,9 @@ Value getinfo(const Array& params, bool fHelp)
     }
     if (pwalletMain && pwalletMain->IsCrypted())
         obj.push_back(Pair("unlocked_until", nWalletUnlockTime));
-    obj.push_back(Pair("paytxfee",      ValueFromAmount(nTransactionFee)));
+    obj.push_back(Pair("paytxfee",      ValueFromAmount(payTxFee.GetFeePerK())));
 #endif
-    obj.push_back(Pair("relayfee",      ValueFromAmount(CTransaction::nMinRelayTxFee)));
+    obj.push_back(Pair("relayfee",      ValueFromAmount(CTransaction::minRelayTxFee.GetFeePerK())));
     obj.push_back(Pair("errors",        GetWarnings("statusbar")));
     return obj;
 }
diff --git a/src/rpcnet.cpp b/src/rpcnet.cpp
index 63eed09b64..0eca55a472 100644
--- a/src/rpcnet.cpp
+++ b/src/rpcnet.cpp
@@ -368,7 +368,7 @@ Value getnetworkinfo(const Array& params, bool fHelp)
     obj.push_back(Pair("timeoffset",    GetTimeOffset()));
     obj.push_back(Pair("connections",   (int)vNodes.size()));
     obj.push_back(Pair("proxy",         (proxy.first.IsValid() ? proxy.first.ToStringIPPort() : string())));
-    obj.push_back(Pair("relayfee",      ValueFromAmount(CTransaction::nMinRelayTxFee)));
+    obj.push_back(Pair("relayfee",      ValueFromAmount(CTransaction::minRelayTxFee.GetFeePerK())));
     Array localAddresses;
     {
         LOCK(cs_mapLocalHost);
diff --git a/src/rpcserver.cpp b/src/rpcserver.cpp
index 2534a9dcf4..72a7fe83ef 100644
--- a/src/rpcserver.cpp
+++ b/src/rpcserver.cpp
@@ -268,6 +268,8 @@ static const CRPCCommand vRPCCommands[] =
     { "createmultisig",         &createmultisig,         true,      true ,      false },
     { "validateaddress",        &validateaddress,        true,      false,      false }, /* uses wallet if enabled */
     { "verifymessage",          &verifymessage,          false,     false,      false },
+    { "estimatefee",            &estimatefee,            true,      true,       false },
+    { "estimatepriority",       &estimatepriority,       true,      true,       false },
 
 #ifdef ENABLE_WALLET
     /* Wallet */
diff --git a/src/rpcserver.h b/src/rpcserver.h
index e8cd2cd0fc..73e8b9426c 100644
--- a/src/rpcserver.h
+++ b/src/rpcserver.h
@@ -133,6 +133,8 @@ extern json_spirit::Value getmininginfo(const json_spirit::Array& params, bool f
 extern json_spirit::Value getwork(const json_spirit::Array& params, bool fHelp);
 extern json_spirit::Value getblocktemplate(const json_spirit::Array& params, bool fHelp);
 extern json_spirit::Value submitblock(const json_spirit::Array& params, bool fHelp);
+extern json_spirit::Value estimatefee(const json_spirit::Array& params, bool fHelp);
+extern json_spirit::Value estimatepriority(const json_spirit::Array& params, bool fHelp);
 
 extern json_spirit::Value getnewaddress(const json_spirit::Array& params, bool fHelp); // in rpcwallet.cpp
 extern json_spirit::Value getaccountaddress(const json_spirit::Array& params, bool fHelp);
diff --git a/src/rpcwallet.cpp b/src/rpcwallet.cpp
index e3b35dbb04..f376ab6b63 100644
--- a/src/rpcwallet.cpp
+++ b/src/rpcwallet.cpp
@@ -1883,7 +1883,7 @@ Value settxfee(const Array& params, bool fHelp)
     if (params[0].get_real() != 0.0)
         nAmount = AmountFromValue(params[0]);        // rejects 0.0 amounts
 
-    nTransactionFee = nAmount;
+    payTxFee = CFeeRate(nAmount, 1000);
     return true;
 }
 
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 64c9eac73d..4bf01d4848 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -6,6 +6,8 @@
 #include "core.h"
 #include "txmempool.h"
 
+#include <boost/circular_buffer.hpp>
+
 using namespace std;
 
 CTxMemPoolEntry::CTxMemPoolEntry()
@@ -35,12 +37,311 @@ 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
+    bool AreSane(const std::vector<CFeeRate>& vecFee)
+    {
+        BOOST_FOREACH(CFeeRate fee, vecFee)
+        {
+            if (fee < CFeeRate(0))
+                return false;
+            if (fee.GetFee(1000) > CTransaction::minRelayTxFee.GetFee(1000) * 10000)
+                return false;
+        }
+        return true;
+    }
+    bool AreSane(const std::vector<double> vecPriority)
+    {
+        BOOST_FOREACH(double priority, vecPriority)
+        {
+            if (priority < 0)
+                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) {
+        std::vector<CFeeRate> vecFee;
+        filein >> vecFee;
+        if (AreSane(vecFee))
+            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(CFeeRate feeRate, 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 > CTransaction::minRelayTxFee);
+        bool sufficientPriority = AllowFree(dPriority);
+        const char* assignedTo = "unassigned";
+        if (sufficientFee && !sufficientPriority)
+        {
+            history[nBlocksTruncated].RecordFee(feeRate);
+            assignedTo = "fee";
+        }
+        else if (sufficientPriority && !sufficientFee)
+        {
+            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)
+    {
+        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[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, dPriority, i);
+            }
+        }
+        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));
+        }
+        sortedFeeSamples.clear();
+        sortedPrioritySamples.clear();
+    }
+
+    // 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() == 0)
+            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() == 0)
+            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, sortedFeeSamples.size()-1);
+        return sortedPrioritySamples[index];
+    }
+
+    void Write(CAutoFile& fileout) const
+    {
+        fileout << nBestSeenHeight;
+        fileout << history.size();
+        BOOST_FOREACH(const CBlockAverage& entry, history)
+        {
+            entry.Write(fileout);
+        }
+    }
+
+    void Read(CAutoFile& filein)
+    {
+        filein >> nBestSeenHeight;
+        size_t numEntries;
+        filein >> numEntries;
+        history.clear();
+        for (size_t i = 0; i < numEntries; i++)
+        {
+            CBlockAverage entry;
+            entry.Read(filein);
+            history.push_back(entry);
+        }
+    }
+};
+
+
 CTxMemPool::CTxMemPool()
 {
     // 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);
+}
+
+CTxMemPool::~CTxMemPool()
+{
+    delete minerPolicyEstimator;
 }
 
 void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
@@ -128,6 +429,28 @@ 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)
+{
+    LOCK(cs);
+    std::vector<CTxMemPoolEntry> entries;
+    BOOST_FOREACH(const CTransaction& tx, vtx)
+    {
+        uint256 hash = tx.GetHash();
+        if (mapTx.count(hash))
+            entries.push_back(mapTx[hash]);
+    }
+    minerPolicyEstimator->seenBlock(entries, nBlockHeight);
+    BOOST_FOREACH(const CTransaction& tx, vtx)
+    {
+        std::list<CTransaction> dummy;
+        remove(tx, dummy, false);
+        removeConflicts(tx, conflicts);
+    }
+}
+
+
 void CTxMemPool::clear()
 {
     LOCK(cs);
@@ -195,6 +518,53 @@ bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
     return true;
 }
 
+CFeeRate CTxMemPool::estimateFee(int nBlocks) const
+{
+    LOCK(cs);
+    return minerPolicyEstimator->estimateFee(nBlocks);
+}
+double CTxMemPool::estimatePriority(int nBlocks) const
+{
+    LOCK(cs);
+    return minerPolicyEstimator->estimatePriority(nBlocks);
+}
+
+bool
+CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
+{
+    try {
+        LOCK(cs);
+        fileout << 99900; // version required to read: 0.9.99 or later
+        fileout << CLIENT_VERSION; // version that wrote the file
+        minerPolicyEstimator->Write(fileout);
+    }
+    catch (std::exception &e) {
+        LogPrintf("CTxMemPool::WriteFeeEstimates() : unable to write policy estimator data (non-fatal)");
+        return false;
+    }
+    return true;
+}
+
+bool
+CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
+{
+    try {
+        int nVersionRequired, nVersionThatWrote;
+        filein >> nVersionRequired >> nVersionThatWrote;
+        if (nVersionRequired > CLIENT_VERSION)
+            return error("CTxMemPool::ReadFeeEstimates() : up-version (%d) fee estimate file", nVersionRequired);
+
+        LOCK(cs);
+        minerPolicyEstimator->Read(filein);
+    }
+    catch (std::exception &e) {
+        LogPrintf("CTxMemPool::ReadFeeEstimates() : unable to read policy estimator data (non-fatal)");
+        return false;
+    }
+    return true;
+}
+
+
 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView &baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 
 bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) {
diff --git a/src/txmempool.h b/src/txmempool.h
index 4509e95778..b2915aa842 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -11,6 +11,13 @@
 #include "core.h"
 #include "sync.h"
 
+inline bool AllowFree(double dPriority)
+{
+    // Large (in bytes) low-priority (new, small-coin) transactions
+    // need a fee.
+    return dPriority > COIN * 144 / 250;
+}
+
 /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
 static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;
 
@@ -41,6 +48,8 @@ public:
     unsigned int GetHeight() const { return nHeight; }
 };
 
+class CMinerPolicyEstimator;
+
 /*
  * CTxMemPool stores valid-according-to-the-current-best-chain
  * transactions that may be included in the next block.
@@ -56,6 +65,7 @@ class CTxMemPool
 private:
     bool fSanityCheck; // Normally false, true if -checkmempool or -regtest
     unsigned int nTransactionsUpdated;
+    CMinerPolicyEstimator* minerPolicyEstimator;
 
 public:
     mutable CCriticalSection cs;
@@ -63,6 +73,7 @@ public:
     std::map<COutPoint, CInPoint> mapNextTx;
 
     CTxMemPool();
+    ~CTxMemPool();
 
     /*
      * If sanity-checking is turned on, check makes sure the pool is
@@ -76,6 +87,8 @@ public:
     bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry);
     void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
     void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
+    void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
+                        std::list<CTransaction>& conflicts);
     void clear();
     void queryHashes(std::vector<uint256>& vtxid);
     void pruneSpent(const uint256& hash, CCoins &coins);
@@ -95,6 +108,16 @@ public:
     }
 
     bool lookup(uint256 hash, CTransaction& result) 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
+    double estimatePriority(int nBlocks) const;
+    // Write/Read estimates to disk
+    bool WriteFeeEstimates(CAutoFile& fileout) const;
+    bool ReadFeeEstimates(CAutoFile& filein);
 };
 
 /** CCoinsView that brings transactions from a memorypool into view.
diff --git a/src/wallet.cpp b/src/wallet.cpp
index 89604f96ac..ef0b442e1a 100644
--- a/src/wallet.cpp
+++ b/src/wallet.cpp
@@ -16,7 +16,7 @@
 using namespace std;
 
 // Settings
-int64_t nTransactionFee = DEFAULT_TRANSACTION_FEE;
+CFeeRate payTxFee(DEFAULT_TRANSACTION_FEE);
 bool bSpendZeroConfChange = true;
 
 //////////////////////////////////////////////////////////////////////////////
@@ -1233,7 +1233,7 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
     {
         LOCK2(cs_main, cs_wallet);
         {
-            nFeeRet = nTransactionFee;
+            nFeeRet = payTxFee.GetFeePerK();
             while (true)
             {
                 wtxNew.vin.clear();
@@ -1246,7 +1246,7 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
                 BOOST_FOREACH (const PAIRTYPE(CScript, int64_t)& s, vecSend)
                 {
                     CTxOut txout(s.second, s.first);
-                    if (txout.IsDust(CTransaction::nMinRelayTxFee))
+                    if (txout.IsDust(CTransaction::minRelayTxFee))
                     {
                         strFailReason = _("Transaction amount too small");
                         return false;
@@ -1272,16 +1272,6 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
                 }
 
                 int64_t nChange = nValueIn - nValue - nFeeRet;
-                // The following if statement should be removed once enough miners
-                // have upgraded to the 0.9 GetMinFee() rules. Until then, this avoids
-                // creating free transactions that have change outputs less than
-                // CENT bitcoins.
-                if (nFeeRet < CTransaction::nMinTxFee && nChange > 0 && nChange < CENT)
-                {
-                    int64_t nMoveToFee = min(nChange, CTransaction::nMinTxFee - nFeeRet);
-                    nChange -= nMoveToFee;
-                    nFeeRet += nMoveToFee;
-                }
 
                 if (nChange > 0)
                 {
@@ -1317,7 +1307,7 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
 
                     // Never create dust outputs; if we would, just
                     // add the dust to the fee.
-                    if (newTxOut.IsDust(CTransaction::nMinRelayTxFee))
+                    if (newTxOut.IsDust(CTransaction::minRelayTxFee))
                     {
                         nFeeRet += nChange;
                         reservekey.ReturnKey();
@@ -1355,7 +1345,7 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64_t> >& vecSend,
                 dPriority = wtxNew.ComputePriority(dPriority, nBytes);
 
                 // Check that enough fee is included
-                int64_t nPayFee = nTransactionFee * (1 + (int64_t)nBytes / 1000);
+                int64_t nPayFee = payTxFee.GetFee(nBytes);
                 bool fAllowFree = AllowFree(dPriority);
                 int64_t nMinFee = GetMinFee(wtxNew, nBytes, fAllowFree, GMF_SEND);
                 if (nFeeRet < max(nPayFee, nMinFee))
@@ -1464,7 +1454,7 @@ string CWallet::SendMoneyToDestination(const CTxDestination& address, int64_t nV
     // Check amount
     if (nValue <= 0)
         return _("Invalid amount");
-    if (nValue + nTransactionFee > GetBalance())
+    if (nValue > GetBalance())
         return _("Insufficient funds");
 
     // Parse Bitcoin address
diff --git a/src/wallet.h b/src/wallet.h
index 8e2917188a..274c31157c 100644
--- a/src/wallet.h
+++ b/src/wallet.h
@@ -24,7 +24,7 @@
 #include <vector>
 
 // Settings
-extern int64_t nTransactionFee;
+extern CFeeRate payTxFee;
 extern bool bSpendZeroConfChange;
 
 // -paytxfee default