Merge bitcoin/bitcoin#35531: txindex: hash keys and pack positions to reduce disk usage

### doc/release-notes-35531.md
@@ -0,0 +1,12 @@
+## Index
+
+- The transaction index (`-txindex`) now stores less data on disk; a fully
+  rebuilt index takes less than half the space. The index is backwards compatible,
+  so existing users will not see the space saving unless the index is recreated.
+  To do so, stop the node, delete the `<datadir>/indexes/txindex` directory, and
+  restart; rebuilding can take up to a few hours depending on hardware. Progress
+  can be monitored using the `getindexinfo` RPC. Once rebuilt, the index can no
+  longer be read by previous releases, so downgrading will rebuild it again in
+  the old format. When downgrading permanently, delete the
+  `<datadir>/indexes/txindex` directory first, since previous releases do not
+  reclaim the space used by entries in the new format. (#35531)

### src/dbwrapper.cpp
@@ -153,6 +153,30 @@ static leveldb::Options GetOptions(size_t nCacheSize, bool bloom_filter)
     return options;
 }
 
+bool CDBWrapper::HasKeyStartingWith(const fs::path& path, uint8_t prefix)
+{
+    if (!fs::exists(path / "CURRENT")) return false;
+
+    CBitcoinLevelDBLogger logger;
+    leveldb::Options options;
+    options.paranoid_checks = true;
+    // Avoid creating or rotating LevelDB's LOG files during this probe.
+    options.info_log = &logger;
+
+    leveldb::DB* raw_db;
+    HandleError(leveldb::DB::Open(options, fs::PathToString(path), &raw_db));
+    const std::unique_ptr<leveldb::DB> db{raw_db};
+
+    leveldb::ReadOptions iteroptions;
+    iteroptions.verify_checksums = true;
+    iteroptions.fill_cache = false;
+    const std::unique_ptr<leveldb::Iterator> it{db->NewIterator(iteroptions)};
+    const leveldb::Slice prefix_slice{reinterpret_cast<const char*>(&prefix), sizeof(prefix)};
+    it->Seek(prefix_slice);
+    HandleError(it->status());
+    return it->Valid() && it->key().starts_with(prefix_slice);
+}
+
 struct CDBBatch::WriteBatchImpl {
     leveldb::WriteBatch batch;
 };

### src/dbwrapper.h
@@ -279,6 +279,11 @@ class CDBWrapper
      */
     bool IsEmpty();
 
+    //! Probe an unopened database for a key prefix. Return true if a database at
+    //! path exists and contains at least 1 entry beginning with prefix; missing
+    //! or empty databases return false, and database errors throw dbwrapper_error.
+    static bool HasKeyStartingWith(const fs::path& path, uint8_t prefix);
+
     template<typename K>
     size_t EstimateSize(const K& key_begin, const K& key_end) const
     {

### src/index/base.h
@@ -66,13 +66,14 @@ class BaseIndex : public CValidationInterface
     public:
         DB(const fs::path& path, size_t n_cache_size,
            bool f_memory = false, bool f_wipe = false, bool f_obfuscate = false, bool f_bloom = true);
+        virtual ~DB() = default;
 
         /// Read block locator of the chain that the index is in sync with.
         /// Note, the returned locator will be empty if no record exists.
-        CBlockLocator ReadBestBlock() const;
+        virtual CBlockLocator ReadBestBlock() const;
 
         /// Write block locator of the chain that the index is in sync with.
-        void WriteBestBlock(CDBBatch& batch, const CBlockLocator& locator);
+        virtual void WriteBestBlock(CDBBatch& batch, const CBlockLocator& locator);
     };
 
 private:

### src/index/txindex.cpp
@@ -4,70 +4,143 @@
 
 #include <index/txindex.h>
 
+#include <chain.h>
 #include <common/args.h>
+#include <crypto/siphash.h>
 #include <dbwrapper.h>
 #include <flatfile.h>
 #include <index/base.h>
 #include <index/disktxpos.h>
+#include <index/txindex_key.h>
 #include <interfaces/chain.h>
 #include <node/blockstorage.h>
 #include <primitives/block.h>
 #include <primitives/transaction.h>
+#include <random.h>
 #include <serialize.h>
 #include <streams.h>
+#include <sync.h>
 #include <uint256.h>
 #include <util/fs.h>
 #include <util/log.h>
 #include <validation.h>
 
+#include <algorithm>
+#include <array>
 #include <cassert>
 #include <cstdint>
 #include <cstdio>
 #include <exception>
+#include <functional>
+#include <memory>
+#include <optional>
 #include <string>
 #include <utility>
 #include <vector>
 
-constexpr uint8_t DB_TXINDEX{'t'};
-
 std::unique_ptr<TxIndex> g_txindex;
 
+namespace {
+SipHasher13UJ ReadOrCreateTxidHasher(CDBWrapper& db)
+{
+    std::pair<uint64_t, uint64_t> salt;
+    if (!db.Read(txindex::DB_TXID_HASH_SALT, salt)) {
+        FastRandomContext rng{};
+        salt = {rng.rand64(), rng.rand64()};
+        db.Write(txindex::DB_TXID_HASH_SALT, salt, /*fSync=*/true);
+    }
+    return SipHasher13UJ{salt.first, salt.second};
+}
+} // namespace
 
 /** Access to the txindex database (indexes/txindex/) */
 class TxIndex::DB : public BaseIndex::DB
 {
 public:
     explicit DB(size_t n_cache_size, bool f_memory = false, bool f_wipe = false);
 
-    /// Read the disk location of the transaction data with the given hash. Returns false if the
-    /// transaction hash is not indexed.
-    bool ReadTxPos(const Txid& txid, CDiskTxPos& pos) const;
+    /// Write a block of transaction positions to the DB.
+    void WriteTxs(const interfaces::BlockInfo& block);
 
-    /// Write a batch of transaction positions to the DB.
-    void WriteTxs(const std::vector<std::pair<Txid, CDiskTxPos>>& v_pos);
+    /// Used to hash the txid to compute the prefix.
+    const SipHasher13UJ m_hasher;
+
+    /// Whether the database contains any legacy ('t' + txid) entries.
+    const bool m_has_legacy;
+
+    CBlockLocator ReadBestBlock() const override;
+    void WriteBestBlock(CDBBatch& batch, const CBlockLocator& locator) override;
+
+private:
+    DB(size_t n_cache_size, bool f_memory, bool f_wipe, bool has_legacy);
 };
 
