Add RPC call abandontransaction

- Make wallet descendant searching more efficient
- Add new rpc call: abandontransaction

Unconfirmed transactions that are not in your mempool either due to eviction or other means may be unlikely to be mined.  abandontransaction gives the wallet a way to no longer consider as spent the coins that are inputs to such a transaction.  All dependent transactions in the wallet will also be marked as abandoned.

- Add RPC test for abandoned and conflicted transactions.
- [Wallet] Call notification signal when a transaction is abandoned

Github-Pull: #7312
Rebased-From: 9e697172542e2b01517e4025df2c23d0ed5447f4 01e06d1fa365cedb7f5d5e17e6bdf0b526e700c5 df0e2226d998483d247c0245170f6b8ff6433b1d d11fc1695c0453ef22a633e516726f82717dd1d9

7 files changed, 285 insertions, 17 deletions

diff --git a/qa/pull-tester/rpc-tests.py b/qa/pull-tester/rpc-tests.py
index 669c508ccd..e7173fda08 100755
--- a/qa/pull-tester/rpc-tests.py
+++ b/qa/pull-tester/rpc-tests.py
@@ -105,6 +105,7 @@ testScripts = [
     'prioritise_transaction.py',
     'invalidblockrequest.py',
     'invalidtxrequest.py',
+    'abandonconflict.py',
 ]
 testScriptsExt = [
     'bip65-cltv.py',
diff --git a/qa/rpc-tests/abandonconflict.py b/qa/rpc-tests/abandonconflict.py
new file mode 100755
index 0000000000..38028df079
--- /dev/null
+++ b/qa/rpc-tests/abandonconflict.py
@@ -0,0 +1,153 @@
+#!/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.
+
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+try:
+    import urllib.parse as urlparse
+except ImportError:
+    import urlparse
+
+class AbandonConflictTest(BitcoinTestFramework):
+
+    def setup_network(self):
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug","-logtimemicros","-minrelaytxfee=0.00001"]))
+        self.nodes.append(start_node(1, self.options.tmpdir, ["-debug","-logtimemicros"]))
+        connect_nodes(self.nodes[0], 1)
+
+    def run_test(self):
+        self.nodes[1].generate(100)
+        sync_blocks(self.nodes)
+        balance = self.nodes[0].getbalance()
+        txA = self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), Decimal("10"))
+        txB = self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), Decimal("10"))
+        txC = self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), Decimal("10"))
+        sync_mempools(self.nodes)
+        self.nodes[1].generate(1)
+
+        sync_blocks(self.nodes)
+        newbalance = self.nodes[0].getbalance()
+        assert(balance - newbalance < Decimal("0.001")) #no more than fees lost
+        balance = newbalance
+
+        url = urlparse.urlparse(self.nodes[1].url)
+        self.nodes[0].disconnectnode(url.hostname+":"+str(p2p_port(1)))
+
+        # Identify the 10btc outputs
+        nA = next(i for i, vout in enumerate(self.nodes[0].getrawtransaction(txA, 1)["vout"]) if vout["value"] == Decimal("10"))
+        nB = next(i for i, vout in enumerate(self.nodes[0].getrawtransaction(txB, 1)["vout"]) if vout["value"] == Decimal("10"))
+        nC = next(i for i, vout in enumerate(self.nodes[0].getrawtransaction(txC, 1)["vout"]) if vout["value"] == Decimal("10"))
+
+        inputs =[]
+        # spend 10btc outputs from txA and txB
+        inputs.append({"txid":txA, "vout":nA})
+        inputs.append({"txid":txB, "vout":nB})
+        outputs = {}
+
+        outputs[self.nodes[0].getnewaddress()] = Decimal("14.99998")
+        outputs[self.nodes[1].getnewaddress()] = Decimal("5")
+        signed = self.nodes[0].signrawtransaction(self.nodes[0].createrawtransaction(inputs, outputs))
+        txAB1 = self.nodes[0].sendrawtransaction(signed["hex"])
+
+        # Identify the 14.99998btc output
+        nAB = next(i for i, vout in enumerate(self.nodes[0].getrawtransaction(txAB1, 1)["vout"]) if vout["value"] == Decimal("14.99998"))
+
+        #Create a child tx spending AB1 and C
+        inputs = []
+        inputs.append({"txid":txAB1, "vout":nAB})
+        inputs.append({"txid":txC, "vout":nC})
+        outputs = {}
+        outputs[self.nodes[0].getnewaddress()] = Decimal("24.9996")
+        signed2 = self.nodes[0].signrawtransaction(self.nodes[0].createrawtransaction(inputs, outputs))
+        txABC2 = self.nodes[0].sendrawtransaction(signed2["hex"])
+
+        # In mempool txs from self should increase balance from change
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance - Decimal("30") + Decimal("24.9996"))
+        balance = newbalance
+
+        # Restart the node with a higher min relay fee so the parent tx is no longer in mempool
+        # TODO: redo with eviction
+        # Note had to make sure tx did not have AllowFree priority
+        stop_node(self.nodes[0],0)
+        self.nodes[0]=start_node(0, self.options.tmpdir, ["-debug","-logtimemicros","-minrelaytxfee=0.0001"])
+
+        # Verify txs no longer in mempool
+        assert(len(self.nodes[0].getrawmempool()) == 0)
+
+        # Not in mempool txs from self should only reduce balance
+        # inputs are still spent, but change not received
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance - Decimal("24.9996"))
+        balance = newbalance
+
+        # Abandon original transaction and verify inputs are available again
+        # including that the child tx was also abandoned
+        self.nodes[0].abandontransaction(txAB1)
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance + Decimal("30"))
+        balance = newbalance
+
+        # Verify that even with a low min relay fee, the tx is not reaccepted from wallet on startup once abandoned
+        stop_node(self.nodes[0],0)
+        self.nodes[0]=start_node(0, self.options.tmpdir, ["-debug","-logtimemicros","-minrelaytxfee=0.00001"])
+        assert(len(self.nodes[0].getrawmempool()) == 0)
+        assert(self.nodes[0].getbalance() == balance)
+
+        # But if its received again then it is unabandoned
+        # And since now in mempool, the change is available
+        # But its child tx remains abandoned
+        self.nodes[0].sendrawtransaction(signed["hex"])
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance - Decimal("20") + Decimal("14.99998"))
+        balance = newbalance
+
+        # Send child tx again so its unabandoned
+        self.nodes[0].sendrawtransaction(signed2["hex"])
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance - Decimal("10") - Decimal("14.99998") + Decimal("24.9996"))
+        balance = newbalance
+
+        # Remove using high relay fee again
+        stop_node(self.nodes[0],0)
+        self.nodes[0]=start_node(0, self.options.tmpdir, ["-debug","-logtimemicros","-minrelaytxfee=0.0001"])
+        assert(len(self.nodes[0].getrawmempool()) == 0)
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance - Decimal("24.9996"))
+        balance = newbalance
+
+        # Create a double spend of AB1 by spending again from only A's 10 output
+        # Mine double spend from node 1
+        inputs =[]
+        inputs.append({"txid":txA, "vout":nA})
+        outputs = {}
+        outputs[self.nodes[1].getnewaddress()] = Decimal("9.9999")
+        tx = self.nodes[0].createrawtransaction(inputs, outputs)
+        signed = self.nodes[0].signrawtransaction(tx)
+        self.nodes[1].sendrawtransaction(signed["hex"])
+        self.nodes[1].generate(1)
+
+        connect_nodes(self.nodes[0], 1)
+        sync_blocks(self.nodes)
+
+        # Verify that B and C's 10 BTC outputs are available for spending again because AB1 is now conflicted
+        newbalance = self.nodes[0].getbalance()
+        assert(newbalance == balance + Decimal("20"))
+        balance = newbalance
+
+        # There is currently a minor bug around this and so this test doesn't work.  See Issue #7315
+        # Invalidate the block with the double spend and B's 10 BTC output should no longer be available
+        # Don't think C's should either
+        self.nodes[0].invalidateblock(self.nodes[0].getbestblockhash())
+        newbalance = self.nodes[0].getbalance()
+        #assert(newbalance == balance - Decimal("10"))
+        print "If balance has not declined after invalidateblock then out of mempool wallet tx which is no longer"
+        print "conflicted has not resumed causing its inputs to be seen as spent.  See Issue #7315"
+        print balance , " -> " , newbalance , " ?"
+
+if __name__ == '__main__':
+    AbandonConflictTest().main()
diff --git a/src/rpcserver.cpp b/src/rpcserver.cpp
index de60bb6b1e..b3abeec4a3 100644
--- a/src/rpcserver.cpp
+++ b/src/rpcserver.cpp
@@ -346,6 +346,7 @@ static const CRPCCommand vRPCCommands[] =
     { "wallet",             "getreceivedbyaccount",   &getreceivedbyaccount,   false },
     { "wallet",             "getreceivedbyaddress",   &getreceivedbyaddress,   false },
     { "wallet",             "gettransaction",         &gettransaction,         false },
