Learn Taproot

https://github.com/jimmysong/learntaproot

Session Objectives

• Learn Schnorr Signatures
• Learn Taproot Key Path Spend
• Learvn Taprvoot Script Path Spend

Schnorr Signatures

Motivation

• Conceptually Simpler
• ECDSA uses DER, which is 72-73 bytes, Schnorr uses 64
• Fewer Elliptic Curve Operations (hash instead)
• Key Aggregation/Signature Aggregation/Batch Verification

ECDSA Signing

• $eG=P$, $z$ is hash of what's being signed, choose a random $k$
• Compute $kG=R=(x,y)$, let $r=x$
• Compute $s=\frac{z+re}{k}$
• Signature is the pair $(r,s)$

ECDSA Verification

• $eG=P$, $z$ is hash of what's being signed, choose a random $k$
• Signature is $(r,s)$ where $s=\frac{z+re}{k}$
• Compute $u=\frac{z}{s}, v=\frac{r}{s}$ $$uG+vP=\frac{z}{s}G+\frac{r}{s}P=\frac{z}{s}G+\frac{re}{s}G \\ =\frac{z+re}{s}G =\frac{(z+re)k}{z+re}G \\ =kG=R=(r,y)$$

ECDSA

• $u$ is used to commit to $z$, or the tx being attested to
• $v$ is used to commit to $r$, or the target/challenge that we're trying to hit/respond to
• Kludgy, uses field division, which is expensive computationally
• Developed after Schnorr and used in Bitcoin due to Patent issues (expired 2008)

Schnorr

• Uses a hash function instead of field division
• That hash can commit to everything at once, instead of just one thing.
• $H(a||b||c||...)$
• Target is a point on the curve $R$, not just the $x$ coordinate
• Aggregation of keys and signatures now possible!
• Batch verification possible!
• BIP340

Tagged Hashes

• Each hash is different so that hashes cannot feasibly collide
• There are 10 different contexts, each creating its own set of hashes
• The hash is SHA256, but with 64 bytes before the actual bytes being hashed
• The 64 bytes are another SHA256 of the tag (e.g. "BIP340/aux") repeated twice
• H_aux(x) = SHA256(SHA256("BIP340/aux") + SHA256("BIP340/aux") + x)

Tagged Hashes

# Example Tagged Hashes
from hash import sha256
challenge_tag = b"BIP0340/challenge"
msg = b"some message"
challenge_hash = sha256(challenge_tag)
hash_challenge = sha256(challenge_hash + challenge_hash + msg)
print(hash_challenge.hex())
    

Exercises

• What is the tagged hash "BIP0340/aux" of "hello world"?
• Make this test pass: hash:HashTest:test_tagged_hash

$x$-only keys

• Assume $y$ is even
• Serialized as 32-bytes
• The private key $e$ is flipped to $N-e$ if $y$ is odd
• $eG=P=(x,y)$ means $(N-e)G=0-eG=-P=(x,-y)$
• Lots of flipping!

$x$-only Keys

# Example X-only pubkey
from ecc import PrivateKey, S256Point
from helper import int_to_big_endian
pubkey = PrivateKey(12345).point
xonly = int_to_big_endian(pubkey.x.num, 32)
print(xonly.hex())
pubkey2 = S256Point.parse(xonly)
print(pubkey.xonly() == pubkey2.xonly())
    

Exercises

• Find the $x$-only pubkey format for the private key with the secret 21,000,000
• Make this test pass: ecc:XOnlyTest:test_xonly

Schnorr Signature

• $x$-only keys (Always even $y$)
• Uses tagged hashes (different hash per operation)
• $k$-generation has a separate process
• Target is an $x$-only key
• $(R,s)$, where $R$ is the pubkey of the target and $s$ is 32 bytes
• Serialization is $R$ as $x$-only followed by $s$ in big endian

ECDSA Verification

