schnorr-bitcoin-taproot.ipynb

Kernel: SageMath 10.0

Connect: Schnorr Signatures in Bitcoin Taproot

Module 09 | Real-World Connections

The Schnorr protocol from this module became Bitcoin's signature scheme via BIP 340. Here is exactly how.

Introduction

In November 2021, Bitcoin activated the Taproot upgrade (BIPs 340/341/342), the most significant protocol change since SegWit. At its core, Taproot replaced ECDSA with Schnorr signatures, the non-interactive version of the Schnorr protocol we studied in 09d and 09e.

The connection is direct:

Module 09 concept	Bitcoin Taproot (BIP 340)
Schnorr identification protocol	Schnorr signature scheme
Fiat-Shamir transform	Non-interactive signatures via hashing
Sigma protocol (commit-challenge-respond)	Sign = commit + hash + respond
Proof of knowledge of discrete log	Proof of knowledge of secret key

In this notebook, we will implement a toy version of BIP 340 Schnorr signatures and explore why Bitcoin chose Schnorr over ECDSA.

BIP 340 Schnorr Signatures

BIP 340 specifies Schnorr signatures on the secp256k1 elliptic curve (the same curve Bitcoin has always used). The signature scheme is the Fiat-Shamir transform of the Schnorr protocol:

Key generation:

• Secret key: $d \in \{1, \ldots, n-1\}$ where $n$ is the curve order

• Public key: $P = dG$ (only the x-coordinate is published)

Signing message $m$:

1. Choose nonce $k$ (deterministically from $d$ and $m$)

2. Compute $R = kG$

3. Compute challenge: $e = H(R_x \| P_x \| m)$ (Fiat-Shamir)

4. Compute $s = k + e \cdot d \pmod{n}$

5. Signature is $(R_x, s)$

Verification of $(R_x, s)$ on message $m$:

1. Compute $e = H(R_x \| P_x \| m)$

2. Check: $sG = R + eP$

This is exactly the Schnorr protocol from 09d, made non-interactive via Fiat-Shamir from 09e, instantiated on an elliptic curve.

Let's implement it on a small curve.

# === Setup: small elliptic curve (toy version of secp256k1) ===
import hashlib

# Use a small prime-order curve for demonstration
p = 10007
E = EllipticCurve(GF(p), [0, 7])  # y^2 = x^3 + 7 (same form as secp256k1)
G = E.gens()[0]
n = G.order()

print(f"Curve: y^2 = x^3 + 7 over F_{p}")
print(f"Generator: G = {G}")
print(f"Order: n = {n}")
print(f"Order is prime? {n.is_prime()}")

# Key generation
d = randint(1, n - 1)  # secret key
P = d * G              # public key
print(f"\nSecret key: d = {d}")
print(f"Public key: P = dG = {P}")

# === BIP 340-style Schnorr Sign and Verify ===

def schnorr_hash(R_x, P_x, message, n):
    """BIP 340 challenge: e = H(R_x || P_x || message) mod n.
    This is the Fiat-Shamir transform from 09e."""
    data = f"{R_x}:{P_x}:{message}".encode()
    h = int(hashlib.sha256(data).hexdigest(), 16)
    return h % n

def schnorr_sign(message, d, G, n):
    """Sign a message using BIP 340-style Schnorr.
    Returns (R, s) where R is a curve point and s is an integer."""
    # Deterministic nonce (simplified)
    nonce_data = f"{d}:{message}".encode()
    k = (int(hashlib.sha256(nonce_data).hexdigest(), 16) % (n - 1)) + 1
    
    R = k * G
    P = d * G
    e = schnorr_hash(Integer(R[0]), Integer(P[0]), message, n)
    s = (k + e * d) % n
    return R, s, e

def schnorr_verify_sig(message, R, s, P, G, n):
    """Verify a BIP 340-style Schnorr signature.
    Check: sG == R + eP."""
    e = schnorr_hash(Integer(R[0]), Integer(P[0]), message, n)
    lhs = s * G
    rhs = R + e * P
    return lhs == rhs

# Sign a message
msg = "Send 1 BTC to Alice"
R_sig, s_sig, e_sig = schnorr_sign(msg, d, G, n)

print(f"Message: '{msg}'")
print(f"Signature:")
print(f"  R = {R_sig}")
print(f"  s = {s_sig}")
print(f"  (challenge e = {e_sig})")
print(f"\nVerification: sG == R + eP?")
print(f"  sG     = {s_sig * G}")
print(f"  R + eP = {R_sig + e_sig * P}")
print(f"  Valid? {schnorr_verify_sig(msg, R_sig, s_sig, P, G, n)}")

Why Schnorr over ECDSA?

Bitcoin used ECDSA for its first 12 years. Why switch to Schnorr? The answer comes from a single algebraic property: linearity.

