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?
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.
Before moving into implementation, it is important to first understand the following information problems:
In a cyclic group, if you know: (g, g * x, g * y), determine g * xy.
In a cyclic group, if you know (g, g * x, g * y, g * z), determine if z ≟ xy
In two cyclic groups, if you know (a, a * x, b, b * y) where a ∈ G₁ and b ∈ G₂, determine if x ≟ y.
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).
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.
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.
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.
Note: you can check for yourself that:
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!
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.