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).

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

No conflicts as of last run.

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:1228 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:1247 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

hodlinator commented at 8:32 am on March 6, 2025:

Responding to #31719 (review): I think it would be more useful to add comments like this directly with the code, rather than in PR comments.

tnndbtc commented at 4:10 am on March 7, 2025:

Agree, added.

hodlinator commented at 7:27 pm on April 15, 2025:

Please resolve this thread as it is now in the code.

in src/script/miniscript.h:1215 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"

DrahtBot removed the label CI failed on Jan 30, 2025

in src/script/miniscript.h:1238 in d411bd847c outdated

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

hodlinator commented at 8:30 am on March 6, 2025:

Since the first commit causes the fuzzer to fail, and the approach in the project is that no commit should introduce errors, I think it makes more sense to squash the 2 commits into 1.
Please avoid inserting the loop in the middle of a pre-existing 2-line comment. Could you also add a comment describing why the added loop was necessary?

tnndbtc commented at 4:12 am on March 7, 2025:

Agree both. Provided comment on why adding the loop to generate number of ZEROs for nsat_return. Also, squashed multiple commits into one commit.

hodlinator commented at 9:37 am on March 7, 2025:

Thanks! Although you are still inserting the loop in the middle of the old comment. How about this? (Or putting the nsat_return-block with comment last, not sure what makes most sense).

0// for nsat_return, it expects node.keys.size() number of ZEROs, thus adding this for loop
1InputStack nsat_return;
2for (size_t i = 0; i < node.keys.size(); ++i) {
3    nsat_return = std::move(nsat_return) + ZERO;
4}
5auto& nsat{nsat_return};
6// The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
7// satisfying 0 keys.
8assert(node.k != 0);
9if (num_of_good_sigs < node.k) {

tnndbtc commented at 3:05 pm on March 7, 2025:

@hodlinator Ah, sorry, overlooked the comment part. Thank you for the example and I have made the change accordingly. Please have a look.

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

hodlinator commented at 9:25 am on March 6, 2025: contributor

Hi @tnndbtc,

Thank you for looking into this issue! Great to have someone more comfortable than me at touching more sensitive parts of the code. Leaving some feedback from my brief testing.

I think it would be good if this PR did one of either: a) Directly included 387c12e0813a863bc9728777719acbafe7b12a34 from #28212, or b) Not mention 387c12e0813a863bc9728777719acbafe7b12a34/#28212 as much as it is doing - instead focusing on #29098.

Having a timeout is more palpable than relying on reviewers to run timing comparisons, and including 387c12e0813a863bc9728777719acbafe7b12a34 in the PR removes the need for everyone to cherry-pick it, even if it will delay merge due to added review. Including the test would significantly decrease the need for all the testing instructions in the PR description as well.

(Would be nicer on the eyes if you used markdown formatting, ```-blocks and `code`).

tnndbtc force-pushed on Mar 7, 2025

tnndbtc commented at 4:20 am on March 7, 2025: none

@hodlinator Appreciate your valuable comments and reviews. I’ve made the changes accordingly so you can check them out one by one.

As for the choice “I think it would be good if this PR did one of either: a) Directly included https://github.com/bitcoin/bitcoin/commit/387c12e0813a863bc9728777719acbafe7b12a34 from #28212, or b) Not mention https://github.com/bitcoin/bitcoin/commit/387c12e0813a863bc9728777719acbafe7b12a34/https://github.com/bitcoin/bitcoin/pull/28212 as much as it is doing - instead focusing on #29098.”, I prefer b) because I haven’t done full code review for #28212 so I’d expect PR owner @eriknylund to focus on the original issue and address review questions by himself. So, just removed the reference of it in PR description.

tnndbtc force-pushed on Mar 7, 2025

sipa commented at 3:11 pm on March 7, 2025: member

@tnndbtc Have you considered my suggestion to instead of just picking the first k signatures, keep using the existing algorithm, but stop trying things as soon as the optimal size is reached? I suspect that that will in practice have the same performance as first-k, but won’t lose the optimality property the current algorithm has.

tnndbtc commented at 4:03 pm on March 7, 2025: none

@sipa Yes, I considered your proposal and it would still make the proposed test to timeout. self.do_test_k_of_n(999, 999)

I just responded your comment in the original thread here

DrahtBot added the label CI failed on Mar 27, 2025

tnndbtc closed this on Mar 30, 2025

tnndbtc reopened this on Mar 30, 2025

tnndbtc force-pushed on Mar 30, 2025

DrahtBot removed the label CI failed on Mar 31, 2025

tnndbtc force-pushed on Apr 3, 2025

DrahtBot added the label Needs rebase on Apr 10, 2025

tnndbtc force-pushed on Apr 13, 2025

tnndbtc referenced this in commit 1f5171f2e9 on Apr 13, 2025

tnndbtc force-pushed on Apr 13, 2025

DrahtBot removed the label Needs rebase on Apr 13, 2025

DrahtBot added the label Needs rebase on Apr 14, 2025

DrahtBot removed the label Needs rebase on Apr 14, 2025

maflcko commented at 2:31 pm on April 14, 2025: member

Please squash your commits according to https://github.com/bitcoin/bitcoin/blob/master/CONTRIBUTING.md#squashing-commits

tnndbtc referenced this in commit d36eb645df on Apr 14, 2025

tnndbtc force-pushed on Apr 14, 2025

tnndbtc referenced this in commit 9dd45d0164 on Apr 14, 2025

tnndbtc force-pushed on Apr 14, 2025

DrahtBot added the label Needs rebase on Apr 14, 2025

tnndbtc closed this on Apr 15, 2025

tnndbtc force-pushed on Apr 15, 2025

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

tnndbtc reopened this on Apr 15, 2025

DrahtBot removed the label Needs rebase on Apr 15, 2025