Skip to content

Instantly share code, notes, and snippets.

@reardencode
Last active November 2, 2023 18:25
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save reardencode/2aa98700b720174598d21989dd46e781 to your computer and use it in GitHub Desktop.
Combined CTV+APO to minimal TXHASH+CSFS

Abstract

This proposal is an alternative to bip119 and bip118, providing the functionality of both proposals with minimal additional overhead in many cases, while clearing certain objections to both, and opening clear upgrade paths.

This is, in essence, an initially constrained version of Russel O'Connor's OP_TXHASH+OP_CSFS proposal.

We define three new Tapscript-only opcodes. Replacing OP_SUCCESS80, OP_SUCCESS187, and OP_SUCCESS188 with OP_TXHASH, OP_CHECKSIGFROMSTACK, and OP_CHECKSIGFROMSTACKVERIFY respectively.

Summary

For OP_TXHASH, we define exactly 5 methods of hashing the transaction depending on a minimally encoded numeric argument popped from the stack:

argument behavior
0 as in bip119
1 as in bip118 with sighash flag 0x41
2 as in bip118 with sighash flag 0xc1
3 as in bip118 with sighash flag 0x43
4 as in bip118 with sighash flag 0xc3

OP_CHECKSIGFROMSTACK(VERIFY) is defined similarly to the implementation in the Elements project, but does not internally SHA256 hash the data argument. As bip340 defines signatures on arbitrary length messages, and these OP_CHECKSIGFROMSTACK(VERIFY) are defined only in Tapscript, the internal hashing is unnecessarily restrictive. Users may wish to use pre-hashed values as in this proposal, or non-SHA256 hashes available in script. OP_CHECKSIGFROMSTACK(VERIFY) also inherit the ability to check signatures against the taproot internal key from bip118 (using OP_0 instead of OP_1 as the reasons for using 1 do not apply in this context).

Motivation

Much ink has been spilled on the discussion of what is next for bitcoin scipt development. The two proposals nearest to consensus are bip118 and bip119, but the proponents of each disagree about the relative priority and the merits of the other. Here, we'll briefly outline some of the objections to each and demonstrate how this proposal reduces those objections. We will not discuss the concerns about the introduction of covenants or recursive covenants generally.

CTV Objections

  • Not general enough
  • Inefficient when otherwise validating the hash (e.g. when combined with OP_CHECKSIGFROMSTACK)
  • Uses OP_NOPx extension semantics even though OP_SUCCESSx is available

APO Objections

  • Not general enough
  • Accidentally enables inefficient, hard to use covenants
  • Uses new Tapscript key version to avoid accidents

Solutions

  • By providing the behavior of both bip118 and bip119, this proposal is more general than either of those proposals. It also provides explicit upgrade hooks for further generality (e.g. to full OP_TXHASH).
  • By splitting the hashing from the validation of bip119, the hash can be used in ways other than OP_EQUALVERIFY.
  • We use OP_SUCCESSx upgrade semantics.
  • We explicitly enable some of the sighash-based covenants accidentally enabled by bip118.
  • By using new signature checking opcodes, we do not require the safety of a new Tapscript key version.

Specification

OP_TXHASH

When validating Tapscript, the behavior of OP_SUCCESS80 is modified as follows:

  • If there is not at least one item on the stack, fail1.
  • If the top item on the stack is not a minimally encoded OP_0, OP_1, OP_2, OP_3, or OP_4; succeed immediately2.
  • Pop the top item from the stack, and name it hash_mode
  • If hash_mode is 0:
    • Hash the transaction as defined in bip119
    • Push the resulting hash to the stack
  • If hash_mode is 1:
    • Hash the transaction as defined in bip118 using sighash_type=0x41
    • Push the resulting hash to the stack
  • If hash_mode is 2:
    • Hash the transaction as defined in bip118 using sighash_type=0xc1
    • Push the resulting hash to the stack
  • If hash_mode is 3:
    • Hash the transaction as defined in bip118 using sighash_type=0x43
    • Push the resulting hash to the stack
  • If hash_mode is 4:
    • Hash the transaction as defined in bip118 using sighash_type=0xc3
    • Push the resulting hash to the stack

