BIP 0341

This page describes a BIP (Bitcoin Improvement Proposal). Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

Please do not modify this page. This is a mirror of the BIP from the source Git repository here.

  BIP: 341
  Layer: Consensus (soft fork)
  Title: Taproot: SegWit version 1 spending rules
  Author: Pieter Wuille <pieter.wuille@gmail.com>
          Jonas Nick <jonasd.nick@gmail.com>
          Anthony Towns <aj@erisian.com.au>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0341
  Status: Draft
  Type: Standards Track
  Created: 2020-01-19
  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

Introduction

Abstract

This document proposes a new SegWit version 1 output type, with spending rules based on Taproot, Schnorr signatures, and Merkle branches.

Copyright

This document is licensed under the 3-clause BSD license.

Motivation

This proposal aims to improve privacy, efficiency, and flexibility of Bitcoin's scripting capabilities without adding new security assumptions. Specifically, it seeks to minimize how much information about the spendability conditions of a transaction output is revealed on chain at creation or spending time and to add a number of upgrade mechanisms, while fixing a few minor but long-standing issues.

Design

A number of related ideas for improving Bitcoin's scripting capabilities have been previously proposed: Schnorr signatures (BIP340), Merkle branches ("MAST", BIP114, BIP117), new sighash modes (BIP118), new opcodes like CHECKSIGFROMSTACK, Taproot, Graftroot, G'root, and cross-input aggregation.

Combining all these ideas in a single proposal would be an extensive change, be hard to review, and likely miss new discoveries that otherwise could have been made along the way. Not all are equally mature as well. For example, cross-input aggregation interacts in complex ways with upgrade mechanisms, and solutions to that are still in flux. On the other hand, separating them all into independent upgrades would reduce the efficiency and privacy gains to be had, and wallet and service providers may not be inclined to go through many incremental updates. Therefore, we're faced with a tradeoff between functionality and scope creep. In this design we strike a balance by focusing on the structural script improvements offered by Taproot and Merkle branches, as well as changes necessary to make them usable and efficient. For things like sighashes and opcodes we include fixes for known problems, but exclude new features that can be added independently with no downsides.

As a result we choose this combination of technologies:

• Merkle branches let us only reveal the actually executed part of the script to the blockchain, as opposed to all possible ways a script can be executed. Among the various known mechanisms for implementing this, one where the Merkle tree becomes part of the script's structure directly maximizes the space savings, so that approach is chosen.
• Taproot on top of that lets us merge the traditionally separate pay-to-pubkey and pay-to-scripthash policies, making all outputs spendable by either a key or (optionally) a script, and indistinguishable from each other. As long as the key-based spending path is used for spending, it is not revealed whether a script path was permitted as well, resulting in space savings and an increase in scripting privacy at spending time.
• 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 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 341. Additionally, future soft forks can make use of the currently unused annex in the witness (see BIP341).
• 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.

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.

Specification

This section specifies the Taproot consensus rules. Validity is defined by exclusion: a block or transaction is valid if no condition exists that marks it failed.

The notation below follows that of BIP340. This includes the hash_tag(x) notation to refer to SHA256(SHA256(tag) || SHA256(tag) || x). To the best of the authors' knowledge, no existing use of SHA256 in Bitcoin feeds it a message that starts with two single SHA256 outputs, making collisions between hash_tag with other hashes extremely unlikely.

Script validation rules

A Taproot output is a native SegWit output (see BIP141) with version number 1, and a 32-byte witness program. The following rules only apply when such an output is being spent. Any other outputs, including version 1 outputs with lengths other than 32 bytes, or P2SH-wrapped version 1 outputs, remain unencumbered.