• $eG=P$, $z$ message, $kG=(r,y)$
• Signature is $(r,s)$ where $s=\frac{z+re}{k}$
• Compute $u=\frac{z}{s}, v=\frac{r}{s}$ $$uG+vP=\frac{z}{s}G+\frac{r}{s}P=\frac{z}{s}G+\frac{re}{s}G \\ =\frac{z+re}{s}G =\frac{(z+re)k}{z+re}G \\ =kG=R=(r,y)$$

Schnorr Verification

• $eG=P$, $m$ message, $kG=R$, $H$ is a hash function
• Signature is $(R,s)$ where $s=k + e H(R||P||m)$ $$-H(R||P||m)P+sG \\ =-H(R||P||m)P+(k+e H(R||P||m))G \\ =-H(R||P||m)P+kG+H(R||P||m)(eG) \\ =R+H(R||P||m)P-H(R||P||m)P=R$$

$x$-only Keys

from ecc import S256Point, SchnorrSignature, G, N
from helper import sha256, big_endian_to_int
from hash import hash_challenge
# the message we're signing
msg = sha256(b"I attest to understanding Schnorr Signatures")
# the signature we're using
sig_raw = bytes.fromhex("f3626c99fe36167e5fef6b95e5ed6e5687caa4dc828986a7de8f9423c0f77f9bc73091ed86085ce43de0e255b3d0afafc7eee41ddc9970c3dc8472acfcdfd39a")
sig = SchnorrSignature.parse(sig_raw)
# the pubkey we are using
xonly = bytes.fromhex("f01d6b9018ab421dd410404cb869072065522bf85734008f105cf385a023a80f")
point = S256Point.parse(xonly)
# calculate the commitment which is R || P || msg
commitment = sig.r.xonly() + point.xonly() + msg
# hash_challenge the commitment, interpret as big endian and mod by N
challenge = big_endian_to_int(hash_challenge(commitment)) % N
# the target is the -challenge * point + s * G
target = -challenge * point + sig.s * G
print(target == sig.r)
    

Exercises

• Verify a Schnorr Signature
• Make this test pass: ecc:SchnorrTest:test_verify

ECDSA Signing

• $eG=P$, $z$ message, $k$ random
• $kG=R=(x,y)$, let $r=x$
• $s=\frac{z+re}{k}$
• Signature is $(r,s)$

Schnorr Signing

• $eG=P$, $m$ message, $k$ random
• $kG=R$, $H$ is a hash function
• $s=k+e H(R||P||m)$ where $R$ and $P$ are $x$-only
• Signature is $(R,s)$

Schnorr Signing

# Example Signing
from ecc import PrivateKey, N, G
from helper import sha256
priv = PrivateKey(12345)
if priv.point.y.num % 2 == 1:
    d = N - priv.secret
else:
    d = priv.secret
msg = sha256(b"I attest to understanding Schnorr Signatures")
k = 21016020145315867006318399104346325815084469783631925097217883979013588851039
r = k * G
if r.y.num % 2 == 1:
    k = N - k
    r = k * G
commitment = r.xonly() + priv.point.xonly() + msg
e = big_endian_to_int(hash_challenge(commitment)) % N
s = (k + e * d) % N
sig = SchnorrSignature(r, s)
if not priv.point.verify_schnorr(msg, sig):
    raise RuntimeError("Bad Signature")
print(sig.serialize().hex())
    

Exercises

• Sign the message "I'm learning Taproot!" with the private key 21,000,000
• Make this test pass: ecc:SchnorrTest:test_sign

$k$ Generation

• Revealing $k$ reveals the private key
• Bad random number generator for $k$ will reveal the private key
• BIP340 starts with a random number $a$ called the auxillary
• Then xor $a$ with the secret to make it impossible to guess
• Then we hash with the message to generate the $k$
• This makes $k$ unique to both the secret and the message
• 32 0-bytes $a$ can be used to create a deterministic $k$

Batch Verification

