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)

5 files changed, 887 insertions, 0 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()