This is the second part of a two part blog post. Part 1 gives an overview of Bitcoin’s current signature scheme, an overview of Schnorr and Taproot, and an analysis of these upgrades from a miner’s perspective. Part 2 is a breakdown from a technical perspective so a reader can understand what this actually looks like under the hood. Here is a link to Part 1.
There are several excellent resources that explain Schnorr and Taproot under the Further Explorations section at the bottom of this post. In order to understand the benefits of these upgrades, it is useful to understand elliptic curve cryptography as it relates to ECDSA, Bitcoin’s current signature scheme. A basic overview of how public and private keys are generated, and why a Schnorr signature upgrade does not inhibit the use of current address generation methods (like HD Wallets) is presented. A single-script transaction is presented in its legacy SegWit v0 form (signed with ECDSA), and also in its new SegWit v1 form (signed with Schnorr). Then a more complex 2-of-2 multisig transaction is presented in both the legacy P2WSH form and then again using MuSig (a multisignature scheme that leverages Schnorr and Taproot). A comparison of the transaction weights shows that there is a substantial reduction in transaction size between the SegWit v0 and SegWit v1 transaction types.
Variables used throughout this blog post are defined in the following table.
G – generator point
point – scalar * G = (x, y)
d – private key
P – public key, P = dG
k – random nonce
R – random nonce point, R = kG
m – SHA256 of message being signed
e – SHA256(tag digest || R.x || P.x || m)
s – k + e * d
Sig – signing algorithm
Note: This post pulls a majority of the technical information from the Schnorr and Taproot BIPs( BIP340¹, BIP34², BIP34³), as well as the outstanding Bitcoin Optech Schnorr Taproot Workshop⁴.
Review of Bitcoin’s Cryptography
Elliptic Curve Cryptography
If you are familiar with ECDSA, ECC, and the SECP256K1 curve, this section can be skipped.
ECC multiplies large numbers together to combine points on a curve on a plane. There is a plane with a bunch of points (x, y) where x and y are scalars (integer numbers). The equation of the curve (just like any equation) dictates which of these points on the plane are on the curve. So if we have the equation for a curve that is a straight line y = 2, then the point (0, 2) is on the curve, but the point (0, 3) is not. Simple as that.
The below graph shows the curve (in this case a straight line) of y = 2 along with four points that are on the curve, (x = -1.75, y = 2), (x = 2, y = 2), (x = 5, y = 2), and (x = 9, y = 2), and one point (x = 2, y = 4) that is not.
y = 2, Real Numbers
The ECC curve used in Bitcoin only considers positive integer numbers. So the point (x = -1.75, y = 2) is also invalid.
y = 2, Integer Numbers
So far, no bounds have been defined for the curve y = 2, meaning that an the curve will span from [-∞, ∞]. In ECC as it relates to Bitcoin, however, the plane does have bounds set to be a very large prime number called a prime order denoted by p such that the bounds are [0, p]. Furthermore, the field is described as being a finite field 𝔽 over p, where p is a very large prime number. This means that an x value that is outside of the [0, p] range is still valid, it just wraps back around to the lower bound value.
Let’s look at an example of this wrapping by taking the simple y = 2 equation as a finite field over the prime number 7, and plot the same valid points as before: x = 2, x = 5, and x = 8. The points that lie on this curve are calculated by taking the modulus with respect to p = 7.
(x = 2, y = 2) -> x-coordinate = 2 % 7 = 2
(x = 5, y = 2) -> x-coordinate = 5 % 7 = 5
(x = 8, y = 2) -> x-coordinate = 8 % 7 = 1
Notice that when x = 8, the actual point that falls on the graph is at x = 1. This is visualized in the graph below.
y = 2 over 𝔽_p where p = 7
Now that we have established what it means for a point to be on a curve defined over a finite field 𝔽_p, let’s progress and examine the underlying curve of the ECC used in Bitcoin, the SECP256K1 curve.
There are many different types of curves that can be used in ECC. These curves are in what is called the Weierstrass form⁶, which is y² = x³ + ax + b, where a and b are constants that determine the shape of the curve. Bitcoin uses the SECP256K1 curve, which sets a = 0 and b = 7, resulting in the equation y² = x³ + 7. This curve, plotted using real numbers, is show in the graph below.
y² = x³ + 7, SECP256K1 Real Numbers
Now how is this curve used to generate the private and public key pair? This key pair must have some property the guarantees to a high degree of certainty that given a private key and the generator point, one can generate the public key, but if given a generator point and public key, one cannot “go back” and find the private key. This ability to easily compute a value in one direction, but not easily undo that computation in the reverse direction is done with what is referred to as a trapdoor function. In the case of ECC, this functionality is ensured because ECC primitives guarantee the ability to easily multiply numbers together, but make it essentially impossible to divide these numbers to get back to the original multiplicand.
To try an internalize this concept, we can consider the following example where we start with the generator point G on the SECP256K1 curve, then start adding G to itself a number of times (aka multiplying G incrementally).
Let’s plot a generator point on the SECP256K1 curve.
Generator point on the SECP256K1 Curve
Now lets calculate 2G by a method called Point Doubling. We take the tangent line with respect to G, find where the tangent line intersects the curve, then reflect that point across the x-axis to arrive at 2G.
2G on Example SECP256K1 Curve
Now a line is drawn from G to 2G, extending until it hits another location on the curve. Again, the reflection of this location across the x-axis is taken to be 3G.
3G on Example SECP256K1 Curve
To calculate 4G, again draw a line between G and 3G, find the intersection of that line on the curve, then mirror the point over the x-axis.
4G on Example SECP256K1 Curve
Now, if we know G and G’s multiplier, denoted as d, it is really easy to compute the final point. We ended at 4G in this example, so in this case the multiplier is 4 and the final point would be that x and y coordinate. But what if we placed a point on this graph represented by dG, where d is unknown? The only way to find d would be to iterate through a bunch of d’s until the final point dG was found.
dG on Example SECP256K1 Curve
In this case, where the prime order of the finite field is assumed to be small, it may not be so difficult to iterate through a small number of multipliers to find the point dG. But in the case where the prime order of the finite field is very large, the operation of dotting G with itself is done numerous times. Iterating through all these d’s in an attempt to find the d that got you to the final point on the curve would take so much time and computational power that it is infeasible to even try.
This is known as the ECC discrete log problem, and is what makes Bitcoin’s public key cryptography secure. The multiplier d is the private key, and the final point dG is the public key.
ECC is very useful because you are able to multiply points by each other, but because the curve is modulo p over a finite field, where p is chosen to be very large, it is considered to be impossible to divide (aka reverse this multiplication) if only the public key and generator point are known. This is where the Bitcoin signature scheme gets is cryptographic security from.
P(x, y) = d * G
The public generator point used in Bitcoin is comprised of very large x and y components.
G(x, y) =
The prime order p used in Bitcoin is also a very large prime.
p = 2²⁵⁶ – 2³² – 2⁹ – 2⁸ – 2⁷ – 2⁶ – 2⁴ – 1
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
This prime order defines the maximum length of a private key, which in decimal is a 77 digital number (very large).
The order number n of the generator point G defines the maximum number of points on the curve. It is also a very large prime number, but is slightly less than p⁵.
n = 2²⁵⁶ – 2³² – 977
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
There is one more thing that needs to be discussed before moving on. In practice, the SECP256K1 curve does not look like a smooth, well defined curve. Instead, as p increases (and remembering that this curve is defined only for integers not real numbers), the curve looks more like a cloud of points.
SECP256K1 curve over Finite Field F_p where p = 257
Elliptic Curve Digital Signature Algorithm (ECDSA)
Digital signatures are based on public key cryptography, also called asymmetric cryptography. First a key pair is generated (detailed above), then the private key is used to encrypt some secret message, m.
Digital signatures are used to sign over some message, m. This message can be anything, but in Bitcoin it is the transaction that a participant is trying to send.
The digital signature scheme currently used by Bitcoin is the Elliptic Curve Digital Signature Algorithm (ECDSA).
In order to generate the ECDSA signature over a message, which in the case of Bitcoin is parts of the transaction, we first need to generate a private key and public key pair with an associated address. Then we need to create a spending transaction from a UXTO under the addresses control (this assumes that the address already controls some UTXO).
SegWit V0 vs SegWit V1: Single Signer
Here we will show each example of a SegWit v0 transaction and a SegWit v1 transaction type for a single singer output. The signing process of both ECDSA are shown in full detail and the final transaction weights are compared. The resulting SegWit v0 transaction has a weight of 437, and the resulting SegWit v1 transaction has a weight of 349 (the same as the 2-of-2 MuSig SegWit v1 transaction shown below). That is almost a 10% reduction in transaction weight.
SegWit V0: Single Signer
This subsection presents the steps to generate an ECDSA signature over a SegWit v0 transaction that sends some bitcoin from one address to another with no complex conditions. It shows the details of the ECDSA signatures scheme. This is how Bitcoin currently works.
1. Generate a private key and public key pair.
d = 0xe6075ae177834de90e007bef0307965f8a5b796b064cd86b6ac943c7ab8f5fca
P = 0x02e650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d497569
2. Generate an associated address by taking the RIPEMD160 hash of the digest of the SHA256 hash of the public key. This is the witness program. The witness program along with the network version number (0x00 for SegWit v0) are then used to generate a bech32 encoded address. We will refer to this as the sending address.
3. In this example, the bitcoin will be sent from the address in step to to another address that is also underneath the control of the same key pair generated in step 2. Essentially we are just sending the bitcoin back to ourselves. We will refer to this as the receiving address.
4. A SegWit v0 unsigned transaction sending 1 bitcoin from the sending address to the receiving address is then built.
The version number is 0x01000000 for legacy transactions. The outpoint contains one input at the output index of 0.
There is one output that spends 50,000,000 satoshis (0.5 bitcoin). This output contains a locking script derived from the receiving address that ensures the output of this spending transactions will only be able to be consumed by the participant who controls the keys to the receiving address. The locking script is prepended with its length byte.
The final unsigned spending transaction is created.
A complete break down is given below.
01000000 – version number
01 – number of inputs
afb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada – previous txid
00000000 – previous output index
00 – legacy signature placeholder
00000000 – sequence number
01 – number of outputs
80f0fa0200000000 – amount, 50,000,000 sats = 0.5 bitcoin 1600140e6a5ae16b91296707c28ef5d0836f04667bdae3 – locking script
00000000 – locktime
Again, this is the transaction our ECDSA signature will commit to.
5. z is derived from the SegWit v0 sighash of the unspent transaction. The sighash is the digest of the SHA256 of several parts of the transaction and the sighash type (in this case SIGHASH_ALL).
The locking script must first be derived from the witness program that was created above.
witness program = pubkey hash = 0x73cdfd7a167d66344cc0aa308132a7fde17d7054P2PKH locking script = [ OP_DUP, OP_HASH160, witness program, OP_EQUALVERIFY, OP_CHECKSIG ]P2PKH locking script = 76a91473cdfd7a167d66344cc0aa308132a7fde17d705488ac
Now we have all the components to generate the sighash, which is the z value in the ECDSA signature algorithm we are trying to create. This is the message (transaction) we are committing to.
nVersion = 0x01000000
outpoint = 0xafb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada00000000
nSequence = 0x00000000
lockingScript = 0x76a91473cdfd7a167d66344cc0aa308132a7fde17d705488ac
amount = 0x00e1f50500000000 (100,000,000 sats = 1 bitcoin)SHA256(outpoint) = SHA256( 0xafb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada || 0x00000000 ) = 0x7544688d2df453bd49836f034e3eb36ed3e410a0578019
310f2d58282693a6baSHA256(nSequence) = SHA256(0x00000000) = 0xb90ca5b5653eabdc3341c6f96b3b80689cdd1bd6870265
adfe17c8172501b98cSHA256(txouts) = SHA256() = 0x85daff2e158d437f078d3c9289c86a2b037e67cf68e6eb994f3113ba0f0831b0SIGHASH_FLAG = SIGHASH_ALL = 0x01000000z = sighash = SHA256(
nVersion || SHA256(outpoint) || SHA256(nSequence) || outpoint || lockingScript || amount || nSequence || SHA256(txouts) || nLockTime || SIGHASH_FLAG)z = sighash = SHA256(0x01000000 || SHA256(0xafb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada || 0x00000000 ) || SHA256(0x00000000) || (0xafb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada || 0x00000000) || 0x76a91473cdfd7a167d66344cc0aa308132a7fde17d705488ac || 0x00e1f50500000000 || 0x00000000 || 0x85daff2e158d437f078d3c9289c86a2b037e67cf68e6eb994f3113ba0f0831b0)z = sighash = SHA256( 01000000baa6932628582d0f31198057a010e4d36eb33e4e036f8349bd53f42d8d6844758cb9012517c817fead650287d61bdd9c68803b6bf9c64133dcab3e65b5a50cb9afb466816ddcf2003bcc64a73b4c3ce627d5af42dd1654b8c4e35e894db73ada000000001976a91473cdfd7a167d66344cc0aa308132a7fde17d705488ac00e1f5050000000000000000b031080fba13314f99ebe668cf677e032b6ac889923c8d077f438d152effda850000000001000000)z = sighash = 0x28b67faf17c13ced9f2ccf2acd3ee28ebd5c2bc9adb9634073e3336cf2a41141
6. Now the actual ECDSA signing takes place. The signature proof definition we are trying to create is repeated again for convenience.
s = k⁻¹ * (z + r * d) mod n
Generate another random private key, k, with in the range [1, n]. This is an ephemeral private key. Then generate the associated public key point, R.
k = 0x7925f65c88fc66ee2fecfd4d8f678d4706762e5300023902af006345a9aec9f3R = (R.x, R.y) = (0x4f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b, 0x60fa3861fc04dac9054398e79407afb088c0aaf8be7e78484a7756319197065d)
The r value used in the ECDSA Signature proof is the x-coordinate of the public key R mod n.
r = R.x mod n = 0x4f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b mod 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141r = 0x4f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b
The k⁻¹ is the modular inverse of k mod n.¹⁴
k⁻¹ = 0x14ec7a2f5f095cb2b83cb22f852876ba810ce9c84c162ebcd02e2308efb8c755
Now we have everything we need to satisfy the ECDSA signature proof.
s = k⁻¹ * (z + r * d) mod ns = 0x14ec7a2f5f095cb2b83cb22f852876ba810ce9c84c162ebcd02e2308efb8c755 * (0x28b67faf17c13ced9f2ccf2acd3ee28ebd5c2bc9adb9634073e3336cf2a41141 + 0x4f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b ) mod 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141s = 0x68ad1571330a5cbcfd0746702a092233c05aa3232fad8059acce0f8ff687cf8e
7. The final step is to encode the ECDSA signature using the DER encoding format.
0x30 – DER sequence indicator
0x45 – byte length of the sequence (69 bytes)
0x02 – indicates that the next value is an integer
0x21 – byte length of integer (33 bytes)
r – random nonce point
0x02 – indicates that the next value is an integer
0x20 – byte length of integer (32 bytes)
s – signature proof
SF – SIGHASH flag (1 byte)
Using this key, the final DER encoded signature is found.
0x4f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b – r
0x68ad1571330a5cbcfd0746702a092233c05aa3232fad8059acce0f8ff687cf8e – s
0x01 – SIGHASH_ALLSig = 0x304402204f0c7a2ed699f37346edb7e10a7d9978b94b6623c3b844e6c5208ddac998933b022068ad1571330a5cbcfd0746702a092233c05aa3232fad8059acce0f8ff687cf8e01
The final signed transaction is now complete.
The transaction weight of this SegWit v0 transaction is 437. In the proceeding section, we will reconstruct this transaction in the SegWit v1 format using Schnorr signatures and Taproot and then compare the weight of the resulting transaction.
SegWit V1: Single Signer
We just saw that to authenticate transactions, Bitcoin currently uses ECDSA signatures over the SECP256K1 curve with SHA256 hashes. Under the hood, Schnorr scheme implemented in BIP34⁰¹ still uses the same ECC as ECDSA does. This means that the same SECP256K1 curve is used and those rules still apply. This is very nice because this means the same private key can be used to generate both ECDSA and Schnorr signatures. It also means that wallet technologies like the hierarchical deterministic wallet scheme detailed in BIP32 are still applicable when signing with a Schnorr signature.
The concept of signing with a Schnorr signature is similar to that of ECDSA. The private key, private nonce, generator point, random nonce point, and public key are all the same.
The Schnorr signature proof is
s = k + e * d
where e = SHA256(R || P || m)
Let’s walk through the steps of the Schnorr signature scheme using the same transaction setup as the above ECDSA signature example. However instead of using the SegWit v0 format, we will use the new SegWit v1 format.
1. Generate a random private key with an associated public key. The same key pair that was used in the ECDSA example above.
privkey, d: 0xe6075ae177834de90e007bef0307965f8a5b796b064cd86b6ac943c7ab8f5fca
pubkey, P: 0x02e650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d497569
Check that the public key is the quadratic residue modulo the field size by using the Jacobi Symbol⁸. If it is not, negate the public key. This is done to avoid having to include the y component of the random nonce point R in the signature. By requiring the verifier to do this check, we avoid having to include the y component of the random nonce point R in the signature, thereby reducing the signature size from 96-bytes to 64-bytes. Essentially it provides a standard way for the verifier to obtain the y component independently. There are other methods besides checking the quadratic residue modulo the field size, but this method is the most efficient.
In this case, the public key is the quadratic residue modulo the field size, so we do not negate.
2. Derive the associated bech32 SegWit encoded spending address using the witness program. The witness program for SegWit v1 transactions is simply the 32-byte x-coordinate of the public key (removing the 0x02 prepended byte). It is no longer the RIPEMD160 of the SHA256 public key as in SegWit v0.
witness program = 0xe650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d497569
The sending address is a bech32 encoded address derived from the SegWit v1 version (0x01) and the witness program.
3. In this example, as in the ECDSA signing example, the bitcoin will be sent from the address in step 2 to another address that is also under the control of the same key pair generated in step 1. Essentially we are just sending the bitcoin back to ourselves. We will refer to this as the receiving address.
4. A SegWit v1 unsigned transaction sending 1 bitcoin from the sending address to the receiving address is then built.
A complete break down is given below.
0x01000000 – version number
0x01 – number of inputs
0x04d67fc6da833dc7d6eb44137ec2034cf655eadd210cc7d84f604257b1c640fb – previous txid
0x00000000 – previous output index
0x00 – legacy signature placeholder
0x00000000 – sequence number
0x01 – number of outputs
0x80f0fa0200000000 – amount, 50,000,000 sats = 0.5 bitcoin
0x160014a7c327071318b12193ddbe5c0b14fada6592df87 – locking script
0x00000000 – locktime
Again, this is the transaction our Schnorr signature will commit to.
5. In order to determine e, we need the SegWit v1 sighash (aka the Taproot sighash) of the unspent transaction.
Transaction with UTXO we are consuming is listed below.
01210240cecf455225bf42ffd09cdfb8ca6aea29c57dfcdf11453b065129a46a7fa16500000000locking script of UTXO being consumed: 0x225120e650125
The sighash is found by taking the tagged hash of the term TapSighash along with the concatenation of different parts of the transaction.
Taproot introduces a new sighash flag, SIGHASH_ALL_TAPROOT.
0x01 – SIGHASH_ALL
0x02 – SIGHASH_NONE
0x03 – SIGHASH_SINGLE
0x81 – SIGHASH_ALL | SIGHASH_ANYONECANPAY
0x82 – SIGHASH_NONE | SIGHASH_ANYONECANPAY
0x83 – SIGHASH_SINGLE | SIGHASH_ANYONECANPAY
0x00 – SIGHASH_ALL_TAPROOT
This sighash has the same semantics as the 0x01 SIGHASH_ALL, but instead of having to include this byte, it is simply implied. So the signature of a taproot transaction is assumed to have a SIGHASH_ALL sighash, unless a different sighash is specified.
sighash = Tagged Hash( “TapSighash”,
0x00 || SIGHASH_ALL_TAPROOT || nVersion || nLockTime || SHA256(outpoint) || SHA256(amount) || SHA256(nSequence) || SHA256(txout) || SPEND_TYPE || locking scrpt of UTXO being consumed || prevIndex )sighash = Tagged Hash(“TapSighash”, 0x00 || 0x00 || 0x01000000 || 0x00000000 || SHA256(0x04d67fc6da833dc7d6eb44137ec2034cf655eadd210cc7d84f604257b1c640fb || 0x00000000) || SHA256(0x80f0fa0200000000) || SHA256(0x00000000) || SHA256(80f0fa020000000
0160014a7c327071318b12193ddbe5c0b14fada6592df87) || 0x00 || 0x225120e650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d497569 || 0x00000000)sighash = Tagged Hash(“TapSighash”, 00000100000000000000342803b540671e08fbc1452d83d80eef3a88c0894dbba6cb52764a950f6b86e12c3417ea6a6d07f4a0218f5b1d380037c8b95c24eeb4e70299776a634a0dffa2df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b8111997baae7ecdb0eee1e5e66b27a0dd8562a70fda6768f9ef570a6584d0096779f800225120e650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d49756900000000)sighash = 0xb09f298288a1656c160c31d3d7445404bfa6a838bf53f1ca486ec1bc4241a43c
6. Now the actual Schnorr signing takes place. The signature proof definition we are trying to create is repeated again for convenience.
s = k + e * d
To deterministically generate the random nonce value k, first the bytes that generate k is derived using a tagged hash of the term BIPSchnorrDerive and the concatenation of the private key d and the message (sighash). These bytes are called the nonce bytes.
nonce_bytes = Tagged Hash(“BIPSchnorrDerive”, d || sighash)nonce_bytes = Tagged Hash(“BIPSchnorrDerive”, 0xe6075ae177834de90e007bef0307965f8a5b796b064cd86b6ac943c7ab8f5fca || 0xb09f298288a1656c160c31d3d7445404bfa6a838bf53f1ca486ec1bc4241a43c)nonce_bytes = 0x70603f193eeb790b0c8c40a9536f7161314d1b30ad1dcebc5c7db88eca1871e6
The nonce bytes are taken modulo the order n, we will call this k’.
k’ = nonce_bytes % n
k’ = 0x70603f193eeb790b0c8c40a9536f7161314d1b30ad1dcebc5c7db88eca1871e6 % 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
k’ = 0x70603f193eeb790b0c8c40a9536f7161314d1b30ad1dcebc5
k’ is used to generate a public key which is the associated nonce point, R.
R = (0x50ed3e867619db28fa917c8b6b86912fa68c9140b8dda1ce864c796b918fad36, 0xeedb98506fba05feb5c1606b015594c1d2d9227c2874a2e0ff421fb3957627ee)
Check that R.y is the quadratic residue modulo the field size by using the Jacobi Symbol⁷. If it is, then set k equal to k’. If it is not, negate k. In this example, R.y is the not quadratic residue modulo the field size, so k is negated.
k = n – k’
k = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 – 0x70603f193eeb790b0c8c40a9536f7161314d1b30ad1dcebc5c7db88eca1871e6
k = 0x8f9fc0e6c11486f4f373bf56ac908e9d8961c1b6022ad17f6354a5fe061dcf5b
e is derived by taking the tagged hash of the term BIPSchnorr and the concatenation of the x-component of the nonce point R.x, the x-component of the public key P.x, and the message (sighash).
e = tagged hash(BIPSchnorr, R.x || P.x || sighash)
e = tagged hash(BIPSchnorr, 0x50ed3e867619db28fa917c8b6b86912fa68c9140b8dda1ce864c796b918fad36 || 0x02e650125312253b7f53659637619f264d8f0b7d750075a9d8ec9533671d497569 || 0xb09f298288a1656c160c31d3d7445404bfa6a838bf53f1ca486ec1bc4241a43c)
e = 0xa7eb946b6b143a8419445e87c3ef24bb541e3098e84c90a6b2b21e51b79f2518
Now we have everything we need to satisfy the ECDSA signature proof.
s = k + e * d mod n
s = 0x8f9fc0e6c11486f4f373bf56ac908e9d8961c1b6022ad17f6354a5fe061dcf5b + 0xa7eb946b6b143a8419445e87c3ef24bb541e3098e84c90a6b2b21e51b79f2518 * 0xe6075ae177834de90e007bef0307965f8a5b796b064cd86b6ac943c7ab8f5fca % 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
s = 0x50ed3e867619db28fa917c8b6b86912fa68c9140b8dda1ce864c796b918fad36bbf1edd482f1edf878f88e51fc9ede51cc732e7d3df2c4146a746208701251ce
The final signed transaction can now be created.
The transaction weight is 396 vbytes.
Comparing this to the transaction weight of the SegWit v0 single script transaction of 437, we see nearly a 10% reduction in transaction weight.
2-of-2 P2WSH vs 2-of-2 MuSig
The Bitcoin Optech Taproot Workshop gives an excellent example detailing a 2-of-2 MuSig transaction which highlights the benefits of using MuSig over a traditional P2WSH 2-of-2 multisig.⁸
Here we will show each example in full detail and compare the final transaction weights. The resulting 2-of-2 P2WSH has a weight of 549, and the resulting 2-of-2 MuSig transaction has a weight of 349 (the same as the single signer SegWit v1 transaction shown above). That is almost a 28% reduction in transaction weight.
1. A 2-of-2 P2WSH output and address are generated. To do this, two private key and public key pairs are generated, followed by a multisig spending script. The SHA256 hash of this script is the witness program and is used along with the legacy version 0x00 to generate the bech32 encoded sending address.
d1 = 0x2876e4fadeece50216d855e3815ce3ccc77b97d0e023abf5d2527183c30759d6
P1 = 0x0273e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0edd2 = 0x32ba129753cb36df53626da1d89a5026ed5e13a71de71eace95850d97f189f3f
P2 = 0x02ed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5emultisig script = [OP_2, P1, P2, OP_2, OP_CHECKMULTISIG]
multisig script = 52210273e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0ed2102ed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e52aeprogram = SHA256(multisig script)
program = SHA256(52210273e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0ed2102ed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e52ae)
program = 0x62bdb00923ba58c766b4399bdc8e42e5aaa6e8e26b1a4022fc4498a93f39b824bech32 address = bcrt1qv27mqzfrhfvvwe458xdaerjzuk42d68zdvdyqghugjv2j0eehqjq68lm9r
One bitcoin is sent to this address in the following SegWit v0 transaction
The txid of this transaction is 0xd0faa3906f521839670df16adb1824b87e07e31d75f82757aeb675f1d80e02de.
2. The bech32 encoded receiving address is generated from the same key pair.
3. Now generate the unsigned SegWit v0 spending transaction that consumes the previous transaction’s UTXO and sends 0.5 bitcoin from the sending address to the receiving address.
4. The SegWit v0 sighash of this unspent transaction is generated.
5. Two ECDSA signatures are generated using the two private key and public key pairs listed in step 1.
sig1 = 30440220311f0ea149bc953e7f5b7f60aca0e2fad3816dd286d98dca4a0a649ffd686fb60220103ea52d3f3c5c11a67fd5afb33a7447b7f76bebd19f9ac67a01bfcd786f5a0901sig2 = 3045022100d1d291d247ce598fba05b3b523c05297b5b4dcdc51d1a141612c0832048a0d5902202f97bbf7a7f3976c609d9dadf77fcc9
6. The witnesses is constructed from the two signatures and the multisig script.
witness = sig1, sig2, multisig scriptwitness = 30440220311f0ea149bc953e7f5b7f60aca0e2fad3816dd286d98dca4a0a649ffd686fb60220103ea52d3f3c5c11a67fd5afb33a7447b7f76bebd19f9ac67a01bfcd786f5a0901,3045022100d1d291d247ce598fba05b3b523c05297b5b4dcdc51d1a141612c0832048a0d5902202f97bbf7a7f3976c609d9dadf77fcc93bd2b01bd2b8949d6d269c85216ad791201,52210273e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0ed2102ed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e52ae
7. The SegWit v0 spending transaction can now be signed.
The transaction weight of this SegWit v0 transaction is 549. In the proceeding section, we will reconstruct this transaction in the SegWit v1 format using aggregate Schnorr signatures and then compare the weight of the resulting transaction.
1. The same private key and public key pairs used in the above example are used again here. These keys are again used to generate the same multisig script, witness program, and bech32 encoded sending address.
d1 = 0x2876e4fadeece50216d855e3815ce3ccc77b97d0e023abf5d2527183c30759d6
P1 = 0x0273e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0edd2 = 0x32ba129753cb36df53626da1d89a5026ed5e13a71de71eace95850d97f189f3f
P2 = 0x02ed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e
2. To prevent against related key attacks, each of the public keys are tweaked by a challenge factor c that is related to all of the public keys but still unique for each participant. Each participant calculates their own challenge factor by hashing all of the public keys together, concatenating that hash with their individual public key, and then taking the SHA256 hash of that result. Once we have the challenge factor for each public key, and aggregate public key can be made and an address is generated from that.
This challenge factor must be created by each participant in a deterministic way, meaning the order of the public keys that are initially hashed together must be in the same. To make sure this is possible, the public keys are first stripped of their 0x02 or 0x03 prefix and then sorted in order from smallest to largest (remember the public key is just a number). Once they are sorted, they are concatenated and the SHA256 hash is taken, let’s call the list of hashesLh, and then the challenge factor can then be derived for each participant.
Lh = SHA256(P1 || P2)
Lh = SHA256(73e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0eded714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e)
Lh = 0x62f6d67ea8270a2ff1e1a84596a500b8caf0128d3ff2bd78e9bea4ff66e31dd4
For each public key in the sorted public key list, a challenge factor, c, is calculated to be the digest of Lh concatenated with the respective public key (without the 0x02 or 0x03 prepended byte).
c₁ = SHA256(Lh || P₁)
c₁ = SHA256( 0x62f6d67ea8270a2ff1e1a84596a500b8caf0128d3ff2bd78e9bea4ff66e31dd4 || 0x73e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0ed)
c₁ = 0xecce388649143900eb4f2b107fcbde7d240336b7f4ad5c37c987701c0eb9159bc₂ = SHA256(Lh + P₂)
c₂ = SHA256( 0x62f6d67ea8270a2ff1e1a84596a500b8caf0128d3ff2bd78e9bea4ff66e31dd4 || 0xed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e)
c₂ = 0x2b9449f654043b1920e5e17d89bf20d9e6e3e449b2f49122621b18d7756a495d
To create the aggregate public key, each public key is first multiplied with its challenge factor. This multiplication step is known as tweaking the public key. The tweaked public keys, denoted as P₁’ and P₂’, are then are added together and the resulting sum is the aggregate public key P’. If the resulting aggregate public key is a negative number, then it is negated along with each challenge factor. The aggregate public key show here is positive so it is not negated.
P₁’ = P₁ * c₁
P₁’ = 0x73e7ab3bcbd3194f01f9a60468cafc557d29043c3d230c98c57107e366ebd0ed * 0xecce388649143900eb4f2b107fcbde7d240336b7f4ad5c37c987701c0eb9159b
P₁’ = 0x031601087da98f7b3afe201984821727f55cc3176278dbcbb1eabbbeb5695da454P₂’ = P₂ * c₂
P₂’ = 0xed714a5d314dc046d39e07966425d7615c18e4dc787eccd963109308f9b34e5e * 0x2b9449f654043b1920e5e17d89bf20d9e6e3e449b2f49122621b18d7756a495d
P₂’ = 0x029294b0c19c018d1495339476a1901b16799c2d00eb7e6b96e85716bab5067348P = P₁’ + P₂’P = 0x1601087da98f7b3afe201984821727f55cc3176278dbcbb1eabbbeb5695da454 + 0x9294b0c19c018d1495339476a1901b16799c2d00eb7e6b96e85716bab5067348P = 0x03f2fe19e10684956111438fa7c69f953e91206d12553b8d898a7e0c43b8a93663
Since we created this aggregated public key from public keys tweaked by their respective challenge factor, in order for the private keys to be valid, they must also be tweaked by this same factor.
d₁’ = d₁ * c₁
d₁’ = 0x2876e4fadeece50216d855e3815ce3ccc77b97d0e023abf5d2527183c30759d6 * 0xecce388649143900eb4f2b107fcbde7d240336b7f4ad5c37c987701c0eb9159b
d₁’ = 0x07cd6d2b4ab956d89bbdf36d6a2b8e27023042ea173f786a9cd86bcdc8cab1dcd₂’ = d₂ * c₂
d₂’ = 0x32ba129753cb36df53626da1d89a5026ed5e13a71de71eace95850d97f189f3f * 0x2b9449f654043b1920e5e17d89bf20d9e6e3e449b2f49122621b18d7756a495d
d₂’ = 0xb05127d427a5422eb473ea9f90622acbebd5d87065aef83fc5d7e4e93a94ac23
The witness program is again the x-coordinate of the public key, only here we use the aggregate public key.
witness program = P.x’
witness program = 0xf2fe19e10684956111438fa7c69f953e91206d12553b8d898a7e0c43b8a93663
The bech32 encoded SegWit v1 sending address for the MuSig aggregate public key can now be derived using the witness program and the SegWit v1 version (0x01).
3. The receiving address is generated from the the aggregate public key.
4. The unsigned spending transaction that sends 0.5 bitcoin from the sending address to the receiving address can now be created.
5. The SegWit v1 sighash of this unspent transaction is created in the same way as step 5 in the SegWit V1: Single Signer section above.
sighash = 0xab73194e488ee26cf6dd58d2be4b40f969b5647f902e6be19688db491f1959c6
This is derived in part by using the locking script of the previous transaction that contains the UTXO we are consuming.
locking script of UTXO being consumed 225120f2fe19e10684956111438fa7c69f953e91206d12553b8d898a7e0c43b8a93663
6. The multisig Schnorr signature proof is the same as a single Schnorr signature proof, only the aggregated values are used.
s’ = k’ + e * d’ mod n
The nonce values are each a random private key whose corresponding public key is the nonce point. If the y-component of the public key is not the quadratic residue modulo the field size by using the Jacobi Symbol, set k equal to the difference between the order n and k.
k₁ = 0x43ae27db41923ba9268683ba53feaa517eabec8b5db62a1612045656dbf64744
R₁ = (0xb642edebb19b616054e945b8dfb9a215dbe56ecaa869cebf0c97c368db35ed48, 0x6a3bf699a3f17b7007ad8f14349270df6b63007ac4ee585104e9af5e9dc9377a)k₂ = 0x5a7dc060ae2a65a22ddc9e5d10b6b51ee588d0a6c8436014ebc4bae0a4ddb023
R₂ = (0x95c86d7887190be800d05cba00fd44b9805daf7e6eb39a1811a7aa3cccb3c743, 0xef833128e30b2a06eadb6c86ce1e63c150af91fe171a8bfe5e979db83da5355c)
In both cases of k in this example, k is negated. So we update both nonce points.
k₁ = n – k₁
k₁ = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141- 0x43ae27db41923ba9268683ba53feaa517eabec8b5db62a1612045656dbf64744
k₁ = 0xbc51d824be6dc456d9797c45ac0155ad3c02f05b51927625adce0835f43ff9fdk₂ = n – k₂
k₂ = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141-0x5a7dc060ae2a65a22ddc9e5d10b6b51ee588d0a6c8436014ebc4bae0a4ddb023
k₂ = 0xa5823f9f51d59a5dd22361a2ef494adfd5260c3fe7054026d40da3ac2b58911e
The final nonce value and nonce point (x-component only with the 0x03 byte prepended) key pairs are generated.
k₁ = 0xbc51d824be6dc456d9797c45ac0155ad3c02f05b51927625adce0835f43ff9fd
R₁ = 0x03b642edebb19b616054e945b8dfb9a215dbe56ecaa869cebf0c97c368db35ed48k₂ = 0xa5823f9f51d59a5dd22361a2ef494adfd5260c3fe7054026d40da3ac2b58911e
R₂ = 0x0395c86d7887190be800d05cba00fd44b9805daf7e6eb39a1811a7aa3cccb3c743
Now that both nonce values and nonce points are found, the aggregate nonce value and nonce point can be generated.
The aggregate nonce point R’ is the sum of the x-components of the nonce points. Check that the y-component of the aggregated nonce point is not the quadratic residue modulo the field size by using the Jacobi Symbol. If it is, negate R’ and both nonce values k₁ and k₂. In this case, the negation is not necessary.
R’ = k₁ + k₂
R’ = 0x03b642edebb19b616054e945b8dfb9a215dbe56ecaa869cebf0c97c368db35ed48 + 0x0395c86d7887190be800d05cba00fd44b9805daf7e6eb39a1811a7aa3cccb3c743
R’ = 0x02338b807352528dc74d83bb717f5560ef34f8c94b340f4867d0129a2107e228a7
e is derived from the tagged hash of the term BIPSchnorr, concatenated with the sum of the x-component of the aggregated nonce point R’.x, the x-component of the aggregated public key P’.x, and the message (sighash).
e = tagged hash(BIPSchnorr || R’.x + P’.x + sighash)
e = 0x8d507fb1955660ee2180917046f767d2c2a174a497348268a8af0aed2c7dd9f7
Now we have everything we need to satisfy the Schnorr signature proof for each participant.
s’₁ = k₁ + e * d’₁ mod n
s’₁ = 0xbc51d824be6dc456d9797c45ac0155ad3c02f05b51927625adce0835f43ff9fd + 0x8d507fb1955660ee2180917046f767d2c2a174a497348268a8af0aed2c7dd9f7 * 0x07cd6d2b4ab956d89bbdf36d6a2b8e27023042ea173f786a9cd86bcdc8cab1dc
s’₁ = 0xfe37255454d8e26b4ff666b93f36588522c796ac2e3e45c7cd4a6699120cae09s’₂ = k₂ + e * d’₂ mod n
s’₂ = 0xa5823f9f51d59a5dd22361a2ef494adfd5260c3fe7054026d40da3ac2b58911e + 0x8d507fb1955660ee2180917046f767d2c2a174a497348268a8af0aed2c7dd9f7 * 0xb05127d427a5422eb473ea9f90622acbebd5d87065aef83fc5d7e4e93a94ac23
s’₂ = 0xfe37255454d8e26b4ff666b93f36588522c796ac2e3e45c7cd4a6699120cae09
Finally, we create aggregate each participants signatures and the aggregate public key to compute the final signature.
s’ = s’₁ + s’₂ mod n
s’ = 0xfe37255454d8e26b4ff666b93f36588522c796ac2e3e45c7cd4a6699120cae09 + 0xfe37255454d8e26b4ff666b93f36588522c796ac2e3e45c7cd4a6699120cae09 mod 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
s’ = 0xc77d4dad11f338b0e05f76b67dfa06b769d12572160adc45767172673d242493sig’ = R’.x || s’
sig’ = 338b807352528dc74d83bb717f5560ef34f8c94b340f4867d0129a2107e228a7c77d4dad11f338b0e05f76b67dfa06b769d12572160adc45767172673d242493
The final signed transaction can now be created.
The transaction weight of this 2-of-2 SegWit v1 MuSig transaction is 396.
Comparing this to the transaction weight of the SegWit v0 2-of-2 P2WSH transaction of 549, we see nearly a 28% reduction in transaction weight.
Also notice both the single script and MuSig SegWit v1 transactions have the same weight.
The Bitcoin Optech Schnorr/Taproot workshop is a great resource for learning more and playing around with the signatures and transactions. The most up to date branch is the 32-bytes-keys branch. Clone it locally along with the bitcoin branch Taproot_V0.1.5-proposed. Build on that branch and make sure the wallet is enabled.Bitcoin Optech: TaprootMurch’s 2-of-3 inputs using Pay-to-TaprootBitcoin Technology Development Talks: Schnorr signatures
Special thanks to Valentine Wallace, Mark Erhardt, Carl Dong, and Harry Sudock for all their feedback.
: Pieter Wuille, Jonas Nick, Tim Ruffing. (January 19, 2020). Schnorr Signatures for secp256k1. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki.
: Pieter Wuille, Jonas Nick, Anthony Towns. (January 19, 2020).Taproot: SegWit version 1 spending rules. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki.
: Pieter Wuille, Jonas Nick, Anthony Towns. (January 19, 2020). Validation of Taproot Scripts. https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki.
: Bitcoin Optech. (October 29, 2019). Bitcoin Optech Schnorr Taproot Workshop. https://bitcoinops.org/en/schorr-taproot-workshop/.
: Bitcoin Wiki. (April 24, 2019). Secp256k1. https://en.bitcoin.it/wiki/Secp256k1.
: Wolfram MathWold. (2021). Weierstrass Form. https://mathworld.wolfram.com/WeierstrassForm.html.
: Wikipedia. (February 19, 2021). Jacobi symbol. https://en.wikipedia.org/wiki/Jacobi_symbol.
: Bitcoin Optech. (October 29, 2019). Bitcoin Optech Schnorr Taproot Workshop: 2.1 segiwth version 1. https://colab.research.google.com/github/bitcoinops/taproot-workshop/blob/Colab/2.1-segwit-version-1.ipynb#scrollTo=FviLk51twL_X.
Legal Disclosure: This blog, and the information contained herein, has been provided to you by Galaxy Digital Holdings LP and its affiliates (“Galaxy Digital”) solely for informational purposes. Neither the information, nor any opinion contained in this document, constitutes an offer to buy or sell, or a solicitation of an offer to buy or sell, any advisory services, securities, futures, options or other financial instruments or to participate in any banking services or trading strategy. Nothing contained in this document constitutes investment, legal or tax advice. You should make your own investigations and evaluations of the information herein. Any decisions based on information contained in this blog are the sole responsibility of the reader. Certain statements in this document reflect Galaxy Digital’s views, estimates, opinions or predictions (which may be based on proprietary models and assumptions, including, in particular, Galaxy Digital’s views on the current and future market for certain digital assets), and there is no guarantee that these views, estimates, opinions or predictions are currently accurate or that they will be ultimately realized. To the extent these assumptions or models are not correct or circumstances change, the actual performance may vary substantially from, and be less than, the estimates included herein. None of Galaxy Digital nor any of its affiliates, shareholders, partners, members, directors, officers, management, employees or representatives makes any representation or warranty, express or implied, as to the accuracy or completeness of any of the information or any other information (whether communicated in written or oral form) transmitted or made available to you. Each of the aforementioned parties expressly disclaims any and all liability relating to or resulting from the use of this information. Certain information contained herein (including financial information) has been obtained from published and non-published sources. Such information has not been independently verified by Galaxy Digital and, Galaxy Digital, does not assume responsibility for the accuracy of such information. Affiliates of Galaxy Digital own investments in some of the digital assets and protocols discussed in this blog. Except where otherwise indicated, the information in this blog is based on matters as they exist as of the date of preparation and not as of any future date, and will not be updated or otherwise revised to reflect information that subsequently becomes available, or circumstances existing or changes occurring after the date hereof. For all inquiries, please email firstname.lastname@example.org. ©Copyright Galaxy Digital Holdings LP 2021. All rights reserved.