• $e_iG=P_i$, $m_i$ message, $H$
• Signature is $(R_i,s_i)$, $h_i=H(R_i||P_i||m_i)$
• $-h_i P_1+s_1G=R_1$
• $-h_i P_2+s_2G=R_2$
• $-h_1 P_1-h_2 P_1+(s_1+s_2)G=R_1+R_2$
• $(s_1+s_2)G=R_1+R_2+h_1 P_1+h_2 P_2$

Exercises

• Batch Verify two Schnorr Signatures

Taproot Key Path Spend

Taproot

• BIP341
• Combines both single-key and arbitrary script type addresses
• p2pkh and p2sh did those previously
• p2wpkh and p2wsh did those in Segwit

Taproot Structure

Taproot Architecture

• KeyPath Spend (single-key like p2pkh and p2wpkh)
• ScriptPath Spend (arbitrary script like p2sh and p2wsh)
• ScriptPath is a Merkle Tree of TapScripts
• TapScripts are like Script, but with slightly different OP codes

Taproot Implementation

• Segwit version 1
• Requires OP_1 and 32 bytes
• The 32 bytes are an $x$-only public key $Q$ (external public key)
• KeyPath spend's public key is $P$ (internal public key)
• The Merkle Root of the ScriptPath Spend combined with the internal public key generates the tweak ($t$)
• $Q=P+tG$

How to spend from the KeyPath

• You have to know the Merkle Root of the ScriptPath
• The internal public key is hashed together with the Merkle Root to generate the tweak $t$
• The formula is $t=H(P||t)$ where H is a Tagged Hash (TapTweak)
• $Q=P+tG$, and $eG=P$ which means $Q=eG+tG$ and $Q=(e+t)G$
• $e+t$ is your private key, which can sign for the public key Q
• Witness only needs the Schnorr Signature
• If you don't want a script path, $t$ is just empty

Key Path UTXO Example

# Example Q calculation for a single-key
from ecc import S256Point, G
from hash import hash_taptweak
from helper import big_endian_to_int
from script import P2TRScriptPubKey
internal_pubkey_raw = bytes.fromhex("cbaa648dbfe734646ce958e2f14a874149fae4010fdeabde4bae6a732537fd91")
internal_pubkey = S256Point.parse(internal_pubkey_raw)
tweak = big_endian_to_int(hash_taptweak(internal_pubkey_raw))
external_pubkey = internal_pubkey + tweak * G
script_pubkey = P2TRScriptPubKey(external_pubkey)
print(script_pubkey)
    

Exercises

• Make a P2TR ScriptPubKey using the private key 9284736473
• Make this test pass: ecc:TapRootTest:test_default_tweak
• Make this test pass: ecc:TapRootTest:test_tweaked_key
• Make this test pass: ecc:TapRootTest:test_p2tr_script

P2TR Addresses

• Uses Bech32m, which is different than Bech32 (BIP350)
• Segwit v0 uses Bech32
• Taproot (Segwit v1) uses Bech32m
• Has error correcting capability and uses 32 letters/numbers
• Segwit v0 addresses start with bc1q and p2wpkh is shorter than p2wsh
• Segwit v1 addresses start with bc1p and they're all one length

P2TR Address Example

# Example of getting a p2tr address
from ecc import S256Point
internal_pubkey_raw = bytes.fromhex("cbaa648dbfe734646ce958e2f14a874149fae4010fdeabde4bae6a732537fd91")
internal_pubkey = S256Point.parse(internal_pubkey_raw)
print(internal_pubkey.p2tr_address())
print(internal_pubkey.p2tr_address(network="signet"))
    

Make your own Signet P2TR Address

Write down your address at this link under "keypath address"

Spending P2TR KeyPath

• We need the tweak $t$ and the private key $e$ to be able to sign the transaction
• The pubkey is in the UTXO as an $x$-only key
• All we need is the Schnorr Signature in the Witness field
• We use the sign_schnorr method in the PrivateKey to do this.

Spending Plan

