test: Add test on skip heights in CBlockIndex

optout21 commented at 12:08 pm on October 20, 2025: none

The skip height values, used by CBlockIndex::BuildSkip() and GetSkipHeight are not tested and not well documented. (noticed while reviewing #33515, recently merged).

The motivation is to document the skip value computation through a test.

The first commit adds a test for the properties of the distribution of skip values, namely that they have non-uniform distribution: most values are small but there are some large ones as well.

The second commit adds low-level tests to the GetSkipHeight() internal method. The tests are low level, thus of limited value, and the commit also touches the non-test code minimally (to make the method accessible). Therefore this commit has lower priority.

DrahtBot added the label Tests on Oct 20, 2025

DrahtBot commented at 12:08 pm on October 20, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33661.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	l0rinc

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

variouse -> various [spelling error in comment making the word invalid]

drahtbot_id_5_m

optout21 force-pushed on Oct 20, 2025

l0rinc commented at 8:48 pm on October 20, 2025: contributor

Concept ACK, thanks for helping with the coverage and documentation. For reference https://maflcko.github.io/b-c-cov/test_bitcoin.coverage/src/chain.cpp.gcov.html is pretty well covered otherwise, but these tests can help with the specifics.

optout21 commented at 9:04 am on October 21, 2025: none

For reference https://maflcko.github.io/b-c-cov/test_bitcoin.coverage/src/chain.cpp.gcov.html is pretty well covered otherwise, but these tests can help with the specifics.

Thanks for the link! Indirectly it is tested extensively, as the skip mechanism is used while searching in the chain. However, there are no tests focusing on this specifically, and the why and how on the exact skip generation algorithm is not documented.

optout21 marked this as ready for review on Oct 30, 2025

in src/chain.cpp:79 in 6a22013f5a outdated

75@@ -76,7 +76,7 @@ CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
76 int static inline InvertLowestOne(int n) { return n & (n - 1); }
77 
78 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
79-int static inline GetSkipHeight(int height) {
80+int GetSkipHeight(int height) {

l0rinc commented at 8:50 am on November 1, 2025:

👍 for the static removal, but why remove the inline keyword?

optout21 commented at 2:37 pm on November 3, 2025:

If it’s inlined, it can’t be used as extern from the test :(

l0rinc commented at 4:02 pm on November 3, 2025:

how so, what’s the failure you’re seeing? It was working for me locally

optout21 commented at 4:22 pm on November 3, 2025:

If GetSkipHeight is inline, I get the error:

0[ 75%] Built target bitcoin-node
1/usr/bin/ld: CMakeFiles/test_bitcoin.dir/chain_tests.cpp.o: in function `chain_tests::get_skip_height_test::test_method()':
2/home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:50:(.text+0x68b): undefined reference to `GetSkipHeight(int)'
3/usr/bin/ld: /home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:51:(.text+0x7cf): undefined reference to `GetSkipHeight(int)'
4/usr/bin/ld: /home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:52:(.text+0x90c): undefined reference to `GetSkipHeight(int)'
5/usr/bin/ld: /home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:53:(.text+0xa49): undefined reference to `GetSkipHeight(int)'
6/usr/bin/ld: /home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:54:(.text+0xb86): undefined reference to `GetSkipHeight(int)'
7/usr/bin/ld: CMakeFiles/test_bitcoin.dir/chain_tests.cpp.o:/home/bitcoin/bitcoin-core/build/src/test/./test/chain_tests.cpp:55: more undefined references to `GetSkipHeight(int)' follow
8collect2: error: ld returned 1 exit status
9gmake[2]: *** [src/test/CMakeFiles/test_bitcoin.dir/build.make:2463: bin/test_bitcoin] Error 1

Inlined method is not included in the obj file as a method. The solution would be to expose it through the header file, but I did not want to make that change just for the sake of the test.

l0rinc commented at 9:53 pm on November 3, 2025:

interesting, it does work for me, but inline might indeed be problematic in this case. Removing it should be fine, please resolve this comment.

optout21 commented at 9:39 am on November 4, 2025:

Indeed. Inline is only a hint, not crucial for modern compliers.

in src/test/chain_tests.cpp:51 in cdffd675d5 outdated

46+    // The test collects and analyses the distribution of the
47+    // skip difference numbers, and checks some properties:
48+    // non-uniform distribution with most values small but
49+    // with some large values as well.
50+
51+    FastRandomContext ctx;

l0rinc commented at 9:00 am on November 1, 2025:

This seems unused

optout21 commented at 2:58 pm on November 3, 2025:

Removed

in src/chain.cpp:80 in 6a22013f5a outdated

75@@ -76,7 +76,7 @@ CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
76 int static inline InvertLowestOne(int n) { return n & (n - 1); }
77 
78 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
79-int static inline GetSkipHeight(int height) {
80+int GetSkipHeight(int height) {
81     if (height < 2)

l0rinc commented at 11:34 am on November 3, 2025:

nit: can this be if (height <= 2) as well? It’s likely outside the scope of the change though

optout21 commented at 1:01 pm on November 3, 2025:

Indeed, the input 2 also gives 0 as result. The intent may have been that got indices 0 and 1 it makes no sense to jump, for the rest follow the computation (but 2 accidentally also gives 0). In any case, I don’t want to change product behavior to the slightest in this PR.

in src/test/chain_tests.cpp:54 in 6a22013f5a

49+    BOOST_CHECK(GetSkipHeight(0b0001011101101001) == 0b0001011101000001);
50+    BOOST_CHECK(GetSkipHeight(0b0110101101011000) == 0b0110101101010000);
51+    BOOST_CHECK(GetSkipHeight(0b0110101101011001) == 0b0110101101000001);
52+    BOOST_CHECK(GetSkipHeight(0) == 0);
53+    BOOST_CHECK(GetSkipHeight(1) == 0);
54+    BOOST_CHECK(GetSkipHeight(2) == 0);

l0rinc commented at 11:38 am on November 3, 2025:

we could add comments explaining the magic values: # height <= 2 # powers of 2 # odd/even heights # absurdly big values or whatever

Otherwise it’s not obvious why 4 is 0 and 5 is 1 and there is no 6 but 7 is 1 again…

I need to understand why we chose these numbers, especially since the PR is meant to document the change

optout21 commented at 2:58 pm on November 3, 2025:

I’ve adjusted the numbers used and added comments

in src/test/chain_tests.cpp:48 in 6a22013f5a

42@@ -41,6 +43,78 @@ const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockInd
43 
44 } // namespace
45 
46+BOOST_AUTO_TEST_CASE(get_skip_height_test)
47+{
48+    BOOST_CHECK(GetSkipHeight(0b0001011101101000) == 0b0001011101100000);

l0rinc commented at 11:40 am on November 3, 2025:

I like the binary representation, but maybe we could use BOOST_CHECK_EQUAL insead (helps with the reason when they fail) and maybe we could align these to simplify finding the differences in their endings:

0    BOOST_CHECK_EQUAL(GetSkipHeight(0b0001011101101000),
1                                    0b0001011101100000);
2    BOOST_CHECK_EQUAL(GetSkipHeight(0b0001011101101001),
3                                    0b0001011101000001);
4    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011000),
5                                    0b0110101101010000);
6    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011001),
7                                    0b0110101101000001);

And a short comment could help in drawing our attention to the ending

optout21 commented at 2:59 pm on November 3, 2025:

Changed to BOOST_CHECK_EQUAL, added comments

l0rinc commented at 9:36 pm on November 3, 2025:

Formatting them to be on top of each other as the above example shows allows easier bit comparison, otherwise the binary representation doesn’t really help

optout21 commented at 9:40 am on November 4, 2025:

I did that for the longer values, for shorter values with only a few ones is not really need.

l0rinc commented at 2:13 pm on November 4, 2025:

Can we do it for the shorter ones as well? it’s easier to compare them and more consistent with the rest

in src/test/chain_tests.cpp:91 in 6a22013f5a outdated

66+
67+BOOST_AUTO_TEST_CASE(skip_height_properties_test)
68+{
69+    // The test collects and analyses the distribution of the
70+    // skip difference numbers, and checks some properties:
71+    // non-uniform distribution with most values small but

l0rinc commented at 11:41 am on November 3, 2025:

it seems to test more than non-uniformity. My understanding is that you want to show that most jumps are small, right? If so, maybe we don’t have to be that specific, can we just check that the median jump is tiny?

 0BOOST_AUTO_TEST_CASE(skip_height_properties_test)
 1{
 2    constexpr int n{30'000};
 3
 4    std::vector<std::unique_ptr<CBlockIndex>> block_index;
 5    block_index.push_back(std::make_unique<CBlockIndex>());
 6    for(int i{0}; i < n; ++i) {
 7        auto new_index{std::make_unique<CBlockIndex>()};
 8        new_index->pprev = block_index.back().get();
 9        new_index->nHeight = new_index->pprev->nHeight + 1;
10        new_index->BuildSkip();
11        block_index.push_back(std::move(new_index));
12    }
13
14    std::vector<int> skip_diffs;
15    skip_diffs.reserve(n);
16    for(int i{1}; i <= n; ++i) {
17        skip_diffs.push_back(i - block_index[i]->pskip->nHeight);
18    }
19
20    std::ranges::sort(skip_diffs);
21    const int median{skip_diffs[n / 2]};
22    
23    BOOST_CHECK_LT(median, 10); // Most jumps are small
24}

optout21 commented at 2:44 pm on November 3, 2025:

I check the avg, which is computationally easier to obtain. It would make sense to check the median as well, and maybe compare the median with the average. However, I prefer to avoid the O(N log N) complexity of the sorting.

l0rinc commented at 4:05 pm on November 3, 2025:

median is less sensitive to outliers - and nlogn is fine in tests

optout21 commented at 9:41 am on November 4, 2025:

Added median check as well. Much lower than the avg!

l0rinc commented at 2:15 pm on November 4, 2025:

The test became more complicated than it was before (which was my main critique of it, seems arbitrary). Could we simplify it? I think we’re testing too many things, a single median check should likely suffice in my opinion.

in src/test/chain_tests.cpp:106 in 6a22013f5a outdated

88+        new_index->nHeight = new_index->pprev->nHeight + 1;
89+        new_index->BuildSkip();
90+        block_index.push_back(std::move(new_index));
91+    }
92+
93+    // Analyze the diff (in height) of each element and its pskip

l0rinc commented at 11:43 am on November 3, 2025:

I need more context, how did we get to these numbers exactly? Do we really need to be this precise? Wouldn’t it suffice to check that their median is low enough?

optout21 commented at 9:41 am on November 4, 2025:

Added explanatory comments

in src/test/chain_tests.cpp:98 in 6a22013f5a

93+    // Analyze the diff (in height) of each element and its pskip
94+    int count_diff_smaller_16 = 0;
95+    int max_diff = 0;
96+    int total_diff = 0;
97+    for(int i = 1; i < n; ++i) {
98+        BOOST_CHECK(block_index[i]->nHeight == i);

l0rinc commented at 11:52 am on November 3, 2025:

this sounds like a BOOST_REQUIRE_EQUAL instead

in src/test/chain_tests.cpp:80 in 6a22013f5a

75+    std::vector<std::unique_ptr<CBlockIndex>> block_index;
76+
77+    // Create genesis block
78+    auto genesis = std::make_unique<CBlockIndex>();
79+    genesis->nHeight = 0;
80+    block_index.push_back(std::move(genesis));

l0rinc commented at 11:55 am on November 3, 2025:

maybe this would also work

0    std::vector<std::unique_ptr<CBlockIndex>> block_index;
1    block_index.push_back(std::make_unique<CBlockIndex>());

optout21 commented at 3:00 pm on November 3, 2025:

Done

l0rinc commented at 9:49 pm on November 3, 2025:

I see you’ve moved it as well, clang complains with:

Clangd: Moving a temporary object prevents copy elision

optout21 commented at 9:41 am on November 4, 2025:

Oops, fixed!

in src/test/chain_tests.cpp:83 in 6a22013f5a

78+    auto genesis = std::make_unique<CBlockIndex>();
79+    genesis->nHeight = 0;
80+    block_index.push_back(std::move(genesis));
81+
82+    // Build a chain
83+    const auto n{30000};

l0rinc commented at 12:02 pm on November 3, 2025:

was wondering how slow this is, but seems acceptable:

0cmake -B build  -DCMAKE_BUILD_TYPE=Debug && cmake --build build && time ./build/bin/test_bitcoin --run_test=chain_tests/skip_height_properties_test
1...
2./build/bin/test_bitcoin --run_test=chain_tests/skip_height_properties_test  0.32s user 0.02s system 27% cpu 1.269 total

optout21 commented at 2:45 pm on November 3, 2025:

Yes, nontheless I reduce the count from 30000 to 10000, that’s also enough for the test.

l0rinc commented at 9:50 pm on November 3, 2025:

nit: consider formatting it as 10'000 for readability

optout21 commented at 9:41 am on November 4, 2025:

Done

in src/test/chain_tests.cpp:110 in 6a22013f5a outdated

92+
93+    // Analyze the diff (in height) of each element and its pskip
94+    int count_diff_smaller_16 = 0;
95+    int max_diff = 0;
96+    int total_diff = 0;
97+    for(int i = 1; i < n; ++i) {

l0rinc commented at 12:07 pm on November 3, 2025:

how come we’re iterating one less than before?

0    for(int i = 1; i <= n; ++i) {

optout21 commented at 2:34 pm on November 3, 2025:

It doesn’t make sense to check the skip for block index 0, that’s why 0 is excluded.

l0rinc commented at 4:01 pm on November 3, 2025:

yeah, but why is n skipped (see my suggested code)

optout21 commented at 4:25 pm on November 3, 2025:

Oh, I see. There are in fact n+1 elements. Will change.

optout21 commented at 9:42 am on November 4, 2025:

All cycles go from 1 to n-1; 0 is the genesis.

in src/chain.cpp:86 in 6a22013f5a

l0rinc commented at 12:09 pm on November 3, 2025:

Can we add a fuzz test that asserts for all h > 0: GetSkipHeight(h) < h and popcount(result) < popcount(h) (and just skip 0 since that’s already unit tested)?

optout21 commented at 9:43 am on November 4, 2025:

A fuzz test for this functionality (essentially a one-liner) seems a bit too much.

l0rinc commented at 2:18 pm on November 4, 2025:

k, please resolve the comment

l0rinc changes_requested

l0rinc commented at 12:33 pm on November 3, 2025: contributor

Concept ACK, during review I also understood this behavior better :) I have a few suggestions for simplification and am throwing you into the deep end by asking for a property based (fuzz) test as well to check certain invariants. Not a must-have, but seems simple enough. I also suggest simplifying the distribution test to just check for the median instead.

optout21 force-pushed on Nov 3, 2025

optout21 commented at 3:02 pm on November 3, 2025: none

Review comments addressed, mostly minor:

Reduce the number of iterations to 10000 (from 30000), for faster test execution.
Add comments on choice of test inputs.
Use BOOST_REQUIRE_EQUAL or BOOST_CHECK_GT where possible.

optout21 commented at 3:03 pm on November 3, 2025: none

@sipa, as this is triggered by #33515 of yours, I would kindly ask for a review.

sipa requested review from sipa on Nov 3, 2025

optout21 force-pushed on Nov 4, 2025

optout21 commented at 9:38 am on November 4, 2025: none

Changes applied:

Fix lint issue
Added check on the median as well
some minor formatting

Add test on skip heights in CBlockIndex

Add unit tests for the properties of the skip height in CBlockIndex.
Skip heights are set by CBlockIndex::BuildSkip(), which internally
uses the GetSkipHeight() and InvertLowestOne() methods.
These methods don't have unit tests and are only minimally documented.
The new unit test collects and analyses the distribution of the skip
difference numbers, and checks some properties:
non-uniform distribution with most values small but
with some large values as well.

d363a99562

Add low-level tests for GetSkipHeight()

This internal method in chain.cpp has low and indirect test
coverage, and not documented well.
A straightforward, simple, direct unit test is added.
The method is changed to be not static and inline, so that
the test can link with it.

6adafaa721

optout21 force-pushed on Nov 4, 2025

optout21 commented at 12:26 pm on November 4, 2025: none

CI failed, limits of the 3rd for cycle were off; fixed

0     int count_diff_smaller_16 = 0;
1     int max_diff = 0;
2     int total_diff = 0;
3-    for(int i{1}; i < n; ++i) {
4+    for(size_t i{0}; i < skip_diffs.size(); ++i) {
5         auto diff = skip_diffs[i];
6         if (diff < 16) {
7             ++count_diff_smaller_16;

in src/test/chain_tests.cpp:49 in 6adafaa721

42@@ -41,6 +43,113 @@ const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockInd
43 
44 } // namespace
45 
46+BOOST_AUTO_TEST_CASE(get_skip_height_test)
47+{
48+    // Even values: the rightmost bit is zeroed
49+    // Test with variouse even values with at least 2 bits set

DrahtBot commented at 2:06 pm on November 4, 2025:

variouse -> various [spelling error in comment making the word invalid]

in src/test/chain_tests.cpp:73 in 6adafaa721

68+                                    0b0001011101000001);
69+    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011000),
70+                                    0b0110101101010000);
71+    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011001),
72+                                    0b0110101101000001);
73+    // All values 0--10

l0rinc commented at 2:15 pm on November 4, 2025:

what does -- mean here?

test: Add test on skip heights in CBlockIndex #33661

Code Coverage & Benchmarks

Reviews

LLM Linter (✨ experimental)