Signature re-use and Miniscript

[apoelstra]

This is more of a blog post than an issue, but not sure where best to file it to get some comments.

In #906 (comment) Jeremy Rubin makes the interesting observation that the Miniscript

<bob> checksigverify IF 12 CSV <Alice> ELSE <Carol> ENDIF Checksig

has the semantic "Bob signs, then depending on circumstances, either Alice or Carol signs". However if we were to split this up into two tapbranches, the semantic is slightly changed: now Bob's signature is tied to one branch or the other, so to get the previous semantics, Bob would need to sign both branches. (And if he chose not to, he could hold funds hostage or otherwise potentially gum up a protocol.)

In many past private discussions, we've viewed this "signatures can be reused across branches" possibility as a sort of vulnerability, or at least an unintended consequence of Bitcoin's sighash algorithm, and we've speculated about adding a new pk_k-type fragment which included a CODESEPARATOR opcode. We've not done this because CODESEPARATOR is poorly supported by wallets, would waste an extra byte per key, and equivalent semantics can be obtained by just making sure each branch has a distinct key.

Indeed, our "sanity" rules forbid duplicate keys in both Miniscript and Policy. And we've considered that we should be able to relax this rule to allow duplicate keys as long as they appear in distinct tabbranches. But we haven't done this relaxation either because Policy currently lacks a way to indicate a "tapbranch or". Historically we've basically let the compiler do anything that's possible/well-typed, and trusted the Miniscript type system to prevent this from causing surprises. We knew, at least in principle, that CODESEP might mess this up. Jeremy's point is that even Taproot has messed this up.

My thought is that if we've already broken this seal, let's go ahead and add a pk variant with CODESEPARATOR. But curiously, this has weird/surprising semnatics and doesn't do what we want! Let's return to Jeremy's example to see why. Imagine now that Alice and Carol each use the codesep-bearing pk_k:

<bob> checksigverify IF 12 CSV <Alice> CODESEP ELSE <Carol> CODESEP ENDIF Checksig

Here we retain the original "Bob signs and walks away, and Alice and Carol figure out the rest of the witness" scenario. But if instead we swap the top-level or, we get

IF 12 CSV <Alice> CODESEP ELSE <Carol> CODESEP ENDIF Checksigverify <bob> checksig

Now Alice and Carol's codeseparators "leak out" and affect Bob's signature, and we have the Taproot semantics! This is particularly alarming because all I did was swap the two children of the top-level or, something the policy compiler currently does when attempting to optimize. I therefore believe that if we add CODESEPARATOR to Miniscript, we want to do it as part of our ors rather than as part of our pks, and we need to be careful when compiling them.

I believe we need to extend the policy language to somehow indicate a "tapbranch or", and while we're at it, I think we should extend Miniscript to add a variant of all four disjunctions that puts CODESEP before each child. When compiling to Taproot, these ors would become distinct Tapbranches. When compiling to pre-Taproot scripts, these would compile to ordinary

When compiling to Taproot, tapbranch ors" are required to be "top-level" combinator. That is, you cannot nest them inside any ands threshes or normal ors. Curiously, the same property needs to apply to the new CODESEP-orvariants! For example, if ouror(bob,or_tap(alice,csv+carol))` policy were compiled using CODESEPARATOR, it would look like one of

1. IF CODESEP 12 CSV <Alice> ELSE CODESEP <Carol> ENDIF Checksigverify <bob> checksig
2. <bob> checksigverify IF CODESEP 12 CSV <Alice> ELSE CODESEP <Carol> ENDIF Checksig

i.e. it might have Taproot semantics, might have legacy semantics, and the user can't easily predict which one they'll get.

But if only top-level ors were allowed to have CODESEPs, there's no problem! We will reliably get Taproot-like semantics, if and only if the user writes a policy with Taproot-ors in it.

[apoelstra]

