Inside Bitcoin

1// Copyright (c) 2022-present 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 <chain.h>
6#include <chainparams.h>
7#include <consensus/params.h>
8#include <headerssync.h>
9#include <net_processing.h>
10#include <pow.h>
11#include <test/util/common.h>
12#include <test/util/setup_common.h>
13#include <test/util/time.h>
14#include <validation.h>
15
16#include <cstddef>
17#include <vector>
18
19#include <boost/test/unit_test.hpp>
20
21using State = HeadersSyncState::State;
22
23// Standard set of checks common to all scenarios. Macro keeps failure lines at the call-site.
24#define CHECK_RESULT(result_expression, hss, exp_state, exp_success, exp_request_more,                   \
25                     exp_headers_size, exp_pow_validated_prev, exp_locator_hash)                         \
26    do {                                                                                                 \
27        const auto result{result_expression};                                                            \
28        BOOST_REQUIRE_EQUAL(hss.GetState(), exp_state);                                                  \
29        BOOST_CHECK_EQUAL(result.success, exp_success);                                                  \
30        BOOST_CHECK_EQUAL(result.request_more, exp_request_more);                                        \
31        BOOST_CHECK_EQUAL(result.pow_validated_headers.size(), exp_headers_size);                        \
32        const std::optional<uint256> pow_validated_prev_opt{exp_pow_validated_prev};                     \
33        if (pow_validated_prev_opt) {                                                                    \
34            BOOST_CHECK_EQUAL(result.pow_validated_headers.at(0).hashPrevBlock, pow_validated_prev_opt); \
35        } else {                                                                                         \
36            BOOST_CHECK_EQUAL(exp_headers_size, 0);                                                      \
37        }                                                                                                \
38        const std::optional<uint256> locator_hash_opt{exp_locator_hash};                                 \
39        if (locator_hash_opt) {                                                                          \
40            BOOST_CHECK_EQUAL(hss.NextHeadersRequestLocator().vHave.at(0), locator_hash_opt);            \
41        } else {                                                                                         \
42            BOOST_CHECK_EQUAL(exp_state, State::FINAL);                                                  \
43        }                                                                                                \
44    } while (false)
45
46constexpr size_t TARGET_BLOCKS{15'000};
47constexpr arith_uint256 CHAIN_WORK{TARGET_BLOCKS * 2};
48
49// Subtract MAX_HEADERS_RESULTS (2000 headers/message) + an arbitrary smaller
50// value (123) so our redownload buffer is well below the number of blocks
51// required to reach the CHAIN_WORK threshold, to behave similarly to mainnet.
52constexpr size_t REDOWNLOAD_BUFFER_SIZE{TARGET_BLOCKS - (MAX_HEADERS_RESULTS + 123)};
53constexpr size_t COMMITMENT_PERIOD{600}; // Somewhat close to mainnet.
54
55struct HeadersGeneratorSetup : public RegTestingSetup {
56    const CBlock& genesis{Params().GenesisBlock()};
57    CBlockIndex& chain_start{WITH_LOCK(::cs_main, return *Assert(m_node.chainman->m_blockman.LookupBlockIndex(genesis.GetHash())))};
58
59    // Generate headers for two different chains (using differing merkle roots
60    // to ensure the headers are different).
61    const std::vector<CBlockHeader>& FirstChain()
62    {
63        // Block header hash target is half of max uint256 (2**256 / 2), expressible
64        // roughly as the coefficient 0x7fffff with the exponent 0x20 (32 bytes).
65        // This implies around every 2nd hash attempt should succeed, which
66        // is why CHAIN_WORK == TARGET_BLOCKS * 2.
67        assert(genesis.nBits == 0x207fffff);
68
69        // Subtract 1 since the genesis block also contributes work so we reach
70        // the CHAIN_WORK target.
71        static const auto first_chain{GenerateHeaders(/*count=*/TARGET_BLOCKS - 1, genesis.GetHash(),
72                genesis.nVersion, genesis.nTime, /*merkle_root=*/uint256::ZERO, genesis.nBits)};
73        return first_chain;
74    }
75    const std::vector<CBlockHeader>& SecondChain()
76    {
77        // Subtract 2 to keep total work below the target.
78        static const auto second_chain{GenerateHeaders(/*count=*/TARGET_BLOCKS - 2, genesis.GetHash(),
79                genesis.nVersion, genesis.nTime, /*merkle_root=*/uint256::ONE, genesis.nBits)};
80        return second_chain;
81    }
82
83    HeadersSyncState CreateState()
84    {
85        return {/*id=*/0,
86                Params().GetConsensus(),
87                HeadersSyncParams{
88                    .commitment_period = COMMITMENT_PERIOD,
89                    .redownload_buffer_size = REDOWNLOAD_BUFFER_SIZE,
90                },
91                chain_start,
92                /*minimum_required_work=*/CHAIN_WORK};
93    }
94
95private:
96    /** Search for a nonce to meet (regtest) proof of work */
97    void FindProofOfWork(CBlockHeader& starting_header);
98    /**
99     * Generate headers in a chain that build off a given starting hash, using
100     * the given nVersion, advancing time by 1 second from the starting
101     * prev_time, and with a fixed merkle root hash.
102     */
103    std::vector<CBlockHeader> GenerateHeaders(size_t count,
104            uint256 prev_hash, int32_t nVersion, uint32_t prev_time,
105            const uint256& merkle_root, uint32_t nBits);
106};
107
108void HeadersGeneratorSetup::FindProofOfWork(CBlockHeader& starting_header)
109{
110    while (!CheckProofOfWork(starting_header.GetHash(), starting_header.nBits, Params().GetConsensus())) {
111        ++starting_header.nNonce;
112    }
113}
114
115std::vector<CBlockHeader> HeadersGeneratorSetup::GenerateHeaders(
116        const size_t count, uint256 prev_hash, const int32_t nVersion,
117        uint32_t prev_time, const uint256& merkle_root, const uint32_t nBits)
118{
119    std::vector<CBlockHeader> headers(count);
120    for (auto& next_header : headers) {
121        next_header.nVersion = nVersion;
122        next_header.hashPrevBlock = prev_hash;
123        next_header.hashMerkleRoot = merkle_root;
124        next_header.nTime = ++prev_time;
125        next_header.nBits = nBits;
126
127        FindProofOfWork(next_header);
128        prev_hash = next_header.GetHash();
129    }
130    return headers;
131}
132
133// In this test, we construct two sets of headers from genesis, one with
134// sufficient proof of work and one without.
135// 1. We deliver the first set of headers and verify that the headers sync state
136//    updates to the REDOWNLOAD phase successfully.
137//    Then we deliver the second set of headers and verify that they fail
138//    processing (presumably due to commitments not matching).
139// 2. Verify that repeating with the first set of headers in both phases is
140//    successful.
141// 3. Repeat the second set of headers in both phases to demonstrate behavior
142//    when the chain a peer provides has too little work.
143BOOST_FIXTURE_TEST_SUITE(headers_sync_chainwork_tests, HeadersGeneratorSetup)
144
145BOOST_AUTO_TEST_CASE(sneaky_redownload)
146{
147    const auto& first_chain{FirstChain()};
148    const auto& second_chain{SecondChain()};
149
150    // Feed the first chain to HeadersSyncState, by delivering 1 header
151    // initially and then the rest.
152    HeadersSyncState hss{CreateState()};
153
154    // Just feed one header and check state.
155    // Pretend the message is still "full", so we don't abort.
156    CHECK_RESULT(hss.ProcessNextHeaders({{first_chain.front()}}, /*full_headers_message=*/true),
157        hss, /*exp_state=*/State::PRESYNC,
158        /*exp_success=*/true, /*exp_request_more=*/true,
159        /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
160        /*exp_locator_hash=*/first_chain.front().GetHash());
161
162    // This chain should look valid, and we should have met the proof-of-work
163    // requirement during PRESYNC and transitioned to REDOWNLOAD.
164    CHECK_RESULT(hss.ProcessNextHeaders(std::span{first_chain}.subspan(1), true),
165        hss, /*exp_state=*/State::REDOWNLOAD,
166        /*exp_success=*/true, /*exp_request_more=*/true,
167        /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
168        /*exp_locator_hash=*/genesis.GetHash());
169
170    // Below is the number of commitment bits that must randomly match between
171    // the two chains for this test to spuriously fail. 1 / 2^25 =
172    // 1 in 33'554'432 (somewhat less due to HeadersSyncState::m_commit_offset).
173    static_assert(TARGET_BLOCKS / COMMITMENT_PERIOD == 25);
174
175    // Try to sneakily feed back the second chain during REDOWNLOAD.
176    CHECK_RESULT(hss.ProcessNextHeaders(second_chain, true),
177        hss, /*exp_state=*/State::FINAL,
178        /*exp_success=*/false, // Foiled! We detected mismatching headers.
179        /*exp_request_more=*/false,
180        /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
181        /*exp_locator_hash=*/std::nullopt);
182}
183
184BOOST_AUTO_TEST_CASE(happy_path)
185{
186    const auto& first_chain{FirstChain()};
187
188    // Headers message that moves us to the next state doesn't need to be full.
189    for (const bool full_headers_message : {false, true}) {
190        // This time we feed the first chain twice.
191        HeadersSyncState hss{CreateState()};
192
193        // Sufficient work transitions us from PRESYNC to REDOWNLOAD:
194        const auto genesis_hash{genesis.GetHash()};
195        CHECK_RESULT(hss.ProcessNextHeaders(first_chain, full_headers_message),
196            hss, /*exp_state=*/State::REDOWNLOAD,
197            /*exp_success=*/true, /*exp_request_more=*/true,
198            /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
199            /*exp_locator_hash=*/genesis_hash);
200
201        // Process only so that the internal threshold isn't exceeded, meaning
202        // validated headers shouldn't be returned yet:
203        CHECK_RESULT(hss.ProcessNextHeaders({first_chain.begin(), REDOWNLOAD_BUFFER_SIZE}, true),
204            hss, /*exp_state=*/State::REDOWNLOAD,
205            /*exp_success=*/true, /*exp_request_more=*/true,
206            /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
207            /*exp_locator_hash=*/first_chain[REDOWNLOAD_BUFFER_SIZE - 1].GetHash());
208
209        // We start receiving headers for permanent storage before completing:
210        CHECK_RESULT(hss.ProcessNextHeaders({{first_chain[REDOWNLOAD_BUFFER_SIZE]}}, true),
211            hss, /*exp_state=*/State::REDOWNLOAD,
212            /*exp_success=*/true, /*exp_request_more=*/true,
213            /*exp_headers_size=*/1, /*exp_pow_validated_prev=*/genesis_hash,
214            /*exp_locator_hash=*/first_chain[REDOWNLOAD_BUFFER_SIZE].GetHash());
215
216        // Feed in remaining headers, meeting the work threshold again and
217        // completing the REDOWNLOAD phase:
218        CHECK_RESULT(hss.ProcessNextHeaders({first_chain.begin() + REDOWNLOAD_BUFFER_SIZE + 1, first_chain.end()}, full_headers_message),
219            hss, /*exp_state=*/State::FINAL,
220            /*exp_success=*/true, /*exp_request_more=*/false,
221            // All headers except the one already returned above:
222            /*exp_headers_size=*/first_chain.size() - 1, /*exp_pow_validated_prev=*/first_chain.front().GetHash(),
223            /*exp_locator_hash=*/std::nullopt);
224    }
225}
226
227BOOST_AUTO_TEST_CASE(too_little_work)
228{
229    const auto& second_chain{SecondChain()};
230
231    // Verify that just trying to process the second chain would not succeed
232    // (too little work).
233    HeadersSyncState hss{CreateState()};
234    BOOST_REQUIRE_EQUAL(hss.GetState(), State::PRESYNC);
235
236    // Pretend just the first message is "full", so we don't abort.
237    CHECK_RESULT(hss.ProcessNextHeaders({{second_chain.front()}}, true),
238        hss, /*exp_state=*/State::PRESYNC,
239        /*exp_success=*/true, /*exp_request_more=*/true,
240        /*exp_headers_size=*/0, /*exp_pow_validated_prev=*/std::nullopt,
241        /*exp_locator_hash=*/second_chain.front().GetHash());
242
243    // Tell the sync logic that the headers message was not full, implying no
244    // more headers can be requested. For a low-work-chain, this should cause
245    // the sync to end with no headers for acceptance.
246    CHECK_RESULT(hss.ProcessNextHeaders(std::span{second_chain}.subspan(1), false),
247        hss, /*exp_state=*/State::FINAL,
248        // Nevertheless, no validation errors should have been detected with the
249        // chain:
250        /*exp_success=*/true,