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

tnndbtc · 2025-01-23T05:37:27Z

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 · 2025-01-23T05:37:29Z

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.

Type	Reviewers
Concept NACK	darosior

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

Conflicts

No conflicts as of last run.

tnndbtc · 2025-01-23T05:47:13Z

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 387c12e

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

tnndbtc · 2025-01-23T05:47:55Z

src/script/miniscript.h

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

src/script/miniscript.h

tnndbtc · 2025-01-23T05:50:21Z

src/script/miniscript.h

This is to follow the original algorithm at:

bitcoin/src/script/sign.cpp

Line 287 in febe2ab

if (auto match = MatchMultiA(script)) {

which only take the first k valid signatures

DrahtBot · 2025-01-23T06:22:29Z

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

Hints

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

from CI:

Run 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.
Error processing input "/Users/runner/work/bitcoin/bitcoin/ci/scratch/qa-assets/fuzz_corpora/miniscript_smart/78ea0831413c5ae883473981e65e7e1b3b4e723c"

Assertion failed: (res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE), function TestNode, file miniscript.cpp, line 1152.
Error processing input "/Users/runner/work/bitcoin/bitcoin/ci/scratch/qa-assets/fuzz_corpora/miniscript_smart/78ea0831413c5ae883473981e65e7e1b3b4e723c"

tnndbtc · 2025-01-30T20:15:29Z

src/script/miniscript.h

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

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?

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

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

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

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

tnndbtc · 2025-01-30T22:43:07Z

@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

hodlinator

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 387c12e from #28212, or
b) Not mention 387c12e/#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 387c12e 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`).

hodlinator · 2025-03-06T08:30:30Z

src/script/miniscript.h

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?

src/script/miniscript.h

tnndbtc · 2025-03-07T04:20:48Z

@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 387c12e from #28212, or
b) Not mention 387c12e/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.

sipa · 2025-03-07T15:11:04Z

@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 · 2025-03-07T16:03:39Z

@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

maflcko · 2025-04-14T14:31:57Z

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

…itcoin#31719

Implements test coverage for Bitcoin Core issue bitcoin#28179, proving that 999-of-999 Taproot multisig descriptors work correctly while maintaining performance requirements. Changes: - Add C++ unit tests in descriptor_tests.cpp for 999-key multi_a validation - Add Python functional test for optimized 999-of-999 multisig operations - Test edge cases: 998-key (valid), 1000-key (invalid), threshold validation - Verify descriptor parsing, address generation, and spending patterns - Performance optimized: completes in ~400ms vs 40+ seconds in failed attempts This addresses the core requirements from issue bitcoin#28179: - Prove 999-of-999 multisig works (structure and spendability) - Reject 1000+ key multisigs with proper error messages - Test both 1-of-1000 and 999-of-1000 rejection cases - Maintain performance for production use Resolves previous failed attempts in PR bitcoin#28212 and bitcoin#31719 through optimized testing approach that validates functionality without triggering signature satisfier performance bottlenecks. 🤖 Generated with [Claude Code](https://claude.ai/code) Co-Authored-By: Claude <noreply@anthropic.com>

…8212 test of bitcoin#28212 rebased on top of bitcoin#31719

darosior · 2025-10-22T14:39:16Z

While it may be desirable, i don't think this is a priority (as demonstrated by the lack of reviewer interest). Concept NACK.

DrahtBot added the Descriptors label Jan 23, 2025

tnndbtc commented Jan 23, 2025

View reviewed changes

src/script/miniscript.h Outdated Show resolved Hide resolved

tnndbtc commented Jan 23, 2025

View reviewed changes

This was referenced Jan 23, 2025

Performance decrease after tapscript miniscript #29098

Open

test: verify spend from 999-of-999 taproot multisig wallet #28212

Closed

test: 999 of 999 multisig #28179

Closed

DrahtBot added the CI failed label Jan 23, 2025

brunoerg reviewed Jan 23, 2025

View reviewed changes

DrahtBot mentioned this pull request Jan 23, 2025

miniscript: convert non-critical asserts to CHECK_NONFATAL #31727

Merged

DrahtBot removed the CI failed label Jan 30, 2025

tnndbtc commented Jan 30, 2025

View reviewed changes

tnndbtc requested a review from brunoerg January 30, 2025 22:43

hodlinator reviewed Mar 6, 2025

View reviewed changes

