In this article, I will roughly explain the concept of BLS signatures, which have an interesting property known as aggregation.
What does this mean? If you have 10 signatures, you normally have to verify each one individually. In blockchain, for example, if validators vote for a block, they must send their signatures as acknowledgment for that block. Moving these signatures around is not efficient at all. If you have 100,000 validators, storing all of their signatures within a block requires a lot of space.
Additionally, if you build a ZKP circuit to verify validator signatures, the circuit size may grow with the number of validators. You might use recursive proofs to divide validator signatures into smaller subsets before using ZKP, then use recursive proofs to aggregate them later. But this still requires a lot of computational power.
It would be better if we could aggregate multiple signatures into one, where we only need to store or verify that single aggregated signature. This would help reduce complexity and storage significantly.
BLS signatures can achieve this. Even Ethereum 2.0 uses BLS signatures. So, without further introduction, letβs dive right in.
Letβs begin with a little math: PAIRING!
Starting with some basic group theory, roughly speaking, a group is a set of elements and a binary operation, ββ. For a set and operation to be considered a group, they must satisfy four fundamental properties:
Closure: For any elements and in the group, the result of is also in the group.
Associativity: For any three elements , , and in the group, the relationship holds true.
Identity Element: There is an element in the group such that every element satisfies the equation .
Inverses: Each element in the group has a corresponding element such that , where is the identity element.
A cyclic group of order means that there are elements in this group, with a generator . Every element in can be expressed as for in . From here on, we will consider only cyclic groups. Thus, the group comprises elements .
Note that I will use multiplicative notation ββ throughout the discussion. This means that for , and . Here, and can be written using the generator as and , where . So, .
Pairing is a function that maps two elements from groups and with the same order to the target group . That is . A pairing useful in cryptography normally requires two properties:
Bilinearity: , where and .
Non-degeneracy: , where is the identity element in .
My intuition is that bilinear pairing gives us a way to multiply two scalars hidden under group elements without knowing their actual values, and . Thus, .
To elaborate:
"Two scalars hidden" means: given , we know its final value but not due to the discrete log problem. So, given and , we only know that they are elements of and , but not and .
If , we can add and using the group operation even though we donβt know them. Assume and , where is the generator of . Using the group operation on and , we get . But we canβt do something like unless we know (or ). Pairing helps with this.
The important property we want for BLS signatures is bilinearity. Letβs see why.
From these properties, we have and .
To sign a message using this pairing, pick a private key from , where is the group order of and . Let be a generator of . We can immediately get the public key .
Since can be of arbitrary length, we need to first hash it to . But this hash is special; we need the result to be in the group , not a regular number. One can do this by hashing it, getting the result, and then treating the result as the -coordinate of a point on the curve. Since elliptic curves have two -values for one -coordinate, we can just use the smaller one. For more detail, you can read from this Medium article.
The signature for the message is .
To verify that the signature is valid, given that everyone knows the signer's public key , one can check the validity using the pairing, the public key, the signature, and the hash of the message by:
If the result of is equal to , then the signature is valid.
Now, the climax: we want to aggregate multiple signatures into one. Assume we have signers with private keys , and they all sign the same message .
Let be the signatures of the 1st to the -th signers, respectively. The aggregated signature is:
The same goes for the aggregated public key:
Now, any verifier can verify that the aggregated signature is valid and corresponds with the aggregated public key by checking:
Let's show that this is correct:
Thatβs it! We have learned about BLS signatures. In the next article, I will explain Lagrange interpolation, which will lead us to threshold BLS signatures.