Figure out how I can satisfy a descriptor without actually generating signatures

[LLFourn]

This library's "satisfaction" API can help you build a witness/scriptsig given something containing signatures and other assorted satisfaction material (hash pre-images etc). What if I want to find how how I am going to satisfy a descriptor before producing signatures. This amounts to finding out which subset of my keys (perhaps represented by fingerprint & origin) do I need to engage to create the optimal witness. Here are the reasons I want to do this:

1. Figure out the witness weight before coin selection (right now in bdk we use max_satisfaction_weight).
2. Populate PSBT fields before signing based on the satisfaction path you plan to use (rather than populating every possible field as was the approach in PsbtEx::update_desc include derivation paths for bip32 keys #335).
3. Following on from (2), so I can know which keys I actually need to sign under rather than signing with all possible keys.

Here's two possible approaches:

Reuse the existing satisfaction API (hacky)

Create a custom Satisfier which when asked for a signature under key outputs a random bogus signature. Internally this custom Satisfier would index each public key requested by the random signature. When get_satisfaction finally outputs the witness (or scriptsig) you look for which bogus signatures made it into the final witness and lookup the associated public keys to find the set of keys used. A similar thing can be done for hash pre-images.

Create a new "satisfaction plan" module

The logic of which would essentially mirror the existing satisfier module except instead of using concrete signatures to create a concrete witness it would create something like an abstract witness ("witness template" maybe) from a list of asset keys which the application could access if need be (perhaps represented by fingerprint & origin). From this template you could determine which subset of keys require signatures (and under which tapleaf etc). The witness template could also give you a good estimate of the witness size.

In my mind this module could actually replace the existing satisfaction module as I think it is more general. Consider that you want to simply finalize a PSBT input with the signatures in it (what Descriptor::satisfy with a PSBT does). You could do this like:

1. Try to create a satisfaction plan using the keys that have entries in partial_sigs or tap_key_sig and tap_script_sigs as the asset keys.
2. If the plan is successfully created then you can satisfy it, so go through the signature items in the witness template and replace them with the signatures in PSBT

(I've skipped a bunch of details like timelocks and hash images and pre-images here but I hope you can image they work in a similar way).

Any other ideas?

For background discussion see #451

[apoelstra]

The planning API was introduced in #592 :)