diff options
Diffstat (limited to 'bip-0341.mediawiki')
| -rw-r--r-- | bip-0341.mediawiki | 68 |
1 files changed, 52 insertions, 16 deletions
diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index 564071f..ba3310f 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -13,6 +13,7 @@ License: BSD-3-Clause Requires: 340 Post-History: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal + 2019-10-09: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017378.html [bitcoin-dev] Taproot updates </pre> ==Introduction== @@ -65,7 +66,7 @@ The following rules only apply when such an output is being spent. Any other out * 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<ref>'''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 ''log<sub>2</sub>(1/probability)'', but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in ''2<sup>128</sup>''. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely.</ref>, inclusive. Fail if it does not have such a length. -** Let ''p = c[1:33]'' and let ''P = lift_x_even_y(int(p))'' where ''lift_x_even_y'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. +** Let ''p = c[1:33]'' and let ''P = lift_x(int(p))'' where ''lift_x'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. ** Let ''v = c[0] & 0xfe'' and call it the ''leaf version''<ref>'''What constraints are there on the leaf version?''' First, the leaf version cannot be odd as ''c[0] & 0xfe'' will always be even, and cannot be ''0x50'' as that would result in ambiguity with the annex. In addition, in order to support some forms of static analysis that rely on being able to identify script spends without access to the output being spent, it is recommended to avoid using any leaf versions that would conflict with a valid first byte of either a valid P2WPKH pubkey or a valid P2WSH script (that is, both ''v'' and ''v | 1'' should be an undefined, invalid or disabled opcode or an opcode that is not valid as the first opcode). The values that comply to this rule are the 32 even values between ''0xc0'' and ''0xfe'' and also ''0x66'', ''0x7e'', ''0x80'', ''0x84'', ''0x96'', ''0x98'', ''0xba'', ''0xbc'', ''0xbe''. Note also that this constraint implies that leaf versions should be shared amongst different witness versions, as knowing the witness version requires access to the output being spent.</ref>. ** Let ''k<sub>0</sub> = hash<sub>TapLeaf</sub>(v || compact_size(size of s) || s)''; also call it the ''tapleaf hash''. ** For ''j'' in ''[0,1,...,m-1]'': @@ -104,16 +105,17 @@ If the parameters take acceptable values, the message is the concatenation of th ** ''nLockTime'' (4): the ''nLockTime'' of the transaction. ** If the ''hash_type & 0x80'' does not equal <code>SIGHASH_ANYONECANPAY</code>: *** ''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_amounts'' (32): the SHA256 of the serialization of all spent output amounts. +*** ''sha_scriptpubkeys'' (32): the SHA256 of the serialization of all spent output ''scriptPubKey''s. *** ''sha_sequences'' (32): the SHA256 of the serialization of all input ''nSequence''. ** If ''hash_type & 3'' does not equal <code>SIGHASH_NONE</code> or <code>SIGHASH_SINGLE</code>: *** ''sha_outputs'' (32): the SHA256 of the serialization of all outputs in <code>CTxOut</code> format. * Data about this input: ** ''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 <code>CTxOut</code>. Its size is always 35 bytes. ** If ''hash_type & 0x80'' equals <code>SIGHASH_ANYONECANPAY</code>: *** ''outpoint'' (36): the <code>COutPoint</code> of this input (32-byte hash + 4-byte little-endian). *** ''amount'' (8): value of the previous output spent by this input. +*** ''scriptPubKey'' (35): ''scriptPubKey'' of the previous output spent by this input, serialized as script inside <code>CTxOut</code>. Its size is always 35 bytes. *** ''nSequence'' (4): ''nSequence'' of this input. ** If ''hash_type & 0x80'' does not equal <code>SIGHASH_ANYONECANPAY</code>: *** ''input_index'' (4): index of this input in the transaction input vector. Index of the first input is 0. @@ -123,11 +125,11 @@ If the parameters take acceptable values, the message is the concatenation of th ** If ''hash_type & 3'' equals <code>SIGHASH_SINGLE</code>: *** ''sha_single_output'' (32): the SHA256 of the corresponding output in <code>CTxOut</code> format. -The total length of ''SigMsg()'' is at most ''209'' bytes<ref>'''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''.</ref>. 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. +The total length of ''SigMsg()'' is at most ''206'' bytes<ref>'''What is the output length of ''SigMsg()''?''' The total length of ''SigMsg()'' can be computed using the following formula: ''174 - is_anyonecanpay * 49 - is_none * 32 + has_annex * 32''.</ref>. 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 [[bip-0143.mediawiki|BIP143]] sighash types remain unchanged, except the following: # The way and order of serialization is changed.<ref>'''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 <code>SIGHASH_ANYONECANPAY</code> 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.</ref> -# The signature message commits to the ''scriptPubKey''<ref>'''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.</ref>. +# The signature message commits to the ''scriptPubKey'' of the spent output and if the <code>SIGHASH_ANYONECANPAY</code> flag is not set, the message commits to the ''scriptPubKey''s of ''all'' outputs spent by the transaction. <ref>'''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. Moreover, committing to all spent ''scriptPubKey''s helps offline signing devices to determine the subset that belong to its own wallet. This is useful in [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-April/017801.html automated coinjoins].</ref>. # If the <code>SIGHASH_ANYONECANPAY</code> flag is not set, the message commits to the amounts of ''all'' transaction inputs.<ref>'''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.</ref> # The signature message commits to all input ''nSequence'' if <code>SIGHASH_NONE</code> or <code>SIGHASH_SINGLE</code> are set (unless <code>SIGHASH_ANYONECANPAY</code> is set as well).<ref>'''Why does the signature message commit to all input ''nSequence'' if <code>SIGHASH_SINGLE</code> or <code>SIGHASH_NONE</code> are set?''' Because setting them already makes the message commit to the <code>prevouts</code> 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 <code>SIGHASH_SINGLE</code> and <code>SIGHASH_NONE</code> only modify the signature message with respect to transaction outputs and not inputs.</ref> # The signature message includes commitments to the taproot-specific data ''spend_type'' and ''annex'' (if present). @@ -135,7 +137,7 @@ In summary, the semantics of the [[bip-0143.mediawiki|BIP143]] sighash types rem ==== 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, hash<sub>TapSigHash</sub>(0x00 || SigMsg(0x00, 0)), sig)''<ref>'''Why is the input to ''hash<sub>TapSigHash</sub>'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hash<sub>TapSigHash</sub>'' 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.</ref>, where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. +* If the ''sig'' is 64 bytes long, return ''Verify(q, hash<sub>TapSighash</sub>(0x00 || SigMsg(0x00, 0)), sig)''<ref>'''Why is the input to ''hash<sub>TapSighash</sub>'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hash<sub>TapSighash</sub>'' 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.</ref>, where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. * If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00<ref>'''Why can the <code>hash_type</code> not be <code>0x00</code> 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</ref> and Verify(q, hash<sub>TapSighash</sub>(0x00 || SigMsg(sig[64], 0)), sig[0:64])''. * Otherwise, fail<ref>'''Why permit two signature lengths?''' By making the most common type of <code>hash_type</code> implicit, a byte can often be saved.</ref>. @@ -150,7 +152,7 @@ Satisfying any of these conditions is sufficient to spend the output. '''Initial steps''' The first step is determining what the internal key and the organization of the rest of the scripts should be. The specifics are likely application dependent, but here are some general guidelines: * When deciding between scripts with conditionals (<code>OP_IF</code> etc.) and splitting them up into multiple scripts (each corresponding to one execution path through the original script), it is generally preferable to pick the latter. * When a single condition requires signatures with multiple keys, key aggregation techniques like MuSig can be used to combine them into a single key. The details are out of scope for this document, but note that this may complicate the signing procedure. -* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = lift_x_even_y(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. +* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. * If the spending conditions do not require a script path, the output key should commit to an unspendable script path instead of having no script path. This can be achieved by computing the output key point as ''Q = P + int(hash<sub>TapTweak</sub>(bytes(P)))G''. <ref>'''Why should the output key always have a taproot commitment, even if there is no script path?''' If the taproot output key is an aggregate of keys, there is the possibility for a malicious party to add a script path without being noticed by the other parties. This allows to bypass the multiparty policy and to steal the coin. @@ -171,14 +173,14 @@ First, we define <code>taproot_tweak_pubkey</code> for 32-byte [[bip-0340.mediaw The function returns a bit indicating the tweaked public key's Y coordinate as well as the public key byte array. The parity bit will be required for spending the output with a script path. In order to allow spending with the key path, we define <code>taproot_tweak_seckey</code> to compute the secret key for a tweaked public key. -For any byte string <code>h</code> it holds that <code>taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h))</code>. +For any byte string <code>h</code> it holds that <code>taproot_tweak_pubkey(pubkey_gen(seckey), h)[1] == pubkey_gen(taproot_tweak_seckey(seckey, h))</code>. <source lang="python"> def taproot_tweak_pubkey(pubkey, h): t = int_from_bytes(tagged_hash("TapTweak", pubkey + h)) if t >= SECP256K1_ORDER: raise ValueError - Q = point_add(lift_x_even_y(int_from_bytes(pubkey)), point_mul(G, t)) + Q = point_add(lift_x(pubkey), point_mul(G, t)) return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q)) def taproot_tweak_seckey(seckey0, h): @@ -191,7 +193,7 @@ def taproot_tweak_seckey(seckey0, h): </source> The following function, <code>taproot_output_script</code>, returns a byte array with the scriptPubKey (see [[bip-0141.mediawiki|BIP141]]). -<code>ser_script</code> refers to a function that prefixes its input with a CCompactSize-encoded length. +<code>ser_script</code> refers to a function that prefixes its input with a CompactSize-encoded length. <source lang="python"> def taproot_tree_helper(script_tree): @@ -217,7 +219,7 @@ def taproot_output_script(internal_pubkey, script_tree): h = bytes() else: _, h = taproot_tree_helper(script_tree) - output_pubkey, _ = taproot_tweak_pubkey(internal_pubkey, h) + _, output_pubkey = taproot_tweak_pubkey(internal_pubkey, h) return bytes([0x51, 0x20]) + output_pubkey </source> @@ -282,9 +284,7 @@ The reason for this is to increase leaf entropy and prevent an observer from lea == Test vectors == -Examples with creation transaction and spending transaction pairs, valid and invalid. - -Examples of preimage for sighashing for each of the sighash modes. +The test vectors used in the [https://github.com/bitcoin/bitcoin/blob/3820090bd619ac85ab35eff376c03136fe4a9f04/src/test/script_tests.cpp#L1718 Bitcoin Core unit test framework] can be found [https://github.com/bitcoin-core/qa-assets/blob/main/unit_test_data/script_assets_test.json?raw=true here]. == Rationale == @@ -292,7 +292,43 @@ Examples of preimage for sighashing for each of the sighash modes. == Deployment == -TODO +This BIP is deployed concurrently with [[bip-0342.mediawiki|BIP342]]. + +For Bitcoin signet, these BIPs are always active. + +For Bitcoin mainnet and testnet3, these BIPs will be deployed by "version bits" with the name "taproot" and bit 2, using [[bip-0009.mediawiki|BIP9]] modified to use a lower threshold, with an additional ''min_activation_height'' parameter and replacing the state transition logic for the DEFINED, STARTED and LOCKED_IN states as follows: + + case DEFINED: + if (GetMedianTimePast(block.parent) >= starttime) { + return STARTED; + } + return DEFINED; + + case STARTED: + int count = 0; + walk = block; + for (i = 0; i < 2016; i++) { + walk = walk.parent; + if ((walk.nVersion & 0xE0000000) == 0x20000000 && ((walk.nVersion >> bit) & 1) == 1) { + count++; + } + } + if (count >= threshold) { + return LOCKED_IN; + } else if (GetMedianTimePast(block.parent) >= timeout) { + return FAILED; + } + return STARTED; + + case LOCKED_IN: + if (block.nHeight < min_activation_height) { + return LOCKED_IN; + } + return ACTIVE; + +For Bitcoin mainnet, the starttime is epoch timestamp 1619222400 (midnight 24 April 2021 UTC), timeout is epoch timestamp 1628640000 (midnight 11 August 2021 UTC), the threshold is 1815 blocks (90%) instead of 1916 blocks (95%), and the min_activation_height is block 709632 (expected approximately 12 November 2021). + +For Bitcoin testnet3, the starttime is epoch timestamp 1619222400 (midnight 24 April 2021 UTC), timeout is epoch timestamp 1628640000 (midnight 11 August 2021 UTC), the threshold is 1512 blocks (75%), and the min_activation_height is block 0. == Backwards compatibility == As a soft fork, older software will continue to operate without modification. @@ -300,7 +336,7 @@ Non-upgraded nodes, however, will consider all SegWit version 1 witness programs They are strongly encouraged to upgrade in order to fully validate the new programs. Non-upgraded wallets can receive and send bitcoin from non-upgraded and upgraded wallets using SegWit version 0 programs, traditional pay-to-pubkey-hash, etc. -Depending on the implementation non-upgraded wallets may be able to send to Segwit version 1 programs if they support sending to [[bip-0173.mediawiki|BIP173]] Bech32 addresses. +Depending on the implementation non-upgraded wallets may be able to send to Segwit version 1 programs if they support sending to [[bip-0350.mediawiki|BIP350]] Bech32m addresses. == Acknowledgements == |