Extensions to standard tooling for TEMPLATEHASH-CSFS-IK support

[Antoine Poinsot]

Hi everyone,

Last year Greg Sanders and i presented what we think is a good stopping point in
terms of expanding scripting capabilities[^0], and then introduced along with
Steven Roose a proposal implementing those capabilities[^1].

I'm following up on this topic today by proposing some extensions to standard
tooling to support the new primitives introduced by our proposal. All the
additions to the PSBT and Miniscript descriptors specifications described
here have been implemented in a proof-of-concept PR to Bitcoin Inquisition[^2],
on top of the OP_TEMPLATEHASH implementation[^3]. This is very much exploratory
at this stage. I am seeking feedback on my design choices and on whether anything
is missing.

Let me start with the integration of the new primitives in Miniscript
descriptors. This wasn't completely straightforward, since some new capabilities
like template hash checks break some invariants, and some primitives like
rebindable signatures require additional context. With some adjustment however,
all the new capabilities fit reasonably well in this framework.

The goal was to enable the following:
- ability to use the Taproot internal key as a key fragment in place of
hardcoded public keys;
- ability to assert that the spending transaction matches a hardcoded template
in a given spending path;
- ability to check a signature for an arbitrary message in a given spending
path;
- ability to use a rebindable signature check in place of the regular
transaction signature check ('c:' fragment).

The Taproot internal key was introduced as a new `pk_i()` fragment, along with a
`pki()` alias for `c:pk_i()` in the same vein as `pk()` and `pkh()`. The
fragment corresponds to the Bitcoin Script `OP_INTERNALKEY`, has type 'K', type
properties 'o', 'n', 'd', 'u', 'k' and malleability properties 's', 'e' (the
very same properties as the `pk_k` fragment). Implementing this fragment only
introduces a requirement on the Script and string parsers to have access to the
Taproot internal key corresponding to the (mini)script being parsed. See the
commit message in the PR linked above for the details of how this was done in
the Bitcoin Core implementation.

Something i think noteworthy is how before the introduction of these primitives,
it was always the case that a fragment that has the 's' malleability property
("satisfying this expression always requires a signature") also guaranteed that
all spending paths were encumbered by at least one signature check. This in turn
limited third-party tempering to the extent permitted by the chosen sighash
mode at signing time. Both the Bitcoin Core and Rust-Bitcoin implementations
rely on this invariant[^4][^5], using the presence of the 's' property to verify
that no spending path lacks a transaction signature check.

But some of the new capabilities introduce signature checks (which require
access to a private key, and therefore should have the 's' property) that are
not over the transaction. And vice-versa, some checks that encumber the spending
transactions' outputs, and therefore should make the Script "sane" or "safe to
spend" but (arguably) not have the 's' property. Therefore i split the 's'
property into 's' (private key knowledge demonstrated) and 't' (all spending
paths encumber the spending transaction) as a preparation step for the following
fragments. All pre-existing fragment that have the 's' property (`0`, `pk_k()`,
`pk_h()`, `multi()`, `multi_a()`, `c:`) also get the 't' property. (nit: the 't'
property is technically not really a type property, since no other fragment
depend on it, but also not a "satisfaction malleability" property, it's more of
a third type of "safety" property. In this writeup i'll use it interchangeably
with type properties for the sake of brevity.)

A new `th(h)` fragment is introduced. It corresponds to the Script `<h>
OP_TEMPLATEHASH OP_EQUAL`. It is of type 'B', with type properties 'z', 'u', 't'
(i.e. encumbers the spending transaction), 'k' and with no (specified)
malleability property. The main design decision here was to pass the template
hash, and not its preimage, as argument to the `th()` fragment. This is closer
in effect to the four hash fragments, while `th()` is conceptually closer to
`older()` and `after()` in that it enables limited introspection on the spending
transaction. Since the preimage is not necessary to build/parse the Script, and
since having a full transaction in the descriptor would be unreasonable anyways,
i went with the template hash as the argument. This seems relevant to the
discussion of whether we want the descriptor language to encode all (public)
information necessary to spend an output, or if it's fine for it to only
partially contain that information[^6]. Note that `th()` does not have the 's'
malleability property, because we can't assume its satisfaction is not always
available, and does not have the 'f' malleability property because, unlike
`older()` and `after()`, a dissatisfaction may be available.

Up until now, all signing in Miniscript implicitly happened over the spending
transaction's sighash. The Miniscript satisfier relied on this invariant to
support composable `K`-typed fragments in addition to simpler leaf key fragments
(`pk_k`, `pk_h`, and now `pk_i`), by triggering the signing logic directly at
the key fragment level, such that the availability of a spending path could be
immediately propagated upward the tree, all the way toward the
signature-checking fragment.

But we are now going to introduce fragments that check a signature against
different messages (rebindable signatures, and arbitrary message signatures), so
the leaf key fragment needs to have the context of which type of signature is
expected. Since there is always exactly 1 signature-checking fragment for N
`K`-typed sub-fragments, this context can simply be propagated downward the tree
from the signature-checking fragment all the way to the leaf key fragment(s).

