ReddCoin (RDD) 4.22 Taproot: Validation of Taproot Scripts (BIP0342)

A complex description of BIP0342 adapted to ReddCoin’s bespoke PoSVv2 staking protocol. Includes initial activation of SegWit (Segregated Witness) network and address support. Content adapted from BTC’s wiki here.

This document specifies the semantics of the initial scripting system under BIP341 as a separate BIP0342.

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.

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[2]. 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)[3].
• 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. [4][5]

Common Signature Message Extension

We define the tapscript message extension ext to BIP341 Common Signature Message, indicated by ext_flag = 1:

• tapleaf_hash (32): the tapleaf hash as defined in BIP341
• key_version (1): a constant value 0x00 representing the current version of public keys in the tapscript signature opcode execution.
• codesep_pos (4): the opcode position of the last executed OP_CODESEPARATOR before the currently executed signature opcode, with the value in little endian (or 0xffffffff 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. Opcodes in parsed but unexecuted branches count towards this value as well.

Signature validation

To validate a signature sig with public key p:

• Compute the tapscript message extension ext described above.
• If the sig is 64 bytes long, return Verify(p, hashTapSighash(0x00 || SigMsg(0x00, 1) || ext), sig), where Verify is defined in BIP340.
• If the sig is 65 bytes long, return sig[64] ≠ 0x00 and Verify(p, hashTapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64]).
• Otherwise, fail.

In summary, the semantics of signature validation is identical to BIP340, except the following:

1. The signature message includes the tapscript-specific data key_version.[7]
2. The signature message commits to the executed script through the tapleaf_hash which includes the leaf version and script instead of scriptCode. This implies that this commitment is unaffected by OP_CODESEPARATOR.
3. The signature message includes the opcode position of the last executed OP_CODESEPARATOR.[8]

Resource limits

In addition to changing the semantics of a number of opcodes, there are also some changes to the resource limitations:

• Script size limit The maximum script size of 10000 bytes does not apply. Their size is only implicitly bounded by the block weight limit.[9]
• Non-push opcodes limit The maximum non-push opcodes limit of 201 per script does not apply.[10]
• Sigops limit The sigops in tapscripts do not count towards the block-wide limit of 80000 (weighted). Instead, there is a per-script sigops budget. The budget equals 50 + the total serialized size in bytes of the transaction input’s witness (including the CompactSize prefix). Executing a signature opcode (OP_CHECKSIG, OP_CHECKSIGVERIFY, or OP_CHECKSIGADD) with a non-empty signature decrements the budget by 50. If that brings the budget below zero, the script fails immediately. Signature opcodes with unknown public key type and non-empty signature are also counted.[11][12][13].
• Stack + altstack element count limit The existing limit of 1000 elements in the stack and altstack together after every executed opcode remains. It is extended to also apply to the size of initial stack.
• Stack element size limit The existing limit of maximum 520 bytes per stack element remains, both in the initial stack and in push opcodes.

Rationale

1. ^ OP_SUCCESSx OP_SUCCESSx is a mechanism to upgrade the Script system. Using an OP_SUCCESSx before its meaning is defined by a softfork is insecure and leads to fund loss. The inclusion of OP_SUCCESSx in a script will pass it unconditionally. It precedes any script execution rules to avoid the difficulties in specifying various edge cases, for example: OP_SUCCESSx in a script with an input stack larger than 1000 elements, OP_SUCCESSx after too many signature opcodes, or even scripts with conditionals lacking OP_ENDIF. The mere existence of an OP_SUCCESSx anywhere in the script will guarantee a pass for all such cases. OP_SUCCESSx are similar to the OP_RETURN in very early bitcoin versions (v0.1 up to and including v0.3.5). The original OP_RETURN 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 OP_RETURN in scriptSig. This is not a concern in the present proposal since it is not possible for a third party to inject an OP_SUCCESSx to the validation process, as the OP_SUCCESSx is part of the script (and thus committed to by the taproot output), implying the consent of the coin owner. OP_SUCCESSx can be used for a variety of upgrade possibilities:

