Add functionality to efficiently perform operations over the BLS12-381 curve, including those for BLS signature verification.
Along with the curve arithmetic, multi-scalar-multiplication operations are included to efficiently aggregate public keys or individual signer's signatures during BLS signature verification.
The motivation of this precompile is to add a cryptographic primitive that allows to get 120+ bits of security for operations over pairing friendly curve compared to the existing BN254 precompile that only provides 80 bits of security.
| Name | Value | Comment |
|---|---|---|
| BLS12_G1ADD | 0x0b | precompile address |
| BLS12_G1MSM | 0x0c | precompile address |
| BLS12_G2ADD | 0x0d | precompile address |
| BLS12_G2MSM | 0x0e | precompile address |
| BLS12_PAIRING_CHECK | 0x0f | precompile address |
| BLS12_MAP_FP_TO_G1 | 0x10 | precompile address |
| BLS12_MAP_FP2_TO_G2 | 0x11 | precompile address |
We introduce seven separate precompiles to perform the following operations:
375 gas600 gas5500 gas23800 gasA mapping functions specification is included as a separate document. This mapping function does NOT perform mapping of the byte string into a field element (as it can be implemented in many different ways and can be efficiently performed in EVM), but only does field arithmetic to map a field element into a curve point. Such functionality is required for signature schemes.
The BLS12 curve is fully defined by the following set of parameters (coefficient A=0 for all BLS12 curves):
One should note that base field modulus p is equal to 3 mod 4 that allows an efficient square root extraction, although as described below gas cost of decompression is larger than gas cost of supplying decompressed point data in calldata.
Field Fp is defined as the finite field of size p with elements represented as integers between 0 and p-1 (both inclusive).
Field Fp2 is defined as Fp[X]/(X^2-nr2) with elements el = c0 + c1 * v, where v is the formal square root of nr2 represented as integer pairs (c0,c1).
Group G1 is defined as a set of Fp pairs (points) (x,y) such that either (x,y) is (0,0) or x,y satisfy the curve Fp equation.
Group G2 is defined as a set of Fp2 pairs (points) (x',y') such that either (x,y) is (0,0) or (x',y') satisfy the curve Fp2 equation.
In order to produce inputs to an operation, one encodes elements of the base field and the extension field.
A base field element (Fp) is encoded as 64 bytes by performing the BigEndian encoding of the corresponding (unsigned) integer. Due to the size of p, the top 16 bytes are always zeroes. 64 bytes are chosen to have 32 byte aligned ABI (representable as e.g. bytes32[2] or uint256[2] with the latter assuming the BigEndian encoding). The corresponding integer must be less than field modulus.
For elements of the quadratic extension field (Fp2), encoding is byte concatenation of individual encoding of the coefficients totaling in 128 bytes for a total encoding. For an Fp2 element in a form el = c0 + c1 * v where v is the formal square root of a quadratic non-residue and c0 and c1 are Fp elements the corresponding byte encoding will be encode(c0) || encode(c1) where || means byte concatenation (or one can use bytes32[4] or uint256[4] in terms of Solidity types).
Note on the top 16 bytes being zero: it is required that an encoded element is "in a field", which means strictly < modulus. In BigEndian encoding it automatically means that for a modulus that is just 381 bit long the top 16 bytes in 64 bytes encoding are zeroes and this must be checked even if only a subslice of input data is used for actual decoding.
On inputs that can not be a valid encodings of field elements the precompile must return an error.
Points of G1 and G2 are encoded as byte concatenation of the respective encodings of the x and y coordinates. Total encoding length for a G1 point is thus 128 bytes and for a G2 point is 256 bytes.
Also referred to as the "zero point". For BLS12 curves, the point with coordinates (0, 0) (zeroes in Fp or Fp2) is not on the curve, so a sequence of 128 resp. 256 zero bytes, which naively would decode as (0, 0) is instead used by convention to encode the point of infinity of G1 resp. G2.
A scalar for the multiplication operation is encoded as 32 bytes by performing BigEndian encoding of the corresponding (unsigned) integer. The corresponding integer is not required to be less than or equal to main subgroup order q.
Certain operations have variable length input, such as MSMs (takes a list of pairs (point, scalar)), or pairing (takes a list of (G1, G2) points). While their behavior is well-defined (from an arithmetic perspective) on empty inputs, this EIP discourages such use cases and variable input length operations must return an error if the input is empty.
G1 addition call expects 256 bytes as an input that is interpreted as byte concatenation of two G1 points (128 bytes each). Output is an encoding of addition operation result - single G1 point (128 bytes).
Error cases:
Note:
There is no subgroup check for the G1 addition precompile.
G1 MSM call expects 160*k (k being a positive integer) bytes as an input that is interpreted as byte concatenation of k slices each of them being a byte concatenation of encoding of a G1 point (128 bytes) and encoding of a scalar value (32 bytes). Output is an encoding of MSM operation result - a single G1 point (128 bytes).
Error cases:
G2 addition call expects 512 bytes as an input that is interpreted as byte concatenation of two G2 points (256 bytes each). Output is an encoding of addition operation result - a single G2 point (256 bytes).
Error cases:
Note:
There is no subgroup check for the G2 addition precompile.
G2 MSM call expects 288*k (k being a positive integer) bytes as an input that is interpreted as byte concatenation of k slices each of them being a byte concatenation of encoding of G2 point (256 bytes) and encoding of a scalar value (32 bytes). Output is an encoding of MSM operation result - a single G2 point (256 bytes).
Error cases:
Pairing check call expects 384*k (k being a positive integer) bytes as an inputs that is interpreted as byte concatenation of k slices. Each slice has the following structure:
128 bytes of G1 point encoding256 bytes of G2 point encodingEach point is expected to be in the subgroup of order q.
It checks the equation e(P1, Q1) * e(P2, Q2) * ... * e(Pk, Qk) == 1 in the pairing target field where e is the pairing operation. Output is 32 bytes where first 31 bytes are equal to 0x00 and the last byte is either 0x00 (false) or 0x01 (true).
Error cases:
Field-to-curve call expects 64 bytes as an input that is interpreted as an element of Fp. Output of this call is 128 bytes and is an encoded G1 point.
Error cases:
Field-to-curve call expects 128 bytes as an input that is interpreted as an element of Fp2. Output of this call is 256 bytes and is an encoded G2 point.
Error cases:
Following the current state of all other precompiles, if a call to one of the precompiles in this EIP results in an error then all the gas supplied along with a CALL or STATICCALL is burned.
A sane implementation of this EIP should not contain potential infinite loops (it is possible and not even hard to implement all the functionality without while loops) and the gas schedule accurately reflects the time spent on computations of the corresponding function (precompiles pricing reflects an amount of gas consumed in the worst case where such a case exists).
Assuming EcRecover precompile as a baseline.
375 gas
12000 gas
600 gas
22500 gas
MSMs are expected to be performed by Pippenger's algorithm (we can also say that it must be performed by Pippenger's algorithm to have a speedup that results in a discount over naive implementation by multiplying each pair separately and adding the results). For this case there was a table prepared for discount in case of k <= 128 points in the MSM with a discount cap max_discount for k > 128.
The call cost is calculated as (k * multiplication_cost * discount) // multiplier where multiplier = 1000, k is a number of (scalar, point) pairs for the call, multiplication_cost is a corresponding G1/G2 multiplication cost presented above and // is an integer division.
G1 and G2 are priced separately, each having their own discount table and max_discount.
Discounts table for G1 MSM as a vector of pairs [k, discount]:
max_discount = 519
Discounts table for G2 MSM as a vector of pairs [k, discount]:
max_discount = 524
The cost of the pairing check operation is 32600*k + 37700 where k is a number of pairs.
Fp -> G1 mapping is 5500 gas.
Fp2 -> G2 mapping is 23800 gas
For MSM and pairing functions, the gas cost depends on the input length. The current state of how the gas schedule is implemented in major clients (at the time of writing) is that the gas cost function does not perform any validation of the length of the input and never returns an error. So we present a list of rules how the gas cost functions must be implemented to ensure consistency between clients and safety.
Define a constant LEN_PER_PAIR that is equal to 160 for G1 operation and to 288 for G2 operation. Define a function discount(k) following the rules in the corresponding section, where k is number of pairs.
The following pseudofunction reflects how gas should be calculated:
We use floor division to get the number of pairs. If the length of the input is not divisible by LEN_PER_PAIR we still produce some result, but later on the precompile will return an error. Also, the case when k = 0 is safe: CALL or STATICCALL cost is non-zero, and the case with formal zero gas cost is already used in Blake2f precompile. In any case, the main precompile routine must produce an error on such an input because it violated encoding rules.
Define a constant LEN_PER_PAIR = 384;
The following pseudofunction reflects how gas should be calculated:
We use floor division to get the number of pairs. If the length of the input is not divisible by LEN_PER_PAIR we still produce some result, but later on the precompile will return an error (the precompile routine must produce an error on such an input because it violated encoding rules).
The motivation section covers a total motivation to have operations over the BLS12-381 curves available. We also extend a rationale for more specific fine points.
Explicit separate MSM operation that allows one to save execution time (so gas) by both the algorithm used (namely Pippenger's algorithm) and (usually forgotten) by the fact that CALL operation in Ethereum is expensive (at the time of writing), so one would have to pay non-negligible overhead if e.g. for MSM of 100 points would have to call the multiplication precompile 100 times and addition for 99 times (roughly 138600 would be saved).
Dedicated MUL precompiles which perform single G1/G2 point by scalar multiplication have exactly the same ABI as MSM with k == 1.
MSM has to inspect the input length to reject inputs of invalid lengths. Therefore, it should recognize the case of k == 1 and invoke the underlying implementation of single point multiplication to avoid the overhead of more complex multi-scalar multiplication algorithm.
There are no backward compatibility questions.
MSMs and pairings MUST perform a subgroup check. Implementations SHOULD use the optimized subgroup check method detailed in a dedicated document. On any input that fails the subgroup check, the precompile MUST return an error. As endomorphism acceleration requires input on the correct subgroup, implementers MAY use endomorphism acceleration.
The algorithms and set of parameters for SWU mapping method are provided by a separate document
Due to the large test parameters space, we first provide properties that various operations must satisfy. We use additive notation for point operations, capital letters (P, Q) for points, small letters (a, b) for scalars. The generator for G1 is labeled as G, the generator for G2 is labeled as H, otherwise we assume random points on a curve in a correct subgroup. 0 means either scalar zero or point at infinity. 1 means either scalar one or multiplicative identity. group_order is the main subgroup order. e(P, Q) means pairing operation where P is in G1, Q is in G2.
Required properties for basic ops (add/multiply):
P + Q = Q + PP + 0 = PP + (-P) = 0P + P = 2*Pgroup_order * P = 01 * P = P0 * P = 0(scalar + group_order) * P = scalar * PRequired properties for pairing operation:
e(a*P, b*Q) = e(a*b*P, Q) = e(P, a*b*Q)e(P, Q) != 1e(P, 0*Q) = e(0*P, Q) = 1e(P, -Q) = e(-P, Q)Test vectors can be found in the test vectors files.
A set of test vectors for quick benchmarking on new implementations is located in a separate file
There are two fully spec compatible implementations on the day of writing:
Strictly following the spec will eliminate security implications or consensus implications in a contrast to the previous BN254 precompile.
Important topic is a "constant time" property for performed operations. We explicitly state that this precompile IS NOT REQUIRED to perform all the operations using constant time algorithms.
Copyright and related rights waived via CC0.