miniscript: fixes #29098 by only use first k valid signatures

tnndbtc commented at 5:37 am on January 23, 2025: none

In issue #29098 a recommendation is not to use “best (smallest) set of k signatures”. So, this effort is to fall back to the original algorithm which only use the first k available signatures for satisfying a k-of-n multisig. Otherwise, there will be timeout in unit test when we have 999-of-999 use case.

Profiling has been done on Mac to confirm the most time consuming function is in internal::InputResult ProduceInput.

Following tests will hit the affected code:

ctest –test-dir build

or to be specific: % build/src/test/test_bitcoin –run_test=descriptor_tests % build/src/test/test_bitcoin –run_test=miniscript_tests

build/test/functional/test_runner.py –extended

or to be specific: build/test/functional/test_runner.py test/functional/wallet_taproot.py –tmpdir /tmp

env -i HOME="$HOME" PATH="$PATH" USER="$USER" bash -c ‘MAKEJOBS="-j8" FILE_ENV="./ci/test/00_setup_env_native_fuzz.sh" ./ci/test_run_all.sh’

Time enhancement comparision: For original wallet_taproot.py test, it reduces the time from 10 seconds to 7 seconds on Apple M1 chipset (Sequoia 15.1.1).

Also, after cherry pick the PR that identified this performance issue: #28212 , the time spent was down from timed out to 36 seconds.

miniscript: fixes #29098 by only use first k valid signatures 4d9c1b741d

DrahtBot commented at 5:37 am on January 23, 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/31719.

Reviews

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31727 (miniscript: convert non-critical asserts to CHECK_NONFATAL by darosior)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Descriptors on Jan 23, 2025

tnndbtc commented at 5:47 am on January 23, 2025: none

I’d like to add more comments on how to test this for people who is new to bitcoin project:

To cherry pick my fixes: % git remote add tnndbtc https://github.com/tnndbtc/bitcoin % git fetch tnndbtc % git cherry-pick 4d9c1b741d4eb29cf66e6cbe4dd8f64bef24c30e

To validate #28212 % git remote add eriknylund https://github.com/eriknylund/bitcoin.git % git fetch eriknylund % git cherry-pick 387c12e0813a863bc9728777719acbafe7b12a34

The profiling results, notes can be found at https://github.com/tnndbtc/notes/blob/main/bitcoin/issues/28179/notes.txt

in src/script/miniscript.h:1208 in 4d9c1b741d outdated

1217+                            } else {
1218+                                sat_return = std::move(sat_return) + std::move(sat);
1219+                            }
1220+                        } else {
1221+                            if (sat.available == Availability::NO && sat_return.has_sig == false) {
1222+                                // when sat is Availability::NO, sat_return should be overwritten by sat:

tnndbtc commented at 5:47 am on January 23, 2025:

For reviewers, this is to cover this case: (lldb) print sat available = NO has_sig = false malleable = false non_canon = false size = 18446744073709551615 stack = size=0

(lldb) print sat_return available = YES has_sig = false malleable = false non_canon = false size = 0 stack = size=0

Or, simply call sat_return.SetAvailable(Availability::NO);

in src/script/miniscript.h:1221 in 4d9c1b741d outdated

1233                     assert(node.k != 0);
1234-                    assert(node.k <= sats.size());
1235-                    return {std::move(nsat), std::move(sats[node.k])};
1236+                    if (num_of_good_sigs < node.k)
1237+                    {
1238+                        sat_return.SetAvailable(Availability::NO);

tnndbtc commented at 5:48 am on January 23, 2025:

For reviewers, this is to reset sat_return when there is not enough k numbers of valid signatures

in src/script/miniscript.h:1195 in 4d9c1b741d outdated

1204-                        next_sats.push_back(sats[0] + ZERO);
1205-                        for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
1206-                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1207-                        // Switch over.
1208-                        sats = std::move(next_sats);
1209+                        if (sat.available == Availability::YES && num_of_good_sigs < node.k) {

tnndbtc commented at 5:50 am on January 23, 2025:

This is to follow the original algorithm at: https://github.com/bitcoin/bitcoin/blob/febe2abc0e3f67b8b0ac9ece1890efb4a0bba83c/src/script/sign.cpp#L287

which only take the first k valid signatures

DrahtBot added the label CI failed on Jan 23, 2025

DrahtBot commented at 6:22 am on January 23, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/36039588773

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

brunoerg commented at 11:37 am on January 23, 2025: contributor

from CI:

0Run miniscript_smart with args ['/Users/runner/work/bitcoin/bitcoin/ci/scratch/build-aarch64-apple-darwin23.6.0/src/test/fuzz/fuzz', PosixPath('/Users/runner/work/bitcoin/bitcoin/ci/scratch/qa-assets/fuzz_corpora/miniscript_smart')]Assertion failed: (res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE), function TestNode, file miniscript.cpp, line 1152.
1Error processing input "/Users/runner/work/bitcoin/bitcoin/ci/scratch/qa-assets/fuzz_corpora/miniscript_smart/78ea0831413c5ae883473981e65e7e1b3b4e723c"
2
3Assertion failed: (res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE), function TestNode, file miniscript.cpp, line 1152.
4Error processing input "/Users/runner/work/bitcoin/bitcoin/ci/scratch/qa-assets/fuzz_corpora/miniscript_smart/78ea0831413c5ae883473981e65e7e1b3b4e723c"

miniscript: prepend ZEROs for nsat d411bd847c

DrahtBot removed the label CI failed on Jan 30, 2025

in src/script/miniscript.h:1218 in d411bd847c

1227+                        }
1228                     }
1229                     // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
1230+                    InputStack nsat_return;
1231+                    for (size_t i = 0; i < node.keys.size(); ++i) {
1232+                        nsat_return = std::move(nsat_return) + ZERO;

tnndbtc commented at 8:15 pm on January 30, 2025:

This was caught by running ci fuzz test in docker container: % cd /ci_container_base/ci/scratch/build-aarch64-unknown-linux-gnu/test/fuzz % ./test_runner.py -j8 -l DEBUG /ci_container_base/ci/scratch/qa-assets/fuzz_corpora/ miniscript_smart –empty_min_time=60

tnndbtc commented at 10:43 pm on January 30, 2025: none

@brunoerg @eriknylund and @darosior : I have reproduced the issue on CI fuzz test and made the fix. Now, it passed all checks. Please review when you are free. Thanks.

CC: @hodlinator

tnndbtc requested review from brunoerg on Jan 30, 2025

miniscript: fixes #29098 by only use first k valid signatures #31719

Code Coverage & Benchmarks

Reviews

Conflicts