Bitcoin added support for schnorr signatures with the Taproot update, which activated at block 709 632. In this article, we dive into how it works and some of the advanced schemes it unlocks.
- Schnorr signatures
- Linearity of Schnorr signatures
- Adaptor signatures
- Musig2
- Musig2 adaptor signatures
- Musig2 BIP 32 derivation
Schnorr signatures are specified in BIP 340. Ignoring many details described in the BIP, at a high level the signing algorithm works as follows:
P = k*G -> signer's public key
m -> message to sign
Sign:
r = {0;1}^256 -> random nonce
R = r*G
e = H(R || P || m)
s = r + e*k
(s, R) -> message signature
Verify:
e = H(R || P || m)
R' = s*G - e*P
If R = R', the signature is valid
A very interesting property of schnorr signatures compared to ECDSA signatures is that they make it easy to combine signatures for a given message if we slightly change the signing algorithm.
A = a*G -> Alice's public key
B = b*G -> Bob's public key
P = A + B -> combined public key
m -> message to sign
Sign:
ra = {0;1}^256 -> random nonce generated by Alice
RA = ra*G -> public partial nonce sent by Alice to Bob
rb = {0;1}^256 -> random nonce generated by Bob
RB = rb*G -> public partial nonce sent by Bob to Alice
R = RA + RB -> public nonce
e = H(R || P || m)
sA = ra + e*a -> partial signature produced by Alice
sB = rb + e*b -> partial signature produced by Bob
s = sA + sB
(s, R) -> combined message signature
Verify:
e = H(R || P || m)
R' = s*G - e*P
If R = R', the signature is valid
You should notice that the verification algorithm hasn't changed. This means that the verifier doesn't even know that multiple signers were involved: the signature looks like it comes from a standard single signer.
The linearity of schnorr signatures also allows revealing a secret through a signature.
P = k*G -> signer's public key
T = t*G -> tweak (t is the secret that will be revealed)
m -> message to sign
Sign:
r = {0;1}^256
R = r*G
e = H(R + T || P || m) -> notice that we tweak the nonce here with T
s = r + e*k -> but we don't tweak it here with t
(s, R, T) -> adaptor signature: will automatically reveal t when a valid signature for nonce R + T is produced
Verify:
e = H(R + T || P || m)
R' = s*G - e*P
If R = R', the adaptor signature is valid
Note that (s, R) or (s, R + T) are not valid schnorr signatures
Complete:
s' = s + t
R' = R + T
(s', R') -> valid schnorr signature
Extract:
e' = H(R' || P || m)
R'' = s'*G - e'*P
If R'' = R', the signature is valid
t = s' - s
The verifier has learnt t through the schnorr signature
NB: for this to work, the verifier must ensure that the nonce R + T is fixed beforehand.
Otherwise the signer may create a valid signature for an unrelated nonce, which would not reveal the secret t.
This is most useful when combined with Musig2, where participants commit to the nonce before signing.
Adaptor signatures can also be used in the opposite way.
If the signer doesn't know the secret t, it can produce an adaptor signature.
Then another participant that knows t can convert that adaptor signature to a valid signature.
Musig2 is a secure scheme for combining multiple signatures into a single schnorr signature. It only needs two rounds of communications between participants, and the first round can be done ahead of time (independently of the message to sign). The novel idea in that scheme is to use multiple nonces for each participant and combine them in a smart way to produce the final nonce. This results in an elegant scheme that looks very similar to standard schnorr signing.
PA = pa*G -> public key of participant A
PB = pb*G -> public key of participant B
L = (PA, PB) -> sorted list of participants public keys
P = H(H(L) || PA)*PA + PB -> combined public key
NonceGenA (run by participant A):
ra1 = {0;1}^256
ra2 = {0;1}^256
RA1 = ra1*G
RA2 = ra2*G
NonceGenB (run by participant B):
rb1 = {0;1}^256
rb2 = {0;1}^256
RB1 = rb1*G
RB2 = rb2*G
NonceExchange (communication round 1):
Participant A sends RA1, RA2 to participant B
Participant B sends RB1, RB2 to participant A
SignA (run by participant A):
x = H(P || RA1 + RB1 || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
ra = ra1 + x*ra2
e = H(R || P || m)
sa = ra + e*H(L || PA)*pa
(sa, R) -> participant A's partial signature
SignB (run by participant B):
x = H(P || RA1 + RB1 || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
rb = rb1 + x*rb2
e = H(R || P || m)
sb = rb + e*pb
(sb, R) -> participant B's partial signature
Combine (communication round 2):
s = sa + sb
(s, R) -> valid schnorr signature for public key P
Verify:
e = H(R || P || m)
R' = s*G - e*P
= (sa + sb)*G - e*P
= (ra + e*H(L || PA)*pa)*G + (rb + e*pb)*G - e*P
= (ra + rb)*G + e*(H(L || PA)*pa + pb)*G - e*P
= R + e*P - e*P
= R
-> this is a valid schnorr signature
NB: we used only two participants to simplify the example, but Musig2 works with any number of participants.
Musig2 can be combined with adaptor signatures:
# The first round (pre-computing nonces) is vanilla Musig2
PA = pa*G -> public key of participant A
PB = pb*G -> public key of participant B
L = (PA, PB) -> sorted list of participants public keys
P = H(H(L) || PA)*PA + PB -> combined public key
NonceGenA (run by participant A):
ra1 = {0;1}^256
ra2 = {0;1}^256
RA1 = ra1*G
RA2 = ra2*G
NonceGenB (run by participant B):
rb1 = {0;1}^256
rb2 = {0;1}^256
RB1 = rb1*G
RB2 = rb2*G
NonceExchange (communication round 1):
Participant A sends RA1, RA2 to participant B
Participant B sends RB1, RB2 to participant A
# The second round simply tweaks the combined nonce with the secret
T = t*G -> secret t known only by B
SignA (run by participant A):
x = H(P || RA1 + RB1 + T || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
ra = ra1 + x*ra2
e = H(R + T || P || m)
sa = ra + e*H(L || PA)*pa
(sa, R + T) -> participant A's partial signature
SignB (run by participant B):
x = H(P || RA1 + RB1 + T || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
rb = rb1 + x*rb2
e = H(R + T || P || m)
sb = rb + e*pb
(sb, R, T) -> participant B's adaptor signature
Participant A can verify participant B's adaptor signature before sending its partial signature:
(sa + sb)*G must be equal to R + H(R + T || P || m)*P
-> NB: it's not a valid schnorr signature, notice the mismatch between R (outside of the hash) and R + T (inside the hash)
Complete (run by participant B):
s = sa + sb + t
R' = R + T
(s, R') -> valid schnorr signature for public key P and nonce R + T
Extract (run by participant A):
t = s - sa - sb
Musig2 can be used with BIP 32 derivation. The trick is that the individual keys will not change, we're only tweaking the aggregated public key.
PA = pa*G -> public key of participant A
PB = pb*G -> public key of participant B
L = (PA, PB) -> sorted list of participants public keys
P = H(H(L) || PA)*PA + PB -> combined master public key
Both participants agree on a chaincode c
The combined public key at index i can be computed:
I = H(c, P || i)
IL = I[0:32]
IR = I[33:64]
Pi = P + IL*G
ci = IR
Participants create partial signatures for this child combined public key with the following steps.
These are the same steps as vanilla Musig2 with Pi instead of P.
NonceGenA (run by participant A):
ra1 = {0;1}^256
ra2 = {0;1}^256
RA1 = ra1*G
RA2 = ra2*G
NonceGenB (run by participant B):
rb1 = {0;1}^256
rb2 = {0;1}^256
RB1 = rb1*G
RB2 = rb2*G
NonceExchange (communication round 1):
Participant A sends RA1, RA2 to participant B
Participant B sends RB1, RB2 to participant A
SignA (run by participant A):
x = H(Pi || RA1 + RB1 || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
ra = ra1 + x*ra2
e = H(R || Pi || m)
sa = ra + e*H(L || PA)*pa
(sa, R) -> participant A's partial signature
SignB (run by participant B):
x = H(Pi || RA1 + RB1 || RA2 + RB2 || m)
R = RA1 + RB1 + x*(RA2 + RB2)
rb = rb1 + x*rb2
e = H(R || Pi || m)
sb = rb + e*pb
(sb, R) -> participant B's partial signature
Combine (communication round 2):
e = H(R || Pi || m) -> this step can be done with anyone able to compute this
s = sa + sb + e*IL
(s, R) -> valid schnorr signature for public key Pi
Verify:
e = H(R || Pi || m)
R' = s*G - e*Pi
= (sa + sb + e*IL)*G - e*Pi
= (ra + e*H(L || PA)*pa)*G + (rb + e*pb)*G + e*IL*G - e*Pi
= (ra + rb)*G + e*(H(L || PA)*pa + pb + IL)*G - e*Pi
= R + e*Pi - e*Pi
= R
-> this is a valid schnorr signature