• An OP_SUCCESSx could be turned into a functional opcode through a softfork. Unlike OP_NOPx-derived opcodes which only have read-only access to the stack, OP_SUCCESSx may also write to the stack. Any rule changes to an OP_SUCCESSx-containing script may only turn a valid script into an invalid one, and this is always achievable with softforks.
• Since OP_SUCCESSx precedes size check of initial stack and push opcodes, an OP_SUCCESSx-derived opcode requiring stack elements bigger than 520 bytes may uplift the limit in a softfork.
• OP_SUCCESSx may also redefine the behavior of existing opcodes so they could work together with the new opcode. For example, if an OP_SUCCESSx-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 OP_SUCCESSx 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 OP_SUCCESSx opcode.

1. ^ Why is a limit on script size no longer needed? Since there is no scriptCode directly included in the signature hash (only indirectly through a precomputable tapleaf hash), the CPU time spent on a signature check is no longer proportional to the size of the script being executed.
2. ^ Why is a limit on the number of opcodes no longer needed? An opcode limit only helps to the extent that it can prevent data structures from growing unboundedly during execution (both because of memory usage, and because of time that may grow in proportion to the size of those structures). The size of stack and altstack is already independently limited. By using O(1) logic for OP_IF, OP_NOTIF, OP_ELSE, and OP_ENDIF as suggested here and implemented here, the only other instance can be avoided as well.
3. ^ 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.
4. ^ Parameter choice of the sigop limit Regular witnesses are unaffected by the limit as their weight is composed of public key and (SIGHASH_ALL) signature pairs with 33 + 65 weight units each (which includes a 1 weight unit CompactSize 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.
5. Why are only signature opcodes counted toward the budget, and not for example hashing opcodes or other expensive operations? It turns out that the CPU cost per witness byte for verification of a script consisting of the maximum density of signature checking opcodes (taking the 50 WU/sigop limit into account) is already very close to that of scripts packed with other opcodes, including hashing opcodes (taking the 520 byte stack element limit into account) and OP_ROLL (taking the 1000 stack element limit into account). That said, the construction is very flexible, and allows adding new signature opcodes like CHECKSIGFROMSTACK 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 no need to stuff the witness with meaningless data. Instead, the taproot annex can be used to add weight to the witness without increasing the actual witness size.

Deployment

This proposal is deployed identically to Taproot (BIP341). See ReddCoin’s adaptation of BIP0341 detail and technical info at https://medium.com/projectredd.

Acknowledgements

This document is the result of ReddCoin’s team adapting directly technology, rationale, code and discussions from the BTC community and dev team around script and signature improvements with many people, and had direct contributions from Greg Maxwell and others. It further builds on top of earlier published proposals such as Taproot by Greg Maxwell, and Merkle branch constructions by Russell O’Connor, Johnson Lau, and Mark Friedenbach.

The ReddCoin team acknowledges the work of the authors who themselves wish tho thank Arik Sosman for suggesting to sort Merkle node children before hashes, removing the need to transfer the position in the tree, as well as all those who provided valuable feedback and reviews, including the participants of the structured reviews.

Source material may be found at: https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki

Further structured review of all features and complex concepts may be found at: https://github.com/ajtowns/taproot-review

About Redd

Redd is a global social movement that allows anyone, anywhere, the power to tip, support, donate and fund social causes, independent content creators, and humanitarian programs. The platform utilizes ReddCoin (RDD), a reliable and versatile decentralized cryptocurrency launched in 2014 that allows for seamless payments across borders and social networks. All Redd Partners are expected to adhere to the project’s high standards of openness, accountability, and user experience as we strive to be an example of not only the stated ideals of love, support and inclusion, but also integrity, transparency, and honor.

Feel free to visit us at Redd.Love, Reddcoin.com or email info@reddcoin.com. You can also follow us on YouTube, Twitter and Telegram Love to all of our Reddheads, new and old, and welcome!