<pre>
  BIP: bip-tapscript
  Layer: Consensus (soft fork)
  Title: Validation of Taproot Scripts
  Author: Pieter Wuille <pieter.wuille@gmail.com>
  Comments-Summary: No comments yet.
  Comments-URI:
  Status: Draft
  Type: Standards Track
  Created:
  License: BSD-3-Clause
</pre>

==Introduction==

===Abstract===

This document specifies the semantics of the initial scripting system under bip-taproot.

===Copyright===

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

===Motivation===

Bip-taproot proposes improvements to just the script structure, but some of its goals are incompatible with the semantics of certain opcodes within the scripting language itself.
While it is possible to deal with these in separate optional improvements, their impact is not guaranteed unless they are addressed simultaneously with bip-taproot itself.

Specifically, the goal is making '''Schnorr signatures''', '''batch validation''', and '''signature hash''' improvements available to spends that use the script system as well.

==Design==

In order to achieve these goals, signature opcodes <code>OP_CHECKSIG</code> and <code>OP_CHECKSIGVERIFY</code> are modified to verify Schnorr signatures as specified in bip-schnorr and to use a new transaction digest based on the taproot transaction digest.
The tapscript transaction digest also simplifies <code>OP_CODESEPARATOR</code> handling and makes it more efficient.

The inefficient <code>OP_CHECKMULTISIG</code> and <code>OP_CHECKMULTISIGVERIFY</code> opcodes are disabled.
Instead, a new opcode <code>OP_CHECKSIGADD</code> is introduced to allow creating the same multisignature policies in a batch-verifiable way.
Tapscript uses a new, simpler signature opcode limit fixing complicated interactions with transaction weight.
Furthermore, a potential malleability vector is eliminated by requiring MINIMALIF.

Tapscript can be upgraded through soft forks by defining unknown key types, for example to add new <code>hash_types</code> or signature algorithms.
Additionally, the new tapscript <code>OP_SUCCESS</code> opcodes allow introducing new opcodes more cleanly than through <code>OP_NOP</code>.

==Specification==

The rules below only apply when validating a transaction input for which all of the conditions below are true:
* The transaction output is a '''segregated witness spend''' (i.e., either the scriptPubKey or BIP16 redeemScript is a witness program as defined in BIP141).
* It is a '''taproot spend''' as defined in bip-taproot (i.e., the witness version is 1, the witness program is 32 bytes).
* It is a '''script path spend''' as defined in bip-taproot (i.e., after removing the optional annex from the witness stack, two or more stack elements remain).
* The leaf version is ''0xc0'' (i.e. the first byte of the last witness element after removing the optional annex is ''0xc0'')<ref>'''How is the ''0xc0'' constant chosen?''' Following the guidelines in bip-taproot, by choosing a value having the two top bits set, tapscript spends are identifiable even without access to the UTXO being spent.</ref>, marking it as a '''tapscript spend'''.

