Merge bitcoin/bitcoin#23174: validation: have LoadBlockIndex account for snapshot use

2283b9cd1ee0fbd1e8ebc61673b1fe7596199a24 test: add tests for LoadBlockIndex when using multiple chainstates (James O'Beirne)
0fd599a51a700c028d6f7ed8067d2d9f6e6a04a5 validation: have LoadBlockIndex account for snapshot use (James O'Beirne)
d0c6e61f5dd3b6af818459d9d03b7ba316c5a3f7 validation: don't modify genesis during snapshot load (James O'Beirne)

Pull request description:

  This is part of the [assumeutxo project](https://github.com/bitcoin/bitcoin/projects/11) (parent PR: #15606)

  ---

  Currently, `BlockManager::LoadBlockIndex` adds all blocks that have downloaded transactions to the active chain state's `setBlockIndexCandidates` set, ignoring the background chain state.

  This PR changes ChainstateManager::LoadBlockIndex to update `setBlockIndexCandidates` in the background chain, not just the active chain. In the active chain, the same blocks are added as before. In the background chain, only blocks that have actually been validated, not blocks marked assumed-valid are added so the background chain will continue to download and validate assumed-valid blocks.

ACKs for top commit:
  MarcoFalke:
    Concept ACK 2283b9cd1ee0fbd1e8ebc61673b1fe7596199a24 🤽
  Sjors:
    utACK 2283b9cd1ee0fbd1e8ebc61673b1fe7596199a24

Tree-SHA512: 7c9a80802df4722d85d12b78d2e7f628ac5f11cb8be66913d5c3230339bd1220c6723805509d4460826a17d1dc04b0ae172eb7d09ac0ea5dc5e41d77975cbd5e

3 files changed, 157 insertions, 18 deletions

diff --git a/src/test/validation_chainstatemanager_tests.cpp b/src/test/validation_chainstatemanager_tests.cpp
index a1f70e7e70..e6bd903b92 100644
--- a/src/test/validation_chainstatemanager_tests.cpp
+++ b/src/test/validation_chainstatemanager_tests.cpp
@@ -232,6 +232,9 @@ BOOST_FIXTURE_TEST_CASE(chainstatemanager_activate_snapshot, TestChain100Setup)
         *chainman.ActiveChainstate().m_from_snapshot_blockhash,
         *chainman.SnapshotBlockhash());
 
+    // Ensure that the genesis block was not marked assumed-valid.
+    BOOST_CHECK(!chainman.ActiveChain().Genesis()->IsAssumedValid());
+
     const AssumeutxoData& au_data = *ExpectedAssumeutxo(snapshot_height, ::Params());
     const CBlockIndex* tip = chainman.ActiveTip();
 
@@ -309,4 +312,81 @@ BOOST_FIXTURE_TEST_CASE(chainstatemanager_activate_snapshot, TestChain100Setup)
         loaded_snapshot_blockhash);
 }
 
