From c0d2f93f3c3c3dcee2318ea26f946ae17de37865 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 13 Jan 2020 14:10:26 -0800 Subject: Abstract out common signature message calculation --- bip-taproot.mediawiki | 87 +++++++++++++++++++++++-------------------------- bip-tapscript.mediawiki | 32 ++++++++---------- 2 files changed, 53 insertions(+), 66 deletions(-) diff --git a/bip-taproot.mediawiki b/bip-taproot.mediawiki index 7d2318e..a05d064 100644 --- a/bip-taproot.mediawiki +++ b/bip-taproot.mediawiki @@ -83,68 +83,61 @@ The following rules only apply when such an output is being spent. Any other out === Signature validation rules === -The following rules apply: +We first define a reusable common signature message calculation function, followed by the actual signature validation as it's used in key path spending. -* If the signature is not 64'''Why permit two signature lengths?''' By making the most common type of hash_type implicit, a byte can often be saved. or 65 bytes, fail. -* If the signature size is 65 bytes: -** If the final byte is not a valid hash_type (defined hereinafter), fail. -** If the final byte is 0x00, fail'''Why can the hash_type not be 0x00 in 65-byte signatures?''' Permitting that would enable malleating (by third parties, including miners) 64-byte signatures into 65-byte ones, resulting in a different `wtxid` and a different fee rate than the creator intended. -** If the first 64 bytes are not a valid signature according to bip-schnorr for the public key and message set to the transaction digest with hash_type set as the final byte, fail. -* If the signature size is 64 bytes: -** If it is not a valid signature according to bip-schnorr for the public key and the hash_type = 0x00 transaction digest as message, fail. -* Otherwise the signature is valid. +==== Common signature message ==== -==== hash_type ==== - -hash_type is an 8-bit unsigned value. The SIGHASH encodings from the legacy script system are used, including SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, and SIGHASH_ANYONECANPAY. Use of the default hash_type = 0x00 results in signing over the whole transaction just as for SIGHASH_ALL. - -The following use of hash_type are invalid, and fail execution: +The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. +The parameter ''hash_type'' is an 8-bit unsigned value. The SIGHASH encodings from the legacy script system are reused, including SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, and SIGHASH_ANYONECANPAY, plus a default ''hash_type'' (0) which results in signing over the whole transaction just as for SIGHASH_ALL. The following restrictions apply, which cause validation failure if violated: +* Using any undefined ''hash_type'' (not ''0x00'', ''0x01'', ''0x02'', ''0x03'', ''0x81'', ''0x82'', or ''0x83'''''Why reject unknown ''hash_type'' values?''' By doing so, it is easier to reason about the worst case amount of signature hashing an implementation with adequate caching must perform.). * Using SIGHASH_SINGLE without a "corresponding output" (an output with the same index as the input being verified). -* Using any hash_type value that is not 0x00, 0x01, 0x02, 0x03, 0x81, 0x82, or 0x83'''Why reject unknown hash_type values?''' By doing so, it is easier to reason about the worst case amount of signature hashing an implementation with adequate caching must perform.. -* The signature has 65 bytes, and hash_type is 0x00. -==== Transaction digest ==== +The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating the presence of extensions. -As the message for signature verification, transaction digest is ''hashTapSighash'' of the following values (size in byte) serialized. Numerical values in 2, 4, or 8-byte are encoded in little-endian. +If the parameters take acceptable values, the message is the concatenation 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: -** epoch (1): always 0. '''What's the purpose of the epoch?''' The epoch can be increased to allow securely creating new transaction digest algorithms with large changes to the structure or interpretation of hash_type if needed. -** hash_type (1). +** ''hash_type'' (1). * Transaction data: -** nVersion (4): the nVersion of the transaction. -** nLockTime (4): the nLockTime of the transaction. -** If the SIGHASH_ANYONECANPAY flag is not set: -*** sha_prevouts (32): the SHA256 of the serialization of all input outpoints. -*** sha_amounts (32): the SHA256 of the serialization of all input amounts. -*** sha_sequences (32): the SHA256 of the serialization of all input nSequence. -** If neither the SIGHASH_NONE nor the SIGHASH_SINGLE flag is set: -*** sha_outputs (32): the SHA256 of the serialization of all outputs in CTxOut format. +** ''nVersion'' (4): the ''nVersion'' of the transaction. +** ''nLockTime'' (4): the ''nLockTime'' of the transaction. +** If the ''hash_type & 0x80'' does not equal SIGHASH_ANYONECANPAY: +*** ''sha_prevouts'' (32): the SHA256 of the serialization of all input outpoints. +*** ''sha_amounts'' (32): the SHA256 of the serialization of all input amounts. +*** ''sha_sequences'' (32): the SHA256 of the serialization of all input ''nSequence''. +** If ''hash_type & 3'' does not equal SIGHASH_NONE or SIGHASH_SINGLE: +*** ''sha_outputs'' (32): the SHA256 of the serialization of all outputs in CTxOut format. * Data about this input: -** spend_type (1): -*** Bit 0 is set if an annex is present (the original witness stack has two or more witness elements, and the first byte of the last element is 0x50). -*** The other bits are unset. -** scriptPubKey (35): scriptPubKey of the previous output spent by this input, serialized as script inside CTxOut. Its size is always 35 bytes. -** If the SIGHASH_ANYONECANPAY flag is set: -*** outpoint (36): the COutPoint of this input (32-byte hash + 4-byte little-endian). -*** amount (8): value of the previous output spent by this input. -*** nSequence (4): nSequence of this input. -** If the SIGHASH_ANYONECANPAY flag is not set: -*** input_index (4): index of this input in the transaction input vector. Index of the first input is 0. -** If bit 0 of spend_type is set: -*** sha_annex (32): the SHA256 of (compact_size(size of annex) || annex). +** ''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'') +** ''scriptPubKey'' (35): ''scriptPubKey'' of the previous output spent by this input, serialized as script inside CTxOut. Its size is always 35 bytes. +** If ''hash_type & 0x80'' equals SIGHASH_ANYONECANPAY: +*** ''outpoint'' (36): the COutPoint of this input (32-byte hash + 4-byte little-endian). +*** ''amount'' (8): value of the previous output spent by this input. +*** ''nSequence'' (4): ''nSequence'' of this input. +** If ''hash_type & 0x80'' does not equal SIGHASH_ANYONECANPAY: +*** ''input_index'' (4): index of this input in the transaction input vector. Index of the first input is 0. +** 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. * Data about this output: -** If the SIGHASH_SINGLE flag is set: -*** sha_single_output (32): the SHA256 of the corresponding output in CTxOut format. +** If ''hash_type & 3'' equals SIGHASH_SINGLE: +*** ''sha_single_output'' (32): the SHA256 of the corresponding output in CTxOut format. -The total number of bytes hashed is at most ''210'' (excluding sub-hashes such as `sha_prevouts`)'''What is the number of bytes hashed for the signature hash?''' The total size of the input to ''hashTapSighash'' (excluding the initial 64-byte hash tag) can be computed using the following formula: ''178 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32''.. Sub-hashes may be cached across signatures of the same transaction. +The total length of ''SigMsg()'' is at most ''209'' bytes'''What is the output length of ''SigMsg()''?''' The total length of ''SigMsg()'' can be computed using the following formula: ''177 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32''.. Note that this does not include the size of sub-hashes such as ''sha_prevouts'', which may be cached across signatures of the same transaction. In summary, the semantics of the [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143] sighash types remain unchanged, except the following: -# The way and order of serialization is changed.'''Why is the serialization in the transaction digest changed?''' Hashes that go into the digest and the digest itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for transaction digests because there is no secret data. Therefore doubling SHA256 is a waste of resources. The digest computation now follows a logical order with transaction level data first, then input data and output data. This allows to efficiently cache the transaction part of the digest across different inputs using the SHA256 midstate. Additionally, sub-hashes can be skipped when calculating the digest (for example `sha_prevouts` if SIGHASH_ANYONECANPAY is set) instead of setting them to zero and then hashing them as in BIP143. Despite that, collisions are made impossible by committing to the length of the data (implicit in hash_type and spend_type) before the variable length data. -# The digest commits to the scriptPubKey'''Why does the transaction digest commit to the scriptPubKey?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (scriptCode in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed.. +# The way and order of serialization is changed.'''Why is the serialization in the transaction digest changed?''' Hashes that go into the digest and the digest itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for transaction digests because there is no secret data. Therefore doubling SHA256 is a waste of resources. The digest computation now follows a logical order with transaction level data first, then input data and output data. This allows to efficiently cache the transaction part of the digest across different inputs using the SHA256 midstate. Additionally, sub-hashes can be skipped when calculating the digest (for example `sha_prevouts` if SIGHASH_ANYONECANPAY is set) instead of setting them to zero and then hashing them as in BIP143. Despite that, collisions are made impossible by committing to the length of the data (implicit in ''hash_type'' and ''spend_type'') before the variable length data. +# The digest commits to the ''scriptPubKey'''''Why does the transaction digest commit to the ''scriptPubKey''?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (''scriptCode'' in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed.. # If the SIGHASH_ANYONECANPAY flag is not set, the digest commits to the amounts of ''all'' transaction inputs.'''Why does the transaction digest commit to the amounts of all transaction inputs?''' This eliminates the possibility to lie to offline signing devices about the fee of a transaction. -# The digest commits to all input nSequence if SIGHASH_NONE or SIGHASH_SINGLE are set (unless SIGHASH_ANYONECANPAY is set as well).'''Why does the transaction digest commit to all input nSequence if SIGHASH_SINGLE or SIGHASH_NONE are set?''' Because setting them already makes the digest commit to the prevouts part of all transaction inputs, it is not useful to treat the nSequence any different. Moreover, this change makes nSequence consistent with the view that SIGHASH_SINGLE and SIGHASH_NONE only modify the digest with respect to transaction outputs and not inputs. -# The digest commits to taproot-specific data epoch, spend_type and annex (if present). +# The digest commits to all input ''nSequence'' if SIGHASH_NONE or SIGHASH_SINGLE are set (unless SIGHASH_ANYONECANPAY is set as well).'''Why does the transaction digest commit to all input ''nSequence'' if SIGHASH_SINGLE or SIGHASH_NONE are set?''' Because setting them already makes the digest commit to the prevouts part of all transaction inputs, it is not useful to treat the ''nSequence'' any different. Moreover, this change makes ''nSequence'' consistent with the view that SIGHASH_SINGLE and SIGHASH_NONE only modify the digest with respect to transaction outputs and not inputs. +# The message includes commitments to the taproot-specific data ''spend_type'' and ''annex'' (if present). + +==== Taproot key path spending signature validation ==== + +To validate a signature ''sig'' with public key ''q'': +* If the ''sig'' is 64 bytes long, return ''Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 0)), sig)'''''Why is the input to ''hashTapSigHash'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hashTapSigHash'' tagged hash in future extensions that make invasive changes to how hashing is performed. An alternative is switching to a different tag, but supporting a growing number of tags may become undesirable., where ''Verify'' is defined in bip-schnorr. +* If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00'''Why can the hash_type not be 0x00 in 65-byte signatures?''' Permitting that would enable malleating (by third parties, including miners) 64-byte signatures into 65-byte ones, resulting in a different `wtxid` and a different fee rate than the creator intended and Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64])''. +* Otherwise, fail'''Why permit two signature lengths?''' By making the most common type of hash_type implicit, a byte can often be saved.. == Constructing and spending Taproot outputs == diff --git a/bip-tapscript.mediawiki b/bip-tapscript.mediawiki index e9c4278..a66e5f3 100644 --- a/bip-tapscript.mediawiki +++ b/bip-tapscript.mediawiki @@ -92,7 +92,7 @@ The following rules apply to OP_CHECKSIG, OP_CHECKSIGVERIFYn 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 signature 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 signature is not the empty vector, the signature is validated against the public key (see the next subsection). * If the public key size is not zero and not 32 bytes, the public key is of an ''unknown public key type'''''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 SIGHASH 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. 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: @@ -104,26 +104,20 @@ The following rules apply to OP_CHECKSIG, OP_CHECKSIGVERIFYOP_CHECKSIG, a 1-byte value 0x01 is pushed onto the stack. *** For OP_CHECKSIGADD, a CScriptNum with value of n + 1 is pushed onto the stack. -===Transaction digest=== +===Signature validation=== -As the message for signature opcodes signature verification, transaction digest has the same definition as in bip-taproot, except the following: +To validate a signature ''sig'' with public key ''p'': +* Compute the tapscript message extension ''ext'', consisting of: +** ''tapleaf_hash'' (32): the tapleaf hash as defined in bip-taproot +** ''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. +* If the ''sig'' is 64 bytes long, return ''Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in bip-schnorr. +* If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00 and Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0) || ext), sig[0:64])''. +* Otherwise, fail. -The one-byte spend_type has a different value, specifically at bit 1: -* Bit 0 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 0x50). -* Bit 1 is set. -* The other bits are unset. - -As additional pieces of data, added at the end of the input to the ''hashTapSighash'' function: -* tapleaf_hash (32): the tapleaf hash as defined in bip-taproot -* key_version (1): a constant value 0x00 representing the current version of public keys in the tapscript signature opcode execution. -* codeseparator_position (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. - -The total number of bytes hashed is at most ''247'''''What is the number of bytes hashed for the signature hash?''' The total size of the input to ''hashTapSighash'' (excluding the initial 64-byte hash tag) can be computed using the following formula: ''215 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32''.. - -In summary, the semantics of the [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143] sighash types remain unchanged, except the following: -# The exceptions mentioned in bip-taproot. -# The digest commits to taproot-specific data key_version.'''Why does the transaction digest commit to the key_version?''' This is for future extensions that define unknown public key types, making sure signatures can't be moved from one key type to another. -# The digest 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. +In summary, the semantics of signature validation is identical to bip-taproot, except the following: +# The digest commits to tapscript-specific data ''key_version''.'''Why does the transaction digest commit to the ''key_version''?''' This is for future extensions that define unknown public key types, making sure signatures can't be moved from one key type to another. +# The digest 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. # The digest commits to the opcode position of the last executed OP_CODESEPARATOR.'''Why does the transaction digest commit to the position of the last executed OP_CODESEPARATOR?''' This allows continuing to use OP_CODESEPARATOR to sign the executed path of the script. Because the codeseparator_position is the last input to the digest, the SHA256 midstate can be efficiently cached for multiple OP_CODESEPARATORs in a single script. In contrast, the BIP143 handling of OP_CODESEPARATOR is to commit to the executed script only from the last executed OP_CODESEPARATOR onwards which requires unnecessary rehashing of the script. It should be noted that the one known OP_CODESEPARATOR 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. ===Resource limits=== -- cgit v1.2.3 From 0e3b6c595c2b90eecb969e9bc84314f4b677ac46 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 14 Jan 2020 10:28:49 -0800 Subject: Address jonas' comments --- bip-taproot.mediawiki | 22 +++++++++++----------- bip-tapscript.mediawiki | 18 +++++++++--------- 2 files changed, 20 insertions(+), 20 deletions(-) diff --git a/bip-taproot.mediawiki b/bip-taproot.mediawiki index a05d064..7126149 100644 --- a/bip-taproot.mediawiki +++ b/bip-taproot.mediawiki @@ -41,7 +41,7 @@ As a result we choose this combination of technologies: * Taproot's advantages become apparent under the assumption that most applications involve outputs that could be spent by all parties agreeing. That's where '''Schnorr''' signatures come in, as they permit [https://eprint.iacr.org/2018/068 key aggregation]: a public key can be constructed from multiple participant public keys, and which requires cooperation between all participants to sign for. Such multi-party public keys and signatures are indistinguishable from their single-party equivalents. This means that with taproot most applications can use the key-based spending path, which is both efficient and private. This can be generalized to arbitrary M-of-N policies, as Schnorr signatures support threshold signing, at the cost of more complex setup protocols. * As Schnorr signatures also permit '''batch validation''', allowing multiple signatures to be validated together more efficiently than validating each one independently, we make sure all parts of the design are compatible with this. * Where unused bits appear as a result of the above changes, they are reserved for mechanisms for '''future extensions'''. As a result, every script in the Merkle tree has an associated version such that new script versions can be introduced with a soft fork while remaining compatible with bip-taproot. Additionally, future soft forks can make use of the currently unused annex in the witness (see [[#Rationale]]). -* While the core semantics of the '''signature hashing algorithm''' are not changed, a number of improvements are included in this proposal. The new signature hashing algorithm fixes the verification capabilities of offline signing devices by including amount and scriptPubKey in the digest, avoids unnecessary hashing, uses '''tagged hashes''' and defines a default sighash byte. +* While the core semantics of the '''signature hashing algorithm''' are not changed, a number of improvements are included in this proposal. The new signature hashing algorithm fixes the verification capabilities of offline signing devices by including amount and scriptPubKey in the signature message, avoids unnecessary hashing, uses '''tagged hashes''' and defines a default sighash byte. * The '''public key is directly included in the output''' in contrast to typical earlier constructions which store a hash of the public key or script in the output. This has the same cost for senders and is more space efficient overall if the key-based spending path is taken. '''Why is the public key directly included in the output?''' While typical earlier constructions store a hash of a script or a public key in the output, this is rather wasteful when a public key is always involved. To guarantee batch verifiability, the public key must be known to every verifier, and thus only revealing its hash as an output would imply adding an additional 32 bytes to the witness. Furthermore, to maintain [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html 128-bit collision security] for outputs, a 256-bit hash would be required anyway, which is comparable in size (and thus in cost for senders) to revealing the public key directly. While the usage of public key hashes is often said to protect against ECDLP breaks or quantum computers, this protection is very weak at best: transactions are not protected while being confirmed, and a very [https://twitter.com/pwuille/status/1108097835365339136 large portion] of the currency's supply is not under such protection regardless. Actual resistance to such systems can be introduced by relying on different cryptographic assumptions, but this proposal focuses on improvements that do not change the security model. Informally, the resulting design is as follows: a new witness version is added (version 1), whose programs consist of 32-byte encodings of points ''Q''. ''Q'' is computed as ''P + hash(P||m)G'' for a public key ''P'', and the root ''m'' of a Merkle tree whose leaves consist of a version number and a script. These outputs can be spent directly by providing a signature for ''Q'', or indirectly by revealing ''P'', the script and leaf version, inputs that satisfy the script, and a Merkle path that proves ''Q'' committed to that leaf. All hashes in this construction (the hash for computing ''Q'' from ''P'', the hashes inside the Merkle tree's inner nodes, and the signature hashes used) are tagged to guarantee domain separation. @@ -59,9 +59,9 @@ The following rules only apply when such an output is being spent. Any other out * Let ''q'' be the 32-byte array containing the witness program (the second push in the scriptPubKey) which represents a public key according to bip-schnorr. * Fail if the witness stack has 0 elements. -* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y squareness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the transaction digest and contributes to transaction weight, but is otherwise ignored during taproot validation. +* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y squareness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. * If there is exactly one element left in the witness stack, key path spending is used: -** The single witness stack element is interpreted as the signature and must be valid (see the next section) for the public key ''q'' and taproot transaction digest (to be defined hereinafter) as message. Fail if it is not. Otherwise pass. +** The single witness stack element is interpreted as the signature and must be valid (see the next section) for the public key ''q'' (see the next subsection). * If there are at least two witness elements left, script path spending is used: ** Call the second-to-last stack element ''s'', the script. ** The last stack element is called the control block ''c'', and must have length ''33 + 32m'', for a value of ''m'' that is an integer between 0 and 128'''Why is the Merkle path length limited to 128?''' The optimally space-efficient Merkle tree can be constructed based on the probabilities of the scripts in the leaves, using the Huffman algorithm. This algorithm will construct branches with lengths approximately equal to ''log2(1/probability)'', but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in ''2128''. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely., inclusive. Fail if it does not have such a length. @@ -89,11 +89,11 @@ We first define a reusable common signature message calculation function, follow The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. -The parameter ''hash_type'' is an 8-bit unsigned value. The SIGHASH encodings from the legacy script system are reused, including SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, and SIGHASH_ANYONECANPAY, plus a default ''hash_type'' (0) which results in signing over the whole transaction just as for SIGHASH_ALL. The following restrictions apply, which cause validation failure if violated: +The parameter ''hash_type'' is an 8-bit unsigned value. The SIGHASH encodings from the legacy script system are reused, including SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, and SIGHASH_ANYONECANPAY, plus the default ''hash_type'' value ''0x00'' which results in signing over the whole transaction just as for SIGHASH_ALL. The following restrictions apply, which cause validation failure if violated: * Using any undefined ''hash_type'' (not ''0x00'', ''0x01'', ''0x02'', ''0x03'', ''0x81'', ''0x82'', or ''0x83'''''Why reject unknown ''hash_type'' values?''' By doing so, it is easier to reason about the worst case amount of signature hashing an implementation with adequate caching must perform.). * Using SIGHASH_SINGLE without a "corresponding output" (an output with the same index as the input being verified). -The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating the presence of extensions. +The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating (in the message) that extensions are added at the end of the message'''What extensions use the ''ext_flag'' mechanism?''' Bip-tapscript reuses the same common signature message algorithm, but adds tapscript-specific data at the end, which is indicated using ''ext_flag = 1''.. If the parameters take acceptable values, the message is the concatenation 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. @@ -126,16 +126,16 @@ If the parameters take acceptable values, the message is the concatenation of th The total length of ''SigMsg()'' is at most ''209'' bytes'''What is the output length of ''SigMsg()''?''' The total length of ''SigMsg()'' can be computed using the following formula: ''177 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32''.. Note that this does not include the size of sub-hashes such as ''sha_prevouts'', which may be cached across signatures of the same transaction. In summary, the semantics of the [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143] sighash types remain unchanged, except the following: -# The way and order of serialization is changed.'''Why is the serialization in the transaction digest changed?''' Hashes that go into the digest and the digest itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for transaction digests because there is no secret data. Therefore doubling SHA256 is a waste of resources. The digest computation now follows a logical order with transaction level data first, then input data and output data. This allows to efficiently cache the transaction part of the digest across different inputs using the SHA256 midstate. Additionally, sub-hashes can be skipped when calculating the digest (for example `sha_prevouts` if SIGHASH_ANYONECANPAY is set) instead of setting them to zero and then hashing them as in BIP143. Despite that, collisions are made impossible by committing to the length of the data (implicit in ''hash_type'' and ''spend_type'') before the variable length data. -# The digest commits to the ''scriptPubKey'''''Why does the transaction digest commit to the ''scriptPubKey''?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (''scriptCode'' in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed.. -# If the SIGHASH_ANYONECANPAY flag is not set, the digest commits to the amounts of ''all'' transaction inputs.'''Why does the transaction digest commit to the amounts of all transaction inputs?''' This eliminates the possibility to lie to offline signing devices about the fee of a transaction. -# The digest commits to all input ''nSequence'' if SIGHASH_NONE or SIGHASH_SINGLE are set (unless SIGHASH_ANYONECANPAY is set as well).'''Why does the transaction digest commit to all input ''nSequence'' if SIGHASH_SINGLE or SIGHASH_NONE are set?''' Because setting them already makes the digest commit to the prevouts part of all transaction inputs, it is not useful to treat the ''nSequence'' any different. Moreover, this change makes ''nSequence'' consistent with the view that SIGHASH_SINGLE and SIGHASH_NONE only modify the digest with respect to transaction outputs and not inputs. -# The message includes commitments to the taproot-specific data ''spend_type'' and ''annex'' (if present). +# The way and order of serialization is changed.'''Why is the serialization in the signature message changed?''' Hashes that go into the signature message and the message itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for signature messages because there is no secret data. Therefore doubling SHA256 is a waste of resources. The message computation now follows a logical order with transaction level data first, then input data and output data. This allows to efficiently cache the transaction part of the message across different inputs using the SHA256 midstate. Additionally, sub-hashes can be skipped when calculating the message (for example `sha_prevouts` if SIGHASH_ANYONECANPAY is set) instead of setting them to zero and then hashing them as in BIP143. Despite that, collisions are made impossible by committing to the length of the data (implicit in ''hash_type'' and ''spend_type'') before the variable length data. +# The signature message commits to the ''scriptPubKey'''''Why does the signature message commit to the ''scriptPubKey''?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (''scriptCode'' in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed.. +# If the SIGHASH_ANYONECANPAY flag is not set, the message commits to the amounts of ''all'' transaction inputs.'''Why does the signature message commit to the amounts of all transaction inputs?''' This eliminates the possibility to lie to offline signing devices about the fee of a transaction. +# The signature message commits to all input ''nSequence'' if SIGHASH_NONE or SIGHASH_SINGLE are set (unless SIGHASH_ANYONECANPAY is set as well).'''Why does the signature message commit to all input ''nSequence'' if SIGHASH_SINGLE or SIGHASH_NONE are set?''' Because setting them already makes the message commit to the prevouts part of all transaction inputs, it is not useful to treat the ''nSequence'' any different. Moreover, this change makes ''nSequence'' consistent with the view that SIGHASH_SINGLE and SIGHASH_NONE only modify the signature message with respect to transaction outputs and not inputs. +# The signature message includes commitments to the taproot-specific data ''spend_type'' and ''annex'' (if present). ==== Taproot key path spending signature validation ==== To validate a signature ''sig'' with public key ''q'': -* If the ''sig'' is 64 bytes long, return ''Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 0)), sig)'''''Why is the input to ''hashTapSigHash'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hashTapSigHash'' tagged hash in future extensions that make invasive changes to how hashing is performed. An alternative is switching to a different tag, but supporting a growing number of tags may become undesirable., where ''Verify'' is defined in bip-schnorr. +* If the ''sig'' is 64 bytes long, return ''Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 0)), sig)'''''Why is the input to ''hashTapSigHash'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hashTapSigHash'' tagged hash in future signature algorithms that make invasive changes to how hashing is performed (as opposed to the ''ext_flag'' mechanism that is used for incremental extensions). An alternative is having them use a different tag, but supporting a growing number of tags may become undesirable., where ''Verify'' is defined in bip-schnorr. * If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00'''Why can the hash_type not be 0x00 in 65-byte signatures?''' Permitting that would enable malleating (by third parties, including miners) 64-byte signatures into 65-byte ones, resulting in a different `wtxid` and a different fee rate than the creator intended and Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64])''. * Otherwise, fail'''Why permit two signature lengths?''' By making the most common type of hash_type implicit, a byte can often be saved.. diff --git a/bip-tapscript.mediawiki b/bip-tapscript.mediawiki index a66e5f3..8beef28 100644 --- a/bip-tapscript.mediawiki +++ b/bip-tapscript.mediawiki @@ -34,8 +34,8 @@ Specifically, the goal is making '''Schnorr signatures''', '''batch validation'' ==Design== -In order to achieve these goals, signature opcodes OP_CHECKSIG and OP_CHECKSIGVERIFY 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 OP_CODESEPARATOR handling and makes it more efficient. +In order to achieve these goals, signature opcodes OP_CHECKSIG and OP_CHECKSIGVERIFY are modified to verify Schnorr signatures as specified in bip-schnorr and to use a signature message algorithm based on the common message calculation in bip-taproot. +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. @@ -92,7 +92,7 @@ The following rules apply to OP_CHECKSIG, OP_CHECKSIGVERIFYn 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 against the public key (see the next subsection). +** 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'''''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 SIGHASH 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. 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: @@ -107,18 +107,18 @@ The following rules apply to OP_CHECKSIG, OP_CHECKSIGVERIFYOP_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. -* If the ''sig'' is 64 bytes long, return ''Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in bip-schnorr. -* If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00 and Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0) || ext), sig[0:64])''. +* If the ''sig'' is 64 bytes long, return ''Verify(p, hashTapSigHash(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in bip-schnorr. +* 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 bip-taproot, except the following: -# The digest commits to tapscript-specific data ''key_version''.'''Why does the transaction digest commit to the ''key_version''?''' This is for future extensions that define unknown public key types, making sure signatures can't be moved from one key type to another. -# The digest 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. -# The digest commits to the opcode position of the last executed OP_CODESEPARATOR.'''Why does the transaction digest commit to the position of the last executed OP_CODESEPARATOR?''' This allows continuing to use OP_CODESEPARATOR to sign the executed path of the script. Because the codeseparator_position is the last input to the digest, the SHA256 midstate can be efficiently cached for multiple OP_CODESEPARATORs in a single script. In contrast, the BIP143 handling of OP_CODESEPARATOR is to commit to the executed script only from the last executed OP_CODESEPARATOR onwards which requires unnecessary rehashing of the script. It should be noted that the one known OP_CODESEPARATOR 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. +# The signature message includes the tapscript-specific data ''key_version''.'''Why does the signature message commit to the ''key_version''?''' This is for future extensions that define unknown public key types, making sure signatures can't be moved from one key type to another. +# 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. +# The signature message includes the opcode position of the last executed OP_CODESEPARATOR.'''Why does the signature message include the position of the last executed OP_CODESEPARATOR?''' This allows continuing to use OP_CODESEPARATOR to sign the executed path of the script. Because the codeseparator_position is the last input to the hash, the SHA256 midstate can be efficiently cached for multiple OP_CODESEPARATORs in a single script. In contrast, the BIP143 handling of OP_CODESEPARATOR is to commit to the executed script only from the last executed OP_CODESEPARATOR onwards which requires unnecessary rehashing of the script. It should be noted that the one known OP_CODESEPARATOR 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. ===Resource limits=== -- cgit v1.2.3