Merge #19606: Backport wtxid relay to v0.20

d4a1ee8f1d4c46ab726be83965bd86bace2ec1ec Further improve comments around recentRejects (Suhas Daftuar)
f082a13ab756a378b260711a30d363f833a2306a Disconnect peers sending wtxidrelay message after VERACK (Suhas Daftuar)
22effa51a77a8b8c72ba3525cb08dd0cf8464715 test: Use wtxid relay generally in functional tests (Fabian Jahr)
e4816819630d1e94469ca5499361e0cd2c9ac7c2 test: Add tests for wtxid tx relay in segwit test (Fabian Jahr)
6be398b6fb7a7d5c6c1fe6d74a0700b7ff93674e test: Update test framework p2p protocol version to 70016 (Fabian Jahr)
e364b2a2d879e8d30ca9dbc578e4d169b41eb227 Rename AddInventoryKnown() to AddKnownTx() (Suhas Daftuar)
879a3cf2c2367d51310204d21030f3b218582c30 Make TX_WITNESS_STRIPPED its own rejection reason (Suhas Daftuar)
c1d6a1003d601ec4ff7d9507563254b29868182f Delay getdata requests from peers using txid-based relay (Suhas Daftuar)
181ffadd162a84551b3518de77b5dcc08c712425 Add p2p message "wtxidrelay" (Suhas Daftuar)
93826726e76730b061ec4c91d69b2b34ebf98ec9 ignore non-wtxidrelay compliant invs (Anthony Towns)
2599277e9cb51e3619582978cba9bf03325c0cb6 Add support for tx-relay via wtxid (Suhas Daftuar)
be1b7a8916fdd060db56846ad5dcec0894aae314 Add wtxids to recentRejects (Suhas Daftuar)
73845211d16ad1558d84c966ae18e3507fa7dea6 Add wtxids of confirmed transactions to bloom filter (Suhas Daftuar)
606755b840b1560e4f92c9252fa4cab6eacabdd3 Add wtxid-index to orphan map (Suhas Daftuar)
36549376740d28159a5834ecf4ed9eeeeef6715d Add a wtxid-index to mapRelay (Suhas Daftuar)
f7833b5bd894aca2d8820402f4a500d71374ea0e Just pass a hash to AddInventoryKnown (Suhas Daftuar)
4df3d139b7261de33c070691f76a535b8b17433a Add a wtxid-index to the mempool (Suhas Daftuar)

Pull request description:

  We want wtxid relay to be widely deployed before taproot activation, so it should be backported to v0.20.

  The main difference from #18044 is removing the changes to the unbroadcast set (which was only added post-v0.20). The rest is mostly minor rebase conflicts (eg connman changed from a pointer to a reference in master, etc).

  We'll also want to backport #19569 after that's merged.

ACKs for top commit:
  fjahr:
    re-ACK d4a1ee8f1d4c46ab726be83965bd86bace2ec1ec
  instagibbs:
    reACK https://github.com/bitcoin/bitcoin/pull/19606/commits/d4a1ee8f1d4c46ab726be83965bd86bace2ec1ec
  laanwj:
    re-ACK d4a1ee8f1d4c46ab726be83965bd86bace2ec1ec
  hebasto:
    re-ACK d4a1ee8f1d4c46ab726be83965bd86bace2ec1ec, only rebased since my [previous](https://github.com/bitcoin/bitcoin/pull/19606#pullrequestreview-492763028) review:

Tree-SHA512: 1bb8725dd2313a9a03cacf8fb7317986eed3d8d1648fa627528441256c37c793bb0fae6c8c139d05ac45d0c7a86265792834e8e09cbf45286426ca6544c10cd5

19 files changed, 444 insertions, 101 deletions

diff --git a/src/consensus/validation.h b/src/consensus/validation.h
index 3a90cd69b3..f7d476951b 100644
--- a/src/consensus/validation.h
+++ b/src/consensus/validation.h
@@ -31,12 +31,16 @@ enum class TxValidationResult {
     TX_MISSING_INPUTS,        //!< transaction was missing some of its inputs
     TX_PREMATURE_SPEND,       //!< transaction spends a coinbase too early, or violates locktime/sequence locks
     /**
-     * Transaction might be missing a witness, have a witness prior to SegWit
+     * Transaction might have a witness prior to SegWit
      * activation, or witness may have been malleated (which includes
      * non-standard witnesses).
      */
     TX_WITNESS_MUTATED,
     /**
+     * Transaction is missing a witness.
+     */
+    TX_WITNESS_STRIPPED,
+    /**
      * Tx already in mempool or conflicts with a tx in the chain
      * (if it conflicts with another tx in mempool, we use MEMPOOL_POLICY as it failed to reach the RBF threshold)
      * Currently this is only used if the transaction already exists in the mempool or on chain.
diff --git a/src/net.h b/src/net.h
index 0dbd5e0549..8822e4e35d 100644
--- a/src/net.h
+++ b/src/net.h
@@ -969,11 +969,11 @@ public:
     }
 
 
-    void AddInventoryKnown(const CInv& inv)
+    void AddKnownTx(const uint256& hash)
     {
         if (m_tx_relay != nullptr) {
             LOCK(m_tx_relay->cs_tx_inventory);
-            m_tx_relay->filterInventoryKnown.insert(inv.hash);
+            m_tx_relay->filterInventoryKnown.insert(hash);
         }
     }
 
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 8572ebb9f7..79a0ce7559 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -68,6 +68,8 @@ static constexpr int HISTORICAL_BLOCK_AGE = 7 * 24 * 60 * 60;
 static constexpr int32_t MAX_PEER_TX_IN_FLIGHT = 100;
 /** Maximum number of announced transactions from a peer */
 static constexpr int32_t MAX_PEER_TX_ANNOUNCEMENTS = 2 * MAX_INV_SZ;
+/** How many microseconds to delay requesting transactions via txids, if we have wtxid-relaying peers */
+static constexpr std::chrono::microseconds TXID_RELAY_DELAY{std::chrono::seconds{2}};
 /** How many microseconds to delay requesting transactions from inbound peers */
 static constexpr std::chrono::microseconds INBOUND_PEER_TX_DELAY{std::chrono::seconds{2}};
 /** How long to wait (in microseconds) before downloading a transaction from an additional peer */
@@ -91,6 +93,7 @@ struct COrphanTx {
 };
 RecursiveMutex g_cs_orphans;
 std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans);
+std::map<uint256, std::map<uint256, COrphanTx>::iterator> g_orphans_by_wtxid GUARDED_BY(g_cs_orphans);
 
 void EraseOrphansFor(NodeId peer);
 
@@ -142,6 +145,15 @@ namespace {
      * million to make it highly unlikely for users to have issues with this
      * filter.
      *
+     * We only need to add wtxids to this filter. For non-segwit
+     * transactions, the txid == wtxid, so this only prevents us from
+     * re-downloading non-segwit transactions when communicating with
+     * non-wtxidrelay peers -- which is important for avoiding malleation
+     * attacks that could otherwise interfere with transaction relay from
+     * non-wtxidrelay peers. For communicating with wtxidrelay peers, having
+     * the reject filter store wtxids is exactly what we want to avoid
+     * redownload of a rejected transaction.
+     *
      * Memory used: 1.3 MB
      */
     std::unique_ptr<CRollingBloomFilter> recentRejects GUARDED_BY(cs_main);
@@ -173,6 +185,9 @@ namespace {
     /** Number of peers from which we're downloading blocks. */
     int nPeersWithValidatedDownloads GUARDED_BY(cs_main) = 0;
 
+    /** Number of peers with wtxid relay. */
+    int g_wtxid_relay_peers GUARDED_BY(cs_main) = 0;
+
     /** Number of outbound peers with m_chain_sync.m_protect. */
     int g_outbound_peers_with_protect_from_disconnect GUARDED_BY(cs_main) = 0;
 
@@ -361,6 +376,9 @@ struct CNodeState {
     //! Whether this peer is a manual connection
     bool m_is_manual_connection;
 
+    //! Whether this peer relays txs via wtxid
+    bool m_wtxid_relay{false};
+
     CNodeState(CAddress addrIn, std::string addrNameIn, bool is_inbound, bool is_manual) :
         address(addrIn), name(std::move(addrNameIn)), m_is_inbound(is_inbound),
         m_is_manual_connection (is_manual)
@@ -711,7 +729,7 @@ void UpdateTxRequestTime(const uint256& txid, std::chrono::microseconds request_
     }
 }
 
-std::chrono::microseconds CalculateTxGetDataTime(const uint256& txid, std::chrono::microseconds current_time, bool use_inbound_delay) EXCLUSIVE_LOCKS_REQUIRED(cs_main)
+std::chrono::microseconds CalculateTxGetDataTime(const uint256& txid, std::chrono::microseconds current_time, bool use_inbound_delay, bool use_txid_delay) EXCLUSIVE_LOCKS_REQUIRED(cs_main)
 {
     std::chrono::microseconds process_time;
     const auto last_request_time = GetTxRequestTime(txid);
@@ -727,6 +745,9 @@ std::chrono::microseconds CalculateTxGetDataTime(const uint256& txid, std::chron
     // We delay processing announcements from inbound peers
     if (use_inbound_delay) process_time += INBOUND_PEER_TX_DELAY;
 
+    // We delay processing announcements from peers that use txid-relay (instead of wtxid)
+    if (use_txid_delay) process_time += TXID_RELAY_DELAY;
+
     return process_time;
 }
 
@@ -744,7 +765,7 @@ void RequestTx(CNodeState* state, const uint256& txid, std::chrono::microseconds
 
     // Calculate the time to try requesting this transaction. Use
     // fPreferredDownload as a proxy for outbound peers.
-    const auto process_time = CalculateTxGetDataTime(txid, current_time, !state->fPreferredDownload);
+    const auto process_time = CalculateTxGetDataTime(txid, current_time, !state->fPreferredDownload, !state->m_wtxid_relay && g_wtxid_relay_peers > 0);
 
     peer_download_state.m_tx_process_time.emplace(process_time, txid);
 }
@@ -801,6 +822,8 @@ void PeerLogicValidation::FinalizeNode(NodeId nodeid, bool& fUpdateConnectionTim
     assert(nPeersWithValidatedDownloads >= 0);
     g_outbound_peers_with_protect_from_disconnect -= state->m_chain_sync.m_protect;
     assert(g_outbound_peers_with_protect_from_disconnect >= 0);
+    g_wtxid_relay_peers -= state->m_wtxid_relay;
+    assert(g_wtxid_relay_peers >= 0);
 
     mapNodeState.erase(nodeid);
 
@@ -810,6 +833,7 @@ void PeerLogicValidation::FinalizeNode(NodeId nodeid, bool& fUpdateConnectionTim
         assert(nPreferredDownload == 0);
         assert(nPeersWithValidatedDownloads == 0);
         assert(g_outbound_peers_with_protect_from_disconnect == 0);
+        assert(g_wtxid_relay_peers == 0);
     }
     LogPrint(BCLog::NET, "Cleared nodestate for peer=%d\n", nodeid);
 }
@@ -868,6 +892,8 @@ bool AddOrphanTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRE
     auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, g_orphan_list.size()});
     assert(ret.second);
     g_orphan_list.push_back(ret.first);
+    // Allow for lookups in the orphan pool by wtxid, as well as txid
+    g_orphans_by_wtxid.emplace(tx->GetWitnessHash(), ret.first);
     for (const CTxIn& txin : tx->vin) {
         mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first);
     }
@@ -904,6 +930,7 @@ int static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
         it_last->second.list_pos = old_pos;
     }
     g_orphan_list.pop_back();