tnndbtc force-pushed the fix-multi-sig-performance branch from ff54d7e to 727ef5d Compare March 7, 2025 04:07

tnndbtc force-pushed the fix-multi-sig-performance branch from 66ff942 to 8228521 Compare March 7, 2025 15:04

DrahtBot added the CI failed label Mar 27, 2025

tnndbtc closed this Mar 30, 2025

tnndbtc reopened this Mar 30, 2025

tnndbtc force-pushed the fix-multi-sig-performance branch from 8228521 to c1c1037 Compare March 30, 2025 23:21

DrahtBot removed the CI failed label Mar 31, 2025

tnndbtc force-pushed the fix-multi-sig-performance branch from c1c1037 to e3637d2 Compare April 3, 2025 20:23

DrahtBot added the Needs rebase label Apr 10, 2025

tnndbtc force-pushed the fix-multi-sig-performance branch from e3637d2 to 1f5171f Compare April 13, 2025 00:34

tnndbtc force-pushed the fix-multi-sig-performance branch from 8d15e67 to 5461f78 Compare April 13, 2025 00:41

DrahtBot removed the Needs rebase label Apr 13, 2025

DrahtBot mentioned this pull request Apr 13, 2025

miniscript: Correct off-by-one assert guards (#31727 follow-up) #32255

Merged

DrahtBot added Needs rebase and removed Needs rebase labels Apr 14, 2025

tnndbtc force-pushed the fix-multi-sig-performance branch from c36fb79 to d36eb64 Compare April 14, 2025 18:04

tnndbtc force-pushed the fix-multi-sig-performance branch from fc3ac01 to 9dd45d0 Compare April 14, 2025 18:09

DrahtBot added the Needs rebase label Apr 14, 2025

tnndbtc closed this Apr 15, 2025

tnndbtc force-pushed the fix-multi-sig-performance branch from 9dd45d0 to cdc3299 Compare April 15, 2025 18:16

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

2e38925

…itcoin#31719

tnndbtc reopened this Apr 15, 2025

DrahtBot removed the Needs rebase label Apr 15, 2025

DrahtBot added CI failed and removed CI failed labels May 16, 2025

gianlucamazza mentioned this pull request Aug 22, 2025

test: Add comprehensive tests for 999-of-999 Taproot multisig #33239

Closed

4 tasks

ubbabeck pushed a commit to ubbabeck/bitcoin that referenced this pull request Oct 19, 2025

test: verify spend from 999-of-999 taproot multisig wallet bitcoin#2…

a4764ee

…8212 test of bitcoin#28212 rebased on top of bitcoin#31719

ubbabeck mentioned this pull request Oct 19, 2025

test: multisig verify spend from 100 of 999 taproot multisig wallet #33658

Closed

achow101 requested a review from sipa October 22, 2025 14:38

achow101 closed this Oct 22, 2025

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

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

Uh oh!

Conversation

tnndbtc commented Jan 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Jan 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

tnndbtc commented Jan 23, 2025

Uh oh!

tnndbtc Jan 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tnndbtc Jan 23, 2025

Choose a reason for hiding this comment

Uh oh!

DrahtBot commented Jan 23, 2025

Uh oh!

brunoerg left a comment

Choose a reason for hiding this comment

Uh oh!

tnndbtc Jan 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hodlinator Mar 6, 2025

Choose a reason for hiding this comment

Uh oh!

tnndbtc Mar 7, 2025

Choose a reason for hiding this comment

Uh oh!

hodlinator Mar 7, 2025

Choose a reason for hiding this comment

Uh oh!

tnndbtc Mar 7, 2025

Choose a reason for hiding this comment

Uh oh!

tnndbtc commented Jan 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

hodlinator left a comment

Choose a reason for hiding this comment

Uh oh!

hodlinator Mar 6, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tnndbtc commented Mar 7, 2025

Uh oh!

sipa commented Mar 7, 2025

Uh oh!

tnndbtc commented Mar 7, 2025

Uh oh!

maflcko commented Apr 14, 2025

Uh oh!

darosior commented Oct 22, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

tnndbtc commented Jan 23, 2025 •

edited

Loading

DrahtBot commented Jan 23, 2025 •

edited

Loading

tnndbtc Jan 23, 2025 •

edited

Loading

tnndbtc Jan 30, 2025 •

edited

Loading

tnndbtc commented Jan 30, 2025 •

edited

Loading