BLS Signatures
$$ \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}} $$
Previously I wrote about several elliptic curve signature schemes. I did not cover pairing based ones. These allow for some great aggregation schemes. so let's cover those now.
Background
Hash to curve
Let $\h_{\mathcal S} : \mathcal I → \mathcal S$ be a hash function mapping some input set $\mathcal I$ to the output set $\mathcal S$. A superscript like $\h'$ is used to indicate two domain separated hash functions.
Securely generating elliptic curve points from binary noise is challenging. The naive solution of multiplying by a generator is not secure, since the discrete logarithm is known. The BLS paper introduced the first solution: repeatedly trying $x$ coordinates until a valid curve point is found. This method is generic but not constant time. Constant time methods exists but are curve specific.
Pairing curves
Let $\G_1$, $\G_2$, $\G_3$ be elliptic curve groups with the same scalar field $\F$, generators $\g_1$, $\g_2$, $\g_3$ and a pairing $\e: \G_1 × \G_2 → \G_3$.
A pairing is a function that satisfies $\e(a ⋅ A, b ⋅ B) = a ⋅ b ⋅ \e(A, B)$ and is not the trivial solution $\e(\dummyarg,\dummyarg) = 0$. From this it follows that $\e(A_1 + A_2, B) = \e(A_1, B) + \e(A_2, B)$ and other useful linear properties.
Note. The pairing is symmetrical in $\G_1$ and $\G_2$ so protocols also work with groups and pairing arguments swapped. This is useful if one group has better performance than the other.
Finding a pairing that satisfy the requirements is challenging, especially when there are additional constraints such as having large binary roots of unity in $\F$. Different families of solutions have been found:
- MNT, Miyaji-Nakabayashi-Takano (2001; paper).
- BLS, Barreto-Lynn-Scott (2002; paper).
- BN, Barreto-Naehrig (2005; paper).
- KSS, Kachisa-Schaefer-Scott (2008; paper).
Two important specific solutions are
Note. The 128 in alt_bn128
revers to the target security level, but it was since found that it is "closer to 96 or so". BLS12-381
development was in part motivated to address this and targets 128 bit security.
Signature aggregation
Like with elliptic curve protocols, the private key is a random scalar field element $x ∈ \F$ and the public key is the private key times a generator $X = x ⋅ \g_2$. However, this alone is not secure in pairing cryptography due to the rogue key attack that I will explain later. We need to prove that we actually know the private key, a proof of possession. To do this compute and publish
$$ S_X = x ⋅ \h_{\G_1}'(X) $$
Now anyone with $(X, S_X)$ can verify the public key using
$$ \e(S_X, \g_2) = \e(\h_{\G_1}'(X), X) $$
Details
$$ \begin{aligned} \e(S_X, \g_2) &= \e(\h_{\G_2}'(X), X) \\ \e(x ⋅ \h_{\G_2}'(X), \g_2) &= \e(\h_{\G_2}'(X), x ⋅ \g_2) \\ x ⋅ \e(\h_{\G_2}'(X), \g_2) &= x ⋅ \e(\h_{\G_2}'(X), \g_2) \\ \end{aligned} $$
In the following I will assume all public keys have had their proofs of possession checked.
One signer, one message
To sign a message $m$, hash the message $H = \h_{\G_1}(m)$ and the signature is $S = x ⋅ H$.
To verify, hash the message $H = \h_{\G_1}(m)$ and check
$$ \e(S, \g_2) = \e(H, X) $$
Details
$$ \begin{aligned} \e(S, \g_2) &= \e(H, X) \\ \e(x ⋅ H, \g_2) &= \e(H, X) \\ x ⋅ \e(H, \g_2) &= \e(H, x ⋅ \g_2) \\ x ⋅ \e(H, \g_2) &= x ⋅ \e(H, \g_2) \\ \end{aligned} $$
Many signers, many messages
To aggregate many signatures, we simply sum them
$$ S = S_1 + S_2 + S_3 + ⋯ $$
Then to verify, we compute all the hashes for the messages $H$ and check
$$ \e(S, \g_2) = \e(H_1, X_1) + \e(H_2, X_2) + \e(H_3, X_3) + ⋯ $$
Many signers, one message
In the case where all messages are the same, the verification simplifies to only two pairing operations:
$$ \e(S, \g_2) = \e(H, X_1 + X_2 + X_3 + ⋯) $$
Threshold signatures
BLS signatures also allows for a threshold signature scheme. For a scheme where $m$ out of $n$ signatories can sign we first do a setup: Assign every signer $i$ a unique $a_i ∈ \F$ and pick another unique $a ∈ \F$ that we will need soon. These values $a$ are public. Use a distributed key generation protocol to create a random $m$-term polynomial $P ∈ \F[X]$ and provide all the signers with private keys $x_i = P(a_i)$ and public keys $X_i = x_i ⋅ G_2$. Also compute the verification public key $X = P(a) ⋅ \g_2$. This is basically Shamir's Secret Sharing scheme where each private key is a share of the private to the verification key.
Signing is as with plain BLS signatures. Given message $m$ compute $H = \h_{\G_1}(m)$. Each signer computes their signature $S_i = x_i ⋅ H$.
To aggregate the treshold, first verify the individual signatures using plain BLS verification. Take $\mathcal I$ to be the set of indices $i$ of valid signatures. Compute the Lagrange interpolation weights $w_i ∈ \F$ as
$$ w_i = \prod_{j ∈ \mathcal I \setminus \set{i}} \frac{a - a_j}{a_i - a_j} $$
where the $j$'s range over all valid signatory indices except $i$. Compute the aggregate signature
$$ S = \sum_{i ∈ \mathcal I} w_i ⋅ S_i $$
The aggregate signature $S$ is now a valid BLS signatured for $m$ for the verification public key $S$:
$$ \e(S, \g_2) = \e(H, X) $$
Details
$$ \begin{aligned} \e(S, \g_2) &= \e(H, X) \\ \e\p{\sum_{i ∈ \mathcal I} w_i ⋅ S_i, \g_2} &= \e(H, P(a) ⋅ \g_2) \\ \e\p{\sum_{i ∈ \mathcal I} w_i ⋅ x_i ⋅ H, \g_2} &= P(a) ⋅ \e(H, \g_2) \\ \p{\sum_{i ∈ \mathcal I} w_i ⋅ x_i} ⋅ \e\p{H, \g_2} &= P(a) ⋅ \e(H, \g_2) \\ \sum_{i ∈ \mathcal I} w_i ⋅ x_i &= P(a) \\ \sum_{i ∈ \mathcal I} P(a_i) ⋅ \prod_{j ∈ \mathcal I \setminus \set{i}} \frac{a - a_j}{a_i - a_j} &= P(a) \\ \end{aligned} $$
This final relation is the Langrange interpolation formula evaluated at $a$, it holds if $\abs{\mathcal I} ≥ m$.
Rogue key attack
The proof-of-possession is sometimes omitted. This makes the system vulnerable to the rogue key attack where an attacker can co-sign with forged signatures making it look like both attacker and one or more victims signed a message $m$. I'll cover the one victim case:
Given victim public key $X$, the attacker generates a random private key $a ∈ \F$ and computes a rogue public key $A = a ⋅ \g_2 - X$. The attacker signs a message $H$ as usual $S = a ⋅ H$. Now $S$ looks like the aggregate signature of $A$ and $X$ on a common message $H$:
$$ \e(S, \g_2) = \e(H, A) + \e(H, X) $$
Details
$$ \begin{aligned} \e(S, \g_2) &= \e(H, A) + \e(H, X) \\ \e(a ⋅ H, \g_2) &= \e(H, a ⋅ \g_2 - X) + \e(H, X) \\ a ⋅ \e(H, \g_2) &= a ⋅ \e(H, \g_2) - \e(H, X) + \e(H, X) \\ a ⋅ \e(H, \g_2) &= a ⋅ \e(H, \g_2) \end{aligned} $$
Besides proof-of-possession that was used above, there are two other notable mitigation strategies (see Boneh, Drijvers & Neven (2018)). For the first, note that the attack requires the messages to be the same. Making sure that every signer signs a different message avoids the attack. One way of achieving this is including the public key in each message:
$$ H = \h_{\G_1}\p{X, m} $$
Since this makes all messages distinct, we can no longer use the "many signers, one message" optimization. A second mitigation strategy is to modify the aggregation method. To aggregate a set of signatures $\mathcal I$ we first compute pseudorandom constants $c_i$ for each signer
$$ c_i = \h_{\F}\p{X_i, \setb{X_j}{j ∈ \mathcal I}} $$
Note These $c_i$ are a function of the whole set of signatories. Simplifying it to $c_i = \h_{\F}(X_i)$ is not enough. This means each $c_i$ will have to be recomputed everytime the set of signatories changes.
Using these $c_i$, we aggregate signatures as
$$ S = \sum_{i∈\mathcal I} c_i ⋅ S_i $$
Signature aggregation is no longer associative. In fact, it can only be done once all signers are known. To verify the aggregate signature we use a correspondingly modified check
$$ \e(S, \g_2) = \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ X_i) $$
Details
$$ \begin{aligned} \e(S, \g_2) &= \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ X_i) \\ \e\p{\sum_{i∈\mathcal I} c_i ⋅ S_i, \g_2} &= \sum_{i∈\mathcal I} \e(H_i, c_i ⋅ x_i ⋅ \g_2) \\ \sum_{i∈\mathcal I} c_i ⋅ \e\p{x_i ⋅ H_i, \g_2} &= \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e(H_i, \g_2) \\ \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e\p{H_i, \g_2} &= \sum_{i∈\mathcal I} c_i ⋅ x_i ⋅ \e(H_i, \g_2) \\ \end{aligned} $$
This method also optimizes to two pairings in the repeated message case
$$ \e(S, \g_2) = \e\p{H, \sum_{i∈\mathcal I} c_i ⋅ X_i} $$
Other gotchas
The BLS signature scheme is very linear. This enables all the useful aggregation schemes above, but also allows for a number of unexpected things. Linearity in the public key allows the rogue key attack. This is why we need proof-of-possession.
Linearity in the private key has interesting behaviour around zero. For example a zero private key produces signatures valid for all messages: $S = 0 ⋅ \h_{\G_1}(m) = 0$. This is mitigated by rejecting the public key $0 ⋅ \g_2$. But this is not enough.
Two colluding signers pick private keys $a_1$ and $a_2 = -a_1$ and register their public keys $A_1 = a_1 ⋅ \g_2$ and $A_2 = a_2 ⋅ \g_2$. Now anyone can claim $A_1$ and $A_2$ are part of any aggregate signature with any message. Given a batch signature $S = \sum_i x_i ⋅ H_i$ such that
$$ \e(S, \g_2) = \sum_i \e(H_i, X_i) $$
Then $S$ also verifies with $A_1$ and $A_2$ signing an arbitrary message $H$:
$$ \e(S, \g_2) = \e(H, A_1) + \e(H, A_2) + \sum_i \e(H_i, X_i) $$
Details
$$ \begin{aligned} \e(S, \g_2) &= \e(H, A_1) + \e(H, A_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= \e(H, a_1 ⋅ \g_2) + \e(H, a_2 ⋅ \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= a_1 ⋅ \e(H, \g_2) + a_2 ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= (a_1 + a_2) ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= 0 ⋅ \e(H, \g_2) + \sum_i \e(H_i, X_i) \\ \e(S, \g_2) &= \sum_i \e(H_i, X_i) \\ \end{aligned} $$
This generalizes to more complex linear relations among the public keys.
Linearity in the signatures can be exploited to create two signatures that are individually invalid, but their aggregate is valid. Start with two valid signatures $S_1, S_2$ and an arbitrary non-zero point $P ∈ \G_1$, then compute the two new signatures
$$ \begin{aligned} S_1' &= S_1 + P & S_2' &= S_2 - P \end{aligned} $$
References
-
Dan Boneh, Ben Lynn & Hovav Shacham (2001). "Short Signatures from the Weil Pairing". pdf
-
A. Faz-Hernandez et al. (2021). "Hashing to Elliptic Curves". IETF Draft. link.
-
Dan Boneh et al. (2020). "BLS Signatures". IETF Draft. link
-
Sean Bowe (2017). "BLS12-381: New zk-SNARK Elliptic Curve Construction" link
-
Thomas Ristenpart & Scott Yilek (2007). "The Power of Proofs-of-Possession". pdf.
-
Nguyen Thoi Minh Quan (2021). "Attacks and weaknesses of BLS aggregate signatures". pdf.
-
Dan Boneh, Manu Drijvers & Gregory Neven (2018). "Compact Multi-Signatures for Smaller Blockchains". pdf
-
Dan Boneh, Manu Drijvers & Gregory Neven (2018). "BLS Multi-Signatures With Public-Key Aggregation". link