# Schnorr signatures: multisignature support

Schnorr signature is mentioned as a promising upgrade to bitcoin to improve scalability. It support multisignature, several signatures can be aggregated into a single, new signature. But I fail to find any information on how is this made possible mathematically.

Some of my questions on the statement "several signatures can be aggregated into a single new signature":

1) Is it true that the "several signatures" can be generated using different private key?

2) If (1) is true, the "single new signature" can be used to verify all the messages that are signed by different private key? How does this work?

Is there any paper published regarding to this topic?

Here is a simple-minded Ed25519-based multisignature or collective signature scheme, in which Alice and Bob each having their own private key, kept secret from one another, must work together to create a joint signature that a verifier knowing both of their public keys, or only a joint public key, can verify. This is a simplification of a recent IETF internet-draft, draft-ford-cfrg-cosi, presently under consideration by the CFRG.

$$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\concat}{\mathop{\Vert}}\newcommand{\U}{\underline{#1}}$$Let $$p = 2^{255} - 19$$, a prime; let $$E$$ be the elliptic curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$$ over $$\F_p$$ (edwards25519, the twisted Edwards curve birationally equivalent to Curve25519 used in the Ed25519 signature scheme); let $$P$$ be the unique $$\F_p$$-rational point on $$E$$ whose $$x$$ coordinate is 4/5 and whose $$y$$ coordinate is ‘positive’, and let $$\ell$$ be its order; let $$H$$ be a uniform random choice of function from byte strings to $$\Z/\ell\Z$$; let $$\U Q$$ be some byte string encoding of a point $$Q \in E(\F_p)$$.

To begin, Alice picks a secret scalar $$a \in \Z/\ell\Z$$ and a secret 32-byte hash key $$h_a$$, and shares the encoding of the point $$A = [a]P$$. Bob does likewise with $$b$$, $$h_b$$, and $$B$$. Their joint public key the encoding of is $$A + B$$.

An Alice/Bob signature on a message $$m$$ is the encoding of a point $$R \in E(\F_p)$$ and a scalar $$s \in \Z/\ell\Z$$ such that $$[s]P = R + [H(\U R\concat \U{A+B}\concat m)](A + B).$$

How do Alice and Bob create such a beast? First, Alice computes $$r_a = H(h_a\concat u_a \concat m)$$ where $$u_a$$ is an independent uniform random 32-byte string, and keeps $$r_a$$ secret but shares $$R_a = [r_a]P$$; Bob does similarly with $$r_b$$ and $$R_b$$. Then they each compute $$R = R_a + R_b$$. Next, Alice computes $$s_a = r_a + H(\U R\concat \U{A+B}\concat m)\,a,$$ and Bob computes $$s_b$$ similarly. Finally, to commit the signature creation, they jointly compute $$s = s_a + s_b$$ and reveal $$R$$ and $$s$$.

This is an Alice/Bob signature, because

\begin{align*} [s]P &= [s_a + s_b]P \\ &= [r_a + r_b + H(\U R\concat \U{A+B}\concat m)\,(a + b)]P \\ &= [r_a]P + [r_b]P + [H(\U R\concat \U{A+B}\concat m)][a + b]P \\ &= R_a + R_b + [H(\U R\concat \U{A+B}\concat m)]([a]P + [b]P) \\ &= R + [H(\U R\concat \U{A+B}\concat m)](A + B). \end{align*}

Unlike a naive concatenation of two Ed25519 signatures which takes a net 128 bytes of storage, an Alice/Bob signature takes only 64 bytes of storage, and that remains so no matter how many additional signers you add. Conveniently, the resulting Alice/Bob signature is also an Ed25519 signature under the public key $$\U{A+B}$$, so you can use existing Ed25519 verifiers to verify it.

(Security analysis is left as an exercise for the reader. Hints: Suppose evil Bob knows Alice's public key $$A$$ before the two of them collectively publish the joint key $$P$$. What nefarious deed can Bob commit in that case? If Alice's random number generator is wedged when she makes a signature so it returns the same $$u_a$$ each time, how can Bob exploit that to do something nefarious with Alice?)

This scheme has various properties:

• Each party's part of the signature was generated by a different private key not known to the other parties.
• All parties must agree to make the signature before it will be accepted by a verifier. We could easily extend the definition of a signature to include a list of the signers, and have a verifier require some threshold of signers before accepting it, at the cost of a little extra space to store a signature (as in draft-ford-cfrg-cosi).
• If we adapted it thus to a threshold scheme, the subset of possible signers who did sign it would not be anonymous to a verifier.

There are variations on the theme of multisignatures: are the signers anonymous to one another, are there thresholds, if there are thresholds is the subset of possible signers who did sign revealed to a verifier? You'll have to look closely at exactly what Bitcoin's scheme is to see which properties it provides. For further background, you might read Micali, Ohta, and Reyzin's paper introducing Schnorr multisignatures, or Bellare and Neven's elaboration on it.

• Squeamish: see my answer/extended comment below for the modern state. Mar 12, 2018 at 13:39

Squeamish Ossifrage's answer is great, however a recent paper supercedes it. Consider my answer as an extended comment.

The two important changes are:

1. Key aggregation is supported. A verifier may know either the complete list of cosigners or the aggregate group key. Depending on the use case this may reduce communication.

2. The preliminary commitment phase is removed. This reduces communication and latency.

The Micali-Ohta-Reyzin multi-signature scheme solves this problem [rogue-key attacks] using a sophisticated interactive key generation protocol. [..] However, this scheme does not allow key aggregation anymore since the entire list of public keys is required for verification.

We propose a new Schnorr-based multi-signature scheme which can be seen as a simpler and more efficient variant of the BN scheme. First, we remove the preliminary commitment phase, so that cosigners start right away by sending each others the shares $$R_i$$. Second, we change the way the challenges are computed [..] In other words, we have recovered the key aggregation property enjoyed by the naive scheme, albeit with respect to a more complex aggregated key [..].

• The above answers made sense at the time they were posted, but since then another paper has found that dropping the preliminary commitment phase actually makes the scheme insecure. The authors of the paper that cypherfox cited made updated their scheme to re-introduce the preliminary phase. Mar 28, 2019 at 16:30