OP_CHECKSIGFROMSTACK(VERIFY)

When validating Tapscript, the behavior of OP_SUCCESS187 and OP_SUCCESS188 are modified as follows:

  • If there are not at least 3 items on the stack, fail1.
  • If the top-minus-0 stack item is exactly equal to OP_0
    • Pop the top item from the stack
    • Push the taproot internal key to the stack
  • If the top-minus-0 stack item's length is not 32, succeed immediately2.
  • If the top-minus-2 stack item's length is not 64, fail3.
  • Pop the top 3 stack items as pubkey, msg, and sig respectively.
  • Let result equal the result of verifying sig against msg and pubkey according to bip340.
  • Push true if result otherwise false to the stack.
  • If validating OP_CHECKSIGFROMSTACKVERIFY
    • Pop the top item from the stack as check.
    • If check is not true, fail.

Discussion

How does the efficiency compare to bip118?

SIGHASH_ANYPREVOUT:

<64-byte signature>||<1-byte sighash type> <33-byte pubkey> OP_CHECKSIG(VERIFY)
with pushes: 64+1+1 + 33+1 + 1 = 101 witness bytes (25.25vBytes)

This proposal:

<64-byte signature> <1-byte argument> OP_TXHASH <32-byte pubkey> OP_CHECKSIGFROMSTACK(VERIFY)
with pushes: 64+1 + 1 + 1 + 32+1 + 1 = 101 witness bytes (25.25vBytes)

How does the efficiency compare to bip119?

Both in Tapscript

OP_CHECKTEMPLATEVERIFY alone4:

<32-byte hash> OP_CHECKTEMPLATEVERIFY
with pushes: 32+1 + 1 = 34 witness bytes (8.5vBytes)

OP_CHECKTEMPLATEVERIFY with a subsequent check:

<32-byte hash> OP_CHECKTEMPLATEVERIFY OP_DROP <...>
with pushes: 32+1 + 1 + 1 = 35 witness bytes (8.75vBytes)

This proposal:

<1-byte argument> OP_TXHASH <32-byte hash> OP_EQUAL(VERIFY)
with pushes: 1 + 1 + 32+1 + 1 = 36 witness bytes (9 vBytes)

Compared to non-Tapscript CTV

Bare OP_CHECKTEMPLATEVERIFY4:

Lock: <32-byte hash> OP_CHECKTEMPLATEVERIFY
with pushes: 32+1 + 1 = 34 bytes (34vBytes)

Unlock: <empty>

Total: 34 + 0 = 34vBytes

Witness v0 CTV:

Lock: OP_0 <32-byte hash>
with pushes: 1 + 32+1 = 34 bytes (34 vBytes)

Unlock:
<34-byte witness script>
with sizes: 34+1 = 35 witness bytes (8.75vBytes)

Total: 34 + 8.75 = 42.75vBytes

This proposal:

Lock: OP_1 <32-byte pubkey>
with pushes: 1 + 32+1 = 34 bytes (34 vBytes)

Unlock:
<36-byte leaf script> <33-byte control block>
with sizes: 36+1 + 33+1 = 71 witness bytes (17.75vBytes)

Total: 34 + 17.75 = 51.75vBytes

Compared to bare CTV, this proposal is 17.75vBytes more costly. If CTV use cases gain popularity, a separate upgrade for bare CTV may be warranted, either as specified in bip119, as its own witness version, or some alternative.

Bearing in mind the risks mentioned in bip119, fee sensitive users can add OP_RIPEMD160 to save 2.75 vBytes when using OP_TXHASH with OP_EQUAL(VERIFY). This brings the excess cost relative to bare CTV down to 15vBytes.

Why not include modes for bip118 sighash_types 0x42 and 0xc2?5

