BLS Deep Dive

Oleg Nikolayev
Feb 5 · 5 min read

By Oleg Nikolayev and Artem Payvin

Hello, everyone!

In this article, we are going to be covering the Boneh-Lynn-Shacham (BLS) signature scheme and the implementation at SKALE.

Note: If you are interested in using BLS, we are going to be open sourcing our library in the coming weeks — stay in touch with us in our Discord for developer updates!

To begin, why are we interested in BLS / aggregate signatures?

Multi-signature Verification

Traditional multi-signature verification is slow and cumbersome — it requires multiple communication rounds to ensure that m of n participants have signed. And in the case of consensus protocols, such schemes require all signatures to be stored across the entire network. But, in the case of BLS, an aggregate signature can be made from some threshold of signatures shares and stored across the network in lieu of these disparate signatures.

Such a mechanism allows for smaller network overhead in the form of traffic / storage and also provides for faster verification of signatures and thresholds. These efficiencies have helped to contribute to the 20k TPS that SKALE has managed to achieve in its early SKALE-Chain implementations.

The first step in this our implementation is known as Distributed Key Generation (DKG) where we securely generate keys for each of n participants, where any threshold t + 1 of n participants could sign a message for a whole group.

Distributed Key Generation (DKG)

At SKALE, we use a modified version of the Joint-Feldman Protocol which uses sets of points on elliptic curves supported by Ethereum. At a high level, we have two sets of points on the elliptic curves:

Note: Secret keys are from the Fp group. Public key(s) are from G₂. Signature and message hashes are from the G₁ group, where G₁ is an additive subgroup of E₁ generated by point P₁ and G₂ is an additive subgroup of E₂ generated by point P₂. It is known that G₁ and G₂ are the only cyclic groups of order q on E₁ and E₂ respectively (with well-chosen P₁ and P₂). p and q are 256-bit prime numbers.

Given these two sets, the following takes place in SKALE’s DKG smart contract on the Ethereum Mainnet:

Note: For more information on DKG, please check out the Wikipedia article on it (academic paper is viewable by purchase only). All additional information about Ethereum cryptography you can search at the Yellowpaper at Appendix E. Precompiled Contracts.

After each node knows its own secret key and the group’s public verification value has been stored in the SKALE DKG smart contract, node(s) can create verifiable BLS signatures.

Boneh-Lynn-Shacham (BLS)

Before moving into implementation, it is important to first understand the following information problems:

Computational Diffie-Hellman

In a cyclic group, if you know: (g, g * x, g * y), determine g * xy.

Decisional Diffie-Hellman

In a cyclic group, if you know (g, g * x, g * y, g * z), determine if zxy

Co-decisional Diffie-Hellman

In two cyclic groups, if you know (a, a * x, b, b * y) where aG₁ and bG₂, determine if xy.

BLS uses a ‘pairing’ to make the Computation and Decisional problems hard in both groups, but the Co-decisional problem easy. To begin with our BLS, we first need a function known as a ‘Bilinear Mapping’.

Note: BLS has been around for >10 years and is provably secure with one additional assumption of hardened implementations (this just means that it has only been implemented over the past <5 years whereas ECDSA and others have been live for >20).

Bilinear Mapping

A Bilinear mapping is a function with the special property that moving around exponents or multiplying doesn’t matter / change the result. At SKALE, we use a bilinear mapping for additive abstract groups with the property that multiplying does not change the result.

Bilinear map for additive abstract groups G₁, G₂, Fp₁₂

Note: SKALE uses this implementation based on this scheme.

Signature Scheme

This function allows us to create the a signature scheme where we multiply the secret key by the hash of the message to create our signature. The BLS signature scheme is represented below:

Note: The source of randomness for selecting x is provided by the libff C++ library for finite fields and elliptic curves.

For verification, we check if the pairing of the signature and our generator point in E₂ is equal to the pairing of message hash and the public key.

verification scheme

Aggregate Signatures

For verification, we check if the pairing of the sum of the aggregated signatures multiplying by corresponding Lagrange coefficients and our generator point on E₂ is equal to the pairing of message hash and the common public key.

verification of aggregate signatures

Note: you can check for yourself that:

Learn More

With DKG and BLS, SKALE has managed to exceed over 20k transactions and achieve finality in its SKALE-Chains. We are currently working on tooling for this technology to provide an open source implementation to the Ethereum community. If you’d like to learn more about our efforts, make sure to join our developer community on Discord and check out our Developer Documentation!

Also, feel free to also check out our Technical Overview and Consensus Overview for a deeper dive into how SKALE works and is able to provide 20,000 TPS.

SKALE’s mission is to make it quick and easy to set up a cost-effective, high-performance sidechain that runs full-state smart contracts. We aim to deliver a performant experience to developers that offers speed and functionality without giving up security or decentralization.

Follow us here on Telegram, Twitter, Discord, and sign up for updates via this form on the SKALE website.

Thanks to Eric Olszewski

Oleg Nikolayev

Written by

Software Developer @skalelabs



Thoughts, ideas, and musings from the SKALE Foundation

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade