script: reduce worst-case boolean scan time #36898

pull l0rinc wants to merge 2 commits into bitcoin:master from l0rinc:l0rinc/script-casttobool changing 2 files +20 −9
  1. l0rinc commented at 8:29 AM on November 17, 2026: contributor

    Problem: Repeated boolean checks on long zero prefixes can make a valid block expensive to validate. For a nearly full block that repeatedly checks 519 zero bytes followed by 01, median submitblock time on a Rpi4 fell from ~3.9 s to ~1.6 s (including RPC transfer and validation). The spending transaction is nonstandard, but a miner could include it directly.

    Fix: Skip leading zero bytes in 64-bit chunks with ReadLE64, keeping the byte checks that handle negative zero. The idea is similar to [the multi-byte XOR processing in #31144](https://github.com/bitcoin/bitcoin/pull/31144) and follows up on #36878. It also adds cases around the 8-byte boundaries to the existing script test vectors.

    Benchmarks:

    VerifyIfDupVerifyFullLast
      Before ████████████████████████ 3.4 s
      After  ████████                 1.1 s
    
    VerifyIfDupFullZero
      Before ████████████████████████ 3.3 s
      After  ███████                  1.0 s
    
    VerifyIfDupFullNegativeZero
      Before ████████████████████████ 3.3 s
      After  ███████                  1.0 s
    
    VerifyIfDupVerifyFullZeroLastWord
      Before ████████████████████████ 3.3 s
      After  ███████                  1.0 s
    

    VerifyNestedIfScript is roughly ~1% slower while VerifyIfDupVerifyFullFirst, VerifyIfDupVerifyTrue, VerifyScriptP2WPKH, VerifyScriptP2TR_KeyPath and VerifyScriptP2TR_ScriptPath are effectively unchanged.

    <details> <summary>Manual benchmark patch</summary>

    diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp
    --- a/src/bench/verify_script.cpp
    +++ b/src/bench/verify_script.cpp
    @@ -5,6 +5,7 @@
     #include <addresstype.h>
     #include <bench/bench.h>
     #include <coins.h>
    +#include <consensus/consensus.h>
     #include <key.h>
     #include <policy/policy.h>
     #include <primitives/transaction.h>
    @@ -22,6 +23,7 @@
     #include <util/translation.h>
     
     #include <cstddef>
    +#include <cstdint>
     #include <map>
     #include <span>
     #include <vector>
    @@ -131,6 +133,60 @@ static void VerifyNestedIfScript(benchmark::Bench& bench)
             });
     }
     
    +//! Maximum-size stack element that is zero except for `byte` at `pos`
    +static std::vector<uint8_t> FullElement(size_t pos, uint8_t byte)
    +{
    +    std::vector<uint8_t> value(MAX_SCRIPT_ELEMENT_SIZE);
    +    value.at(pos) = byte;
    +    return value;
    +}
    +static constexpr size_t LAST_BYTE{MAX_SCRIPT_ELEMENT_SIZE - 1};
    +
    +// A single tapscript can occupy nearly the entire block weight budget
    +// Both patterns cast the element to bool about once per opcode byte
    +static void VerifyIfDupBench(benchmark::Bench& bench, const std::vector<uint8_t>& value, bool truthy = true)
    +{
    +    constexpr uint32_t SCRIPT_SIZE{MAX_BLOCK_WEIGHT - 4000};
    +    CScript script;
    +    script.reserve(SCRIPT_SIZE);
    +    if (truthy) {
    +        for (uint32_t i{0}; i < SCRIPT_SIZE / 2; ++i) {
    +            script << OP_IFDUP << OP_VERIFY;
    +        }
    +    } else {
    +        script.insert(script.end(), SCRIPT_SIZE - 2, OP_IFDUP);
    +        script << OP_DROP << OP_1;
    +    }
    +    TaprootBuilder builder;
    +    builder.Add(0, script, TAPROOT_LEAF_TAPSCRIPT).Finalize(XOnlyPubKey::NUMS_H);
    +    const CScript script_pub_key{GetScriptForDestination(builder.GetOutput())};
    +    const auto spend_data{builder.GetSpendData()};
    +    CScriptWitness witness;
    +    witness.stack = {value, ToByteVector(script), *spend_data.scripts.begin()->second.begin()};
    +    assert(script.size() == SCRIPT_SIZE);
    +    assert(value.size() <= MAX_SCRIPT_ELEMENT_SIZE);
    +
    +    bench.unit("script").run([&] {
    +        ScriptError error;
    +        const bool success{VerifyScript({}, script_pub_key, &witness, STANDARD_SCRIPT_VERIFY_FLAGS, BaseSignatureChecker(), &error)};
    +        assert(success && error == SCRIPT_ERR_OK);
    +    });
    +}
    +
    +static void VerifyIfDupVerifyFullLast(benchmark::Bench& bench) { VerifyIfDupBench(bench, FullElement(LAST_BYTE, 1)); }
    +static void VerifyIfDupVerifyFullFirst(benchmark::Bench& bench) { VerifyIfDupBench(bench, FullElement(0, 1)); }
    +static void VerifyIfDupVerifyFullZeroLastWord(benchmark::Bench& bench) { VerifyIfDupBench(bench, FullElement(LAST_BYTE - sizeof(uint64_t), 1)); }
    +static void VerifyIfDupVerifyTrue(benchmark::Bench& bench) { VerifyIfDupBench(bench, {1}); }
    +static void VerifyIfDupFullZero(benchmark::Bench& bench) { VerifyIfDupBench(bench, FullElement(0, 0), /*truthy=*/false); }
    +static void VerifyIfDupFullNegativeZero(benchmark::Bench& bench) { VerifyIfDupBench(bench, FullElement(LAST_BYTE, 0x80), /*truthy=*/false); }
    +
    +BENCHMARK(VerifyIfDupVerifyFullLast);
    +BENCHMARK(VerifyIfDupVerifyFullFirst);
    +BENCHMARK(VerifyIfDupVerifyFullZeroLastWord);
    +BENCHMARK(VerifyIfDupVerifyTrue);
    +BENCHMARK(VerifyIfDupFullZero);
    +BENCHMARK(VerifyIfDupFullNegativeZero);
    +
     BENCHMARK(VerifyScriptP2WPKH);
     BENCHMARK(VerifyScriptP2TR_KeyPath);
     BENCHMARK(VerifyScriptP2TR_ScriptPath);
    

    </details>

  2. test: cover boolean casts at word boundaries
    Extend the existing script vectors with explicit results around 8-byte scan boundaries before changing `CastToBool`.
    8456412c9d
  3. script: reduce worst-case boolean scan time
    Repeated boolean checks on long zero prefixes can make a valid block expensive to validate.
    Skip leading zero bytes in 64-bit chunks, keeping the byte checks that handle negative zero.
    
    For a nearly full block that repeatedly checks 519 zero bytes followed by `01`, median `submitblock` time on a Raspberry Pi 4 fell from ~3.9 s to ~1.6 s (including RPC transfer and validation).
    The spending transaction is nonstandard, but a miner could include it directly.
    
    This follows up on #36878.
    
    Co-authored-by: jrakibi <j.errakibi@gmail.com>
    3b7f9f5be1
  4. DrahtBot added the label Consensus on Nov 17, 2026
  5. DrahtBot commented at 8:29 AM on November 17, 2026: contributor

    <!--e57a25ab6845829454e8d69fc972939a-->

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

    <!--006a51241073e994b41acfe9ec718e94-->

    External sites

    <!--021abf342d371248e50ceaed478a90ca-->

    Reviews

    See the guideline and AI policy for information on the review process. A summary of reviews will appear here.

    <!--5faf32d7da4f0f540f40219e4f7537a3-->


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-11-17 16:51 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me