Merge bitcoin/bitcoin#25768: wallet: Properly rebroadcast unconfirmed transaction chains

3405f3eed5cf841b23a569b64a376c2e5b5026cd test: Test that an unconfirmed not-in-mempool chain is rebroadcast (Andrew Chow)
10d91c5abe9ed7dcc237c9d52c588e7d26e162a4 wallet: Deduplicate Resend and ReacceptWalletTransactions (Andrew Chow)

Pull request description:

  Currently `ResendWalletTransactions` (used for normal rebroadcasts) will attempt to rebroadcast all of the transactions in the wallet in the order they are stored in `mapWallet`. This ends up being random as `mapWallet` is a `std::unordered_map`. However `ReacceptWalletTransactions` (used for adding to the mempool on loading) first sorts the txs by wallet insertion order, then submits them. The result is that `ResendWalletTranactions` will fail to rebroadcast child transactions if their txids happen to be lexicographically less than their parent's txid. This PR resolves this issue by combining `ReacceptWalletTransactions` and `ResendWalletTransactions` into a new `ResubmitWalletTransactions` so that the iteration code and basic checks are shared.

  A test has also been added that checks that such transaction chains are rebroadcast correctly.

ACKs for top commit:
  naumenkogs:
    utACK 3405f3eed5cf841b23a569b64a376c2e5b5026cd
  1440000bytes:
    reACK https://github.com/bitcoin/bitcoin/pull/25768/commits/3405f3eed5cf841b23a569b64a376c2e5b5026cd
  furszy:
    Late code review ACK 3405f3ee
  stickies-v:
    ACK 3405f3eed5cf841b23a569b64a376c2e5b5026cd

Tree-SHA512: 1240d9690ecc2ae8d476286b79e2386f537a90c41dd2b8b8a5a9c2a917aa3af85d6aee019fbbb05e772985a2b197e2788305586d9d5dac78ccba1ee5aa31d77a

4 files changed, 56 insertions, 52 deletions

diff --git a/src/wallet/rpc/backup.cpp b/src/wallet/rpc/backup.cpp
index 4c623fa1ba..35df151e84 100644
--- a/src/wallet/rpc/backup.cpp
+++ b/src/wallet/rpc/backup.cpp
@@ -295,7 +295,7 @@ RPCHelpMan importaddress()
         RescanWallet(*pwallet, reserver);
         {
             LOCK(pwallet->cs_wallet);
-            pwallet->ReacceptWalletTransactions();
+            pwallet->ResubmitWalletTransactions(/*relay=*/false, /*force=*/true);
         }
     }
 
@@ -476,7 +476,7 @@ RPCHelpMan importpubkey()
         RescanWallet(*pwallet, reserver);
         {
             LOCK(pwallet->cs_wallet);
-            pwallet->ReacceptWalletTransactions();
+            pwallet->ResubmitWalletTransactions(/*relay=*/false, /*force=*/true);
         }
     }
 
@@ -1397,7 +1397,7 @@ RPCHelpMan importmulti()
         int64_t scannedTime = pwallet->RescanFromTime(nLowestTimestamp, reserver, true /* update */);
         {
             LOCK(pwallet->cs_wallet);
-            pwallet->ReacceptWalletTransactions();
+            pwallet->ResubmitWalletTransactions(/*relay=*/false, /*force=*/true);
         }
 
         if (pwallet->IsAbortingRescan()) {
@@ -1691,7 +1691,7 @@ RPCHelpMan importdescriptors()
         int64_t scanned_time = pwallet->RescanFromTime(lowest_timestamp, reserver, true /* update */);
         {
             LOCK(pwallet->cs_wallet);
-            pwallet->ReacceptWalletTransactions();
+            pwallet->ResubmitWalletTransactions(/*relay=*/false, /*force=*/true);
         }
 
         if (pwallet->IsAbortingRescan()) {
diff --git a/src/wallet/transaction.h b/src/wallet/transaction.h
index 271d698e56..27983e356d 100644
--- a/src/wallet/transaction.h
+++ b/src/wallet/transaction.h
@@ -305,6 +305,13 @@ public:
     CWalletTx(CWalletTx const &) = delete;
     void operator=(CWalletTx const &x) = delete;
 };
+
+struct WalletTxOrderComparator {
+    bool operator()(const CWalletTx* a, const CWalletTx* b) const
+    {
+        return a->nOrderPos < b->nOrderPos;
+    }
+};
 } // namespace wallet
 
 #endif // BITCOIN_WALLET_TRANSACTION_H
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index b25488f6a1..0949045ff0 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -1857,34 +1857,6 @@ CWallet::ScanResult CWallet::ScanForWalletTransactions(const uint256& start_bloc
     return result;
 }
 
