Hello everyone,
I would like to propose another LIP for the roadmap objective “Enhance signature scheme”. This LIP specifies how to use BLS signatures within Lisk, including compact aggregate BLS signatures.
I’m looking forward to your feedback.
Here is the complete LIP draft:
LIP: <LIP number>
Title: Introduce BLS signatures
Author: Andreas Kendziorra <andreas.kendziorra@lightcurve.io>
Type: Informational
Created: <YYYYMMDD>
Updated: <YYYYMMDD>
Abstract
This document specifies how to use BLS signatures within Lisk. In particular, it specifies how to create and validate compact aggregate signatures with BLS. The specification consists mainly of a choice of a ciphersuite, i.e., the choice of a concrete BLS variant including the choice of several parameters. Moreover, some guidelines on how to use it within a blockchain created with the Lisk SDK are given.
This document does not specify any concrete applications of BLS signatures nor does it impose any protocol changes. It is purely informational on how to use them if desired. Specific applications need to be defined in separate LIPs.
Copyright
This LIP is licensed under the Creative Commons Zero 1.0 Universal.
Motivation
The purpose of this LIP is to be prepared for use cases where multisignatures for large sets of signers are required but the size of concatenated Ed25519 signatures is too disadvantageous. Cross chain transactions for a trustless interoperability solution are likely candidates for such use cases.
With the BLS variant we choose, several signatures of the same message can be aggregated into a single compact signature with a size of 96 bytes. If we consider, for example, a transaction that requires signatures from 68 active delegates, concatenated Ed25519 signatures would sum up to more than 4.35 kB which is about 45 times larger than an aggregate BLS signature.
Very recent advancements have pushed the BLS signature scheme to a state that gives sufficient confidence in the theory of BLS signatures and in its implementations: The IETF standardization process was initiated and driven forward, several implementations were developed, matured and partially audited, and last but not least, the Ethereum2 Beacon Chain that started running recently adopted BLS, which results in realworld usage of both the BLS scheme as specified in the latest standard draft (version 4 at the time of writing) and the BLS implementations. Note that filecoin is using BLS signatures as well. However, their specification is based on an outdated BLS specification draft.
Specification
The BLS signature scheme as specified in the IETF draft “BLS Signatures draftirtfcfrgblssignature04” is used. More specifically, the ciphersuite BLS_SIG_BLS12381G2_XMD:SHA256_SSWU_RO_POP_ is chosen. This ciphersuite uses the proof of possession scheme and the minimalpubkeysize variant.
The ciphersuite exposes the following functions:
KeyGen
SkToPk
Aggregate

