24 files changed, 1394 insertions, 124 deletions

diff --git a/qa/pull-tester/rpc-tests.py b/qa/pull-tester/rpc-tests.py
index 7a30db68dd..3d156a2e7b 100755
--- a/qa/pull-tester/rpc-tests.py
+++ b/qa/pull-tester/rpc-tests.py
@@ -112,6 +112,7 @@ testScriptsExt = [
     'p2p-acceptblock.py',
     'mempool_packages.py',
     'maxuploadtarget.py',
+    'replace-by-fee.py',
 ]
 
 #Enable ZMQ tests
diff --git a/qa/replace-by-fee/.gitignore b/qa/replace-by-fee/.gitignore
new file mode 100644
index 0000000000..b2c4f4657a
--- /dev/null
+++ b/qa/replace-by-fee/.gitignore
@@ -0,0 +1 @@
+python-bitcoinlib
diff --git a/qa/replace-by-fee/README.md b/qa/replace-by-fee/README.md
new file mode 100644
index 0000000000..baad86de9a
--- /dev/null
+++ b/qa/replace-by-fee/README.md
@@ -0,0 +1,13 @@
+Replace-by-fee regression tests
+===============================
+
+First get version v0.5.0 of the python-bitcoinlib library. In this directory
+run:
+
+    git clone -n https://github.com/petertodd/python-bitcoinlib
+    (cd python-bitcoinlib && git checkout 8270bfd9c6ac37907d75db3d8b9152d61c7255cd)
+
+Then run the tests themselves with a bitcoind available running in regtest
+mode:
+
+    ./rbf-tests.py
diff --git a/qa/replace-by-fee/rbf-tests.py b/qa/replace-by-fee/rbf-tests.py
new file mode 100755
index 0000000000..1ee6c83875
--- /dev/null
+++ b/qa/replace-by-fee/rbf-tests.py
@@ -0,0 +1,360 @@
+#!/usr/bin/env python3
+# Copyright (c) 2015 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#
+# Test replace-by-fee
+#
+
+import os
+import sys
+
+# Add python-bitcoinlib to module search path, prior to any system-wide
+# python-bitcoinlib.
+sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), "python-bitcoinlib"))
+
+import unittest
+
+import bitcoin
+bitcoin.SelectParams('regtest')
+
+import bitcoin.rpc
+
+from bitcoin.core import *
+from bitcoin.core.script import *
+from bitcoin.wallet import *
+
+MAX_REPLACEMENT_LIMIT = 100
+
+class Test_ReplaceByFee(unittest.TestCase):
+    proxy = None
+
+    @classmethod
+    def setUpClass(cls):
+        if cls.proxy is None:
+            cls.proxy = bitcoin.rpc.Proxy()
+
+    @classmethod
+    def mine_mempool(cls):
+        """Mine until mempool is empty"""
+        mempool_size = 1
+        while mempool_size:
+            cls.proxy.call('generate', 1)
+            new_mempool_size = len(cls.proxy.getrawmempool())
+
+            # It's possible to get stuck in a loop here if the mempool has
+            # transactions that can't be mined.
+            assert(new_mempool_size != mempool_size)
+            mempool_size = new_mempool_size
+
+    @classmethod
+    def tearDownClass(cls):
+        # Make sure mining works
+        cls.mine_mempool()
+
+    def make_txout(self, amount, confirmed=True, scriptPubKey=CScript([1])):
+        """Create a txout with a given amount and scriptPubKey
+
+        Mines coins as needed.
+
+        confirmed - txouts created will be confirmed in the blockchain;
+                    unconfirmed otherwise.
+        """
+        fee = 1*COIN
+        while self.proxy.getbalance() < amount + fee:
+            self.proxy.call('generate', 100)
+
+        addr = P2SHBitcoinAddress.from_redeemScript(CScript([]))
+        txid = self.proxy.sendtoaddress(addr, amount + fee)
+
+        tx1 = self.proxy.getrawtransaction(txid)
+
+        i = None
+        for i, txout in enumerate(tx1.vout):
+            if txout.scriptPubKey == addr.to_scriptPubKey():
+                break
+        assert i is not None
+
+        tx2 = CTransaction([CTxIn(COutPoint(txid, i), CScript([1, CScript([])]), nSequence=0)],
+                           [CTxOut(amount, scriptPubKey)])
+
+        tx2_txid = self.proxy.sendrawtransaction(tx2, True)
+
+        # If requested, ensure txouts are confirmed.
+        if confirmed:
+            self.mine_mempool()
+
+        return COutPoint(tx2_txid, 0)
+
+    def test_simple_doublespend(self):
+        """Simple doublespend"""
+        tx0_outpoint = self.make_txout(1.1*COIN)
+
+        tx1a = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                            [CTxOut(1*COIN, CScript([b'a']))])
+        tx1a_txid = self.proxy.sendrawtransaction(tx1a, True)
+
+        # Should fail because we haven't changed the fee
+        tx1b = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                            [CTxOut(1*COIN, CScript([b'b']))])
+
+        try:
+            tx1b_txid = self.proxy.sendrawtransaction(tx1b, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26) # insufficient fee
+        else:
+            self.fail()
+
+        # Extra 0.1 BTC fee
+        tx1b = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                            [CTxOut(0.9*COIN, CScript([b'b']))])
+        tx1b_txid = self.proxy.sendrawtransaction(tx1b, True)
+
+        # tx1a is in fact replaced
+        with self.assertRaises(IndexError):
+            self.proxy.getrawtransaction(tx1a_txid)
+
+        self.assertEqual(tx1b, self.proxy.getrawtransaction(tx1b_txid))
+
+    def test_doublespend_chain(self):
+        """Doublespend of a long chain"""
+
+        initial_nValue = 50*COIN
+        tx0_outpoint = self.make_txout(initial_nValue)
+
+        prevout = tx0_outpoint
+        remaining_value = initial_nValue
+        chain_txids = []
+        while remaining_value > 10*COIN:
+            remaining_value -= 1*COIN
+            tx = CTransaction([CTxIn(prevout, nSequence=0)],
+                              [CTxOut(remaining_value, CScript([1]))])
+            txid = self.proxy.sendrawtransaction(tx, True)
+            chain_txids.append(txid)
+            prevout = COutPoint(txid, 0)
+
+        # Whether the double-spend is allowed is evaluated by including all
+        # child fees - 40 BTC - so this attempt is rejected.
+        dbl_tx = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                              [CTxOut(initial_nValue - 30*COIN, CScript([1]))])
+
+        try:
+            self.proxy.sendrawtransaction(dbl_tx, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26) # insufficient fee
+        else:
+            self.fail()
+
+        # Accepted with sufficient fee
+        dbl_tx = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                              [CTxOut(1*COIN, CScript([1]))])
+        self.proxy.sendrawtransaction(dbl_tx, True)
+
+        for doublespent_txid in chain_txids:
+            with self.assertRaises(IndexError):
+                self.proxy.getrawtransaction(doublespent_txid)
+
+    def test_doublespend_tree(self):
+        """Doublespend of a big tree of transactions"""
+
+        initial_nValue = 50*COIN
+        tx0_outpoint = self.make_txout(initial_nValue)
+
+        def branch(prevout, initial_value, max_txs, *, tree_width=5, fee=0.0001*COIN, _total_txs=None):
+            if _total_txs is None:
+                _total_txs = [0]
+            if _total_txs[0] >= max_txs:
+                return
+
+            txout_value = (initial_value - fee) // tree_width
+            if txout_value < fee:
+                return
+
+            vout = [CTxOut(txout_value, CScript([i+1]))
+                    for i in range(tree_width)]
+            tx = CTransaction([CTxIn(prevout, nSequence=0)],
+                              vout)
+
+            self.assertTrue(len(tx.serialize()) < 100000)
+            txid = self.proxy.sendrawtransaction(tx, True)
+            yield tx
+            _total_txs[0] += 1
+
+            for i, txout in enumerate(tx.vout):
+                yield from branch(COutPoint(txid, i), txout_value,
+                                  max_txs,
+                                  tree_width=tree_width, fee=fee,
+                                  _total_txs=_total_txs)
+
+        fee = 0.0001*COIN
+        n = MAX_REPLACEMENT_LIMIT
+        tree_txs = list(branch(tx0_outpoint, initial_nValue, n, fee=fee))
+        self.assertEqual(len(tree_txs), n)
+
+        # Attempt double-spend, will fail because too little fee paid
+        dbl_tx = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                              [CTxOut(initial_nValue - fee*n, CScript([1]))])
+        try:
+            self.proxy.sendrawtransaction(dbl_tx, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26) # insufficient fee
+        else:
+            self.fail()
+
+        # 1 BTC fee is enough
+        dbl_tx = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                              [CTxOut(initial_nValue - fee*n - 1*COIN, CScript([1]))])
+        self.proxy.sendrawtransaction(dbl_tx, True)
+
+        for tx in tree_txs:
+            with self.assertRaises(IndexError):
+                self.proxy.getrawtransaction(tx.GetHash())
+
+        # Try again, but with more total transactions than the "max txs
+        # double-spent at once" anti-DoS limit.
+        for n in (MAX_REPLACEMENT_LIMIT, MAX_REPLACEMENT_LIMIT*2):
+            fee = 0.0001*COIN
+            tx0_outpoint = self.make_txout(initial_nValue)
+            tree_txs = list(branch(tx0_outpoint, initial_nValue, n, fee=fee))
+            self.assertEqual(len(tree_txs), n)
+
+            dbl_tx = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                                  [CTxOut(initial_nValue - fee*n, CScript([1]))])
+            try:
+                self.proxy.sendrawtransaction(dbl_tx, True)
+            except bitcoin.rpc.JSONRPCException as exp:
+                self.assertEqual(exp.error['code'], -26)
+            else:
+                self.fail()
+
+            for tx in tree_txs:
+                self.proxy.getrawtransaction(tx.GetHash())
+
+    def test_replacement_feeperkb(self):
+        """Replacement requires fee-per-KB to be higher"""
+        tx0_outpoint = self.make_txout(1.1*COIN)
+
+        tx1a = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                            [CTxOut(1*COIN, CScript([b'a']))])
+        tx1a_txid = self.proxy.sendrawtransaction(tx1a, True)
+
+        # Higher fee, but the fee per KB is much lower, so the replacement is
+        # rejected.
+        tx1b = CTransaction([CTxIn(tx0_outpoint, nSequence=0)],
+                            [CTxOut(0.001*COIN,
+                                    CScript([b'a'*999000]))])
+
+        try:
+            tx1b_txid = self.proxy.sendrawtransaction(tx1b, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26) # insufficient fee
+        else:
+            self.fail()
+
+    def test_spends_of_conflicting_outputs(self):
+        """Replacements that spend conflicting tx outputs are rejected"""
+        utxo1 = self.make_txout(1.2*COIN)
+        utxo2 = self.make_txout(3.0*COIN)
+
+        tx1a = CTransaction([CTxIn(utxo1, nSequence=0)],
+                            [CTxOut(1.1*COIN, CScript([b'a']))])
+        tx1a_txid = self.proxy.sendrawtransaction(tx1a, True)
+
+        # Direct spend an output of the transaction we're replacing.
+        tx2 = CTransaction([CTxIn(utxo1, nSequence=0), CTxIn(utxo2, nSequence=0),
+                            CTxIn(COutPoint(tx1a_txid, 0), nSequence=0)],
+                           tx1a.vout)
+
+        try:
+            tx2_txid = self.proxy.sendrawtransaction(tx2, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26)
+        else:
+            self.fail()
+
+        # Spend tx1a's output to test the indirect case.
+        tx1b = CTransaction([CTxIn(COutPoint(tx1a_txid, 0), nSequence=0)],
+                            [CTxOut(1.0*COIN, CScript([b'a']))])
+        tx1b_txid = self.proxy.sendrawtransaction(tx1b, True)
+
+        tx2 = CTransaction([CTxIn(utxo1, nSequence=0), CTxIn(utxo2, nSequence=0),
+                            CTxIn(COutPoint(tx1b_txid, 0))],
+                           tx1a.vout)
+
+        try:
+            tx2_txid = self.proxy.sendrawtransaction(tx2, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26)
+        else:
+            self.fail()
+
+    def test_new_unconfirmed_inputs(self):
+        """Replacements that add new unconfirmed inputs are rejected"""
+        confirmed_utxo = self.make_txout(1.1*COIN)
+        unconfirmed_utxo = self.make_txout(0.1*COIN, False)
+
+        tx1 = CTransaction([CTxIn(confirmed_utxo)],
+                           [CTxOut(1.0*COIN, CScript([b'a']))])
+        tx1_txid = self.proxy.sendrawtransaction(tx1, True)
+
+        tx2 = CTransaction([CTxIn(confirmed_utxo), CTxIn(unconfirmed_utxo)],
+                           tx1.vout)
+
+        try:
+            tx2_txid = self.proxy.sendrawtransaction(tx2, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26)
+        else:
+            self.fail()
+
+    def test_too_many_replacements(self):
+        """Replacements that evict too many transactions are rejected"""
+        # Try directly replacing more than MAX_REPLACEMENT_LIMIT
+        # transactions
+
+        # Start by creating a single transaction with many outputs
+        initial_nValue = 10*COIN
+        utxo = self.make_txout(initial_nValue)
+        fee = 0.0001*COIN
+        split_value = int((initial_nValue-fee)/(MAX_REPLACEMENT_LIMIT+1))
+        actual_fee = initial_nValue - split_value*(MAX_REPLACEMENT_LIMIT+1)
+
+        outputs = []
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            outputs.append(CTxOut(split_value, CScript([1])))
+
+        splitting_tx = CTransaction([CTxIn(utxo, nSequence=0)], outputs)
+        txid = self.proxy.sendrawtransaction(splitting_tx, True)
+
+        # Now spend each of those outputs individually
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            tx_i = CTransaction([CTxIn(COutPoint(txid, i), nSequence=0)],
+                                [CTxOut(split_value-fee, CScript([b'a']))])
+            self.proxy.sendrawtransaction(tx_i, True)
+
+        # Now create doublespend of the whole lot, should fail
+        # Need a big enough fee to cover all spending transactions and have
+        # a higher fee rate
+        double_spend_value = (split_value-100*fee)*(MAX_REPLACEMENT_LIMIT+1)
+        inputs = []
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            inputs.append(CTxIn(COutPoint(txid, i), nSequence=0))
+        double_tx = CTransaction(inputs, [CTxOut(double_spend_value, CScript([b'a']))])
+
+        try:
+            self.proxy.sendrawtransaction(double_tx, True)
+        except bitcoin.rpc.JSONRPCException as exp:
+            self.assertEqual(exp.error['code'], -26)
+            self.assertEqual("too many potential replacements" in exp.error['message'], True)
+        else:
+            self.fail()
+
+        # If we remove an input, it should pass
+        double_tx = CTransaction(inputs[0:-1],
+                                 [CTxOut(double_spend_value, CScript([b'a']))])
+
+        self.proxy.sendrawtransaction(double_tx, True)
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/qa/rpc-tests/replace-by-fee.py b/qa/rpc-tests/replace-by-fee.py
new file mode 100755
index 0000000000..537a1ed8d9
--- /dev/null
+++ b/qa/rpc-tests/replace-by-fee.py
@@ -0,0 +1,512 @@
+#!/usr/bin/env python2
+# Copyright (c) 2014-2015 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#
+# Test replace by fee code
+#
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+from test_framework.script import *
+from test_framework.mininode import *
+import binascii
+
+COIN = 100000000
+MAX_REPLACEMENT_LIMIT = 100
+
+def satoshi_round(amount):
+    return Decimal(amount).quantize(Decimal('0.00000001'), rounding=ROUND_DOWN)
+
+def txToHex(tx):
+    return binascii.hexlify(tx.serialize()).decode('utf-8')
+
+def make_utxo(node, amount, confirmed=True, scriptPubKey=CScript([1])):
+    """Create a txout with a given amount and scriptPubKey
+
+    Mines coins as needed.
+
+    confirmed - txouts created will be confirmed in the blockchain;
+                unconfirmed otherwise.
+    """
+    fee = 1*COIN
+    while node.getbalance() < satoshi_round((amount + fee)/COIN):
+        node.generate(100)
+        #print (node.getbalance(), amount, fee)
+
+    new_addr = node.getnewaddress()
+    #print new_addr
+    txid = node.sendtoaddress(new_addr, satoshi_round((amount+fee)/COIN))
+    tx1 = node.getrawtransaction(txid, 1)
+    txid = int(txid, 16)
+    i = None
+
+    for i, txout in enumerate(tx1['vout']):
+        #print i, txout['scriptPubKey']['addresses']
+        if txout['scriptPubKey']['addresses'] == [new_addr]:
+            #print i
+            break
+    assert i is not None
+
+    tx2 = CTransaction()
+    tx2.vin = [CTxIn(COutPoint(txid, i))]
+    tx2.vout = [CTxOut(amount, scriptPubKey)]
+    tx2.rehash()
+
+    tx2_hex = binascii.hexlify(tx2.serialize()).decode('utf-8')
+    #print tx2_hex
+
+    signed_tx = node.signrawtransaction(binascii.hexlify(tx2.serialize()).decode('utf-8'))
+
+    txid = node.sendrawtransaction(signed_tx['hex'], True)
+
+    # If requested, ensure txouts are confirmed.
+    if confirmed:
+        while len(node.getrawmempool()):
+            node.generate(1)
+
+    return COutPoint(int(txid, 16), 0)
+
+class ReplaceByFeeTest(BitcoinTestFramework):
+
+    def setup_network(self):
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-maxorphantx=1000",
+                                                              "-relaypriority=0", "-whitelist=127.0.0.1"]))
+        self.is_network_split = False
+
+    def run_test(self):
+        make_utxo(self.nodes[0], 1*COIN)
+
+        print "Running test simple doublespend..."
+        self.test_simple_doublespend()
+
+        print "Running test doublespend chain..."
+        self.test_doublespend_chain()
+
+        print "Running test doublespend tree..."
+        self.test_doublespend_tree()
+
+        print "Running test replacement feeperkb..."
+        self.test_replacement_feeperkb()
+
+        print "Running test spends of conflicting outputs..."
+        self.test_spends_of_conflicting_outputs()
+
+        print "Running test new unconfirmed inputs..."
+        self.test_new_unconfirmed_inputs()
+
+        print "Running test too many replacements..."
+        self.test_too_many_replacements()
+
+        print "Running test opt-in..."
+        self.test_opt_in()
+
+        print "Passed\n"
+
+    def test_simple_doublespend(self):
+        """Simple doublespend"""
+        tx0_outpoint = make_utxo(self.nodes[0], 1.1*COIN)
+
+        tx1a = CTransaction()
+        tx1a.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1a.vout = [CTxOut(1*COIN, CScript([b'a']))]
+        tx1a_hex = txToHex(tx1a)
+        tx1a_txid = self.nodes[0].sendrawtransaction(tx1a_hex, True)
+
+        # Should fail because we haven't changed the fee
+        tx1b = CTransaction()
+        tx1b.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1b.vout = [CTxOut(1*COIN, CScript([b'b']))]
+        tx1b_hex = txToHex(tx1b)
+
+        try:
+            tx1b_txid = self.nodes[0].sendrawtransaction(tx1b_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26) # insufficient fee
+        else:
+            assert(False)
+
+        # Extra 0.1 BTC fee
+        tx1b = CTransaction()
+        tx1b.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1b.vout = [CTxOut(0.9*COIN, CScript([b'b']))]
+        tx1b_hex = txToHex(tx1b)
+        tx1b_txid = self.nodes[0].sendrawtransaction(tx1b_hex, True)
+
+        mempool = self.nodes[0].getrawmempool()
+
+        assert (tx1a_txid not in mempool)
+        assert (tx1b_txid in mempool)
+
+        assert_equal(tx1b_hex, self.nodes[0].getrawtransaction(tx1b_txid))
+
+    def test_doublespend_chain(self):
+        """Doublespend of a long chain"""
+
+        initial_nValue = 50*COIN
+        tx0_outpoint = make_utxo(self.nodes[0], initial_nValue)
+
+        prevout = tx0_outpoint
+        remaining_value = initial_nValue
+        chain_txids = []
+        while remaining_value > 10*COIN:
+            remaining_value -= 1*COIN
+            tx = CTransaction()
+            tx.vin = [CTxIn(prevout, nSequence=0)]
+            tx.vout = [CTxOut(remaining_value, CScript([1]))]
+            tx_hex = txToHex(tx)
+            txid = self.nodes[0].sendrawtransaction(tx_hex, True)
+            chain_txids.append(txid)
+            prevout = COutPoint(int(txid, 16), 0)
+
+        # Whether the double-spend is allowed is evaluated by including all
+        # child fees - 40 BTC - so this attempt is rejected.
+        dbl_tx = CTransaction()
+        dbl_tx.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        dbl_tx.vout = [CTxOut(initial_nValue - 30*COIN, CScript([1]))]
+        dbl_tx_hex = txToHex(dbl_tx)
+
+        try:
+            self.nodes[0].sendrawtransaction(dbl_tx_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26) # insufficient fee
+        else:
+            assert(False) # transaction mistakenly accepted!
+
+        # Accepted with sufficient fee
+        dbl_tx = CTransaction()
+        dbl_tx.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        dbl_tx.vout = [CTxOut(1*COIN, CScript([1]))]
+        dbl_tx_hex = txToHex(dbl_tx)
+        self.nodes[0].sendrawtransaction(dbl_tx_hex, True)
+
+        mempool = self.nodes[0].getrawmempool()
+        for doublespent_txid in chain_txids:
+            assert(doublespent_txid not in mempool)
+
+    def test_doublespend_tree(self):
+        """Doublespend of a big tree of transactions"""
+
+        initial_nValue = 50*COIN
+        tx0_outpoint = make_utxo(self.nodes[0], initial_nValue)
+
+        def branch(prevout, initial_value, max_txs, tree_width=5, fee=0.0001*COIN, _total_txs=None):
+            if _total_txs is None:
+                _total_txs = [0]
+            if _total_txs[0] >= max_txs:
+                return
+
+            txout_value = (initial_value - fee) // tree_width
+            if txout_value < fee:
+                return
+
+            vout = [CTxOut(txout_value, CScript([i+1]))
+                    for i in range(tree_width)]
+            tx = CTransaction()
+            tx.vin = [CTxIn(prevout, nSequence=0)]
+            tx.vout = vout
+            tx_hex = txToHex(tx)
+
+            assert(len(tx.serialize()) < 100000)
+            txid = self.nodes[0].sendrawtransaction(tx_hex, True)
+            yield tx
+            _total_txs[0] += 1
+
+            txid = int(txid, 16)
+
+            for i, txout in enumerate(tx.vout):
+                for x in branch(COutPoint(txid, i), txout_value,
+                                  max_txs,
+                                  tree_width=tree_width, fee=fee,
+                                  _total_txs=_total_txs):
+                    yield x
+
+        fee = 0.0001*COIN
+        n = MAX_REPLACEMENT_LIMIT
+        tree_txs = list(branch(tx0_outpoint, initial_nValue, n, fee=fee))
+        assert_equal(len(tree_txs), n)
+
+        # Attempt double-spend, will fail because too little fee paid
+        dbl_tx = CTransaction()
+        dbl_tx.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        dbl_tx.vout = [CTxOut(initial_nValue - fee*n, CScript([1]))]
+        dbl_tx_hex = txToHex(dbl_tx)
+        try:
+            self.nodes[0].sendrawtransaction(dbl_tx_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26) # insufficient fee
+        else:
+            assert(False)
+
+        # 1 BTC fee is enough
+        dbl_tx = CTransaction()
+        dbl_tx.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        dbl_tx.vout = [CTxOut(initial_nValue - fee*n - 1*COIN, CScript([1]))]
+        dbl_tx_hex = txToHex(dbl_tx)
+        self.nodes[0].sendrawtransaction(dbl_tx_hex, True)
+
+        mempool = self.nodes[0].getrawmempool()
+
+        for tx in tree_txs:
+            tx.rehash()
+            assert (tx.hash not in mempool)
+
+        # Try again, but with more total transactions than the "max txs
+        # double-spent at once" anti-DoS limit.
+        for n in (MAX_REPLACEMENT_LIMIT+1, MAX_REPLACEMENT_LIMIT*2):
+            fee = 0.0001*COIN
+            tx0_outpoint = make_utxo(self.nodes[0], initial_nValue)
+            tree_txs = list(branch(tx0_outpoint, initial_nValue, n, fee=fee))
+            assert_equal(len(tree_txs), n)
+
+            dbl_tx = CTransaction()
+            dbl_tx.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+            dbl_tx.vout = [CTxOut(initial_nValue - 2*fee*n, CScript([1]))]
+            dbl_tx_hex = txToHex(dbl_tx)
+            try:
+                self.nodes[0].sendrawtransaction(dbl_tx_hex, True)
+            except JSONRPCException as exp:
+                assert_equal(exp.error['code'], -26)
+                assert_equal("too many potential replacements" in exp.error['message'], True)
+            else:
+                assert(False)
+
+            for tx in tree_txs:
+                tx.rehash()
+                self.nodes[0].getrawtransaction(tx.hash)
+
+    def test_replacement_feeperkb(self):
+        """Replacement requires fee-per-KB to be higher"""
+        tx0_outpoint = make_utxo(self.nodes[0], 1.1*COIN)
+
+        tx1a = CTransaction()
+        tx1a.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1a.vout = [CTxOut(1*COIN, CScript([b'a']))]
+        tx1a_hex = txToHex(tx1a)
+        tx1a_txid = self.nodes[0].sendrawtransaction(tx1a_hex, True)
+
+        # Higher fee, but the fee per KB is much lower, so the replacement is
+        # rejected.
+        tx1b = CTransaction()
+        tx1b.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1b.vout = [CTxOut(0.001*COIN, CScript([b'a'*999000]))]
+        tx1b_hex = txToHex(tx1b)
+
+        try:
+            tx1b_txid = self.nodes[0].sendrawtransaction(tx1b_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26) # insufficient fee
+        else:
+            assert(False)
+
+    def test_spends_of_conflicting_outputs(self):
+        """Replacements that spend conflicting tx outputs are rejected"""
+        utxo1 = make_utxo(self.nodes[0], 1.2*COIN)
+        utxo2 = make_utxo(self.nodes[0], 3.0*COIN)
+
+        tx1a = CTransaction()
+        tx1a.vin = [CTxIn(utxo1, nSequence=0)]
+        tx1a.vout = [CTxOut(1.1*COIN, CScript([b'a']))]
+        tx1a_hex = txToHex(tx1a)
+        tx1a_txid = self.nodes[0].sendrawtransaction(tx1a_hex, True)
+
+        tx1a_txid = int(tx1a_txid, 16)
+
+        # Direct spend an output of the transaction we're replacing.
+        tx2 = CTransaction()
+        tx2.vin = [CTxIn(utxo1, nSequence=0), CTxIn(utxo2, nSequence=0)]
+        tx2.vin.append(CTxIn(COutPoint(tx1a_txid, 0), nSequence=0))
+        tx2.vout = tx1a.vout
+        tx2_hex = txToHex(tx2)
+
+        try:
+            tx2_txid = self.nodes[0].sendrawtransaction(tx2_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+        else:
+            assert(False)
+
+        # Spend tx1a's output to test the indirect case.
+        tx1b = CTransaction()
+        tx1b.vin = [CTxIn(COutPoint(tx1a_txid, 0), nSequence=0)]
+        tx1b.vout = [CTxOut(1.0*COIN, CScript([b'a']))]
+        tx1b_hex = txToHex(tx1b)
+        tx1b_txid = self.nodes[0].sendrawtransaction(tx1b_hex, True)
+        tx1b_txid = int(tx1b_txid, 16)
+
+        tx2 = CTransaction()
+        tx2.vin = [CTxIn(utxo1, nSequence=0), CTxIn(utxo2, nSequence=0),
+                   CTxIn(COutPoint(tx1b_txid, 0))]
+        tx2.vout = tx1a.vout
+        tx2_hex = txToHex(tx2)
+
+        try:
+            tx2_txid = self.nodes[0].sendrawtransaction(tx2_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+        else:
+            assert(False)
+
+    def test_new_unconfirmed_inputs(self):
+        """Replacements that add new unconfirmed inputs are rejected"""
+        confirmed_utxo = make_utxo(self.nodes[0], 1.1*COIN)
+        unconfirmed_utxo = make_utxo(self.nodes[0], 0.1*COIN, False)
+
+        tx1 = CTransaction()
+        tx1.vin = [CTxIn(confirmed_utxo)]
+        tx1.vout = [CTxOut(1.0*COIN, CScript([b'a']))]
+        tx1_hex = txToHex(tx1)
+        tx1_txid = self.nodes[0].sendrawtransaction(tx1_hex, True)
+
+        tx2 = CTransaction()
+        tx2.vin = [CTxIn(confirmed_utxo), CTxIn(unconfirmed_utxo)]
+        tx2.vout = tx1.vout
+        tx2_hex = txToHex(tx2)
+
+        try:
+            tx2_txid = self.nodes[0].sendrawtransaction(tx2_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+        else:
+            assert(False)
+
+    def test_too_many_replacements(self):
+        """Replacements that evict too many transactions are rejected"""
+        # Try directly replacing more than MAX_REPLACEMENT_LIMIT
+        # transactions
+
+        # Start by creating a single transaction with many outputs
+        initial_nValue = 10*COIN
+        utxo = make_utxo(self.nodes[0], initial_nValue)
+        fee = 0.0001*COIN
+        split_value = int((initial_nValue-fee)/(MAX_REPLACEMENT_LIMIT+1))
+        actual_fee = initial_nValue - split_value*(MAX_REPLACEMENT_LIMIT+1)
+
+        outputs = []
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            outputs.append(CTxOut(split_value, CScript([1])))
+
+        splitting_tx = CTransaction()
+        splitting_tx.vin = [CTxIn(utxo, nSequence=0)]
+        splitting_tx.vout = outputs
+        splitting_tx_hex = txToHex(splitting_tx)
+
+        txid = self.nodes[0].sendrawtransaction(splitting_tx_hex, True)
+        txid = int(txid, 16)
+
+        # Now spend each of those outputs individually
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            tx_i = CTransaction()
+            tx_i.vin = [CTxIn(COutPoint(txid, i), nSequence=0)]
+            tx_i.vout = [CTxOut(split_value-fee, CScript([b'a']))]
+            tx_i_hex = txToHex(tx_i)
+            self.nodes[0].sendrawtransaction(tx_i_hex, True)
+
+        # Now create doublespend of the whole lot; should fail.
+        # Need a big enough fee to cover all spending transactions and have
+        # a higher fee rate
+        double_spend_value = (split_value-100*fee)*(MAX_REPLACEMENT_LIMIT+1)
+        inputs = []
+        for i in range(MAX_REPLACEMENT_LIMIT+1):
+            inputs.append(CTxIn(COutPoint(txid, i), nSequence=0))
+        double_tx = CTransaction()
+        double_tx.vin = inputs
+        double_tx.vout = [CTxOut(double_spend_value, CScript([b'a']))]
+        double_tx_hex = txToHex(double_tx)
+
+        try:
+            self.nodes[0].sendrawtransaction(double_tx_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+            assert_equal("too many potential replacements" in exp.error['message'], True)
+        else:
+            assert(False)
+
+        # If we remove an input, it should pass
+        double_tx = CTransaction()
+        double_tx.vin = inputs[0:-1]
+        double_tx.vout = [CTxOut(double_spend_value, CScript([b'a']))]
+        double_tx_hex = txToHex(double_tx)
+        self.nodes[0].sendrawtransaction(double_tx_hex, True)
+
+    def test_opt_in(self):
+        """ Replacing should only work if orig tx opted in """
+        tx0_outpoint = make_utxo(self.nodes[0], 1.1*COIN)
+
+        # Create a non-opting in transaction
+        tx1a = CTransaction()
+        tx1a.vin = [CTxIn(tx0_outpoint, nSequence=0xffffffff)]
+        tx1a.vout = [CTxOut(1*COIN, CScript([b'a']))]
+        tx1a_hex = txToHex(tx1a)
+        tx1a_txid = self.nodes[0].sendrawtransaction(tx1a_hex, True)
+
+        # Shouldn't be able to double-spend
+        tx1b = CTransaction()
+        tx1b.vin = [CTxIn(tx0_outpoint, nSequence=0)]
+        tx1b.vout = [CTxOut(0.9*COIN, CScript([b'b']))]
+        tx1b_hex = txToHex(tx1b)
+
+        try:
+            tx1b_txid = self.nodes[0].sendrawtransaction(tx1b_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+        else:
+            print tx1b_txid
+            assert(False)
+
+        tx1_outpoint = make_utxo(self.nodes[0], 1.1*COIN)
+
+        # Create a different non-opting in transaction
+        tx2a = CTransaction()
+        tx2a.vin = [CTxIn(tx1_outpoint, nSequence=0xfffffffe)]
+        tx2a.vout = [CTxOut(1*COIN, CScript([b'a']))]
+        tx2a_hex = txToHex(tx2a)
+        tx2a_txid = self.nodes[0].sendrawtransaction(tx2a_hex, True)
+
+        # Still shouldn't be able to double-spend
+        tx2b = CTransaction()
+        tx2b.vin = [CTxIn(tx1_outpoint, nSequence=0)]
+        tx2b.vout = [CTxOut(0.9*COIN, CScript([b'b']))]
+        tx2b_hex = txToHex(tx2b)
+
+        try:
+            tx2b_txid = self.nodes[0].sendrawtransaction(tx2b_hex, True)
+        except JSONRPCException as exp:
+            assert_equal(exp.error['code'], -26)
+        else:
+            assert(False)
+
+        # Now create a new transaction that spends from tx1a and tx2a
+        # opt-in on one of the inputs
+        # Transaction should be replaceable on either input
+
+        tx1a_txid = int(tx1a_txid, 16)
+        tx2a_txid = int(tx2a_txid, 16)
+
+        tx3a = CTransaction()
+        tx3a.vin = [CTxIn(COutPoint(tx1a_txid, 0), nSequence=0xffffffff),
+                    CTxIn(COutPoint(tx2a_txid, 0), nSequence=0xfffffffd)]
+        tx3a.vout = [CTxOut(0.9*COIN, CScript([b'c'])), CTxOut(0.9*COIN, CScript([b'd']))]
+        tx3a_hex = txToHex(tx3a)
+
+        self.nodes[0].sendrawtransaction(tx3a_hex, True)
+
+        tx3b = CTransaction()
+        tx3b.vin = [CTxIn(COutPoint(tx1a_txid, 0), nSequence=0)]
+        tx3b.vout = [CTxOut(0.5*COIN, CScript([b'e']))]
+        tx3b_hex = txToHex(tx3b)
+
+        tx3c = CTransaction()
+        tx3c.vin = [CTxIn(COutPoint(tx2a_txid, 0), nSequence=0)]
+        tx3c.vout = [CTxOut(0.5*COIN, CScript([b'f']))]
+        tx3c_hex = txToHex(tx3c)
+
+        self.nodes[0].sendrawtransaction(tx3b_hex, True)
+        # If tx3b was accepted, tx3c won't look like a replacement,
+        # but make sure it is accepted anyway
+        self.nodes[0].sendrawtransaction(tx3c_hex, True)
+
+if __name__ == '__main__':
+    ReplaceByFeeTest().main()
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/init.cpp b/src/init.cpp
index 479a3f75d1..bc6d724d71 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -592,6 +592,7 @@ void CleanupBlockRevFiles()
 
 void ThreadImport(std::vector<boost::filesystem::path> vImportFiles)
 {
+    const CChainParams& chainparams = Params();
     RenameThread("bitcoin-loadblk");
     // -reindex
     if (fReindex) {
@@ -605,14 +606,14 @@ void ThreadImport(std::vector<boost::filesystem::path> vImportFiles)
             if (!file)
                 break; // This error is logged in OpenBlockFile
             LogPrintf("Reindexing block file blk%05u.dat...\n", (unsigned int)nFile);
-            LoadExternalBlockFile(file, &pos);
+            LoadExternalBlockFile(chainparams, file, &pos);
             nFile++;
         }
         pblocktree->WriteReindexing(false);
         fReindex = false;
         LogPrintf("Reindexing finished\n");
         // To avoid ending up in a situation without genesis block, re-try initializing (no-op if reindexing worked):
-        InitBlockIndex();
+        InitBlockIndex(chainparams);
     }
 
     // hardcoded $DATADIR/bootstrap.dat
@@ -623,7 +624,7 @@ void ThreadImport(std::vector<boost::filesystem::path> vImportFiles)
             CImportingNow imp;
             boost::filesystem::path pathBootstrapOld = GetDataDir() / "bootstrap.dat.old";
             LogPrintf("Importing bootstrap.dat...\n");
-            LoadExternalBlockFile(file);
+            LoadExternalBlockFile(chainparams, file);
             RenameOver(pathBootstrap, pathBootstrapOld);
         } else {
             LogPrintf("Warning: Could not open bootstrap file %s\n", pathBootstrap.string());
@@ -636,7 +637,7 @@ void ThreadImport(std::vector<boost::filesystem::path> vImportFiles)
         if (file) {
             CImportingNow imp;
             LogPrintf("Importing blocks file %s...\n", path.string());
-            LoadExternalBlockFile(file);
+            LoadExternalBlockFile(chainparams, file);
         } else {
             LogPrintf("Warning: Could not open blocks file %s\n", path.string());
         }
@@ -1319,7 +1320,7 @@ bool AppInit2(boost::thread_group& threadGroup, CScheduler& scheduler)
                     return InitError(_("Incorrect or no genesis block found. Wrong datadir for network?"));
 
                 // Initialize the block index (no-op if non-empty database was already loaded)
-                if (!InitBlockIndex()) {
+                if (!InitBlockIndex(chainparams)) {
                     strLoadError = _("Error initializing block database");
                     break;
                 }
@@ -1354,7 +1355,7 @@ bool AppInit2(boost::thread_group& threadGroup, CScheduler& scheduler)
                     }
                 }
 
-                if (!CVerifyDB().VerifyDB(pcoinsdbview, GetArg("-checklevel", DEFAULT_CHECKLEVEL),
+                if (!CVerifyDB().VerifyDB(chainparams, pcoinsdbview, GetArg("-checklevel", DEFAULT_CHECKLEVEL),
                               GetArg("-checkblocks", DEFAULT_CHECKBLOCKS))) {
                     strLoadError = _("Corrupted block database detected");
                     break;
@@ -1578,7 +1579,7 @@ bool AppInit2(boost::thread_group& threadGroup, CScheduler& scheduler)
     uiInterface.InitMessage(_("Activating best chain..."));
     // scan for better chains in the block chain database, that are not yet connected in the active best chain
     CValidationState state;
-    if (!ActivateBestChain(state))
+    if (!ActivateBestChain(state, chainparams))
         strErrors << "Failed to connect best block";
 
     std::vector<boost::filesystem::path> vImportFiles;
diff --git a/src/main.cpp b/src/main.cpp
index b0b58141a2..ceb5cb66f3 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -832,15 +832,42 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         return state.Invalid(false, REJECT_ALREADY_KNOWN, "txn-already-in-mempool");
 
     // Check for conflicts with in-memory transactions
+    set<uint256> setConflicts;
     {
     LOCK(pool.cs); // protect pool.mapNextTx
-    for (unsigned int i = 0; i < tx.vin.size(); i++)
+    BOOST_FOREACH(const CTxIn &txin, tx.vin)
     {
-        COutPoint outpoint = tx.vin[i].prevout;
-        if (pool.mapNextTx.count(outpoint))
+        if (pool.mapNextTx.count(txin.prevout))
         {
-            // Disable replacement feature for now
-            return state.Invalid(false, REJECT_CONFLICT, "txn-mempool-conflict");
+            const CTransaction *ptxConflicting = pool.mapNextTx[txin.prevout].ptx;
+            if (!setConflicts.count(ptxConflicting->GetHash()))
+            {
+                // Allow opt-out of transaction replacement by setting
+                // nSequence >= maxint-1 on all inputs.
+                //
+                // maxint-1 is picked to still allow use of nLockTime by
+                // non-replacable transactions. All inputs rather than just one
+                // is for the sake of multi-party protocols, where we don't
+                // want a single party to be able to disable replacement.
+                //
+                // The opt-out ignores descendants as anyone relying on
+                // first-seen mempool behavior should be checking all
+                // unconfirmed ancestors anyway; doing otherwise is hopelessly
+                // insecure.
+                bool fReplacementOptOut = true;
+                BOOST_FOREACH(const CTxIn &txin, ptxConflicting->vin)
+                {
+                    if (txin.nSequence < std::numeric_limits<unsigned int>::max()-1)
+                    {
+                        fReplacementOptOut = false;
+                        break;
+                    }
+                }
+                if (fReplacementOptOut)
+                    return state.Invalid(false, REJECT_CONFLICT, "txn-mempool-conflict");
+
+                setConflicts.insert(ptxConflicting->GetHash());
+            }
         }
     }
     }
@@ -958,6 +985,160 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
             return state.DoS(0, false, REJECT_NONSTANDARD, "too-long-mempool-chain", false, errString);
         }
 
+        // A transaction that spends outputs that would be replaced by it is invalid. Now
+        // that we have the set of all ancestors we can detect this
+        // pathological case by making sure setConflicts and setAncestors don't
+        // intersect.
+        BOOST_FOREACH(CTxMemPool::txiter ancestorIt, setAncestors)
+        {
+            const uint256 &hashAncestor = ancestorIt->GetTx().GetHash();
+            if (setConflicts.count(hashAncestor))
+            {
+                return state.DoS(10, error("AcceptToMemoryPool: %s spends conflicting transaction %s",
+                                           hash.ToString(),
+                                           hashAncestor.ToString()),
+                                 REJECT_INVALID, "bad-txns-spends-conflicting-tx");
+            }
+        }
+
+        // Check if it's economically rational to mine this transaction rather
+        // than the ones it replaces.
+        CAmount nConflictingFees = 0;
+        size_t nConflictingSize = 0;
+        uint64_t nConflictingCount = 0;
+        CTxMemPool::setEntries allConflicting;
+
+        // If we don't hold the lock allConflicting might be incomplete; the
+        // subsequent RemoveStaged() and addUnchecked() calls don't guarantee
+        // mempool consistency for us.
+        LOCK(pool.cs);
+        if (setConflicts.size())
+        {
+            CFeeRate newFeeRate(nFees, nSize);
+            set<uint256> setConflictsParents;
+            const int maxDescendantsToVisit = 100;
+            CTxMemPool::setEntries setIterConflicting;
+            BOOST_FOREACH(const uint256 &hashConflicting, setConflicts)
+            {
+                CTxMemPool::txiter mi = pool.mapTx.find(hashConflicting);
+                if (mi == pool.mapTx.end())
+                    continue;
+
+                // Save these to avoid repeated lookups
+                setIterConflicting.insert(mi);
+
+                // If this entry is "dirty", then we don't have descendant
+                // state for this transaction, which means we probably have
+                // lots of in-mempool descendants.
+                // Don't allow replacements of dirty transactions, to ensure
+                // that we don't spend too much time walking descendants.
+                // This should be rare.
+                if (mi->IsDirty()) {
+                    return state.DoS(0,
+                            error("AcceptToMemoryPool: rejecting replacement %s; cannot replace tx %s with untracked descendants",
+                                hash.ToString(),
+                                mi->GetTx().GetHash().ToString()),
+                            REJECT_NONSTANDARD, "too many potential replacements");
+                }
+
+                // Don't allow the replacement to reduce the feerate of the
+                // mempool.
+                //
+                // We usually don't want to accept replacements with lower
+                // feerates than what they replaced as that would lower the
+                // feerate of the next block. Requiring that the feerate always
+                // be increased is also an easy-to-reason about way to prevent
+                // DoS attacks via replacements.
+                //
+                // The mining code doesn't (currently) take children into
+                // account (CPFP) so we only consider the feerates of
+                // transactions being directly replaced, not their indirect
+                // descendants. While that does mean high feerate children are
+                // ignored when deciding whether or not to replace, we do
+                // require the replacement to pay more overall fees too,
+                // mitigating most cases.
+                CFeeRate oldFeeRate(mi->GetFee(), mi->GetTxSize());
+                if (newFeeRate <= oldFeeRate)
+                {
+                    return state.DoS(0,
+                            error("AcceptToMemoryPool: rejecting replacement %s; new feerate %s <= old feerate %s",
+                                  hash.ToString(),
+                                  newFeeRate.ToString(),
+                                  oldFeeRate.ToString()),
+                            REJECT_INSUFFICIENTFEE, "insufficient fee");
+                }
+
+                BOOST_FOREACH(const CTxIn &txin, mi->GetTx().vin)
+                {
+                    setConflictsParents.insert(txin.prevout.hash);
+                }
+
+                nConflictingCount += mi->GetCountWithDescendants();
+            }
+            // This potentially overestimates the number of actual descendants
+            // but we just want to be conservative to avoid doing too much
+            // work.
+            if (nConflictingCount <= maxDescendantsToVisit) {
+                // If not too many to replace, then calculate the set of
+                // transactions that would have to be evicted
+                BOOST_FOREACH(CTxMemPool::txiter it, setIterConflicting) {
+                    pool.CalculateDescendants(it, allConflicting);
+                }
+                BOOST_FOREACH(CTxMemPool::txiter it, allConflicting) {
+                    nConflictingFees += it->GetFee();
+                    nConflictingSize += it->GetTxSize();
+                }
+            } else {
+                return state.DoS(0,
+                        error("AcceptToMemoryPool: rejecting replacement %s; too many potential replacements (%d > %d)\n",
+                            hash.ToString(),
+                            nConflictingCount,
+                            maxDescendantsToVisit),
+                        REJECT_NONSTANDARD, "too many potential replacements");
+            }
+
+            for (unsigned int j = 0; j < tx.vin.size(); j++)
+            {
+                // We don't want to accept replacements that require low
+                // feerate junk to be mined first. Ideally we'd keep track of
+                // the ancestor feerates and make the decision based on that,
+                // but for now requiring all new inputs to be confirmed works.
+                if (!setConflictsParents.count(tx.vin[j].prevout.hash))
+                {
+                    // Rather than check the UTXO set - potentially expensive -
+                    // it's cheaper to just check if the new input refers to a
+                    // tx that's in the mempool.
+                    if (pool.mapTx.find(tx.vin[j].prevout.hash) != pool.mapTx.end())
+                        return state.DoS(0, error("AcceptToMemoryPool: replacement %s adds unconfirmed input, idx %d",
+                                                  hash.ToString(), j),
+                                         REJECT_NONSTANDARD, "replacement-adds-unconfirmed");
+                }
+            }
+
+            // The replacement must pay greater fees than the transactions it
+            // replaces - if we did the bandwidth used by those conflicting
+            // transactions would not be paid for.
+            if (nFees < nConflictingFees)
+            {
+                return state.DoS(0, error("AcceptToMemoryPool: rejecting replacement %s, less fees than conflicting txs; %s < %s",
+                                          hash.ToString(), FormatMoney(nFees), FormatMoney(nConflictingFees)),
+                                 REJECT_INSUFFICIENTFEE, "insufficient fee");
+            }
+
+            // Finally in addition to paying more fees than the conflicts the
+            // new transaction must pay for its own bandwidth.
+            CAmount nDeltaFees = nFees - nConflictingFees;
+            if (nDeltaFees < ::minRelayTxFee.GetFee(nSize))
+            {
+                return state.DoS(0,
+                        error("AcceptToMemoryPool: rejecting replacement %s, not enough additional fees to relay; %s < %s",
+                              hash.ToString(),
+                              FormatMoney(nDeltaFees),
+                              FormatMoney(::minRelayTxFee.GetFee(nSize))),
+                        REJECT_INSUFFICIENTFEE, "insufficient fee");
+            }
+        }
+
         // Check against previous transactions
         // This is done last to help prevent CPU exhaustion denial-of-service attacks.
         if (!CheckInputs(tx, state, view, true, STANDARD_SCRIPT_VERIFY_FLAGS, true))
@@ -978,6 +1159,17 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
                 __func__, hash.ToString(), FormatStateMessage(state));
         }
 
+        // Remove conflicting transactions from the mempool
+        BOOST_FOREACH(const CTxMemPool::txiter it, allConflicting)
+        {
+            LogPrint("mempool", "replacing tx %s with %s for %s BTC additional fees, %d delta bytes\n",
+                    it->GetTx().GetHash().ToString(),
+                    hash.ToString(),
+                    FormatMoney(nFees - nConflictingFees),
+                    (int)nSize - (int)nConflictingSize);
+        }
+        pool.RemoveStaged(allConflicting);
+
         // Store transaction in memory
         pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload());
 
@@ -1947,6 +2139,7 @@ enum FlushStateMode {
  * or always and in all cases if we're in prune mode and are deleting files.
  */
 bool static FlushStateToDisk(CValidationState &state, FlushStateMode mode) {
+    const CChainParams& chainparams = Params();
     LOCK2(cs_main, cs_LastBlockFile);
     static int64_t nLastWrite = 0;
     static int64_t nLastFlush = 0;
@@ -1955,7 +2148,7 @@ bool static FlushStateToDisk(CValidationState &state, FlushStateMode mode) {
     bool fFlushForPrune = false;
     try {
     if (fPruneMode && fCheckForPruning && !fReindex) {
-        FindFilesToPrune(setFilesToPrune);
+        FindFilesToPrune(setFilesToPrune, chainparams.PruneAfterHeight());
         fCheckForPruning = false;
         if (!setFilesToPrune.empty()) {
             fFlushForPrune = true;
@@ -2155,8 +2348,8 @@ static int64_t nTimePostConnect = 0;
  * Connect a new block to chainActive. pblock is either NULL or a pointer to a CBlock
  * corresponding to pindexNew, to bypass loading it again from disk.
  */
-bool static ConnectTip(CValidationState &state, CBlockIndex *pindexNew, const CBlock *pblock) {
-    const CChainParams& chainparams = Params();
+bool static ConnectTip(CValidationState& state, const CChainParams& chainparams, CBlockIndex* pindexNew, const CBlock* pblock)
+{
     assert(pindexNew->pprev == chainActive.Tip());
     mempool.check(pcoinsTip);
     // Read block from disk.
@@ -2288,8 +2481,8 @@ static void PruneBlockIndexCandidates() {
  * Try to make some progress towards making pindexMostWork the active block.
  * pblock is either NULL or a pointer to a CBlock corresponding to pindexMostWork.
  */
-static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMostWork, const CBlock *pblock) {
-    const CChainParams& chainparams = Params();
+static bool ActivateBestChainStep(CValidationState& state, const CChainParams& chainparams, CBlockIndex* pindexMostWork, const CBlock* pblock)
+{
     AssertLockHeld(cs_main);
     bool fInvalidFound = false;
     const CBlockIndex *pindexOldTip = chainActive.Tip();
@@ -2322,7 +2515,7 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo
 
     // Connect new blocks.
     BOOST_REVERSE_FOREACH(CBlockIndex *pindexConnect, vpindexToConnect) {
-        if (!ConnectTip(state, pindexConnect, pindexConnect == pindexMostWork ? pblock : NULL)) {
+        if (!ConnectTip(state, chainparams, pindexConnect, pindexConnect == pindexMostWork ? pblock : NULL)) {
             if (state.IsInvalid()) {
                 // The block violates a consensus rule.
                 if (!state.CorruptionPossible())
@@ -2363,10 +2556,10 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo
  * or an activated best chain. pblock is either NULL or a pointer to a block
  * that is already loaded (to avoid loading it again from disk).
  */
-bool ActivateBestChain(CValidationState &state, const CBlock *pblock) {
+bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams, const CBlock* pblock)
+{
     CBlockIndex *pindexNewTip = NULL;
     CBlockIndex *pindexMostWork = NULL;
-    const CChainParams& chainparams = Params();
     do {
         boost::this_thread::interruption_point();
 
@@ -2379,7 +2572,7 @@ bool ActivateBestChain(CValidationState &state, const CBlock *pblock) {
             if (pindexMostWork == NULL || pindexMostWork == chainActive.Tip())
                 return true;
 
-            if (!ActivateBestChainStep(state, pindexMostWork, pblock && pblock->GetHash() == pindexMostWork->GetBlockHash() ? pblock : NULL))
+            if (!ActivateBestChainStep(state, chainparams, pindexMostWork, pblock && pblock->GetHash() == pindexMostWork->GetBlockHash() ? pblock : NULL))
                 return false;
 
             pindexNewTip = chainActive.Tip();
@@ -2858,9 +3051,9 @@ static bool AcceptBlockHeader(const CBlockHeader& block, CValidationState& state
     return true;
 }
 
-bool AcceptBlock(const CBlock& block, CValidationState& state, CBlockIndex** ppindex, bool fRequested, CDiskBlockPos* dbp)
+/** Store block on disk. If dbp is non-NULL, the file is known to already reside on disk */
+static bool AcceptBlock(const CBlock& block, CValidationState& state, const CChainParams& chainparams, CBlockIndex** ppindex, bool fRequested, CDiskBlockPos* dbp)
 {
-    const CChainParams& chainparams = Params();
     AssertLockHeld(cs_main);
 
     CBlockIndex *&pindex = *ppindex;
@@ -2950,7 +3143,7 @@ bool ProcessNewBlock(CValidationState& state, const CChainParams& chainparams, c
 
         // Store to disk
         CBlockIndex *pindex = NULL;
-        bool ret = AcceptBlock(*pblock, state, &pindex, fRequested, dbp);
+        bool ret = AcceptBlock(*pblock, state, chainparams, &pindex, fRequested, dbp);
         if (pindex && pfrom) {
             mapBlockSource[pindex->GetBlockHash()] = pfrom->GetId();
         }
@@ -2959,7 +3152,7 @@ bool ProcessNewBlock(CValidationState& state, const CChainParams& chainparams, c
             return error("%s: AcceptBlock FAILED", __func__);
     }
 
-    if (!ActivateBestChain(state, pblock))
+    if (!ActivateBestChain(state, chainparams, pblock))
         return error("%s: ActivateBestChain failed", __func__);
 
     return true;
@@ -3049,13 +3242,13 @@ void UnlinkPrunedFiles(std::set<int>& setFilesToPrune)
 }
 
 /* Calculate the block/rev files that should be deleted to remain under target*/
-void FindFilesToPrune(std::set<int>& setFilesToPrune)
+void FindFilesToPrune(std::set<int>& setFilesToPrune, uint64_t nPruneAfterHeight)
 {
     LOCK2(cs_main, cs_LastBlockFile);
     if (chainActive.Tip() == NULL || nPruneTarget == 0) {
         return;
     }
-    if (chainActive.Tip()->nHeight <= Params().PruneAfterHeight()) {
+    if (chainActive.Tip()->nHeight <= nPruneAfterHeight) {
         return;
     }
 
@@ -3283,9 +3476,8 @@ CVerifyDB::~CVerifyDB()
     uiInterface.ShowProgress("", 100);
 }
 
-bool CVerifyDB::VerifyDB(CCoinsView *coinsview, int nCheckLevel, int nCheckDepth)
+bool CVerifyDB::VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview, int nCheckLevel, int nCheckDepth)
 {
-    const CChainParams& chainparams = Params();
     LOCK(cs_main);
     if (chainActive.Tip() == NULL || chainActive.Tip()->pprev == NULL)
         return true;
@@ -3401,9 +3593,8 @@ bool LoadBlockIndex()
     return true;
 }
 
-
-bool InitBlockIndex() {
-    const CChainParams& chainparams = Params();
+bool InitBlockIndex(const CChainParams& chainparams) 
+{
     LOCK(cs_main);
 
     // Initialize global variables that cannot be constructed at startup.
@@ -3421,7 +3612,7 @@ bool InitBlockIndex() {
     // Only add the genesis block if not reindexing (in which case we reuse the one already on disk)
     if (!fReindex) {
         try {
-            CBlock &block = const_cast<CBlock&>(Params().GenesisBlock());
+            CBlock &block = const_cast<CBlock&>(chainparams.GenesisBlock());
             // Start new block file
             unsigned int nBlockSize = ::GetSerializeSize(block, SER_DISK, CLIENT_VERSION);
             CDiskBlockPos blockPos;
@@ -3433,7 +3624,7 @@ bool InitBlockIndex() {
             CBlockIndex *pindex = AddToBlockIndex(block);
             if (!ReceivedBlockTransactions(block, state, pindex, blockPos))
                 return error("LoadBlockIndex(): genesis block not accepted");
-            if (!ActivateBestChain(state, &block))
+            if (!ActivateBestChain(state, chainparams, &block))
                 return error("LoadBlockIndex(): genesis block cannot be activated");
             // Force a chainstate write so that when we VerifyDB in a moment, it doesn't check stale data
             return FlushStateToDisk(state, FLUSH_STATE_ALWAYS);
@@ -3445,11 +3636,8 @@ bool InitBlockIndex() {
     return true;
 }
 
-
-
-bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp)
+bool LoadExternalBlockFile(const CChainParams& chainparams, FILE* fileIn, CDiskBlockPos *dbp)
 {
-    const CChainParams& chainparams = Params();
     // Map of disk positions for blocks with unknown parent (only used for reindex)
     static std::multimap<uint256, CDiskBlockPos> mapBlocksUnknownParent;
     int64_t nStart = GetTimeMillis();
@@ -3469,10 +3657,10 @@ bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp)
             try {
                 // locate a header
                 unsigned char buf[MESSAGE_START_SIZE];
-                blkdat.FindByte(Params().MessageStart()[0]);
+                blkdat.FindByte(chainparams.MessageStart()[0]);
                 nRewind = blkdat.GetPos()+1;
                 blkdat >> FLATDATA(buf);
-                if (memcmp(buf, Params().MessageStart(), MESSAGE_START_SIZE))
+                if (memcmp(buf, chainparams.MessageStart(), MESSAGE_START_SIZE))
                     continue;
                 // read size
                 blkdat >> nSize;
@@ -3866,7 +4054,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
                         // best equivalent proof of work) than the best header chain we know about.
                         send = mi->second->IsValid(BLOCK_VALID_SCRIPTS) && (pindexBestHeader != NULL) &&
                             (pindexBestHeader->GetBlockTime() - mi->second->GetBlockTime() < nOneMonth) &&
-                            (GetBlockProofEquivalentTime(*pindexBestHeader, *mi->second, *pindexBestHeader, Params().GetConsensus()) < nOneMonth);
+                            (GetBlockProofEquivalentTime(*pindexBestHeader, *mi->second, *pindexBestHeader, consensusParams) < nOneMonth);
                         if (!send) {
                             LogPrintf("%s: ignoring request from peer=%i for old block that isn't in the main chain\n", __func__, pfrom->GetId());
                         }
@@ -4740,7 +4928,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
         uint256 alertHash = alert.GetHash();
         if (pfrom->setKnown.count(alertHash) == 0)
         {
-            if (alert.ProcessAlert(Params().AlertKey()))
+            if (alert.ProcessAlert(chainparams.AlertKey()))
             {
                 // Relay
                 pfrom->setKnown.insert(alertHash);
diff --git a/src/main.h b/src/main.h
index eb61ff9570..f738e3eb57 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) */
@@ -172,9 +170,9 @@ FILE* OpenUndoFile(const CDiskBlockPos &pos, bool fReadOnly = false);
 /** Translation to a filesystem path */
 boost::filesystem::path GetBlockPosFilename(const CDiskBlockPos &pos, const char *prefix);
 /** Import blocks from an external file */
-bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp = NULL);
+bool LoadExternalBlockFile(const CChainParams& chainparams, FILE* fileIn, CDiskBlockPos *dbp = NULL);
 /** Initialize a new block tree database + block data on disk */
-bool InitBlockIndex();
+bool InitBlockIndex(const CChainParams& chainparams);
 /** Load the block tree and coins database from disk */
 bool LoadBlockIndex();
 /** Unload database information */
@@ -199,7 +197,7 @@ std::string GetWarnings(const std::string& strFor);
 /** Retrieve a transaction (from memory pool, or from disk, if possible) */
 bool GetTransaction(const uint256 &hash, CTransaction &tx, const Consensus::Params& params, uint256 &hashBlock, bool fAllowSlow = false);
 /** Find the best known block, and make it the tip of the block chain */
-bool ActivateBestChain(CValidationState &state, const CBlock *pblock = NULL);
+bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams, const CBlock* pblock = NULL);
 CAmount GetBlockSubsidy(int nHeight, const Consensus::Params& consensusParams);
 
 /**
@@ -217,7 +215,7 @@ CAmount GetBlockSubsidy(int nHeight, const Consensus::Params& consensusParams);
  *
  * @param[out]   setFilesToPrune   The set of file indices that can be unlinked will be returned
  */
-void FindFilesToPrune(std::set<int>& setFilesToPrune);
+void FindFilesToPrune(std::set<int>& setFilesToPrune, uint64_t nPruneAfterHeight);
 
 /**
  *  Actually unlink the specified files
@@ -383,9 +381,6 @@ bool ContextualCheckBlock(const CBlock& block, CValidationState& state, CBlockIn
 /** Check a block is completely valid from start to finish (only works on top of our current best block, with cs_main held) */
 bool TestBlockValidity(CValidationState& state, const CChainParams& chainparams, const CBlock& block, CBlockIndex* pindexPrev, bool fCheckPOW = true, bool fCheckMerkleRoot = true);
 
-/** Store block on disk. If dbp is non-NULL, the file is known to already reside on disk */
-bool AcceptBlock(const CBlock& block, CValidationState& state, CBlockIndex **pindex, bool fRequested, CDiskBlockPos* dbp);
-
 
 class CBlockFileInfo
 {
@@ -446,7 +441,7 @@ class CVerifyDB {
 public:
     CVerifyDB();
     ~CVerifyDB();
-    bool VerifyDB(CCoinsView *coinsview, int nCheckLevel, int nCheckDepth);
+    bool VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview, int nCheckLevel, int nCheckDepth);
 };
 
 /** Find the last common block between the parameter chain and a locator. */
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..c872822759 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"
@@ -566,7 +567,7 @@ UniValue verifychain(const UniValue& params, bool fHelp)
     if (params.size() > 1)
         nCheckDepth = params[1].get_int();
 
-    return CVerifyDB().VerifyDB(pcoinsTip, nCheckLevel, nCheckDepth);
+    return CVerifyDB().VerifyDB(Params(), pcoinsTip, nCheckLevel, nCheckDepth);
 }
 
 /** Implementation of IsSuperMajority with better feedback */
@@ -834,7 +835,7 @@ UniValue invalidateblock(const UniValue& params, bool fHelp)
     }
 
     if (state.IsValid()) {
-        ActivateBestChain(state);
+        ActivateBestChain(state, Params());
     }
 
     if (!state.IsValid()) {
@@ -873,7 +874,7 @@ UniValue reconsiderblock(const UniValue& params, bool fHelp)
     }
 
     if (state.IsValid()) {
-        ActivateBestChain(state);
+        ActivateBestChain(state, Params());
     }
 
     if (!state.IsValid()) {
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/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp
index 9a3517a27b..2fe190f885 100644
--- a/src/test/test_bitcoin.cpp
+++ b/src/test/test_bitcoin.cpp
@@ -51,6 +51,7 @@ BasicTestingSetup::~BasicTestingSetup()
 
 TestingSetup::TestingSetup(const std::string& chainName) : BasicTestingSetup(chainName)
 {
+    const CChainParams& chainparams = Params();
 #ifdef ENABLE_WALLET
         bitdb.MakeMock();
 #endif
@@ -61,7 +62,7 @@ TestingSetup::TestingSetup(const std::string& chainName) : BasicTestingSetup(cha
         pblocktree = new CBlockTreeDB(1 << 20, true);
         pcoinsdbview = new CCoinsViewDB(1 << 23, true);
         pcoinsTip = new CCoinsViewCache(pcoinsdbview);
-        InitBlockIndex();
+        InitBlockIndex(chainparams);
 #ifdef ENABLE_WALLET
         bool fFirstRun;
         pwalletMain = new CWallet("wallet.dat");
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..7f43120f7f 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -420,6 +420,11 @@ public:
      */
     bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true);
 
+    /** Populate setDescendants with all in-mempool descendants of hash.
+     *  Assumes that setDescendants includes all in-mempool descendants of anything
+     *  already in it.  */
+    void CalculateDescendants(txiter it, setEntries &setDescendants);
+
     /** The minimum fee to get into the mempool, which may itself not be enough
       *  for larger-sized transactions.
       *  The minReasonableRelayFee constructor arg is used to bound the time it
@@ -454,9 +459,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;
     
@@ -493,10 +510,6 @@ private:
     void UpdateForRemoveFromMempool(const setEntries &entriesToRemove);
     /** Sever link between specified transaction and direct children. */
     void UpdateChildrenForRemoval(txiter entry);
-    /** Populate setDescendants with all in-mempool descendants of hash.
-     *  Assumes that setDescendants includes all in-mempool descendants of anything
-     *  already in it.  */
-    void CalculateDescendants(txiter it, setEntries &setDescendants);
 
     /** Before calling removeUnchecked for a given transaction,
      *  UpdateForRemoveFromMempool must be called on the entire (dependent) set
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);