diff options
Diffstat (limited to 'bip-0341.mediawiki')
| -rw-r--r-- | bip-0341.mediawiki | 51 |
1 files changed, 34 insertions, 17 deletions
diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index ba3310f..8d2af3c 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -78,7 +78,7 @@ The following rules only apply when such an output is being spent. Any other out ** If ''t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'' (order of secp256k1), fail. ** Let ''Q = P + int(t)G''. ** If ''q ≠ x(Q)'' or ''c[0] & 1 ≠ y(Q) mod 2'', fail<ref>'''Why is it necessary to reveal a bit in a script path spend and check that it matches the parity of the Y coordinate of ''Q''?''' The parity of the Y coordinate is necessary to lift the X coordinate ''q'' to a unique point. While this is not strictly necessary for verifying the taproot commitment as described above, it is necessary to allow batch verification. Alternatively, ''Q'' could be forced to have an even Y coordinate, but that would require retrying with different internal public keys (or different messages) until ''Q'' has that property. There is no downside to adding the parity bit because otherwise the control block bit would be unused.</ref>. -** Execute the script, according to the applicable script rules<ref>'''What are the applicable script rules in script path spends?''' [[bip-0342.mediawiki|BIP342]] specifies validity rules that apply for leaf version 0xc0, but future proposals can introduce rules for other leaf versions.</ref>, using the witness stack elements excluding the script ''s'', the control block ''c'', and the annex ''a'' if present, as initial stack. +** Execute the script, according to the applicable script rules<ref>'''What are the applicable script rules in script path spends?''' [[bip-0342.mediawiki|BIP342]] specifies validity rules that apply for leaf version 0xc0, but future proposals can introduce rules for other leaf versions.</ref>, using the witness stack elements excluding the script ''s'', the control block ''c'', and the annex ''a'' if present, as initial stack. This implies that for the future leaf versions (non-''0xC0'') the execution must succeed.<ref>'''Why we need to success on future leaf version validation''' This is required to enable future leaf versions as soft forks</ref>. ''q'' is referred to as ''taproot output key'' and ''p'' as ''taproot internal key''. @@ -88,13 +88,13 @@ We first define a reusable common signature message calculation function, follow ==== Common signature message ==== -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 function ''SigMsg(hash_type, ext_flag)'' computes the common portion of 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 <code>SIGHASH</code> encodings from the legacy script system are reused, including <code>SIGHASH_ALL</code>, <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code>, and <code>SIGHASH_ANYONECANPAY</code>, plus the default ''hash_type'' value ''0x00'' which results in signing over the whole transaction just as for <code>SIGHASH_ALL</code>. The following restrictions apply, which cause validation failure if violated: +The parameter ''hash_type'' is an 8-bit unsigned value. The <code>SIGHASH</code> encodings from the legacy script system are reused, including <code>SIGHASH_ALL</code>, <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code>, and <code>SIGHASH_ANYONECANPAY</code>. We define a new ''hashtype'' <code>SIGHASH_DEFAULT</code> (value ''0x00'') which results in signing over the whole transaction just as for <code>SIGHASH_ALL</code>. The following restrictions apply, which cause validation failure if violated: * Using any undefined ''hash_type'' (not ''0x00'', ''0x01'', ''0x02'', ''0x03'', ''0x81'', ''0x82'', or ''0x83''<ref>'''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.</ref>). * Using <code>SIGHASH_SINGLE</code> 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 (in the message) that extensions are added at the end of the message<ref>'''What extensions use the ''ext_flag'' mechanism?''' [[bip-0342.mediawiki|BIP342]] reuses the same common signature message algorithm, but adds BIP342-specific data at the end, which is indicated using ''ext_flag = 1''.</ref>. +The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating (in the message) that extensions are appended to the output of ''SigMsg()''<ref>'''What extensions use the ''ext_flag'' mechanism?''' [[bip-0342.mediawiki#common-signature-message-extension|BIP342]] reuses the same common signature message algorithm, but adds BIP342-specific data at the end, which is indicated using ''ext_flag = 1''.</ref>. 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. @@ -106,7 +106,7 @@ If the parameters take acceptable values, the message is the concatenation of th ** 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 spent output amounts. -*** ''sha_scriptpubkeys'' (32): the SHA256 of the serialization of all spent output ''scriptPubKey''s. +*** ''sha_scriptpubkeys'' (32): the SHA256 of all spent outputs' ''scriptPubKeys'', serialized as script inside <code>CTxOut</code>. *** ''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. @@ -138,7 +138,7 @@ In summary, the semantics of the [[bip-0143.mediawiki|BIP143]] sighash types rem 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 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])''. +* 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>. == Constructing and spending Taproot outputs == @@ -167,7 +167,7 @@ Alice will not be able to notice the script path, but Mallory can unilaterally s </ref> * The remaining scripts should be organized into the leaves of a binary tree. This can be a balanced tree if each of the conditions these scripts correspond to are equally likely. If probabilities for each condition are known, consider constructing the tree as a Huffman tree. -'''Computing the output script''' Once the spending conditions are split into an internal key <code>internal_pubkey</code> and a binary tree whose leaves are (leaf_version, script) tuples, the output script can be computed using the Python3 algorithms below. These algorithms take advantage of helper functions from the [bip-0340/referency.py BIP340 reference code] for integer conversion, point multiplication, and tagged hashes. +'''Computing the output script''' Once the spending conditions are split into an internal key <code>internal_pubkey</code> and a binary tree whose leaves are (leaf_version, script) tuples, the output script can be computed using the Python3 algorithms below. These algorithms take advantage of helper functions from the [[bip-0340/reference.py|BIP340 reference code]] for integer conversion, point multiplication, and tagged hashes. First, we define <code>taproot_tweak_pubkey</code> for 32-byte [[bip-0340.mediawiki|BIP340]] public key arrays. The function returns a bit indicating the tweaked public key's Y coordinate as well as the public key byte array. @@ -175,21 +175,27 @@ 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)[1] == pubkey_gen(taproot_tweak_seckey(seckey, h))</code>. +Note that because tweaks are applied to 32-byte public keys, `taproot_tweak_seckey` may need to negate the secret key before applying the tweak. + <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(pubkey), point_mul(G, t)) + P = lift_x(int_from_bytes(pubkey)) + if P is None: + raise ValueError + Q = point_add(P, point_mul(G, t)) return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q)) def taproot_tweak_seckey(seckey0, h): - P = point_mul(G, int_from_bytes(seckey0)) + seckey0 = int_from_bytes(seckey0) + P = point_mul(G, seckey0) seckey = seckey0 if has_even_y(P) else SECP256K1_ORDER - seckey0 t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h)) if t >= SECP256K1_ORDER: raise ValueError - return (seckey + t) % SECP256K1_ORDER + return bytes_from_int((seckey + t) % SECP256K1_ORDER) </source> The following function, <code>taproot_output_script</code>, returns a byte array with the scriptPubKey (see [[bip-0141.mediawiki|BIP141]]). @@ -242,10 +248,13 @@ TapTweak = tagged_hash("TapTweak", p + ABCDE) '''Spending using the key path''' A Taproot output can be spent with the secret key corresponding to the <code>internal_pubkey</code>. To do so, a witness stack consists of a single element: a [[bip-0340.mediawiki|BIP340]] signature on the signature hash as defined above, with the secret key tweaked by the same <code>h</code> as in the above snippet. See the code below: <source lang="python"> -def taproot_sign_key(script_tree, internal_seckey, hash_type): - _, h = taproot_tree_helper(script_tree) +def taproot_sign_key(script_tree, internal_seckey, hash_type, bip340_aux_rand): + if script_tree is None: + h = bytes() + else: + _, h = taproot_tree_helper(script_tree) output_seckey = taproot_tweak_seckey(internal_seckey, h) - sig = schnorr_sign(sighash(hash_type), output_seckey) + sig = schnorr_sign(sighash(hash_type), output_seckey, bip340_aux_rand) if hash_type != 0: sig += bytes([hash_type]) return [sig] @@ -284,7 +293,13 @@ The reason for this is to increase leaf entropy and prevent an observer from lea == Test vectors == -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]. +Test vectors for wallet operation (scriptPubKey computation, key path spending, control block construction) can be found [[bip-0341/wallet-test-vectors.json|here]]. +It consists of two sets of vectors. +* The first "scriptPubKey" tests concern computing the scriptPubKey and (mainnet) BIP350 address given an internal public key, and a script tree. The script tree is encoded as <code>null</code> to represent no scripts, a JSON object to represent a leaf node, or a 2-element array to represent an inner node. The control blocks needed for script path spending are also provided for each of the script leaves. +* The second "keyPathSpending" tests consists of a list of test cases, each of which provides an unsigned transaction and the UTXOs it spends. For each of its BIP341 inputs, the internal private key and the Merkle root it was derived from is given, as well as the expected witness to spend it. All signatures are created with an all-zero (0x0000...0000) BIP340 auxiliary randomness array. +* In all cases, hexadecimal values represent byte arrays, not numbers. In particular, that means that provided hash values have the hex digits corresponding to the first bytes first. This differs from the convention used for txids and block hashes, where the hex strings represent numbers, resulting in a reversed order. + +Validation 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 == @@ -296,7 +311,7 @@ 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: +For Bitcoin mainnet and testnet3, these BIPs are 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) { @@ -326,9 +341,11 @@ For Bitcoin mainnet and testnet3, these BIPs will be deployed by "version bits" } 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 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. +The deployment did activate at height 709632 on Bitcoin mainnet. 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. +The deployment did activate at height 2011968 on Bitcoin testnet3. == Backwards compatibility == As a soft fork, older software will continue to operate without modification. @@ -340,6 +357,6 @@ Depending on the implementation non-upgraded wallets may be able to send to Segw == Acknowledgements == -This document is the result of discussions 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. +This document is the result of discussions 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 authors wish the 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 [https://github.com/ajtowns/taproot-review structured reviews]. |