fuzz: Fix difficulty target generation in p2p_headers_presync #31213

1. 
   marcofleon commented at 3:00 pm on November 4, 2024: contributor

   In the p2p_headers_presync fuzz target, this assertion failed:

   0 assert(total_work < chainman.MinimumChainWork());
   

   Input that triggered the failure: p2ppresync_crash.txt

   The test previously used ConsumeIntegralInRange to generate header difficulty targets within a hardcoded range. The fuzzer found specific values in that range that correspond to very low thresholds due to how SetCompact works. The total work of a long enough test chain ended up exceeding MinimumChainWork.

   Fix this by adding a new ConsumeArithUInt256InRange helper function and use it in the fuzz test to generate target values within the originally intended range. The target is then converted to an nBits value using GetCompact().

   For some more context, see #30918.

2. 
   DrahtBot commented at 3:00 pm on November 4, 2024: 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/31213.

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   ACK	instagibbs, dergoegge, brunoerg

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

3. DrahtBot added the label Tests on Nov 4, 2024
4. 
   instagibbs commented at 3:04 pm on November 4, 2024: member

   To be clear, nBits is “deterministic” in that the value, given the chain history, is static, right?
5. 
   marcofleon commented at 3:37 pm on November 4, 2024: contributor

   To be clear, nBits is “deterministic” in that the value, given the chain history, is static, right?

   Hmm I’m not entirely sure what you’re asking. nBits does always start with the genesis block value, yes. Then it’ll either change or stay the same according to the fuzzer. Is that what you meant?

6. marcofleon force-pushed on Nov 4, 2024
7. 
   instagibbs commented at 4:25 pm on November 4, 2024: member

   @marcofleon Ah, I didn’t understand how pre-sync nBits checking works, my question makes no sense for pre-sync
8. in src/test/fuzz/util.h:194 in 6328f3cb75 outdated

   189+    // Avoid division by 0, in case range + 1 results in overflow.
   190+    if (range != ~arith_uint256(0)) {
   191+        const arith_uint256 quotient = value / (range + 1);
   192+        result = value - (quotient * (range + 1));
   193+    }
   194+    return min + result;
   

   ---

   ---

   

   instagibbs commented at 6:30 pm on November 4, 2024:

   some pedantic assertions to catch hypothetical issues with the function earlier

   0    assert(min + result >= min);
   1    assert(min + result <= max);
   2    return min + result;
   

   ---

   

   marcofleon commented at 3:48 pm on November 5, 2024:

   Done.
9. in src/test/fuzz/p2p_headers_presync.cpp:97 in 6328f3cb75 outdated

    95-                       prev_nbits :
    96-                       fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0x17058EBE, 0x1D00FFFF);
    97+    if (fuzzed_data_provider.ConsumeBool()) {
    98+        header.nBits = prev_nbits;
    99+    } else {
   100+        arith_uint256 lower_target = UintToArith256(uint256{"000000000000000000058ebe0000000000000000000000000000000000000000"});
   

   ---

   ---

   

   instagibbs commented at 6:32 pm on November 4, 2024:

   are there any easy ways to verify these lower and higher target values? In other words, how can these values be justified at a glance or programatically

   ---

   

   marcofleon commented at 3:48 pm on November 5, 2024:

   The upper target is the nBits value from the genesis block (0x1D00FFFF) and the lower one is the nBits from some mainnet block at a certain height (0x17058EBE). Using SetCompact on those values gives those two uint256 values. The work returned from the lower target multiplied by the longest possible chain (1600) in the test should be lower than MinimumChainWork.

   I get 0x11fe50e0ab9cbcf864c0500 for the theoretical max amount of work a headers chain from this test could have. MinimumChainWork is 0x88e186b70e0862c193ec44d6.

   ---

   

   marcofleon commented at 5:44 pm on November 5, 2024:

   I should also add, I used the expression in GetBlockProof https://github.com/bitcoin/bitcoin/blob/65b194193661e27cf2d9c0e0d7e3b627a379513a/src/chain.cpp#L143 to calculate the work on a single header.

   ---

   

   marcofleon commented at 7:55 pm on November 5, 2024:

   If I wanted to do a lower target based on MinimumChainWork, I think I could do

   0target = (~work + 1) / work
   

   where work would be MinimumChainWork / 1600 or maybe a bit less to be safe.

   ---

   

   instagibbs commented at 3:59 pm on November 6, 2024:

   Would this be correct? I would like this to be easily verifiable, and filling in the FIXMEs would make that simple

    0diff --git a/src/test/fuzz/p2p_headers_presync.cpp b/src/test/fuzz/p2p_headers_presync.cpp
    1index 08e8d08c08..41ac8d172b 100644
    2--- a/src/test/fuzz/p2p_headers_presync.cpp
    3+++ b/src/test/fuzz/p2p_headers_presync.cpp
    4@@ -92,12 +92,14 @@ CBlockHeader ConsumeHeader(FuzzedDataProvider& fuzzed_data_provider, const uint2
    5     header.nNonce = 0;
    6     // Either use the previous difficulty or let the fuzzer choose
    7     if (fuzzed_data_provider.ConsumeBool()) {
    8         header.nBits = prev_nbits;
    9     } else {
   10-        arith_uint256 lower_target = UintToArith256(uint256{"000000000000000000058ebe0000000000000000000000000000000000000000"});
   11-        arith_uint256 upper_target = UintToArith256(uint256{"00000000ffff0000000000000000000000000000000000000000000000000000"});
   12+        arith_uint256 lower_target;
   13+        lower_target.SetCompact(0x17058ebe); // "bits" result for testnet3 getblockheader <FIXME hash>
   14+        arith_uint256 upper_target;
   15+        upper_target.SetCompact(0x1d00ffff); // "bits" result for testnet3 getblockheader <FIXME hash>
   16         arith_uint256 target = ConsumeArithUInt256InRange(fuzzed_data_provider, lower_target, upper_target);
   17         header.nBits = target.GetCompact();
   18     }
   19     header.nTime = ConsumeTime(fuzzed_data_provider);
   20     header.hashPrevBlock = prev_hash;
   

   ---

   

   marcofleon commented at 3:17 pm on November 7, 2024:

   Agreed, it should be clear where the hardcoded values are coming from. It doesn’t seem necessary to call SetCompact every iteration, so I decided to explain in the comment above. Let me know what you think.
10. util: Add ConsumeArithUInt256InRange fuzzing helper fa327c77e3
11. marcofleon force-pushed on Nov 5, 2024
12. marcofleon force-pushed on Nov 7, 2024
13. marcofleon force-pushed on Nov 7, 2024
14. in src/test/fuzz/p2p_headers_presync.cpp:97 in fb30c4b186 outdated

     96-                       fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0x17058EBE, 0x1D00FFFF);
     97+    // Either use the previous difficulty or let the fuzzer choose. The upper target in the
     98+    // range comes from the bits value of the genesis block, which is 0x1d00ffff. The lower
     99+    // target comes from the bits value of mainnet block 840000, which is 0x17034219.
    100+    // Calling lower_target.SetCompact(0x17034219) and upper_target.SetCompact(0x1d00ffff)
    101+    // should return the values below.
    

    ---

    ---

    

    dergoegge commented at 10:36 am on November 12, 2024:

    0    // should return the values below.
    1    //
    2    // RPC commands to verify:
    3    // getblockheader 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
    4    // getblockheader 0000000000000000000320283a032748cef8227873ff4872689bf23f1cda83a5
    

    nit: Perhaps add the rpc commands that can be used to verify the values to the comment

    ---

    

    marcofleon commented at 5:04 pm on November 12, 2024:

    Good call, done.
15. fuzz: Fix difficulty target generation in p2p_headers_presync

    The hardcoded nBits range would occasionally produce values for
    the difficulty target that were too low, causing the total work
    of the test chain to exceed MinimumChainWork. This fix uses
    ConsumeArithUInt256InRange to properly generate targets that
    will produce header chains with less work than MinimumChainWork.

    a6ca8f3243
16. marcofleon force-pushed on Nov 12, 2024
17. in src/test/fuzz/p2p_headers_presync.cpp:93 in a6ca8f3243

    89@@ -89,10 +90,23 @@ CBlockHeader ConsumeHeader(FuzzedDataProvider& fuzzed_data_provider, const uint2
    90 {
    91     CBlockHeader header;
    92     header.nNonce = 0;
    93-    // Either use the previous difficulty or let the fuzzer choose
    94-    header.nBits = fuzzed_data_provider.ConsumeBool() ?
    95-                       prev_nbits :
    96-                       fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0x17058EBE, 0x1D00FFFF);
    97+    // Either use the previous difficulty or let the fuzzer choose. The upper target in the
    

    ---

    ---

    

    instagibbs commented at 2:58 pm on November 14, 2024:

    maybe leave a note that in presync we’re allowed to have arbitrary nBits adjustments, within the clamped values?

    ---

    

    marcofleon commented at 1:32 pm on November 15, 2024:

    As is, the test doesn’t hit that part in pow.cpp. But I’ll look to improve this test and its coverage in a future PR. Still thinking about the best way to do it. For now, I’m going leave it as is and just be sure that the crash is fixed.
18. 
    instagibbs commented at 3:01 pm on November 14, 2024: member

    ACK https://github.com/bitcoin/bitcoin/pull/31213/commits/a6ca8f324396522e9748c9a7bbefb3bf1c74a436

    seems strictly better than as-is

19. dergoegge approved
20. 
    dergoegge commented at 5:09 pm on November 14, 2024: member

    Code review ACK a6ca8f324396522e9748c9a7bbefb3bf1c74a436
21. marcofleon marked this as a draft on Nov 15, 2024
22. marcofleon marked this as ready for review on Nov 15, 2024
23. brunoerg approved
24. 
    brunoerg commented at 11:34 am on November 20, 2024: contributor

    code review ACK a6ca8f324396522e9748c9a7bbefb3bf1c74a436
25. fanquake merged this on Nov 20, 2024
26. fanquake closed this on Nov 20, 2024

    ---

Contributors
marcofleon DrahtBot instagibbs dergoegge brunoerg

Labels
Tests