Aggregated Schnorr Signatures

In this section we describe a multiparty Schnorr signature scheme for elliptic curves based on the work of Boneh et al. (Compact Multi-Signatures for Smaller Blockchains section 5.1). The same protocol can be found also in the MuSig paper (Simple Schnorr Multi-Signatures with Applications to Bitcoin).

Simple Schnorr Signature

We first start by presenting Schnorr signature algorithm:

The public parameters are (𝔾, q, G) where 𝔾 is a group defined by elliptic curve, q is the order of the groups and G is the generator of the group. To generate a key pair Alice chooses a private signing key x from the allowed set and the corresponding public key will be Y = x ⋅ G. To sign a message m Alice chooses a random number k from the allowed set ℤ_q.

Let R = k ⋅ G, c = H(Y||R||m) where H is a cryptographic hash function H : {0, 1}^* → ℤ_q. Alice calculates s = k + xc and outputs the signature (R, s). Validation is checked simply by:

(1) s ⋅ G = R + c ⋅ Y

This is a key-prefixed variant of the scheme where the public key is hashed together with R, m.

Multiparty Schnorr Signature

Multiparty Schnorr signature scheme, also called multi-signature scheme is a set of protocols between n parties such that they can jointly sign a message. The specific protocol we describe uses hash functions H₀, H₁, H₂ : {0, 1}^* → ℤ_q. These hash functions can be constructed from a single one using proper domain separation The parameters are the same as in the case of single signer signature: (𝔾, q, G).

Key Generation: Each party chooses x and computes Y = x ⋅ G.
Key Aggregation: Compute apk ← H₁(Y_j, {Y₁, ..., Y_n}) ⋅ Y_j

Signing: Signing is an interactive three round protocol:

Round 1: This is a commitment round. Party i chooses r_i at random and compute R_i = r_i ⋅ G. Let t_i ← H₂(R_i). Send t_i to all other signers corresponding to Y₁, ..., Y_n and wait to receive t_j = H₂(R_i) from all other signers j ≠ i.

Round 2: Send R_i to all other signers corresponding to Y_i, ..., Y_n and wait to receive R_j from all other signers j ≠ i. Check that t_j = H₂(R_j) for all j = 1, ..., n.

Round 3: each party:

1. Compute apk - Key Aggregation with public keys Y_i, ..Y_n.

2. Compute a_i = H₁(Y_i, {Y₁, ..., Y_n}).

3. Compute R̂ ← R_j and c ← H₀(R̂, apk, m).

4. Compute s_i ← r_i + c ⋅ x_i ⋅ a_imod q.

5. Send s_i to all other signers and wait to receive s_j from other signers j ≠ i.

6. Compute s ← s_j and output (R̂, s) as the final signature

Validation is the same as in simple Schnorr (eq. 1). Conventions and preferred encodings of points and scalars can be found in https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki. Specifically pay attention that in the proposal  k is not chosen in random but derived from the private key: k = H(x||m)mod q