My Lecture Note 1: BLS Signatures
May 29th, 2024

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 aa and bb in the group, the result of aβ‹…ba \cdot b is also in the group.

  2. Associativity: For any three elements aa, bb, and cc in the group, the relationship (aβ‹…b)β‹…c=aβ‹…(bβ‹…c)(a \cdot b) \cdot c = a \cdot (b \cdot c) holds true.

  3. Identity Element: There is an element ee in the group such that every element aa satisfies the equation eβ‹…a=aβ‹…e=ae \cdot a = a \cdot e = a.

  4. Inverses: Each element aa in the group has a corresponding element aβˆ’1a^{-1} such that aβ‹…aβˆ’1=aβˆ’1β‹…a=ea \cdot a^{-1} = a^{-1} \cdot a = e, where ee is the identity element.

A cyclic group of order pp means that there are pp elements in this group, with a generator gg. Every element in GG can be expressed as gmg^m for mm in {0,1,...,pβˆ’1}\{0, 1, ..., p - 1\}. From here on, we will consider only cyclic groups. Thus, the group GG comprises elements {g0,g1,...,gpβˆ’1}\{g^0, g^1, ..., g^{p-1}\}.

Note that I will use multiplicative notation β€œβ‹…\cdot” throughout the discussion. This means that for u,v∈Gu, v \in G, and uβ‹…v=w∈Gu \cdot v = w \in G. Here, uu and vv can be written using the generator as gxg^x and gyg^y, where x,y∈{0,1,...,pβˆ’1}x, y \in \{0, 1, ..., p - 1\}. So, uβ‹…v=gxβ‹…gy=gx+y=w∈Gu \cdot v = g^x \cdot g^y = g^{x+y} = w \in G.

Pairing is a function ee that maps two elements from groups G1G_1 and G2G_2 with the same order to the target group GtG_t. That is e:G1Γ—G2β†’Gte: G_1 Γ— G_2 β†’ G_t. A pairing useful in cryptography normally requires two properties:

  1. Bilinearity: e(ua,vb)=e(u,v)abe(u^a, v^b) = e(u, v)^{ab}, where u∈G1u \in G_1 and v∈G2v \in G_2.

  2. Non-degeneracy: e(g1,g2)β‰ IGte(g_1, g_2) \neq I_{G_t}, where IGtI_{G_t} is the identity element in GtG_t.

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

To elaborate:

  1. "Two scalars hidden" means: given uau^a, we know its final value but not aa due to the discrete log problem. So, given uau^a and vbv^b, we only know that they are elements of G1G_1 and G2G_2, but not aa and bb.

  2. If u,v∈G1u, v \in G_1, we can add xx and yy using the group operation even though we don’t know them. Assume u=gxu = g^x and v=gyv = g^y, where gg is the generator of G1G_1. Using the group operation on uu and vv, we get uβ‹…v=gxβ‹…gy=gx+yu \cdot v = g^x \cdot g^y = g^{x+y}. But we can’t do something like gxy=(gx)y=uyg^{xy} = (g^x)^y = u^y unless we know yy (or xx). Pairing helps with this.

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

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

To sign a message MM using this pairing, pick a private key sksk from {1,...,qβˆ’1}\{1, ..., q - 1\}, where qq is the group order of G1G_1 and G2G_2. Let gg be a generator of G1G_1. We can immediately get the public key pk=gskpk = g^{sk}.

Since MM can be of arbitrary length, we need to first hash it to H(M)H(M). But this hash is special; we need the result to be in the group G2G_2, not a regular number. One can do this by hashing it, getting the result, and then treating the result as the xx-coordinate of a point on the curve. Since elliptic curves have two yy-values for one xx-coordinate, we can just use the smaller one. For more detail, you can read from this Medium article.

The signature for the message MM is S=H(M)sk∈G2S = H(M)^{sk} \in G_2.

To verify that the signature is valid, given that everyone knows the signer's public key pkpk, 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(gsk,H(M))=e(g,H(M)sk)=e(g,S)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))e(pk, H(M)) is equal to e(g,S)e(g, S), then the signature is valid.

Now, the climax: we want to aggregate multiple signatures into one. Assume we have nn signers with private keys sk1,sk2,...,sknsk_1, sk_2, ..., sk_n, and they all sign the same message MM.

Let S1,S2,...,SnS_1, S_2, ..., S_n be the signatures of the 1st to the nn-th signers, respectively. The aggregated signature is:

Sagg=S1β‹…S2β‹…...β‹…Sn=H(M)sk1β‹…H(M)sk2β‹…...β‹…H(M)skn=H(M)sk1+sk2+...+sknS_{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:

pkagg=pk1β‹…pk2β‹…...β‹…pkn=gsk1β‹…gsk2β‹…...β‹…gskn=gsk1+sk2+...+sknpk_{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(pkagg,H(M))=e(g,Sagg)e(pk_{agg}, H(M)) = e(g, S_{agg})

Let's show that this is correct:

e(pkagg,H(M))=e(gsk1+sk2+...+skn,H(M))=e(g,H(M)sk1+sk2+...+skn)=e(g,Sagg)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.

Subscribe to Fieldlnwza007
Receive the latest updates directly to your inbox.
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from Fieldlnwza007

Skeleton

Skeleton

Skeleton