Merge pull request #6871

63b5840 Fix usage of local python-bitcoinlib (Peter Todd)
16a2f93 Fix incorrect locking of mempool during RBF replacement (Peter Todd)
97203f5 Port test to rpc-test framework (Suhas Daftuar)
20367d8 Add test for max replacement limit (Suhas Daftuar)
73d9040 Improve RBF replacement criteria (Suhas Daftuar)
b272ecf Reject replacements that add new unconfirmed inputs (Peter Todd)
fc8c19a Prevent low feerate txs from (directly) replacing high feerate txs (Peter Todd)
0137e6f Add tests for transaction replacement (Peter Todd)
5891f87 Add opt-in full-RBF to mempool (Peter Todd)

7 files changed, 1089 insertions, 9 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/src/main.cpp b/src/main.cpp
index b0b58141a2..e48d0a6d43 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());
 
diff --git a/src/txmempool.h b/src/txmempool.h
index 5d8231fb77..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
@@ -505,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