diff options
Diffstat (limited to 'bip-0342.mediawiki')
| -rw-r--r-- | bip-0342.mediawiki | 22 |
1 files changed, 16 insertions, 6 deletions
diff --git a/bip-0342.mediawiki b/bip-0342.mediawiki index 3cf87a3..64d07cc 100644 --- a/bip-0342.mediawiki +++ b/bip-0342.mediawiki @@ -7,7 +7,7 @@ Anthony Towns <aj@erisian.com.au> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0342 - Status: Draft + Status: Final Type: Standards Track Created: 2020-01-19 License: BSD-3-Clause @@ -104,13 +104,17 @@ The following rules apply to <code>OP_CHECKSIG</code>, <code>OP_CHECKSIGVERIFY</ *** 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. +===Common Signature Message Extension=== + +We define the tapscript message extension ''ext'' to [[bip-0341.mediawiki#common-signature-message|BIP341 Common Signature Message]], indicated by ''ext_flag = 1'': +* ''tapleaf_hash'' (32): the tapleaf hash as defined in [[bip-0341.mediawiki#design|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 <code>OP_CODESEPARATOR</code> 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'', consisting of the concatenation of: -** ''tapleaf_hash'' (32): the tapleaf hash as defined in [[bip-0341.mediawiki#design|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 <code>OP_CODESEPARATOR</code> 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. +* Compute the tapscript message extension ''ext'' described above. * If the ''sig'' is 64 bytes long, return ''Verify(p, hash<sub>TapSighash</sub>(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. * If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00 and Verify(p, hash<sub>TapSighash</sub>(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64])''. * Otherwise, fail. @@ -125,7 +129,7 @@ In summary, the semantics of signature validation is identical to BIP340, except 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.<ref>'''Why is a limit on script size no longer needed?''' Since there is no <code>scriptCode</code> 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.</ref> * '''Non-push opcodes limit''' The maximum non-push opcodes limit of 201 per script does not apply.<ref>'''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 <code>OP_IF</code>, <code>OP_NOTIF</code>, <code>OP_ELSE</code>, and <code>OP_ENDIF</code> as suggested [https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/ here] and implemented [https://github.com/bitcoin/bitcoin/pull/16902 here], the only other instance can be avoided as well.</ref> -* '''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 <code>CCompactSize</code> prefix). Executing a signature opcode (<code>OP_CHECKSIG</code>, <code>OP_CHECKSIGVERIFY</code>, or <code>OP_CHECKSIGADD</code>) 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.<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.</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><ref>'''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 <code>OP_ROLL</code> (taking the 1000 stack element limit into account). That said, the construction is very flexible, and allows adding 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 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.</ref>. +* '''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 <code>CompactSize</code> prefix). Executing a signature opcode (<code>OP_CHECKSIG</code>, <code>OP_CHECKSIGVERIFY</code>, or <code>OP_CHECKSIGADD</code>) 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.<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.</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>CompactSize</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><ref>'''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 <code>OP_ROLL</code> (taking the 1000 stack element limit into account). That said, the construction is very flexible, and allows adding 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 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.</ref>. * '''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. @@ -133,8 +137,14 @@ In addition to changing the semantics of a number of opcodes, there are also som <references /> +==Deployment== + +This proposal is deployed identically to Taproot ([[bip-0341.mediawiki|BIP341]]). + ==Examples== +The Taproot ([[bip-0341.mediawiki|BIP341]]) test vectors also contain examples for Tapscript execution. + ==Acknowledgements== This document is the result of many discussions and contains contributions by a number of people. The authors wish to thank all those who provided valuable feedback and reviews, including the participants of the [https://github.com/ajtowns/taproot-review structured reviews]. |