-void CWallet::ReacceptWalletTransactions()
-{
-    // If transactions aren't being broadcasted, don't let them into local mempool either
-    if (!fBroadcastTransactions)
-        return;
-    std::map<int64_t, CWalletTx*> mapSorted;
-
-    // Sort pending wallet transactions based on their initial wallet insertion order
-    for (std::pair<const uint256, CWalletTx>& item : mapWallet) {
-        const uint256& wtxid = item.first;
-        CWalletTx& wtx = item.second;
-        assert(wtx.GetHash() == wtxid);
-
-        int nDepth = GetTxDepthInMainChain(wtx);
-
-        if (!wtx.IsCoinBase() && (nDepth == 0 && !wtx.isAbandoned())) {
-            mapSorted.insert(std::make_pair(wtx.nOrderPos, &wtx));
-        }
-    }
-
-    // Try to add wallet transactions to memory pool
-    for (const std::pair<const int64_t, CWalletTx*>& item : mapSorted) {
-        CWalletTx& wtx = *(item.second);
-        std::string unused_err_string;
-        SubmitTxMemoryPoolAndRelay(wtx, unused_err_string, false);
-    }
-}
-
 bool CWallet::SubmitTxMemoryPoolAndRelay(CWalletTx& wtx, std::string& err_string, bool relay) const
 {
     AssertLockHeld(cs_wallet);
@@ -1925,43 +1897,69 @@ std::set<uint256> CWallet::GetTxConflicts(const CWalletTx& wtx) const
     return result;
 }
 
-// Rebroadcast transactions from the wallet. We do this on a random timer
-// to slightly obfuscate which transactions come from our wallet.
+// Resubmit transactions from the wallet to the mempool, optionally asking the
+// mempool to relay them. On startup, we will do this for all unconfirmed
+// transactions but will not ask the mempool to relay them. We do this on startup
+// to ensure that our own mempool is aware of our transactions, and to also
+// initialize nNextResend so that the actual rebroadcast is scheduled. There
+// is a privacy side effect here as not broadcasting on startup also means that we won't
+// inform the world of our wallet's state, particularly if the wallet (or node) is not
+// yet synced.
+//
+// Otherwise this function is called periodically in order to relay our unconfirmed txs.
+// We do this on a random timer to slightly obfuscate which transactions
+// come from our wallet.
 //
-// Ideally, we'd only resend transactions that we think should have been
+// TODO: Ideally, we'd only resend transactions that we think should have been
 // mined in the most recent block. Any transaction that wasn't in the top
 // blockweight of transactions in the mempool shouldn't have been mined,
 // and so is probably just sitting in the mempool waiting to be confirmed.
 // Rebroadcasting does nothing to speed up confirmation and only damages
 // privacy.
