BLS Signatures in Solidity

Thank @kilic, @jannikluhn, and @Mikerah for the review and the advice

This article targets developers who want to perform BLS signature verification in Eth1 contracts.

For readers interested in the BLS signature in Eth2, I highly recommend “BLS12-381 For The Rest Of Us”^ben-bls by Ben Edgington, which provides long but not too long answers to common questions.

The article also assumes the readers heard of the terms like G_1, G_2, and pairings. “BLS12-381 For The Rest Of Us” is also a good source for understanding those.

Introduction

When we talk about the BLS signature, we are talking about the signature aggregation technique. The BLS here is the name of three authors Boneh, Lynn, and Shacham. ^bls

Which curve should I use?

BLS signature aggregation works on pairing friendly curves. We have to choose which of the following curves to use.

  • alt_bn128: Barreto-Naehrig curve. ^bn
  • BLS12-381: This BLS is Barreto, Lynn, and Scott. ^bls-curve

At the time of writing this document (2020-Aug), we can only use alt_bn128 curve in contracts. The alt_bn128 curve is specified in EIP-196^eip196 (curve point addition and multiplication) and EIP-197^eip197 (curve pairing) and introduced in Byzantium hardfork October 16, 2017^byzantium-fork.

The cost is further reduced in EIP-1108^eip1108, and was live on mainnet in Istanbul-fork^istanbul-fork.

The BLS12-381 curve is specified in EIP-2537^eip2537 and expected to go live in the Berlin hardfork^eip2070.

The alt_bn128(BN256) is shown in 2016 to have less than 100-bits of security^ietf. To target 128-bits security use BLS12-381 whenever possible.

We use alt_bn128 in the examples hereafter.

alt_bn128, bn256, bn254, why so many names and so confusing?

  • Originally named alt_bn128 for targeting theoretic security at 128 bits.
  • It then be shown to have security level less than 128 bits^ietf, so people call it bn254.
  • Some also call it bn256 for unknown reason.

Notes on size of the elements

alt_bn128 BLS12-381 Note
F_q 254 bits (32 bytes) 381 bits (48 bytes) has leading zero bits
F_{q^2} 64 bytes 96 bytes
\Bbb G_1 Uncompressed 64 bytes 96 bytes has x and y coordinates as F_q
\Bbb G_2 Uncompressed 128 bytes 192 bytes has x and y coordinates as F_{q^2}

A curve point’s y coordinate can be compressed to 1 bit and recovered by x.

alt_bn128 BLS12-381
\Bbb G_1 compressed 32 bytes 48 bytes
\Bbb G_2 compressed 64 bytes 96 bytes

Big Signatures or Big public keys?

This is a decision you’ll face in the project.

Choose either:

  • Use \Bbb G_2 for signatures and messages, and \Bbb G_1 for public keys, or
  • Use \Bbb G_2 for public keys, and \Bbb G_1 for signatures and messages.

\Bbb G_2 is 128 bytes (uint256[4] in Solidity) and \Bbb G_1 is 64 bytes (uint256[2] in Solidity). Also field/curve operations on \Bbb G_2 are more expensive.

The option saves more gas in your project is better.

We’ll use the big public keys in the examples hereafter.

BLS cheat sheet

We have a curve. The points on the curve can form a subgroup. We define \Bbb G_2 to be the subgroup of points where the curve’s x and y coordinates defined on F_{q^2}. And subgroup \Bbb G_1 with coordinates on F_q.

Tips

  • Field operations: We are talking about arithmetics of field elements F_q or F_{q^2}. F_q can be added, subtracted, multiplied, and divided by other F_q. Same applies for F_{q^2}.
  • Curve operations: We are talking about operations of curve elements \Bbb G_1 or \Bbb G_2. An element in \Bbb G_1 can be added to another element in a geometrical way. An element can be added to itself multiple times, so we can define multiplications of an element in \Bbb G_1 with an integer in Z_q^ecmul. Same applies for \Bbb G_2.

Pairing function

e:\Bbb G_1 \times \Bbb G_2 \to \Bbb G_T

G_1, G_2 are the generators of \Bbb G_1 and \Bbb G_2 respectively

Pairing function has bilinear property, which means for a, b \in Z_q, P \in \Bbb G_1, and Q \in \Bbb G_2, we have:

e( a \times P, b \times Q) = e( ab \times P, Q) = e( P, ab \times Q)

Hash function

It maps the message to an element of \Bbb G_1

H_0: \mathcal{M} \to \Bbb G_1

Key Generation

Secret key:

\alpha \gets \Bbb Z_q

Public key:

h \gets \alpha \times G_2 \in \Bbb G_2

Signing

\sigma \gets \alpha \times H_0(m) \in \Bbb G_1

Verification

e(\sigma, G_2)\stackrel{?}{=} e(H_0(m), h)

Proof of why verification works

