diff --git a/src/net_processing.h b/src/net_processing.h
--- a/src/net_processing.h
+++ b/src/net_processing.h
@@ -207,7 +207,7 @@
     BanMan *const m_banman;
     ChainstateManager &m_chainman;
     CTxMemPool &m_mempool;
-    TxRequestTracker m_txrequest GUARDED_BY(::cs_main);
+    TxRequestTracker<TxId> m_txrequest GUARDED_BY(::cs_main);
 
     //! Next time to check for stale tip
     int64_t m_stale_tip_check_time;
diff --git a/src/test/fuzz/txrequest.cpp b/src/test/fuzz/txrequest.cpp
--- a/src/test/fuzz/txrequest.cpp
+++ b/src/test/fuzz/txrequest.cpp
@@ -70,7 +70,7 @@
  */
 class Tester {
     //! TxRequestTracker object being tested.
-    TxRequestTracker m_tracker;
+    TxRequestTracker<TxId> m_tracker;
 
     //! States for txid/peer combinations in the naive data structure.
     enum class State {
diff --git a/src/test/txrequest_tests.cpp b/src/test/txrequest_tests.cpp
--- a/src/test/txrequest_tests.cpp
+++ b/src/test/txrequest_tests.cpp
@@ -32,7 +32,7 @@
  */
 struct Runner {
     /** The TxRequestTracker being tested. */
-    TxRequestTracker txrequest;
+    TxRequestTracker<TxId> txrequest;
 
     /** List of actions to be executed (in order of increasing timestamp). */
     std::vector<Action> actions;
diff --git a/src/txrequest.h b/src/txrequest.h
--- a/src/txrequest.h
+++ b/src/txrequest.h
@@ -6,12 +6,11 @@
 #define BITCOIN_TXREQUEST_H
 
 #include <net.h> // For NodeId
-#include <primitives/transaction.h>
 
 #include <chrono>
-#include <vector>
-
 #include <cstdint>
+#include <functional>
+#include <vector>
 
 /**
  * Data structure to keep track of, and schedule, transaction downloads from
@@ -120,7 +119,7 @@
 
 // Avoid littering this header file with implementation details.
 class Impl {
-    friend class TxRequestTracker;
+    template <class InvId> friend class TxRequestTracker;
 
     // The base class is responsible for building the child implementation.
     // This is a hack that allows for hiding the concrete implementation details
@@ -157,7 +156,14 @@
     virtual ~Impl() = default;
 };
 
-class TxRequestTracker {
+template <class InvId> class TxRequestTracker {
+    /*
+     * Only uint256-based InvId types are supported for now.
+     * FIXME: use a template constraint when C++20 is available.
+     */
+    static_assert(std::is_base_of<uint256, InvId>::value,
+                  "InvRequestTracker inv id type should be uint256 or derived");
+
     const std::unique_ptr<Impl> m_impl;
 
 public:
@@ -191,7 +197,7 @@
      * Does nothing if one already exists for that (txid, peer) combination
      * (whether it's CANDIDATE, REQUESTED, or COMPLETED).
      */
-    void ReceivedInv(NodeId peer, const TxId &txid, bool preferred,
+    void ReceivedInv(NodeId peer, const InvId &txid, bool preferred,
                      std::chrono::microseconds reqtime);
 
     /**
@@ -208,7 +214,7 @@
      * should ensure that new announcements for the same txid will not trigger
      * new ReceivedInv calls, at least in the short term after this call.
      */
-    void ForgetTxId(const TxId &txid);
+    void ForgetTxId(const InvId &txid);
 
     /**
      * Find the txids to request now from peer.
@@ -232,9 +238,9 @@
      *    peer, and end up being requested from them, the requests will happen
      *    in announcement order.
      */
-    std::vector<TxId>
+    std::vector<InvId>
     GetRequestable(NodeId peer, std::chrono::microseconds now,
-                   std::vector<std::pair<NodeId, TxId>> *expired = nullptr);
+                   std::vector<std::pair<NodeId, InvId>> *expired = nullptr);
 
     /**
      * Marks a transaction as requested, with a specified expiry.
@@ -247,7 +253,7 @@
      *    never advise doing so). In this case it is converted to COMPLETED, as
      *    we're no longer waiting for a response to it.
      */
-    void RequestedTx(NodeId peer, const TxId &txid,
+    void RequestedTx(NodeId peer, const InvId &txid,
                      std::chrono::microseconds expiry);
 
     /**
@@ -258,7 +264,7 @@
      * a peer. When the transaction is not needed entirely anymore, ForgetTxId
      * should be called instead of, or in addition to, this call.
      */
-    void ReceivedResponse(NodeId peer, const TxId &txid);
+    void ReceivedResponse(NodeId peer, const InvId &txid);
 
     // The operations below inspect the data structure.
 
@@ -281,7 +287,7 @@
     size_t Size() const;
 
     /** Access to the internal priority computation (testing only) */
-    uint64_t ComputePriority(const TxId &txid, NodeId peer,
+    uint64_t ComputePriority(const InvId &txid, NodeId peer,
                              bool preferred) const;
 
     /** Run internal consistency check (testing only). */
@@ -296,4 +302,88 @@
     void PostGetRequestableSanityCheck(std::chrono::microseconds now) const;
 };
 
+template <class InvId>
+TxRequestTracker<InvId>::TxRequestTracker(bool deterministic)
+    : m_impl{Impl::BuildImpl(deterministic)} {}
+
+template <class InvId> TxRequestTracker<InvId>::~TxRequestTracker() = default;
+
+template <class InvId>
+void TxRequestTracker<InvId>::ForgetTxId(const InvId &txid) {
+    m_impl->ForgetTxId(txid);
+}
+template <class InvId>
+void TxRequestTracker<InvId>::DisconnectedPeer(NodeId peer) {
+    m_impl->DisconnectedPeer(peer);
+}
+template <class InvId>
+size_t TxRequestTracker<InvId>::CountInFlight(NodeId peer) const {
+    return m_impl->CountInFlight(peer);
+}
+template <class InvId>
+size_t TxRequestTracker<InvId>::CountCandidates(NodeId peer) const {
+    return m_impl->CountCandidates(peer);
+}
+template <class InvId>
+size_t TxRequestTracker<InvId>::Count(NodeId peer) const {
+    return m_impl->Count(peer);
+}
+template <class InvId> size_t TxRequestTracker<InvId>::Size() const {
+    return m_impl->Size();
+}
+template <class InvId> void TxRequestTracker<InvId>::SanityCheck() const {
+    m_impl->SanityCheck();
+}
+
+template <class InvId>
+void TxRequestTracker<InvId>::PostGetRequestableSanityCheck(
+    std::chrono::microseconds now) const {
+    m_impl->PostGetRequestableSanityCheck(now);
+}
+
+template <class InvId>
+void TxRequestTracker<InvId>::ReceivedInv(NodeId peer, const InvId &txid,
+                                          bool preferred,
+                                          std::chrono::microseconds reqtime) {
+    m_impl->ReceivedInv(peer, txid, preferred, reqtime);
+}
+
+template <class InvId>
+void TxRequestTracker<InvId>::RequestedTx(NodeId peer, const InvId &txid,
+                                          std::chrono::microseconds expiry) {
+    m_impl->RequestedTx(peer, txid, expiry);
+}
+
+template <class InvId>
+void TxRequestTracker<InvId>::ReceivedResponse(NodeId peer, const InvId &txid) {
+    m_impl->ReceivedResponse(peer, txid);
+}
+
+template <class InvId>
+std::vector<InvId> TxRequestTracker<InvId>::GetRequestable(
+    NodeId peer, std::chrono::microseconds now,
+    std::vector<std::pair<NodeId, InvId>> *expired) {
+    Impl::clearExpiredFun clearExpired = [expired]() {
+        if (expired) {
+            expired->clear();
+        }
+    };
+    Impl::emplaceExpiredFun emplaceExpired = [expired](const NodeId &nodeid,
+                                                       const uint256 &txid) {
+        if (expired) {
+            expired->emplace_back(nodeid, InvId(txid));
+        }
+    };
+    std::vector<uint256> hashes =
+        m_impl->GetRequestable(peer, now, clearExpired, emplaceExpired);
+    return std::vector<InvId>(hashes.begin(), hashes.end());
+}
+
+template <class InvId>
+uint64_t TxRequestTracker<InvId>::ComputePriority(const InvId &txid,
+                                                  NodeId peer,
+                                                  bool preferred) const {
+    return m_impl->ComputePriority(txid, peer, preferred);
+}
+
 #endif // BITCOIN_TXREQUEST_H
diff --git a/src/txrequest.cpp b/src/txrequest.cpp
--- a/src/txrequest.cpp
+++ b/src/txrequest.cpp
@@ -6,7 +6,6 @@
 
 #include <crypto/siphash.h>
 #include <net.h>
-#include <primitives/transaction.h>
 #include <random.h>
 
 #include <boost/multi_index/ordered_index.hpp>
@@ -14,7 +13,6 @@
 
 #include <cassert>
 #include <chrono>
-#include <functional>
 #include <unordered_map>
 #include <utility>
 
@@ -860,74 +858,3 @@
 std::unique_ptr<Impl> Impl::BuildImpl(bool deterministic) {
     return std::unique_ptr<Impl>(new ImplConcrete(deterministic));
 }
-
-TxRequestTracker::TxRequestTracker(bool deterministic)
-    : m_impl{Impl::BuildImpl(deterministic)} {}
-
-TxRequestTracker::~TxRequestTracker() = default;
-
-void TxRequestTracker::ForgetTxId(const TxId &txid) {
-    m_impl->ForgetTxId(txid);
-}
-void TxRequestTracker::DisconnectedPeer(NodeId peer) {
-    m_impl->DisconnectedPeer(peer);
-}
-size_t TxRequestTracker::CountInFlight(NodeId peer) const {
-    return m_impl->CountInFlight(peer);
-}
-size_t TxRequestTracker::CountCandidates(NodeId peer) const {
-    return m_impl->CountCandidates(peer);
-}
-size_t TxRequestTracker::Count(NodeId peer) const {
-    return m_impl->Count(peer);
-}
-size_t TxRequestTracker::Size() const {
-    return m_impl->Size();
-}
-void TxRequestTracker::SanityCheck() const {
-    m_impl->SanityCheck();
-}
-
-void TxRequestTracker::PostGetRequestableSanityCheck(
-    std::chrono::microseconds now) const {
-    m_impl->PostGetRequestableSanityCheck(now);
-}
-
-void TxRequestTracker::ReceivedInv(NodeId peer, const TxId &txid,
-                                   bool preferred,
-                                   std::chrono::microseconds reqtime) {
-    m_impl->ReceivedInv(peer, txid, preferred, reqtime);
-}
-
-void TxRequestTracker::RequestedTx(NodeId peer, const TxId &txid,
-                                   std::chrono::microseconds expiry) {
-    m_impl->RequestedTx(peer, txid, expiry);
-}
-
-void TxRequestTracker::ReceivedResponse(NodeId peer, const TxId &txid) {
-    m_impl->ReceivedResponse(peer, txid);
-}
-
-std::vector<TxId> TxRequestTracker::GetRequestable(
-    NodeId peer, std::chrono::microseconds now,
-    std::vector<std::pair<NodeId, TxId>> *expired) {
-    Impl::clearExpiredFun clearExpired = [expired]() {
-        if (expired) {
-            expired->clear();
-        }
-    };
-    Impl::emplaceExpiredFun emplaceExpired = [expired](const NodeId &nodeid,
-                                                       const uint256 &txid) {
-        if (expired) {
-            expired->emplace_back(nodeid, TxId(txid));
-        }
-    };
-    std::vector<uint256> hashes =
-        m_impl->GetRequestable(peer, now, clearExpired, emplaceExpired);
-    return std::vector<TxId>(hashes.begin(), hashes.end());
-}
-
-uint64_t TxRequestTracker::ComputePriority(const TxId &txid, NodeId peer,
-                                           bool preferred) const {
-    return m_impl->ComputePriority(txid, peer, preferred);
-}