+    { "wallet",             "abandontransaction",     &abandontransaction,     false },
     { "wallet",             "getunconfirmedbalance",  &getunconfirmedbalance,  false },
     { "wallet",             "getwalletinfo",          &getwalletinfo,          false },
     { "wallet",             "importprivkey",          &importprivkey,          true  },
diff --git a/src/rpcserver.h b/src/rpcserver.h
index f85ab42f02..babf7c8d2e 100644
--- a/src/rpcserver.h
+++ b/src/rpcserver.h
@@ -221,6 +221,7 @@ extern UniValue listaddressgroupings(const UniValue& params, bool fHelp);
 extern UniValue listaccounts(const UniValue& params, bool fHelp);
 extern UniValue listsinceblock(const UniValue& params, bool fHelp);
 extern UniValue gettransaction(const UniValue& params, bool fHelp);
+extern UniValue abandontransaction(const UniValue& params, bool fHelp);
 extern UniValue backupwallet(const UniValue& params, bool fHelp);
 extern UniValue keypoolrefill(const UniValue& params, bool fHelp);
 extern UniValue walletpassphrase(const UniValue& params, bool fHelp);
diff --git a/src/wallet/rpcwallet.cpp b/src/wallet/rpcwallet.cpp
index 374f2fd401..9e7d9cc98a 100644
--- a/src/wallet/rpcwallet.cpp
+++ b/src/wallet/rpcwallet.cpp
@@ -1764,6 +1764,40 @@ UniValue gettransaction(const UniValue& params, bool fHelp)
     return entry;
 }
 