+    g_orphans_by_wtxid.erase(it->second.tx->GetWitnessHash());
 
     mapOrphanTransactions.erase(it);
     return 1;
@@ -1074,6 +1101,7 @@ static bool MaybePunishNodeForTx(NodeId nodeid, const TxValidationState& state,
     case TxValidationResult::TX_MISSING_INPUTS:
     case TxValidationResult::TX_PREMATURE_SPEND:
     case TxValidationResult::TX_WITNESS_MUTATED:
+    case TxValidationResult::TX_WITNESS_STRIPPED:
     case TxValidationResult::TX_CONFLICT:
     case TxValidationResult::TX_MEMPOOL_POLICY:
         break;
@@ -1113,14 +1141,15 @@ PeerLogicValidation::PeerLogicValidation(CConnman* connmanIn, BanMan* banman, CS
     recentRejects.reset(new CRollingBloomFilter(120000, 0.000001));
 
     // Blocks don't typically have more than 4000 transactions, so this should
-    // be at least six blocks (~1 hr) worth of transactions that we can store.
+    // be at least six blocks (~1 hr) worth of transactions that we can store,
+    // inserting both a txid and wtxid for every observed transaction.
     // If the number of transactions appearing in a block goes up, or if we are
     // seeing getdata requests more than an hour after initial announcement, we
     // can increase this number.
     // The false positive rate of 1/1M should come out to less than 1
     // transaction per day that would be inadvertently ignored (which is the
     // same probability that we have in the reject filter).
-    g_recent_confirmed_transactions.reset(new CRollingBloomFilter(24000, 0.000001));
+    g_recent_confirmed_transactions.reset(new CRollingBloomFilter(48000, 0.000001));
 
     const Consensus::Params& consensusParams = Params().GetConsensus();
     // Stale tip checking and peer eviction are on two different timers, but we
@@ -1172,6 +1201,9 @@ void PeerLogicValidation::BlockConnected(const std::shared_ptr<const CBlock>& pb
         LOCK(g_cs_recent_confirmed_transactions);
         for (const auto& ptx : pblock->vtx) {
             g_recent_confirmed_transactions->insert(ptx->GetHash());
+            if (ptx->GetHash() != ptx->GetWitnessHash()) {
+                g_recent_confirmed_transactions->insert(ptx->GetWitnessHash());
+            }
         }
     }
 }
@@ -1324,6 +1356,7 @@ bool static AlreadyHave(const CInv& inv, const CTxMemPool& mempool) EXCLUSIVE_LO
     {
     case MSG_TX:
     case MSG_WITNESS_TX:
+    case MSG_WTX:
         {
             assert(recentRejects);
             if (::ChainActive().Tip()->GetBlockHash() != hashRecentRejectsChainTip)
@@ -1338,7 +1371,11 @@ bool static AlreadyHave(const CInv& inv, const CTxMemPool& mempool) EXCLUSIVE_LO
 
             {
                 LOCK(g_cs_orphans);
-                if (mapOrphanTransactions.count(inv.hash)) return true;
+                if (inv.type != MSG_WTX && mapOrphanTransactions.count(inv.hash)) {
+                    return true;
+                } else if (inv.type == MSG_WTX && g_orphans_by_wtxid.count(inv.hash)) {
+                    return true;
+                }
             }
 
             {
@@ -1346,8 +1383,8 @@ bool static AlreadyHave(const CInv& inv, const CTxMemPool& mempool) EXCLUSIVE_LO
                 if (g_recent_confirmed_transactions->contains(inv.hash)) return true;
             }
 
-            return recentRejects->contains(inv.hash) ||
-                   mempool.exists(inv.hash);
+            const bool by_wtxid = (inv.type == MSG_WTX);
+            return recentRejects->contains(inv.hash) || mempool.exists(inv.hash, by_wtxid);
         }
     case MSG_BLOCK:
     case MSG_WITNESS_BLOCK:
@@ -1357,12 +1394,17 @@ bool static AlreadyHave(const CInv& inv, const CTxMemPool& mempool) EXCLUSIVE_LO
     return true;
 }
 
-void RelayTransaction(const uint256& txid, const CConnman& connman)
+void RelayTransaction(const uint256& txid, const uint256& wtxid, const CConnman& connman)
 {
-    CInv inv(MSG_TX, txid);
-    connman.ForEachNode([&inv](CNode* pnode)
+    connman.ForEachNode([&txid, &wtxid](CNode* pnode)
     {
-        pnode->PushInventory(inv);
+        AssertLockHeld(cs_main);
+        CNodeState &state = *State(pnode->GetId());
+        if (state.m_wtxid_relay) {
+            pnode->PushInventory({MSG_TX, wtxid});  // inv type is MSG_TX even for wtxid relay
+        } else {
+            pnode->PushInventory({MSG_TX, txid});
+        }
     });
 }
 
@@ -1577,7 +1619,7 @@ void static ProcessGetData(CNode* pfrom, const CChainParams& chainparams, CConnm
         // 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.
-        while (it != pfrom->vRecvGetData.end() && (it->type == MSG_TX || it->type == MSG_WITNESS_TX)) {
+        while (it != pfrom->vRecvGetData.end() && (it->type == MSG_TX || it->type == MSG_WITNESS_TX || it->type == MSG_WTX)) {
             if (interruptMsgProc)
                 return;
             // The send buffer provides backpressure. If there's no space in
@@ -1600,7 +1642,7 @@ void static ProcessGetData(CNode* pfrom, const CChainParams& chainparams, CConnm
                 connman->PushMessage(pfrom, msgMaker.Make(nSendFlags, NetMsgType::TX, *mi->second));
                 push = true;
             } else {
-                auto txinfo = mempool.info(inv.hash);
+                auto txinfo = mempool.info(inv.hash, inv.type == MSG_WTX);
                 // To protect privacy, do not answer getdata using the mempool when
                 // that TX couldn't have been INVed in reply to a MEMPOOL request,
                 // or when it's too recent to have expired from mapRelay.
@@ -1880,7 +1922,7 @@ void static ProcessOrphanTx(CConnman* connman, CTxMemPool& mempool, std::set<uin
         if (setMisbehaving.count(fromPeer)) continue;
         if (AcceptToMemoryPool(mempool, orphan_state, porphanTx, &removed_txn, false /* bypass_limits */, 0 /* nAbsurdFee */)) {
             LogPrint(BCLog::MEMPOOL, "   accepted orphan tx %s\n", orphanHash.ToString());
-            RelayTransaction(orphanHash, *connman);
+            RelayTransaction(orphanHash, porphanTx->GetWitnessHash(), *connman);
             for (unsigned int i = 0; i < orphanTx.vout.size(); i++) {
                 auto it_by_prev = mapOrphanTransactionsByPrev.find(COutPoint(orphanHash, i));
                 if (it_by_prev != mapOrphanTransactionsByPrev.end()) {
@@ -1902,17 +1944,35 @@ void static ProcessOrphanTx(CConnman* connman, CTxMemPool& mempool, std::set<uin
             // Has inputs but not accepted to mempool
             // Probably non-standard or insufficient fee
             LogPrint(BCLog::MEMPOOL, "   removed orphan tx %s\n", orphanHash.ToString());
-            if ((!orphanTx.HasWitness() && orphan_state.GetResult() != TxValidationResult::TX_WITNESS_MUTATED) ||
-                    orphan_state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD) {
-                // Do not use rejection cache for witness transactions or
-                // witness-stripped transactions, as they can have been malleated.
-                // See https://github.com/bitcoin/bitcoin/issues/8279 for details.
-                // However, if the transaction failed for TX_INPUTS_NOT_STANDARD,
+            if (orphan_state.GetResult() != TxValidationResult::TX_WITNESS_STRIPPED) {
+                // We can add the wtxid of this transaction to our reject filter.
+                // Do not add txids of witness transactions or witness-stripped
+                // transactions to the filter, as they can have been malleated;
+                // adding such txids to the reject filter would potentially
+                // interfere with relay of valid transactions from peers that
+                // do not support wtxid-based relay. See
+                // https://github.com/bitcoin/bitcoin/issues/8279 for details.
+                // We can remove this restriction (and always add wtxids to
+                // the filter even for witness stripped transactions) once
+                // wtxid-based relay is broadly deployed.
+                // See also comments in https://github.com/bitcoin/bitcoin/pull/18044#discussion_r443419034
+                // for concerns around weakening security of unupgraded nodes
+                // if we start doing this too early.
+                assert(recentRejects);
+                recentRejects->insert(orphanTx.GetWitnessHash());
+                // If the transaction failed for TX_INPUTS_NOT_STANDARD,
                 // then we know that the witness was irrelevant to the policy
                 // failure, since this check depends only on the txid
                 // (the scriptPubKey being spent is covered by the txid).
-                assert(recentRejects);
-                recentRejects->insert(orphanHash);
+                // Add the txid to the reject filter to prevent repeated
+                // processing of this transaction in the event that child
+                // transactions are later received (resulting in
+                // parent-fetching by txid via the orphan-handling logic).
+                if (orphan_state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD && orphanTx.GetWitnessHash() != orphanTx.GetHash()) {
+                    // We only add the txid if it differs from the wtxid, to
+                    // avoid wasting entries in the rolling bloom filter.
+                    recentRejects->insert(orphanTx.GetHash());
+                }
             }
             EraseOrphanTx(orphanHash);
             done = true;
@@ -2016,6 +2076,10 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
         if (pfrom->fInbound)
             PushNodeVersion(pfrom, connman, GetAdjustedTime());
 
+        if (nVersion >= WTXID_RELAY_VERSION) {
+            connman->PushMessage(pfrom, CNetMsgMaker(INIT_PROTO_VERSION).Make(NetMsgType::WTXIDRELAY));
+        }
+
         connman->PushMessage(pfrom, CNetMsgMaker(INIT_PROTO_VERSION).Make(NetMsgType::VERACK));
 
         pfrom->nServices = nServices;
@@ -2155,6 +2219,25 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
         return true;
     }
 
+    // Feature negotiation of wtxidrelay should happen between VERSION and
+    // VERACK, to avoid relay problems from switching after a connection is up
+    if (msg_type == NetMsgType::WTXIDRELAY) {
+        if (pfrom->fSuccessfullyConnected) {
+            // Disconnect peers that send wtxidrelay message after VERACK; this
+            // must be negotiated between VERSION and VERACK.
+            pfrom->fDisconnect = true;
+            return false;
+        }
+        if (pfrom->nVersion >= WTXID_RELAY_VERSION) {
+            LOCK(cs_main);
+            if (!State(pfrom->GetId())->m_wtxid_relay) {
+                State(pfrom->GetId())->m_wtxid_relay = true;
+                g_wtxid_relay_peers++;
+            }
+        }
+        return false;
+    }
+
     if (!pfrom->fSuccessfullyConnected) {
         // Must have a verack message before anything else
         LOCK(cs_main);
@@ -2275,6 +2358,13 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
             if (interruptMsgProc)
                 return true;
 
+            // ignore INVs that don't match wtxidrelay setting
+            if (State(pfrom->GetId())->m_wtxid_relay) {
+                if (inv.type == MSG_TX) continue;
+            } else {
+                if (inv.type == MSG_WTX) continue;
+            }
+
             bool fAlreadyHave = AlreadyHave(inv, mempool);
             LogPrint(BCLog::NET, "got inv: %s  %s peer=%d\n", inv.ToString(), fAlreadyHave ? "have" : "new", pfrom->GetId());
 
@@ -2293,7 +2383,7 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
                     best_block = &inv.hash;
                 }
             } else {
-                pfrom->AddInventoryKnown(inv);
+                pfrom->AddKnownTx(inv.hash);
                 if (fBlocksOnly) {
                     LogPrint(BCLog::NET, "transaction (%s) inv sent in violation of protocol, disconnecting peer=%d\n", inv.hash.ToString(), pfrom->GetId());
                     pfrom->fDisconnect = true;
@@ -2532,26 +2622,50 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
         vRecv >> ptx;
         const CTransaction& tx = *ptx;
 
-        CInv inv(MSG_TX, tx.GetHash());
-        pfrom->AddInventoryKnown(inv);
+        const uint256& txid = ptx->GetHash();
+        const uint256& wtxid = ptx->GetWitnessHash();
 
         LOCK2(cs_main, g_cs_orphans);
 
+        CNodeState* nodestate = State(pfrom->GetId());
+
+        const uint256& hash = nodestate->m_wtxid_relay ? wtxid : txid;
+        pfrom->AddKnownTx(hash);
+        if (nodestate->m_wtxid_relay && txid != wtxid) {
+            // Insert txid into filterInventoryKnown, even for
+            // wtxidrelay peers. This prevents re-adding of
+            // unconfirmed parents to the recently_announced
+            // filter, when a child tx is requested. See
+            // ProcessGetData().
+            pfrom->AddKnownTx(txid);
+        }
+
         TxValidationState state;
 
-        CNodeState* nodestate = State(pfrom->GetId());
-        nodestate->m_tx_download.m_tx_announced.erase(inv.hash);
-        nodestate->m_tx_download.m_tx_in_flight.erase(inv.hash);
-        EraseTxRequest(inv.hash);
+        nodestate->m_tx_download.m_tx_announced.erase(hash);
+        nodestate->m_tx_download.m_tx_in_flight.erase(hash);
+        EraseTxRequest(hash);
 
         std::list<CTransactionRef> lRemovedTxn;
 
-        if (!AlreadyHave(inv, mempool) &&
+        // We do the AlreadyHave() check using wtxid, rather than txid - in the
+        // absence of witness malleation, this is strictly better, because the
+        // recent rejects filter may contain the wtxid but will never contain
+        // the txid of a segwit transaction that has been rejected.
+        // In the presence of witness malleation, it's possible that by only
+        // doing the check with wtxid, we could overlook a transaction which
+        // was confirmed with a different witness, or exists in our mempool
+        // with a different witness, but this has limited downside:
+        // mempool validation does its own lookup of whether we have the txid
+        // already; and an adversary can already relay us old transactions
+        // (older than our recency filter) if trying to DoS us, without any need
+        // for witness malleation.
+        if (!AlreadyHave(CInv(MSG_WTX, wtxid), mempool) &&
             AcceptToMemoryPool(mempool, state, ptx, &lRemovedTxn, false /* bypass_limits */, 0 /* nAbsurdFee */)) {
             mempool.check(&::ChainstateActive().CoinsTip());
-            RelayTransaction(tx.GetHash(), *connman);
+            RelayTransaction(tx.GetHash(), tx.GetWitnessHash(), *connman);
             for (unsigned int i = 0; i < tx.vout.size(); i++) {
-                auto it_by_prev = mapOrphanTransactionsByPrev.find(COutPoint(inv.hash, i));
+                auto it_by_prev = mapOrphanTransactionsByPrev.find(COutPoint(txid, i));
                 if (it_by_prev != mapOrphanTransactionsByPrev.end()) {
                     for (const auto& elem : it_by_prev->second) {
                         pfrom->orphan_work_set.insert(elem->first);
@@ -2582,10 +2696,17 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
                 uint32_t nFetchFlags = GetFetchFlags(pfrom);
                 const auto current_time = GetTime<std::chrono::microseconds>();
 
-                for (const CTxIn& txin : tx.vin) {
-                    CInv _inv(MSG_TX | nFetchFlags, txin.prevout.hash);
-                    pfrom->AddInventoryKnown(_inv);
-                    if (!AlreadyHave(_inv, mempool)) RequestTx(State(pfrom->GetId()), _inv.hash, current_time);
+                if (!State(pfrom->GetId())->m_wtxid_relay) {
+                    for (const CTxIn& txin : tx.vin) {
+                        // Here, we only have the txid (and not wtxid) of the
+                        // inputs, so we only request parents from
+                        // non-wtxid-relay peers.
+                        // Eventually we should replace this with an improved
+                        // protocol for getting all unconfirmed parents.
+                        CInv _inv(MSG_TX | nFetchFlags, txin.prevout.hash);
+                        pfrom->AddKnownTx(txin.prevout.hash);
+                        if (!AlreadyHave(_inv, mempool)) RequestTx(State(pfrom->GetId()), _inv.hash, current_time);
+                    }
                 }
                 AddOrphanTx(ptx, pfrom->GetId());
 
@@ -2599,20 +2720,41 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
                 LogPrint(BCLog::MEMPOOL, "not keeping orphan with rejected parents %s\n",tx.GetHash().ToString());
                 // We will continue to reject this tx since it has rejected
                 // parents so avoid re-requesting it from other peers.
+                // Here we add both the txid and the wtxid, as we know that
+                // regardless of what witness is provided, we will not accept
+                // this, so we don't need to allow for redownload of this txid
+                // from any of our non-wtxidrelay peers.
                 recentRejects->insert(tx.GetHash());
+                recentRejects->insert(tx.GetWitnessHash());
             }
         } else {
-            if ((!tx.HasWitness() && state.GetResult() != TxValidationResult::TX_WITNESS_MUTATED) ||
-                    state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD) {
-                // Do not use rejection cache for witness transactions or
-                // witness-stripped transactions, as they can have been malleated.
-                // See https://github.com/bitcoin/bitcoin/issues/8279 for details.
-                // However, if the transaction failed for TX_INPUTS_NOT_STANDARD,
+            if (state.GetResult() != TxValidationResult::TX_WITNESS_STRIPPED) {
+                // We can add the wtxid of this transaction to our reject filter.
+                // Do not add txids of witness transactions or witness-stripped
+                // transactions to the filter, as they can have been malleated;
+                // adding such txids to the reject filter would potentially
+                // interfere with relay of valid transactions from peers that
+                // do not support wtxid-based relay. See
+                // https://github.com/bitcoin/bitcoin/issues/8279 for details.
+                // We can remove this restriction (and always add wtxids to
+                // the filter even for witness stripped transactions) once
+                // wtxid-based relay is broadly deployed.
+                // See also comments in https://github.com/bitcoin/bitcoin/pull/18044#discussion_r443419034
+                // for concerns around weakening security of unupgraded nodes
+                // if we start doing this too early.
+                assert(recentRejects);
+                recentRejects->insert(tx.GetWitnessHash());
+                // If the transaction failed for TX_INPUTS_NOT_STANDARD,
                 // then we know that the witness was irrelevant to the policy
                 // failure, since this check depends only on the txid
                 // (the scriptPubKey being spent is covered by the txid).
-                assert(recentRejects);
-                recentRejects->insert(tx.GetHash());
+                // Add the txid to the reject filter to prevent repeated
+                // processing of this transaction in the event that child
+                // transactions are later received (resulting in
+                // parent-fetching by txid via the orphan-handling logic).
+                if (state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD && tx.GetWitnessHash() != tx.GetHash()) {
+                    recentRejects->insert(tx.GetHash());
+                }
                 if (RecursiveDynamicUsage(*ptx) < 100000) {
                     AddToCompactExtraTransactions(ptx);
                 }
@@ -2629,7 +2771,7 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
                     LogPrintf("Not relaying non-mempool transaction %s from whitelisted peer=%d\n", tx.GetHash().ToString(), pfrom->GetId());
                 } else {
                     LogPrintf("Force relaying tx %s from whitelisted peer=%d\n", tx.GetHash().ToString(), pfrom->GetId());
-                    RelayTransaction(tx.GetHash(), *connman);
+                    RelayTransaction(tx.GetHash(), tx.GetWitnessHash(), *connman);
                 }
             }
         }
@@ -3245,7 +3387,7 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
         vRecv >> vInv;
         if (vInv.size() <= MAX_PEER_TX_IN_FLIGHT + MAX_BLOCKS_IN_TRANSIT_PER_PEER) {
             for (CInv &inv : vInv) {
-                if (inv.type == MSG_TX || inv.type == MSG_WITNESS_TX) {
+                if (inv.type == MSG_TX || inv.type == MSG_WITNESS_TX || inv.type == MSG_WTX) {
                     // If we receive a NOTFOUND message for a txid we requested, erase
                     // it from our data structures for this peer.
                     auto in_flight_it = state->m_tx_download.m_tx_in_flight.find(inv.hash);
@@ -3537,17 +3679,19 @@ namespace {
 class CompareInvMempoolOrder
 {
     CTxMemPool *mp;
+    bool m_wtxid_relay;
 public:
-    explicit CompareInvMempoolOrder(CTxMemPool *_mempool)
+    explicit CompareInvMempoolOrder(CTxMemPool *_mempool, bool use_wtxid)
     {
         mp = _mempool;
+        m_wtxid_relay = use_wtxid;
     }
 
     bool operator()(std::set<uint256>::iterator a, std::set<uint256>::iterator b)
     {
         /* As std::make_heap produces a max-heap, we want the entries with the
          * fewest ancestors/highest fee to sort later. */
-        return mp->CompareDepthAndScore(*b, *a);
+        return mp->CompareDepthAndScore(*b, *a, m_wtxid_relay);
     }
 };
 }
@@ -3854,8 +3998,8 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                     LOCK(pto->m_tx_relay->cs_filter);
 
                     for (const auto& txinfo : vtxinfo) {
-                        const uint256& hash = txinfo.tx->GetHash();
-                        CInv inv(MSG_TX, hash);
+                        const uint256& hash = state.m_wtxid_relay ? txinfo.tx->GetWitnessHash() : txinfo.tx->GetHash();
+                        CInv inv(state.m_wtxid_relay ? MSG_WTX : MSG_TX, hash);
                         pto->m_tx_relay->setInventoryTxToSend.erase(hash);
                         // Don't send transactions that peers will not put into their mempool
                         if (txinfo.fee < filterrate.GetFee(txinfo.vsize)) {
@@ -3889,7 +4033,7 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                     }
                     // Topologically and fee-rate sort the inventory we send for privacy and priority reasons.
                     // A heap is used so that not all items need sorting if only a few are being sent.
-                    CompareInvMempoolOrder compareInvMempoolOrder(&m_mempool);
+                    CompareInvMempoolOrder compareInvMempoolOrder(&m_mempool, state.m_wtxid_relay);
                     std::make_heap(vInvTx.begin(), vInvTx.end(), compareInvMempoolOrder);
                     // No reason to drain out at many times the network's capacity,
                     // especially since we have many peers and some will draw much shorter delays.
@@ -3908,17 +4052,19 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                             continue;
                         }
                         // Not in the mempool anymore? don't bother sending it.
-                        auto txinfo = m_mempool.info(hash);
+                        auto txinfo = m_mempool.info(hash, state.m_wtxid_relay);
                         if (!txinfo.tx) {
                             continue;
                         }
+                        auto txid = txinfo.tx->GetHash();
+                        auto wtxid = txinfo.tx->GetWitnessHash();
                         // Peer told you to not send transactions at that feerate? Don't bother sending it.
                         if (txinfo.fee < filterrate.GetFee(txinfo.vsize)) {
                             continue;
                         }
                         if (pto->m_tx_relay->pfilter && !pto->m_tx_relay->pfilter->IsRelevantAndUpdate(*txinfo.tx)) continue;
                         // Send
-                        vInv.push_back(CInv(MSG_TX, hash));
+                        vInv.push_back(CInv(state.m_wtxid_relay ? MSG_WTX : MSG_TX, hash));
                         nRelayedTransactions++;
                         {
                             // Expire old relay messages
@@ -3928,9 +4074,14 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                                 vRelayExpiration.pop_front();
                             }
 
-                            auto ret = mapRelay.insert(std::make_pair(hash, std::move(txinfo.tx)));
+                            auto ret = mapRelay.emplace(txid, std::move(txinfo.tx));
                             if (ret.second) {
-                                vRelayExpiration.push_back(std::make_pair(nNow + std::chrono::microseconds{RELAY_TX_CACHE_TIME}.count(), ret.first));
+                                vRelayExpiration.emplace_back(nNow + std::chrono::microseconds{RELAY_TX_CACHE_TIME}.count(), ret.first);
+                            }
+                            // Add wtxid-based lookup into mapRelay as well, so that peers can request by wtxid
+                            auto ret2 = mapRelay.emplace(wtxid, ret.first->second);
+                            if (ret2.second) {
+                                vRelayExpiration.emplace_back(nNow + std::chrono::microseconds{RELAY_TX_CACHE_TIME}.count(), ret2.first);
                             }
                         }
                         if (vInv.size() == MAX_INV_SZ) {
@@ -3938,6 +4089,14 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                             vInv.clear();
                         }
                         pto->m_tx_relay->filterInventoryKnown.insert(hash);
+                        if (hash != txid) {
+                            // Insert txid into filterInventoryKnown, even for
+                            // wtxidrelay peers. This prevents re-adding of
+                            // unconfirmed parents to the recently_announced
+                            // filter, when a child tx is requested. See
+                            // ProcessGetData().
+                            pto->m_tx_relay->filterInventoryKnown.insert(txid);
+                        }
                     }
                 }
             }
@@ -4062,7 +4221,7 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
             // Erase this entry from tx_process_time (it may be added back for
             // processing at a later time, see below)
             tx_process_time.erase(tx_process_time.begin());
-            CInv inv(MSG_TX | GetFetchFlags(pto), txid);
+            CInv inv(state.m_wtxid_relay ? MSG_WTX : (MSG_TX | GetFetchFlags(pto)), txid);
             if (!AlreadyHave(inv, m_mempool)) {
                 // If this transaction was last requested more than 1 minute ago,
                 // then request.
@@ -4081,7 +4240,15 @@ bool PeerLogicValidation::SendMessages(CNode* pto)
                     // up processing to happen after the download times out
                     // (with a slight delay for inbound peers, to prefer
                     // requests to outbound peers).
-                    const auto next_process_time = CalculateTxGetDataTime(txid, current_time, !state.fPreferredDownload);
+                    // Don't apply the txid-delay to re-requests of a
+                    // transaction; the heuristic of delaying requests to
+                    // txid-relay peers is to save bandwidth on initial
+                    // announcement of a transaction, and doesn't make sense
+                    // for a followup request if our first peer times out (and
+                    // would open us up to an attacker using inbound
+                    // wtxid-relay to prevent us from requesting transactions
+                    // from outbound txid-relay peers).
+                    const auto next_process_time = CalculateTxGetDataTime(txid, current_time, !state.fPreferredDownload, false);
                     tx_process_time.emplace(next_process_time, txid);
                 }
             } else {
@@ -4134,6 +4301,7 @@ public:
         // orphan transactions
         mapOrphanTransactions.clear();
         mapOrphanTransactionsByPrev.clear();
+        g_orphans_by_wtxid.clear();
     }
 };
 static CNetProcessingCleanup instance_of_cnetprocessingcleanup;
diff --git a/src/net_processing.h b/src/net_processing.h
index ddb1780148..79a3ccd4ed 100644
--- a/src/net_processing.h
+++ b/src/net_processing.h
@@ -92,6 +92,6 @@ struct CNodeStateStats {
 bool GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats);
 
 /** Relay transaction to every node */
-void RelayTransaction(const uint256&, const CConnman& connman);
+void RelayTransaction(const uint256& txid, const uint256& wtxid, const CConnman& connman) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
 #endif // BITCOIN_NET_PROCESSING_H
diff --git a/src/node/transaction.cpp b/src/node/transaction.cpp
index 201406ce3b..17878eeb17 100644
--- a/src/node/transaction.cpp
+++ b/src/node/transaction.cpp
@@ -78,7 +78,8 @@ TransactionError BroadcastTransaction(NodeContext& node, const CTransactionRef t
     }
 
     if (relay) {
-        RelayTransaction(hashTx, *node.connman);
+        LOCK(cs_main);
+        RelayTransaction(hashTx, tx->GetWitnessHash(), *node.connman);
     }
 
     return TransactionError::OK;
diff --git a/src/protocol.cpp b/src/protocol.cpp
index bd3ed25a8a..8b2043fda4 100644
--- a/src/protocol.cpp
+++ b/src/protocol.cpp
@@ -40,6 +40,7 @@ const char *SENDCMPCT="sendcmpct";
 const char *CMPCTBLOCK="cmpctblock";
 const char *GETBLOCKTXN="getblocktxn";
 const char *BLOCKTXN="blocktxn";
+const char *WTXIDRELAY="wtxidrelay";
 } // namespace NetMsgType
 
 /** All known message types. Keep this in the same order as the list of
@@ -71,6 +72,7 @@ const static std::string allNetMessageTypes[] = {
     NetMsgType::CMPCTBLOCK,
     NetMsgType::GETBLOCKTXN,
     NetMsgType::BLOCKTXN,
+    NetMsgType::WTXIDRELAY,
 };
 const static std::vector<std::string> allNetMessageTypesVec(allNetMessageTypes, allNetMessageTypes+ARRAYLEN(allNetMessageTypes));
 
@@ -183,6 +185,8 @@ std::string CInv::GetCommand() const
     switch (masked)
     {
     case MSG_TX:             return cmd.append(NetMsgType::TX);
+    // WTX is not a message type, just an inv type
+    case MSG_WTX:            return cmd.append("wtx");
     case MSG_BLOCK:          return cmd.append(NetMsgType::BLOCK);
     case MSG_FILTERED_BLOCK: return cmd.append(NetMsgType::MERKLEBLOCK);
     case MSG_CMPCT_BLOCK:    return cmd.append(NetMsgType::CMPCTBLOCK);
diff --git a/src/protocol.h b/src/protocol.h
index 6639ae2aac..a27ca56495 100644
--- a/src/protocol.h
+++ b/src/protocol.h
@@ -234,6 +234,12 @@ extern const char *GETBLOCKTXN;
  * @since protocol version 70014 as described by BIP 152
  */
 extern const char *BLOCKTXN;
+/**
+ * Indicates that a node prefers to relay transactions via wtxid, rather than
+ * txid.
+ * @since protocol version 70016 as described by BIP 339.
+ */
+extern const char *WTXIDRELAY;
 };
 
 /* Get a vector of all valid message types (see above) */
@@ -362,12 +368,12 @@ const uint32_t MSG_TYPE_MASK    = 0xffffffff >> 2;
  * These numbers are defined by the protocol. When adding a new value, be sure
  * to mention it in the respective BIP.
  */
-enum GetDataMsg
-{
+enum GetDataMsg : uint32_t {
     UNDEFINED = 0,
     MSG_TX = 1,
     MSG_BLOCK = 2,
-    // The following can only occur in getdata. Invs always use TX or BLOCK.
+    MSG_WTX = 5,                                      //!< Defined in BIP 339
+    // The following can only occur in getdata. Invs always use TX/WTX or BLOCK.
     MSG_FILTERED_BLOCK = 3,  //!< Defined in BIP37
     MSG_CMPCT_BLOCK = 4,     //!< Defined in BIP152
     MSG_WITNESS_BLOCK = MSG_BLOCK | MSG_WITNESS_FLAG, //!< Defined in BIP144
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index c14417a847..8de225ba19 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -724,12 +724,12 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
     assert(innerUsage == cachedInnerUsage);
 }
 
-bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb)
+bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid)
 {
     LOCK(cs);
-    indexed_transaction_set::const_iterator i = mapTx.find(hasha);
+    indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha);
     if (i == mapTx.end()) return false;
-    indexed_transaction_set::const_iterator j = mapTx.find(hashb);
+    indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb);
     if (j == mapTx.end()) return true;
     uint64_t counta = i->GetCountWithAncestors();
     uint64_t countb = j->GetCountWithAncestors();
@@ -809,10 +809,10 @@ CTransactionRef CTxMemPool::get(const uint256& hash) const
     return i->GetSharedTx();
 }
 
-TxMempoolInfo CTxMemPool::info(const uint256& hash) const
+TxMempoolInfo CTxMemPool::info(const uint256& hash, bool wtxid) const
 {
     LOCK(cs);
-    indexed_transaction_set::const_iterator i = mapTx.find(hash);
+    indexed_transaction_set::const_iterator i = (wtxid ? get_iter_from_wtxid(hash) : mapTx.find(hash));
     if (i == mapTx.end())
         return TxMempoolInfo();
     return GetInfo(i);
@@ -915,8 +915,8 @@ bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
 
 size_t CTxMemPool::DynamicMemoryUsage() const {
     LOCK(cs);
-    // Estimate the overhead of mapTx to be 12 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
-    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 12 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
+    // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
+    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
 }
 
 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
diff --git a/src/txmempool.h b/src/txmempool.h
index 3dae0a04c7..40986f13a3 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -198,6 +198,22 @@ struct mempoolentry_txid
     }
 };
 
+// extracts a transaction witness-hash from CTxMemPoolEntry or CTransactionRef
+struct mempoolentry_wtxid
+{
+    typedef uint256 result_type;
+    result_type operator() (const CTxMemPoolEntry &entry) const
+    {
+        return entry.GetTx().GetWitnessHash();
+    }
+
+    result_type operator() (const CTransactionRef& tx) const
+    {
+        return tx->GetWitnessHash();
+    }
+};
+
+
 /** \class CompareTxMemPoolEntryByDescendantScore
  *
  *  Sort an entry by max(score/size of entry's tx, score/size with all descendants).
@@ -318,6 +334,7 @@ public:
 struct descendant_score {};
 struct entry_time {};
 struct ancestor_score {};
+struct index_by_wtxid {};
 
 class CBlockPolicyEstimator;
 
@@ -383,8 +400,9 @@ public:
  *
  * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
  *
- * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
- * - transaction hash
+ * mapTx is a boost::multi_index that sorts the mempool on 5 criteria:
+ * - transaction hash (txid)
+ * - witness-transaction hash (wtxid)
  * - descendant feerate [we use max(feerate of tx, feerate of tx with all descendants)]
  * - time in mempool
  * - ancestor feerate [we use min(feerate of tx, feerate of tx with all unconfirmed ancestors)]
@@ -469,6 +487,12 @@ public:
         boost::multi_index::indexed_by<
             // sorted by txid
             boost::multi_index::hashed_unique<mempoolentry_txid, SaltedTxidHasher>,
+            // sorted by wtxid
+            boost::multi_index::hashed_unique<
+                boost::multi_index::tag<index_by_wtxid>,
+                mempoolentry_wtxid,
+                SaltedTxidHasher
+            >,
             // sorted by fee rate
             boost::multi_index::ordered_non_unique<
                 boost::multi_index::tag<descendant_score>,
@@ -583,7 +607,7 @@ public:
 
     void clear();
     void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs); //lock free
-    bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb);
+    bool CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid=false);
     void queryHashes(std::vector<uint256>& vtxid) const;
     bool isSpent(const COutPoint& outpoint) const;
     unsigned int GetTransactionsUpdated() const;
@@ -686,14 +710,22 @@ public:
         return totalTxSize;
     }
 
-    bool exists(const uint256& hash) const
+    bool exists(const uint256& hash, bool wtxid=false) const
     {
         LOCK(cs);
+        if (wtxid) {
+            return (mapTx.get<index_by_wtxid>().count(hash) != 0);
+        }
         return (mapTx.count(hash) != 0);
     }
 
     CTransactionRef get(const uint256& hash) const;
-    TxMempoolInfo info(const uint256& hash) const;
+    txiter get_iter_from_wtxid(const uint256& wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
+    {
+        AssertLockHeld(cs);
+        return mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid));
+    }
+    TxMempoolInfo info(const uint256& hash, bool wtxid=false) const;
     std::vector<TxMempoolInfo> infoAll() const;
 
     size_t DynamicMemoryUsage() const;
diff --git a/src/validation.cpp b/src/validation.cpp
index 5a98b2cb92..a4adc81b5a 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -916,7 +916,7 @@ bool MemPoolAccept::PolicyScriptChecks(ATMPArgs& args, Workspace& ws, Precompute
         if (!tx.HasWitness() && CheckInputScripts(tx, state_dummy, m_view, scriptVerifyFlags & ~(SCRIPT_VERIFY_WITNESS | SCRIPT_VERIFY_CLEANSTACK), true, false, txdata) &&
                 !CheckInputScripts(tx, state_dummy, m_view, scriptVerifyFlags & ~SCRIPT_VERIFY_CLEANSTACK, true, false, txdata)) {
             // Only the witness is missing, so the transaction itself may be fine.
-            state.Invalid(TxValidationResult::TX_WITNESS_MUTATED,
+            state.Invalid(TxValidationResult::TX_WITNESS_STRIPPED,
                     state.GetRejectReason(), state.GetDebugMessage());
         }
         return false; // state filled in by CheckInputScripts
diff --git a/src/version.h b/src/version.h
index d932b512d4..e55871fc41 100644
--- a/src/version.h
+++ b/src/version.h
@@ -9,7 +9,7 @@
  * network protocol versioning
  */
 
-static const int PROTOCOL_VERSION = 70015;
+static const int PROTOCOL_VERSION = 70016;
 
 //! initial proto version, to be increased after version/verack negotiation
 static const int INIT_PROTO_VERSION = 209;
@@ -42,4 +42,7 @@ static const int SHORT_IDS_BLOCKS_VERSION = 70014;
 //! not banning for invalid compact blocks starts with this version
 static const int INVALID_CB_NO_BAN_VERSION = 70015;
 
+//! "wtxidrelay" command for wtxid-based relay starts with this version
+static const int WTXID_RELAY_VERSION = 70016;
+
 #endif // BITCOIN_VERSION_H
diff --git a/test/functional/mempool_packages.py b/test/functional/mempool_packages.py
index a07dad18d6..5a1a73d16e 100755
--- a/test/functional/mempool_packages.py
+++ b/test/functional/mempool_packages.py
@@ -67,10 +67,15 @@ class MempoolPackagesTest(BitcoinTestFramework):
         fee = Decimal("0.0001")
         # MAX_ANCESTORS transactions off a confirmed tx should be fine
         chain = []
+        witness_chain = []
         for i in range(MAX_ANCESTORS):
             (txid, sent_value) = self.chain_transaction(self.nodes[0], txid, 0, value, fee, 1)
             value = sent_value
             chain.append(txid)
+            # We need the wtxids to check P2P announcements
+            fulltx = self.nodes[0].getrawtransaction(txid)
+            witnesstx = self.nodes[0].decoderawtransaction(fulltx, True)
+            witness_chain.append(witnesstx['hash'])
 
         # Check mempool has MAX_ANCESTORS transactions in it, and descendant and ancestor
         # count and fees should look correct
diff --git a/test/functional/p2p_blocksonly.py b/test/functional/p2p_blocksonly.py
index 3258a38e3c..1069702da7 100755
--- a/test/functional/p2p_blocksonly.py
+++ b/test/functional/p2p_blocksonly.py
@@ -52,7 +52,7 @@ class P2PBlocksOnly(BitcoinTestFramework):
         self.log.info('Check that txs from rpc are not rejected and relayed to other peers')
         assert_equal(self.nodes[0].getpeerinfo()[0]['relaytxes'], True)
         txid = self.nodes[0].testmempoolaccept([sigtx])[0]['txid']
-        with self.nodes[0].assert_debug_log(['received getdata for: tx {} peer=1'.format(txid)]):
+        with self.nodes[0].assert_debug_log(['received getdata for: wtx {} peer=1'.format(txid)]):
             self.nodes[0].sendrawtransaction(sigtx)
             self.nodes[0].p2p.wait_for_tx(txid)
             assert_equal(self.nodes[0].getmempoolinfo()['size'], 1)
diff --git a/test/functional/p2p_feefilter.py b/test/functional/p2p_feefilter.py
index 4f242bd94a..f77937d726 100755
--- a/test/functional/p2p_feefilter.py
+++ b/test/functional/p2p_feefilter.py
@@ -7,7 +7,7 @@
 from decimal import Decimal
 import time
 
-from test_framework.messages import msg_feefilter
+from test_framework.messages import MSG_TX, MSG_WTX, msg_feefilter
 from test_framework.mininode import mininode_lock, P2PInterface
 from test_framework.test_framework import BitcoinTestFramework
 
@@ -31,7 +31,7 @@ class TestP2PConn(P2PInterface):
 
     def on_inv(self, message):
         for i in message.inv:
-            if (i.type == 1):
+            if (i.type == MSG_TX) or (i.type == MSG_WTX):
                 self.txinvs.append(hashToHex(i.hash))
 
     def clear_invs(self):
diff --git a/test/functional/p2p_segwit.py b/test/functional/p2p_segwit.py
index a7cfefc485..40925ae8c9 100755
--- a/test/functional/p2p_segwit.py
+++ b/test/functional/p2p_segwit.py
@@ -22,7 +22,9 @@ from test_framework.messages import (
     CTxOut,
     CTxWitness,
     MAX_BLOCK_BASE_SIZE,
+    MSG_TX,
     MSG_WITNESS_FLAG,
+    MSG_WTX,
     NODE_NETWORK,
     NODE_WITNESS,
     msg_no_witness_block,
@@ -32,6 +34,7 @@ from test_framework.messages import (
     msg_tx,
     msg_block,
     msg_no_witness_tx,
+    msg_verack,
     ser_uint256,
     ser_vector,
     sha256,
@@ -79,6 +82,7 @@ from test_framework.util import (
     softfork_active,
     hex_str_to_bytes,
     assert_raises_rpc_error,
+    wait_until,
 )
 
 # The versionbit bit used to signal activation of SegWit
@@ -141,23 +145,42 @@ def test_witness_block(node, p2p, block, accepted, with_witness=True, reason=Non
 
 
 class TestP2PConn(P2PInterface):
-    def __init__(self):
+    def __init__(self, wtxidrelay=False):
         super().__init__()
         self.getdataset = set()
+        self.last_wtxidrelay = []
+        self.lastgetdata = []
+        self.wtxidrelay = wtxidrelay
 
     # Avoid sending out msg_getdata in the mininode thread as a reply to invs.
     # They are not needed and would only lead to races because we send msg_getdata out in the test thread
     def on_inv(self, message):
         pass
 
+    def on_version(self, message):
+        if self.wtxidrelay:
+            super().on_version(message)
+        else:
+            self.send_message(msg_verack())
+            self.nServices = message.nServices
+
     def on_getdata(self, message):
+        self.lastgetdata = message.inv
         for inv in message.inv:
             self.getdataset.add(inv.hash)
 
-    def announce_tx_and_wait_for_getdata(self, tx, timeout=60, success=True):
+    def on_wtxidrelay(self, message):
+        self.last_wtxidrelay.append(message)
+
+    def announce_tx_and_wait_for_getdata(self, tx, timeout=60, success=True, use_wtxid=False):
         with mininode_lock:
             self.last_message.pop("getdata", None)
-        self.send_message(msg_inv(inv=[CInv(1, tx.sha256)]))
+        if use_wtxid:
+            wtxid = tx.calc_sha256(True)
+            self.send_message(msg_inv(inv=[CInv(MSG_WTX, wtxid)]))
+        else:
+            self.send_message(msg_inv(inv=[CInv(MSG_TX, tx.sha256)]))
+
         if success:
             self.wait_for_getdata(timeout)
         else:
@@ -275,6 +298,7 @@ class SegWitTest(BitcoinTestFramework):
         self.test_upgrade_after_activation()
         self.test_witness_sigops()
         self.test_superfluous_witness()
+        self.test_wtxid_relay()
 
     # Individual tests
 
@@ -1268,7 +1292,6 @@ class SegWitTest(BitcoinTestFramework):
         test_transaction_acceptance(self.nodes[0], self.test_node, tx, with_witness=True, accepted=False)
 
         # Verify that removing the witness succeeds.
-        self.test_node.announce_tx_and_wait_for_getdata(tx)
         test_transaction_acceptance(self.nodes[0], self.test_node, tx, with_witness=False, accepted=True)
 
         # Now try to add extra witness data to a valid witness tx.
@@ -1295,8 +1318,6 @@ class SegWitTest(BitcoinTestFramework):
         # Node will not be blinded to the transaction
         self.std_node.announce_tx_and_wait_for_getdata(tx3)
         test_transaction_acceptance(self.nodes[1], self.std_node, tx3, True, False, 'tx-size')
-        self.std_node.announce_tx_and_wait_for_getdata(tx3)
-        test_transaction_acceptance(self.nodes[1], self.std_node, tx3, True, False, 'tx-size')
 
         # Remove witness stuffing, instead add extra witness push on stack
         tx3.vout[0] = CTxOut(tx2.vout[0].nValue - 1000, CScript([OP_TRUE, OP_DROP] * 15 + [OP_TRUE]))
@@ -2023,6 +2044,11 @@ class SegWitTest(BitcoinTestFramework):
 
         # TODO: test p2sh sigop counting
 
+        # Cleanup and prep for next test
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+    @subtest  # type: ignore
     def test_superfluous_witness(self):
         # Serialization of tx that puts witness flag to 3 always
         def serialize_with_bogus_witness(tx):
@@ -2066,6 +2092,67 @@ class SegWitTest(BitcoinTestFramework):
         with self.nodes[0].assert_debug_log(['Unknown transaction optional data']):
             self.nodes[0].p2p.send_and_ping(msg_bogus_tx(tx))
 
+    @subtest  # type: ignore
+    def test_wtxid_relay(self):
+        # Use brand new nodes to avoid contamination from earlier tests
+        self.wtx_node = self.nodes[0].add_p2p_connection(TestP2PConn(wtxidrelay=True), services=NODE_NETWORK | NODE_WITNESS)
+        self.tx_node = self.nodes[0].add_p2p_connection(TestP2PConn(wtxidrelay=False), services=NODE_NETWORK | NODE_WITNESS)
+
+        # Check wtxidrelay feature negotiation message through connecting a new peer
+        def received_wtxidrelay():
+            return (len(self.wtx_node.last_wtxidrelay) > 0)
+        wait_until(received_wtxidrelay, timeout=60, lock=mininode_lock)
+
+        # Create a Segwit output from the latest UTXO
+        # and announce it to the network
+        witness_program = CScript([OP_TRUE])
+        witness_hash = sha256(witness_program)
+        script_pubkey = CScript([OP_0, witness_hash])
+
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue - 1000, script_pubkey))
+        tx.rehash()
+
+        # Create a Segwit transaction
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue - 1000, script_pubkey))
+        tx2.wit.vtxinwit.append(CTxInWitness())
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [witness_program]
+        tx2.rehash()
+
+        # Announce Segwit transaction with wtxid
+        # and wait for getdata
+        self.wtx_node.announce_tx_and_wait_for_getdata(tx2, use_wtxid=True)
+        with mininode_lock:
+            lgd = self.wtx_node.lastgetdata[:]
+        assert_equal(lgd, [CInv(MSG_WTX, tx2.calc_sha256(True))])
+
+        # Announce Segwit transaction from non wtxidrelay peer
+        # and wait for getdata
+        self.tx_node.announce_tx_and_wait_for_getdata(tx2, use_wtxid=False)
+        with mininode_lock:
+            lgd = self.tx_node.lastgetdata[:]
+        assert_equal(lgd, [CInv(MSG_TX | MSG_WITNESS_FLAG, tx2.sha256)])
+
+        # Send tx2 through; it's an orphan so won't be accepted
+        with mininode_lock:
+            self.tx_node.last_message.pop("getdata", None)
+        test_transaction_acceptance(self.nodes[0], self.tx_node, tx2, with_witness=True, accepted=False)
+
+        # Expect a request for parent (tx) due to use of non-WTX peer
+        self.tx_node.wait_for_getdata(60)
+        with mininode_lock:
+            lgd = self.tx_node.lastgetdata[:]
+        assert_equal(lgd, [CInv(MSG_TX | MSG_WITNESS_FLAG, tx.sha256)])
+
+        # Send tx through
+        test_transaction_acceptance(self.nodes[0], self.tx_node, tx, with_witness=False, accepted=True)
+
+        # Check tx2 is there now
+        assert_equal(tx2.hash in self.nodes[0].getrawmempool(), True)
+
 
 if __name__ == '__main__':
     SegWitTest().main()
diff --git a/test/functional/p2p_tx_download.py b/test/functional/p2p_tx_download.py
index b56dc994e7..7e7df1442e 100755
--- a/test/functional/p2p_tx_download.py
+++ b/test/functional/p2p_tx_download.py
@@ -12,6 +12,7 @@ from test_framework.messages import (
     FromHex,
     MSG_TX,
     MSG_TYPE_MASK,
+    MSG_WTX,
     msg_inv,
     msg_notfound,
 )
@@ -36,7 +37,7 @@ class TestP2PConn(P2PInterface):
 
     def on_getdata(self, message):
         for i in message.inv:
-            if i.type & MSG_TYPE_MASK == MSG_TX:
+            if i.type & MSG_TYPE_MASK == MSG_TX or i.type & MSG_TYPE_MASK == MSG_WTX:
                 self.tx_getdata_count += 1
 
 
@@ -44,12 +45,13 @@ class TestP2PConn(P2PInterface):
 GETDATA_TX_INTERVAL = 60  # seconds
 MAX_GETDATA_RANDOM_DELAY = 2  # seconds
 INBOUND_PEER_TX_DELAY = 2  # seconds
+TXID_RELAY_DELAY = 2 # seconds
 MAX_GETDATA_IN_FLIGHT = 100
 TX_EXPIRY_INTERVAL = GETDATA_TX_INTERVAL * 10
 
 # Python test constants
 NUM_INBOUND = 10
-MAX_GETDATA_INBOUND_WAIT = GETDATA_TX_INTERVAL + MAX_GETDATA_RANDOM_DELAY + INBOUND_PEER_TX_DELAY
+MAX_GETDATA_INBOUND_WAIT = GETDATA_TX_INTERVAL + MAX_GETDATA_RANDOM_DELAY + INBOUND_PEER_TX_DELAY + TXID_RELAY_DELAY
 
 
 class TxDownloadTest(BitcoinTestFramework):
@@ -63,7 +65,7 @@ class TxDownloadTest(BitcoinTestFramework):
         txid = 0xdeadbeef
 
         self.log.info("Announce the txid from each incoming peer to node 0")
-        msg = msg_inv([CInv(t=1, h=txid)])
+        msg = msg_inv([CInv(t=MSG_WTX, h=txid)])
         for p in self.nodes[0].p2ps:
             p.send_and_ping(msg)
 
@@ -135,13 +137,13 @@ class TxDownloadTest(BitcoinTestFramework):
         with mininode_lock:
             p.tx_getdata_count = 0
 
-        p.send_message(msg_inv([CInv(t=1, h=i) for i in txids]))
+        p.send_message(msg_inv([CInv(t=MSG_WTX, h=i) for i in txids]))
         wait_until(lambda: p.tx_getdata_count >= MAX_GETDATA_IN_FLIGHT, lock=mininode_lock)
         with mininode_lock:
             assert_equal(p.tx_getdata_count, MAX_GETDATA_IN_FLIGHT)
 
         self.log.info("Now check that if we send a NOTFOUND for a transaction, we'll get one more request")
-        p.send_message(msg_notfound(vec=[CInv(t=1, h=txids[0])]))
+        p.send_message(msg_notfound(vec=[CInv(t=MSG_WTX, h=txids[0])]))
         wait_until(lambda: p.tx_getdata_count >= MAX_GETDATA_IN_FLIGHT + 1, timeout=10, lock=mininode_lock)
         with mininode_lock:
             assert_equal(p.tx_getdata_count, MAX_GETDATA_IN_FLIGHT + 1)
diff --git a/test/functional/test_framework/messages.py b/test/functional/test_framework/messages.py
index 5f8fcc6fd8..c8c38e017a 100755
--- a/test/functional/test_framework/messages.py
+++ b/test/functional/test_framework/messages.py
@@ -31,7 +31,7 @@ from test_framework.siphash import siphash256
 from test_framework.util import hex_str_to_bytes, assert_equal
 
 MIN_VERSION_SUPPORTED = 60001
-MY_VERSION = 70014  # past bip-31 for ping/pong
+MY_VERSION = 70016  # past wtxid relay
 MY_SUBVERSION = b"/python-mininode-tester:0.0.3/"
 MY_RELAY = 1 # from version 70001 onwards, fRelay should be appended to version messages (BIP37)
 
@@ -52,6 +52,7 @@ NODE_NETWORK_LIMITED = (1 << 10)
 MSG_TX = 1
 MSG_BLOCK = 2
 MSG_FILTERED_BLOCK = 3
+MSG_WTX = 5
 MSG_WITNESS_FLAG = 1 << 30
 MSG_TYPE_MASK = 0xffffffff >> 2
 
@@ -231,7 +232,8 @@ class CInv:
         MSG_TX | MSG_WITNESS_FLAG: "WitnessTx",
         MSG_BLOCK | MSG_WITNESS_FLAG: "WitnessBlock",
         MSG_FILTERED_BLOCK: "filtered Block",
-        4: "CompactBlock"
+        4: "CompactBlock",
+        5: "WTX",
     }
 
     def __init__(self, t=0, h=0):
@@ -252,6 +254,9 @@ class CInv:
         return "CInv(type=%s hash=%064x)" \
             % (self.typemap[self.type], self.hash)
 
+    def __eq__(self, other):
+        return isinstance(other, CInv) and self.hash == other.hash and self.type == other.type
+
 
 class CBlockLocator:
     __slots__ = ("nVersion", "vHave")
@@ -1113,6 +1118,22 @@ class msg_tx:
     def __repr__(self):
         return "msg_tx(tx=%s)" % (repr(self.tx))
 
+class msg_wtxidrelay:
+    __slots__ = ()
+    command = b"wtxidrelay"
+
+    def __init__(self):
+        pass
+
+    def deserialize(self, f):
+        pass
+
+    def serialize(self):
+        return b""
+
+    def __repr__(self):
+        return "msg_wtxidrelay()"
+
 
 class msg_no_witness_tx(msg_tx):
     __slots__ = ()
diff --git a/test/functional/test_framework/mininode.py b/test/functional/test_framework/mininode.py
index ad330f2a93..383b340118 100755
--- a/test/functional/test_framework/mininode.py
+++ b/test/functional/test_framework/mininode.py
@@ -52,6 +52,7 @@ from test_framework.messages import (
     MSG_TYPE_MASK,
     msg_verack,
     msg_version,
+    msg_wtxidrelay,
     NODE_NETWORK,
     NODE_WITNESS,
     sha256,
@@ -86,6 +87,7 @@ MESSAGEMAP = {
     b"tx": msg_tx,
     b"verack": msg_verack,
     b"version": msg_version,
+    b"wtxidrelay": msg_wtxidrelay,
 }
 
 MAGIC_BYTES = {
@@ -343,6 +345,7 @@ class P2PInterface(P2PConnection):
     def on_sendcmpct(self, message): pass
     def on_sendheaders(self, message): pass
     def on_tx(self, message): pass
+    def on_wtxidrelay(self, message): pass
 
     def on_inv(self, message):
         want = msg_getdata()
@@ -360,6 +363,8 @@ class P2PInterface(P2PConnection):
 
     def on_version(self, message):
         assert message.nVersion >= MIN_VERSION_SUPPORTED, "Version {} received. Test framework only supports versions greater than {}".format(message.nVersion, MIN_VERSION_SUPPORTED)
+        if message.nVersion >= 70016:
+            self.send_message(msg_wtxidrelay())
         self.send_message(msg_verack())
         self.nServices = message.nServices
 
diff --git a/test/functional/wallet_resendwallettransactions.py b/test/functional/wallet_resendwallettransactions.py
index d122e3db52..fe670ddaee 100755
--- a/test/functional/wallet_resendwallettransactions.py
+++ b/test/functional/wallet_resendwallettransactions.py
@@ -7,7 +7,11 @@ from collections import defaultdict
 import time
 
 from test_framework.blocktools import create_block, create_coinbase
-from test_framework.messages import ToHex
+from test_framework.messages import (
+    MSG_TX,
+    MSG_WTX,
+    ToHex,
+)
 from test_framework.mininode import P2PInterface, mininode_lock
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import assert_equal, wait_until
@@ -21,7 +25,7 @@ class P2PStoreTxInvs(P2PInterface):
     def on_inv(self, message):
         # Store how many times invs have been received for each tx.
         for i in message.inv:
-            if i.type == 1:
+            if i.type == MSG_TX or i.type == MSG_WTX:
                 # save txid
                 self.tx_invs_received[i.hash] += 1
 
@@ -39,7 +43,8 @@ class ResendWalletTransactionsTest(BitcoinTestFramework):
         node.add_p2p_connection(P2PStoreTxInvs())
 
         self.log.info("Create a new transaction and wait until it's broadcast")
-        txid = int(node.sendtoaddress(node.getnewaddress(), 1), 16)
+        txid = node.sendtoaddress(node.getnewaddress(), 1)
+        wtxid = int(node.getrawtransaction(txid, 1)['hash'], 16)
 
         # Wallet rebroadcast is first scheduled 1 sec after startup (see
         # nNextResend in ResendWalletTransactions()). Sleep for just over a
@@ -48,7 +53,7 @@ class ResendWalletTransactionsTest(BitcoinTestFramework):
         time.sleep(1.1)
 
         # Can take a few seconds due to transaction trickling
-        wait_until(lambda: node.p2p.tx_invs_received[txid] >= 1, lock=mininode_lock)
+        wait_until(lambda: node.p2p.tx_invs_received[wtxid] >= 1, lock=mininode_lock)
 
         # Add a second peer since txs aren't rebroadcast to the same peer (see filterInventoryKnown)
         node.add_p2p_connection(P2PStoreTxInvs())
@@ -67,13 +72,13 @@ class ResendWalletTransactionsTest(BitcoinTestFramework):
         # Transaction should not be rebroadcast
         node.syncwithvalidationinterfacequeue()
         node.p2ps[1].sync_with_ping()
-        assert_equal(node.p2ps[1].tx_invs_received[txid], 0)
+        assert_equal(node.p2ps[1].tx_invs_received[wtxid], 0)
 
         self.log.info("Transaction should be rebroadcast after 30 minutes")
         # Use mocktime and give an extra 5 minutes to be sure.
         rebroadcast_time = int(time.time()) + 41 * 60
         node.setmocktime(rebroadcast_time)
-        wait_until(lambda: node.p2ps[1].tx_invs_received[txid] >= 1, lock=mininode_lock)
+        wait_until(lambda: node.p2ps[1].tx_invs_received[wtxid] >= 1, lock=mininode_lock)
 
 
 if __name__ == '__main__':