Validation of such inputs must be equivalent to performing the following steps in the specified order.
# If the input is invalid due to BIP16, BIP141, or bip-taproot, fail.
# The script as defined in bip-taproot (i.e., the penultimate witness stack element after removing the optional annex) is called the '''tapscript''' and is decoded into opcodes, one by one:
## If any opcode numbered ''80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254'' is encountered, validation succeeds (none of the rules below apply). This is true even if later bytes in the tapscript would fail to decode otherwise. These opcodes are renamed to <code>OP_SUCCESS80</code>, ..., <code>OP_SUCCESS254</code>, and collectively known as <code>OP_SUCCESSx</code><ref>'''<code>OP_SUCCESSx</code>''' <code>OP_SUCCESSx</code> is a mechanism to upgrade the Script system. Using an <code>OP_SUCCESSx</code> before its meaning is defined by a softfork is insecure and leads to fund loss. The inclusion of <code>OP_SUCCESSx</code> in a script will pass it unconditionally. It precedes any script execution rules to avoid the difficulties in specifying various edge cases, for example: <code>OP_SUCCESSx</code> being the 202nd opcode, <code>OP_SUCCESSx</code> after too many signature opcodes, or even scripts with conditionals lacking <code>OP_ENDIF</code>. The mere existence of an <code>OP_SUCCESSx</code> anywhere in the script will guarantee a pass for all such cases. <code>OP_SUCCESSx</code> are similar to the <code>OP_RETURN</code> in very early bitcoin versions (v0.1 up to and including v0.3.5). The original <code>OP_RETURN</code> terminates script execution immediately, and return pass or fail based on the top stack element at the moment of termination. This was one of a major design flaws in the original bitcoin protocol as it permitted unconditional third party theft by placing an <code>OP_RETURN</code> in <code>scriptSig</code>. This is not a concern in the present proposal since it is not possible for a third party to inject an <code>OP_SUCCESSx</code> to the validation process, as the <code>OP_SUCCESSx</code> is part of the script (and thus committed to be the taproot output), implying the consent of the coin owner. <code>OP_SUCCESSx</code> can be used for a variety of upgrade possibilities:
* An <code>OP_SUCCESSx</code> could be turned into a functional opcode through a softfork. Unlike <code>OP_NOPx</code>-derived opcodes which only have read-only access to the stack, <code>OP_SUCCESSx</code> may also write to the stack. Any rule changes to an <code>OP_SUCCESSx</code>-containing script may only turn a valid script into an invalid one, and this is always achievable with softforks.
* Since <code>OP_SUCCESSx</code> precedes size check of initial stack and push opcodes, an <code>OP_SUCCESSx</code>-derived opcode requiring stack elements bigger than 520 bytes may uplift the limit in a softfork.
* <code>OP_SUCCESSx</code> may also redefine the behavior of existing opcodes so they could work together with the new opcode. For example, if an <code>OP_SUCCESSx</code>-derived opcode works with 64-bit integers, it may also allow the existing arithmetic opcodes in the ''same script'' to do the same.
* Given that <code>OP_SUCCESSx</code> even causes potentially unparseable scripts to pass, it can be used to introduce multi-byte opcodes, or even a completely new scripting language when prefixed with a specific <code>OP_SUCCESSx</code> opcode.</ref>.
## If any push opcode fails to decode because it would extend past the end of the tapscript, fail.
# If the size of any element in the '''initial stack''' as defined in bip-taproot (i.e., the witness stack after removing both the optional annex and the two last stack elements after that) is bigger than 520 bytes, fail.
# If the tapscript is bigger than 10000 bytes, fail.
# The tapscript is executed according to the rules in the following section, with the initial stack as input.
## If execution fails for any reason (including the 201 non-push opcode limit), fail.
## If the execution results in anything but exactly one element on the stack which evaluates to true with <code>CastToBool()</code>, fail.
# If this step is reached without encountering a failure, validation succeeds.

===Script execution===