• We have 20,000 sats in this output:
  • 871864...66995:0
• We want to spend all of it to:
  • tb1ptaqplrhn...quchufq
• 1 input/1 output transaction

Spending Example

# Spending from a p2tr
from ecc import PrivateKey, N
from helper import sha256
from script import address_to_script_pubkey
from tx import Tx, TxIn, TxOut
my_email = b"jimmy@programmingblockchain.com"
my_secret = big_endian_to_int(sha256(my_email))
priv = PrivateKey(my_secret)
prev_tx = bytes.fromhex("871864d7631024465fc210e553fa9f50e7f0f2359288ad121aa733d65e366995")
prev_index = 0
target_address = "tb1ptaqplrhnyh3kq85n7dtm5vcpgstt0ev80f4wd8ngeppch4fzu8mquchufq"
fee = 500
tx_in = TxIn(prev_tx, prev_index)
target_script_pubkey = address_to_script_pubkey(target_address)
target_amount = tx_in.value(network="signet") - fee
tx_out = TxOut(target_amount, target_script_pubkey)
tx_obj = Tx(1, [tx_in], [tx_out], network="signet", segwit=True)
tweaked_secret = (priv.secret + priv.point.default_tweak()) % N
tweaked_key = PrivateKey(tweaked_secret)
tx_obj.sign_p2tr_keypath(0, tweaked_key)
print(tx_obj.serialize().hex())
    

Exercises

• Make this test pass: ecc:PrivateKeyTest:test_tweaked_key

Spend from your P2TR Address

You have been sent 100,000 sats to your address on Signet. Send 40,000 sats back to tb1q7kn55vf3mmd40gyj46r245lw87dc6us5n50lrg, the rest to yourself.

Use Mempool Signet to broadcast your transaction

Taproot Script Path Spend

Taproot Structure

TapScript

• Defined in BIP342
• Same as Script except for a few New/Changed OP Codes
• OP_CHECKSIG and OP_CHECKSIGVERIFY use Schnorr Signatures
• OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY are disabled
• OP_CHECKSIGADD is added to replace multisig

OP_CHECKSIGADD

• Consumes the top three elements: a pubkey, a number, and a signature.
• Valid sig, returns the number+1 to the stack
• Invalid sig, returns the number back to the stack

Example Multisig using OP_CHECKSIGADD

Exercises

• Make this test pass: op:TapScriptTest:test_opchecksigadd

Example TapScripts

• 1-of-1 (pay-to-pubkey) [pubkey, OP_CHECKSIG]
• 2-of-2 [pubkey A, OP_CHECKSIGVERIFY, pubkey B, OP_CHECKSIG]
• 2-of-3 [pubkey A, OP_CHECKSIG, pubkey B, OP_CHECKSIGADD, pubkey C, OP_CHECKSIGADD, OP_2, OP_EQUAL]
• halvening timelock 1-of-1 [840000, OP_CHECKLOCKTIMEVERIFY, OP_DROP, pubkey, OP_CHECKSIG]

Example TapScript

# Example TapScripts
from ecc import PrivateKey
from op import encode_minimal_num
from taproot import TapScript
pubkey_a = PrivateKey(11111111).point.xonly()
pubkey_b = PrivateKey(22222222).point.xonly()
pubkey_c = PrivateKey(33333333).point.xonly()
# 1-of-1 (0xAC is OP_CHECKSIG)
script_pubkey = TapScript([pubkey_a, 0xAC])
print(script_pubkey)
# 2-of-2 (0xAD is OP_CHECKSIGVERIFY)
script_pubkey = TapScript([pubkey_a, 0xAD, pubkey_b, 0xAC])
print(script_pubkey)
# 2-of-3 (0xBA is OP_CHECKSIGADD, 0x52 is OP_2, 0x87 is OP_EQUAL)
script_pubkey = TapScript([pubkey_a, 0xAD, pubkey_b, 0xBA, pubkey_c, 0xBA, 0x52, 0x87])
print(script_pubkey)
# halvening timelock 1-of-1 (0xB1 is OP_CLTV, 0x75 is OP_DROP)
script_pubkey = TapScript([encode_minimal_num(840000), 0xB1, 0x75, pubkey_a, 0xAC])
print(script_pubkey)
    

