Bitcoin Taproot & MuSig
For intuition
Note:
Now the problem before taproot
Bitcoin uses P2SH and P2WSH, etc - a transaction UTXO (fancy name for tx inputs) types for creating complex spending conditions like multisig.
P2SH (Pay 2 Script Hash):
<user_sig> <bitgo_sig> 2 user_pubkey bitgo_pubkey backup_pubkey 3 CHECKMULTISIG
Problem:
But, look closer => (user_pubkey, bitgo_pubkey) OR (user_pubkey & backup_key) OR (bitgo_pubkey & backup_key)
Almost all complex scripts are nothing but bunch of ‘OR’ conditions. Showing only the matching condition should be enough to prove the valid script is executed. And throw some hashes over other conditions.
Taproot solution - Script Path Spending using MAST
hash B
user backup CHECKMULTISIG
hash C
bitgo backup CHECKMULTISIG
hash A
user bitgo CHECKMULTISIG
hash BC
hash ABC
MAST (Merkelized Abstract Syntax Trees)
note: all scripts should be at leaf nodes.
Taproot does further optimisation - Key Path Spending using key aggregation
hash B
user backup CHECKMULTISIG
hash C
bitgo backup CHECKMULTISIG
user+bitgo
hash BC
Tweaked output key
If magically, multiple keys & signatures can be aggregated and verified as one single signature, then more privacy & speed and less computation, space & fee.
single aggregated internal pub key = user pubkey + bitgo pubkey (added, not appended)
single aggregated signature = user sig + bitgo sig (added, not appended)
note: it can be any single key
Let’s refresh digital signature basics
Goal: Prove that you the know private key d of the given public key P using a message e.
Let’s create a dummy digital signature scheme and see an example to get an intuition.
Ingredients:
Here, regular multiplication will be used for convenience, but just assume that division is not possible in this hypothetical world.
Let G = 3, d = 2, e = 5
Calculate public key P = dG = 6 (remember! division doesn’t exist, so cant calculate d=P/G)
Sign: s = ed
s = 5 x 2 = 10 => s
Verify: sG = eP => (ed)G = e(dG) => associative property of multiplication is the core idea of this digital signing!
10 x 3 = 5 x 6 ⇒ (5 x 2) x 3 = 5 x (2 x 3) ⇒ 30 = 30
Let’s try to do the magic
ECC allows us to do key aggregation. Let’s try a naive approach to understand.
Let G as generator point on ECC and d1 and d2 as private keys of 2 signers.
P1 = d1G, P2 = d2G
P = P1 + P2
But what about signature aggregation and verification with ECDSA?
Problem and solution for sig aggregation and verification
Oops, ECDSA uses complex non-linear modular inverse equations to sign and verify.
Let k random secure nonce, K = kG public nonce, e = H(P || K || msg) message to sign.
Sign: s = k-1 (e + Kxd) => s,K (signature to share with verifier)
Verify: C = e*s-1G + K*s-1P
Cx= Kx
Schnorr signature scheme uses simple linear equation to save the day.
Sign: s = k + ed => s,K
ed = cryptographic binding. avoids attack by signer from signing without private key.
k+d = cryptographic hiding, avoids attack by verifier from extracting private key.
Verify: sG = kG + edG = K + eP
Naive approach key aggregation and signing cont…
Key aggregation:
P1 = d1G, P2 = d2G
P = P1 + P2
P = d1G + d2G = (d1 + d2)G = dG
Signing: Let k1, k2 are secure nonces created by 2 signers for the signing session.
K1 = k1G, K2 = k2G
K = K1 + K2 = k1G + k2G = (k1 + k2)G = kG
s1 = k1 + ed1, s2 = k2 + ed2
s = s1 + s2
=> s,K
Naive approach verification cont…
Verifying:
s,K from singer
s = s1 + s2
s = (k1 + ed1) + (k2 + ed2)
sG = ((k1 + ed1) + (k2 + ed2))G
sG = (k1 + k2)G + (d1 + d2)eG
sG = (k)G + (d1 + d2)eG
sG = kG + edG
sG = K + eP
Key cancellation attack on naive approach
P1 = d1G, P2 = d2G
P’2 = P2 - P1 (signer 2 creates malicious pub key and share it with signer 1 as P2)
P = P1 + P’2 (signer 1 uses malicious pub key from signer 2 for key agg)
P = P1 + (P2 - P1)
P = P2 (now signer 1 believes P2 as aggregated key)
Now key path can be signed with single signature using d2 alone.
Musig - key and sig aggregation without the attack
MuSig is a n-of-n multisig protocol for aggregating public keys and signatures for the schnorr digital signature algorithm.
Note: It is a not an m-of-n (threshold) multisig protocol.
Key aggregation:
P1 = d1G, P2 = d2G
c1 = H(P1 || P2 || P1), c2 = H(P1 || P2 || P2)
d’1 = c1d1 d’2 = c2d2
P’1 = c1P1 , P’2 = c2P2(commit all pub keys)
P’ = P’1 + P’2
Musig signing
Sign step 1: Signers exchange nonce commitments Com1 and Com2 to avoid some attacks.
K1 = k1G, K2 = k2G
Com1 = H(K1), Com2 = H(K2) (the attacker signer 2 can not tamper with K1)
Sign step 2: Calculate K’ and e
K’ = K1 + K2
K’ = k1G + k2G = (k1 + k2)G = k’G
k’ = k1 + k2
e = H(K’ || P’ || msg)
Musig signing cont…
Sign step 3: signature
s1 = k1 + ed’1, s2 = k2 + ed’2
s’ = s1 + s2
signature = s’,K’
Musig verify
s’ = s1 + s2
s’ = (k1 + ed’1) + (k2 + ed’2)
s’G = ((k1 + k2) + e(d’1 + d’2))G
s’G = (k1 + k2)G + e(d’1 + d’2)G
s’G = (k’)G + e(d’1 + d’2)G
s’G = K’ + ed’G
s’G = K’ + eP’
Tweaking musig key and merkle root to output key
P’ = user pubkey + bitgo pub key (musig aggregation)
d’1 , d’2 = user & bitgo private keys
M = Script path taptree root (hash BC)
Calculate tweaked output key:
t = H(P’ || M)
Q = tweaked output key
Q = P’ + tG
Q = d’1G + d’2G + tG
Q = (d’1 + d’2 + t)G = (d’ + t)G = qG
Tweaked key signing and verification
Sign:
s’ = (k1 + ed’1) + (k2 + ed’2) + et
s’ = s1 + s2 + et
Verify:
s’G = ((k1 + k2) + e(d’1 + d’2 + t))G
s’G = (k1 + k2)G + e(d’1 + d’2 + t)G
s’G = (k’)G + e(d’1 + d’2 + t)G
s’G = K’ + e(d’ + t)G
s’G = K’ + eqG
s’G = K’ + eQ
Important notes
Links:
Taproot upgrade is composed of 3 different bips.
BIP340 – Schnorr signature - Schnorr signature scheme to Bitcoin
BIP341 – Taproot - MAST and such
BIP342 – Tapscript - New scripts and opcodes used for script path conditions
BIP - MuSig2 - Not part of taproot upgrade.
Q & A