• Let q be the 32-byte array containing the witness program (the second push in the scriptPubKey) which represents a public key according to BIP340.
• 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, this last element is called annex a 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 (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, inclusive. Fail if it does not have such a length.
  • Let p = c[1:33] and let P = point(p) where point 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.
  • Let k₀ = hash_TapLeaf(v || compact_size(size of s) || s); also call it the tapleaf hash.
  • For j in [0,1,...,m-1]:
    • Let e_j = c[33+32j:65+32j].
    • Let k_j+1 depend on whether k_j < e_j (lexicographically):
      • If k_j < e_j: k_j+1 = hash_TapBranch(k_j || e_j).
      • If k_j ≥ e_j: k_j+1 = hash_TapBranch(e_j || k_j).
  • Let t = hash_TapTweak(p || k_m).
  • If t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 (order of secp256k1), fail.
  • Let Q = point(q) if (c[0] & 1) = 1 and -point(q) otherwise. Fail if this point is not on the curve.
  • If Q ≠ P + int(t)G, fail.
  • Execute the script, according to the applicable script rules, using the witness stack elements excluding the script s, the control block c, and the annex a if present, as initial stack.

q is referred to as taproot output key and p as taproot internal key.

Signature validation rules

We first define a reusable common signature message calculation function, followed by the actual signature validation as it's used in key path spending.

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 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).
• 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 (in the message) that extensions are added at the end of the message.

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:
  • hash_type (1).
• Transaction data:
  • 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): 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 hash_type & 3 equals SIGHASH_SINGLE:
    • sha_single_output (32): the SHA256 of the corresponding output in CTxOut format.

The total length of SigMsg() is at most 209 bytes. 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 BIP143 sighash types remain unchanged, except the following:

1. The way and order of serialization is changed.
2. The signature message commits to the scriptPubKey.
3. If the SIGHASH_ANYONECANPAY flag is not set, the message commits to the amounts of all transaction inputs.
4. The signature message commits to all input nSequence if SIGHASH_NONE or SIGHASH_SINGLE are set (unless SIGHASH_ANYONECANPAY is set as well).
5. 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, hash_TapSigHash(0x00 || SigMsg(0x00, 0)), sig), where Verify is defined in BIP340.
• If the sig is 65 bytes long, return sig[64] ≠ 0x00 and Verify(q, hash_TapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64]).
• Otherwise, fail.

Constructing and spending Taproot outputs

This section discusses how to construct and spend Taproot outputs. It only affects wallet software that chooses to implement receiving and spending, and is not consensus critical in any way.

Conceptually, every Taproot output corresponds to a combination of a single public key condition (the internal key), and zero or more general conditions encoded in scripts organized in a tree. 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 (OP_IF 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 = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) which is constructed by taking the hash of the standard uncompressed encoding of the 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_TapTweak(bytes(P)))G.
• 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 internal_pubkey 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.

First, we define taproot_tweak_pubkey for 32-byte BIP340 public key arrays. In addition to the tweaked public key byte array, the function returns a boolean indicating whether the public key represents the tweaked point or its negation. This will be required for spending the output with a script path. In order to allow spending with the key path, we define taproot_tweak_seckey to compute the secret key for a tweaked public key. For any byte string h it holds that taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h)).

def taproot_tweak_pubkey(pubkey, h):
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    Q = point_add(point(pubkey), point_mul(G, t))
    is_negated = not has_square_y(Q)
    return bytes_from_int(x(Q)), is_negated

def taproot_tweak_seckey(seckey0, h):
    P = point_mul(G, int_from_bytes(seckey0))
    seckey = SECP256K1_ORDER - seckey0 if not has_square_y(P) else seckey
    t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    return (seckey + t) % SECP256K1_ORDER

The following function, taproot_output_script, returns a byte array with the scriptPubKey (see BIP141). ser_script refers to a function that prefixes its input with a CCompactSize-encoded length.

def taproot_tree_helper(script_tree):
    if isinstance(script_tree, tuple):
        leaf_version, script = script_tree
        h = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
        return ([((leaf_version, script), bytes())], h)
    left, left_h = taproot_tree_helper(script_tree[0])
    right, right_h = taproot_tree_helper(script_tree[1])
    ret = [(l, c + right_h) for l, c in left] + [(l, c + left_h) for l, c in right]
    if right_h < left_h:
        left_h, right_h = right_h, left_h
    return (ret, tagged_hash("TapBranch", left_h + right_h))