In the past we've imagined having a "privacy knob", or multiple compilers, to let users choose whether to compile a policy with a maximally large Taptree or not. In light of Jeremy's concern, I think this is a bad approach and I think that policy authors need to explicitly opt into Taproot-ors if that's what they want.

Then we can have a single compiler (or at least, one compiler per descriptor type), which will always compile Taproot-ors into multiple tapbranches (for Taproot) and will always compile them into CODESEP-bearing ors (for pre-Taproot).

[apoelstra]

We should also add a 'Taproot thresh', which in pre-Taproot would be a new thresh combinator that added CODESEP, and in Taproot would do a combinatorial explosion of Tapbranches.

I guess we would want a compiler setting to put a limit on how many branches are allowed to be produced. If the policy would exceed the limit, the compiler would be allowed to fail or to just fallback to old-style CODESEP branches/thresholds.

[apoelstra]

cc @sipa @darosior @JeremyRubin I'd appreciate your thoughts on this whenever you get a chance

[JeremyRubin]

Were I designing an "easy" soft fork around this, I think what I would do is allow an additional data tag (non annex, on stack) to get hashed in instead of the leaf itself.

Then at script compile time you could either specify which tags a script will accept, and at signing time you can pick which tag you want to sign from.

E.g., suppose there is a set of tapleafs where i want the signatures to be fungible across, then I could just sign them all with the same tag.

A second way of doing something similar would be to sign the tap-path up to a certain depth. E.g., all scripts under this internal node can use this signature.

Alternatively, I would just drop the leaf entirely, but I recognize there are reasons you might want it covered.

---

I'm not sure this gives any insight here, but maybe thinking through blue-sky options might help with what can be done today to emulate that behavior?

[kwsantiago]