e(\sigma, G_2) \\ = e( \alpha \times H_0(m), G_2) \\ = e( H_0(m), \alpha \times G_2) \\ = e(H_0(m), h)

Contracts / Precompiles

Developers usually work with a wrapped contract that has clear function names and function signatures. However, the core of the implementation could be confusing. Here we provide a simple walkthrough.

Verify Single

Below shows an example Solidity function that verifies a single signature. It is the small signature and big public key setup. A signature is a 64 bytes \Bbb G_1 group element, and its calldata is a length 2 array of uint256. On the other hand, a public key is a 128 bytes \Bbb G_2 group element, and its calldata is a length 4 array of uint256.

EIP 197 defined a pairing precompile contract at address 0x8 and requires input to a multiple of 192. This assembly code calls the precompile contract at address 0x8 with inputs.

function verifySingle(
    uint256[2] memory signature, \\ small signature
    uint256[4] memory pubkey, \\ big public key: 96 bytes
    uint256[2] memory message
) internal view returns (bool) {
    uint256[12] memory input = [
        signature[0],
        signature[1],
        nG2x1,
        nG2x0,
        nG2y1,
        nG2y0,
        message[0],
        message[1],
        pubkey[1],
        pubkey[0],
        pubkey[3],
        pubkey[2]
    ];
    uint256[1] memory out;
    bool success;
    // solium-disable-next-line security/no-inline-assembly
    assembly {
        success := staticcall(sub(gas(), 2000), 8, input, 384, out, 0x20)
        switch success
            case 0 {
                invalid()
            }
    }
    require(success, "");
    return out[0] != 0;
}

We translate the above code into math formula. Where the nG2 is the negative “curve” operation of the G_2 group generator.

e(\text{signature}, neg(G_2)) e(\text{message}, \text{pubkey}) \stackrel{?}{=} 1

If the above formula is not straight forward, let’s derive from the pairing check we usually see. The message here is the raw message hashed to G_1.

e(\text{message}, \text{pubkey}) \\ = e(\text{message}, \text{privkey} \times G_2 ) \\ = e(\text{privkey} \times \text{message}, G_2 ) \\ = e(\text{signature}, G_2)
e(\text{message}, \text{pubkey}) \stackrel{?}{=} e(\text{signature}, G_2)

Hash to curve

We can choose from Hash and pray approach or Fouque Tibouchi approach:

  • Hash and pray approach is easy to implement, but since it is non-constant time to run it has a security issue^hash-and-pray-issue. Each iteration is expensive in solidity and attacker can grind a message that’s too expensive to check on chain.
  • Fouque Tibouchi is constant time, but more difficult to implement.

The following discussion are for hash to G1. For the case of bn254 in G2, see musalbas’s implementation

Attempts to fix hash and pray

Avg 30k gas for hash and pray https://github.com/thehubbleproject/RedditHubble/runs/1011657548#step:7:35

A sqrt iteration takes 14k gas due to the call to modexp precompile.

Attempt to replace modexp with a series of modmul. optimized cost is 6.7k

Kobi has a proposal that user provides outputs of modexp and onchain we use 1 modmul to verify. https://gist.github.com/kobigurk/b9142a4755691bb12df59fbe999c2a1f#file-bls_with_help-sol-L129-L154

Gas Consumption

Post EIP-1108, k pairings cost 34 000 * k + 45 000 gas.

So as the above example, to validate a single signature takes 2 pairings and thus 113000 gas.

Validating n different messages takes n + 1 pairings, which costs 80 000 + 34000*n gas.

In comparison, ECDSA takes 3000 gas, see ecrecover^ethgastable.

Here are cases to consider the aggregate signature:

  • When there’s only one message, but many signatures to verify. The aggregate signature takes 2 pairings (113000 gas), and it wins ECDSA when you have 38 more signatures to verify.
  • When you need to store or log signatures on chain. Storing a word (32 bytes) costs 20000 or 5000 gas, and logging costs 8 gas per byte. The aggregate signature (48 bytes * 1 sig) wins ECDSA (65 bytes * n sigs) easily in this case.

In the Hubble project, we use BLS signature to achieve 3000 TPS on ropsten

Packages to do BLS

JavaScript/TypeScript

Python

Cookbook

Aggregations

TODO

  • how to create private keys, public keys, and signatures (just listing the formulas should be enough, everyone can then use their favorite library to implement them).
  • test data for one cycle (a private key, a public key, a message, and a signature)
  • a note on encodings: The solidity code just uses the plain uints, but at least for BLS12-381 there are standardized encodings, aren’t there? Not sure if it makes sense to go into details, but just mentioning that they exist with maybe a link could be helpful
  • public key aggregation (my problem basically): My understanding from our discussion yesterday is that it’s not easily possible on-chain with bn128 and public keys from G2. I looked into the EIP fro BLS12-381 and they have a precompile for G2 additions, so with that it should be easy.
