Skip to content

Schnorr Signature Aggregation

Table of contents

Open Table of contents

What it is

Schnorr’s Signature Protocol can be used in a setup so that the secret key is shared among a group of users such that a valid signature can only be produced if those users collaborate.

The secret key is split-up and shared in a way such that it’s never reconstructed in one central place. This way an attacker would need to compromise all involved parties to produce a valid signature.

How it works

As a prerequisite, it’s useful to have a basic understanding of Schnorr Signatures before continuing.

We’ll be working with an Elliptic Curve EE that is of order qq and has a generator GG.

In our example, Alice and Bob collaborate to produce a valid signature which Carol will validate.

Note: In our example, every parameter Alice generates uses the subscript 1_1, whereas all the parameters Bob generates use the subscript 2_2.

The first step is for Alice and Bob to generate their private- and public keys.

x1$Zqx_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q X1=x1GX_1 = x_1G x2$Zqx_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q X2=x2GX_2 = x_2G

Alice and Bob then share the public values X1X_1 and X2X_2 with each other.

Next up, Alice and Bob generate the random secret nonce value as well as its public derivative:

r1$Zqr_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R1=r1GR_1 = r_1G r2$Zqr_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R2=r2GR_2 = r_2G

Alice and Bob also share the public values R1R_1 and R2R_2 with each other.

Once they’ve received those values, they can compute the shared RR as R=R1+R2R = R_1 + R_2.

As a next step, Alice and Bob compute cc as the hash value of the concatenation of GG, X1X_1, X2X_2 and RR:

c=H(GX1X2R)c = H(G \mathbin\Vert X_1 \mathbin\Vert X_2 \mathbin\Vert R)

The ee values can be computed by Alice and Bob independently as:

e1=r1+cx1modqe_1 = r_1 + cx_1 \mod q e2=r2+cx2modqe_2 = r_2 + cx_2 \mod q

The signature is R=R1+R2R = R_1 + R_2 and e=e1+e2e = e_1 + e_2 which Carol can validate by checking eG=?R+cXeG \overset{?}{=} R + cX as it’s done in a regular Schnorr Signature.

This works because:

eG=R+cX(r+cx)G=rG+cxG(r+cx)G=(r+cx)G\begin{aligned} eG &= R + cX \\ (r + cx)G &= rG + cxG \\ (r + cx)G &= (r + cx)G \end{aligned}

Schnorr Signature Aggregation

Why it works

Carol, the verifier uses the regular Schnorr Signature verification method eG=?R+cXeG \overset{?}{=} R + cX to check the signature for its validity.

Given the linearity of the mathematical operations involved in the Schnorr Signature protocol (mostly addition and multiplication is used) we can calculate RR and ee as the addition of their respective shared values.

Expanding the signature validation equation from above with the knowledge that R=R1+R2R = R_1 + R_2 and e=e1+e2e = e_1 + e_2 we get:

eG=R+cX(e1+e2)G=R1+R2+cX(r1+cx1+r2+cx2)G=r1G+r2G+c(x1G+x2G)(r1+r2+cx1+cx2)G=(r1+r2+cx1+cx2)G(r+c(x1+x2))G=(r+c(x1+x2))G(r+cx)G=(r+cx)G\begin{aligned} eG &= R + cX \\ (e_1 + e_2)G &= R_1 + R_2 + cX \\ (r_1 + cx_1 + r_2 + cx_2)G &= r_1G + r_2G + c(x_1G + x_2G) \\ (r_1 + r_2 + cx_1 + cx_2)G &= (r_1 + r_2 + cx_1 + cx_2)G \\ (r + c(x_1 + x_2))G &= (r + c(x_1 + x_2))G \\ (r + cx)G &= (r + cx)G \end{aligned}

Rogue-Key Attack

It’s important to note that the aforementioned key aggregation scheme isn’t secure under adversarial conditions (when the co-signers can’t trust each other).

The reason being that the last co-signer can wait until all the other co-signers shared their public keys to then compute a “fake” public key that subtracts the other co-signers public keys. This ultimately gives the last co-signer full control over the signature creation.

To show how this would work, let’s take a look at our example where Alice and Bob both create a signature collaboratively. Assuming that Alice shared here public key X1=x1GX_1 = x_1G first, Bob can now generate his public key as X2=x2GX_2 = x_2G but share a “fake” public key with Alice that subtracts her public key from his:

X2=X2X1X_2' = X_2 - X_1

The shared public key XX that’s both derived by Alice and Bob is therefore Bob’s public key:

X=X1+X2=X1+(X2X1)=X2\begin{aligned} X &= X_1 + X_2' \\ &= X_1 + (X_2 - X_1) \\ &= X_2 \end{aligned}

Given this, Bob can now sign without Alice while Carol, the validator would assume that the signature was generated collaboratively.

Fortunately there’s a simple solution to this problem called “Knowledge of Secret Key” (KOSK). All parties participating in the protocol need to not only share their public key but also a signature over that public key to ensure that they also know the private key that was used to derive the public key.

This mitigation works as the adversary computing and sharing the “fake” public key has no way to figure out what its private key would be.

Additional Resources