On "what can be done today": compile_tr_native (#906) already decomposes into tapbranches with a max_leaves cap, so the explosion handling for the thresh case has a working reference. It gives the per-leaf-signature semantics, not the fungible-across-leaves one, so it's the opposite end of what you're describing but it's buildable now.

On the API: agree with explicit opt-in over a privacy knob. A flag that silently changes signing semantics is the same footgun as reordering the or children, the user can't tell from the policy which semantics they got.

If the direction is a Taproot-or / Taproot-thresh combinator that always decomposes into tapbranches, happy to reshape the compile_tr_native work into that.

[darosior]

Having a signature that commits to a specific spending path strikes me as the best / safest default. Also, a single-script policy and(A,or(B,C)) whereby a single signature from A unlocks 2 spending paths boils down to satisfaction malleability from a participant in the Script, which is explicitly ruled as out of scope for the Miniscript framework. I'm skeptical that we need to support applications that rely on this type of satisfaction malleability in the policy compiler, let alone make it the default with wallet authors having to explicitly signal that they want a clean separation of all spending paths.

Taking a step back, this goes in the direction opposite to where i think the policy language should be heading. I think we should introduce more abstractions rather than require the end user to make more choices that are arguably in the realm of what the Miniscript framework should provide. For instance, the compiler expects policies with specific keys, enforcing the duplicate key rule already at this level. This forces users to apply a pre-compilation step before using the policy compiler, rather than specify a straightforward spending policy. A better interface would take a policy specifying a set of signers, and compile that to a Miniscript that may use more than one key for each signer under the hood.

It seems fine to also support advanced users hinting the compiler that they expect some sub-expressions to be part of the same leaf, and specify keys directly rather than signers. But we should also specify what we expect from the policy compiler. Should it be a straightforward, footgun-free interface for users to give abstract spending policies and get a safe-and-somewhat-optimized Script in return? Should we try to support a variety of optimizations and malleability requirements an advanced user may desire, or do we say at some point one can also just design the Miniscripts for his advanced application by hand?

[JeremyRubin]

It's not really an "advanced user requirement" it's a fundamental question of how software using Miniscript / Policy can be used.

thresh(2, A, B, C) means Alice can go and sign and satisfy with either Bob or Carol later, not knowing if it's ultimately with Bob or Carol.

TR{ABC, {AB, AC, BC}} means that Alice must know a priori if her signature should combine with Bob or Carol, or must know to generate a signature per branch if it's "don't care" or some subset otherwise.

As a protocol developer, you have to know which circumstance you are in. Because thresh(2, A, B, C) is the current behavior / legacy behavior and it happens to be the more permissive option, we haven't really noticed this complexity, because the default is free, malleable, combination of signatures.

Moving to a TR decomposed world inherently means that users need to do something different.

The burden of this choice has to be paid for somewhere. It can be paid by a combination of miniscript devs, miniscript policy authors, or miniscript specific policy users.

[pythcoiner]

TR{ABC, {AB, AC, BC}} means that Alice must know a priori if her signature should combine with Bob or Carol, or must know to generate a signature per branch if it's "don't care" or some subset otherwise.

Anyway you have to decide which leave you'll spend with before signing, as you need to process fees before signing, and if you want to avoid this the taptree must be crafted manually to keep all leaves at same depth.

[apoelstra]

@darosior

Having a signature that commits to a specific spending path strikes me as the best / safest default.

I agree with this. Though if we add a different form of or to the Policy language, I think the Taproot one has to be the new one, so that old scripts continue to work without surprising failures or behavior changes.

Also, a single-script policy and(A,or(B,C)) whereby a single signature from A unlocks 2 spending paths boils down to satisfaction malleability from a participant in the Script, which is explicitly ruled as out of scope for the Miniscript framework.

I agree with you in principle, but in practice there's currently no way to specify which branch you intend to sign for, so if we make a change that "just tightens up this form of out-of-scope malleability", we'll be breaking users' signing workflows.

Another consideration is that for Taproot, the BIP 371 PSBT fields enforce that users provide distinct signatures for different branches. While for some sort of synthetic CODESEPARATOR-based Taproot emulation, there is no such PSBT support.

The PSBT situation does support your case: it's technically impossible for PSBT users to be unaware of the different-paths-mean-different-signatures distinction because they have to specify a leafhash (in the <keydata> of PSBT_IN_TAP_SCRIPT_SIG), so it's not like they can blindly make a signature for a single branch and think that they're making a signature for all of them. (And conversely, if we add a CODESEPARATOR-based form of Taproot emulation, it will be quite difficult for users to specify this, since the BIP-174 PSBT_IN_PARTIAL_SIG gives them no room to do this.)

It does lead to the question of "what should the 'default signer' in rust-miniscript do?" ... presumably it should sign all the branches? Or maybe "sign all the branches for which the feerate is acceptable (and entirely reject cases where duplicate leafhashes appear at different heights, or the whole tree isn't visible)"? Hard to say.

I'm skeptical that we need to support applications that rely on this type of satisfaction malleability in the policy compiler, let alone make it the default with wallet authors having to explicitly signal that they want a clean separation of all spending paths.

Taking a step back, this goes in the direction opposite to where i think the policy language should be heading.

Here I disagree with you (and agree with @JeremyRubin). Going from "you sign the transaction" to "you sign the transaction and a specific branch" seems like a meaningful semantic change to me, and one that ought to be reflected in Policy.

You make a good point that forcing users to tweak their own keys (or whatever) to get distinct keys everywhere is already onerous. But similarly, different keys mean a different signing process and that also seems to me like something we should enforce in Policy.

It seems fine to also support advanced users hinting the compiler that they expect some sub-expressions to be part of the same leaf, and specify keys directly rather than signers. But we should also specify what we expect from the policy compiler. Should it be a straightforward, footgun-free interface for users to give abstract spending policies and get a safe-and-somewhat-optimized Script in return? Should we try to support a variety of optimizations and malleability requirements an advanced user may desire, or do we say at some point one can also just design the Miniscripts for his advanced application by hand?

Yeah, these are all great questions.