Satisfier: track non-removable signatures when assessing timelock malleability

[guggero]

Requested by this comment.
PR #1037 introduces a new regression_1037 test that demonstrates this in src/miniscript/satisfy/mod.rs.

The following text is from GPT-6.

Problem

The satisfier passes a single root_has_sig boolean down to every timelock
fragment. This is intended to indicate that every satisfaction requires a
signature. When a timelock check fails:

• With root_has_sig, the branch is Witness::Impossible: the signature
  constrains the transaction's timelock fields, so a third party cannot change
  them to make the branch available.
• Without it, the branch is Witness::Unavailable: the satisfier cannot use
  it, but a third party might be able to change the transaction's timelocks.

This is a coarse approximation of whether the witness being constructed
contains a signature that a third party cannot remove. It can reject a
non-malleable witness because a timelocked alternative is treated as a
possible malleation.

The malleability enum makes this approximation more conservative: expressions
classified as Malleability::Malleable no longer retain a signature property,
even when every spend requires a signature. Consequently,
non_malleable_and_requires_sig() returns false for those expressions.

Reproduction

Consider the following Miniscript, parsed with from_str_insane:

and_v(v:pk(K),or_i(after(100),after(200)))

Provide a signature for K and an absolute height locktime of 100. Every
spend requires that signature. Only the first timelock is satisfied, and a
third party cannot change the transaction's locktime to select the other
branch without invalidating the signature.

Expected: satisfy returns the first branch's witness, [1, sig(K)].

Actual: the root is classified as malleable, so root_has_sig is false.
The unmet after(200) becomes Unavailable, and the two unsigned or_i
alternatives cause satisfy to return Error::CouldNotSatisfy.

The same problem occurs with
and_v(v:pk(K),or_i(older(100),older(200))) and a relative height locktime
of 100.

regression_1037 in src/miniscript/satisfy/mod.rs covers both cases. It
also demonstrates that satisfy_malleable returns the expected witness and
that explicitly passing root_has_sig = true to the internal satisfier
recovers that witness through the non-malleable algorithm.

[milah-247]

Hi! I'd like to work on this issue if it's still available.

From my reading, the satisfier passes a single root_has_sig boolean to every timelock fragment. For and_v(v:pk(K),or_i(after(100),after(200))), the root gets classified as malleable, so root_has_sig ends up false. The unmet after(200) then becomes Unavailable instead of Impossible, and satisfy returns CouldNotSatisfy even though every spend requires the signature for K.

My plan is to:

1. Start from the regression_1037 test in src/miniscript/satisfy/mod.rs, which covers both the after and older cases.
2. Track whether the witness being built contains a non-removable signature, rather than relying on the single root-level boolean.
3. Check that the regression_1037 cases pass and that the existing satisfier and malleability tests still pass.

I'm still fairly new to the codebase, so I'd appreciate any pointers on the preferred approach, or on whether this should wait for #1037 to merge first. I recently reviewed #1018 and have been building and running the test suite locally, so I'm comfortable with the workflow.

Thanks!

[apoelstra]

Track whether the witness being built contains a non-removable signature, rather than relying on the single root-level boolean.

This will not work. You do not know whether a non-removable signature will appear later in the witness, which will also affect your decision.