The execution rules for tapscript are based on those for P2WSH according to BIP141, including the <code>OP_CHECKLOCKTIMEVERIFY</code> and <code>OP_CHECKSEQUENCEVERIFY</code> opcodes defined in BIP65 and BIP112, but with the following modifications:
* '''Disabled script opcodes''' The following script opcodes are disabled in tapscript: <code>OP_CHECKMULTISIG</code> and <code>OP_CHECKMULTISIGVERIFY</code>. The disabled opcodes behave in the same way as <code>OP_RETURN</code>, by failing and terminating the script immediately when executed, and being ignored when found in unexecuted branch. While being ignored, they are still counted towards the 201 non-push opcodes limit.
* '''Consensus-enforced MINIMALIF''' The MINIMALIF rules, which are only a standardness rule in P2WSH, are consensus enforced in tapscript. This means that the input argument to the <code>OP_IF</code> and <code>OP_NOTIF</code> opcodes must be either exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1)<ref>'''Why make MINIMALIF consensus?''' This makes it considerably easier to write non-malleable scripts that take branch information from the stack.</ref>.
* '''OP_SUCCESSx opcodes''' As listed above, some opcodes are renamed to <code>OP_SUCCESSx</code>, and make the script unconditionally valid.
* '''Signature opcodes'''. The <code>OP_CHECKSIG</code> and <code>OP_CHECKSIGVERIFY</code> are modified to operate on Schnorr public keys and signatures (see bip-schnorr) instead of ECDSA, and a new opcode <code>OP_CHECKSIGADD</code> is added.
** The opcode 186 (<code>0xba</code>) is named as <code>OP_CHECKSIGADD</code>. <ref>'''<code>OP_CHECKSIGADD</code>''' This opcode is added to compensate for the loss of <code>OP_CHECKMULTISIG</code>-like opcodes, which are incompatible with batch verification. <code>OP_CHECKSIGADD</code> is functionally equivalent to <code>OP_ROT OP_SWAP OP_CHECKSIG OP_ADD</code>, but is only counted as one opcode towards the 201 non-push opcodes limit. All <code>CScriptNum</code>-related behaviours of <code>OP_ADD</code> are also applicable to <code>OP_CHECKSIGADD</code>.</ref><ref>'''Comparison of <code>CHECKMULTISIG</code> and <code>CHECKSIG</code>''' A <code>CHECKMULTISIG</code> script <code>m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG</code> with witness <code>0 <signature_1> ... <signature_m></code> can be rewritten as script <code><pubkey_1> CHECKSIG ... <pubkey_n> CHECKSIGADD m NUMEQUAL</code> with witness <code><w_1> ... <w_n></code>. Every witness element <code>w_i</code> is either a signature corresponding to the public key with the same index or an empty vector. A similar <code>CHECKMULTISIGVERIFY</code> script can be translated to bip-tapscript by replacing <code>NUMEQUAL</code> with <code>NUMEQUALVERIFY</code>. Alternatively, an m-of-n multisig policy can be implemented by splitting the script into several leaves of the Merkle tree, each implementing an m-of-m policy using <code><pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG</code>. If the setting allows the participants to interactively collaborate while signing, multisig policies can be realized with [https://eprint.iacr.org/2018/068 MuSig] for m-of-m and with [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps threshold signatures] using verifiable secret sharing for m-of-n.</ref>

===Rules for signature opcodes===

The following rules apply to <code>OP_CHECKSIG</code>, <code>OP_CHECKSIGVERIFY</code>, and <code>OP_CHECKSIGADD</code>.

* For <code>OP_CHECKSIGVERIFY</code> and <code>OP_CHECKSIG</code>, the public key (top element) and a signature (second to top element) are popped from the stack.
** If fewer than 2 elements are on the stack, the script MUST fail and terminate immediately.
* For <code>OP_CHECKSIGADD</code>, the public key (top element), a <code>CScriptNum</code> <code>n</code> (second to top element), and a signature (third to top element) are popped from the stack.
** If fewer than 3 elements are on the stack, the script MUST fail and terminate immediately.
** If <code>n</code> is larger than 4 bytes, the script MUST fail and terminate immediately.
* If the public key size is zero, the script MUST fail and terminate immediately.
* If the public key size is 32 bytes, it is considered to be a public key as described in bip-schnorr:
** If the signature is not the empty vector, the signature is validated according to the bip-taproot signing validation rules against the public key and the tapscript transaction digest (to be defined hereinafter) as message. Validation failure MUST cause the script to fail and terminate immediately.
* If the public key size is not zero and not 32 bytes, the public key is of an ''unknown public key type''<ref>'''Unknown public key types''' allow adding new signature validation rules through softforks. A softfork could add actual signature validation which either passes or makes the script fail and terminate immediately. This way, new <code>SIGHASH</code> modes can be added, as well as [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-December/016549.html NOINPUT-tagged public keys] and a public key constant which is replaced by the taproot internal key for signature validation.</ref> and no actual signature verification is applied. During script execution of signature opcodes they behave exactly as known public key types except that signature validation is considered to be successful.
* If the script did not fail and terminate before this step, regardless of the public key type:
** If the signature is the empty vector:
*** For <code>OP_CHECKSIGVERIFY</code>, the script MUST fail and terminate immediately.
*** For <code>OP_CHECKSIG</code>, an empty vector is pushed onto the stack, and execution continues with the next opcode.
*** For <code>OP_CHECKSIGADD</code>, a <code>CScriptNum</code> with value <code>n</code> is pushed onto the stack, and execution continues with the next opcode.
** If the signature is not the empty vector, the <code>sigops_passed</code> counter is incremented (see further)
*** For <code>OP_CHECKSIGVERIFY</code>, execution continues without any further changes to the stack.
*** For <code>OP_CHECKSIG</code>, a 1-byte value <code>0x01</code> is pushed onto the stack.
*** For <code>OP_CHECKSIGADD</code>, a <code>CScriptNum</code> with value of <code>n + 1</code> is pushed onto the stack.

These opcodes count toward the 201 non-push opcodes limit.

===Transaction digest===

As the message for signature opcodes signature verification, transaction digest has the same definition as in bip-taproot, except the following:

The one-byte <code>spend_type</code> has a different value, specificially at bit-2:
* Bit-0 is set if the <code>scriptPubKey</code> being spent is P2SH (opposed to "native segwit").
* Bit-1 is set if an annex is present (the original witness stack has at least two witness elements, and the first byte of the last element is <code>0x50</code>).
* Bit-2 is set.
* The other bits are unset.

As additional pieces of data, added at the end of the input to the ''hash<sub>TapSighash</sub>'' function:
* <code>tapleaf_hash</code> (32): the tapleaf hash as defined in bip-taproot
* <code>key_version</code> (1): a constant value <code>0x00</code> representing the current version of public keys in the tapscript signature opcode execution.
* <code>codeseparator_position</code> (2): the opcode position of the last executed <code>OP_CODESEPARATOR</code> before the currently executed signature opcode, with the value in little endian (or <code>0xffff</code> if none executed). The first opcode in a script has a position of 0. A multi-byte push opcode is counted as one opcode, regardless of the size of data being pushed.

The total number of bytes hashed is at most ''244''<ref>'''What is the number of bytes hashed for the signature hash?''' The total size of the input to ''hash<sub>TapSighash</sub>'' (excluding the initial 64-byte hash tag) can be computed using the following formula: ''211 - is_anyonecanpay * 50 - is_none * 32 - is_p2sh_spending * 11 + has_annex * 32''.</ref>.

In summary, the semantics of the BIP143 sighash types remain unchanged, except the following:
# The exceptions mentioned in bip-taproot.
# The digest commits to taproot-specific data <code>key_version</code>.<ref>'''Why does the transaction digest commit to the <code>key_version</code>?''' This is for future extensions that define unknown public key types, making sure signatures can't be moved from one key type to another.</ref>
# The digest commits to the executed script through the <code>tapleaf_hash</code> which includes the leaf version and script instead of <code>scriptCode</code>. This implies that this commitment is unaffected by <code>OP_CODESEPARATOR</code>.
# The digest commits to the opcode position of the last executed <code>OP_CODESEPARATOR</code>.<ref>'''Why does the transaction digest commit to the position of the last executed <code>OP_CODESEPARATOR</code>?''' This allows continuing to use <code>OP_CODESEPARATOR</code> to sign the executed path of the script. Because the <code>codeseparator_position</code> is the last input to the digest, the SHA256 midstate can be efficiently cached for multiple <code>OP_CODESEPARATOR</code>s in a single script. In contrast, the BIP143 handling of <code>OP_CODESEPARATOR</code> is to commit to the executed script only from the last executed <code>OP_CODESEPARATOR</code> onwards which requires unnecessary rehashing of the script. It should be noted that the one known <code>OP_CODESEPARATOR</code> use case of saving a second public key push in a script by sharing the first one between two code branches can be most likely expressed even cheaper by moving each branch into a separate taproot leaf.</ref>

===Signature opcodes limitation===

In addition to the 201 non-push opcodes limit, the use of signature opcodes is subject to further limitations.

* <code>input_witness_weight</code> is defined as the size of the serialized input witness associated to a particular transaction input. As defined in BIP141, a serialized input witness includes <code>CCompactSize</code> tags indicating the number of elements and size of each element, and contents of each element. <code>input_witness_weight</code> is the total size of the said <code>CCompactSize</code> tags and element contents.
* <code>sigops_passed</code> is defined as the total number of successfully executed signature opcodes, which have non-zero signature size and do not fail and terminate the script. For the avoidance of doubt, passing signature opcodes with unknown type public key and non-zero size signature are also counted towards <code>sigops_passed</code>.
* If <code>50 * (sigops_passed - 1)</code> is greater than <code>input_witness_weight</code>, the script MUST fail and terminate immediately.

This rule limits worst-case validation costs in tapscript similar to the ''sigops limit'' that only applies to legacy and P2WSH scripts<ref>'''The tapscript sigop limit''' The signature opcode limit protects against scripts which are slow to verify due to excessively many signature operations. In tapscript the number of signature opcodes does not count towards the BIP141 or legacy sigop limit. The old sigop limit makes transaction selection in block construction unnecessarily difficult because it is a second constraint in addition to weight. Instead, the number of tapscript signature opcodes is limited by witness weight. Additionally, the limit applies to the transaction input instead of the block and only actually executed signature opcodes are counted. Tapscript execution allows one signature opcode per 50 witness weight units plus one free signature opcode. The tapscript signature opcode limit allows to add new signature opcodes like <code>CHECKSIGFROMSTACK</code> to count towards the limit through a soft fork. Even if in the future new opcodes are introduced which change normal script cost there is need to stuff the witness with meaningless data. In that case the taproot annex can be used to add weight to the witness without increasing the actual witness size.</ref>
<ref>'''Parameter choice of the sigop limit''' Regular witnesses are unaffected by the limit as their weight is composed of public key and (<code>SIGHASH_ALL</code>) signature pairs with ''33 + 65'' weight units each (which includes a 1 weight unit <code>CCompactSize</code> tag). This is also the case if public keys are reused in the script because a signature's weight alone is 65 or 66 weight units. However, the limit increases the fees of abnormal scripts with duplicate signatures (and public keys) by requiring additional weight. The weight per sigop factor 50 corresponds to the ratio of BIP141 block limits: 4 mega weight units divided by 80,000 sigops. The "free" signature opcode permitted by the limit exists to account for the weight of the non-witness parts of the transaction input.</ref>.

==Rationale==

<references />

==Examples==

==Acknowledgements==

This document is the result of many discussions and contains contributions by Jonas Nick, Anthony Towns, and others.