14
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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}[1]{\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 m)$ and keeps it 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. Hint: 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?)

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.

$\endgroup$
  • $\begingroup$ Squeamish: see my answer/extended comment below for the modern state. $\endgroup$ – cypherfox Mar 12 '18 at 13:39
1
$\begingroup$

Squeamish Ossifrage's answer is great, however a recent paper superseeds 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 [..].

Edit: A high level description

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – NeQuahsu Mar 28 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.