EIP-2537 BLS12-381 curve operation precompiles (Precompile for BLS12-381 curve operations)
Final · EVM & execution · EIP status Final · created 2020-02-21
Adds seven BLS12-381 elliptic curve operations as precompiles (built-in fast-operation functions) so smart contracts can efficiently verify BLS signatures and aggregate public keys.
Why it is needed
Verifying a BLS signature (a signature scheme that lets multiple signatures or public keys be combined into one for verification) in a smart contract requires a special elliptic curve operation called pairing. Ethereum currently only has a precompile (a fast operation function built into the client) for a curve called BN254, whose security strength is only 80 bits. This EIP adds operations for BLS12-381, a pairing-friendly curve offering security strength of 120 bits or higher, as precompiles. Alongside point addition and pairing checks, it also adds multi-scalar multiplication (MSM), allowing multiple public keys or individual signers' signatures to be efficiently aggregated during BLS signature verification.
What changes
Today
- Pairing operations can only be done via the BN254 curve precompile, which has 80-bit security strength
- There is no built-in support for BLS12-381 curve operations
- Aggregating multiple points requires calling the operation separately for each point, so call costs pile up
After EIP-2537
- Seven precompiles at addresses 0x0b through 0x11 perform BLS12-381 point addition, MSM, pairing checks, and field element mapping
- BLS signatures can be verified on a curve with security strength of 120 bits or higher
- A single MSM call can aggregate multiple public keys or signatures and receive a gas discount based on batch size
Who is affected
- Smart contract developers: BLS signature verification, public key aggregation, and pairing checks can be performed in contracts via precompile calls.
- Client teams: The seven precompiles, their gas calculation rules, and subgroup checks must be implemented exactly as specified.
- BLS signature based protocols: They also receive built-in support for mapping field elements to curve points, which the signature scheme requires.
In depth
The composition of the seven precompiles
Adds seven precompiles at addresses 0x0b through 0x11. BLS12_G1ADD (0x0b) performs point addition on curve G1 over the base field, BLS12_G1MSM (0x0c) performs multi-scalar multiplication on G1, BLS12_G2ADD (0x0d) performs point addition on curve G2 over the quadratic extension field, BLS12_G2MSM (0x0e) performs multi-scalar multiplication on G2, BLS12_PAIRING_CHECK (0x0f) performs a pairing check over a set of (G1, G2) point pairs, and BLS12_MAP_FP_TO_G1 (0x10) and BLS12_MAP_FP2_TO_G2 (0x11) map field elements to G1 and G2 points respectively. The mapping precompiles do not include the process of converting a byte string into a field element. That process can be done in several ways and can be implemented efficiently in the EVM, so the precompiles only perform the arithmetic that moves a field element to a curve point. This kind of mapping is required for signature schemes.
Input encoding rules
An Fp element is a 64-byte big-endian encoding of an unsigned integer. Since the modulus p is 381 bits, the top 16 bytes must always be zero and the value must be less than p. Even if only part of the input is actually used for decoding, this condition must still be checked. An Fp2 element is 128 bytes formed by concatenating the encodings of c0 and c1, a G1 point is 128 bytes formed by concatenating x and y, and a G2 point is 256 bytes. Since the coordinates (0, 0) are not a point on the BLS12 curve, an all-zero byte string is interpreted by convention as the point at infinity (zero point). A scalar is 32 bytes big-endian and need not be less than the subgroup order q. Invalid encodings, incorrect lengths, and empty inputs for MSM and pairing checks must all return an error.
Presence or absence of subgroup checks
G1ADD and G2ADD do not perform subgroup checks. They accept any input as long as it is a point on the curve or the point at infinity. G1/G2 MSM and the pairing check, on the other hand, MUST check that the input points belong to the correct subgroup of order q, and MUST return an error if that check fails. Implementations SHOULD use the optimized subgroup-check methods documented in a separate document. Endomorphism-based acceleration MAY be used by implementers on the premise that this check guarantees the input is in the correct subgroup.
Gas cost table
G1 addition costs 375 gas and G2 addition costs 600 gas. The base multiplication cost is 12000 gas for G1 and 22500 gas for G2. MSM cost is computed as (k * multiplication_cost * discount) // multiplier, where multiplier is 1000, k is the number of (point, scalar) pairs, and // denotes integer division. The discount rate follows the respective discount tables for G1 and G2 when k is 128 or less, and applies max_discount (519 for G1, 524 for G2) when k exceeds 128. This discount assumes MSM is implemented using the Pippenger algorithm. The pairing check costs 32600*k + 37700 gas for k pairs. Mapping from Fp to G1 costs 5500 gas, and mapping from Fp2 to G2 costs 23800 gas.
Gas calculation and error handling for variable-length input
The gas calculation functions for MSM and the pairing check do not validate input length and do not return errors. k is obtained by dividing the input length (rounded down) by the per-pair length LEN_PER_PAIR (160 for G1 MSM, 288 for G2 MSM, 384 for pairing). If k is 0 for MSM, the function returns 0 gas, which is safe since the CALL or STATICCALL itself has a nonzero cost and there is already precedent for zero gas in the Blake2f precompile. If the input length is not divisible by LEN_PER_PAIR, gas is computed anyway, but the main processing step must return an error for violating the encoding rules. As with other precompiles, if a call ends in an error, all gas supplied to the CALL or STATICCALL is consumed.
Why MSM is a separate call and a dedicated MUL was not included
No dedicated precompile for single-point multiplication was added, because the ABI for MSM with k equal to 1 is identical to that of a dedicated multiplication. Instead, when checking input length, implementations should recognize the case where k equals 1 and call a single-point multiplication implementation instead of the more complex multi-scalar multiplication algorithm, to avoid overhead. There are two reasons MSM was made a separate operation. The Pippenger algorithm can reduce execution time and gas, and because the CALL operation itself is expensive on Ethereum, replacing an MSM of 100 points with 100 calls to the multiplication precompile plus 99 additions would cost roughly 138600 more gas.
Security considerations and current status
The original text states that, if the specification is followed strictly, this does not introduce any security or consensus issues unlike the existing BN254 precompiles. It also specifies that operations in this precompile ARE NOT REQUIRED to run in constant time. Implementations must not contain potential infinite loops, and the gas schedule was set to reflect the computation time of the worst case for operations that have one. This EIP's status is Final, meaning the specification is finalized.