Exercises

• Make a TapScript for a 4-of-4 using pubkeys from private keys which correspond to 10101, 20202, 30303, 40404

TapLeaf

• These are the leaves of the Merkle Tree
• Has a TapLeaf Version (0xc0) and TapScript
• Any Leaf can be executed to satisfy the Taproot Script Path
• Hash of a TapLeaf is a Tagged Hash (TapLeaf) of the version + TapScript

Taproot Structure

Example TapLeaf Hash

# Example of making a TapLeaf and calculating the hash
from ecc import PrivateKey
from hash import hash_tapleaf
from helper import int_to_byte
from taproot import TapScript, TapLeaf
pubkey_a = PrivateKey(11111111).point.xonly()
pubkey_b = PrivateKey(22222222).point.xonly()
tap_script = TapScript([pubkey_a, 0xAD, pubkey_b, 0xAC])
tap_leaf = TapLeaf(tap_script)
h = hash_tapleaf(int_to_byte(tap_leaf.tapleaf_version) + tap_leaf.tap_script.serialize())
print(h.hex())
    

Exercises

• Calculate the TapLeaf hash whose TapScript is a 2-of-4 using pubkeys from private keys which correspond to 10101, 20202, 30303, 40404
• Make this test pass: taproot:TapRootTest:test_tapleaf_hash

TapBranch

• These are the branches of the Merkle Tree
• These connect a left child and a right child.
• Each child is a TapLeaf or TapBranch
• Hash of a TapBranch is a Tagged Hash (TapBranch) of the left hash and right hash, sorted

Taproot Structure

Example TapBranch Hash

# Example of making a TapBranch and calculating the hash
from ecc import PrivateKey
from hash import hash_tapbranch
from helper import int_to_byte
from taproot import TapScript, TapLeaf, TapBranch
pubkey_1 = PrivateKey(11111111).point.xonly()
pubkey_2 = PrivateKey(22222222).point.xonly()
tap_script_1 = TapScript([pubkey_1, 0xAC])
tap_script_2 = TapScript([pubkey_2, 0xAC])
tap_leaf_1 = TapLeaf(tap_script_1)
tap_leaf_2 = TapLeaf(tap_script_2)
tap_branch = TapBranch(tap_leaf_1, tap_leaf_2)
left_hash = tap_leaf_1.hash()
right_hash = tap_leaf_2.hash()
if left_hash > right_hash:
    h = hash_tapbranch(left_hash + right_hash)
else:
    h = hash_tapbranch(right_hash + left_hash)
print(h.hex())
    

Exercises

• Calculate the TabBranch hash whose left and right nodes are TapLeafs whose TapScripts are for a 1-of-2 using pubkeys from private keys which correspond to (10101, 20202) for the left, (30303, 40404) for the right
• Make this test pass: taproot:TapRootTest:test_tapbranch_hash

Merkle Root

• The Merkle Root of the Merkle Tree can be used to compute the tweak $t$
• A TapLeaf (1 condition) or TapBranch (more than 1 condition) or a deterministic hash (0 conditions)
• Any TapScript inside the Merkle Tree can unlock the UTXO
• Unlocking requires satisfying the TapScript and a Control Block
• Unlocking conditions are hidden until spent
• Unused unlocking conditions remain hidden
• Up to 128 levels, meaning $2^{128}$ conditions

Taproot Structure

Computing the Merkle Root

• The Merkle Root is the hash of the root element of the Merkle Tree
• For TapLeaf: Tagged hash (TapLeaf) of TapLeaf Version followed by the TapScript
• For TapBranch: Tagged hash (TapBranch) of the sorted children (left and right)
• It doesn't have to be the hash of anything, just has to be 32 bytes