-void CWallet::ResendWalletTransactions()
+//
+// The `force` option results in all unconfirmed transactions being submitted to
+// the mempool. This does not necessarily result in those transactions being relayed,
+// that depends on the `relay` option. Periodic rebroadcast uses the pattern
+// relay=true force=false (also the default values), while loading into the mempool
+// (on start, or after import) uses relay=false force=true.
+void CWallet::ResubmitWalletTransactions(bool relay, bool force)
 {
+    // Don't attempt to resubmit if the wallet is configured to not broadcast,
+    // even if forcing.
+    if (!fBroadcastTransactions) return;
+
     // During reindex, importing and IBD, old wallet transactions become
     // unconfirmed. Don't resend them as that would spam other nodes.
-    if (!chain().isReadyToBroadcast()) return;
+    // We only allow forcing mempool submission when not relaying to avoid this spam.
+    if (!force && relay && !chain().isReadyToBroadcast()) return;
 
     // Do this infrequently and randomly to avoid giving away
     // that these are our transactions.
-    if (GetTime() < nNextResend || !fBroadcastTransactions) return;
-    bool fFirst = (nNextResend == 0);
+    if (!force && GetTime() < nNextResend) return;
     // resend 12-36 hours from now, ~1 day on average.
     nNextResend = GetTime() + (12 * 60 * 60) + GetRand(24 * 60 * 60);
-    if (fFirst) return;
 
     int submitted_tx_count = 0;
 
     { // cs_wallet scope
         LOCK(cs_wallet);
 
-        // Relay transactions
-        for (std::pair<const uint256, CWalletTx>& item : mapWallet) {
-            CWalletTx& wtx = item.second;
-            // Attempt to rebroadcast all txes more than 5 minutes older than
-            // the last block. SubmitTxMemoryPoolAndRelay() will not rebroadcast
-            // any confirmed or conflicting txs.
-            if (wtx.nTimeReceived > m_best_block_time - 5 * 60) continue;
+        // First filter for the transactions we want to rebroadcast.
+        // We use a set with WalletTxOrderComparator so that rebroadcasting occurs in insertion order
+        std::set<CWalletTx*, WalletTxOrderComparator> to_submit;
+        for (auto& [txid, wtx] : mapWallet) {
+            // Only rebroadcast unconfirmed txs
+            if (!wtx.isUnconfirmed()) continue;
+
+            // attempt to rebroadcast all txes more than 5 minutes older than
+            // the last block, or all txs if forcing.
+            if (!force && wtx.nTimeReceived > m_best_block_time - 5 * 60) continue;
+            to_submit.insert(&wtx);
+        }
+        // Now try submitting the transactions to the memory pool and (optionally) relay them.
+        for (auto wtx : to_submit) {
             std::string unused_err_string;
-            if (SubmitTxMemoryPoolAndRelay(wtx, unused_err_string, true)) ++submitted_tx_count;
+            if (SubmitTxMemoryPoolAndRelay(*wtx, unused_err_string, relay)) ++submitted_tx_count;
         }
     } // cs_wallet
 
@@ -1975,7 +1973,7 @@ void CWallet::ResendWalletTransactions()
 void MaybeResendWalletTxs(WalletContext& context)
 {
     for (const std::shared_ptr<CWallet>& pwallet : GetWallets(context)) {
-        pwallet->ResendWalletTransactions();
+        pwallet->ResubmitWalletTransactions(/*relay=*/true, /*force=*/false);
     }
 }
 
@@ -3191,7 +3189,7 @@ void CWallet::postInitProcess()
 
     // Add wallet transactions that aren't already in a block to mempool
     // Do this here as mempool requires genesis block to be loaded
-    ReacceptWalletTransactions();
+    ResubmitWalletTransactions(/*relay=*/false, /*force=*/true);
 
     // Update wallet transactions with current mempool transactions.
     chain().requestMempoolTransactions(*this);
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index dc148512f8..f4ea5f1920 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -537,8 +537,7 @@ public:
     };
     ScanResult ScanForWalletTransactions(const uint256& start_block, int start_height, std::optional<int> max_height, const WalletRescanReserver& reserver, bool fUpdate, const bool save_progress);
     void transactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t mempool_sequence) override;
-    void ReacceptWalletTransactions() EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
-    void ResendWalletTransactions();
+    void ResubmitWalletTransactions(bool relay, bool force);
 
     OutputType TransactionChangeType(const std::optional<OutputType>& change_type, const std::vector<CRecipient>& vecSend) const;