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                 :            : #ifndef BITCOIN_HEADERSSYNC_H
       6                 :            : #define BITCOIN_HEADERSSYNC_H
       7                 :            : 
       8                 :            : #include <arith_uint256.h>
       9                 :            : #include <chain.h>
      10                 :            : #include <consensus/params.h>
      11                 :            : #include <net.h> // For NodeId
      12                 :            : #include <primitives/block.h>
      13                 :            : #include <uint256.h>
      14                 :            : #include <util/bitdeque.h>
      15                 :            : #include <util/hasher.h>
      16                 :            : 
      17                 :            : #include <deque>
      18                 :            : #include <vector>
      19                 :            : 
      20                 :            : // A compressed CBlockHeader, which leaves out the prevhash
      21                 :            : struct CompressedHeader {
      22                 :            :     // header
      23                 :          0 :     int32_t nVersion{0};
      24                 :            :     uint256 hashMerkleRoot;
      25                 :          0 :     uint32_t nTime{0};
      26                 :          0 :     uint32_t nBits{0};
      27                 :          0 :     uint32_t nNonce{0};
      28                 :            : 
      29                 :            :     CompressedHeader()
      30                 :            :     {
      31                 :            :         hashMerkleRoot.SetNull();
      32                 :            :     }
      33                 :            : 
      34                 :          0 :     CompressedHeader(const CBlockHeader& header)
      35                 :            :     {
      36                 :          0 :         nVersion = header.nVersion;
      37                 :          0 :         hashMerkleRoot = header.hashMerkleRoot;
      38                 :          0 :         nTime = header.nTime;
      39                 :          0 :         nBits = header.nBits;
      40                 :          0 :         nNonce = header.nNonce;
      41                 :          0 :     }
      42                 :            : 
      43                 :          0 :     CBlockHeader GetFullHeader(const uint256& hash_prev_block) {
      44                 :          0 :         CBlockHeader ret;
      45                 :          0 :         ret.nVersion = nVersion;
      46                 :          0 :         ret.hashPrevBlock = hash_prev_block;
      47                 :          0 :         ret.hashMerkleRoot = hashMerkleRoot;
      48                 :          0 :         ret.nTime = nTime;
      49                 :          0 :         ret.nBits = nBits;
      50                 :          0 :         ret.nNonce = nNonce;
      51                 :          0 :         return ret;
      52                 :            :     };
      53                 :            : };
      54                 :            : 
      55                 :            : /** HeadersSyncState:
      56                 :            :  *
      57                 :            :  * We wish to download a peer's headers chain in a DoS-resistant way.
      58                 :            :  *
      59                 :            :  * The Bitcoin protocol does not offer an easy way to determine the work on a
      60                 :            :  * peer's chain. Currently, we can query a peer's headers by using a GETHEADERS
      61                 :            :  * message, and our peer can return a set of up to 2000 headers that connect to
      62                 :            :  * something we know. If a peer's chain has more than 2000 blocks, then we need
      63                 :            :  * a way to verify that the chain actually has enough work on it to be useful to
      64                 :            :  * us -- by being above our anti-DoS minimum-chain-work threshold -- before we
      65                 :            :  * commit to storing those headers in memory. Otherwise, it would be cheap for
      66                 :            :  * an attacker to waste all our memory by serving us low-work headers
      67                 :            :  * (particularly for a new node coming online for the first time).
      68                 :            :  *
      69                 :            :  * To prevent memory-DoS with low-work headers, while still always being
      70                 :            :  * able to reorg to whatever the most-work chain is, we require that a chain
      71                 :            :  * meet a work threshold before committing it to memory. We can do this by
      72                 :            :  * downloading a peer's headers twice, whenever we are not sure that the chain
      73                 :            :  * has sufficient work:
      74                 :            :  *
      75                 :            :  * - In the first download phase, called pre-synchronization, we can calculate
      76                 :            :  * the work on the chain as we go (just by checking the nBits value on each
      77                 :            :  * header, and validating the proof-of-work).
      78                 :            :  *
      79                 :            :  * - Once we have reached a header where the cumulative chain work is
      80                 :            :  * sufficient, we switch to downloading the headers a second time, this time
      81                 :            :  * processing them fully, and possibly storing them in memory.
      82                 :            :  *
      83                 :            :  * To prevent an attacker from using (eg) the honest chain to convince us that
      84                 :            :  * they have a high-work chain, but then feeding us an alternate set of
      85                 :            :  * low-difficulty headers in the second phase, we store commitments to the
      86                 :            :  * chain we see in the first download phase that we check in the second phase,
      87                 :            :  * as follows:
      88                 :            :  *
      89                 :            :  * - In phase 1 (presync), store 1 bit (using a salted hash function) for every
      90                 :            :  * N headers that we see. With a reasonable choice of N, this uses relatively
      91                 :            :  * little memory even for a very long chain.
      92                 :            :  *
      93                 :            :  * - In phase 2 (redownload), keep a lookahead buffer and only accept headers
      94                 :            :  * from that buffer into the block index (permanent memory usage) once they
      95                 :            :  * have some target number of verified commitments on top of them. With this
      96                 :            :  * parametrization, we can achieve a given security target for potential
      97                 :            :  * permanent memory usage, while choosing N to minimize memory use during the
      98                 :            :  * sync (temporary, per-peer storage).
      99                 :            :  */
     100                 :            : 
     101                 :            : class HeadersSyncState {
     102                 :            : public:
     103                 :          0 :     ~HeadersSyncState() {}
     104                 :            : 
     105                 :            :     enum class State {
     106                 :            :         /** PRESYNC means the peer has not yet demonstrated their chain has
     107                 :            :          * sufficient work and we're only building commitments to the chain they
     108                 :            :          * serve us. */
     109                 :            :         PRESYNC,
     110                 :            :         /** REDOWNLOAD means the peer has given us a high-enough-work chain,
     111                 :            :          * and now we're redownloading the headers we saw before and trying to
     112                 :            :          * accept them */
     113                 :            :         REDOWNLOAD,
     114                 :            :         /** We're done syncing with this peer and can discard any remaining state */
     115                 :            :         FINAL
     116                 :            :     };
     117                 :            : 
     118                 :            :     /** Return the current state of our download */
     119                 :          0 :     State GetState() const { return m_download_state; }
     120                 :            : 
     121                 :            :     /** Return the height reached during the PRESYNC phase */
     122                 :          0 :     int64_t GetPresyncHeight() const { return m_current_height; }
     123                 :            : 
     124                 :            :     /** Return the block timestamp of the last header received during the PRESYNC phase. */
     125                 :          0 :     uint32_t GetPresyncTime() const { return m_last_header_received.nTime; }
     126                 :            : 
     127                 :            :     /** Return the amount of work in the chain received during the PRESYNC phase. */
     128                 :          0 :     arith_uint256 GetPresyncWork() const { return m_current_chain_work; }
     129                 :            : 
     130                 :            :     /** Construct a HeadersSyncState object representing a headers sync via this
     131                 :            :      *  download-twice mechanism).
     132                 :            :      *
     133                 :            :      * id: node id (for logging)
     134                 :            :      * consensus_params: parameters needed for difficulty adjustment validation
     135                 :            :      * chain_start: best known fork point that the peer's headers branch from
     136                 :            :      * minimum_required_work: amount of chain work required to accept the chain
     137                 :            :      */
     138                 :            :     HeadersSyncState(NodeId id, const Consensus::Params& consensus_params,
     139                 :            :             const CBlockIndex* chain_start, const arith_uint256& minimum_required_work);
     140                 :            : 
     141                 :            :     /** Result data structure for ProcessNextHeaders. */
     142                 :          0 :     struct ProcessingResult {
     143                 :            :         std::vector<CBlockHeader> pow_validated_headers;
     144                 :          0 :         bool success{false};
     145                 :          0 :         bool request_more{false};
     146                 :            :     };
     147                 :            : 
     148                 :            :     /** Process a batch of headers, once a sync via this mechanism has started
     149                 :            :      *
     150                 :            :      * received_headers: headers that were received over the network for processing.
     151                 :            :      *                   Assumes the caller has already verified the headers
     152                 :            :      *                   are continuous, and has checked that each header
     153                 :            :      *                   satisfies the proof-of-work target included in the
     154                 :            :      *                   header (but not necessarily verified that the
     155                 :            :      *                   proof-of-work target is correct and passes consensus
     156                 :            :      *                   rules).
     157                 :            :      * full_headers_message: true if the message was at max capacity,
     158                 :            :      *                       indicating more headers may be available
     159                 :            :      * ProcessingResult.pow_validated_headers: will be filled in with any
     160                 :            :      *                       headers that the caller can fully process and
     161                 :            :      *                       validate now (because these returned headers are
     162                 :            :      *                       on a chain with sufficient work)
     163                 :            :      * ProcessingResult.success: set to false if an error is detected and the sync is
     164                 :            :      *                       aborted; true otherwise.
     165                 :            :      * ProcessingResult.request_more: if true, the caller is suggested to call
     166                 :            :      *                       NextHeadersRequestLocator and send a getheaders message using it.
     167                 :            :      */
     168                 :            :     ProcessingResult ProcessNextHeaders(const std::vector<CBlockHeader>&
     169                 :            :             received_headers, bool full_headers_message);
     170                 :            : 
     171                 :            :     /** Issue the next GETHEADERS message to our peer.
     172                 :            :      *
     173                 :            :      * This will return a locator appropriate for the current sync object, to continue the
     174                 :            :      * synchronization phase it is in.
     175                 :            :      */
     176                 :            :     CBlockLocator NextHeadersRequestLocator() const;
     177                 :            : 
     178                 :            : protected:
     179                 :            :     /** The (secret) offset on the heights for which to create commitments.
     180                 :            :      *
     181                 :            :      * m_header_commitments entries are created at any height h for which
     182                 :            :      * (h % HEADER_COMMITMENT_PERIOD) == m_commit_offset. */
     183                 :            :     const unsigned m_commit_offset;
     184                 :            : 
     185                 :            : private:
     186                 :            :     /** Clear out all download state that might be in progress (freeing any used
     187                 :            :      * memory), and mark this object as no longer usable.
     188                 :            :      */
     189                 :            :     void Finalize();
     190                 :            : 
     191                 :            :     /**
     192                 :            :      *  Only called in PRESYNC.
     193                 :            :      *  Validate the work on the headers we received from the network, and
     194                 :            :      *  store commitments for later. Update overall state with successfully
     195                 :            :      *  processed headers.
     196                 :            :      *  On failure, this invokes Finalize() and returns false.
     197                 :            :      */
     198                 :            :     bool ValidateAndStoreHeadersCommitments(const std::vector<CBlockHeader>& headers);
     199                 :            : 
     200                 :            :     /** In PRESYNC, process and update state for a single header */
     201                 :            :     bool ValidateAndProcessSingleHeader(const CBlockHeader& current);
     202                 :            : 
     203                 :            :     /** In REDOWNLOAD, check a header's commitment (if applicable) and add to
     204                 :            :      * buffer for later processing */
     205                 :            :     bool ValidateAndStoreRedownloadedHeader(const CBlockHeader& header);
     206                 :            : 
     207                 :            :     /** Return a set of headers that satisfy our proof-of-work threshold */
     208                 :            :     std::vector<CBlockHeader> PopHeadersReadyForAcceptance();
     209                 :            : 
     210                 :            : private:
     211                 :            :     /** NodeId of the peer (used for log messages) **/
     212                 :            :     const NodeId m_id;
     213                 :            : 
     214                 :            :     /** We use the consensus params in our anti-DoS calculations */
     215                 :            :     const Consensus::Params& m_consensus_params;
     216                 :            : 
     217                 :            :     /** Store the last block in our block index that the peer's chain builds from */
     218                 :            :     const CBlockIndex* m_chain_start{nullptr};
     219                 :            : 
     220                 :            :     /** Minimum work that we're looking for on this chain. */
     221                 :            :     const arith_uint256 m_minimum_required_work;
     222                 :            : 
     223                 :            :     /** Work that we've seen so far on the peer's chain */
     224                 :            :     arith_uint256 m_current_chain_work;
     225                 :            : 
     226                 :            :     /** m_hasher is a salted hasher for making our 1-bit commitments to headers we've seen. */
     227                 :            :     const SaltedTxidHasher m_hasher;
     228                 :            : 
     229                 :            :     /** A queue of commitment bits, created during the 1st phase, and verified during the 2nd. */
     230                 :            :     bitdeque<> m_header_commitments;
     231                 :            : 
     232                 :            :     /** m_max_commitments is a bound we calculate on how long an honest peer's chain could be,
     233                 :            :      * given the MTP rule.
     234                 :            :      *
     235                 :            :      * Any peer giving us more headers than this will have its sync aborted. This serves as a
     236                 :            :      * memory bound on m_header_commitments. */
     237                 :            :     uint64_t m_max_commitments{0};
     238                 :            : 
     239                 :            :     /** Store the latest header received while in PRESYNC (initialized to m_chain_start) */
     240                 :            :     CBlockHeader m_last_header_received;
     241                 :            : 
     242                 :            :     /** Height of m_last_header_received */
     243                 :            :     int64_t m_current_height{0};
     244                 :            : 
     245                 :            :     /** During phase 2 (REDOWNLOAD), we buffer redownloaded headers in memory
     246                 :            :      *  until enough commitments have been verified; those are stored in
     247                 :            :      *  m_redownloaded_headers */
     248                 :            :     std::deque<CompressedHeader> m_redownloaded_headers;
     249                 :            : 
     250                 :            :     /** Height of last header in m_redownloaded_headers */
     251                 :            :     int64_t m_redownload_buffer_last_height{0};
     252                 :            : 
     253                 :            :     /** Hash of last header in m_redownloaded_headers (initialized to
     254                 :            :      * m_chain_start). We have to cache it because we don't have hashPrevBlock
     255                 :            :      * available in a CompressedHeader.
     256                 :            :      */
     257                 :            :     uint256 m_redownload_buffer_last_hash;
     258                 :            : 
     259                 :            :     /** The hashPrevBlock entry for the first header in m_redownloaded_headers
     260                 :            :      * We need this to reconstruct the full header when it's time for
     261                 :            :      * processing.
     262                 :            :      */
     263                 :            :     uint256 m_redownload_buffer_first_prev_hash;
     264                 :            : 
     265                 :            :     /** The accumulated work on the redownloaded chain. */
     266                 :            :     arith_uint256 m_redownload_chain_work;
     267                 :            : 
     268                 :            :     /** Set this to true once we encounter the target blockheader during phase
     269                 :            :      * 2 (REDOWNLOAD). At this point, we can process and store all remaining
     270                 :            :      * headers still in m_redownloaded_headers.
     271                 :            :      */
     272                 :            :     bool m_process_all_remaining_headers{false};
     273                 :            : 
     274                 :            :     /** Current state of our headers sync. */
     275                 :            :     State m_download_state{State::PRESYNC};
     276                 :            : };
     277                 :            : 
     278                 :            : #endif // BITCOIN_HEADERSSYNC_H