17 Likes

To expand on this a bit - a client library can generate witness values as to the expected result of a sqrt operation. If the sqrt for x exists - great, provide a witness w such that w^2 = x. If not, provide a witness w such that w^2=-x. This exists and works since -1 is not a quadratic residue (doesn’t have a square root) when the field has p = 3 \pmod 4, and so if x is not a quadratic residue then -x is. p = 3 \pmod 4 is true for both BN254 and BLS12-381.

3 Likes

i have an example for BLS signature verification (following the scheme used in eth2) here:

it uses the EIP-2537 precompiles (which are not yet deployed) but may be useful for anyone looking to play around with this stuff.

2 Likes

I think the the groups where switched, G1 is over Fq and G2 is over Fq^2
Hash: H(m) ∈ G2
sk: a ∈ Zq
pk: aG1 ∈ G1
sig: a
H(m) ∈ G2
verification: e(sig, G1) =? e(pk, H(m))

My two cents:

This strongly depends on:

  • the security level we want.
    • We don’t protect private keys here so is ~100 bits of security acceptable?
  • the efficiency we want, as EVM is using 256-bit words, BN254 Fq elements fit in one EVM word while BLS12-381 wille requires 1.5 EVM words. The space wasted grows with curve point:
    • On BN254, G1 Affine needs 2 words, G2 Affine needs 4
    • On BLS12-381 G1 Affine would require 4 words (2 being half-empty), G2 Affine would requires 8 words (4 being half-empty). We can optimize long-term storage by packing the half empty words.

BLS cheat sheet

The BLS signature standardized draft spec is there by the way: https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02

Big Signatures or Big public keys?

If that can help, in Eth2 we use small public key and big signature because each individual validator public key must be store in the state while signatures can be aggregated.

Hash function

If we create something new, I think we should follow the hash-to-curve draft standard. Many blockchains agreed to follow it for BLS signature over BLS12-381 (Algorand, Chia, Dfinity, Eth2.0, Filecoin, Zcash at least and Tezos is exploring it), unless we need it for legacy purposes (Aztec protocol for example), I think all hashing going forward are better served by a standard. It would be easier for optimized software (and hardware?) implementations to emerge.

https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-09

Also a hash-to-curve precompile might be necessary there are many costly operations namely:

  • Generating an uniform random byte string. (Think something similar to HKDF that repeatedly call SHA256)
  • Transforming that byte string into a modular integer in Fq or Fq2 (somewhat fast but still involves modulo)
  • Mapping that to the G1 or G2 curves. This involves inversion and square root which are the slowest operations you can have on Fq:
    • inversion is about 40 to 100 times slower than modular multiplication if non-constant-time (or as slow as square root if constant-time but I don’t think this is needed or expected in the EVM)
    • square root is 500 times slower than modular multiplication for BN254 and 620x for BLS12-381 from my measurements.
  • Last but not least we need to clear the cofactor. While BN curves have no cofactor on G1, BN on G2 and BLS on G1 G2 have a cofactor. Naively this involves a scalar multiplication and this is easily 2500x~5500x slower than a modular multiplication even though BN and BLS cofactors have low Hamming-Weight.
    An optimized cofactor clearing can be made cheaper using endomorphism (Fuentes-Castaneda 2011 for BN G2 and Budroni-Pintore 2017 / Wahby-Boneh 2019), but since those are likely provided by all BN254 libraries used for the existing precompiles or BLS12-381 libraries, if we use library calls, we might as well just do a whole hash-to-curve call.

Lastly, I’ve skimmed through the Pixel signature scheme by Dfinity and Algorand and it seemed quite interesting in terms of state size:

They claim 35% reduction of state size and 38% reduction in verification time.


Performance figures on Fp, those are from the pairing library I’m building at: https://github.com/mratsim/constantine and should give you an idea of the gap between Solidity and an optimal native implementation. Unfortunately I didn’t implement pairing/verification yet.

The code on Fq / G1 is probably optimal (as in even if you write pure assembly you cannot get more than 3% faster). Note that variable-time inversion can be made 5x~10x faster than constant-time inversion.

3 Likes

Well - we have them implemented at SKALE

2 Likes

I recently submitted an EIP requesting a precompiled contract for the Fouque and Tibouchi hash-to-curve algorithm. I have implemented this both in Solidity and Go for geth. The estimates for gas cost in Solidity is ~140K, while the cost would be closer to 8500 if it were a precompiled contract. The cost is only slightly more expensive than G1 scalar multiplication. This hash-to-curve algorithm would reduce gas cost for verifying BLS signatures using BN256 in Ethereum.

Similar to EIP-2537, if the deterministic field-to-curve algorithm is the precompiled contract, then different users could have different mappings for hash-to-field. This would allow for greater flexibility.

1 Like