We introduce a new `cms(X,m)` fragment, which takes a sub-fragment of type `K`,
an arbitrarily-sized (within the consensus limits) message `m`, and corresponds
to the Script `[X] <m> OP_SWAP OP_CHECKSIGFROMSTACK`. It always has type
properties 'u' and 's'. Its type properties 'o', 'n', 'd', 't, 'h', 'i', 'j' and
'k' are equal to that of its sub-fragment. Same for its malleability properties
'f' and 'e'. Interestingly, the order of arguments in BIP 348 is such that an
additional `OP_SWAP` is necessary to support composable keys (in place of a
hardcoded key expression) in Miniscript. This does not mean that BIP 348 should
necessarily be amended, as the Miniscript framework could equally be adapted to
support "wrapped key" types (the equivalent of 'W' but for 'K' instead of 'B').
I'm ambivalent about setting the 's' property (which is explicitly set here, but
importantly also propagated from the key fragment leaves), because it seems that
for this fragment a third party should be able to get ahold of a signature for
the arbitrary message more easily than for transaction signature checks. The
distinction does not seem quite tractable at the Miniscript level, but always
ripping-off the 's' property for this fragment may be a saner default, since a
spending path that contains an arbitrary message signature should likely always
also contain a transaction signature check. Or maybe a `th()`? In which case it
wouldn't get the 's' property at all. At the end of the day this is only about
analyzing satisfaction malleability, not correctness, but i am curious what
others think about this.

Finally, we introduce an 'r:' wrapper, the analog of 'c:' but for rebindable
signature checks. It corresponds to the Bitcoin Script `[X] OP_TEMPLATEHASH
OP_SWAP OP_CHECKSIGFROMSTACK`. It has type 'B' and takes an argument X of type
'K'. It always has type properties 'u', 's', and 't'. Its type properties 'o',
'n', 'd', 'g', 'h', 'i', 'j' and 'k' are the same as that of its sub-fragment.
Same for its malleability properties 's' and 'f'. This is essentially `cms(X,m)`
with `m` fixed to the transaction's template hash such that it can have the 't'
property (and a neater, 'c:'-like, syntax).

Now regarding PSBTs, i think the only extension that really makes sense is to
make available information to verify the outputs of a transaction committed in
an output via `th()`. Since i expect `cms(X,m)` would be used with `m` set to
the hash of the actual message being signed, for obvious onchain efficiency and
privacy reasons, or simply because the message is larger than 520 bytes, i
considered a PSBT input field that would map arbitrary message hashes to their
preimage. But we already have such fields for SHA256/HASH256/RIPEMD160/HASH160
preimages, and i don't really see a reason why not use one of these hash
functions, so an extra field seems unnecessary. Similarly, rebindable signatures
can simply be provided through the `PSBT_IN_TAP_SCRIPT_SIG` mapping, since the
specs already assume that keys are not repeated within a Script anyways.

We introduce a new `PSBT_OUT_COMMITTED_TXS` field, which is a mapping from
template hash to Bitcoin-serialized transaction. The alternative, as Ademan
pointed out in private discussions, is to use a mapping for each field committed
to by the template hash (version, locktime, sequences, input index, annex,
outputs). This could be a small space saving in case the committed transaction
has many inputs, but for smaller transactions the repeated map keys would
actually be less efficient. It does have the advantage of not including
non-committed fields in the mapping, which could be a footgun in the simpler
version. Of course another alternative would be to keep a single mapping and
create a custom serialization of only the committed fields to use as value in
place of the regular Bitcoin serialization, but i don't think the complexity
would be worth it. I'm curious what people think about that.

The existing `PSBT_OUT_TAP_INTERNAL_KEY` is not keyed, and therefore may only be
used once per output. Since we may want verifiers to be able to inspect the
output(s) of transaction(s) committed in this output, we introduce a new
`PSBT_OUT_TAP_INTERNAL_KEYS` field. It is a mapping from Taproot output key to
Taproot internal key.

For the same reason, we introduce a `PSBT_OUT_TAP_TREES` field, which is a
mapping from Taproot output key to a list of tuples representing the depth,
version and Script for a leaf in a Taproot tree (same format as the value for
`PSBT_OUT_TAP_TREE`).

Other fields useful to verify the outputs of committed transactions, such as
`PSBT_OUT_TAP_BIP32_DERIVATION`, are already keyed and can just be reused
directly.

Do these extensions to PSBTs and descriptors make sense to support the
"Taproot-native (re-)bindable transaction bundle" proposal? Is there anything
you think should be included that i'm missing?

Best,
Antoine Poinsot

[^0]: https://gnusha.org/pi/bitcoindev/F5vsDVNGXP_hmCvp4kFnptFLBCXOoRxWk9d05kSInq_kXj0ePqVAJGADkBFJxYIGkjk8Pw1gzBonTivH6WUUb4f6mwNCmJIwdXBMrjjQ0lI=@protonmail.com/
[^1]: https://gnusha.org/pi/bitcoindev/26b96fb1-d916-474a...@googlegroups.com/
[^2]: https://github.com/bitcoin-inquisition/bitcoin/pull/108
[^3]: https://github.com/bitcoin-inquisition/bitcoin/pull/100
[^4]: https://github.com/bitcoin/bitcoin/blob/241ad5853bcac94b0fcbe5c67199e5a226da5218/src/script/miniscript.h#L1697
[^5]: https://github.com/rust-bitcoin/rust-miniscript/blob/411b651b7805c781839096832be2ea0e81ed3588/src/miniscript/analyzable.rs#L186-L187
[^6]: To my knowledge this has been discussed a number of times and the latest
iteration is https://github.com/bitcoin/bitcoin/issues/24114