Skip to content

Latest commit

 

History

History
249 lines (199 loc) · 17.4 KB

bip-template-key.mediawiki

File metadata and controls

249 lines (199 loc) · 17.4 KB
Raw

  BIP: TBD
  Layer: Consensus (soft fork)
  Title: Template Key
  Author: Brandon Black <freedom@reardencode.com>
  Status: Draft
  Type: Standards Track
  Created: 2023-09-07
  License: BSD-3-Clause
  Requires: 119, 340, 341, 342
  Replaces: 118

Table of Contents

Introduction

Abstract

This BIP describes a new set of hashing modes corresponding to a new type of public key for tapscript (BIP 342) transactions. It defines a virtual public key for use in tapscript, corresponding to the taproot internal key used with these new hashing modes.

Many of the hashing modes defined in this BIP do not commit to the previous outpoint being spent, enabling dynamic binding of the signed transaciton to different UTXOs providing the other hashed parts of the transaction match.

In addition to defining these new hashing modes for use in signature verification, this BIP also defines a set of corresponding hashing modes for use with hash equality verification as an extension to BIP 119. Some of the resulting hashing modes will not be useful due to hash cycles.

Copyright

This document is licensed under the 3-clause BSD license.

Motivation

The motivation for this BIP is inclusive of the motivation for BIP 118.

The specific design of these hashing modes has been influenced by conversations with James O'Beirne, Greg Sanders, @4moonsettler, Burak Keçeli, Super Testnet, and others. See this mailing list thread, and this post on Delving Bitcoin for some additional context.

To summarize some of the considerations that have gone into these hashing modes:

  • Because BIP 118 ANYPREVOUTANYSCRIPT(APOAS) does not commit to the previout outpoint or script, it can also be used to produce a template covenant by placing a signature in the locking script (APOAS|ALL is similar to BIP 119 DefaultCheckTemplateVerifyHash, but does not commit to sufficient data to produce predictable txids for subsequent transactions. See this table). This type of covenant is an unavoidable property of fully re-bindable signatures as required for LN Symmetry. By extending BIP 119 to include the hash modes introduced in this BIP, we deliberately support these covenants with far fewer witness bytes.
  • Much ado has been made about the recursive covenants enabled by BIP 118. The recursion enabled is limited to movement between pre-defined states, and only possible using a trusted setup ceremony with deleted keys. These constructions are therefore primarily of academic interest, and do not represent a way to alter the execution flow or incentive model of bitcoin.
  • Jeremy Rubin has written about the future need for a transaction-external fee payment mechanism for bitcoin transactions (fee accounts, transaction sponsors, etc.); any such proposal is many years away. In the meantime, partial transaction input/output hashing can allow for transaction-internal fees to be added within many proposed protocols.
  • A signature hash that allows rebinding of one or more transaction inputs while fixing one or more others can further enable off-chain protocols.
    • Allowing this in general would create quadratic hashing, so this BIP only allows the first transaction input to be rebindable with all others fixed; adding only linear hashing in the worst case.
    • This could also potentially reduced sufficiently by limiting the number of possible combinations, but this would be more difficult to reason about.
  • One of the limitations of BIP 118 is that it extends the existing BIP 341 and BIP 342 signature hashing, which requires the use of 65-byte signatures for all ANYPREVOUT modes. By introducing a new signature hash, this BIP allows the selection of a new default hashing mode specific to Tapscript 33-byte key version 1.
    • The default signature mode selected is analogous to BIP 119 DefaultCheckTemplateVerifyHash.

Specification[1]

This BIP modifies the behaviour of the BIP 342 signature opcodes[2] (CHECKSIG, CHECKSIGVERIFY, and CHECKSIGADD) for public keys that have a length of 33 bytes and a first byte of 0x01 or the public key which is precisely the single byte vector 0x01[3]. These keys are termed Template public keys.

Rules for signature opcodes

The BIP 342 rules for signature opcodes are modified by removing keys with the first byte 0x01 and length of either 1-byte or 33-bytes from the list of unknown public key types, and adding the following rule prior to the handling of unknown public key types:

  • If the public key is the single byte 0x01, or if the public key is 33 bytes and the first byte of the public key is 0x01, it is considered to be a template public key:
    • If the signature is not the empty vector, the signature is validated according to the BIP 341 signing validation rules with the public key, allowable hash_type values, and transaction digest modified as defined below.
Public key

To convert the 1-byte Template public key for use with BIP 340, use the 32-byte taproot internal key, p, as defined in BIP 341.

To convert a 33-byte Template public key for use with BIP 340, remove the 0x01 prefix and use the remaining 32 bytes.

Signature verification

To verify a signature sig for a template public key p:

  • If the sig is 64 bytes long, return Verify(p, hashTapSigHash(0x01[4] || TemplateMsg(0x00, true)), sig)
  • If the sig is 65 bytes long, return sig[64] ≠ 0x00 and Verify(p, hashTapSighash(0x01 || TemplateMsg(sig[64], true)), sig[0:64]).
  • Otherwise, fail.
Verify is as defined in BIP 340.

Rules for OP_CHECKTEMPLATEVERIFY

