• Let $G$ be the generator point.
• $sk, pk$ are private and public keys, respectively.
• $H$ is the hash of the message.
• $e$ is the bilinear pairing function.

1. Key Generation:
   • Private Key: $sk\in\mathbb{Z}_q$ (where $q$ is the order of the curve)
   • Public Key: $pk=sk⋅G$ (where $G$ is a generator point on the curve)
2. Signing:
   • Given a message $m$:
     • Hash the message: $h=H(m)$ (now $h$ is an elliptic curve point)
     • Sign the message: $\sigma=sk⋅h$
3. Verification:
   • Given a public key $pk$ and a signature $\sigma$:
     • Verify: $e(pk,h)=e(\sigma,G)$

BLS Aggregated Signature:

1. Aggregation:
   • Given a set of signatures $\sigma_1,\sigma_2,\dots,\sigma_n$ and corresponding public keys $pk_1,pk_2,...,pk_n$:
     • Aggregate Signatures: $\sigma_{agg}=\sigma_1+\sigma_2+\dots+\sigma_n$
     • Aggregate Public Keys: $pk_{agg}=pk_1+pk_2+\dots+pk_n$
2. Verification of Aggregated Signature:
   • Given $\sigma_{agg}$, $pk_{agg}$, and the original message m:
     • Hash the message: $h=H(m)$
     • Verify: $e(pk_{agg},h)=e(\sigma_{agg},G)$

Rogue key attacks

When aggregating signatures over the same message, we need to take care of a possible “rogue public key attack”.

Say your public key is $pk_1$, and the attacker has a secret key, $sk_2$. The attacker publishes $pk'2=sk_2⋅G-pk_1$ as a public key instead of publishing his true public key (that is, his real public key plus the inverse of yours). The attacker can sign a message $H(m)$ with his secret key to make the signature $\sigma=sk_2⋅H(m)$. He then publishes this claiming that it is an aggregate signature that both you and the attacker have signed, and that the aggregate public key is $pk{agg}=pk_1+pk'_2$.

Now, when verifying, his claim checks out: it looks like you signed the message when you didn’t: $e(\sigma,G)=e(sk_2⋅H(m),G)=e(H(m),sk_2⋅G)=e(H(m), pk_1+pk'_2)$

In cases where a threshold is expected to be met, a message can be signed without having a sufficient majority using this attack. One relatively simple defense against this is to force validators to register a “proof of possession” of the private key corresponding to their claimed public key. The attacker doesn’t have the $sk'_2$ corresponding to $pk'_2$. This can be done simply by getting the validator to sign its public key on registration: if the signature validates with that public key then all is well.

BLS Threshold Signature

BLS threshold signatures are a type of cryptographic signature scheme that allows a group of participants to collectively sign a message while maintaining the properties of BLS signatures. In this system, m out of n signatories can sign the same message and verification can be done with a single group public key. To define the signature steps, we need to provide explanations for some terms first:

Share Distribution (Shamir's Secret Sharing):

1. Polynomial Creation:
   • A dealer creates a polynomial $f(x)$ of degree $t$ with a constant term $s$ and random coefficients $a_i$ for $i=1,\dots,t$.
   • $f(x)$ is represented as $f(x)=s+a_1x+a_2x^2+...+a_tx^t$.