bls/

README

BLS Signatures

An implementation of the Boneh-Lynn-Shacham (BLS) signatures according to the standard on top of the Barreto-Lynn-Scott (BLS) 12-381 curve. The BLS12-381 curve provides roughly 128-bits of security and BLS is a digital signature with aggregation properties.

We have implemented all three signature schemes described in the standard which are designed to handle rogue-key attacks differently. These three are:

• Basic handles rogue key attacks by requiring all signed messages in an aggregate signature be distinct
• Message Augmentation handles rogue key attacks by prepending the public key to the message during signing which ensures that all messages are distinct for different public keys.
• Proof of Possession handles rogue key attacks by validating public keys in a separate step called a proof of possession. This allows for faster aggregate verification.

Pairing-friendly curves have two generator-groups 𝔾₁, 𝔾₂. Data in 𝔾₂ is twice the size of 𝔾₁ and operations are slower. BLS signatures require signatures and public keys to be in opposite groups i.e. signatures in 𝔾₁ and public keys in 𝔾₂ or signatures in 𝔾₂ and public keys in 𝔾₁. This means one of two things:

• Short public keys, long signatures: Signatures are longer and slower to create, verify, and aggregate but public keys are small and fast to aggregate. Used when signing and verification operations not computed as often or for minimizing storage or bandwidth for public keys.
• Short signatures, long public keys: Signatures are short and fast to create, verify, and aggregate but public keys are bigger and slower to aggregate. Used when signing and verification operations are computed often or for minimizing storage or bandwidth for signatures.

This library supports both of these variants for all three signature schemes. The more widely deployed variant is short public keys, long signatures. We refer to this variant as UsualBls. The other variant, short signatures, long public keys, is named TinyBls. The naming convention follows SigSchemeType[Vt] where Vt is short for variant. For example,

• Usual Bls Basic -> SigBasic: Provides all the functions for the Basic signature scheme with signatures in 𝔾₂ and public keys in 𝔾₁
• Tiny Bls Basic -> SigBasicVt: Provides all the functions for the Basic signature scheme with signatures in 𝔾₁ and public keys in 𝔾₂

One final note, in cryptography, it is considered good practice to use domain separation values to limit attacks to specific contexts. The standard recommends specific values for each scheme but this library also supports supplying custom domain separation values. For example, there are two functions for creating a BLS signing instance:

• NewSigBasic() creates a Basic BLS signature using the recommended domain separation value.
• NewSigBasicWithDst(dst) creates a Basic BLS signature using the parameter dst as the domain separation value such as in the Eth2.0 Spec

Also implemented is Threshold BLS as described in section 3.2 of B03.

• ThresholdKeygen(parts, threshold int) -> ([]*SecretKeyShare, error)
• PartialSign(share *SecretKeyShare, msg []byte) -> *PartialSignature
• CombineSigs(*PartialSignature...) -> *Signature

Security Considerations

Validating secret keys

Low entropy secret keys are a problem since this means an attacker can more easily guess the value and now can impersonate the key holder. Secret keys are derived using trusted random number generators (TRNG). If the TRNG produces bad entropy the secret key will be weak. Secret keys are checked to be non-zero values. A zero value secret key not only fails the entropy test but also yields a public key that will validate any signature.

Malchemy is used to test the entropy of the secret keys. Malchemy runs 5 entropy tests to validate secret keys. This library uses the BLS12-381 curve which has a bias in the modulus which causes malchemy to fail two tests: mean and χ². These two tests do not account for this bias but does not mean the secret keys are not sufficiently random. The keys still pass the Shannon entropy, Monte Carlo Pi calculation, and Serial Correlation Coefficient tests. This is an acceptable pass rate.

Validating public keys

Public keys are ensured to be valid. A valid public key means it represents a valid, non-identity elliptic curve point in the correct subgroup. Public keys that are the identity element mean any signature would pass a call to verify.

Validating signatures

Generated signatures are ensured to be valid. A valid signature means it represents a valid, non-identity elliptic curve point in the correct subgroup. Signatures that are the identity element mean any signature would pass a call to verify. Verify checks signatures for non-identity elements in the correct subgroup before checking for a valid signature.

Mitigating Rogue Key Attacks

A rogue key attacks can only happen to multisignature or aggregated signature. A rogue key attack is where at least one party produces a valid but malicious public key such that the multisignature requires less than the threshold to verify a signature. There are two ways to mitigate rogue key attacks: Guarantee all signed messages are unique or validate each public key before use. This library offers both solutions.

Comparison to other BLS implementations and integrations

This library has been tested to be compatible with the following implementations by randomly generating millions of keys and signatures and importing and verifying between the two libraries.

1. Ethereum's py_ecc
2. PhoreProject Go BLS
3. Herumi's BLS
4. Algorand's Rust BLS Sig
5. Miracl's Rust and Go BLS sig

The most common and high risk failures that can occur with library implementations are low entropy secret keys, malformed public keys, and invalid signature generation.

Low entropy secret keys are a problem since this means an attacker can more easily guess the value and now can impersonate the key holder.

Malformed public keys and signatures result in invalid addresses and no ability to withdraw funds.

To check for these problems, We tested millions of keys/signatures (vs say thousands or hundreds) to prove that

1. The odds of producing an invalid key/signature is already theoretically low 2^-255
2. The results of running millions of checks shows that nothing bad happened in 10M attempts

In other words, keys and signatures generated from these libraries can be consumed by this library and visa-versa.

Some of the libraries, namely Algorand's and Miracl's implementations for hash to curve were either out of date or not compliant with the IETF Spec. This meant that signatures generated by this library would not validate with Algorand or Miracl and visa-versa. However, public keys were found to be compatible in all libraries.

This library is compliant with the latest version (10 as of this writing).