Merge bitcoin/bitcoin#27675: p2p: Drop m_recently_announced_invs bloom filter

fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0 mempool_entry: improve struct packing (Anthony Towns)
1a118062fbc4ec8f645f4ec4298d869a869c3344 net_processing: Clean up INVENTORY_BROADCAST_MAX constants (Anthony Towns)
6fa49937e488d0924044786c76b42324b659f351 test: Check tx from disconnected block is immediately requestable (glozow)
e4ffabbffacc4b890d393aafcc8286916ef887d8 net_processing: don't add txids to m_tx_inventory_known_filter (Anthony Towns)
6ec1809d33bfc42b80cb6f35625dccd56be8d507 net_processing: drop m_recently_announced_invs bloom filter (Anthony Towns)
a70beafdb22564043dc24fc98133fdadbaf77d8a validation: when adding txs due to a block reorg, allow immediate relay (Anthony Towns)
1e9684f39fba909b3501e9402d5b61f4bf744ff2 mempool_entry: add mempool entry sequence number (Anthony Towns)

Pull request description:

  This PR replaces the `m_recently_announced_invs` bloom filter with a simple sequence number tracking the mempool state when we last considered sending an INV message to a node. This saves 33kB per peer (or more if we raise the rate at which we relay transactions over the network, in which case we would need to increase the size of the bloom filter proportionally).

  The philosophy here (compare with #18861 and #19109) is that we consider the rate limiting on INV messages to only be about saving bandwidth and not protecting privacy, and therefore after you receive an INV message, it's immediately fair game to request any transaction that was in the mempool at the time the INV message was sent. We likewise consider the BIP 133 feefilter and BIP 37 bloom filters to be bandwidth optimisations here, and treat transactions as requestable if they would have been announced without those filters. Given that philosophy, tracking the timestamp of the last INV message and comparing that against the mempool entry time allows removal of each of `m_recently_announced_invs`, `m_last_mempool_req` and `UNCONDITIONAL_RELAY_DELAY` and associated logic.

ACKs for top commit:
  naumenkogs:
    ACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0
  amitiuttarwar:
    review ACK fb02ba3c5f5
  glozow:
    reACK fb02ba3c5f5bcd96b5e3622ef001b8e57ce63fc0

Tree-SHA512: cbba5ee04c86df26b6057f3654c00a2b45ec94d354f4f157a769cecdaa0b509edaac02b3128afba39b023e82473fc5e28c915a787f84457ffe66638c6ac9c2d4

15 files changed, 151 insertions, 91 deletions

diff --git a/src/bench/mempool_eviction.cpp b/src/bench/mempool_eviction.cpp
index 735dc92dfb..1a9b013277 100644
--- a/src/bench/mempool_eviction.cpp
+++ b/src/bench/mempool_eviction.cpp
@@ -13,11 +13,12 @@ static void AddTx(const CTransactionRef& tx, const CAmount& nFee, CTxMemPool& po
 {
     int64_t nTime = 0;
     unsigned int nHeight = 1;
+    uint64_t sequence = 0;
     bool spendsCoinbase = false;
     unsigned int sigOpCost = 4;
     LockPoints lp;
     pool.addUnchecked(CTxMemPoolEntry(
-        tx, nFee, nTime, nHeight,
+        tx, nFee, nTime, nHeight, sequence,
         spendsCoinbase, sigOpCost, lp));
 }
 
diff --git a/src/bench/mempool_stress.cpp b/src/bench/mempool_stress.cpp
index 826da73800..1f94461d19 100644
--- a/src/bench/mempool_stress.cpp
+++ b/src/bench/mempool_stress.cpp
@@ -16,10 +16,11 @@ static void AddTx(const CTransactionRef& tx, CTxMemPool& pool) EXCLUSIVE_LOCKS_R
 {
     int64_t nTime = 0;
     unsigned int nHeight = 1;
+    uint64_t sequence = 0;
     bool spendsCoinbase = false;
     unsigned int sigOpCost = 4;
     LockPoints lp;
-    pool.addUnchecked(CTxMemPoolEntry(tx, 1000, nTime, nHeight, spendsCoinbase, sigOpCost, lp));
+    pool.addUnchecked(CTxMemPoolEntry(tx, 1000, nTime, nHeight, sequence, spendsCoinbase, sigOpCost, lp));
 }
 
 struct Available {
diff --git a/src/bench/rpc_mempool.cpp b/src/bench/rpc_mempool.cpp
index 7e274370e0..a55aa0c794 100644
--- a/src/bench/rpc_mempool.cpp
+++ b/src/bench/rpc_mempool.cpp
@@ -16,7 +16,7 @@
 static void AddTx(const CTransactionRef& tx, const CAmount& fee, CTxMemPool& pool) EXCLUSIVE_LOCKS_REQUIRED(cs_main, pool.cs)
 {
     LockPoints lp;
-    pool.addUnchecked(CTxMemPoolEntry(tx, fee, /*time=*/0, /*entry_height=*/1, /*spends_coinbase=*/false, /*sigops_cost=*/4, lp));
+    pool.addUnchecked(CTxMemPoolEntry(tx, fee, /*time=*/0, /*entry_height=*/1, /*entry_sequence=*/0, /*spends_coinbase=*/false, /*sigops_cost=*/4, lp));
 }
 
 static void RpcMempool(benchmark::Bench& bench)
diff --git a/src/kernel/mempool_entry.h b/src/kernel/mempool_entry.h
index 886e1e1b3a..1f175a5ccf 100644
--- a/src/kernel/mempool_entry.h
+++ b/src/kernel/mempool_entry.h
@@ -78,6 +78,7 @@ private:
     const int32_t nTxWeight;         //!< ... and avoid recomputing tx weight (also used for GetTxSize())
     const size_t nUsageSize;        //!< ... and total memory usage
     const int64_t nTime;            //!< Local time when entering the mempool
+    const uint64_t entry_sequence;  //!< Sequence number used to determine whether this transaction is too recent for relay
     const unsigned int entryHeight; //!< Chain height when entering the mempool
     const bool spendsCoinbase;      //!< keep track of transactions that spend a coinbase
     const int64_t sigOpCost;        //!< Total sigop cost
@@ -101,7 +102,7 @@ private:
 
 public:
     CTxMemPoolEntry(const CTransactionRef& tx, CAmount fee,
-                    int64_t time, unsigned int entry_height,
+                    int64_t time, unsigned int entry_height, uint64_t entry_sequence,
                     bool spends_coinbase,
                     int64_t sigops_cost, LockPoints lp)
         : tx{tx},
@@ -109,6 +110,7 @@ public:
           nTxWeight{GetTransactionWeight(*tx)},
           nUsageSize{RecursiveDynamicUsage(tx)},
           nTime{time},
+          entry_sequence{entry_sequence},
           entryHeight{entry_height},
           spendsCoinbase{spends_coinbase},
           sigOpCost{sigops_cost},
@@ -130,6 +132,7 @@ public:
     int32_t GetTxWeight() const { return nTxWeight; }
     std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
     unsigned int GetHeight() const { return entryHeight; }
+    uint64_t GetSequence() const { return entry_sequence; }
     int64_t GetSigOpCost() const { return sigOpCost; }
     CAmount GetModifiedFee() const { return m_modified_fee; }
     size_t DynamicMemoryUsage() const { return nUsageSize; }
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index e2bbfe3308..6d011c239b 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -51,8 +51,6 @@
 #include <optional>
 #include <typeinfo>
 
-/** How long a transaction has to be in the mempool before it can unconditionally be relayed. */
-static constexpr auto UNCONDITIONAL_RELAY_DELAY = 2min;
 /** Headers download timeout.
  *  Timeout = base + per_header * (expected number of headers) */
 static constexpr auto HEADERS_DOWNLOAD_TIMEOUT_BASE = 15min;
@@ -149,15 +147,12 @@ static constexpr auto OUTBOUND_INVENTORY_BROADCAST_INTERVAL{2s};
 /** Maximum rate of inventory items to send per second.
  *  Limits the impact of low-fee transaction floods. */
 static constexpr unsigned int INVENTORY_BROADCAST_PER_SECOND = 7;
+/** Target number of tx inventory items to send per transmission. */
+static constexpr unsigned int INVENTORY_BROADCAST_TARGET = INVENTORY_BROADCAST_PER_SECOND * count_seconds(INBOUND_INVENTORY_BROADCAST_INTERVAL);
 /** Maximum number of inventory items to send per transmission. */
-static constexpr unsigned int INVENTORY_BROADCAST_MAX = INVENTORY_BROADCAST_PER_SECOND * count_seconds(INBOUND_INVENTORY_BROADCAST_INTERVAL);
-/** The number of most recently announced transactions a peer can request. */
-static constexpr unsigned int INVENTORY_MAX_RECENT_RELAY = 3500;
-/** Verify that INVENTORY_MAX_RECENT_RELAY is enough to cache everything typically
- *  relayed before unconditional relay from the mempool kicks in. This is only a
- *  lower bound, and it should be larger to account for higher inv rate to outbound
- *  peers, and random variations in the broadcast mechanism. */
-static_assert(INVENTORY_MAX_RECENT_RELAY >= INVENTORY_BROADCAST_PER_SECOND * UNCONDITIONAL_RELAY_DELAY / std::chrono::seconds{1}, "INVENTORY_RELAY_MAX too low");
+static constexpr unsigned int INVENTORY_BROADCAST_MAX = 1000;
+static_assert(INVENTORY_BROADCAST_MAX >= INVENTORY_BROADCAST_TARGET, "INVENTORY_BROADCAST_MAX too low");
+static_assert(INVENTORY_BROADCAST_MAX <= MAX_PEER_TX_ANNOUNCEMENTS, "INVENTORY_BROADCAST_MAX too high");
 /** Average delay between feefilter broadcasts in seconds. */
 static constexpr auto AVG_FEEFILTER_BROADCAST_INTERVAL{10min};
 /** Maximum feefilter broadcast delay after significant change. */
@@ -273,13 +268,10 @@ struct Peer {
         /** A bloom filter for which transactions to announce to the peer. See BIP37. */
         std::unique_ptr<CBloomFilter> m_bloom_filter PT_GUARDED_BY(m_bloom_filter_mutex) GUARDED_BY(m_bloom_filter_mutex){nullptr};
 
-        /** A rolling bloom filter of all announced tx CInvs to this peer */
-        CRollingBloomFilter m_recently_announced_invs GUARDED_BY(NetEventsInterface::g_msgproc_mutex){INVENTORY_MAX_RECENT_RELAY, 0.000001};
-
         mutable RecursiveMutex m_tx_inventory_mutex;
-        /** A filter of all the txids and wtxids that the peer has announced to
+        /** A filter of all the (w)txids that the peer has announced to
          *  us or we have announced to the peer. We use this to avoid announcing
-         *  the same txid/wtxid to a peer that already has the transaction. */
+         *  the same (w)txid to a peer that already has the transaction. */
         CRollingBloomFilter m_tx_inventory_known_filter GUARDED_BY(m_tx_inventory_mutex){50000, 0.000001};
         /** Set of transaction ids we still have to announce (txid for
          *  non-wtxid-relay peers, wtxid for wtxid-relay peers). We use the
@@ -290,11 +282,12 @@ struct Peer {
          *  permitted if the peer has NetPermissionFlags::Mempool or we advertise
          *  NODE_BLOOM. See BIP35. */
         bool m_send_mempool GUARDED_BY(m_tx_inventory_mutex){false};
-        /** The last time a BIP35 `mempool` request was serviced. */
-        std::atomic<std::chrono::seconds> m_last_mempool_req{0s};
         /** The next time after which we will send an `inv` message containing
          *  transaction announcements to this peer. */
         std::chrono::microseconds m_next_inv_send_time GUARDED_BY(m_tx_inventory_mutex){0};
+        /** The mempool sequence num at which we sent the last `inv` message to this peer.
+         *  Can relay txs with lower sequence numbers than this (see CTxMempool::info_for_relay). */
+        uint64_t m_last_inv_sequence GUARDED_BY(NetEventsInterface::g_msgproc_mutex){1};
 
         /** Minimum fee rate with which to filter transaction announcements to this node. See BIP133. */
         std::atomic<CAmount> m_fee_filter_received{0};
@@ -907,7 +900,7 @@ private:
     std::atomic<std::chrono::seconds> m_last_tip_update{0s};
 
     /** Determine whether or not a peer can request a transaction, and return it (or nullptr if not found or not allowed). */
-    CTransactionRef FindTxForGetData(const Peer::TxRelay& tx_relay, const GenTxid& gtxid, const std::chrono::seconds mempool_req, const std::chrono::seconds now)
+    CTransactionRef FindTxForGetData(const Peer::TxRelay& tx_relay, const GenTxid& gtxid)
         EXCLUSIVE_LOCKS_REQUIRED(!m_most_recent_block_mutex, NetEventsInterface::g_msgproc_mutex);
 
     void ProcessGetData(CNode& pfrom, Peer& peer, const std::atomic<bool>& interruptMsgProc)
@@ -2288,22 +2281,14 @@ void PeerManagerImpl::ProcessGetBlockData(CNode& pfrom, Peer& peer, const CInv&
     }
 }
 
-CTransactionRef PeerManagerImpl::FindTxForGetData(const Peer::TxRelay& tx_relay, const GenTxid& gtxid, const std::chrono::seconds mempool_req, const std::chrono::seconds now)
+CTransactionRef PeerManagerImpl::FindTxForGetData(const Peer::TxRelay& tx_relay, const GenTxid& gtxid)
 {
-    auto txinfo = m_mempool.info(gtxid);
+    // If a tx was in the mempool prior to the last INV for this peer, permit the request.
+    auto txinfo = m_mempool.info_for_relay(gtxid, tx_relay.m_last_inv_sequence);
     if (txinfo.tx) {
-        // If a TX could have been INVed in reply to a MEMPOOL request,
-        // or is older than UNCONDITIONAL_RELAY_DELAY, permit the request
-        // unconditionally.
-        if ((mempool_req.count() && txinfo.m_time <= mempool_req) || txinfo.m_time <= now - UNCONDITIONAL_RELAY_DELAY) {
-            return std::move(txinfo.tx);
-        }
+        return std::move(txinfo.tx);
     }
 
-    // Otherwise, the transaction might have been announced recently.
-    bool recent = tx_relay.m_recently_announced_invs.contains(gtxid.GetHash());
-    if (recent && txinfo.tx) return std::move(txinfo.tx);
-
     // Or it might be from the most recent block
     {
         LOCK(m_most_recent_block_mutex);
@@ -2326,10 +2311,6 @@ void PeerManagerImpl::ProcessGetData(CNode& pfrom, Peer& peer, const std::atomic
     std::vector<CInv> vNotFound;
     const CNetMsgMaker msgMaker(pfrom.GetCommonVersion());
 
-    const auto now{GetTime<std::chrono::seconds>()};
-    // Get last mempool request time
-    const auto mempool_req = tx_relay != nullptr ? tx_relay->m_last_mempool_req.load() : std::chrono::seconds::min();
-
     // Process as many TX items from the front of the getdata queue as
     // possible, since they're common and it's efficient to batch process
     // them.
@@ -2347,33 +2328,12 @@ void PeerManagerImpl::ProcessGetData(CNode& pfrom, Peer& peer, const std::atomic
             continue;
         }
 
-        CTransactionRef tx = FindTxForGetData(*tx_relay, ToGenTxid(inv), mempool_req, now);
+        CTransactionRef tx = FindTxForGetData(*tx_relay, ToGenTxid(inv));
         if (tx) {
             // WTX and WITNESS_TX imply we serialize with witness
             int nSendFlags = (inv.IsMsgTx() ? SERIALIZE_TRANSACTION_NO_WITNESS : 0);
             m_connman.PushMessage(&pfrom, msgMaker.Make(nSendFlags, NetMsgType::TX, *tx));
             m_mempool.RemoveUnbroadcastTx(tx->GetHash());
-            // As we're going to send tx, make sure its unconfirmed parents are made requestable.
-            std::vector<uint256> parent_ids_to_add;
-            {
-                LOCK(m_mempool.cs);
-                auto tx_iter = m_mempool.GetIter(tx->GetHash());
-                if (tx_iter) {
-                    const CTxMemPoolEntry::Parents& parents = (*tx_iter)->GetMemPoolParentsConst();
-                    parent_ids_to_add.reserve(parents.size());
-                    for (const CTxMemPoolEntry& parent : parents) {
-                        if (parent.GetTime() > now - UNCONDITIONAL_RELAY_DELAY) {
-                            parent_ids_to_add.push_back(parent.GetTx().GetHash());
-                        }
-                    }
-                }
-            }
-            for (const uint256& parent_txid : parent_ids_to_add) {
-                // Relaying a transaction with a recent but unconfirmed parent.
-                if (WITH_LOCK(tx_relay->m_tx_inventory_mutex, return !tx_relay->m_tx_inventory_known_filter.contains(parent_txid))) {
-                    tx_relay->m_recently_announced_invs.insert(parent_txid);
-                }
-            }
         } else {
             vNotFound.push_back(inv);
         }
@@ -4131,14 +4091,6 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type,
 
         const uint256& hash = peer->m_wtxid_relay ? wtxid : txid;
         AddKnownTx(*peer, hash);
-        if (peer->m_wtxid_relay && txid != wtxid) {
-            // Insert txid into m_tx_inventory_known_filter, even for
-            // wtxidrelay peers. This prevents re-adding of
-            // unconfirmed parents to the recently_announced
-            // filter, when a child tx is requested. See
-            // ProcessGetData().
-            AddKnownTx(*peer, txid);
-        }
 
         LOCK(cs_main);
 
@@ -5684,7 +5636,7 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
         std::vector<CInv> vInv;
         {
             LOCK(peer->m_block_inv_mutex);
-            vInv.reserve(std::max<size_t>(peer->m_blocks_for_inv_relay.size(), INVENTORY_BROADCAST_MAX));
+            vInv.reserve(std::max<size_t>(peer->m_blocks_for_inv_relay.size(), INVENTORY_BROADCAST_TARGET));
 
             // Add blocks
             for (const uint256& hash : peer->m_blocks_for_inv_relay) {
@@ -5736,14 +5688,12 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
                             if (!tx_relay->m_bloom_filter->IsRelevantAndUpdate(*txinfo.tx)) continue;
                         }
                         tx_relay->m_tx_inventory_known_filter.insert(hash);
-                        // Responses to MEMPOOL requests bypass the m_recently_announced_invs filter.
                         vInv.push_back(inv);
                         if (vInv.size() == MAX_INV_SZ) {
                             m_connman.PushMessage(pto, msgMaker.Make(NetMsgType::INV, vInv));
                             vInv.clear();
                         }
                     }
-                    tx_relay->m_last_mempool_req = std::chrono::duration_cast<std::chrono::seconds>(current_time);
                 }
 
                 // Determine transactions to relay
@@ -5763,8 +5713,8 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
                     // especially since we have many peers and some will draw much shorter delays.
                     unsigned int nRelayedTransactions = 0;
                     LOCK(tx_relay->m_bloom_filter_mutex);
-                    size_t broadcast_max{INVENTORY_BROADCAST_MAX + (tx_relay->m_tx_inventory_to_send.size()/1000)*5};
-                    broadcast_max = std::min<size_t>(1000, broadcast_max);
+                    size_t broadcast_max{INVENTORY_BROADCAST_TARGET + (tx_relay->m_tx_inventory_to_send.size()/1000)*5};
+                    broadcast_max = std::min<size_t>(INVENTORY_BROADCAST_MAX, broadcast_max);
                     while (!vInvTx.empty() && nRelayedTransactions < broadcast_max) {
                         // Fetch the top element from the heap
                         std::pop_heap(vInvTx.begin(), vInvTx.end(), compareInvMempoolOrder);
@@ -5783,14 +5733,12 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
                         if (!txinfo.tx) {
                             continue;
                         }
-                        auto txid = txinfo.tx->GetHash();
                         // Peer told you to not send transactions at that feerate? Don't bother sending it.
                         if (txinfo.fee < filterrate.GetFee(txinfo.vsize)) {
                             continue;
                         }
                         if (tx_relay->m_bloom_filter && !tx_relay->m_bloom_filter->IsRelevantAndUpdate(*txinfo.tx)) continue;
                         // Send
-                        tx_relay->m_recently_announced_invs.insert(hash);
                         vInv.push_back(inv);
                         nRelayedTransactions++;
                         if (vInv.size() == MAX_INV_SZ) {
@@ -5798,15 +5746,11 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
                             vInv.clear();
                         }
                         tx_relay->m_tx_inventory_known_filter.insert(hash);
-                        if (hash != txid) {
-                            // Insert txid into m_tx_inventory_known_filter, even for
-                            // wtxidrelay peers. This prevents re-adding of
-                            // unconfirmed parents to the recently_announced
-                            // filter, when a child tx is requested. See
-                            // ProcessGetData().
-                            tx_relay->m_tx_inventory_known_filter.insert(txid);
-                        }
                     }
+
+                    // Ensure we'll respond to GETDATA requests for anything we've just announced
+                    LOCK(m_mempool.cs);
+                    tx_relay->m_last_inv_sequence = m_mempool.GetSequence();
                 }
         }
         if (!vInv.empty())
diff --git a/src/node/interfaces.cpp b/src/node/interfaces.cpp
index 42e021fcc9..14192bd962 100644
--- a/src/node/interfaces.cpp
+++ b/src/node/interfaces.cpp
@@ -677,7 +677,7 @@ public:
     {
         if (!m_node.mempool) return true;
         LockPoints lp;
-        CTxMemPoolEntry entry(tx, 0, 0, 0, false, 0, lp);
+        CTxMemPoolEntry entry(tx, 0, 0, 0, 0, false, 0, lp);
         const CTxMemPool::Limits& limits{m_node.mempool->m_limits};
         LOCK(m_node.mempool->cs);
         return m_node.mempool->CalculateMemPoolAncestors(entry, limits).has_value();
diff --git a/src/test/fuzz/util/mempool.cpp b/src/test/fuzz/util/mempool.cpp
index 4baca5ec77..8e7499a860 100644
--- a/src/test/fuzz/util/mempool.cpp
+++ b/src/test/fuzz/util/mempool.cpp
@@ -23,8 +23,9 @@ CTxMemPoolEntry ConsumeTxMemPoolEntry(FuzzedDataProvider& fuzzed_data_provider,
     const CAmount fee{ConsumeMoney(fuzzed_data_provider, /*max=*/std::numeric_limits<CAmount>::max() / CAmount{100'000})};
     assert(MoneyRange(fee));
     const int64_t time = fuzzed_data_provider.ConsumeIntegral<int64_t>();
+    const uint64_t entry_sequence{fuzzed_data_provider.ConsumeIntegral<uint64_t>()};
     const unsigned int entry_height = fuzzed_data_provider.ConsumeIntegral<unsigned int>();
     const bool spends_coinbase = fuzzed_data_provider.ConsumeBool();
     const unsigned int sig_op_cost = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, MAX_BLOCK_SIGOPS_COST);
-    return CTxMemPoolEntry{MakeTransactionRef(tx), fee, time, entry_height, spends_coinbase, sig_op_cost, {}};
+    return CTxMemPoolEntry{MakeTransactionRef(tx), fee, time, entry_height, entry_sequence, spends_coinbase, sig_op_cost, {}};
 }
diff --git a/src/test/util/setup_common.cpp b/src/test/util/setup_common.cpp
index 08ef890ec4..ecae743d14 100644
--- a/src/test/util/setup_common.cpp
+++ b/src/test/util/setup_common.cpp
@@ -424,7 +424,7 @@ std::vector<CTransactionRef> TestChain100Setup::PopulateMempool(FastRandomContex
             LOCK2(cs_main, m_node.mempool->cs);
             LockPoints lp;
             m_node.mempool->addUnchecked(CTxMemPoolEntry(ptx, /*fee=*/(total_in - num_outputs * amount_per_output),
-                                                         /*time=*/0, /*entry_height=*/1,
+                                                         /*time=*/0, /*entry_height=*/1, /*entry_sequence=*/0,
                                                          /*spends_coinbase=*/false, /*sigops_cost=*/4, lp));
         }
         --num_transactions;
@@ -454,7 +454,7 @@ void TestChain100Setup::MockMempoolMinFee(const CFeeRate& target_feerate)
     const auto tx_fee = target_feerate.GetFee(GetVirtualTransactionSize(*tx)) -
         m_node.mempool->m_incremental_relay_feerate.GetFee(GetVirtualTransactionSize(*tx));
     m_node.mempool->addUnchecked(CTxMemPoolEntry(tx, /*fee=*/tx_fee,
-                                                 /*time=*/0, /*entry_height=*/1,
+                                                 /*time=*/0, /*entry_height=*/1, /*entry_sequence=*/0,
                                                  /*spends_coinbase=*/true, /*sigops_cost=*/1, lp));
     m_node.mempool->TrimToSize(0);
     assert(m_node.mempool->GetMinFee() == target_feerate);
diff --git a/src/test/util/txmempool.cpp b/src/test/util/txmempool.cpp
index 4797d9c310..c945f35d79 100644
--- a/src/test/util/txmempool.cpp
+++ b/src/test/util/txmempool.cpp
@@ -34,5 +34,5 @@ CTxMemPoolEntry TestMemPoolEntryHelper::FromTx(const CMutableTransaction& tx) co
 
 CTxMemPoolEntry TestMemPoolEntryHelper::FromTx(const CTransactionRef& tx) const
 {
-    return CTxMemPoolEntry{tx, nFee, TicksSinceEpoch<std::chrono::seconds>(time), nHeight, spendsCoinbase, sigOpCost, lp};
+    return CTxMemPoolEntry{tx, nFee, TicksSinceEpoch<std::chrono::seconds>(time), nHeight, m_sequence, spendsCoinbase, sigOpCost, lp};
 }
diff --git a/src/test/util/txmempool.h b/src/test/util/txmempool.h
index 2fe7d69693..4b0daf0d42 100644
--- a/src/test/util/txmempool.h
+++ b/src/test/util/txmempool.h
@@ -19,6 +19,7 @@ struct TestMemPoolEntryHelper {
     CAmount nFee{0};
     NodeSeconds time{};
     unsigned int nHeight{1};
+    uint64_t m_sequence{0};
     bool spendsCoinbase{false};
     unsigned int sigOpCost{4};
     LockPoints lp;
@@ -30,6 +31,7 @@ struct TestMemPoolEntryHelper {
     TestMemPoolEntryHelper& Fee(CAmount _fee) { nFee = _fee; return *this; }
     TestMemPoolEntryHelper& Time(NodeSeconds tp) { time = tp; return *this; }
     TestMemPoolEntryHelper& Height(unsigned int _height) { nHeight = _height; return *this; }
+    TestMemPoolEntryHelper& Sequence(uint64_t _seq) { m_sequence = _seq; return *this; }
     TestMemPoolEntryHelper& SpendsCoinbase(bool _flag) { spendsCoinbase = _flag; return *this; }
     TestMemPoolEntryHelper& SigOpsCost(unsigned int _sigopsCost) { sigOpCost = _sigopsCost; return *this; }
 };
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 79b2b4ec94..497a41d6a9 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -853,6 +853,17 @@ TxMempoolInfo CTxMemPool::info(const GenTxid& gtxid) const
     return GetInfo(i);
 }
 
+TxMempoolInfo CTxMemPool::info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const
+{
+    LOCK(cs);
+    indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash()));
+    if (i != mapTx.end() && i->GetSequence() < last_sequence) {
+        return GetInfo(i);
+    } else {
+        return TxMempoolInfo();
+    }
+}
+
 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
 {
     {
diff --git a/src/txmempool.h b/src/txmempool.h
index fa1dbbf4b5..4d7d53ff68 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -708,6 +708,10 @@ public:
         return mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid));
     }
     TxMempoolInfo info(const GenTxid& gtxid) const;
+
+    /** Returns info for a transaction if its entry_sequence < last_sequence */
+    TxMempoolInfo info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const;
+
     std::vector<TxMempoolInfo> infoAll() const;
 
     size_t DynamicMemoryUsage() const;
diff --git a/src/validation.cpp b/src/validation.cpp
index cec6d13181..d6c4d49b34 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -833,7 +833,10 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
         }
     }
 
-    entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(),
+    // Set entry_sequence to 0 when bypass_limits is used; this allows txs from a block
+    // reorg to be marked earlier than any child txs that were already in the mempool.
+    const uint64_t entry_sequence = bypass_limits ? 0 : m_pool.GetSequence();
+    entry.reset(new CTxMemPoolEntry(ptx, ws.m_base_fees, nAcceptTime, m_active_chainstate.m_chain.Height(), entry_sequence,
                                     fSpendsCoinbase, nSigOpsCost, lock_points.value()));
     ws.m_vsize = entry->GetTxSize();
 
diff --git a/src/validation.h b/src/validation.h
index 4c9f807f5d..e4980c51a7 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -241,7 +241,8 @@ struct PackageMempoolAcceptResult
  * @param[in]  tx                 The transaction to submit for mempool acceptance.
  * @param[in]  accept_time        The timestamp for adding the transaction to the mempool.
  *                                It is also used to determine when the entry expires.
- * @param[in]  bypass_limits      When true, don't enforce mempool fee and capacity limits.
+ * @param[in]  bypass_limits      When true, don't enforce mempool fee and capacity limits,
+ *                                and set entry_sequence to zero.
  * @param[in]  test_accept        When true, run validation checks but don't submit to mempool.
  *
  * @returns a MempoolAcceptResult indicating whether the transaction was accepted/rejected with reason.
diff --git a/test/functional/mempool_reorg.py b/test/functional/mempool_reorg.py
index 3a5bc1ebcd..28ba666dc7 100755
--- a/test/functional/mempool_reorg.py
+++ b/test/functional/mempool_reorg.py
@@ -8,6 +8,17 @@ Test re-org scenarios with a mempool that contains transactions
 that spend (directly or indirectly) coinbase transactions.
 """
 
+import time
+
+from test_framework.messages import (
+    CInv,
+    MSG_WTX,
+    msg_getdata,
+)
+from test_framework.p2p import (
+    P2PTxInvStore,
+    p2p_lock,
+)
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import assert_equal, assert_raises_rpc_error
 from test_framework.wallet import MiniWallet
@@ -22,8 +33,84 @@ class MempoolCoinbaseTest(BitcoinTestFramework):
             []
         ]
 
+    def test_reorg_relay(self):
+        self.log.info("Test that transactions from disconnected blocks are available for relay immediately")
+        # Prevent time from moving forward
+        self.nodes[1].setmocktime(int(time.time()))
+        self.connect_nodes(0, 1)
+        self.generate(self.wallet, 3)
+
+        # Disconnect node0 and node1 to create different chains.
+        self.disconnect_nodes(0, 1)
+        # Connect a peer to node1, which doesn't have immediate tx relay
+        peer1 = self.nodes[1].add_p2p_connection(P2PTxInvStore())
+
+        # Create a transaction that is included in a block.
+        tx_disconnected = self.wallet.send_self_transfer(from_node=self.nodes[1])
+        self.generate(self.nodes[1], 1, sync_fun=self.no_op)
+
+        # Create a transaction and submit it to node1's mempool.
+        tx_before_reorg = self.wallet.send_self_transfer(from_node=self.nodes[1])
+
+        # Create a child of that transaction and submit it to node1's mempool.
+        tx_child = self.wallet.send_self_transfer(utxo_to_spend=tx_disconnected["new_utxo"], from_node=self.nodes[1])
+        assert_equal(self.nodes[1].getmempoolentry(tx_child["txid"])["ancestorcount"], 1)
+        assert_equal(len(peer1.get_invs()), 0)
+
+        # node0 has a longer chain in which tx_disconnected was not confirmed.
+        self.generate(self.nodes[0], 3, sync_fun=self.no_op)
+
+        # Reconnect the nodes and sync chains. node0's chain should win.
+        self.connect_nodes(0, 1)
+        self.sync_blocks()
+
+        # Child now has an ancestor from the disconnected block
+        assert_equal(self.nodes[1].getmempoolentry(tx_child["txid"])["ancestorcount"], 2)
+        assert_equal(self.nodes[1].getmempoolentry(tx_before_reorg["txid"])["ancestorcount"], 1)
+
+        # peer1 should not have received an inv for any of the transactions during this time, as not
+        # enough time has elapsed for those transactions to be announced. Likewise, it cannot
+        # request very recent, unanounced transactions.
+        assert_equal(len(peer1.get_invs()), 0)
+        # It's too early to request these two transactions
+        requests_too_recent = msg_getdata([CInv(t=MSG_WTX, h=int(tx["tx"].getwtxid(), 16)) for tx in [tx_before_reorg, tx_child]])
+        peer1.send_and_ping(requests_too_recent)
+        for _ in range(len(requests_too_recent.inv)):
+            peer1.sync_with_ping()
+        with p2p_lock:
+            assert "tx" not in peer1.last_message
+            assert "notfound" in peer1.last_message
+
+        # Request the tx from the disconnected block
+        request_disconnected_tx = msg_getdata([CInv(t=MSG_WTX, h=int(tx_disconnected["tx"].getwtxid(), 16))])
+        peer1.send_and_ping(request_disconnected_tx)
+
+        # The tx from the disconnected block was never announced, and it entered the mempool later
+        # than the transactions that are too recent.
+        assert_equal(len(peer1.get_invs()), 0)
+        with p2p_lock:
+            # However, the node will answer requests for the tx from the recently-disconnected block.
+            assert_equal(peer1.last_message["tx"].tx.getwtxid(),tx_disconnected["tx"].getwtxid())
+
+        self.nodes[1].setmocktime(int(time.time()) + 30)
+        peer1.sync_with_ping()
+        # the transactions are now announced
+        assert_equal(len(peer1.get_invs()), 3)
+        for _ in range(3):
+            # make sure all tx requests have been responded to
+            peer1.sync_with_ping()
+        last_tx_received = peer1.last_message["tx"]
+
+        tx_after_reorg = self.wallet.send_self_transfer(from_node=self.nodes[1])
+        request_after_reorg = msg_getdata([CInv(t=MSG_WTX, h=int(tx_after_reorg["tx"].getwtxid(), 16))])
+        assert tx_after_reorg["txid"] in self.nodes[1].getrawmempool()
+        peer1.send_and_ping(request_after_reorg)
+        with p2p_lock:
+            assert_equal(peer1.last_message["tx"], last_tx_received)
+
     def run_test(self):
-        wallet = MiniWallet(self.nodes[0])
+        self.wallet = MiniWallet(self.nodes[0])
+        wallet = self.wallet
 
         # Start with a 200 block chain
         assert_equal(self.nodes[0].getblockcount(), 200)
@@ -103,6 +190,8 @@ class MempoolCoinbaseTest(BitcoinTestFramework):
         assert_equal(set(self.nodes[0].getrawmempool()), set())
         self.sync_all()
 
+        self.test_reorg_relay()
+
 
 if __name__ == '__main__':
     MempoolCoinbaseTest().main()