Optimize 1-of-N thresholds to or()s

[darosior]

https://github.com/rust-bitcoin/rust-miniscript/pull/113 left out a FIXME that we are unsure to fix at all, opening this to clarify if we want it or not.

We now optimize N-of-N thresholds to and(), and i propose to do the same for 1-of-N thresholds (using or()s). After discussing this with sipa (who implemented this in C++) and @sanket1729 the main issue with the latter seems to be the exponential complexity with the number of or()s.

I personally think (user point of view) that if the complexity growth is only applied on the policy compilation it's fine, as we only ever compile once to miniscript per user and then store the Miniscript Descriptor while the Script size is felt onchain For Ever (:tm:).

[sanket1729]

Here are some more points for discussion.

1) The current C++ compiler does not produce an output for 1 of 21 in 5 minutes on my machine. The rust version is significantly slower than that. With such high thresholds and because of the op-code limit of ~200, we are also losing the optimality of the compiler, so some value of the compiler is lost. 2) It can be possible to have a feature guard allowing this, but I don't know if this is good engineering and might cause more maintenance in the future. 3) Given that we probably have to redesign the compiler(I don't know how yet!) for Tapscript. I don't think there is this change is worth it. My vote is to remove the FIXME and replace it with a link to this issue.

I also plan to address the compiler related confusion in a separate doc. #128

any comments @apoelstra ?

[apoelstra]

+1 to replacing the FIXME with a link to this issue.

I agree that we should not feature-gate functionality like this. If we can't do it efficiently then we should find a different way to approach it.

[darosior]

The current C++ compiler does not produce an output for 1 of 21 in 5 minutes on my machine. The rust version is significantly slower than that.

Anyway, we currently error for thresh(1, [pubkey;21]) compilations.

It can be possible to have a feature guard allowing this, but I don't know if this is good engineering and might cause more maintenance in the future.

Agreed that a feature guard is not the way to go. However, if we ever accept compilation flags as in https://github.com/rust-bitcoin/rust-miniscript/issues/114#issuecomment-674521507 (or we can think of other flags, eg MALLEABLE_OK) this could be sneaked in.

From my usecase, i would trade 5+ minutes of compilation time (we can probably optimize this nonetheless? IIRC sipa mentioned a bug for that in his implem) for more space optimisation.

[apoelstra]

But would you trade 5 years of compilation time? ;)

I wonder if we ought to give the compiler a timeout, and let it do wildly inefficient things as long as it can give up once it gets near the timeout.

[darosior]

But would you trade 5 years of compilation time? ;)

Maybe not :)

I wonder if we ought to give the compiler a timeout, and let it do wildly inefficient things as long as it can give up once it gets near the timeout.

iirc Sipa implemented this with a similar tradeoff.

[darosior]

Ok so it seems we actually have to do this according to the requirements in http://bitcoin.sipa.be/miniscript/ (1 < k < n) ? Cf https://github.com/rust-bitcoin/rust-miniscript/pull/242

[sanket1729]

For other readers of this issue, we updated thresh to include the bounds too. (1 <= k <= n) .

See https://bitcoin.sipa.be/miniscript/ for updated spec

[sanket1729]

Another interesting result here is that, in the case of taproot outputs at the top level, it is always better(for privacy and efficiency) to split these into different leaves.