BLS Signatures in Solidity

Thank Onur, Jannik, and Mikerah for the review and the advice

published version https://ethresear.ch/t/bls-signatures-in-solidity/7919

BLS Signatures in Solidity

Who should read this?

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"^[1] 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. ^[2]

Which curve should I use?

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

alt_bn128: Barreto-Naehrig curve. ^[3]
BLS12-381: This BLS is Barreto, Lynn, and Scott. ^[4]

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^[5] (curve point addition and multiplication) and EIP-197^[6] (curve pairing) and introduced in Byzantium hardfork October 16, 2017^[7].

The cost is further reduced in EIP-1108^[8], and was live on mainnet in Istanbul-fork^[9].

The BLS12-381 curve is specified in EIP-2537^[10] and expected to go live in the Berlin hardfork^[11].

The alt_bn128(BN256) is shown in 2016 to have less than 100-bits of security^[12]. 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 works on a 254 bit prime field, so people also 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
$G_{1}$ Uncompressed	64 bytes	96 bytes	has x and y coordinates as $F_{q}$
$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
$G_{1}$ compressed	32 bytes	48 bytes
$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
$G_{2}$ for signatures and messages, and
$G_{1}$ for public keys, or
Use
$G_{2}$ for public keys, and
$G_{1}$ for signatures and messages.

G_{2}

is 128 bytes (uint256[4] in Solidity) and

G_{1}

is 64 bytes (uint256[2] in Solidity). Also field/curve operations on

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

G_{2}

to be the subgroup of points where the curve's x and y coordinates defined on

F_{q^{2}}

. And subgroup

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
$G_{1}$ or
$G_{2}$ . An element in
$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
$G_{1}$ with an integer in
$Z_{q}$ ^[13]. Same applies for
$G_{2}$ .

Pairing function

e : G_{1} \times G_{2} \to G_{T}

G_{1}

G_{2}

are the generators of

G_{1}

and

G_{2}

respectively

Pairing function has bilinear property, which means for

a, b \in Z_{q}

P \in G_{1}

, and

Q \in G_{2}

, we have:

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

Hash function

It maps the message to an element of

G_{1}

H_{0} : M \to G_{1}

Key Generation

Secret key:

α \leftarrow Z_{q}

Public key:

h \leftarrow α \times G_{2} \in G_{2}

Signing

σ \leftarrow α \times H_{0} (m) \in G_{1}

Verification

e (σ, G_{2}) \overset{?}{=} e (H_{0} (m), h)

Proof of why verification works

e (σ, G_{2}) = e (α \times H_{0} (m), G_{2}) = e (H_{0} (m), α \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

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

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 (signature, n e g (G_{2})) e (message, pubkey) \overset{?}{=} 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 (message, pubkey) = e (message, privkey \times G_{2}) = e (privkey \times message, G_{2}) = e (signature, G_{2})

e (message, pubkey) \overset{?}{=} e (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^[14]. 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.

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
https://github.com/ChihChengLiang/modexp

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^[15].

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.

Packages to do BLS

JavaScript/TypeScript

https://github.com/kilic/evmbls

Python

https://github.com/ChihChengLiang/bls_solidity_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.