Validation of Taproot Scripts

  BIP: 342
  Layer: Consensus (soft fork)
  Title: Validation of Taproot Scripts
  Authors: Pieter Wuille 
           Jonas Nick 
           Anthony Towns 
  Status: Deployed
  Type: Specification
  Assigned: 2020-01-19
  License: BSD-3-Clause
  Discussion: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal
  Requires: 340, 341

Introduction

Abstract

This document specifies the semantics of the initial scripting system under BIP341.

Copyright

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

Motivation

BIP341 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 BIP341 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 OP_CHECKSIG and OP_CHECKSIGVERIFY are modified to verify Schnorr signatures as specified in BIP340 and to use a signature message algorithm based on the common message calculation in BIP341. The tapscript signature message also simplifies OP_CODESEPARATOR handling and makes it more efficient.

The inefficient OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY opcodes are disabled. Instead, a new opcode OP_CHECKSIGADD 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 hash_types or signature algorithms. Additionally, the new tapscript OP_SUCCESS opcodes allow introducing new opcodes more cleanly than through OP_NOP.

Specification

The rules below only apply when validating a transaction input for which all of the conditions below are true:

• The transaction input is a segregated witness spend (i.e., the scriptPubKey contains a witness program as defined in BIP141).
• It is a taproot spend as defined in BIP341 (i.e., the witness version is 1, the witness program is 32 bytes, and it is not P2SH wrapped).
• It is a script path spend as defined in BIP341 (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 or 0xc1), 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 BIP141 or BIP341, fail. # The script as defined in BIP341 (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 OP_SUCCESS80, ..., OP_SUCCESS254, and collectively known as OP_SUCCESSx. ## If any push opcode fails to decode because it would extend past the end of the tapscript, fail. # If the initial stack as defined in BIP341 (i.e., the witness stack after removing both the optional annex and the two last stack elements after that) violates any resource limits (stack size, and size of the elements in the stack; see "Resource Limits" below), fail. Note that this check can be bypassed using OP_SUCCESSx. # The tapscript is executed according to the rules in the following section, with the initial stack as input. ## If execution fails for any reason, fail. ## If the execution results in anything but exactly one element on the stack which evaluates to true with CastToBool(), 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 OP_CHECKLOCKTIMEVERIFY and OP_CHECKSEQUENCEVERIFY opcodes defined in BIP65 and BIP112, but with the following modifications:

• Disabled script opcodes The following script opcodes are disabled in tapscript: OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY. The disabled opcodes behave in the same way as OP_RETURN, by failing and terminating the script immediately when executed, and being ignored when found in unexecuted branch of the script.
• 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 OP_IF and OP_NOTIF opcodes must be either exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1).
• OP_SUCCESSx opcodes As listed above, some opcodes are renamed to OP_SUCCESSx, and make the script unconditionally valid.
• Signature opcodes. The OP_CHECKSIG and OP_CHECKSIGVERIFY are modified to operate on Schnorr public keys and signatures (see BIP340) instead of ECDSA, and a new opcode OP_CHECKSIGADD is added.

** The opcode 186 (0xba) is named as OP_CHECKSIGADD.

Rules for signature opcodes

The following rules apply to OP_CHECKSIG, OP_CHECKSIGVERIFY, and OP_CHECKSIGADD.

• For OP_CHECKSIGVERIFY and OP_CHECKSIG, 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 OP_CHECKSIGADD, the public key (top element), a CScriptNum n (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 n 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 BIP340:

** If the signature is not the empty vector, the signature is validated against the public key (see the next subsection). Validation failure in this case immediately terminates script execution with failure.

• If the public key size is not zero and not 32 bytes, the public key is of an unknown public key type 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 OP_CHECKSIGVERIFY, the script MUST fail and terminate immediately. *** For OP_CHECKSIG, an empty vector is pushed onto the stack, and execution continues with the next opcode. *** For OP_CHECKSIGADD, a CScriptNum with value <