WIP: Output descriptors/miniscript support

[jgriffiths]

Based on the excellent work of @k-matsuzawa in https://github.com/ElementsProject/libwally-core/pull/202 (which this PR replaces).

The major changes from the original PR are:

• Use the new _n api call variants to work directly from the input string
• Use wally_map for variable substitutions.
• Expose descriptor canonicalization
• Remove all sub-allocations while parsing, reduce allocation sizes.
• Expose to SWIG targets
• Extend the test cases
• Various minor bug fixes, speedups, simplifications and a little renaming

This PR also includes a change to BIP32 path derivation allowing public-only hardened derivation from private extended keys.

@k-matsuzawa I would be very grateful if you could review when you have time.

[jgriffiths]

Note that the parsing code still allocates a large buffer for each child when generating scripts; I intend to fix this by computing the exact required length up-front in the future. Since this is an internal change, it won't affect the exposed API/ABI.

[darosior]

I still plan to review this. (Sorry for taking so long with #202..)

[jgriffiths]

I'm sorry.

The implementation is totally suitable for typical use, please don't apologise! My desire to reduce these allocations is only for the special case of using wally on constrained devices like Jade and the bitbox02, but I don't expect external contributors to have to optimise for that when submitting!

[Sjors]

Would it make sense to split out Miniscript parsing and do that later / separate? I thought there were still some pending changes to the Miniscript syntax to make it compatible with descriptors? https://github.com/bitcoin/bitcoin/pull/16800#issuecomment-903211605

[darosior]

The Miniscript syntax for P2WSH is now final. The pkh() and pk() aliases, as well as the rename of thresh_m() to multi() made the syntax of Miniscript descriptors backward compatible with "legacy" descriptors.

[jgriffiths]

Note: Moving back to WIP, I think we need a couple more features.

[LeoComandini]

utACK 99b25e063ed782aa737ee02674fe4d88eedae7d0 (just the first commit "bip32: Allow public path derivation with hardened child elements"), with comment

[Sjors]

There's a couple of functions that I would find quite useful, for sanity checking a multisig wallet:

• infer the (sub)descriptor type(s): e.g. it's a witness script hash (KIND_DESCRIPTOR_SH) with a sorted multisig (KIND_DESCRIPTOR_MULTI_S )
• for multisig: get the threshold value
• extract xpub(s)
• know if it's ranged, and if not: which index
• infer the network (though you can't distinguish testnet, regtest and signet, and you can't tell from a hex public key, so maybe this is not realistic)

All of that currently happens internally in descriptor.c. Could wait for a followup.

[Sjors]

Similar to what I'm suggesting in https://github.com/bitcoin/bitcoin/pull/24147#issuecomment-1029278730, instead of introducing all of Miniscript you could start with the subset that's needed for current descriptor functionality: KIND_MINISCRIPT_PK(_K), KIND_MINISCRIPT_PK(H/_H), and KIND_MINISCRIPT_MULTI. You only need TYPE_B and TYPE_K and none of the PROP_ logic.

That allows you to introduce a bunch of plumbing, without the need for reviewers to understand all of Miniscript. And in combination with my suggestions above, it's already practically useful for building single- and simple multisig wallets in a way that's compatible with what's out there (Specter, ColdCard, etc).

[darosior]

For the Miniscript part, how about we look into making https://github.com/sipa/miniscript/ a library and exposing a C API?

[jgriffiths]

For the Miniscript part, how about we look into making https://github.com/sipa/miniscript/ a library and exposing a C API?

C++ code is not acceptable for wally, and our implementation requirements are stricter than some other implementations; because we need to work on embedded devices and hardware wallets we need to constrain both code size and stack/memory usage for exposed functionality.

[darosior]

Is it still WIP? What is left to be done there? Any way i can help this work to move forward?

[jgriffiths]

Is it still WIP? What is left to be done there? Any way i can help this work to move forward?

Hi @darosior sorry for the late reply. This PR is still WIP for 2 reasons:

1 - The interface currently only allows generating one script type; I'd like to extend this to be able to generate scriptsigs, scriptpubkeys and witness scripts (as well as tapscript in due course) 2 - The creation of scripts internally currently requires a lot of memory which needs fixing in order to work well on smaller devices like the Jade or Bitbox02

Item 1 is a pre-requisite for merging as it will change the API interface slightly. 2 is not blocker for merging as the internals can be refactored once the interface is stable.

I am currently working on PSBT v2/PSET support for wally, and hope to be able to re-visit this following that. Unfortunately I have rather extreme demands on my time at present.