Possibly due to a lack of imagination, we are unable to see a use for signing none of the inputs and none of the outputs (or a single input script and none of the outputs).

Can this be used in ln-symmetry?

Yes, this is fully compatible with ln-symmetry. It uses a different script, but has the same size and behavior as bip118 for this purpose.

Can this be used in PTLCs?

Yes, this is fully compatible with PTLCs. It uses a different script, but has the same size and behavior as bip118 for this purpose.

Can this be used with OP_VAULT?

Yes, this is fully compatible with OP_VAULT. It uses a different script, but has the same size and behavior as bip119 for this purpose.

Can selection of OP_TXHASH mode be deferred to spend time?

Yes. The argument to OP_TXHASH is taken from the stack, so it can be specified by the spender, however the script would need to do a range check to prevent OP_TXHASH being turned into OP_SUCCESS. This would only be advisable with a signature check to authorize the spend.

OP_0 OP_5 OP_WITHIN OP_VERIFY OP_TXHASH <pubkey> OP_CHECKSIGFROMSTACK

It is also possible to construct a script which allows spending with OP_TXHASH OP_CHECKSIGFROMSTACK or OP_CHECKSIG with the same pubkey depending on the spend stack.

<pubkey> OP_TOALTSTACK OP_SIZE OP_1SUB OP_IF OP_FROMALTSTACK OP_CHECKSIG OP_ELSE OP_0 OP_5 OP_WITHIN OP_VERIFY OP_TXHASH OP_FROMALTSTACK OP_CHECKSIGFROMSTACK OP_ENDIF

What is hashed?

field \ mode CTV(0) APO/ALL(1) APOAS/ALL(2) APO/SINGLE(3) APOAS/SINGLE(4) ARK6
hash type x x x x x
version/locktime x x x x x x
this input UTXO
other input UTXOs x
this script pubkey/amount x x x
other script pubkeys/amounts x
this script sig x x
other script sig x x
the number of inputs x x
this input sequence x x x x x x
other input sequences x x
spend type/annex x x x x x
leaf script x x x
key version/codesep pos x x x x x
tap merkle path7 x
corresponding output script/amount x x x x x x
other output scripts/amounts x x x x
the number of outputs x x

WIP what should be hashed?

If this proposal gains traction, we'll implement it similarly to bip119, updated to be more in line with bip341/bip342 hashing. This gives us an opportunity to consider additional fields for hashing. Specifically:

  • all modes will get an updated hash type specific to this application
  • modes 0, 1, and 3 include the tap merkle path
  • modes 1 and 2 include the number of outputs
  • modes 1, 2, 3, and 4 drop the (now meaningless) key version
  • mode 0 includes the spend type, annex, and codesep pos
field \ mode 0 1 2 3 4
hash type x x x x x
version/locktime x x x x x
this input UTXO
other input UTXOs
this script pubkey/amount x x
other script pubkeys/amounts
this script sig x
other script sig x
the number of inputs x
this input sequence x x x x x
other input sequences x
spend type/annex x x x x x
leaf script x x
codesep pos x x x x x
tap merkle path7 x x x
corresponding output script/amount x x x x x
other output scripts/amounts x x x
the number of outputs x x x

Notes

Footnotes

  1. We fail on invalid stack lengths to ensure that attackers cannot skip validation. 2

  2. We succeed on unspecified txhash modes or pubkey lengths to allow future extensions. 2

  3. We fail on invalid signature lengths after the pubkey length check, thus allowing only 64-byte signatures for 32-byte keys, but allowing future key types to potentially also have different signature lengths.

  4. OP_CHECKTEMPLATEVERIFY leaves the checked hash on the stack, which evaluates to true via bitcoin's CastToBool function, so this satisfies both legacy and segwit script success criteria without any additional ops (e.g. OP_DROP OP_TRUE). 2

  5. As far as we know there is no use for sighash types other than those defined in bip118 with this proposal, as the other types either reduce to OP_CHECKSIG(VERIFY) or create infinite hash loops.

  6. Ark could benefit from a hash that includes other UTXOs but not this UTXO. This would introduce uncacheable per-input hashing.

  7. Some or all of these probably should: https://github.com/bitcoin-inquisition/bitcoin/issues/19 2

