LCOV - code coverage report
Current view: top level - src - headerssync.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 4 164 2.4 %
Date: 2023-10-05 12:38:51 Functions: 4 12 33.3 %
Branches: 3 256 1.2 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #include <headerssync.h>
       6                 :            : #include <logging.h>
       7                 :            : #include <pow.h>
       8                 :            : #include <timedata.h>
       9                 :            : #include <util/check.h>
      10                 :            : #include <util/vector.h>
      11                 :            : 
      12                 :            : // The two constants below are computed using the simulation script on
      13                 :            : // https://gist.github.com/sipa/016ae445c132cdf65a2791534dfb7ae1
      14                 :            : 
      15                 :            : //! Store a commitment to a header every HEADER_COMMITMENT_PERIOD blocks.
      16                 :            : constexpr size_t HEADER_COMMITMENT_PERIOD{584};
      17         [ +  - ]:          2 : 
      18         [ +  - ]:          2 : //! Only feed headers to validation once this many headers on top have been
      19                 :            : //! received and validated against commitments.
      20                 :            : constexpr size_t REDOWNLOAD_BUFFER_SIZE{13959}; // 13959/584 = ~23.9 commitments
      21                 :            : 
      22                 :            : // Our memory analysis assumes 48 bytes for a CompressedHeader (so we should
      23                 :            : // re-calculate parameters if we compress further)
      24                 :            : static_assert(sizeof(CompressedHeader) == 48);
      25                 :            : 
      26   [ #  #  #  #  :          0 : HeadersSyncState::HeadersSyncState(NodeId id, const Consensus::Params& consensus_params,
             #  #  #  # ]
      27                 :            :         const CBlockIndex* chain_start, const arith_uint256& minimum_required_work) :
      28                 :          0 :     m_commit_offset(GetRand<unsigned>(HEADER_COMMITMENT_PERIOD)),
      29                 :          0 :     m_id(id), m_consensus_params(consensus_params),
      30                 :          0 :     m_chain_start(chain_start),
      31                 :          0 :     m_minimum_required_work(minimum_required_work),
      32                 :          0 :     m_current_chain_work(chain_start->nChainWork),
      33         [ #  # ]:          0 :     m_last_header_received(m_chain_start->GetBlockHeader()),
      34                 :          0 :     m_current_height(chain_start->nHeight)
      35                 :            : {
      36                 :            :     // Estimate the number of blocks that could possibly exist on the peer's
      37                 :            :     // chain *right now* using 6 blocks/second (fastest blockrate given the MTP
      38                 :            :     // rule) times the number of seconds from the last allowed block until
      39                 :            :     // today. This serves as a memory bound on how many commitments we might
      40                 :            :     // store from this peer, and we can safely give up syncing if the peer
      41                 :            :     // exceeds this bound, because it's not possible for a consensus-valid
      42                 :            :     // chain to be longer than this (at the current time -- in the future we
      43                 :            :     // could try again, if necessary, to sync a longer chain).
      44   [ #  #  #  #  :          0 :     m_max_commitments = 6*(Ticks<std::chrono::seconds>(GetAdjustedTime() - NodeSeconds{std::chrono::seconds{chain_start->GetMedianTimePast()}}) + MAX_FUTURE_BLOCK_TIME) / HEADER_COMMITMENT_PERIOD;
          #  #  #  #  #  
                #  #  # ]
      45                 :            : 
      46   [ #  #  #  #  :          0 :     LogPrint(BCLog::NET, "Initial headers sync started with peer=%d: height=%i, max_commitments=%i, min_work=%s\n", m_id, m_current_height, m_max_commitments, m_minimum_required_work.ToString());
          #  #  #  #  #  
                #  #  # ]
      47                 :          0 : }
      48                 :            : 
      49                 :            : /** Free any memory in use, and mark this object as no longer usable. This is
      50                 :            :  * required to guarantee that we won't reuse this object with the same
      51                 :            :  * SaltedTxidHasher for another sync. */
      52                 :          0 : void HeadersSyncState::Finalize()
      53                 :            : {
      54                 :          0 :     Assume(m_download_state != State::FINAL);
      55                 :          0 :     ClearShrink(m_header_commitments);
      56                 :          0 :     m_last_header_received.SetNull();
      57                 :          0 :     ClearShrink(m_redownloaded_headers);
      58                 :          0 :     m_redownload_buffer_last_hash.SetNull();
      59                 :          0 :     m_redownload_buffer_first_prev_hash.SetNull();
      60                 :          0 :     m_process_all_remaining_headers = false;
      61                 :          0 :     m_current_height = 0;
      62                 :            : 
      63                 :          0 :     m_download_state = State::FINAL;
      64                 :          0 : }
      65                 :            : 
      66                 :            : /** Process the next batch of headers received from our peer.
      67                 :            :  *  Validate and store commitments, and compare total chainwork to our target to
      68                 :            :  *  see if we can switch to REDOWNLOAD mode.  */
      69                 :          0 : HeadersSyncState::ProcessingResult HeadersSyncState::ProcessNextHeaders(const
      70                 :            :         std::vector<CBlockHeader>& received_headers, const bool full_headers_message)
      71                 :            : {
      72                 :          0 :     ProcessingResult ret;
      73                 :            : 
      74         [ #  # ]:          2 :     Assume(!received_headers.empty());
      75         [ #  # ]:          0 :     if (received_headers.empty()) return ret;
      76                 :            : 
      77         [ #  # ]:          0 :     Assume(m_download_state != State::FINAL);
      78         [ #  # ]:          0 :     if (m_download_state == State::FINAL) return ret;
      79                 :            : 
      80         [ #  # ]:          0 :     if (m_download_state == State::PRESYNC) {
      81                 :            :         // During PRESYNC, we minimally validate block headers and
      82                 :            :         // occasionally add commitments to them, until we reach our work
      83         [ +  - ]:          2 :         // threshold (at which point m_download_state is updated to REDOWNLOAD).
      84         [ #  # ]:          0 :         ret.success = ValidateAndStoreHeadersCommitments(received_headers);
      85         [ #  # ]:          0 :         if (ret.success) {
      86   [ #  #  #  # ]:          0 :             if (full_headers_message || m_download_state == State::REDOWNLOAD) {
      87                 :            :                 // A full headers message means the peer may have more to give us;
      88                 :            :                 // also if we just switched to REDOWNLOAD then we need to re-request
      89                 :            :                 // headers from the beginning.
      90                 :          0 :                 ret.request_more = true;
      91                 :          0 :             } else {
      92         [ #  # ]:          0 :                 Assume(m_download_state == State::PRESYNC);
      93                 :            :                 // If we're in PRESYNC and we get a non-full headers
      94                 :            :                 // message, then the peer's chain has ended and definitely doesn't
      95                 :            :                 // have enough work, so we can stop our sync.
      96   [ #  #  #  #  :          0 :                 LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: incomplete headers message at height=%i (presync phase)\n", m_id, m_current_height);
          #  #  #  #  #  
                      # ]
      97                 :            :             }
      98                 :          0 :         }
      99         [ #  # ]:          0 :     } else if (m_download_state == State::REDOWNLOAD) {
     100                 :            :         // During REDOWNLOAD, we compare our stored commitments to what we
     101                 :            :         // receive, and add headers to our redownload buffer. When the buffer
     102                 :            :         // gets big enough (meaning that we've checked enough commitments),
     103                 :            :         // we'll return a batch of headers to the caller for processing.
     104                 :          0 :         ret.success = true;
     105         [ #  # ]:          0 :         for (const auto& hdr : received_headers) {
     106   [ #  #  #  # ]:          0 :             if (!ValidateAndStoreRedownloadedHeader(hdr)) {
     107                 :            :                 // Something went wrong -- the peer gave us an unexpected chain.
     108                 :            :                 // We could consider looking at the reason for failure and
     109                 :            :                 // punishing the peer, but for now just give up on sync.
     110                 :          0 :                 ret.success = false;
     111                 :          0 :                 break;
     112                 :            :             }
     113                 :            :         }
     114                 :            : 
     115         [ #  # ]:          0 :         if (ret.success) {
     116                 :            :             // Return any headers that are ready for acceptance.
     117         [ #  # ]:          0 :             ret.pow_validated_headers = PopHeadersReadyForAcceptance();
     118                 :            : 
     119                 :            :             // If we hit our target blockhash, then all remaining headers will be
     120                 :            :             // returned and we can clear any leftover internal state.
     121   [ #  #  #  # ]:          0 :             if (m_redownloaded_headers.empty() && m_process_all_remaining_headers) {
     122   [ #  #  #  #  :          0 :                 LogPrint(BCLog::NET, "Initial headers sync complete with peer=%d: releasing all at height=%i (redownload phase)\n", m_id, m_redownload_buffer_last_height);
          #  #  #  #  #  
                      # ]
     123         [ #  # ]:          0 :             } else if (full_headers_message) {
     124                 :            :                 // If the headers message is full, we need to request more.
     125                 :          0 :                 ret.request_more = true;
     126                 :          0 :             } else {
     127                 :            :                 // For some reason our peer gave us a high-work chain, but is now
     128                 :            :                 // declining to serve us that full chain again. Give up.
     129                 :            :                 // Note that there's no more processing to be done with these
     130                 :            :                 // headers, so we can still return success.
     131   [ #  #  #  #  :          0 :                 LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: incomplete headers message at height=%i (redownload phase)\n", m_id, m_redownload_buffer_last_height);
          #  #  #  #  #  
                      # ]
     132                 :            :             }
     133                 :          0 :         }
     134                 :          0 :     }
     135                 :            : 
     136   [ #  #  #  #  :          0 :     if (!(ret.success && ret.request_more)) Finalize();
                   #  # ]
     137                 :          0 :     return ret;
     138         [ #  # ]:          0 : }
     139                 :            : 
     140                 :          0 : bool HeadersSyncState::ValidateAndStoreHeadersCommitments(const std::vector<CBlockHeader>& headers)
     141                 :            : {
     142                 :            :     // The caller should not give us an empty set of headers.
     143                 :          0 :     Assume(headers.size() > 0);
     144         [ #  # ]:          0 :     if (headers.size() == 0) return true;
     145                 :            : 
     146                 :          0 :     Assume(m_download_state == State::PRESYNC);
     147         [ #  # ]:          0 :     if (m_download_state != State::PRESYNC) return false;
     148                 :            : 
     149         [ #  # ]:          0 :     if (headers[0].hashPrevBlock != m_last_header_received.GetHash()) {
     150                 :            :         // Somehow our peer gave us a header that doesn't connect.
     151                 :            :         // This might be benign -- perhaps our peer reorged away from the chain
     152                 :            :         // they were on. Give up on this sync for now (likely we will start a
     153                 :            :         // new sync with a new starting point).
     154   [ #  #  #  #  :          0 :         LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: non-continuous headers at height=%i (presync phase)\n", m_id, m_current_height);
             #  #  #  # ]
     155                 :          0 :         return false;
     156                 :            :     }
     157                 :            : 
     158                 :            :     // If it does connect, (minimally) validate and occasionally store
     159                 :            :     // commitments.
     160         [ #  # ]:          0 :     for (const auto& hdr : headers) {
     161         [ #  # ]:          0 :         if (!ValidateAndProcessSingleHeader(hdr)) {
     162                 :          0 :             return false;
     163                 :            :         }
     164                 :            :     }
     165                 :            : 
     166         [ #  # ]:          0 :     if (m_current_chain_work >= m_minimum_required_work) {
     167                 :          0 :         m_redownloaded_headers.clear();
     168                 :          0 :         m_redownload_buffer_last_height = m_chain_start->nHeight;
     169                 :          0 :         m_redownload_buffer_first_prev_hash = m_chain_start->GetBlockHash();
     170                 :          0 :         m_redownload_buffer_last_hash = m_chain_start->GetBlockHash();
     171                 :          0 :         m_redownload_chain_work = m_chain_start->nChainWork;
     172                 :          0 :         m_download_state = State::REDOWNLOAD;
     173   [ #  #  #  #  :          0 :         LogPrint(BCLog::NET, "Initial headers sync transition with peer=%d: reached sufficient work at height=%i, redownloading from height=%i\n", m_id, m_current_height, m_redownload_buffer_last_height);
             #  #  #  # ]
     174                 :          0 :     }
     175                 :          0 :     return true;
     176                 :          0 : }
     177                 :            : 
     178                 :          0 : bool HeadersSyncState::ValidateAndProcessSingleHeader(const CBlockHeader& current)
     179                 :            : {
     180                 :          0 :     Assume(m_download_state == State::PRESYNC);
     181         [ #  # ]:          0 :     if (m_download_state != State::PRESYNC) return false;
     182                 :            : 
     183                 :          0 :     int next_height = m_current_height + 1;
     184                 :            : 
     185                 :            :     // Verify that the difficulty isn't growing too fast; an adversary with
     186                 :            :     // limited hashing capability has a greater chance of producing a high
     187                 :            :     // work chain if they compress the work into as few blocks as possible,
     188                 :            :     // so don't let anyone give a chain that would violate the difficulty
     189                 :            :     // adjustment maximum.
     190   [ #  #  #  # ]:          0 :     if (!PermittedDifficultyTransition(m_consensus_params, next_height,
     191                 :          0 :                 m_last_header_received.nBits, current.nBits)) {
     192   [ #  #  #  #  :          0 :         LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (presync phase)\n", m_id, next_height);
             #  #  #  # ]
     193                 :          0 :         return false;
     194                 :            :     }
     195                 :            : 
     196         [ #  # ]:          0 :     if (next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
     197                 :            :         // Add a commitment.
     198                 :          0 :         m_header_commitments.push_back(m_hasher(current.GetHash()) & 1);
     199         [ #  # ]:          0 :         if (m_header_commitments.size() > m_max_commitments) {
     200                 :            :             // The peer's chain is too long; give up.
     201                 :            :             // It's possible the chain grew since we started the sync; so
     202                 :            :             // potentially we could succeed in syncing the peer's chain if we
     203                 :            :             // try again later.
     204   [ #  #  #  #  :          0 :             LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: exceeded max commitments at height=%i (presync phase)\n", m_id, next_height);
             #  #  #  # ]
     205                 :          0 :             return false;
     206                 :            :         }
     207                 :          0 :     }
     208                 :            : 
     209                 :          0 :     m_current_chain_work += GetBlockProof(CBlockIndex(current));
     210                 :          0 :     m_last_header_received = current;
     211                 :          0 :     m_current_height = next_height;
     212                 :            : 
     213                 :          0 :     return true;
     214                 :          0 : }
     215                 :            : 
     216                 :          0 : bool HeadersSyncState::ValidateAndStoreRedownloadedHeader(const CBlockHeader& header)
     217                 :            : {
     218                 :          0 :     Assume(m_download_state == State::REDOWNLOAD);
     219         [ #  # ]:          0 :     if (m_download_state != State::REDOWNLOAD) return false;
     220                 :            : 
     221                 :          0 :     int64_t next_height = m_redownload_buffer_last_height + 1;
     222                 :            : 
     223                 :            :     // Ensure that we're working on a header that connects to the chain we're
     224                 :            :     // downloading.
     225         [ #  # ]:          0 :     if (header.hashPrevBlock != m_redownload_buffer_last_hash) {
     226   [ #  #  #  #  :          0 :         LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: non-continuous headers at height=%i (redownload phase)\n", m_id, next_height);
             #  #  #  # ]
     227                 :          0 :         return false;
     228                 :            :     }
     229                 :            : 
     230                 :            :     // Check that the difficulty adjustments are within our tolerance:
     231                 :          0 :     uint32_t previous_nBits{0};
     232         [ #  # ]:          0 :     if (!m_redownloaded_headers.empty()) {
     233                 :          0 :         previous_nBits = m_redownloaded_headers.back().nBits;
     234                 :          0 :     } else {
     235                 :          0 :         previous_nBits = m_chain_start->nBits;
     236                 :            :     }
     237                 :          0 : 
     238   [ #  #  #  # ]:          0 :     if (!PermittedDifficultyTransition(m_consensus_params, next_height,
     239                 :          0 :                 previous_nBits, header.nBits)) {
     240   [ #  #  #  #  :          0 :         LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (redownload phase)\n", m_id, next_height);
             #  #  #  # ]
     241                 :          0 :         return false;
     242                 :            :     }
     243                 :            : 
     244                 :            :     // Track work on the redownloaded chain
     245                 :          0 :     m_redownload_chain_work += GetBlockProof(CBlockIndex(header));
     246                 :            : 
     247         [ #  # ]:          0 :     if (m_redownload_chain_work >= m_minimum_required_work) {
     248                 :          0 :         m_process_all_remaining_headers = true;
     249                 :          0 :     }
     250                 :            : 
     251                 :          0 :     // If we're at a header for which we previously stored a commitment, verify
     252                 :            :     // it is correct. Failure will result in aborting download.
     253                 :            :     // Also, don't check commitments once we've gotten to our target blockhash;
     254                 :            :     // it's possible our peer has extended its chain between our first sync and
     255                 :            :     // our second, and we don't want to return failure after we've seen our
     256                 :            :     // target blockhash just because we ran out of commitments.
     257   [ #  #  #  # ]:          0 :     if (!m_process_all_remaining_headers && next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
     258         [ #  # ]:          0 :         if (m_header_commitments.size() == 0) {
     259   [ #  #  #  #  :          0 :             LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: commitment overrun at height=%i (redownload phase)\n", m_id, next_height);
             #  #  #  # ]
     260                 :            :             // Somehow our peer managed to feed us a different chain and
     261                 :            :             // we've run out of commitments.
     262                 :          0 :             return false;
     263                 :            :         }
     264                 :          0 :         bool commitment = m_hasher(header.GetHash()) & 1;
     265                 :          0 :         bool expected_commitment = m_header_commitments.front();
     266                 :          0 :         m_header_commitments.pop_front();
     267         [ #  # ]:          0 :         if (commitment != expected_commitment) {
     268   [ #  #  #  #  :          0 :             LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: commitment mismatch at height=%i (redownload phase)\n", m_id, next_height);
             #  #  #  # ]
     269                 :          0 :             return false;
     270                 :            :         }
     271                 :          0 :     }
     272                 :          0 : 
     273                 :            :     // Store this header for later processing.
     274                 :          0 :     m_redownloaded_headers.push_back(header);
     275                 :          0 :     m_redownload_buffer_last_height = next_height;
     276                 :          0 :     m_redownload_buffer_last_hash = header.GetHash();
     277                 :            : 
     278                 :          0 :     return true;
     279                 :          0 : }
     280                 :            : 
     281                 :          0 : std::vector<CBlockHeader> HeadersSyncState::PopHeadersReadyForAcceptance()
     282                 :            : {
     283                 :          0 :     std::vector<CBlockHeader> ret;
     284                 :            : 
     285         [ #  # ]:          0 :     Assume(m_download_state == State::REDOWNLOAD);
     286         [ #  # ]:          0 :     if (m_download_state != State::REDOWNLOAD) return ret;
     287                 :            : 
     288   [ #  #  #  # ]:          0 :     while (m_redownloaded_headers.size() > REDOWNLOAD_BUFFER_SIZE ||
     289         [ #  # ]:          0 :             (m_redownloaded_headers.size() > 0 && m_process_all_remaining_headers)) {
     290   [ #  #  #  # ]:          0 :         ret.emplace_back(m_redownloaded_headers.front().GetFullHeader(m_redownload_buffer_first_prev_hash));
     291                 :          0 :         m_redownloaded_headers.pop_front();
     292         [ #  # ]:          0 :         m_redownload_buffer_first_prev_hash = ret.back().GetHash();
     293                 :            :     }
     294                 :          0 :     return ret;
     295         [ #  # ]:          0 : }
     296                 :            : 
     297                 :          0 : CBlockLocator HeadersSyncState::NextHeadersRequestLocator() const
     298                 :            : {
     299                 :          0 :     Assume(m_download_state != State::FINAL);
     300         [ #  # ]:          0 :     if (m_download_state == State::FINAL) return {};
     301                 :            : 
     302                 :          0 :     auto chain_start_locator = LocatorEntries(m_chain_start);
     303                 :          0 :     std::vector<uint256> locator;
     304                 :            : 
     305         [ #  # ]:          0 :     if (m_download_state == State::PRESYNC) {
     306                 :            :         // During pre-synchronization, we continue from the last header received.
     307   [ #  #  #  # ]:          0 :         locator.push_back(m_last_header_received.GetHash());
     308                 :          0 :     }
     309                 :            : 
     310         [ #  # ]:          0 :     if (m_download_state == State::REDOWNLOAD) {
     311                 :            :         // During redownload, we will download from the last received header that we stored.
     312         [ #  # ]:          0 :         locator.push_back(m_redownload_buffer_last_hash);
     313                 :          0 :     }
     314                 :            : 
     315         [ #  # ]:          0 :     locator.insert(locator.end(), chain_start_locator.begin(), chain_start_locator.end());
     316                 :            : 
     317         [ #  # ]:          0 :     return CBlockLocator{std::move(locator)};
     318                 :          0 : }

Generated by: LCOV version 1.14