Bug: `thresh(k, pubkeys[21])` policy does not compile for `k < 3`

[darosior]

<sanket1729> Yup, that is indeed a bug. The issue is for k = 1 to 3, we pick sub-compilations for children optimally. All pk() are mapped to pkh() with a likely wrapper and that exceeds the max-opcount for 200 
20:01 <sanket1729> The correct compiler logic would pick optimal compilation for children keeping tract of possible op-counts. 
20:02 <sanket1729> But that would lead to even slower compiler with high space requirements. 
20:03 <sanket1729> For k = 4, the probabilities for leaf are high, so their optimal compilations are mapped correctly under the MAX_OP_COUNT
20:03 <sanket1729> sipa: Do you have any inputs?
20:04 <jeremyrubin> "taproot fixes this"
20:06 <sipa> lol
20:06 <sipa> yes
20:06 <sanket1729> Maybe, if the optimal greedy compiler fails. We should build another version that minimizes the op-counts but still constructs some miniscript. 

Should Taproot or us fix this ?

[sanket1729]

I am locally able to compile for k = 3. Fails for k = 2 and k = 1. Any inputs @apoelstra ?

[apoelstra]

No input. Let's leave this bug open so we know this is an issue we need to deal with. But honestly I'm tempted to just call this a bug in Script rather than a bug in the Miniscript compiler. I think, if you're working with policies so large that they bump against the consensus limits you're probably going to have to hand-roll your Miniscripts rather than using this compiler. And there's a pretty narrow range where you're "bumping against the limits" but there still exist legal compilations, and I'm hesitant to add more complexity.

Having said this I think it would be useful in general if we had an option to tell the compiler to do space-optimization (or other forms of optimization than the "minimize weighted weight" scheme that we have). If we ever implement that, then it would be easy to add code that would attempt a optimize-space compilation after failure.

[sanket1729]

I am going to leave this a wont-fix for now. The current compiler operates on a greedy basis by choosing children that minimize total weight. However, the output is also bounded by various other factors like the number of witness items, or op-code count during execution(CMS miscounting).

While it is possible to address this, it is not worth the effort to consider all stack_elem_count while compiling. For example, it is possible that higher weight, but lower stack_elem_count exists, but our greedy algorithm cannot find it.

These problems are addressed to a large extent with taproot as the resource limitations are either really large or completely removed.
Keeping this issue open to discuss more ideas or incase anyone else bumps into this