Table of Contents

Motivation

Since posting my minimal TXHASH+CSFS proposal, I've had the pleasure to continue learning about a variety of trade-offs and use cases for bitcoin scripts including both signed and and unsigned hash checks. Here are some things that I've learned in that process:

  • The requirements for a transaction hash are different when committed to in the locking script vs by a signature in the unlock script.
  • For transaction hash covenants, recursion is only possible through deleted key signatures.
    • If the hash commits to an output, there is a hash-loop unless the hash is committed to in the unlock by a deleted key signature.
    • If the hash does not commit to any outputs then it cannot constrain the next spend, no recursion.
  • Single-output, single-input script covenants can be useful to enable fees to be added to covenant constructions
    • Bitcoin does not have transaction sponsors, ephemeral anchors, or fee accounts
  • All-but-one input covenants can be useful when a third party will be broadcasting a transaction paying a specific amount and script, but may change the tx hash.
    • This type of hash can easily lead to quadratic hashing behavior and the resulting DoS vector
  • BIP118 introduces a new Tapscript key type which can be signed for with any of the existing sighash_types, in addition to the added types.
    • I propose that an entirely new signature hash digest is more appropriate for a new key version.

Abstract

There are two parts to this proposal:

1. Define an extension to BIP119 to include several hashing modes beyond DefaultCheckTemplateVerifyHash. 2. Define Tapscript key version 2 for use with template signatures, and having default hash modes identical to the extended OP_CHECKTEPLATEVERIFY hashing modes defined above, except that these hashes include a committment to the Taproot annex and spend type.

Specification

We define the following input related data elements:

  • may be included for any input
    • prevout:
    • prevscript: output amount and script
    • sequence:
  • only from the input being validated
    • script: control block[1], leaf script, and code separator position
    • annex: taproot spend type and annex
    • index: the input index, with the first input having index 0
  • only for all inputs if present:
    • scriptsigs: hash of all scriptSigs if any scriptSig is non-empty
We define template_mode to be the last byte of a 33-byte input to OP_CHECKTEMPLATEVERIFY, or a 65-byte signature for Tapscript key version 2. If 32-byte has or 64-byte signature are used, template_mode is set to 0.

We define template_output_mode = template_mode & 0x03. If template_output_mode equals 0, nOutputs and sha_outputs are included in the hash. If template_output_mode equals 1, the corresponding output's sha_single_output is included. Otherwise no output data is included.

We define template_tx_mode = template_mode & 0xfc.

We define the following template_tx_mode hashing modes. If the hash is being generated during signature verification, then the Taproot annex and spend type are also hashed.

template_tx_mode included data
0x00 nInputs, index, locktime, scriptsigs, and all sequences (with template_output_mode = 0, identical to BIP119)
0x04 0x00 without locktime, scriptsigs, and all sequences.
0x08 0x00 with all prevscripts and script
0x0c 0x08 with all prevouts
0x40 -
0x44 locktime and this sequence (similar to BIP118 0xc?)
0x48 0x44 with this prevscript and script (similar to BIP118 0x4?)
0x80 0x00 with all but input 0's prevscript
0x84 0x80 with all but input 0's prevout

Modes 0x08, 0x0c, and 0x48 do not work with OP_CHECKTEMPLATEVERIFY, as they would create a hash cycle.

Modes 0x80 and 0x84 only work on input 0 which is a bit of an odd behavior, but enables a hash mode that constrains all other inputs’ prevouts without incurring quadratic hashing. Because such a mode could only ever be used on one input to a transaction, constraining it to input 0 seems a reasonable solution.

Template Hash

