BLS Signature changes

Yolan Romailler @anomalroil yolan@protocol.ai

drand primer

Maths stuff:

drand primer

Maths stuff:

drand primer

Maths stuff:

Basically we are using the fact that the pairing operation is bilinear to extract the secret key once from the public key and once from the signature to perform what can also be seen as a kind of key agreement:

Pairing’s magic

Basically we are using the fact that the pairing operation is bilinear to extract the secret key once from the public key and once from the signature to perform what can also be seen as a kind of key agreement:

Pairing’s magic

BLS signature

Basically we are using the fact that the pairing operation is bilinear to extract the secret key once from the public key and once from the signature to perform what can also be seen as a kind of key agreement:

Pairing’s magic

BLS signature

BLS public key

This is the way drand currently works:

• Uses the BLS 12-381 “pairing friendly” curve
• Public key on 𝔾₁
• Signature on 𝔾₂

drand current setup

BLS signature

BLS public key

The BLS 12-381 curve has the following properties:

• 𝔾₁ compressed points can be represented with 381 bits ~ 48 bytes
• 𝔾₂ compressed points can be represented with 2*381 bits ~ 96 bytes
• 𝔾_T only used for comparisons as temporary values, not important

​

Note that currently BLS 12-381 is believed to have a security of ~117 bits according to the latest improvements of attacks.

We don’t foresee any need to “upgrade” to stronger curves in the near future (<5 years), but this could change if attacks get further improved.

BLS 12-381

​

For drand currently it means that:

• The public keys of each nodes and that of the group are all ~ 48 bytes
• Each beacon has a group signature of ~ 96 bytes

Usually the choice of using public keys on 𝔾₁ and signatures on 𝔾₂ is motivated by the fact that the signatures are easily aggregated into a single signature, and therefore it’s interesting to have small public keys since we’ll need each of them to verify an aggregated signature.

However! For drand, this motivation isn’t true, since each beacon has a signature and we’re not doing aggregation of these signatures.

Consequences

Currently beacons are made of:

• Round number encoded as an uint64, 8 bytes
• Signature on 𝔾₂ encoded as a compressed point in hex, 192 bytes
• Randomness (optional since derived from the signature) encoded in hex, 64 bytes

Total: 264 bytes (456 bytes in case of chained randomness with the previous sig.)��"round":3056681,�"randomness":"0f3bcf2d501948ac63d2c262fa73c4a710a1c59be0bb82e57547da839803f56b",�"signature":"b40bae32c874197d6f81f4c45e2e2bf7cde1556b035330f4018670ad2c2e6e33d33c717244692f3829a40516485f62b206b382bafbe492c952cad85b48559d407b644af319cd12f9a51a4b3cce38981c68e26dc1adbaf415b22d94beeb896a74",�"previous_signature":"82e70256e40c83026b983f3b4cdac983e91dbec0a7ac33fca8fbd700965d6d06d10594298ac59223d5bcda8535e9339500adf8239675f81ec25368c1103456243904cd26684df0275234f0e1abcb14e4bff2ac1c69e41cb3a8642a8a8ea4ecce"

Anatomy of a beacon

So, what prevent us from doing BLS the other way around? Swapping it:

• Signatures on 𝔾₁
• Public keys on 𝔾₂

​

Certainly not the pairings, bilinearity applies in the same way to verify the signatures:

What if?

​

On the gas cost side of things, notice that EIP 2537 reads like:

• BLS12_PAIRING - 43000*k + 65000 gas for k pairs of points
• BLS12_MAP_FP_TO_G1 - maps base field element into 𝔾₁: 5500 gas
• BLS12_MAP_FP2_TO_G2 - maps extension field element into the 𝔾₂ point with a gas cost of 75000 gas (13x costlier!)

Do we map to 𝔾₁ or 𝔾₂ currently to verify drand signatures?� - Yes: messages need to be mapped to 𝔾₂ : 75000 gas

What would that change?

​

On the gas cost side of things, notice that EIP 2537 reads like:

• BLS12_PAIRING - 43000*k + 65000 gas for k pairs of points
• BLS12_MAP_FP_TO_G1 - maps base field element into 𝔾₁: 5500 gas
• BLS12_MAP_FP2_TO_G2 - maps extension field element into the 𝔾₂ point with a gas cost of 75000 gas (13x costlier!)

Do we need pairings?� - Yes, with two pairs of points to compare: 43000*2 + 65000 = 151000 gas

What would that change?

​

The new beacons would be made of:

• Round number encoded as an uint64, 8 bytes
• Signature on 𝔾₁ encoded as a compressed point in hex, 96 bytes
• Randomness (optional since derived from the signature) encoded in hex, 64 bytes

Total: 168 bytes, saving 100 bytes per round! (264 bytes for chained randomness)��"round":3056681,�"randomness":"0f3bcf2d501948ac63d2c262fa73c4a710a1c59be0bb82e57547da839803f56b",�"signature":"868f005eb8e6e4ca0a47c8a77ceaa5309a47978a7c71bc5cce96366b5d7a569937c529eeda66c7293784a9402801af31",�"previous_signature":"82e70256e40c83026b983f3b4cdac983e91dbec0a7ac33fca8fbd700965d6d06d10594298ac59223d5bcda8535e93395"

Anatomy of a new beacon

Do BLS the other way around, in order to save gas costs and reduce signature sizes.

• Signature on 𝔾₁
• Public keys on 𝔾₂

​

This would allow us to save ~37% space & bandwidth:

• 168MB instead of 264MB a year for 30s beacons, 1.7GB for 3s network…
• ~443GB of http relay bandwidth instead of ~696GB a month

�

​

​

Proposal

Do BLS the other way around, in order to save gas costs and reduce signature sizes.

• Signature on 𝔾₁
• Public keys on 𝔾₂

​

It would also make the gas cost of drand verification onchain ~25% cheaper:

• From a cost of (43000*2 + 65000) + 75000 = 226000 gas
• To a cost of (43000*2 + 65000) + 5500 = 156500 gas

Same should hold on many other chains.

�

​

​

Proposal

Do BLS the other way around, in order to save gas costs and reduce signature sizes.

• Signature on 𝔾₁
• Public keys on 𝔾₂

​

But note that we cannot re-use the same secret key, sadly, since otherwise anybody could generate signatures by using our previous public key on 𝔾₁

This means we’ll need to deploy that change on a new network.

​

​

​

Proposal

Thank you !

For more information and/or if you want to reach out, go to:

https://drand.love

https://leagueofentropy.com�https://github.com/drand/drand

yolan@protocol.ai

Email

https://twitter.com/anomalroil

Twitter