The Schnorr response equation $s = k + e \cdot d$ is linear in both $k$ and $d$. ECDSA's equation $s = k^{-1}(e + d \cdot r)$ involves a multiplicative inverse of $k$, destroying linearity.

Linearity enables:

Feature	Schnorr	ECDSA
Key aggregation	Add public keys, add partial signatures	Requires complex MPC protocols
Batch verification	Verify $n$ signatures faster than $n$ individual checks	Not possible
Adapter signatures	Atomic swaps without hash-time-lock contracts	Not possible
Provable security	Tight reduction to DLP in ROM	Loose reduction, relies on generic group model

# === Key Aggregation: the killer feature ===
# Two parties create a joint public key and joint signature
# that looks like a single-signer signature on-chain.

# Alice and Bob each have a key pair
d_alice = randint(1, n - 1)
P_alice = d_alice * G

d_bob = randint(1, n - 1)
P_bob = d_bob * G

# Naive key aggregation: P_agg = P_alice + P_bob
# (Real MuSig2 adds key-prefixed hashing to prevent rogue-key attacks)
P_agg = P_alice + P_bob

print(f"Alice's public key: P_A = {P_alice}")
print(f"Bob's public key:   P_B = {P_bob}")
print(f"Aggregated key:     P   = P_A + P_B = {P_agg}")
print(f"\nOn the blockchain, P_agg looks like any other public key.")
print(f"Nobody can tell it represents a 2-of-2 multisig!")

# Collaborative signing (simplified, real MuSig2 has extra rounds)
msg_joint = "Joint transaction"

# Each party picks a nonce
k_alice = randint(1, n - 1)
R_alice = k_alice * G

k_bob = randint(1, n - 1)
R_bob = k_bob * G

# Aggregate nonce
R_agg = R_alice + R_bob

# Joint challenge
e_joint = schnorr_hash(Integer(R_agg[0]), Integer(P_agg[0]), msg_joint, n)

# Each party computes a partial signature
s_alice = (k_alice + e_joint * d_alice) % n
s_bob   = (k_bob   + e_joint * d_bob)   % n

# Aggregate signature: s = s_alice + s_bob
s_agg = (s_alice + s_bob) % n

# Verify: s_agg * G == R_agg + e_joint * P_agg
valid_agg = schnorr_verify_sig(msg_joint, R_agg, s_agg, P_agg, G, n)

print(f"\n--- Collaborative Signing ---")
print(f"Message: '{msg_joint}'")
print(f"Aggregated R: {R_agg}")
print(f"Aggregated s: {s_agg}")
print(f"Verifies against P_agg? {valid_agg}")
print(f"\nThe signature (R_agg, s_agg) is indistinguishable from")
print(f"a single-signer Schnorr signature. This is the power of linearity.")

Why Key Aggregation Works: Linearity

Let's trace the algebra. Alice computes $s_A = k_A + e \cdot d_A$ and Bob computes $s_B = k_B + e \cdot d_B$. The aggregate is:

$$s = s_A + s_B = (k_A + k_B) + e \cdot (d_A + d_B)$$

Verification checks $sG = R + eP$:

$$sG = (k_A + k_B)G + e(d_A + d_B)G = (k_A G + k_B G) + e(d_A G + d_B G) = R_A + R_B + e(P_A + P_B) = R_{\text{agg}} + e \cdot P_{\text{agg}}$$

Everything is linear, addition in keys maps to addition in signatures. ECDSA's $s = k^{-1}(e + dr)$ has no such property because the inverse $k^{-1}$ breaks the linear structure.

# === Batch Verification: another Schnorr advantage ===
# Verify multiple signatures faster than checking each individually.
#
# Given signatures (R_i, s_i) on messages m_i with public keys P_i,
# instead of checking each s_i * G == R_i + e_i * P_i separately,
# pick random weights a_i and check:
#   sum(a_i * s_i) * G == sum(a_i * R_i) + sum(a_i * e_i * P_i)
#
# This uses ONE multi-scalar multiplication instead of N separate ones.

# Generate 5 independent signatures
num_sigs = 5
keys = [(randint(1, n-1), None) for _ in range(num_sigs)]
keys = [(d_i, d_i * G) for d_i, _ in keys]
messages = [f"Transaction {i}" for i in range(num_sigs)]

signatures = []
for i in range(num_sigs):
    d_i, P_i = keys[i]
    R_i, s_i, e_i = schnorr_sign(messages[i], d_i, G, n)
    signatures.append((R_i, s_i, P_i))

# Individual verification (baseline)
print("Individual verification:")
for i in range(num_sigs):
    R_i, s_i, P_i = signatures[i]
    valid = schnorr_verify_sig(messages[i], R_i, s_i, P_i, G, n)
    print(f"  Sig {i}: valid={valid}")

# Batch verification
print(f"\nBatch verification:")
weights = [randint(1, n-1) for _ in range(num_sigs)]