+static fs::path TxIndexDBPath() { return gArgs.GetDataDirNet() / "indexes" / "txindex"; }
+
 TxIndex::DB::DB(size_t n_cache_size, bool f_memory, bool f_wipe) :
-    BaseIndex::DB(gArgs.GetDataDirNet() / "indexes" / "txindex", n_cache_size, f_memory, f_wipe)
+    // Bloom filters are built for every key but only consulted by point reads,
+    // which iterators bypass: the per-tx hashed ('x') lookups seek with an
+    // iterator, and the 's'/'h' point reads are at most one per block against a
+    // tiny keyspace. Only the legacy entries' per-tx point lookups benefit, so
+    // enable the filters only for databases still containing them.
+    DB(n_cache_size, f_memory, f_wipe,
+       /*has_legacy=*/!f_memory && !f_wipe && CDBWrapper::HasKeyStartingWith(TxIndexDBPath(), txindex::DB_TXINDEX))
 {}
 
-bool TxIndex::DB::ReadTxPos(const Txid& txid, CDiskTxPos& pos) const
+TxIndex::DB::DB(size_t n_cache_size, bool f_memory, bool f_wipe, bool has_legacy) :
+    BaseIndex::DB(TxIndexDBPath(), n_cache_size, f_memory, f_wipe, /*f_obfuscate=*/false, /*f_bloom=*/has_legacy),
+    m_hasher{ReadOrCreateTxidHasher(*this)},
+    m_has_legacy{has_legacy}
+{}
+
+CBlockLocator TxIndex::DB::ReadBestBlock() const
 {
-    return Read(std::make_pair(DB_TXINDEX, txid.ToUint256()), pos);
+    CBlockLocator locator;
+    if (Read(txindex::DB_BEST_BLOCK_V2, locator)) {
+        return locator;
+    }
+    // If we don't have a locator yet, start from the legacy best block.
+    return BaseIndex::DB::ReadBestBlock();
 }
 
-void TxIndex::DB::WriteTxs(const std::vector<std::pair<Txid, CDiskTxPos>>& v_pos)
+void TxIndex::DB::WriteBestBlock(CDBBatch& batch, const CBlockLocator& locator)
 {
+    batch.Write(txindex::DB_BEST_BLOCK_V2, locator);
+}
+
+void TxIndex::DB::WriteTxs(const interfaces::BlockInfo& block)
+{
+    // A block may be submitted again after it was already indexed, e.g. when it
+    // reconnects after a reorg or is re-processed after an unclean shutdown. It
+    // keeps its original sequence number, so skip it to avoid duplicate entries.
+    if (Exists(txindex::BlockHashKey{block.hash})) return;
+
+    uint32_t block_seq{0};
+    Read(txindex::DB_NEXT_BLOCK_SEQ, block_seq);
+
     CDBBatch batch(*this);
-    for (const auto& [txid, pos] : v_pos) {
-        batch.Write(std::make_pair(DB_TXINDEX, txid.ToUint256()), pos);
+    batch.Write(txindex::BlockHashKey{block.hash}, block_seq);
+    batch.Write(txindex::BlockSeqKey{block_seq}, block.hash);
+    batch.Write(txindex::DB_NEXT_BLOCK_SEQ, block_seq + 1);
+    uint32_t tx_offset_in_block{txindex::BLOCK_HEADER_SIZE + GetSizeOfCompactSize(block.data->vtx.size())};
+    for (const auto& tx : block.data->vtx) {
+        const txindex::DBKey key{txindex::CreateKeyPrefix(m_hasher, tx->GetHash()),
+                                 txindex::BlockTxPosition{block_seq, tx_offset_in_block}};
+        batch.Write(key, txindex::EMPTY_VALUE);
+        tx_offset_in_block += tx->ComputeTotalSize();
     }
     WriteBatch(batch);
 }
 
 TxIndex::TxIndex(std::unique_ptr<interfaces::Chain> chain, size_t n_cache_size, bool f_memory, bool f_wipe)
     : BaseIndex(std::move(chain), "txindex", "txidx"), m_db(std::make_unique<TxIndex::DB>(n_cache_size, f_memory, f_wipe))
-{}
+{
+    if (m_db->m_has_legacy) {
+        LogInfo("txindex contains entries in the legacy format, which uses excessive disk space. "
+                "To reclaim disk space, stop the node, delete %s and restart to rebuild the index.",
+                fs::PathToString(TxIndexDBPath()));
+    }
+}
 
 TxIndex::~TxIndex() = default;
 
@@ -77,44 +150,98 @@ bool TxIndex::CustomAppend(const interfaces::BlockInfo& block)
     if (block.height == 0) return true;
 
     assert(block.data);
-    CDiskTxPos pos({block.file_number, block.data_pos}, GetSizeOfCompactSize(block.data->vtx.size()));
-    std::vector<std::pair<Txid, CDiskTxPos>> vPos;
-    vPos.reserve(block.data->vtx.size());
-    for (const auto& tx : block.data->vtx) {
-        vPos.emplace_back(tx->GetHash(), pos);
-        pos.nTxOffset += ::GetSerializeSize(TX_WITH_WITNESS(*tx));
-    }
-    m_db->WriteTxs(vPos);
+    m_db->WriteTxs(block);
     return true;
 }
 
 BaseIndex::DB& TxIndex::GetDB() const { return *m_db; }
 
-bool TxIndex::FindTx(const Txid& tx_hash, uint256& block_hash, CTransactionRef& tx) const
+std::optional<TxIndexResult> TxIndex::FindTx(const Txid& tx_hash) const
+{
+    struct Candidate {
+        FlatFilePos tx_position;
+        uint256 block_hash;
+        uint32_t block_seq;
+        //! Whether this candidate's block is currently in the active chain.
+        //! Active chain candidates are attempted first, so duplicate entries
+        //! in both active and stale blocks will always return the active block hash.
+        bool in_active_chain;
+    };
+    std::vector<Candidate> candidates;
+    {
+        std::unique_ptr<CDBIterator> it{m_db->NewIterator()};
+        const txindex::TxHashKeyPrefix prefix{txindex::CreateKeyPrefix(m_db->m_hasher, tx_hash)};
+        txindex::DBKey key{prefix, {}};
+        for (it->Seek(key); it->Valid() && it->GetKey(key) && key.hash_prefix == prefix; it->Next()) {
+            uint256 candidate_block_hash;
+            if (!m_db->Read(txindex::BlockSeqKey{key.pos.block_seq}, candidate_block_hash)) {
+                LogWarning("Block sequence %u not found for txid %s", key.pos.block_seq, tx_hash.ToString());
+                continue;
+            }
+            LOCK(cs_main);
+            const CBlockIndex* block_index{m_chainstate->m_blockman.LookupBlockIndex(candidate_block_hash)};
+            if (!block_index) {
+                LogWarning("Block index entry %s not found for txid %s", candidate_block_hash.ToString(), tx_hash.ToString());
+                continue;
+            }
+            if (!(block_index->nStatus & BLOCK_HAVE_DATA)) continue;
+            const FlatFilePos tx_position{block_index->nFile, block_index->nDataPos + key.pos.tx_offset_in_block};
+            candidates.emplace_back(tx_position, candidate_block_hash, key.pos.block_seq, m_chainstate->m_chain.Contains(*block_index));
+        }
+    }
+
+    // Prefer active-chain matches, then later-connected blocks.
+    std::ranges::sort(candidates, std::greater{}, [](const Candidate& c) {
+        return std::pair{c.in_active_chain, c.block_seq};
+    });
+
+    for (const auto& candidate : candidates) {
+        AutoFile file{m_chainstate->m_blockman.OpenBlockFile(candidate.tx_position, /*fReadOnly=*/true)};
+        if (file.IsNull()) {
+            LogWarning("OpenBlockFile failed for txid %s", tx_hash.ToString());
+            continue;
+        }
+        CTransactionRef tx;
+        try {
+            file >> TX_WITH_WITNESS(tx);
+        } catch (const std::exception& e) {
+            LogWarning("Deserialize or I/O error - %s", e.what());
+            continue;
+        }
+        if (tx->GetHash() == tx_hash) {
+            return TxIndexResult{candidate.block_hash, std::move(tx)};
+        }
+    }
+    // Fall back to legacy if no hashed entry matched. This makes misses pay an
+    // extra lookup, but keeps existing full-txid entries readable after upgrade.
+    return m_db->m_has_legacy ? FindLegacyTx(tx_hash) : std::nullopt;
+}
+
+std::optional<TxIndexResult> TxIndex::FindLegacyTx(const Txid& tx_hash) const
 {
     CDiskTxPos postx;
-    if (!m_db->ReadTxPos(tx_hash, postx)) {
-        return false;
+    if (!m_db->Read(txindex::LegacyTxKey(tx_hash), postx)) {
+        return std::nullopt;
     }
 
-    AutoFile file{m_chainstate->m_blockman.OpenBlockFile(postx, true)};
+    AutoFile file{m_chainstate->m_blockman.OpenBlockFile(postx, /*fReadOnly=*/true)};
     if (file.IsNull()) {
         LogError("OpenBlockFile failed");
-        return false;
+        return std::nullopt;
     }
     CBlockHeader header;
+    CTransactionRef tx;
     try {
         file >> header;
         file.seek(postx.nTxOffset, SEEK_CUR);
         file >> TX_WITH_WITNESS(tx);
     } catch (const std::exception& e) {
         LogError("Deserialize or I/O error - %s", e.what());
-        return false;
+        return std::nullopt;
     }
     if (tx->GetHash() != tx_hash) {
         LogError("txid mismatch");
-        return false;
+        return std::nullopt;
     }
-    block_hash = header.GetHash();
-    return true;
+    return TxIndexResult{header.GetHash(), std::move(tx)};
 }

### src/index/txindex.h
@@ -7,32 +7,46 @@
 
 #include <index/base.h>
 #include <primitives/transaction.h>
+#include <uint256.h>
 
 #include <cstddef>
 #include <memory>
+#include <optional>
 
-class uint256;
 namespace interfaces {
 class Chain;
 }
+namespace txindex_tests {
+class TxIndexTest;
+}
 
 inline constexpr bool DEFAULT_TXINDEX{false};
 
+/// A found transaction and the hash of the block that contains it.
+struct TxIndexResult {
+    uint256 block_hash;
+    CTransactionRef tx;
+};
+
 /**
  * TxIndex is used to look up transactions included in the blockchain by hash.
- * The index is written to a LevelDB database and records the filesystem
- * location of each transaction by transaction hash.
+ * The index is written to a LevelDB database and records the block sequence
+ * number and serialized block offset of each transaction by transaction hash.
  */
 class TxIndex final : public BaseIndex
 {
 protected:
     class DB;
 
 private:
+    friend class txindex_tests::TxIndexTest;
     const std::unique_ptr<DB> m_db;
 
     bool AllowPrune() const override { return false; }
 
+    /// Look up a transaction among the legacy (full-txid) entries.
+    std::optional<TxIndexResult> FindLegacyTx(const Txid& tx_hash) const;
+
 protected:
     bool CustomAppend(const interfaces::BlockInfo& block) override;
 
@@ -48,10 +62,8 @@ class TxIndex final : public BaseIndex
     /// Look up a transaction by hash.
     ///
     /// @param[in]   tx_hash  The hash of the transaction to be returned.
-    /// @param[out]  block_hash  The hash of the block the transaction is found in.
-    /// @param[out]  tx  The transaction itself.
-    /// @return  true if transaction is found, false otherwise
-    bool FindTx(const Txid& tx_hash, uint256& block_hash, CTransactionRef& tx) const;
+    /// @return  the transaction and containing block hash, or nullopt if it is not found
+    std::optional<TxIndexResult> FindTx(const Txid& tx_hash) const;
 };
 
 /// The global transaction index, used in GetTransaction. May be null.

### src/index/txindex_key.h
@@ -0,0 +1,128 @@
+// Copyright (c) The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_INDEX_TXINDEX_KEY_H
+#define BITCOIN_INDEX_TXINDEX_KEY_H
+
+#include <consensus/consensus.h>
+#include <crypto/siphash.h>
+#include <primitives/transaction_identifier.h>
+#include <serialize.h>
+#include <uint256.h>
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <ios>
+#include <string>
+#include <utility>
+
+namespace txindex {
+/*
+ * Database layout:
+ *
+ *   ['x', hash prefix, block seq, tx offset] -> (empty)
+ *   ['s', block seq]                         -> block hash
+ *   ['h', block hash]                        -> block seq
+ *   ["next_block_seq"]                       -> next block seq to assign
+ *   ["txid_hash_salt"]                       -> txid hasher salt
+ *   ["best_block_v2"]                        -> current sync locator
+ *   ['t', txid]                              -> legacy CDiskTxPos
+ *   ['B']                                    -> legacy sync locator
+ */
+
+constexpr uint8_t DB_TXINDEX_HASHED{'x'};
+constexpr uint8_t DB_BLOCK_SEQ{'s'};
+constexpr uint8_t DB_BLOCK_HASH{'h'};
+inline const std::string DB_NEXT_BLOCK_SEQ{"next_block_seq"};
+inline const std::string DB_TXID_HASH_SALT{"txid_hash_salt"};
+inline const std::string DB_BEST_BLOCK_V2{"best_block_v2"};
+//! Prefix of a legacy (pre-hashing) txindex row.
+constexpr uint8_t DB_TXINDEX{'t'};
+
+//! Empty value of a hashed txindex row, whose position is encoded in its key.
+inline constexpr std::array<std::byte, 0> EMPTY_VALUE{};
+
+//! Serialized size of a block header, the offset of the first byte after it.
+constexpr uint32_t BLOCK_HEADER_SIZE{80};
+
+//! The location of a transaction: the sequence number of the block that contains it
+//! and the transaction's serialized byte offset from the start of that block
+//! (including the header), so the on-disk position is simply
+//! block_data_pos + tx_offset_in_block.
+//!
+struct BlockTxPosition {
+    uint32_t block_seq{0};
+    uint32_t tx_offset_in_block{0};
+
+    friend bool operator==(const BlockTxPosition&, const BlockTxPosition&) = default;
+
+    // tx_offset is encoded in 3-byte big-endian integer.
+    // This can hold up to 16,777,216, which is >4x the maximum 4 million block weight position
+    static constexpr uint32_t TX_OFFSET_SIZE{3};
+    static_assert(MAX_BLOCK_SERIALIZED_SIZE <= BigEndianFormatter<TX_OFFSET_SIZE>::MAX);
+
+    SERIALIZE_METHODS(BlockTxPosition, obj)
+    {
+        READWRITE(VARINT(obj.block_seq),
+                  Using<BigEndianFormatter<TX_OFFSET_SIZE>>(obj.tx_offset_in_block));
+    }
+};
+
+//! Key for looking up the hash of the block with the given sequence number.
+struct BlockSeqKey {
+    uint32_t block_seq{0};
+
+    SERIALIZE_METHODS(BlockSeqKey, obj)
+    {
+        uint8_t prefix{DB_BLOCK_SEQ};
+        READWRITE(prefix);
+        if (ser_action.ForRead() && prefix != DB_BLOCK_SEQ) throw std::ios_base::failure("Invalid format for txindex block seq key");
+        READWRITE(VARINT(obj.block_seq));
+    }
+};
+
+//! Key for looking up the sequence number assigned to the block with the given hash.
+struct BlockHashKey {
+    uint256 block_hash;
+
+    SERIALIZE_METHODS(BlockHashKey, obj)
+    {
+        uint8_t prefix{DB_BLOCK_HASH};
+        READWRITE(prefix);
+        if (ser_action.ForRead() && prefix != DB_BLOCK_HASH) throw std::ios_base::failure("Invalid format for txindex block hash key");
+        READWRITE(obj.block_hash);
+    }
+};
+
+constexpr int HASH_PREFIX_SIZE{5};
+using TxHashKeyPrefix = uint64_t;
+
+inline TxHashKeyPrefix CreateKeyPrefix(const SipHasher13UJ& hasher, const Txid& txid)
+{
+    return hasher.Hash(txid.ToUint256()) >> (8 * (sizeof(TxHashKeyPrefix) - HASH_PREFIX_SIZE));
+}
+
+struct DBKey {
+    TxHashKeyPrefix hash_prefix{0};
+    BlockTxPosition pos;
+
+    SERIALIZE_METHODS(DBKey, obj)
+    {
+        uint8_t prefix{DB_TXINDEX_HASHED};
+        READWRITE(prefix);
+        if (ser_action.ForRead() && prefix != DB_TXINDEX_HASHED) throw std::ios_base::failure("Invalid format for txindex DB key");
+        READWRITE(Using<BigEndianFormatter<HASH_PREFIX_SIZE>>(obj.hash_prefix), obj.pos);
+    }
+};
+
+//! Key of a legacy (pre-hashing) txindex row: the full txid under the 't' prefix.
+inline std::pair<uint8_t, uint256> LegacyTxKey(const Txid& txid)
+{
+    return {DB_TXINDEX, txid.ToUint256()};
+}
+
+} // namespace txindex
+
+#endif // BITCOIN_INDEX_TXINDEX_KEY_H

### src/node/transaction.cpp
@@ -146,15 +146,13 @@ CTransactionRef GetTransaction(const CBlockIndex* const block_index, const CTxMe
         if (ptx) return ptx;
     }
     if (g_txindex) {
-        CTransactionRef tx;
-        uint256 block_hash;
-        if (g_txindex->FindTx(hash, block_hash, tx)) {
-            if (!block_index || block_index->GetBlockHash() == block_hash) {
+        if (auto result{g_txindex->FindTx(hash)}) {
+            if (!block_index || block_index->GetBlockHash() == result->block_hash) {
                 // Don't return the transaction if the provided block hash doesn't match.
                 // The case where a transaction appears in multiple blocks (e.g. reorgs or
                 // BIP30) is handled by the block lookup below.
-                hashBlock = block_hash;
-                return tx;
+                hashBlock = result->block_hash;
+                return result->tx;
             }
         }
     }

### src/rpc/rawtransaction.cpp
@@ -152,8 +152,7 @@ PartiallySignedTransaction ProcessPSBT(const std::string& psbt_string, const std
 
         // Look in the txindex
         if (g_txindex) {
-            uint256 block_hash;
-            g_txindex->FindTx(psbt_input.prev_txid, block_hash, tx);
+            if (auto result{g_txindex->FindTx(psbt_input.prev_txid)}) tx = result->tx;
         }
         // If we still don't have it look in the mempool
         if (!tx) {

### src/test/txindex_tests.cpp
@@ -3,28 +3,144 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <addresstype.h>
+#include <chain.h>
 #include <chainparams.h>
+#include <common/args.h>
+#include <consensus/amount.h>
+#include <consensus/validation.h>
+#include <crypto/hex_base.h>
+#include <dbwrapper.h>
+#include <flatfile.h>
+#include <index/disktxpos.h>
 #include <index/txindex.h>
+#include <index/txindex_key.h>
 #include <interfaces/chain.h>
+#include <key.h>
+#include <node/blockstorage.h>
+#include <primitives/block.h>
+#include <script/script.h>
+#include <streams.h>
+#include <sync.h>
 #include <test/util/setup_common.h>
 #include <util/byte_units.h>
+#include <util/check.h>
+#include <util/strencodings.h>
 #include <validation.h>
 
+#include <cstdint>
+#include <memory>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
 #include <boost/test/unit_test.hpp>
 
 BOOST_AUTO_TEST_SUITE(txindex_tests)
 
+// Grants tests access to the otherwise non-public txindex database handle.
+class TxIndexTest
+{
+public:
+    static CDBWrapper& GetDB(const TxIndex& txindex) { return txindex.GetDB(); }
+    static CBlockLocator ReadBestBlock(const TxIndex& txindex) { return txindex.GetDB().ReadBestBlock(); }
+    static void WriteBestBlock(const TxIndex& txindex, const CBlockLocator& locator)
+    {
+        auto& db{txindex.GetDB()};
+        CDBBatch batch{db};
+        db.WriteBestBlock(batch, locator);
+        db.WriteBatch(batch);
+    }
+};
+
+namespace {
+
+SipHasher13UJ ReadHasher(const CDBWrapper& db)
+{
+    std::pair<uint64_t, uint64_t> salt;
+    BOOST_REQUIRE(db.Read(txindex::DB_TXID_HASH_SALT, salt));
+    return SipHasher13UJ{salt.first, salt.second};
+}
+
+std::vector<txindex::BlockTxPosition> BucketPositions(CDBWrapper& db, txindex::TxHashKeyPrefix prefix)
+{
+    std::vector<txindex::BlockTxPosition> positions;
+    std::unique_ptr<CDBIterator> it{db.NewIterator()};
+    txindex::DBKey key{prefix, {}};
+    for (it->Seek(key); it->Valid() && it->GetKey(key) && key.hash_prefix == prefix; it->Next()) {
+        positions.push_back(key.pos);
+    }
+    return positions;
+}
+
+FlatFilePos BlockFilePos(const ChainstateManager& chainman, uint32_t height)
+{
+    LOCK(cs_main);
+    const CBlockIndex* block_index{chainman.ActiveChain()[height]};
+    BOOST_REQUIRE(block_index);
+    return {block_index->nFile, block_index->nDataPos};
+}
+
+uint256 LookupTx(const TxIndex& txindex, const Txid& txid)
+{
+    const auto result{txindex.FindTx(txid)};
+    BOOST_REQUIRE(result);
+    BOOST_CHECK(result->tx->GetHash() == txid);
+    return result->block_hash;
+}
+
+void InvalidateBlock(ChainstateManager& chainman, const uint256& block_hash)
+{
+    CBlockIndex* block_index{WITH_LOCK(cs_main, return chainman.m_blockman.LookupBlockIndex(block_hash))};
+    BOOST_REQUIRE(block_index);
+    BlockValidationState state;
+    BOOST_REQUIRE(chainman.ActiveChainstate().InvalidateBlock(state, block_index));
+}
+
+} // namespace
+
+BOOST_AUTO_TEST_CASE(txindex_position_encoding)
+{
+    constexpr struct { txindex::BlockTxPosition position; std::string_view encoded; } test_vectors[]{
+        {{0, 0}, "00000000"},
+        {{1, 2}, "01000002"},
+        {{10'000'000, 123}, "83e1ac0000007b"},
+        {{456, 3'999'999}, "82483d08ff"},
+    };
+
+    for (const auto& [position, encoded] : test_vectors) {
+        BOOST_CHECK_EQUAL(HexStr(DataStream{} << position), encoded);
+
+        txindex::BlockTxPosition decoded;
+        BOOST_CHECK((DataStream{ParseHex(encoded)} >> decoded).empty());
+        BOOST_CHECK(decoded == position);
+    }
+
+    // Pin the full key encodings, including the type prefixes.
+    BOOST_CHECK_EQUAL(HexStr(DataStream{} << txindex::BlockSeqKey{1}), "7301");
+    BOOST_CHECK_EQUAL(HexStr(DataStream{} << txindex::DBKey{0x0102030405, {1, 2}}),
+                      "78010203040501000002");
+
+    BOOST_CHECK_EQUAL(txindex::BLOCK_HEADER_SIZE, GetSerializeSize(CBlockHeader{}));
+}
+
+BOOST_AUTO_TEST_CASE(txindex_hash_prefix)
+{
+    BOOST_CHECK_EQUAL(
+        txindex::CreateKeyPrefix(
+            SipHasher13UJ{0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL},
+            Txid{"1f1e1d1c1b1a191817161514131211100f0e0d0c0b0a09080706050403020100"}),
+        0xc67d87b08cULL);
+}
+
 BOOST_FIXTURE_TEST_CASE(txindex_initial_sync, TestChain100Setup)
 {
-    TxIndex txindex(interfaces::MakeChain(m_node), 1_MiB, true);
+    TxIndex txindex(interfaces::MakeChain(m_node), /*n_cache_size=*/1_MiB, /*f_memory=*/true);
     BOOST_REQUIRE(txindex.Init());
 
-    CTransactionRef tx_disk;
-    uint256 block_hash;
-
     // Transaction should not be found in the index before it is started.
     for (const auto& txn : m_coinbase_txns) {
-        BOOST_CHECK(!txindex.FindTx(txn->GetHash(), block_hash, tx_disk));
+        BOOST_CHECK(!txindex.FindTx(txn->GetHash()));
     }
 
     // BlockUntilSyncedToCurrentChain should return false before txindex is started.
@@ -35,16 +151,12 @@ BOOST_FIXTURE_TEST_CASE(txindex_initial_sync, TestChain100Setup)
     // Check that txindex excludes genesis block transactions.
     const CBlock& genesis_block = Params().GenesisBlock();
     for (const auto& txn : genesis_block.vtx) {
-        BOOST_CHECK(!txindex.FindTx(txn->GetHash(), block_hash, tx_disk));
+        BOOST_CHECK(!txindex.FindTx(txn->GetHash()));
     }
 
     // Check that txindex has all txs that were in the chain before it started.
     for (const auto& txn : m_coinbase_txns) {
-        if (!txindex.FindTx(txn->GetHash(), block_hash, tx_disk)) {
-            BOOST_ERROR("FindTx failed");
-        } else if (tx_disk->GetHash() != txn->GetHash()) {
-            BOOST_ERROR("Read incorrect tx");
-        }
+        LookupTx(txindex, txn->GetHash());
     }
 
     // Check that new transactions in new blocks make it into the index.
@@ -55,15 +167,189 @@ BOOST_FIXTURE_TEST_CASE(txindex_initial_sync, TestChain100Setup)
         const CTransaction& txn = *block.vtx[0];
 
         BOOST_CHECK(txindex.BlockUntilSyncedToCurrentChain());
-        if (!txindex.FindTx(txn.GetHash(), block_hash, tx_disk)) {
-            BOOST_ERROR("FindTx failed");
-        } else if (tx_disk->GetHash() != txn.GetHash()) {
-            BOOST_ERROR("Read incorrect tx");
-        }
+        LookupTx(txindex, txn.GetHash());
     }
 
     // shutdown sequence (c.f. Shutdown() in init.cpp)
     txindex.Stop();
 }
 
+BOOST_FIXTURE_TEST_CASE(txindex_collision_scan_path, TestChain100Setup)
+{
+    // On-disk, so the legacy-entry probe at construction runs against a fresh
+    // database, as it would on a node whose index was created by this version.
+    TxIndex txindex(interfaces::MakeChain(m_node), /*n_cache_size=*/1_MiB, /*f_memory=*/false);
+    BOOST_REQUIRE(txindex.Init());
+    txindex.Sync();
+
+    CDBWrapper& db{TxIndexTest::GetDB(txindex)};
+    const SipHasher13UJ hasher{ReadHasher(db)};
+
+    // Lookups scan candidates in descending sequence order, so entries of
+    // later-connected blocks are tried first. Forge a colliding entry under the
+    // first coinbase's prefix pointing at the last coinbase, so looking up the
+    // first tx must scan that false positive first.
+    const Txid fake_txid{m_coinbase_txns.back()->GetHash()};
+    const Txid target_txid{m_coinbase_txns.front()->GetHash()};
+    const auto fake_prefix{txindex::CreateKeyPrefix(hasher, fake_txid)};
+    const auto target_prefix{txindex::CreateKeyPrefix(hasher, target_txid)};
+    // Distinct prefixes guarantee the target's bucket initially holds only the target.
+    BOOST_REQUIRE(fake_prefix != target_prefix);
+
+    // Read the last coinbase's encoded position straight from its bucket.
+    const auto fake_bucket{BucketPositions(db, fake_prefix)};
+    BOOST_REQUIRE_EQUAL(fake_bucket.size(), 1U);
+    const txindex::BlockTxPosition fake_pos{fake_bucket.front()};
+
+    db.Write(txindex::DBKey{target_prefix, fake_pos}, txindex::EMPTY_VALUE);
+
+    // The target's bucket now holds the real target first (lower sequence
+    // number), then the forged false positive, which the descending scan tries first.
+    const auto target_bucket{BucketPositions(db, target_prefix)};
+    BOOST_REQUIRE_EQUAL(target_bucket.size(), 2U);
+    BOOST_CHECK(target_bucket[0] != fake_pos);
+    BOOST_CHECK(target_bucket[1] == fake_pos);
+
+    LookupTx(txindex, target_txid);
+
+    // A database created fresh by this version cannot contain legacy entries, so
+    // lookups skip the legacy fallback: drop the last coinbase's hashed entry and
+    // re-add it under the old 't' + txid schema (a physical CDiskTxPos), then
+    // confirm the lookup misses even though the legacy row exists.
+    // BlockTxPosition offsets are from the block start (header included), while
+    // the legacy CDiskTxPos.nTxOffset is measured after the header.
+    const CDiskTxPos fake_physical{BlockFilePos(*m_node.chainman, fake_pos.block_seq + 1), fake_pos.tx_offset_in_block - txindex::BLOCK_HEADER_SIZE};
+    db.Erase(txindex::DBKey{fake_prefix, fake_pos});
+    db.Write(txindex::LegacyTxKey(fake_txid), fake_physical);
+    BOOST_CHECK(!txindex.FindTx(fake_txid));
+
+    txindex.Stop();
+}
+
+BOOST_FIXTURE_TEST_CASE(txindex_legacy_fallback, TestChain100Setup)
+{
+    // Seed the on-disk database with a legacy ('t' + txid) entry before the index
+    // is opened, as if it had been written by a pre-hashing version.
+    const Txid legacy_txid{m_coinbase_txns.front()->GetHash()};
+    // The block at height 1 holds only the coinbase, so the tx starts right after
+    // the header and the 1-byte tx count.
+    const CDiskTxPos legacy_pos{BlockFilePos(*m_node.chainman, 1), 1};
+    {
+        CDBWrapper db{DBParams{.path = gArgs.GetDataDirNet() / "indexes" / "txindex", .cache_bytes = 1_MiB}};
+        db.Write(txindex::LegacyTxKey(legacy_txid), legacy_pos);
+    }
+
+    TxIndex txindex(interfaces::MakeChain(m_node), /*n_cache_size=*/1_MiB, /*f_memory=*/false);
+    BOOST_REQUIRE(txindex.Init());
+    txindex.Sync();
+
+    // Drop the hashed entries so only the legacy row remains, then confirm the
+    // lookup succeeds through the fallback.
+    CDBWrapper& db{TxIndexTest::GetDB(txindex)};
+    const auto prefix{txindex::CreateKeyPrefix(ReadHasher(db), legacy_txid)};
+    const auto bucket{BucketPositions(db, prefix)};
+    BOOST_REQUIRE(!bucket.empty());
+    for (const auto& pos : bucket) db.Erase(txindex::DBKey{prefix, pos});
+
+    LookupTx(txindex, legacy_txid);
+
+    txindex.Stop();
+}
+
+BOOST_FIXTURE_TEST_CASE(txindex_locator_upgrade, TestChain100Setup)
+{
+    uint256 legacy_hash, new_hash;
+    {
+        LOCK(cs_main);
+        legacy_hash = Assert(m_node.chainman->ActiveChain()[1])->GetBlockHash();
+        new_hash = Assert(m_node.chainman->ActiveChain().Tip())->GetBlockHash();
+    }
+    CBlockLocator legacy_locator{{legacy_hash}}, new_locator{{new_hash}};
+    { CDBWrapper{DBParams{.path = gArgs.GetDataDirNet() / "indexes" / "txindex", .cache_bytes = 1_MiB}}.Write(uint8_t{'B'}, legacy_locator); }
+
+    TxIndex txindex(interfaces::MakeChain(m_node), /*n_cache_size=*/1_MiB, /*f_memory=*/false);
+    BOOST_CHECK(TxIndexTest::ReadBestBlock(txindex).vHave == legacy_locator.vHave);
+
+    TxIndexTest::WriteBestBlock(txindex, new_locator);
+    BOOST_CHECK(TxIndexTest::ReadBestBlock(txindex).vHave == new_locator.vHave);
+
+    CBlockLocator stored_legacy_locator;
+    BOOST_REQUIRE(TxIndexTest::GetDB(txindex).Read(uint8_t{'B'}, stored_legacy_locator));
+    BOOST_CHECK(stored_legacy_locator.vHave == legacy_locator.vHave);
+}
+
+BOOST_FIXTURE_TEST_CASE(txindex_reorg_keeps_stale_entries, TestChain100Setup)
+{
+    TxIndex txindex(interfaces::MakeChain(m_node), /*n_cache_size=*/1_MiB, /*f_memory=*/true);
+    BOOST_REQUIRE(txindex.Init());
+    txindex.Sync();
+
+    const CScript coinbase_script{CScript() << ToByteVector(coinbaseKey.GetPubKey()) << OP_CHECKSIG};
+
+    // Mine a unique (non-coinbase) transaction into a new block at height 101.
+    CMutableTransaction unique_mtx{CreateValidMempoolTransaction(
+        /*input_transaction=*/m_coinbase_txns[0],
+        /*input_vout=*/0,
+        /*input_height=*/1,
+        /*input_signing_key=*/coinbaseKey,
+        /*output_destination=*/CScript() << OP_TRUE,
+        /*output_amount=*/CAmount{1 * COIN},
+        /*submit=*/false)};
+    const Txid unique_txid{MakeTransactionRef(unique_mtx)->GetHash()};
+    const uint256 stale_block_hash{CreateAndProcessBlock({unique_mtx}, coinbase_script).GetHash()};
+    BOOST_REQUIRE(txindex.BlockUntilSyncedToCurrentChain());
+
+    BOOST_CHECK(LookupTx(txindex, unique_txid) == stale_block_hash);
+
+    CDBWrapper& db{TxIndexTest::GetDB(txindex)};
+    const auto prefix{txindex::CreateKeyPrefix(ReadHasher(db), unique_txid)};
+    const auto original_bucket{BucketPositions(db, prefix)};
+    BOOST_REQUIRE_EQUAL(original_bucket.size(), 1U);
+
+    ChainstateManager& chainman{*m_node.chainman};
+
+    // Invalidate the block holding the unique transaction.
+    InvalidateBlock(chainman, stale_block_hash);
+    BOOST_REQUIRE(txindex.BlockUntilSyncedToCurrentChain());
+
+    // The disconnected transaction is still found, in the now-stale block.
+    BOOST_CHECK(LookupTx(txindex, unique_txid) == stale_block_hash);
+    {
+        LOCK(cs_main);
+        const CBlockIndex* stale_index{chainman.m_blockman.LookupBlockIndex(stale_block_hash)};
+        BOOST_REQUIRE(stale_index);
+        BOOST_CHECK(!chainman.ActiveChain().Contains(*stale_index));
+    }
+
+    // Mine the same transaction into a replacement branch, which gets a later
+    // sequence number. The lookup must now return the branch block in the active chain.
+    const uint256 branch_block_hash{CreateAndProcessBlock({unique_mtx}, CScript() << OP_TRUE).GetHash()};
+    CreateAndProcessBlock({}, coinbase_script);
+    BOOST_REQUIRE(txindex.BlockUntilSyncedToCurrentChain());
+    BOOST_CHECK(LookupTx(txindex, unique_txid) == branch_block_hash);
+
+    // Reorg back to the original branch. The original branch block must be
+    // now be preferred even though the replacement branch has a later sequence.
+    {
+        LOCK(cs_main);
+        chainman.ActiveChainstate().ResetBlockFailureFlags(chainman.m_blockman.LookupBlockIndex(stale_block_hash));
+    }
+    InvalidateBlock(chainman, branch_block_hash);
+    {
+        BlockValidationState state;
+        BOOST_REQUIRE(chainman.ActiveChainstate().ActivateBestChain(state));
+    }
+    BOOST_REQUIRE(txindex.BlockUntilSyncedToCurrentChain());
+    BOOST_CHECK(WITH_LOCK(cs_main, return chainman.ActiveChain().Tip()->GetBlockHash()) == stale_block_hash);
+
+    BOOST_CHECK(LookupTx(txindex, unique_txid) == stale_block_hash);
+
+    // Reconnecting the original block must not create duplicate entries.
+    const auto reorg_bucket{BucketPositions(db, prefix)};
+    BOOST_REQUIRE_EQUAL(reorg_bucket.size(), 2U);
+    BOOST_CHECK(reorg_bucket.front() == original_bucket.front());
+
+    txindex.Stop();
+}
+
 BOOST_AUTO_TEST_SUITE_END()

### test/functional/feature_txindex_compatibility.py
@@ -0,0 +1,72 @@
+#!/usr/bin/env python3
+# Copyright (c) 2026 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""Test txindex forward compatibility.
+
+"""
+
+import shutil
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import assert_equal
+from test_framework.wallet import MiniWallet
+
+class TxIndexTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.num_nodes = 2
+        self.extra_args = [["-txindex"],["-txindex"]]
+
+    def skip_test_if_missing_module(self):
+        self.skip_if_no_previous_releases()
+
+    def setup_nodes(self):
+        self.add_nodes(
+            self.num_nodes,
+            extra_args=self.extra_args,
+            versions=[
+                None,
+                280200,
+            ],
+        )
+        self.start_nodes()
+
+    def run_test(self):
+        self._test_txindex_compatibility()
+
+    def _test_txindex_compatibility(self):
+        node = self.nodes[0]
+        legacy_node = self.nodes[1]
+        self.wallet = MiniWallet(self.nodes[0])
+        tx1 = self.wallet.send_self_transfer(from_node=self.nodes[0])
+        self.generate(self.nodes[0], 1)
+        txId1 = tx1['txid']
+
+        for n in self.nodes:
+            self.wait_until(lambda: n.getindexinfo()['txindex']['synced'])
+
+        self.log.info("Ensure that queries to the txindex are consistent between the different index versions")
+        assert_equal(node.getrawtransaction(txId1), tx1['hex'])
+        assert_equal(legacy_node.getrawtransaction(txId1), tx1['hex'])
+
+        self.log.info("Exercise the new index running on a datadir with the old version")
+        self.stop_nodes()
+        self.cleanup_folder(node.chain_path)
+        shutil.copytree(legacy_node.chain_path, node.chain_path)
+        msg = "txindex contains entries in the legacy format"
+        with node.assert_debug_log(expected_msgs=[msg]):
+            self.start_node(0)
+        self.wait_until(lambda: node.getindexinfo()['txindex']['synced'])
+        assert_equal(node.getrawtransaction(txId1), tx1['hex'])
+
+        self.log.info("Test that looking up a newly added transaction in a mixed-format db is possible")
+        tx2 = self.wallet.send_self_transfer(from_node=self.nodes[0])
+        self.generate(self.nodes[0], 1, sync_fun=self.no_op)
+        txId2 = tx2['txid']
+        self.wait_until(lambda: node.getindexinfo()['txindex']['synced'])
+        assert_equal(node.getrawtransaction(txId1), tx1['hex'])
+        assert_equal(node.getrawtransaction(txId2), tx2['hex'])
+
+
+if __name__ == '__main__':
+    TxIndexTest(__file__).main()

### test/functional/test_runner.py
@@ -125,6 +125,7 @@
     'feature_segwit.py --v2transport',
     'feature_segwit.py --v1transport',
     'p2p_tx_download.py',
+    'feature_txindex_compatibility.py',
     'wallet_avoidreuse.py',
     'feature_abortnode.py',
     'wallet_address_types.py',