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 <firstname.lastname@example.org> Type: Informational Created: <YYYY-MM-DD> Updated: <YYYY-MM-DD>
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.
This LIP is licensed under the Creative Commons Zero 1.0 Universal.
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 real-world 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.
The BLS signature scheme as specified in the IETF draft “BLS Signatures draft-irtf-cfrg-bls-signature-04” is used. More specifically, the ciphersuite BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_ is chosen. This ciphersuite uses the proof of possession scheme and the minimal-pubkey-size variant.
The ciphersuite exposes the following functions:
AggregateVerify is, however, not used here. How and when the remaining functions are used is specified in the following subsection.
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
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).
In order to use a BLS keypair
(sk, pk) for on-chain signatures, the public key
pk of the keypair must first be registered on-chain via some transaction. Otherwise, every transaction or block that needs to verify a signature for
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
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 on-chain, 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
sk is the matching secret key. During the validation of the delegate registration transaction, it must be checked that
PopVerify(pk, prf) returns
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
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 i-th 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 i-th entry specifies the weight for the i-th public key in
keysList and a weight 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 i-th 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
verifyWeightedAggSig will fail.
We choose the variant minimal-pubkey-size 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 minimal-pubkey-size functionality of BLS libraries is significantly used and tested in practice and can be relied on.
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.
FastAggregateVerifyrequires only two pairing operations whereas
n+1 pairing operations where
n is the number of individual signatures that are aggregated. Note that pairing operations are very expensive.
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.
This LIP is purely informational. Therefore, it does not imply any incompatibilities.
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 ASCII-encoded string with the space symbol (0x20) between two words. The user needs to remember or store safely the passphrase.
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 AES-256-GCM, 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.
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 AES-256-GCM, 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.
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.