Miniscript optimization for slowly-decaying multisigs

[darosior]

Any multisig that decays by 1 key at every step can be represented as a single threshold instead of (nested) or() fragments. For instance or(and(pk(A),and(pk(B),pk(C))),and(thresh(2,pk(A),pk(B),pk(C)),older(42))) can be flattened into thresh(3,pk(A),pk(B),pk(C),older(42)). This generalizes to any number of spending paths, as long as they all have increasing timelocks, the very same set of public keys, and multisig thresholds that decrease by one on each step.

Currently Liana never benefits from this optimization for two reasons:

• It never builds a policy such as the same keys are repeated in the different spending paths. This can be addressed with some complexity by removing (and caching) the derivation paths of all xpubs in the policy, such as Miniscript tooling is able to recognize pairs of (origin, xpub) as being the same key (the same owner). The policy with duplicate keys may then be normalized or compiled to perform the optimization, if at all possible.
• Rust-miniscript is not able to perform this optimisation. The compiler does not support duplicate keys, and the normalization of abstract policies does not merge the nested thresholds in these conditions. It should be possible to implement the optimization in a somewhat general manner, but the conditions under which it is available are fairly specific to some (fairly specific) usages of Liana. I brought it up on the Miniscript IRC channel here.

I'm opening this issue for discussion. At present i believe the juice is not worth the squeeze. Note that in Taproot there is also a privacy tradeoff to this optimization.

[darosior]

One issue pointed by @pythcoiner is that we must be careful to keep the abstract policy we lift to always be an "N-ary or()". That is a list of spending paths that user facing logic can then iterate, for instance to present a neat list of spending paths to the user on the GUI.

Today a Miniscript like thresh(3,pk(A),s:pk(B),s:pk(C),sln:older(42)) would have Liana-compatible semantics but i think would be refused here:

liana/liana/src/descriptors/analysis.rs

Lines 620 to 628 in 369ef7c

	// The policy must always be "1 of N spending paths" with at least an always-available
	// primary path with at least one key, and at least one timelocked recovery path with at
	// least one key.
	let subs = match policy {
	SemanticPolicy::Thresh(thresh) if thresh.is_or() && thresh.n() > 1 => {
	thresh.into_data()
	}
	_ => return Err(LianaPolicyError::IncompatibleDesc),
	};

Because lifting the above Miniscript as a semantic policy would not be translated into an or() between the 4 spending paths during normalization, in the same way as such an or() would not get flattened into a thresh() as we would like to in the optimization described in OP.

So that's another thing that would need to be done to implement the optimization: we would need to generalize our analysis. Essentially what we need is to be able to iterate over all spending paths of a semantic policy.