chain_tests.cpp
1 // Copyright (c) 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 <boost/test/unit_test.hpp> 6 7 #include <chain.h> 8 #include <test/util/setup_common.h> 9 10 #include <array> 11 #include <memory> 12 13 BOOST_FIXTURE_TEST_SUITE(chain_tests, BasicTestingSetup) 14 15 namespace { 16 17 const CBlockIndex* NaiveGetAncestor(const CBlockIndex* a, int height) 18 { 19 while (a->nHeight > height) { 20 a = a->pprev; 21 } 22 BOOST_REQUIRE_EQUAL(a->nHeight, height); 23 return a; 24 } 25 26 const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockIndex* b) 27 { 28 while (a->nHeight > b->nHeight) { 29 a = a->pprev; 30 } 31 while (b->nHeight > a->nHeight) { 32 b = b->pprev; 33 } 34 while (a != b) { 35 BOOST_REQUIRE_EQUAL(a->nHeight, b->nHeight); 36 a = a->pprev; 37 b = b->pprev; 38 } 39 BOOST_REQUIRE_EQUAL(a, b); 40 return a; 41 } 42 43 } // namespace 44 45 BOOST_AUTO_TEST_CASE(basic_tests) 46 { 47 // An empty chain 48 const CChain chain_0; 49 // A chain with 2 blocks 50 CChain chain_2; 51 52 CBlockIndex genesis; 53 genesis.nHeight = 0; 54 chain_2.SetTip(genesis); 55 56 CBlockIndex bi1; 57 bi1.pprev = &genesis; 58 bi1.nHeight = 1; 59 chain_2.SetTip(bi1); 60 61 BOOST_CHECK_EQUAL(chain_0.Height(), -1); 62 BOOST_CHECK_EQUAL(chain_2.Height(), 1); 63 64 BOOST_CHECK_EQUAL(chain_0.Tip(), nullptr); 65 BOOST_CHECK_EQUAL(chain_2.Tip(), &bi1); 66 67 // Indexer accessor: call with valid and invalid (low & high) values 68 BOOST_CHECK_EQUAL(chain_2[-1], nullptr); 69 BOOST_CHECK_EQUAL(chain_2[0], &genesis); 70 BOOST_CHECK_EQUAL(chain_2[1], &bi1); 71 BOOST_CHECK_EQUAL(chain_2[2], nullptr); 72 73 // Contains: call with contained & non-contained blocks 74 BOOST_CHECK(chain_2.Contains(genesis)); 75 BOOST_CHECK(chain_2.Contains(bi1)); 76 BOOST_CHECK(!chain_0.Contains(genesis)); 77 78 // Call with non-tip & tip blocks 79 BOOST_CHECK_EQUAL(chain_2.Next(genesis), &bi1); 80 BOOST_CHECK_EQUAL(chain_2.Next(bi1), nullptr); 81 BOOST_CHECK_EQUAL(chain_0.Next(genesis), nullptr); 82 83 BOOST_CHECK_EQUAL(chain_2.Genesis(), &genesis); 84 BOOST_CHECK_EQUAL(chain_0.Genesis(), nullptr); 85 } 86 87 BOOST_AUTO_TEST_CASE(findfork_tests) 88 { 89 // Create a forking chain 90 const auto init_branch{[](auto& blocks, CBlockIndex* parent, int start_height) { 91 for (size_t i{0}; i < blocks.size(); ++i) { 92 blocks[i].pprev = i == 0 ? parent : &blocks[i - 1]; 93 blocks[i].nHeight = start_height + i; 94 } 95 }}; 96 97 const auto check_same{[](const CChain& chain, const auto& blocks) { 98 for (const auto& block : blocks) { 99 BOOST_CHECK_EQUAL(chain.FindFork(block), &block); 100 } 101 }}; 102 103 const auto check_fork_point{[](const CChain& chain, const auto& blocks, const CBlockIndex& fork_point) { 104 for (const auto& block : blocks) { 105 BOOST_CHECK_EQUAL(chain.FindFork(block), &fork_point); 106 } 107 }}; 108 109 std::array<CBlockIndex, 10> blocks_common; 110 init_branch(blocks_common, nullptr, 0); 111 112 std::array<CBlockIndex, 10> blocks_long; 113 init_branch(blocks_long, &blocks_common.back(), blocks_common.size()); 114 115 std::array<CBlockIndex, 5> blocks_short; 116 init_branch(blocks_short, &blocks_common.back(), blocks_common.size()); 117 118 // Create a chain with the longer fork 119 CChain chain_long; 120 chain_long.SetTip(blocks_long.back()); 121 BOOST_CHECK_EQUAL(chain_long.Height(), 10 + 10 - 1); 122 // Test the blocks in the common part -> result should be the same 123 check_same(chain_long, blocks_common); 124 // Test the blocks on the longer fork -> result should be the same 125 check_same(chain_long, blocks_long); 126 // Test the blocks on the other shorter fork -> result should be the fork point 127 check_fork_point(chain_long, blocks_short, blocks_common.back()); 128 129 // Create a chain with the shorter fork 130 CChain chain_short; 131 chain_short.SetTip(blocks_short.back()); 132 BOOST_CHECK_EQUAL(chain_short.Height(), 10 + 5 - 1); 133 // Test the blocks in the common part -> result should be the same 134 check_same(chain_short, blocks_common); 135 // Test the blocks on the shorter fork -> result should be the same 136 check_same(chain_short, blocks_short); 137 // Test the blocks on the other longer fork -> result should be the fork point 138 check_fork_point(chain_short, blocks_long, blocks_common.back()); 139 140 // Invalid test case. Mixing chains is not supported 141 CBlockIndex block_on_unrelated_chain; 142 BOOST_CHECK_EQUAL(chain_long.FindFork(block_on_unrelated_chain), nullptr); 143 } 144 145 BOOST_AUTO_TEST_CASE(chain_test) 146 { 147 FastRandomContext ctx; 148 std::vector<std::unique_ptr<CBlockIndex>> block_index; 149 // Run 10 iterations of the whole test. 150 for (int i = 0; i < 10; ++i) { 151 block_index.clear(); 152 // Create genesis block. 153 auto genesis = std::make_unique<CBlockIndex>(); 154 genesis->nHeight = 0; 155 block_index.push_back(std::move(genesis)); 156 // Create 10000 more blocks. 157 for (int b = 0; b < 10000; ++b) { 158 auto new_index = std::make_unique<CBlockIndex>(); 159 // 95% of blocks build on top of the last block; the others fork off randomly. 160 if (ctx.randrange(20) != 0) { 161 new_index->pprev = block_index.back().get(); 162 } else { 163 new_index->pprev = block_index[ctx.randrange(block_index.size())].get(); 164 } 165 new_index->nHeight = new_index->pprev->nHeight + 1; 166 new_index->BuildSkip(); 167 block_index.push_back(std::move(new_index)); 168 } 169 // Run 10000 random GetAncestor queries. 170 for (int q = 0; q < 10000; ++q) { 171 const CBlockIndex* block = block_index[ctx.randrange(block_index.size())].get(); 172 unsigned height = ctx.randrange<unsigned>(block->nHeight + 1); 173 const CBlockIndex* result = block->GetAncestor(height); 174 BOOST_CHECK(result == NaiveGetAncestor(block, height)); 175 } 176 // Run 10000 random LastCommonAncestor queries. 177 for (int q = 0; q < 10000; ++q) { 178 const CBlockIndex* block1 = block_index[ctx.randrange(block_index.size())].get(); 179 const CBlockIndex* block2 = block_index[ctx.randrange(block_index.size())].get(); 180 const CBlockIndex* result = LastCommonAncestor(block1, block2); 181 BOOST_CHECK(result == NaiveLastCommonAncestor(block1, block2)); 182 } 183 } 184 } 185 186 BOOST_AUTO_TEST_SUITE_END()