Hash the parts of the transaction as follows:

  • Control:
    • If template_mode is not equal to 0x00:
      • OP_CHECKTEMPLATEVERIFY || template_mode (2).
  • Transaction data:
    • nVersion (4): the nVersion of the transaction.
    • If template_tx_mode is not equal to 0x04 or 0x40:
      • nLockTime (4): the nLockTime of the transaction.
    • If template_tx_mode & 0x40 equals 0 and template_tx_mode is not equal to 0x04:
      • sha_scriptsigs (32): the SHA256 of the serialization of all input scriptSigs.
    • If template_tx_mode & 0x40 equals 0:
      • nInputs (4): the 32-bit little endian serialization of the number of transaction inputs.
    • If template_tx_mode is equal to 0x0c:
      • sha_prevouts (32): the SHA256 of the serialization of all input outpoints.
    • If template_tx_mode is equal to 0x84:
      • sha_rest_prevouts (32): the SHA256 of the serialization of all input outpoints other than the first.
    • If template_tx_mode is equal to 0x08 or 0x0c
      • sha_amounts (32): the SHA256 of the serialization of all input amounts.
      • sha_scriptpubkeys (32): the SHA256 of all spent outputs' scriptPubKeys, serialized as script inside CTxOut.
    • If template_tx_mode is equal to 0x80 or 0x84
      • sha_rest_amounts (32): the SHA256 of the serialization of all input amounts other than the first.
      • sha_rest_scriptpubkeys (32): the SHA256 of all spent outputs' scriptPubKeys other than the first, serialized as script inside CTxOut.
    • If template_tx_mode & 0x40 equals 0 and template_tx_mode is not equal to 0x04:
      • sha_sequences (32): the SHA256 of the serialization of all input nSequence.
    • If template_output_mode equals 0:
      • nOoutputs (4): the 32-bit little endian serializtion of the number of transaction outputs
      • sha_outputs (32): the SHA256 of the serialization of all outputs in CTxOut format.
  • Data about this input:
    • If currently executing op is not OP_CHECKTEMPLATEVERIFY:
      • spend_type (1): equal to (ext_flag * 2) + annex_present, where annex_present is 0 if no annex is present, or 1 otherwise (the original witness stack has two or more witness elements, and the first byte of the last element is 0x50)
      • If an annex is present (the lowest bit of spend_type is set):
        • sha_annex (32): the SHA256 of (compact_size(size of annex) || annex), where annex includes the mandatory 0x50 prefix.
    • If template_tx_mode & 0x04 is equal to 0
      • input_index (4): index of this input in the transaction input vector. Index of the first input is 0.
    • If template_tx_mode equals 0x48:
      • amount (8): value of the previous output spent by this input.
      • scriptPubKey (35): scriptPubKey of the previous output spent by this input, serialized as script inside CTxOut. Its size is always 35 bytes.
    • If template_tx_mode equals 0x08, 0x0c, or 0x48:
      • controlblock (33-4129): the BIP341 control block of the input being validated.
      • tapleaf_hash (32): the tapleaf hash as defined in BIP341
      • codesep_pos (4): the opcode position of the last executed OP_CODESEPARATOR before the currently executed opcode, as defined in BIP342.
    • If template_tx_mode is equal to 0x44 or 0x48:
      • nSequence (4): nSequence of this input.
  • Data about this output:
    • If template_output_mode equals 0x01:
      • sha_single_output (32): the SHA256 of the corresponding output in CTxOut format.

Execution of Tapscript sigops for 33-byte keys starting with 0x02

TODO

Execution of OP_CHECKTEMPLATEVERIFY for 33-byte hashes

TODO

Discussion

Thanks to all of the feedback I received on my earlier proposal, this update aims to provide a set of hashing modes with broad applicability to current and future proposals, including OP_VAULT, LN-Symmetry, Ark, Lightning PTLCs, &c.

  1. ^ Without the control block, a transaction with 2 identical script paths may be malleated after signing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment