0341 - Final - Standards - Jan. 19, 2020 (6 years, 6 months ago)
19
2020
BIP: 341
Layer: Consensus (soft fork)
Title: Taproot: SegWit version 1 spending rules
Author: Pieter Wuille <[email protected]>
Jonas Nick <[email protected]>
Anthony Towns <[email protected]>
Comments-Summary: No comments yet.
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP 341
Status: Final
Type: Standards Track
Created: 2020-01-19
License: BSD-3-Clause
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
Requires: 340
This document proposes a new SegWit version 1 output type, with spending rules based on Taproot, Schnorr signatures, and Merkle branches.
This document is licensed under the 3-clause BSD license.
This proposal aims to improve privacy, efficiency, and flexibility of Bitcoin's scripting capabilities without adding new security assumptions 1 . 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.
A number of related ideas for improving Bitcoin's scripting capabilities have been previously proposed: Schnorr signatures ( BIP 340 ), Merkle branches ("MAST", BIP 114 , BIP 117 ), new sighash modes ( BIP 118 ), 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:
annex
in the witness (see
Rationale
).
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.
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 BIP 340 . 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.
A Taproot output is a native SegWit output (see BIP 141 ) 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 3 , remain unencumbered.
q is referred to as taproot output key and p as taproot internal key .
We first define a reusable common signature message calculation function, followed by the actual signature validation as it's used in key path spending.
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
SIGHASH
encodings from the legacy script system are reused,
including
SIGHASH_ALL
,
SIGHASH_NONE
,
SIGHASH_SINGLE
, and
SIGHASH_ANYONECANPAY
. We
define a new
hashtype
SIGHASH_DEFAULT
(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:
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 appended to the output of SigMsg() 14 .
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.
SIGHASH_ANYONECANPAY
:
CTxOut
.
SIGHASH_NONE
or
SIGHASH_SINGLE
:
CTxOut
format.
SIGHASH_ANYONECANPAY
:
COutPoint
of this input
(32-byte hash + 4-byte little-endian).
CTxOut
. Its size is always 35 bytes.
SIGHASH_ANYONECANPAY
:
SIGHASH_SINGLE
:
CTxOut
format.
The total length of SigMsg() is at most 206 bytes 15 . 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 143 sighash types remain unchanged, except the following:
SIGHASH_ANYONECANPAY
flag is not
set, the message commits to the
scriptPubKey
s of
all
outputs spent by the transaction.
17
.
SIGHASH_ANYONECANPAY
flag is not set, the
message commits to the amounts of
all
transaction inputs.
18
SIGHASH_NONE
or
SIGHASH_SINGLE
are set (unless
SIGHASH_ANYONECANPAY
is set as well).
19
A Taproot signature is a 64-byte Schnorr signature, as defined in BIP 340 , with the sighash byte appended in the usual Bitcoin fashion. This sighash byte is optional. If omitted, the resulting signatures are 64 bytes, and a SIGHASH_DEFAULT mode is implied.
To validate a signature sig with public key q :
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:
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.
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. MuSig key aggregation does not have this issue because it already causes the internal key to be randomized.
The attack works as follows: Assume Alice and Mallory want to aggregate their keys into a taproot output key without a script path. In order to prevent key cancellation and related attacks they use MSDL-pop instead of MuSig. The MSDL-pop protocol requires all parties to provide a proof of possession of their corresponding secret key and the aggregated key is just the sum of the individual keys. After Mallory receives Alice's key A , Mallory creates M = M 0 + int(t)G where M 0 is Mallory's original key and t allows a script path spend with internal key P = A + M 0 and a script that only contains Mallory's key. Mallory sends a proof of possession of M to Alice and both parties compute output key Q = A + M = P + int(t)G . Alice will not be able to notice the script path, but Mallory can unilaterally spend any coin with output key Q .
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 340 reference code
for integer
conversion, point multiplication, and tagged hashes.
First, we define
taproot_tweak_pubkey
for 32-byte
BIP 340
public key arrays. 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
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)[1] == pubkey_gen(taproot_tweak_seckey(seckey, h))
.
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.
def taproot_tweak_pubkey(pubkey, h):
t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
if t >= SECP256K1_ORDER:
raise ValueError
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):
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 bytes_from_int((seckey + t) % SECP256K1_ORDER)
The following function,
taproot_output_script
, returns a
byte array with the scriptPubKey (see
BIP 141
).
ser_script
refers to a function that prefixes its input with a CompactSize-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|BIP 342]] 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
To spend this output using script D , the control block would contain the following data in this order:
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
BIP 340
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, 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, bip340_aux_rand)
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]
output_pubkey_y_parity, _ = taproot_tweak_pubkey(internal_pubkey, h)
pubkey_data = bytes([output_pubkey_y_parity + leaf_version]) + internal_pubkey
return inputs + [script, pubkey_data + path]
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 for wallet operation (scriptPubKey computation, key path spending, control block construction) can be found here . It consists of two sets of vectors.
null
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.
Validation test vectors used in the Bitcoin Core unit test framework can be found here .
This BIP is deployed concurrently with BIP 342 .
For Bitcoin signet, these BIPs are always active.
For Bitcoin mainnet and testnet3, these BIPs are deployed by "version bits" with the name "taproot" and bit 2, using BIP 9 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. 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.
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 BIP 350 Bech32m addresses.
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 .
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 parity of the
public key's Y coordinate, 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.
↩︎
annex
in transactions, or it may
lead to PERMANENT FUND LOSS.
↩︎
SIGHASH_ANYONECANPAY
is set) instead of setting them to
zero and then hashing them as in BIP 143. 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.
↩︎
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.
↩︎
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.
↩︎
hash_type
implicit, a byte
can often be saved.
↩︎