The validation of OP_CHECKTEMPLATEVERIFY is modified as follows:

  • If there is not at least one element on the stack, fail.
  • If the top element on the stack is not 32 or 33-bytes long, NOP.
  • If the top element on the stack is 32-bytes long:
    • If the DefaultCheckTemplateVerifyHash does not equal the top stack element, fail.
  • Else: (33-byte stack element)
    • Let check_item = stack_top()
    • Let check_hash = check_item[0:32]
    • Let hash_type = check_item[32]
    • If hash_type equals 0, fail.
    • Let template_hash = SHA256(TemplateMsg(hash_type, false))[5]
    • If template_hash does not equal check_hash, fail.

Template message

We define the function TemplateMsg(hash_type, for_sig) which computes the template message as a byte array.

The parameter hash_type is an 8-bit unsigned value.

If hash_type & 0x03 equals 0x01 and there is not an output corresponding to the input being validated, fail.

If hash_type & 0xfc does not equal 0x00, 0x04, 0x08, 0x0c, 0x40, 0x44, 0x48, 0x4c, 0x80, 0x84, or 0x88, fail.

The parameter for_sig is a boolean where true indicates that the template message will be used in signature validation.

If the parameters take acceptable values, TemplateMsg(hash_type, for_sig) is the contatenation of the following data, in order (with byte size of each item listed in parentheses). Numerical values in 2, 4, or 8-byte are encoded in little-endian.

  • Control:
    • hash_type (1)[6].
  • 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 or 0x88:
      • 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, 0x0c, or 0x88:
      • 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 or 2:
      • nOoutputs (4): the 32-bit little endian serializtion of the number of transaction outputs
    • If template_output_mode equals 0:
      • sha_outputs (32): the SHA256 of the serialization of all outputs in CTxOut format.
    • If template_output_mode equals 2:
      • sha_rest_outputs (32): the SHA256 of the serialization of all outputs other than the first in CTxOut format.
  • Data about this input:
    • If for_sig is true:
      • 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 0x4c:
      • prevout (36): the COutPoint of this input (32-byte hash + 4-byte little-endian).
    • If template_tx_mode equals 0x48 or 0x4c:
      • 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, 0x48, or 0x88:
      • controlblock_hash (32): the SHA256 of 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.

What is hashed?

While the above description of TemplateMsg is useful for implementors, it is difficult to understand from the text exactly what is hashed for each hash_type. Here we describe the hashed data in another more digestible format.

We define the following input related data elements:

  • may be included for any input
    • prevout:
    • prevscript: previout output amount and previous output script
    • sequence:
  • only from the input being validated
    • spendscript: control block[7], 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
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. If template_output_mode equals 2, all outputs except output 0 are included in the hash. Otherwise no output data is included.

If for_sig is true, the Taproot annex and spend type are hashed.

We define the following template_tx_mode hashing modes.

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

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

Modes 0x80 and 0x84 only work on input 0 for OP_CHECKTEMPLATEVERIFY which is a bit of an odd behavior, but enables a hash mode that constrains all other inputs’ 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.

Comparison to BIP341, BIP342, and BIP118 sighash modes

sighash mode value similar template mode
SIGHASH_DEFAULT 0x00 0x0c
SIGHASH_ALL 0x01 0x0c
SIGHASH_ALL|SIGHASH_SINGLE 0x03 0x0d
SIGHASH_ALL|SIGHASH_NONE 0x02 0x0e
SIGHASH_ANYONECANPAY 0x81 0x4c
SIGHASH_ANYONECANPAY|SIGHASH_SINGLE 0x83 0x4d
SIGHASH_ANYONECANPAY|SIGHASH_NONE 0x82 0x4e
SIGHASH_ANYPREVOUT 0x41 0x48
SIGHASH_ANYPREVOUT|SIGHASH_SINGLE 0x43 0x49
SIGHASH_ANYPREVOUT|SIGHASH_NONE 0x42 0x4a
SIGHASH_ANYPREVOUTANYSCRIPT 0xc1 0x44
SIGHASH_ANYPREVOUTANYSCRIPT|SIGHASH_SINGLE 0xc3 0x45
SIGHASH_ANYPREVOUTANYSCRIPT|SIGHASH_NONE 0xc2 0x46

Discussion

This BIP 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. ^ Some text copied from BIP 118.
  2. ^ What about key path spends? These new signature modes could also be supported on key path spends (by encumbering SegWit v1 33-byte keys), but this would make such outputs distinct in the output set from other SegWit v1 outputs. With the ability to use these modes with the taproot internal key, the total round-trip cost difference between key path and script is 7.75vB. Extending keypath can be done with a separate BIP.
  3. ^ Use of 0x01 public key type Because OP_0 leaves an empty vector on the stack it would not satisfy BIP 342's rules for unknown public key types. As such, it is convenient to use one of OP_1..OP_16 or OP_1NEGATE as a way to reference the taproot internal key. To keep things as simple as possible, we use the first of these, and add the same byte as a prefix to allow Template key signatures for explicitly specified keys.
  4. ^ Why is the hash prefixed with 0x01? To indicate that this is a distinct signature hashing epoch.
  5. ^ Why is this not a tagged hash? See BIP119's discussion of this topic. With 33-byte hashes, each hash type is identified by the hash_type committed to.
  6. ^ Use as DefaultCheckTemplateVerifyHash: There is no hash_type in the DefaultCheckTemplateVerifyHash, so if this specification is to be used to fully replace BIP 119's hash function, we can drop this byte if it's zero and for_sig is false; or we can modify BIP 119 to include a 0-byte.
  7. ^ Without the control block, a transaction with 2 identical script paths may be malleated after signing.