+//! Test LoadBlockIndex behavior when multiple chainstates are in use.
+//!
+//! - First, verfiy that setBlockIndexCandidates is as expected when using a single,
+//!   fully-validating chainstate.
+//!
+//! - Then mark a region of the chain BLOCK_ASSUMED_VALID and introduce a second chainstate
+//!   that will tolerate assumed-valid blocks. Run LoadBlockIndex() and ensure that the first
+//!   chainstate only contains fully validated blocks and the other chainstate contains all blocks,
+//!   even those assumed-valid.
+//!
+BOOST_FIXTURE_TEST_CASE(chainstatemanager_loadblockindex, TestChain100Setup)
+{
+    ChainstateManager& chainman = *Assert(m_node.chainman);
+    CTxMemPool& mempool = *m_node.mempool;
+    CChainState& cs1 = chainman.ActiveChainstate();
+
+    int num_indexes{0};
+    int num_assumed_valid{0};
+    const int expected_assumed_valid{20};
+    const int last_assumed_valid_idx{40};
+    const int assumed_valid_start_idx = last_assumed_valid_idx - expected_assumed_valid;
+
+    CBlockIndex* validated_tip{nullptr};
+    CBlockIndex* assumed_tip{chainman.ActiveChain().Tip()};
+
+    auto reload_all_block_indexes = [&]() {
+        for (CChainState* cs : chainman.GetAll()) {
+            LOCK(::cs_main);
+            cs->UnloadBlockIndex();
+            BOOST_CHECK(cs->setBlockIndexCandidates.empty());
+        }
+
+        WITH_LOCK(::cs_main, chainman.LoadBlockIndex());
+    };
+
+    // Ensure that without any assumed-valid BlockIndex entries, all entries are considered
+    // tip candidates.
+    reload_all_block_indexes();
+    BOOST_CHECK_EQUAL(cs1.setBlockIndexCandidates.size(), cs1.m_chain.Height() + 1);
+
+    // Mark some region of the chain assumed-valid.
+    for (int i = 0; i <= cs1.m_chain.Height(); ++i) {
+        auto index = cs1.m_chain[i];
+
+        if (i < last_assumed_valid_idx && i >= assumed_valid_start_idx) {
+            index->nStatus = BlockStatus::BLOCK_VALID_TREE | BlockStatus::BLOCK_ASSUMED_VALID;
+        }
+
+        ++num_indexes;
+        if (index->IsAssumedValid()) ++num_assumed_valid;
+
+        // Note the last fully-validated block as the expected validated tip.
+        if (i == (assumed_valid_start_idx - 1)) {
+            validated_tip = index;
+            BOOST_CHECK(!index->IsAssumedValid());
+        }
+    }
+
+    BOOST_CHECK_EQUAL(expected_assumed_valid, num_assumed_valid);
+
+    CChainState& cs2 = WITH_LOCK(::cs_main,
+        return chainman.InitializeChainstate(&mempool, GetRandHash()));
+
+    reload_all_block_indexes();
+
+    // The fully validated chain only has candidates up to the start of the assumed-valid
+    // blocks.
+    BOOST_CHECK_EQUAL(cs1.setBlockIndexCandidates.count(validated_tip), 1);
+    BOOST_CHECK_EQUAL(cs1.setBlockIndexCandidates.count(assumed_tip), 0);
+    BOOST_CHECK_EQUAL(cs1.setBlockIndexCandidates.size(), assumed_valid_start_idx);
+
+    // The assumed-valid tolerant chain has all blocks as candidates.
+    BOOST_CHECK_EQUAL(cs2.setBlockIndexCandidates.count(validated_tip), 1);
+    BOOST_CHECK_EQUAL(cs2.setBlockIndexCandidates.count(assumed_tip), 1);
+    BOOST_CHECK_EQUAL(cs2.setBlockIndexCandidates.size(), num_indexes);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
index 861831444a..1aac71fb0f 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -55,6 +55,7 @@
 #include <validationinterface.h>
 #include <warnings.h>
 
+#include <algorithm>
 #include <numeric>
 #include <optional>
 #include <string>
@@ -3694,7 +3695,7 @@ CBlockIndex * BlockManager::InsertBlockIndex(const uint256& hash)
 
 bool BlockManager::LoadBlockIndex(
     const Consensus::Params& consensus_params,
-    std::set<CBlockIndex*, CBlockIndexWorkComparator>& block_index_candidates)
+    ChainstateManager& chainman)
 {
     if (!m_block_tree_db->LoadBlockIndexGuts(consensus_params, [this](const uint256& hash) EXCLUSIVE_LOCKS_REQUIRED(cs_main) { return this->InsertBlockIndex(hash); })) {
         return false;
@@ -3709,17 +3710,41 @@ bool BlockManager::LoadBlockIndex(
         vSortedByHeight.push_back(std::make_pair(pindex->nHeight, pindex));
     }
     sort(vSortedByHeight.begin(), vSortedByHeight.end());
+
+    // Find start of assumed-valid region.
+    int first_assumed_valid_height = std::numeric_limits<int>::max();
+
+    for (const auto& [height, block] : vSortedByHeight) {
+        if (block->IsAssumedValid()) {
+            auto chainstates = chainman.GetAll();
+
+            // If we encounter an assumed-valid block index entry, ensure that we have
+            // one chainstate that tolerates assumed-valid entries and another that does
+            // not (i.e. the background validation chainstate), since assumed-valid
+            // entries should always be pending validation by a fully-validated chainstate.
+            auto any_chain = [&](auto fnc) { return std::any_of(chainstates.cbegin(), chainstates.cend(), fnc); };
+            assert(any_chain([](auto chainstate) { return chainstate->reliesOnAssumedValid(); }));
+            assert(any_chain([](auto chainstate) { return !chainstate->reliesOnAssumedValid(); }));
+
+            first_assumed_valid_height = height;
+            break;
+        }
+    }
+
     for (const std::pair<int, CBlockIndex*>& item : vSortedByHeight)
     {
         if (ShutdownRequested()) return false;
         CBlockIndex* pindex = item.second;
         pindex->nChainWork = (pindex->pprev ? pindex->pprev->nChainWork : 0) + GetBlockProof(*pindex);
         pindex->nTimeMax = (pindex->pprev ? std::max(pindex->pprev->nTimeMax, pindex->nTime) : pindex->nTime);
-        // We can link the chain of blocks for which we've received transactions at some point.
+
+        // We can link the chain of blocks for which we've received transactions at some point, or
+        // blocks that are assumed-valid on the basis of snapshot load (see
+        // PopulateAndValidateSnapshot()).
         // Pruned nodes may have deleted the block.
         if (pindex->nTx > 0) {
             if (pindex->pprev) {
-                if (pindex->pprev->HaveTxsDownloaded()) {
+                if (pindex->pprev->nChainTx > 0) {
                     pindex->nChainTx = pindex->pprev->nChainTx + pindex->nTx;
                 } else {
                     pindex->nChainTx = 0;
@@ -3736,7 +3761,36 @@ bool BlockManager::LoadBlockIndex(
         if (pindex->IsAssumedValid() ||
                 (pindex->IsValid(BLOCK_VALID_TRANSACTIONS) &&
                  (pindex->HaveTxsDownloaded() || pindex->pprev == nullptr))) {
-            block_index_candidates.insert(pindex);
+
+            // Fill each chainstate's block candidate set. Only add assumed-valid
+            // blocks to the tip candidate set if the chainstate is allowed to rely on
+            // assumed-valid blocks.
+            //
+            // If all setBlockIndexCandidates contained the assumed-valid blocks, the
+            // background chainstate's ActivateBestChain() call would add assumed-valid
+            // blocks to the chain (based on how FindMostWorkChain() works). Obviously
+            // we don't want this since the purpose of the background validation chain
+            // is to validate assued-valid blocks.
+            //
+            // Note: This is considering all blocks whose height is greater or equal to
+            // the first assumed-valid block to be assumed-valid blocks, and excluding
+            // them from the background chainstate's setBlockIndexCandidates set. This
+            // does mean that some blocks which are not technically assumed-valid
+            // (later blocks on a fork beginning before the first assumed-valid block)
+            // might not get added to the the background chainstate, but this is ok,
+            // because they will still be attached to the active chainstate if they
+            // actually contain more work.
+            //
+            // Instad of this height-based approach, an earlier attempt was made at
+            // detecting "holistically" whether the block index under consideration
+            // relied on an assumed-valid ancestor, but this proved to be too slow to
+            // be practical.
+            for (CChainState* chainstate : chainman.GetAll()) {
+                if (chainstate->reliesOnAssumedValid() ||
+                        pindex->nHeight < first_assumed_valid_height) {
+                    chainstate->setBlockIndexCandidates.insert(pindex);
+                }
+            }
         }
         if (pindex->nStatus & BLOCK_FAILED_MASK && (!pindexBestInvalid || pindex->nChainWork > pindexBestInvalid->nChainWork))
             pindexBestInvalid = pindex;
@@ -3760,11 +3814,9 @@ void BlockManager::Unload() {
     m_block_index.clear();
 }
 
-bool BlockManager::LoadBlockIndexDB(std::set<CBlockIndex*, CBlockIndexWorkComparator>& setBlockIndexCandidates)
+bool BlockManager::LoadBlockIndexDB(ChainstateManager& chainman)
 {
-    if (!LoadBlockIndex(
-            ::Params().GetConsensus(),
-            setBlockIndexCandidates)) {
+    if (!LoadBlockIndex(::Params().GetConsensus(), chainman)) {
         return false;
     }
 
@@ -4110,7 +4162,7 @@ bool ChainstateManager::LoadBlockIndex()
     // Load block index from databases
     bool needs_init = fReindex;
     if (!fReindex) {
-        bool ret = m_blockman.LoadBlockIndexDB(ActiveChainstate().setBlockIndexCandidates);
+        bool ret = m_blockman.LoadBlockIndexDB(*this);
         if (!ret) return false;
         needs_init = m_blockman.m_block_index.empty();
     }
@@ -4999,7 +5051,14 @@ bool ChainstateManager::PopulateAndValidateSnapshot(
 
     // Fake various pieces of CBlockIndex state:
     CBlockIndex* index = nullptr;
-    for (int i = 0; i <= snapshot_chainstate.m_chain.Height(); ++i) {
+
+    // Don't make any modifications to the genesis block.
+    // This is especially important because we don't want to erroneously
+    // apply BLOCK_ASSUMED_VALID to genesis, which would happen if we didn't skip
+    // it here (since it apparently isn't BLOCK_VALID_SCRIPTS).
+    constexpr int AFTER_GENESIS_START{1};
+
+    for (int i = AFTER_GENESIS_START; i <= snapshot_chainstate.m_chain.Height(); ++i) {
         index = snapshot_chainstate.m_chain[i];
 
         // Fake nTx so that LoadBlockIndex() loads assumed-valid CBlockIndex
@@ -5008,7 +5067,7 @@ bool ChainstateManager::PopulateAndValidateSnapshot(
             index->nTx = 1;
         }
         // Fake nChainTx so that GuessVerificationProgress reports accurately
-        index->nChainTx = index->pprev ? index->pprev->nChainTx + index->nTx : 1;
+        index->nChainTx = index->pprev->nChainTx + index->nTx;
 
         // Mark unvalidated block index entries beneath the snapshot base block as assumed-valid.
         if (!index->IsValid(BLOCK_VALID_SCRIPTS)) {
@@ -5019,7 +5078,7 @@ bool ChainstateManager::PopulateAndValidateSnapshot(
 
         // Fake BLOCK_OPT_WITNESS so that CChainState::NeedsRedownload()
         // won't ask to rewind the entire assumed-valid chain on startup.
-        if (index->pprev && DeploymentActiveAt(*index, ::Params().GetConsensus(), Consensus::DEPLOYMENT_SEGWIT)) {
+        if (DeploymentActiveAt(*index, ::Params().GetConsensus(), Consensus::DEPLOYMENT_SEGWIT)) {
             index->nStatus |= BLOCK_OPT_WITNESS;
         }
 
diff --git a/src/validation.h b/src/validation.h
index 7457ca5239..534df9bc87 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -433,20 +433,16 @@ public:
 
     std::unique_ptr<CBlockTreeDB> m_block_tree_db GUARDED_BY(::cs_main);
 
-    bool LoadBlockIndexDB(std::set<CBlockIndex*, CBlockIndexWorkComparator>& setBlockIndexCandidates) EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
+    bool LoadBlockIndexDB(ChainstateManager& chainman) EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
 
     /**
      * Load the blocktree off disk and into memory. Populate certain metadata
      * per index entry (nStatus, nChainWork, nTimeMax, etc.) as well as peripheral
      * collections like setDirtyBlockIndex.
-     *
-     * @param[out] block_index_candidates  Fill this set with any valid blocks for
-     *                                     which we've downloaded all transactions.
      */
     bool LoadBlockIndex(
         const Consensus::Params& consensus_params,
-        std::set<CBlockIndex*, CBlockIndexWorkComparator>& block_index_candidates)
-        EXCLUSIVE_LOCKS_REQUIRED(cs_main);
+        ChainstateManager& chainman) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
     /** Clear all data members. */
     void Unload() EXCLUSIVE_LOCKS_REQUIRED(cs_main);
@@ -626,6 +622,10 @@ public:
      */
     const std::optional<uint256> m_from_snapshot_blockhash;
 
+    //! Return true if this chainstate relies on blocks that are assumed-valid. In
+    //! practice this means it was created based on a UTXO snapshot.
+    bool reliesOnAssumedValid() { return m_from_snapshot_blockhash.has_value(); }
+
     /**
      * The set of all CBlockIndex entries with either BLOCK_VALID_TRANSACTIONS (for
      * itself and all ancestors) *or* BLOCK_ASSUMED_VALID (if using background