READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server440 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

11,371 bytes · SHA-256 9eec53e04cf2a5a6… · View upstream ↗

1// Copyright (c) 2014-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 <test/util/random.h>
7#include <test/util/setup_common.h>
8
9#include <algorithm>
10#include <vector>
11#include <utility>
12
13#include <boost/test/unit_test.hpp>
14
15#define SKIPLIST_LENGTH 300000
16
17BOOST_FIXTURE_TEST_SUITE(skiplist_tests, BasicTestingSetup)
18
19BOOST_AUTO_TEST_CASE(skiplist_test)
20{
21    std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
22
23    for (int i=0; i<SKIPLIST_LENGTH; i++) {
24        vIndex[i].nHeight = i;
25        vIndex[i].pprev = (i == 0) ? nullptr : &vIndex[i - 1];
26        vIndex[i].BuildSkip();
27    }
28
29    for (int i=0; i<SKIPLIST_LENGTH; i++) {
30        if (i > 0) {
31            BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
32            BOOST_CHECK(vIndex[i].pskip->nHeight < i);
33        } else {
34            BOOST_CHECK(vIndex[i].pskip == nullptr);
35        }
36    }
37
38    for (int i=0; i < 1000; i++) {
39        int from = m_rng.randrange(SKIPLIST_LENGTH - 1);
40        int to = m_rng.randrange(from + 1);
41
42        BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
43        BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
44        BOOST_CHECK(vIndex[from].GetAncestor(0) == vIndex.data());
45    }
46}
47
48BOOST_AUTO_TEST_CASE(getlocator_test)
49{
50    // Build a main chain 100000 blocks long.
51    std::vector<uint256> vHashMain(100000);
52    std::vector<CBlockIndex> vBlocksMain(100000);
53    for (unsigned int i=0; i<vBlocksMain.size(); i++) {
54        vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
55        vBlocksMain[i].nHeight = i;
56        vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
57        vBlocksMain[i].phashBlock = &vHashMain[i];
58        vBlocksMain[i].BuildSkip();
59        BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
60        BOOST_CHECK(vBlocksMain[i].pprev == nullptr || vBlocksMain[i].nHeight == vBlocksMain[i].pprev->nHeight + 1);
61    }
62
63    // Build a branch that splits off at block 49999, 50000 blocks long.
64    std::vector<uint256> vHashSide(50000);
65    std::vector<CBlockIndex> vBlocksSide(50000);
66    for (unsigned int i=0; i<vBlocksSide.size(); i++) {
67        vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
68        vBlocksSide[i].nHeight = i + 50000;
69        vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : (vBlocksMain.data()+49999);
70        vBlocksSide[i].phashBlock = &vHashSide[i];
71        vBlocksSide[i].BuildSkip();
72        BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
73        BOOST_CHECK(vBlocksSide[i].pprev == nullptr || vBlocksSide[i].nHeight == vBlocksSide[i].pprev->nHeight + 1);
74    }
75
76    // Build a CChain for the main branch.
77    CChain chain;
78    chain.SetTip(vBlocksMain.back());
79
80    // Test 100 random starting points for locators.
81    for (int n=0; n<100; n++) {
82        int r = m_rng.randrange(150000);
83        CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
84        CBlockLocator locator = GetLocator(tip);
85
86        // The first result must be the block itself, the last one must be genesis.
87        BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
88        BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
89
90        // Entries 1 through 11 (inclusive) go back one step each.
91        for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
92            BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i]).GetLow64(), tip->nHeight - i);
93        }
94
95        // The further ones (excluding the last one) go back with exponential steps.
96        unsigned int dist = 2;
97        for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
98            BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
99            dist *= 2;
100        }
101    }
102}
103
104BOOST_AUTO_TEST_CASE(findearliestatleast_test)
105{
106    std::vector<uint256> vHashMain(100000);
107    std::vector<CBlockIndex> vBlocksMain(100000);
108    for (unsigned int i=0; i<vBlocksMain.size(); i++) {
109        vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
110        vBlocksMain[i].nHeight = i;
111        vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
112        vBlocksMain[i].phashBlock = &vHashMain[i];
113        vBlocksMain[i].BuildSkip();
114        if (i < 10) {
115            vBlocksMain[i].nTime = i;
116            vBlocksMain[i].nTimeMax = i;
117        } else {
118            // randomly choose something in the range [MTP, MTP*2]
119            int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
120            int r{int(m_rng.randrange(medianTimePast))};
121            vBlocksMain[i].nTime = uint32_t(r + medianTimePast);
122            vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
123        }
124    }
125    // Check that we set nTimeMax up correctly.
126    unsigned int curTimeMax = 0;
127    for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
128        curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
129        BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
130    }
131
132    // Build a CChain for the main branch.
133    CChain chain;
134    chain.SetTip(vBlocksMain.back());
135
136    // Verify that FindEarliestAtLeast is correct.
137    for (unsigned int i=0; i<10000; ++i) {
138        // Pick a random element in vBlocksMain.
139        int r = m_rng.randrange(vBlocksMain.size());
140        int64_t test_time = vBlocksMain[r].nTime;
141        CBlockIndex* ret = chain.FindEarliestAtLeast(test_time, 0);
142        BOOST_CHECK(ret->nTimeMax >= test_time);
143        BOOST_CHECK((ret->pprev==nullptr) || ret->pprev->nTimeMax < test_time);
144        BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
145    }
146}
147
148BOOST_AUTO_TEST_CASE(findearliestatleast_edge_test)
149{
150    std::list<CBlockIndex> blocks;
151    for (const unsigned int timeMax : {100, 100, 100, 200, 200, 200, 300, 300, 300}) {
152        CBlockIndex* prev = blocks.empty() ? nullptr : &blocks.back();
153        blocks.emplace_back();
154        blocks.back().nHeight = prev ? prev->nHeight + 1 : 0;
155        blocks.back().pprev = prev;
156        blocks.back().BuildSkip();
157        blocks.back().nTimeMax = timeMax;
158    }
159
160    CChain chain;
161    chain.SetTip(blocks.back());
162
163    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50, 0)->nHeight, 0);
164    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100, 0)->nHeight, 0);
165    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150, 0)->nHeight, 3);
166    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200, 0)->nHeight, 3);
167    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250, 0)->nHeight, 6);
168    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300, 0)->nHeight, 6);
169    BOOST_CHECK(!chain.FindEarliestAtLeast(350, 0));
170
171    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
172    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1, 0)->nHeight, 0);
173
174    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::min(), 0)->nHeight, 0);
175    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits<unsigned int>::max()) - 1, 0)->nHeight, 0);
176    BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::max(), 0));
177    BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::max(), 0));
178    BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits<unsigned int>::max()) + 1, 0));
179
180    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, -1)->nHeight, 0);
181    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
182    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 3)->nHeight, 3);
183    BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 8)->nHeight, 8);
184    BOOST_CHECK(!chain.FindEarliestAtLeast(0, 9));
185
186    CBlockIndex* ret1 = chain.FindEarliestAtLeast(100, 2);
187    BOOST_CHECK(ret1->nTimeMax >= 100);
188    BOOST_CHECK(ret1->nHeight == 2);
189    BOOST_CHECK(!chain.FindEarliestAtLeast(300, 9));
190    CBlockIndex* ret2 = chain.FindEarliestAtLeast(200, 4);
191    BOOST_CHECK(ret2->nTimeMax >= 200);
192    BOOST_CHECK(ret2->nHeight == 4);
193}
194
195BOOST_AUTO_TEST_CASE(build_skip_height_test)
196{
197    // clang-format off
198    const std::pair<int, int> TEST_DATA[]{
199        // EVEN values: the rightmost set bit is zeroed
200        // Various even values with at least 2 bits set
201        { 0b00010010 ,
202          0b00010000 },
203        { 0b00100010 ,
204          0b00100000 },
205        { 0b01000010 ,
206          0b01000000 },
207        { 0b00010100 ,
208          0b00010000 },
209        { 0b00011000 ,
210          0b00010000 },
211        { 0b10101010 ,
212          0b10101000 },
213        // ODD values: the 2nd and 3rd set bits are zeroed
214        // Various odd values with at least 4 bits set
215        { 0b10010011 ,
216          0b10000001 },
217        { 0b10100011 ,
218          0b10000001 },
219        { 0b11000011 ,
220          0b10000001 },
221        { 0b10010101 ,
222          0b10000001 },
223        { 0b10011001 ,
224          0b10000001 },
225        { 0b10101011 ,
226          0b10100001 },
227        // Some longer random values (even and odd)
228        { 0b0001011101101000 ,
229          0b0001011101100000 },
230        { 0b0001011101101001 ,
231          0b0001011101000001 },
232        { 0b0110101101011000 ,
233          0b0110101101010000 },
234        { 0b0110101101011001 ,
235          0b0110101101000001 },
236        // All values 1-20
237        {  1,  0 },
238        {  2,  0 },
239        {  3,  1 },
240        {  4,  0 },
241        {  5,  1 },
242        {  6,  4 },
243        {  7,  1 },
244        {  8,  0 },
245        {  9,  1 },
246        { 10,  8 },
247        { 11,  1 },
248        { 12,  8 },
249        { 13,  1 },
250        { 14, 12 },

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

src/clientversion.cpp

src/common/signmessage.cpp

src/compat/assumptions.h

src/compat/byteswap.h

src/deploymentinfo.cpp

src/deploymentinfo.h

src/deploymentstatus.cpp

src/deploymentstatus.h

src/dummywallet.cpp

src/external_signer.h

src/init/bitcoin-gui.cpp

src/init/bitcoin-node.cpp

src/init/bitcoin-qt.cpp

src/init/bitcoin-wallet.cpp

src/init/bitcoind.cpp

src/init/common.h

src/interfaces/init.h

src/interfaces/ipc.h

src/key_io.h

src/logging/categories.h

src/logging/timer.h

src/mapport.h

src/musig.h

src/net_permissions.h

src/netgroup.h

src/netmessagemaker.h

src/node/chainstatemanager_args.cpp

src/node/connection_types.h

src/node/context.h

src/node/interface_ui.h

src/node/mempool_args.cpp

src/node/mining_args.cpp

src/node/minisketchwrapper.cpp

src/node/txreconciliation.h

src/policy/fees/estimator_args.cpp

src/policy/fees/estimator_args.h

src/policy/fees/estimator_man.cpp

src/policy/fees/estimator_man.h

src/policy/packages.h

src/policy/rbf.h

src/policy/truc_policy.h

src/pow.h

src/primitives/block.cpp

src/randomenv.h

src/rest.h

src/script/keyorigin.h

src/script/parsing.cpp

src/script/parsing.h

src/script/script_error.h

src/script/sigcache.cpp

src/script/sigcache.h

src/script/solver.h

src/script/verify_flags.h

src/semaphore_grant.h

src/signet.h

src/span.h

src/support/allocators/secure.h

src/support/allocators/zeroafterfree.h

src/util/tokenpipe.cpp

src/util/translation.h

src/util/vector.h

src/versionbits.h

src/versionbits_impl.h

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/fees.h

src/wallet/load.h

src/wallet/receive.h

src/wallet/rpc/wallet.h

src/wallet/types.h

src/walletinitinterface.h

src/zmq/zmqabstractnotifier.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.