Performance decrease after tapscript miniscript #29098

1. 
   Sjors commented at 8:28 am on December 16, 2023: member

   Is there an existing issue for this?

   • I have searched the existing issues

   Current behaviour

   @eriknylund noticed while testing large multisigs that after 4f473ea515bc77b9138323dab8a741c063d32e8f sendtoaddress causes a timeout for much smaller (though still rather large) multisigs than before.

   #28212 (review)

   Expected behaviour

   Not sure, perhaps the performance decrease is justified. Ideally it would not slow down.

   Since these descriptors don’t involve any miniscript-specific operations, perhaps it’s possible to return earlier in whatever parsing / signing algorithm is involved here.

   Steps to reproduce

   Run the large multisig test in the above mentioned PR before and after the commit.

   Relevant log output

   No response

   How did you obtain Bitcoin Core

   Compiled from source

   What version of Bitcoin Core are you using?

   master@4f473ea515bc77b9138323dab8a741c063d32e8f

   Operating system and version

   macOS and CI

   Machine specifications

   No response

2. 
   fanquake commented at 11:04 am on December 18, 2023: member

   cc @darosior @sipa
3. fanquake added the label RPC/REST/ZMQ on Dec 18, 2023
4. fanquake added the label Descriptors on Dec 18, 2023
5. 
   darosior commented at 11:30 am on December 18, 2023: member

   Without profiling my hunch is that this performance decrease comes from using a less efficient but more optimal algorithm for satisfying a multi_a fragment: https://github.com/bitcoin/bitcoin/blob/3695ecbf680a66b718f97d504308578d001eec49/src/script/miniscript.h#L1178-L1205

   The previous algorithm would use the first k available signatures for satisfying a k-of-n multisig. The new algorithm uses the best (smallest) set of k signatures.

   Since two valid signatures would differ in size by at most a byte, it’s probably not worth using the more optimal algorithm for large multisigs..

6. 
   sipa commented at 1:56 pm on December 18, 2023: member

   That sounds very plausible, @darosior.

   If so, I think there is an approach that doesn’t lose optimality: keep track of the optimal satisfaction size, and once reached, don’t bother evaluation further keys?

7. 
   darosior commented at 2:00 pm on December 18, 2023: member

   Neat. This would give us the same performance in the large majority of cases while still being optimal in the rare non-SIGHASH_DEFAULT cases. In any case this would fix the slowdown you noticed @eriknylund.
8. 
   nickguo commented at 6:45 am on May 15, 2024: none

   Hello, is anyone actively working on this? – and if not, would this be an appropriate “good first issue”?
9. 
   eriknylund commented at 6:59 am on May 15, 2024: contributor

   Hello, is anyone actively working on this? – and if not, would this be an appropriate “good first issue”? @darosior replied to my (then) open PR that he has no plans to implement right now (see #28212 (comment)), so afaik no one is actively working on this. I can’t say if it’s a good first issue, but I would be happy to help with review in combination with my 999-of-999 tests if you want to have a go at it. ❤️

Contributors
Sjors fanquake darosior sipa nickguo eriknylund

Labels
RPC/REST/ZMQ Descriptors