Schnorr SignaturesSchnorr signatures were created by Claus Schnorr, and covered by a patent that expired in 2008. The Schnorr signature method supports the merging of public keys to produce a single public key to check the signature of a transaction. It is used in SegWit (segregated witness) to merge the signing of a transaction when there are more than one entity involved in the signing of a transaction [1].
|
Overview (using elliptic curve methods)
An overview of the Schnorr signature is given below. In this case Bob wants to sign a message (\(M\)). For this he has a private key of \(sk\) and generates a public key of \(P=sk.G\), and where \(G\) is the base point on the elliptic curve. To sign a message, he generates a random number for his signature (\(k\)), an and then computes:
\(R=k.G\)
\(s=k-H(M || R) . sk\)
and where \(H()\) is the hash of the associated byte values, and (\(M || R\)) is appended byte values from \(M\) and \(R\). Bob then sends the message (\(M\)) and the signature (\(R,s\)) to Alice. When Alice received the signature and the message, she checks:
\(H(M || R).P + s.G = R\)
If they are the same, the signature checks out. This works because:
\begin{align} H(M || R).P + s.G &= H(M || R).(sk.G) + (k-(H(M || R).sk).G \\ &= H(M || R).(sk.G) + k.G-(H(M || R).sk.G\\ &= k.G \end{align}
Multiple signatures (MuSig) with Schnorr
So how do Bob and Wendy sign a message for Alice? With the Schnorr signature method we can simply perform an add operation. With this, Bob will generate his private key (\(sk_1\)) and derive his public key from:
\(P_1=sk_1.G\)
He will then generate:
\(R_1=k_1.G\)
\(s_1=k_1+H(P || M || R).sk_1\)
and where \(H()\) is the hash of the associated byte values, and (\(P || M || R\)) is appended byte values from \(M\) and \(R\). The overall public key (\(P\)) will be computed by the adding of Bob and Wendy's public key. Wendy will generate her private key (\(sk_2\)) and derive her public key from:
\(P_2=sk_2.G\)
She will then generate:
\(R_2=k_2.G\)
\(s_2=k_2+H(P || M || R) . sk_2\)
and where the public key to sign the message will be:
\(P=P_1+P_2\)
Bob then sends the message (\(M\)) and the signature (\(R,s\)) to Alice. The signature becomes:
\(R=R_1 + R_2\)
\(s=s_1 + s_2\)
When Alice received the signature (\(R,s\)) and the message (\(M\)), she checks:
\(R+H(P || M || R).P = sG\)
If they are the same, the signature checks out.
Doodle
And here's a doodle:
And for MuSig:
References
[1] Maxwell, G., Poelstra, A., Seurin, Y., & Wuille, P. (2019). Simple schnorr multi-signatures with applications to bitcoin. Designs, Codes and Cryptography, 87(9), 2139-2164.
Presentations