Sign
(identical toCoreSign
) 
Verify
(identical toCoreVerify
) 
AggregateVerify
(identical toCoreAggregateVerify
) FastAggregateVerify
PopProve
PopVerify
The function AggregateVerify
is, however, not used here. How and when the remaining functions are used is specified in the following subsection.
Usage
Keypair Creation
A secret key is created using KeyGen
. The input for KeyGen
must be an infeasible to guess octet string of length at least 32. See the appendix for a recommendation on how to choose this input and on key management.
The public key for a secret key sk
is created by SkToPk(sk)
.
Signing and Verifying
Let m
be a binary message, tag
the correct message tag for m
as specified in the LIP “Use message tags and network identifiers for signatures”, networkIdentifier
the correct network identifier of the chain and sk
a secret key. Then, the signature is computed by signBLS(sk, tag, networkIdentifier, m)
as defined below. The resulting signature sig
in combination with the message m
and the matching public key pk
is verified by verifyBLS(pk, tag, networkIdentifier, m, sig)
. In the following, let tagMessage
be the function defined in the LIP “Use message tags and network identifiers for signatures”.
signBLS(sk, tag, networkIdentifier, m):
taggedMessage = tagMessage(tag, networkIdentifier, m)
return Sign(sk, taggedMessage)
verifyBLS(pk, tag, networkIdentifier, m, sig):
taggedMessage = tagMessage(tag, networkIdentifier, m)
return Verify(pk, taggedMessage, sig).
Public Key Registration and Proof of Possession
In order to use a BLS keypair (sk, pk)
for onchain signatures, the public key pk
of the keypair must first be registered onchain via some transaction. Otherwise, every transaction or block that needs to verify a signature for pk
via Verify
or FastAggregateVerify
must be rejected.
The Lisk protocol could contain several transaction types that perform such a registration. In particular, there could be different registration transactions for different keys, e.g, one for validator public keys and one for public keys of regular accounts. This LIP does not specify any registration transactions. Such transaction types must be defined in separate LIPs. In the following, we just assume there exists such a transaction type which we call register public key transaction. To register the public key of the key pair (sk, pk)
by a register public key transaction, registerPublicKeyTransaction
, the transaction must contain pk
and a proof, prf
, generated by PopProve(sk)
. If prf
does not satisfy PopVerify(pk, prf) == VALID
, then registerPublicKeyTransaction
is invalid and must be rejected. Once registerPublicKeyTransaction
is included, transactions and blocks that require to have a valid signature for pk
can be included in the blockchain.
Example (delegate registration): Delegates will be required to register their BLS public key onchain, which may be included in the delegate registration transactions. Hence, a delegate registration transaction needs to contain the BLS public key, pk
, and a proof, prf
, generated by PopProve(sk)
, where sk
is the matching secret key. During the validation of the delegate registration transaction, it must be checked that PopVerify(pk, prf)
returns VALID
.
Aggregate Signatures and their Verification
We only consider signature aggregation for the case where several signatures for the same message are aggregated.
Each aggregate signature needs to be accompanied by some information that specifies the set of public keys that correspond to the aggregate signature. Here, this is realized using a bitmap. Assume that keyList
is a list that includes all potential public keys that could participate in the signature aggregation. The entries must be pairwise distinct. Moreover, let pubKeySignaturePairs
be a list of pairs of public keys and signatures where all signatures belong to the same message, and all public keys are unique and contained in keyList
. Then, the corresponding aggregate signature and bitmap can be computed via createAggSig(keysList, pubKeySignaturePairs)
as in the pseudo code below. To verify if a signature is an aggregate signature of a binary message m
, the function verifyAggSig
can be used. verifyAggSig(keysList, aggregationBits, signature, tag, networkIdentifier, m)
returns VALID
if and only if signature
is an aggregate signature of the message m
for the message tag tag
, the network identifier networkIdentifier
and for the public keys in keyList
defined by aggregationBits
.
createAggSig(keysList, pubKeySignaturePairs):
aggregationBits = byte string of length ceil(length(keyList)/8) with all bytes set to 0
signatures = []
for pair in pubKeySignaturePairs:
signatures.append(pair.sig)
index = keysList.index(pair.pubkey)
set bit at position index to 1 in aggregationBits
signature = Aggregate(signatures)
return (aggregationBits, signature)
verifyAggSig(keysList, aggregationBits, signature, tag, networkIdentifier, m):
taggedMessage = convert2BLSSignatureInput(tag, networkIdentifier, m)
keys = []
for every i in [0, …, ceil(length(keyList)/8)]:
if ith bit of aggregationBits is set to 1:
keys.append(keysList[i])
return FastAggregateVerify(keys, taggedMessage, signature)
If one wants to additionally validate that the participating public keys satisfy a certain weight threshold, the function verifyWeightedAggSig
can be used. The function takes additionally a list of weights, weights
, where the ith entry specifies the weight for the ith public key in keysList
and a weight threshold threshold
.
verifyWeightedAggSig(keysList, aggregationBits, signature, tag, networkIdentifier, m, weights, threshold):
taggedMessage = convert2BLSSignatureInput(tag, networkIdentifier, m)
keys = []
weightSum = 0
for every i in [0, …, ceil(length(keyList)/8)]:
if ith bit of aggregationBits is set to 1:
keys.append(keysList[i])
weightSum += weights[i]
if weightSum < threshold:
return INVALID
return FastAggregateVerify(keys, taggedMessage, signature)
Note that the public keys in pubKeySignaturePairs
need to be distinct when calling createAggSig.
Otherwise, validation via verifyAggSig
and verifyWeightedAggSig
will fail.
Rationale
Variant minimalpubkeysize
We choose the variant minimalpubkeysize because this one is used in Ethereum2 and filecoin and therefore the only variant that found considerable adoption. This means in particular that only the minimalpubkeysize functionality of BLS libraries is significantly used and tested in practice and can be relied on.
Proof of Possession scheme
Choice of Scheme
We use the proof of possession scheme as we only need the use case of aggregating signatures of the same message, and this scheme allows us to use FastAggregateVerify
for this case. FastAggregateVerify
requires only two pairing operations whereas AggregateVerify
requires n
+1 pairing operations where n
is the number of individual signatures that are aggregated. Note that pairing operations are very expensive.
Why Proofs of Possession?
Using FastAggregateVerify
without requiring proofs of possession is insecure as it allows rogue key attacks. See this blog post for how rogue key attacks work for BLS signatures. To see why simply signing the public key is not a sufficient proof of possession method that defends against powerful attackers (chosen message attack model), see section 4.3 of this paper.
Backwards Compatibility
This LIP is purely informational. Therefore, it does not imply any incompatibilities.
Appendix
Key Management
We propose two ways to manage the keys: using a passphrase and storing the encrypted secret key. Moreover, we discuss below for which use cases the methods are preferred.
Using a Passphrase (BIP 39 Mnemonic)
This approach is similar to the key derivation method for the EdDSA account key pair in Lisk.
To create a new key pair, a passphrase is created according to the BIP 39 specifications, where an initial entropy of 32 bytes is used. In Node.js, this initial entropy can be created, for example, via crypto.randomBytes. The resulting passphrase consists of 24 words.
The passphrase is used as the input for KeyGen
to derive the secret key, where the passphrase is treated as a single ASCIIencoded string with the space symbol (0x20) between two words. The user needs to remember or store safely the passphrase.
Storing Passphrase on a Remote Server
If the secret key is needed on a remote server, the encrypted passphrase must be stored on the server. The passphrase should be encrypted by AES256GCM, and the encryption key should be derived by Argon2d. The password used to derive the encryption key should conform to common guidelines for strong passwords. On the user interface level, the user should be warned otherwise.
Storing Encrypted Secret Key
To create a new key pair, an initial randomness of at least 32 bytes is created, e.g., via crypto.randomBytes. This randomness is used as the input for KeyGen
to derive the secret key. The secret key is encrypted via AES256GCM, where the encryption key is derived by Argon2d. The password used to derive the encryption key should conform to common guidelines for strong passwords. On the user interface level, the user should be warned otherwise. The user needs to store the encrypted secret key (and ideally backs up the encrypted key) and needs to remember or store the password safely.
Choosing the Key Management Method
Using a passphrase is suitable for users that need their key pair only on local machines, e.g., for singing transactions. Users only need to remember or securely store the passphrase for this approach. Storing the encrypted secret key is suitable for users that need the key pair only on some remote server, e.g., a forging node on a remote data center. If the key pair is needed on local machines and on remote servers, there is a tradeoff between the two approaches. The first one requires to remember or store secretly a passphrase and a password, but does not require to store and backup any encrypted data locally. The second one requires to store and backup an encrypted file, but needs to remember or secretly store only one password.
Test Vectors
TBA