Exercises

• Calculate the External PubKey for a Taproot output whose internal pubkey is 90909 and whose Merkle Root is from two TapBranches, each of which is a single signature TapLeaf. The private keys corresponding to the left TapBranch's TapLeafs are 10101 and 20202. The private keys corresponding to the right TapBranch's TapLeafs are 30303 and 40404.

Script Path Spending

• Merkle Proof and Internal Public Key in the Control Block (last element of Witness)
• TapScript is the second-to-last element of the Witness
• Unlock/Satisfy the TapScript, which are the other elements of the Witness
• Combine the TapScript and the Merkle Proof to get the Merkle Root
• Combine Merkle Root and Internal Public Key to get the External Public Key

Control Block

• Required for spending a TapScript, last element of Witness
• TapScript Version (0xc0 or 0xc1)
• The last bit expresses the parity of the external pubkey, which is necessary for batch verification
• Internal PubKey $P$
• Merkle Proof (list of hashes to combine to get to the Merkle Root)

Merkle Proof

• List of hashes
• Combine each with the hash of the TapScript, sorting them each time
• The result is the Merkle Root, which can be combined with the Internal PubKey $P$ to get the tweak $t$
• If the result of $P+tG=Q$ where $Q$ is the External PubKey from the UTXO, this is a valid TapScript

Merkle Proof

Control Block Validation Example

# Example of Control Block Validation
from ecc import PrivateKey, S256Point
from hash import hash_tapbranch
from helper import int_to_byte
from taproot import TapScript, TapLeaf, TapBranch
external_pubkey_xonly = bytes.fromhex("cbe433288ae1eede1f24818f08046d4e647fef808cfbbffc7d10f24a698eecfd")
pubkey_2 = bytes.fromhex("027aa71d9cdb31cd8fe037a6f441e624fe478a2deece7affa840312b14e971a4")
tap_script_2 = TapScript([pubkey_2, 0xAC])
tap_leaf_2 = TapLeaf(tap_script_2)
tap_leaf_1_hash = bytes.fromhex("76f5c1cdfc8b07dc8edca5bef2b4991201c5a0e18b1dbbcfe00ef2295b8f6dff")
tap_leaf_3_hash = bytes.fromhex("5dd270ec91aa5644d907059400edfd98e307a6f1c6fe3a2d1d4550674ff6bc6e")
internal_pubkey = S256Point.parse(bytes.fromhex("407910a4cfa5fe195ad4844b6069489fcb429f27dff811c65e99f7d776e943e5"))
current = tap_leaf_2.hash()
for h in (tap_leaf_1_hash, tap_leaf_3_hash):
    if h < current:
        current = hash_tapbranch(h + current)
    else:
        current = hash_tapbranch(current + h)
print(internal_pubkey.tweaked_key(current).xonly() == external_pubkey_xonly)
print(internal_pubkey.p2tr_address(current, network="signet"))
    

Exercises

• Validate the Control Block for the pubkey whose private key is 40404 for the previous external pubkey
• Make this test pass: taproot:TapRootTest:test_control_block

Exercise

1. Internal Public Key is cd04c1...51d9e
2. Leaf 1 and Leaf 2 make Branch 1, Branch 1 and Leaf 3 make Branch 2, which is the Merkle Root
3. All TapLeaf are single key locked TapScripts (pubkey, OP_CHECKSIG)
4. Leaf 1 uses your xonly pubkey
5. Leaf 2 uses this xonly pubkey: 331a8f...74aeec
6. Leaf 3 uses this xonly pubkey: 158a49...8ff16f

Exercise

• Send yourself the rest of the coins from the output of the previous exercise to the address you just created
• Now spend this output using the script path from the second TapLeaf send it all to tb1q7kn55vf3mmd40gyj46r245lw87dc6us5n50lrg

Use Mempool Signet to broadcast your transactions