# My Lecture Note 1: BLS Signatures

By [Fieldlnwza007](https://paragraph.com/@fieldlnwza007) · 2024-05-29

---

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, “$$\\cdot$$”. For a set and operation to be considered a group, they must satisfy four fundamental properties:

1.  **Closure**: For any elements $$a$$ and $$b$$ in the group, the result of $$a \\cdot b$$ is also in the group.
    
2.  **Associativity**: For any three elements $$a$$, $$b$$, and $$c$$ in the group, the relationship $$(a \\cdot b) \\cdot c = a \\cdot (b \\cdot c)$$ holds true.
    
3.  **Identity Element**: There is an element $$e$$ in the group such that every element $$a$$ satisfies the equation $$e \\cdot a = a \\cdot e = a$$.
    
4.  **Inverses**: Each element $$a$$ in the group has a corresponding element $$a^{-1}$$ such that $$a \\cdot a^{-1} = a^{-1} \\cdot a = e$$, where $$e$$ is the identity element.
    

A cyclic group of order $$p$$ means that there are $$p$$ elements in this group, with a generator $$g$$. Every element in $$G$$ can be expressed as $$g^m$$ for $$m$$ in $${0, 1, ..., p - 1}$$. From here on, we will consider only cyclic groups. Thus, the group $$G$$ comprises elements $${g^0, g^1, ..., g^{p-1}}$$.

Note that I will use multiplicative notation “$$\\cdot$$” throughout the discussion. This means that for $$u, v \\in G$$, and $$u \\cdot v = w \\in G$$. Here, $$u$$ and $$v$$ can be written using the generator as $$g^x$$ and $$g^y$$, where $$x, y \\in {0, 1, ..., p - 1}$$. So, $$u \\cdot v = g^x \\cdot g^y = g^{x+y} = w \\in G$$.

Pairing is a function $$e$$ that maps two elements from groups $$G\_1$$ and $$G\_2$$ with the same order to the target group $$G\_t$$. That is $$e: G\_1 × G\_2 → G\_t$$. A pairing useful in cryptography normally requires two properties:

1.  **Bilinearity**: $$e(u^a, v^b) = e(u, v)^{ab}$$, where $$u \\in G\_1$$ and $$v \\in G\_2$$.
    
2.  **Non-degeneracy**: $$e(g\_1, g\_2) \\neq I\_{G\_t}$$, where $$I\_{G\_t}$$ is the identity element in $$G\_t$$.
    

My intuition is that bilinear pairing gives us a way to multiply two scalars hidden under group elements without knowing their actual values, $$a$$ and $$b$$. Thus, $$e(u^a, v^b) = e(u, v)^{ab}$$.

To elaborate:

1.  "Two scalars hidden" means: given $$u^a$$, we know its final value but not $$a$$ due to the discrete log problem. So, given $$u^a$$ and $$v^b$$, we only know that they are elements of $$G\_1$$ and $$G\_2$$, but not $$a$$ and $$b$$.
    
2.  If $$u, v \\in G\_1$$, we can add $$x$$ and $$y$$ using the group operation even though we don’t know them. Assume $$u = g^x$$ and $$v = g^y$$, where $$g$$ is the generator of $$G\_1$$. Using the group operation on $$u$$ and $$v$$, we get $$u \\cdot v = g^x \\cdot g^y = g^{x+y}$$. But we can’t do something like $$g^{xy} = (g^x)^y = u^y$$ unless we know $$y$$ (or $$x$$). Pairing helps with this.
    

The important property we want for BLS signatures is bilinearity. Let’s see why.

From these properties, we have $$e(u^a, v^b) = e(u, v)^{ab}$$ and $$e(u, v^b) = e(u, v)^b = e(u^b, v)$$.

To sign a message $$M$$ using this pairing, pick a private key $$sk$$ from $${1, ..., q - 1}$$, where $$q$$ is the group order of $$G\_1$$ and $$G\_2$$. Let $$g$$ be a generator of $$G\_1$$. We can immediately get the public key $$pk = g^{sk}$$.

Since $$M$$ can be of arbitrary length, we need to first hash it to $$H(M)$$. But this hash is special; we need the result to be in the group $$G\_2$$, not a regular number. One can do this by hashing it, getting the result, and then treating the result as the $$x$$-coordinate of a point on the curve. Since elliptic curves have two $$y$$-values for one $$x$$-coordinate, we can just use the smaller one. For more detail, you can read from [this Medium article](https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716).

The signature for the message $$M$$ is $$S = H(M)^{sk} \\in G\_2$$.

To verify that the signature is valid, given that everyone knows the signer's public key $$pk$$, one can check the validity using the pairing, the public key, the signature, and the hash of the message by:

$$e(pk, H(M)) = e(g^{sk}, H(M)) = e(g, H(M)^{sk}) = e(g, S)$$

If the result of $$e(pk, H(M))$$ is equal to $$e(g, S)$$, then the signature is valid.

**Now, the climax: we want to aggregate multiple signatures into one.** Assume we have $$n$$ signers with private keys $$sk\_1, sk\_2, ..., sk\_n$$, and they all sign the same message $$M$$.

Let $$S\_1, S\_2, ..., S\_n$$ be the signatures of the 1st to the $$n$$-th signers, respectively. The aggregated signature is:

$$S\_{agg} = S\_1 \\cdot S\_2 \\cdot ... \\cdot S\_n = H(M)^{sk\_1} \\cdot H(M)^{sk\_2} \\cdot ... \\cdot H(M)^{sk\_n} = H(M)^{sk\_1 + sk\_2 + ... + sk\_n}$$

The same goes for the aggregated public key:

$$pk\_{agg} = pk\_1 \\cdot pk\_2 \\cdot ... \\cdot pk\_n = g^{sk\_1} \\cdot g^{sk\_2} \\cdot ... \\cdot g^{sk\_n} = g^{sk\_1 + sk\_2 + ... + sk\_n}$$

Now, any verifier can verify that the aggregated signature is valid and corresponds with the aggregated public key by checking:

$$e(pk\_{agg}, H(M)) = e(g, S\_{agg})$$

Let's show that this is correct:

$$e(pk\_{agg}, H(M)) = e(g^{sk\_1 + sk\_2 + ... + sk\_n}, H(M)) = e(g, H(M)^{sk\_1 + sk\_2 + ... + sk\_n}) = e(g, S\_{agg})$$

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.

---

*Originally published on [Fieldlnwza007](https://paragraph.com/@fieldlnwza007/my-lecture-note-1-bls-signatures)*