# Herumi mcl and bls libraries: request for proposals ## Introduction We would like to announce a Request for Proposals (RfP) for a security review of the [herumi mcl](https://github.com/herumi/mcl) and [bls](https://github.com/herumi/bls) libraries and optionally, a number of language-specific wrapper libraries ([1](https://github.com/herumi/bls-eth-go-binary/), [2](https://github.com/herumi/bls-eth-wasm), [3](https://github.com/herumi/mcl-wasm), [4](https://github.com/herumi/bls-eth-rust)). This request describes the `mcl` and `bls` libraries, the scope of the security assessment, the deliverables expected, and a suggested timeline. It also provides guidelines on fee structure, selection criteria, and bidding instructions. ## Table of contents [toc] ## Preliminaries ### BLS signatures The [Boneh–Lynn–Shacham](https://en.wikipedia.org/wiki/Boneh%E2%80%93Lynn%E2%80%93Shacham) (BLS) signature scheme allows a user to verify that a signer is authentic. Signatures are elements of an elliptic curve group, and a [pairing](https://en.wikipedia.org/wiki/Pairing-based_cryptography) is used for verification. The scheme has a variety of important properties. For our purposes, two distinguishing ones are: 1. **Signature aggregation.** A collection of signatures (signature_1, ..., signature_n) can be aggregated into a single signature. Moreover, the aggregate signature can be verified using only n+1 pairings, as opposed to 2n pairings, when verifying n signatures separately (verifying a signature requires 2 pairing operations). Furthermore the most expensive part of pairing computation, the final exponentiation, can be done [once per aggregate](https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407). 2. **Threshold signatures.** Threshold signatures allows verifiers to check that a threshold number of nodes have signed something. Specifically, threshold signatures allow for a private key to be spread across multiple nodes. Any subset of these nodes, as long as they are more than some threshold number, can then sign a message, without bringing their private keys together. ### Pairings A [pairing](https://en.wikipedia.org/wiki/Pairing-based_cryptography) is a bilinear map defined between groups. In the context of BLS signatures, it is a map `e: G1 x G2 --> GT` where `G1`, `G2`, and `GT` are distinct subgroups of the same prime order. [Pairings](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627) greatly expand what elliptic curve-based protocols can do, enabling things like threshold signatures, for example. ### BLS signatures in eth2 In eth2, validators are organised into committees to do their work. A vote cast by a validator is called an attestation. And an attestation is comprised of many elements, specifically: - a vote for the current beacon chain head - a vote on which beacon block should be justified/finalised - a vote on the current state of the shard chain - the signatures of all of the validators who agree with that vote Attestations are designed to be easily combined such that if two or more validators have attestations with the same votes, they can be combined by adding the signatures fields together in one attestation. This is what we mean by aggregation. This is the mechanism by which eth2 scales the number of validators. By breaking the validators up into committees, validators need only to care about their fellow committee members and only have to check very few aggregated attestations from each of the other committees. Eth2 makes use of BLS signatures to do this (significantly reducing both bandwidth and storage requirements). On the specific curve chosen (BLS12-381), signatures are 96 bytes each. ### A note on BLS12-381 [BLS12-381](https://electriccoin.co/blog/new-snark-curve/) is part of a family of curves described by [Barreto, Lynn, and Scott](https://eprint.iacr.org/2002/088.pdf). It's a curve that's both secure and optimized for pairing operations. The 12 is the [embedding degree](https://hackmd.io/@benjaminion/bls12-381#Embedding-degree) of the curve. The 381 is the number of bits needed to represent a coordinate (in Fq) on the curve: the field modulus, `q`. In other words, the 381 means that the prime in the finite field `Fq` is of 381 bits. The size of this number is guided both by [security requirements](https://hackmd.io/@benjaminion/bls12-381#Security-level) and implementation efficiency. > Note that the BLS (Barreto-Lynn-Scott) in BLS12-381 is different from the BLS (Boneh–Lynn–Shacham) in BLS signature scheme. The BLS signature scheme works with many curves, BLS and non-BLS. **Full description** ``` u = -0xd201000000010000 k = 12 q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 E(Fq) := y^2 = x^3 + 4 Fq2 := Fq[i]/(x^2 + 1) E'(Fq2) := y^2 = x^3 + 4(i + 1) ``` For a more thorough introduction to the curve, and it's properties, see [here](https://hackmd.io/@benjaminion/bls12-381). ### Spec requirements The BLS signature requirements for phase 0 are described in the beacon chain spec [here](https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/beacon-chain.md#bls-signatures). ### Standardization efforts The relevant IETF standardization efforts are [BLS12-381 curve](https://tools.ietf.org/id/draft-yonezawa-pairing-friendly-curves-02.html), [Hash-To-Curve draft 7](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-07), and [BLS Signatures draft 2]( https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02). ### Ciphersuites A ciphersuite describes the building blocks (a curve, mapping a message to a point on the curve, a signature scheme, magic constants/ID, etc) underpinning a crypto protocol. For our purposes the relevant ciphersuites are: - Hash-To-Curve: `BLS12381G2_XMD:SHA-256_SSWU_RO` - Curve: BLS12-381 - Hash_to_curve: targets the G2 curve - Hash_to_field_Fp2: produces a pseudo randombytes with expand_xmd - Hash function is SHA2-256 - Mapping_Fp2_to_G2 uses Simplified Shallue-van de Woestijne-Ulas Method - RO: hashing uses the "indifferentiable from random oracle" method - BLS Signatures: `BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_` - BLS Proof-of-possession: `BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_` ## Project description The purpose of this audit is to ensure BLS signatures in the [herumi](https://github.com/herumi) libraries work as expected, and that eth2 clients that use herumi are as secure as possible. The `mcl` libary contains the low level pairing-based cryptography. While the `bls` library builds off `mcl` to enable the bls signature scheme. ### mcl [`mcl`](https://github.com/herumi/mcl) is a portable and fast pairing-based cryptography library, which supports the optimal [Ate pairing](https://github.com/herumi/ate-pairing) over [BN curves](https://tools.ietf.org/id/draft-kasamatsu-bncurves-01.html) and [BLS12-381](https://github.com/zkcrypto/bls12_381) curves. ### bls [`bls`](https://github.com/herumi/bls) is an implementation of the BLS signature scheme using low level components from `mcl`. `bls` supports the subset of the IETF standards required by Ethereum 2.0 Phase 0 [Ethereum 2.0 Phase 0](https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/beacon-chain.md#bls-signatures). It supports [type-3](https://eprint.iacr.org/2010/388.pdf) pairings, including BN curves and BLS curves: where G1, G2, and GT are a cyclic group of prime order r. ``` e : G1 x G2 -> GT ``` With respect to BLS signatures, it supports two modes, a default mode, and an eth2 spec mode. type|SecretKey|PublicKey|Signature| -|-|-|-| default|Fr|G2|G1| ETH2.0 spec (BLS_ETH=1)|Fr|G1|G2| ### A note on backends Herumi `mcl` can use three different backends. One of them involves just-in-time compilation (Xbyak JIT compiler), another involves assembly generated by LLVM IR, and the third uses [GMP](https://gmplib.org/). GMP is out of scope for eth2 cliets due to the underlying license. The other two backends are candidates for this RfP. We're happy to discuss with bidders how best to approach the multiple backends. ### Resources - [Herumi mcl libary](https://github.com/herumi/mcl) - [Herumi bls library](https://github.com/herumi/bls) - [Evaluation of Nim-blscurve backends](https://notes.status.im/nim-bls-curve-backends#) - [BLS signature scheme](https://en.wikipedia.org/wiki/Boneh%E2%80%93Lynn%E2%80%93Shacham) - [BLS12-381 for the rest of us](https://hackmd.io/@benjaminion/bls12-381) - [BLS12-381 curve construction](https://electriccoin.co/blog/new-snark-curve/) - [BLS12-382 parameterisation](https://github.com/zkcrypto/pairing/tree/master/src/bls12_381) - [BLS12-381 Keys and Signatures Sizes](https://ethresear.ch/t/bls12-381-keys-and-signatures-sizes/6152/3) - [Understanding BLS12-381](https://crypto.stackexchange.com/questions/62183/understanding-bls12-381-curve) - [Exploring elliptic curve pairings](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627) - [Ethereum 2.0 Phase 0 -- The Beacon Chain](https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/beacon-chain.md) - [Validated, staking on eth2: #3 - Sharding Consensus](https://blog.ethereum.org/2020/03/27/sharding-consensus/) - [IETF draft: BLS specification](https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02) - [IETF draft: Hashing to elliptic curves](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-07) - [IETF draft: Pairing-friendly curves](https://tools.ietf.org/id/draft-yonezawa-pairing-friendly-curves-00.html) - [IETF draft: Barreto-Naehrig curves](https://tools.ietf.org/id/draft-kasamatsu-bncurves-01.html) - [Implementing Pairings at the 192-bit Security Level](https://eprint.iacr.org/2012/232.pdf) - [EIP 2537](https://eips.ethereum.org/EIPS/eip-2537) - [Side-channel Attacks on Blinded Scalar Multiplications Revisited](https://eprint.iacr.org/2019/1220) - [State-of-the-art of secure ECC implementations: a survey on known side-channel attacks and countermeasures](https://www.esat.kuleuven.be/cosic/publications/article-1461.pdf) ## Security assessment scope While there are many attacks available against cryptography run on embedded devices such as smart cards, FPGA, and Raspberry Pis, in this RfP we focus on correctness and on protection from remote attacks. The scope of this security engagement includes the review of the following components: ``` - The bls implementation of the IETF standards utilized by eth2 - Elliptic curve operations of mcl: addition, scalar multiplication, and pairing operations - Field implementations of mcl: Fp and Fp2 as a building block for elliptic curve operations and Fp6 and Fp12 as a building block for pairing operations - mcl backends: Xbyak JIT compiler and/or LLVM IR assembler ``` > Additional wrapper libraries can also be considered in scope depending on auditor’s expertise and time constraints. These include: [Go](https://github.com/herumi/bls-eth-go-binary/), [Wasm bls](https://github.com/herumi/bls-eth-wasm), [Wasm mcl]( https://github.com/herumi/mcl-wasm), and [Rust](https://github.com/herumi/bls-eth-rust). The assessment will focus on identifying vulnerabilities that can lead to the following (non-exhaustive list): ``` - Divergence from IETF specification (e.g. incorrect aggregation, false positives/negatives for verification, etc) - Leaking of private information - System faults/crashes - Any high level behaviours other than those expected ``` Other areas of concern include: ``` - Issues leading to mistaken misuse of library components - Issues arising only on specific builds/machines - Consensus issues that may arise when using bls in a production blockchain setting - Any other issue that might lead to loss of funds ``` ## Process summary The entire process can be summarised as follows: 1. **Request:** EF releases RfP (this post) 2. **Gather:** Vendors submit proposals 3. **Deliberate:** EF decides which proposal to accept, and comes up with a plan based on the resources and needs of the accepted proposal. 4. **Propose:** EF proposes the plan to vendor, and makes adjustments based on vendor's feedback 5. **Begin:** Vendor accepts and work begins ## Engagement timeline The proposed timeline of the engagement is approximately 4 to 6 weeks. The engagement is broken up into the following stages: a vendor assessment, followed by a break for developer response and mitigation, followed by a review phase from the vendor. The vendor will then summarize findings and publish the results to help the community understand the work that was done. | Stage | Description | | ------------- |:-------------: | | 1 | Vendor assessment period | | 2 | Developer issue response | | 3 | Vendor review issue response | | 4 | Vendor summarises findings | Members of the EF will be available at all times to answer questions and comments during the assessment period in order to make life as easy as possible for the vendor. ## Deliverables Deliverables will take the form of Github issues in the relevant Github repository for every security concern found. As outlined above, the vendor will provide a report distilling the lessons learnt, and summarising the issues submitted. ## Fee Structure ### Invoices Based on the timeline of this audit, the chosen vendor will be expected to submit 2 invoices: - a first invoice of **40**% of the total engagement fee at the start of the engagement - a second invoice of **60**% of the total engagement fee at the end of the engagement, following the delivery of the summary report and a 5 day review period. ### Payment method The vendor will be given the option to be paid in Fiat money (via bank transfer) or Ether (ETH). If the vendor chooses to be paid in ETH, the value of ETH described under the agreement will be the value in USD at NYSE closing time (4 PM EST) on the day prior to the due date (as described at https://www.coingecko.com). ## Selection criteria The selected vendor will have significant expertise in the areas necessary to meet the needs and requirements set forth in this RfP. Particularly: ``` - Expertise in applied cryptography and cryptographic systems - Expertise in low level, optimised code - Familiarity with common attacks and pitfalls in applied cryptography - Familiarity with blockchain systems ``` The EF has considerable expertise in these domains and is ready to support the vendor. ## Bidding instructions Upon reception of this request, interested vendors are expected to confirm receipt and intention to bid on the engagement. In this confirmation, they should explain what they need from us in order to get started. As well as bring attention to areas in which they feel they do not have significant expertise. We will use this information to try to provide appropriate entrance material for the engagement. Proposals must be submitted before *July 14th, 12 PM EST*. We expect to take 1 week to deliberate and respond. Please send initial confirmations, and proposals (in PDF format) to the following address: [email protected] We're also happy to arrange pre-bid meetings, should you feel there's a need.