Detect key reuse in policy and Miniscript (was: Optimise policy compilation when keys are shared across branches)

[darosior]

Currently, the policy needs to be tweaked to get the most optimized Bitcoin Script when thresh() that share some keys are used across or() branches.

For example:

or(thresh(4,pk(A),pk(B),pk(C),pk(D)), thresh(4,pk(A),pk(B),pk(E),pk(F)))

Currently returns (on http://bitcoin.sipa.be/miniscript/, but tested the same behaviour with rust-bitcoin locally)

OP_IF
  <A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY <C> OP_CHECKSIGVERIFY <D>
OP_ELSE
  <A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY <E> OP_CHECKSIGVERIFY <F>
OP_ENDIF
OP_CHECKSIG

    Script: 282 WU
    Input: 293.500000 WU
    Total: 575.500000 WU

And needs to be optimized by hand:

and(thresh(2,pk(A),pk(B)),or(thresh(2,pk(C),pk(D)),thresh(2,pk(E),pk(F))))

To return

<A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY OP_IF
  <C> OP_CHECKSIGVERIFY <D>
OP_ELSE
  <E> OP_CHECKSIGVERIFY <F>
OP_ENDIF
OP_CHECKSIG

    Script: 212 WU
    Input: 293.500000 WU
    Total: 505.500000 WU

Would a PR adding an analysis of duplicated keys to the policy compiler be welcome ?

[apoelstra]

Sorry for getting to this so late.

The short answer is no -- if keys are reused in Miniscript then none of our malleability analysis works, so this is not something that we support. A PR to detect repeated keys and to have the compiler fail might be welcome, though we'd have to have some discussion on IRC first.

Also, it is not tractable in general to eliminate repeated keys (or more generally, repeated subexpressions). What was your algorithmic strategy going to be?

[sanket1729]

Recalling our IRC discussion on this and some of Pieter's comments.

darosior: Has the inclusion of an analysis of duplicated keys in policy compilers already been discussed (any implem) ?
sanket1729: It is difficult to guarantee non-malleability if the scripts has duplicated keys.
sanket1729: We can transfer witness from one satisfaction to another.
sanket1729: darosior: I saw your issue, my hunch is that it not always possible to convert duplicated keys into an equivalent policy such that the resultant policy only contains one key
sipa: i think analysis of duplicate keys would just be "does it have repeated keys? if so, can't say anything about nonmalleability"
sanket1729: He is suggesting that in some cases it is possible to convert policy description that has key reuse into another one where there is no key-reuse.
sanket1729: See #115
sipa: sure
sipa: but not always
darosior: Indeed, but could we at least try to optimize in some simple cases similar to the one I mention in the issue ?
sipa: but i don't think it's an optimization
sipa: you're giving the policy in a degraded equivalent notation
sipa: in general, if you have a policy with repeated keys, we'll just fail to compile

@apoelstra Should we detect repeating keys polices and fail our compiler on those.

Note that implementing this would have two engineering costs to our codebase

1. Translation of policies can fail. So, there would be an API change.
2. Many of our testcases rely on repeated keys in DummyKey struct making all of those invalid. I cannot directly see a clean way to have the current DummyKey struct and support detecting repetitive keys.

[apoelstra]

To answer (2), we could impl PartialEq and Eq on DummyKey to have it always return false :P

[sanket1729]

But then equality tests of miniscript roundtrip would fail

[darosior]

Changed the title to a feature request for detecting duplicated keys. This would indeed be great to have.

[apoelstra]

Agreed. But I really don't know what we should do about DummyKey.

Maybe we need to make it DummyKey(char) or something and then change all our tests to give single-letter names to all the keys..

[sanket1729]

There are two solutions that I can think of.

1. As @apoelstra mentioned, changed DummyKey to DummyKey(str) where it merely becomes equivalent to String. Or only allow a restricted number of instantiations with char.
2. Add something doc(hidden) in MiniscriptKey that detects whether something is DummyKey. We already have
   is_uncompressed() in MiniscriptKey, so there is precedent for doing these kinds of things :P . The pro here, we don't have to change all our tests.

[apoelstra]

Done in #168