9.8 KiB

Raw Permalink Blame History

Schnorr Wizardry

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

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

Linearity of Schnorr signatures

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.

⚠️ This signing scheme is not secure when Alice or Bob is malicious. We will describe a secure signing scheme in the Musig2 section below.

Adaptor signatures

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

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 adaptor signatures

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 BIP 32 derivation

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

9.8 KiB Raw Permalink Blame History