Pragmatic signature aggregation with BLS

Sharding
29

Following the steps of @lovesh, we’ve also started an implementation of BLS multisig in Nim, based on Apache Milagro-Crypto as discussed in the sharding implementer call #0.

For reference I’ve compiled a list of implementations.

Here are a few tips for implementers, note that Milagro has multiple implementations (C, Go, Java, Javascript, Rust, Python, WASM) and we used the C version but those tips do not apply exclusively to Milagro or Milagro C.

  1. Py-ecc only implements BN128, the “bls” file present in the beacon chain repo only mocks BLS interface at the moment.

  2. Check the ECDSA signing API exported by the library you are using. ECDSA signing can either require a cryptographically secure random integer or be deterministic depending on a private key and the message being signed. Further reading resources on ECDSA available in nim-milagro-crypto wiki [1]. For Casper we need the deterministic ECDSA.

  3. Single message signing: unfortunately Milagro does not include the deterministic ECDSA so you will have to implement it, however you can use @lovesh’s implementation as a base, Milagro includes all the primitives necessary to make it very short. Using the C or C++ implementation requires you to manage array arguments size and lifetimes.

The Nim aggregate signature implementation is still being debugged.

If you’re looking for resources to help you make sense of ECDSA or BLS multisignature, generator points G1 & G2 (G0 and G1 in the BLS short spec), extension fields FP/FQ, FP2, FP12, here are a couple resources that I find useful:

[1] Readings from nim-milagro-crypto wiki:

  • Layman’s Guide to Elliptic Curve Digital Signatures: you will find, examples, 2D graphs. Key points: normally elliptic curve would require floating point but by using modulus math we can transform all fractions to (big) integers.

  • The fundamentals of ECDSA: you will find key generation, signature and verification. Note that this ECDSA scheme uses a crypto-secure random number generator. As noted in Wikipedia:

    Another way ECDSA signature may leak private keys is when k is generated by a faulty random number generator. Such a failure in random number generation caused users of Android Bitcoin Wallet to lose their funds in August 2013. To ensure that k is unique for each message one may bypass random number generation completely and generate deterministic signatures by deriving k from both the message and the private key.

  • High-level primer of ECSDA by Cloudflare

  • Short spec for BLS multisig

  • To be read in parallel, switch to the other when stuck, it helps a lot:

    BLS is a particular curve because it is pairing friendly. The key point is that what we call elliptic curve with modulus, is also called elliptic curve over FP (or FQ). FP is an extension field i.e. same operations/rules as normal math, except that everything is modulo the modulus.
    And we also need equations of higher order (FP2 to FP12) which are solved using complex integer numbers.

    The complex i is called “u” in the Zcash spec.

8 Likes