# LHS: sum(a_i * s_i) * G
lhs_scalar = sum(weights[i] * signatures[i][1] for i in range(num_sigs)) % n
lhs_point = lhs_scalar * G

# RHS: sum(a_i * R_i) + sum(a_i * e_i * P_i)
rhs_point = E(0)  # point at infinity
for i in range(num_sigs):
    R_i, s_i, P_i = signatures[i]
    e_i = schnorr_hash(Integer(R_i[0]), Integer(P_i[0]), messages[i], n)
    rhs_point = rhs_point + weights[i] * R_i + (weights[i] * e_i % n) * P_i

batch_valid = (lhs_point == rhs_point)
print(f"  All {num_sigs} signatures valid as a batch? {batch_valid}")
print(f"\nBatch verification uses fewer point multiplications,")
print(f"saving ~50% computation for large batches of signatures.")

Taproot: Hiding Scripts Behind Keys

Taproot (BIP 341) uses Schnorr signatures for an additional trick: key tweaking.

A Taproot output commits to both a public key $P$ and a script tree $S$ via a tweaked key:

$$Q = P + H(P \| S) \cdot G$$

• Key path spend: If all parties agree, they sign with the tweaked key $Q$ using $d' = d + H(P \| S)$. The transaction looks like any ordinary single-signature payment. Nobody can tell there was a script at all.

• Script path spend: If parties disagree, reveal $P$, $S$, and a Merkle proof. Execute the script.

This is possible because of Schnorr's linearity: tweaking the key by adding $t \cdot G$ simply adds $t$ to the secret key. ECDSA has no such clean tweaking mechanism.

# === Taproot Key Tweaking ===

# Internal key
d_internal = randint(1, n - 1)
P_internal = d_internal * G

# Script tree (simplified as a string)
script = "OP_IF <alice_pk> OP_CHECKSIG OP_ELSE <timeout> OP_CSV <bob_pk> OP_CHECKSIG OP_ENDIF"

# Compute tweak: t = H(P || script)
tweak_data = f"{Integer(P_internal[0])}:{script}".encode()
t = int(hashlib.sha256(tweak_data).hexdigest(), 16) % n

# Tweaked key: Q = P + t*G
Q = P_internal + t * G
d_tweaked = (d_internal + t) % n  # tweaked secret key

print(f"Internal public key: P = {P_internal}")
print(f"Tweak: t = H(P||script) = {t}")
print(f"Tweaked public key: Q = P + t*G = {Q}")
print(f"Verify: d_tweaked * G = {d_tweaked * G}")
print(f"Matches Q? {d_tweaked * G == Q}")

# Key path spend: sign with tweaked key (looks like normal payment)
msg_spend = "Spend UTXO via key path"
R_tap, s_tap, _ = schnorr_sign(msg_spend, d_tweaked, G, n)
valid_tap = schnorr_verify_sig(msg_spend, R_tap, s_tap, Q, G, n)

print(f"\n--- Key Path Spend ---")
print(f"Sign with tweaked key, verify against Q")
print(f"Valid? {valid_tap}")
print(f"\nThis transaction is indistinguishable from a simple payment.")
print(f"The script tree is completely hidden, maximum privacy.")

Concept Map

Module 09 Concept	Bitcoin Taproot Application
Schnorr protocol (09d)	BIP 340 signature scheme
Fiat-Shamir transform (09e)	Non-interactive signatures: $e = H(R | P | m)$
Sigma protocol structure	Sign = commit ($R$) + challenge ($e$) + respond ($s$)
Proof of knowledge of DL	Proof of knowledge of secret key
Linearity of $s = k + ex$	Key aggregation (MuSig2), batch verification
Nonce reuse vulnerability	RFC 6979 deterministic nonces in BIP 340
Soundness (cannot forge without $x$)	Unforgeability of signatures (EUF-CMA)

Summary

Concept	Key idea
BIP 340	Schnorr signatures on secp256k1, the Fiat-Shamir transform of the Schnorr identification protocol
Key aggregation	MuSig2 enables $n$-of-$n$ multisig that looks like a single signature on-chain, thanks to the linearity of $s = k + ex$
Batch verification	Multiple signatures can be checked faster than individual verification, again exploiting linearity
Key tweaking	Script trees are hidden behind ordinary-looking public keys, enabling privacy-preserving smart contracts
Why not ECDSA	The equation $s = k^{-1}(e + dr)$ is not linear, so none of these features are possible with ECDSA

The journey from a three-message interactive proof (commit, challenge, respond) to a deployed signature scheme signing billions of dollars in transactions is remarkably direct. Every concept from Module 09, including sigma protocols, Fiat-Shamir, and nonce discipline, is load-bearing in Bitcoin's cryptographic infrastructure.

---

Back to Module 09: Commitment Schemes and Sigma Protocols