+UniValue abandontransaction(const UniValue& params, bool fHelp)
+{
+    if (!EnsureWalletIsAvailable(fHelp))
+        return NullUniValue;
+
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "abandontransaction \"txid\"\n"
+            "\nMark in-wallet transaction <txid> as abandoned\n"
+            "This will mark this transaction and all its in-wallet descendants as abandoned which will allow\n"
+            "for their inputs to be respent.  It can be used to replace \"stuck\" or evicted transactions.\n"
+            "It only works on transactions which are not included in a block and are not currently in the mempool.\n"
+            "It has no effect on transactions which are already conflicted or abandoned.\n"
+            "\nArguments:\n"
+            "1. \"txid\"    (string, required) The transaction id\n"
+            "\nResult:\n"
+            "\nExamples:\n"
+            + HelpExampleCli("abandontransaction", "\"1075db55d416d3ca199f55b6084e2115b9345e16c5cf302fc80e9d5fbf5d48d\"")
+            + HelpExampleRpc("abandontransaction", "\"1075db55d416d3ca199f55b6084e2115b9345e16c5cf302fc80e9d5fbf5d48d\"")
+        );
+
+    LOCK2(cs_main, pwalletMain->cs_wallet);
+
+    uint256 hash;
+    hash.SetHex(params[0].get_str());
+
+    if (!pwalletMain->mapWallet.count(hash))
+        throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Invalid or non-wallet transaction id");
+    if (!pwalletMain->AbandonTransaction(hash))
+        throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Transaction not eligible for abandonment");
+
+    return NullUniValue;
+}
+
 
 UniValue backupwallet(const UniValue& params, bool fHelp)
 {
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 610d99dc8d..2930131508 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -54,6 +54,8 @@ CFeeRate CWallet::minTxFee = CFeeRate(DEFAULT_TRANSACTION_MINFEE);
  */
 CFeeRate CWallet::fallbackFee = CFeeRate(DEFAULT_FALLBACK_FEE);
 
+const uint256 CMerkleTx::ABANDON_HASH(uint256S("0000000000000000000000000000000000000000000000000000000000000001"));
+
 /** @defgroup mapWallet
  *
  * @{
@@ -461,8 +463,11 @@ bool CWallet::IsSpent(const uint256& hash, unsigned int n) const
     {
         const uint256& wtxid = it->second;
         std::map<uint256, CWalletTx>::const_iterator mit = mapWallet.find(wtxid);
-        if (mit != mapWallet.end() && mit->second.GetDepthInMainChain() >= 0)
-            return true; // Spent
+        if (mit != mapWallet.end()) {
+            int depth = mit->second.GetDepthInMainChain();
+            if (depth > 0  || (depth == 0 && !mit->second.isAbandoned()))
+                return true; // Spent
+        }
     }
     return false;
 }
@@ -616,7 +621,7 @@ bool CWallet::AddToWallet(const CWalletTx& wtxIn, bool fFromLoadWallet, CWalletD
         BOOST_FOREACH(const CTxIn& txin, wtx.vin) {
             if (mapWallet.count(txin.prevout.hash)) {
                 CWalletTx& prevtx = mapWallet[txin.prevout.hash];
-                if (prevtx.nIndex == -1 && !prevtx.hashBlock.IsNull()) {
+                if (prevtx.nIndex == -1 && !prevtx.hashUnset()) {
                     MarkConflicted(prevtx.hashBlock, wtx.GetHash());
                 }
             }
@@ -637,7 +642,7 @@ bool CWallet::AddToWallet(const CWalletTx& wtxIn, bool fFromLoadWallet, CWalletD
             wtxOrdered.insert(make_pair(wtx.nOrderPos, TxPair(&wtx, (CAccountingEntry*)0)));
 
             wtx.nTimeSmart = wtx.nTimeReceived;
-            if (!wtxIn.hashBlock.IsNull())
+            if (!wtxIn.hashUnset())
             {
                 if (mapBlockIndex.count(wtxIn.hashBlock))
                 {
@@ -687,7 +692,13 @@ bool CWallet::AddToWallet(const CWalletTx& wtxIn, bool fFromLoadWallet, CWalletD
         if (!fInsertedNew)
         {
             // Merge
-            if (!wtxIn.hashBlock.IsNull() && wtxIn.hashBlock != wtx.hashBlock)
+            if (!wtxIn.hashUnset() && wtxIn.hashBlock != wtx.hashBlock)
+            {
+                wtx.hashBlock = wtxIn.hashBlock;
+                fUpdated = true;
+            }
+            // If no longer abandoned, update
+            if (wtxIn.hashBlock.IsNull() && wtx.isAbandoned())
             {
                 wtx.hashBlock = wtxIn.hashBlock;
                 fUpdated = true;
@@ -774,6 +785,64 @@ bool CWallet::AddToWalletIfInvolvingMe(const CTransaction& tx, const CBlock* pbl
     return false;
 }
 
+bool CWallet::AbandonTransaction(const uint256& hashTx)
+{
+    LOCK2(cs_main, cs_wallet);
+
+    // Do not flush the wallet here for performance reasons
+    CWalletDB walletdb(strWalletFile, "r+", false);
+
+    std::set<uint256> todo;
+    std::set<uint256> done;
+
+    // Can't mark abandoned if confirmed or in mempool
+    assert(mapWallet.count(hashTx));
+    CWalletTx& origtx = mapWallet[hashTx];
+    if (origtx.GetDepthInMainChain() > 0 || origtx.InMempool()) {
+        return false;
+    }
+
+    todo.insert(hashTx);
+
+    while (!todo.empty()) {
+        uint256 now = *todo.begin();
+        todo.erase(now);
+        done.insert(now);
+        assert(mapWallet.count(now));
+        CWalletTx& wtx = mapWallet[now];
+        int currentconfirm = wtx.GetDepthInMainChain();
+        // If the orig tx was not in block, none of its spends can be
+        assert(currentconfirm <= 0);
+        // if (currentconfirm < 0) {Tx and spends are already conflicted, no need to abandon}
+        if (currentconfirm == 0 && !wtx.isAbandoned()) {
+            // If the orig tx was not in block/mempool, none of its spends can be in mempool
+            assert(!wtx.InMempool());
+            wtx.nIndex = -1;
+            wtx.setAbandoned();
+            wtx.MarkDirty();
+            wtx.WriteToDisk(&walletdb);
+            NotifyTransactionChanged(this, wtx.GetHash(), CT_UPDATED);
+            // Iterate over all its outputs, and mark transactions in the wallet that spend them abandoned too
+            TxSpends::const_iterator iter = mapTxSpends.lower_bound(COutPoint(hashTx, 0));
+            while (iter != mapTxSpends.end() && iter->first.hash == now) {
+                if (!done.count(iter->second)) {
+                    todo.insert(iter->second);
+                }
+                iter++;
+            }
+            // If a transaction changes 'conflicted' state, that changes the balance
+            // available of the outputs it spends. So force those to be recomputed
+            BOOST_FOREACH(const CTxIn& txin, wtx.vin)
+            {
+                if (mapWallet.count(txin.prevout.hash))
+                    mapWallet[txin.prevout.hash].MarkDirty();
+            }
+        }
+    }
+
+    return true;
+}
+
 void CWallet::MarkConflicted(const uint256& hashBlock, const uint256& hashTx)
 {
     LOCK2(cs_main, cs_wallet);
@@ -790,14 +859,14 @@ void CWallet::MarkConflicted(const uint256& hashBlock, const uint256& hashTx)
     // Do not flush the wallet here for performance reasons
     CWalletDB walletdb(strWalletFile, "r+", false);
 
-    std::deque<uint256> todo;
+    std::set<uint256> todo;
     std::set<uint256> done;
 
-    todo.push_back(hashTx);
+    todo.insert(hashTx);
 
     while (!todo.empty()) {
-        uint256 now = todo.front();
-        todo.pop_front();
+        uint256 now = *todo.begin();
+        todo.erase(now);
         done.insert(now);
         assert(mapWallet.count(now));
         CWalletTx& wtx = mapWallet[now];
@@ -813,7 +882,7 @@ void CWallet::MarkConflicted(const uint256& hashBlock, const uint256& hashTx)
             TxSpends::const_iterator iter = mapTxSpends.lower_bound(COutPoint(now, 0));
             while (iter != mapTxSpends.end() && iter->first.hash == now) {
                  if (!done.count(iter->second)) {
-                     todo.push_back(iter->second);
+                     todo.insert(iter->second);
                  }
                  iter++;
             }
@@ -982,7 +1051,7 @@ int CWalletTx::GetRequestCount() const
         if (IsCoinBase())
         {
             // Generated block
-            if (!hashBlock.IsNull())
+            if (!hashUnset())
             {
                 map<uint256, int>::const_iterator mi = pwallet->mapRequestCount.find(hashBlock);
                 if (mi != pwallet->mapRequestCount.end())
@@ -998,7 +1067,7 @@ int CWalletTx::GetRequestCount() const
                 nRequests = (*mi).second;
 
                 // How about the block it's in?
-                if (nRequests == 0 && !hashBlock.IsNull())
+                if (nRequests == 0 && !hashUnset())
                 {
                     map<uint256, int>::const_iterator mi = pwallet->mapRequestCount.find(hashBlock);
                     if (mi != pwallet->mapRequestCount.end())
@@ -1172,7 +1241,7 @@ void CWallet::ReacceptWalletTransactions()
 
         int nDepth = wtx.GetDepthInMainChain();
 
-        if (!wtx.IsCoinBase() && nDepth == 0) {
+        if (!wtx.IsCoinBase() && (nDepth == 0 && !wtx.isAbandoned())) {
             mapSorted.insert(std::make_pair(wtx.nOrderPos, &wtx));
         }
     }
@@ -1192,7 +1261,7 @@ bool CWalletTx::RelayWalletTransaction()
     assert(pwallet->GetBroadcastTransactions());
     if (!IsCoinBase())
     {
-        if (GetDepthInMainChain() == 0) {
+        if (GetDepthInMainChain() == 0 && !isAbandoned()) {
             LogPrintf("Relaying wtx %s\n", GetHash().ToString());
             RelayTransaction((CTransaction)*this);
             return true;
@@ -2926,8 +2995,9 @@ int CMerkleTx::SetMerkleBranch(const CBlock& block)
 
 int CMerkleTx::GetDepthInMainChain(const CBlockIndex* &pindexRet) const
 {
-    if (hashBlock.IsNull())
+    if (hashUnset())
         return 0;
+
     AssertLockHeld(cs_main);
 
     // Find the block it claims to be in
@@ -2955,4 +3025,3 @@ bool CMerkleTx::AcceptToMemoryPool(bool fLimitFree, bool fRejectAbsurdFee)
     CValidationState state;
     return ::AcceptToMemoryPool(mempool, state, *this, fLimitFree, NULL, false, fRejectAbsurdFee);
 }
-
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index 89fc17bc74..df417fef42 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -157,6 +157,10 @@ struct COutputEntry
 /** A transaction with a merkle branch linking it to the block chain. */
 class CMerkleTx : public CTransaction
 {
+private:
+  /** Constant used in hashBlock to indicate tx has been abandoned */
+    static const uint256 ABANDON_HASH;
+
 public:
     uint256 hashBlock;
 
@@ -208,6 +212,9 @@ public:
     bool IsInMainChain() const { const CBlockIndex *pindexRet; return GetDepthInMainChain(pindexRet) > 0; }
     int GetBlocksToMaturity() const;
     bool AcceptToMemoryPool(bool fLimitFree=true, bool fRejectAbsurdFee=true);
+    bool hashUnset() const { return (hashBlock.IsNull() || hashBlock == ABANDON_HASH); }
+    bool isAbandoned() const { return (hashBlock == ABANDON_HASH); }
+    void setAbandoned() { hashBlock = ABANDON_HASH; }
 };
 
 /** 
@@ -487,7 +494,6 @@ private:
     /* Mark a transaction (and its in-wallet descendants) as conflicting with a particular block. */
     void MarkConflicted(const uint256& hashBlock, const uint256& hashTx);
 
-
     void SyncMetaData(std::pair<TxSpends::iterator, TxSpends::iterator>);
 
 public:
@@ -785,6 +791,9 @@ public:
     bool GetBroadcastTransactions() const { return fBroadcastTransactions; }
     /** Set whether this wallet broadcasts transactions. */
     void SetBroadcastTransactions(bool broadcast) { fBroadcastTransactions = broadcast; }
+
+    /* Mark a transaction (and it in-wallet descendants) as abandoned so its inputs may be respent. */
+    bool AbandonTransaction(const uint256& hashTx);
 };
 
 /** A key allocated from the key pool. */