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
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.
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
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"23Assertion 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
d411bd847coutdated
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;
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?
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) {
@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.
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.
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
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: 2025-05-31 00:12 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me