def taproot_output_script(internal_pubkey, script_tree):
    """Given a internal public key and a tree of scripts, compute the output script.
    script_tree is either:
     - a (leaf_version, script) tuple (leaf_version is 0xc0 for [[bip-0342.mediawiki|BIP342]] scripts)
     - a list of two elements, each with the same structure as script_tree itself
     - None
    """
    if script_tree is None:
        h = bytes()
    else:
        _, h = taproot_tree_helper(script_tree)
    output_pubkey, _ = taproot_tweak_pubkey(internal_pubkey, h)
    return bytes([0x51, 0x20]) + output_pubkey

File:Bip-0341/tree.png

This diagram shows the hashing structure to obtain the tweak from an internal key P and a Merkle tree consisting of 5 script leaves. A, B, C and E are TapLeaf hashes similar to D and AB is a TapBranch hash. Note that when CDE is computed E is hashed first because E is less than CD.

To spend this output using script D, the control block would contain the following data in this order:

    <control byte with leaf version and negation bit> <internal key p> <C> <E> <AB>

The TapTweak would then be computed as described above like so:

D = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
CD = tagged_hash("TapBranch", C + D)
CDE = tagged_hash("TapBranch", E + CD)
ABCDE = tagged_hash("TapBranch", AB + CDE)
TapTweak = tagged_hash("TapTweak", p + ABCDE)

Spending using the key path A Taproot output can be spent with the secret key corresponding to the internal_pubkey. To do so, a witness stack consists of a single element: a BIP340 signature on the signature hash as defined above, with the secret key tweaked by the same h as in the above snippet. See the code below:

def taproot_sign_key(script_tree, internal_seckey, hash_type):
    _, h = taproot_tree_helper(script_tree)
    output_seckey = taproot_tweak_seckey(internal_seckey, h)
    sig = schnorr_sign(sighash(hash_type), output_seckey)
    if hash_type != 0:
        sig += bytes([hash_type])
    return [sig]

This function returns the witness stack necessary and a sighash function to compute the signature hash as defined above (for simplicity, the snippet above ignores passing information like the transaction, the input position, ... to the sighashing code).

Spending using one of the scripts A Taproot output can be spent by satisfying any of the scripts used in its construction. To do so, a witness stack consisting of the script's inputs, plus the script itself and the control block are necessary. See the code below:

def taproot_sign_script(internal_pubkey, script_tree, script_num, inputs):
    info, h = taproot_tree_helper(script_tree)
    (leaf_version, script), path = info[script_num]
    _, is_negated = taproot_tweak_pubkey(internal_pubkey, h)
    output_pubkey_tag = 0 if is_negated else 1
    pubkey_data = bytes([output_pubkey_tag + leaf_version]) + internal_pubkey
    return inputs + [script, pubkey_data + path]

Security

Taproot improves the privacy of Bitcoin because instead of revealing all possible conditions for spending an output, only the satisfied spending condition has to be published. Ideally, outputs are spent using the key path which prevents observers from learning the spending conditions of a coin. A key path spend could be a "normal" payment from a single- or multi-signature wallet or the cooperative settlement of hidden multiparty contract.

A script path spend leaks that there is a script path and that the key path was not applicable - for example because the involved parties failed to reach agreement. Moreover, the depth of a script in the Merkle root leaks information including the minimum depth of the tree, which suggests specific wallet software that created the output and helps clustering. Therefore, the privacy of script spends can be improved by deviating from the optimal tree determined by the probability distribution over the leaves.

Just like other existing output types, taproot outputs should never reuse keys, for privacy reasons. This does not only apply to the particular leaf that was used to spend an output but to all leaves committed to in the output. If leaves were reused, it could happen that spending a different output would reuse the same Merkle branches in the Merkle proof. Using fresh keys implies that taproot output construction does not need to take special measures to randomizing leaf positions because they are already randomized due to the branch-sorting Merkle tree construction used in taproot. This does not avoid leaking information through the leaf depth and therefore only applies to balanced (sub-) trees. In addition, every leaf should have a set of keys distinct from every other leaf. The reason for this is to increase leaf entropy and prevent an observer from learning an undisclosed script using brute-force search.

Test vectors

Examples with creation transaction and spending transaction pairs, valid and invalid.

Examples of preimage for sighashing for each of the sighash modes.

Deployment

TODO

Backwards compatibility

As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will consider all SegWit version 1 witness programs as anyone-can-spend scripts. 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 BIP173 Bech32 addresses.

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.

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 structured reviews.