EIP-2539: BLS12-377 curve operations Ethereum Improvement Proposals AllCoreNetworkingInterfaceERCMetaInformational ⚠️ Draft Standards Track: Core EIP-2539: BLS12-377 curve operations Precompiles for BLS12-377 curve operations Authors Alex Vlasov (@shamatar), hujw77 (@hujw77) Created 2020-02-26 Discussion Link https://ethereum-magicians.org/t/eip-2539-bls12-377-precompile-discussion-thread/4659 Requires EIP-1109, EIP-2046 Table of Contents Abstract Proposed addresses table Motivation Specification Fine points and encoding of base elements ABI for operations Prevention of DDoS on error handling Gas schedule Rationale Multiexponentiation as a separate call Backwards Compatibility Important notes Test Cases Reference Implementation Security Considerations Copyright Abstract This precompile adds operation on BLS12-377 curve (from Zexe paper) as a precompile in a set necessary to efficiently perform operations such as BLS signature verification and perform SNARKs verifications. Unique properties of BLS12-377 also later allow to have SNARKs that check BLS12-377 pairing in an efficient way and allow e.g. constant-size BLS signature aggregation. If block.number >= X we introduce nine separate precompiles to perform the following operations: BLS12_377_G1ADD - to perform point addition on a curve defined over prime field BLS12_377_G1MUL - to perform point multiplication on a curve defined over prime field BLS12_377_G1MULTIEXP - to perform multiexponentiation on a curve defined over prime field BLS12_377_G2ADD - to perform point addition on a curve twist defined over quadratic extension of the base field BLS12_377_G2MUL - to perform point multiplication on a curve twist defined over quadratic extension of the base field BLS12_377_G2MULTIEXP - to perform multiexponentiation on a curve twist defined over quadratic extension of the base field BLS12_377_PAIRING - to perform a pairing operations between a set of pairs of (G1, G2) points BLS12_377_MAP_FP_TO_G1 - maps base field element into the G1 point BLS12_377_MAP_FP2_TO_G2 - maps extension field element into the G2 point Multiexponentiation operation is included to efficiently aggregate public keys or individual signer’s signatures during BLS signature verification. Proposed addresses table Precompile Address BLS12_377_G1ADD 0x15 BLS12_377_G1MUL 0x16 BLS12_377_G1MULTIEXP 0x17 BLS12_377_G2ADD 0x18 BLS12_377_G2MUL 0x19 BLS12_377_G2MULTIEXP 0x1a BLS12_377_PAIRING 0x1b BLS12_377_MAP_FP_TO_G1 0x1c BLS12_377_MAP_FP2_TO_G2 0x1d Motivation 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. In addition it allows efficient one-time recursive proof aggregations, e.g. proofs about existence of BLS12-377 based signature. Specification Curve parameters: BLS12-377 curve is fully defined by the following set of parameters (coefficient A=0 for all BLS12 curves): Base field modulus = 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001 B coefficient = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 Main subgroup order = 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001 Extension tower: Fp2 construction: Fp quadratic non-residue = 0x01ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508bffffffffffc Fp6/Fp12 construction: Fp2 cubic non-residue c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 Fp2 cubic non-residue c1 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 Twist parameters: Twist type: D B coefficient for twist c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 B coefficient for twist c1 = 0x010222f6db0fd6f343bd03737460c589dc7b4f91cd5fd889129207b63c6bf8000dd39e5c1ccccccd1c9ed9999999999a Generators: G1: X = 0x008848defe740a67c8fc6225bf87ff5485951e2caa9d41bb188282c8bd37cb5cd5481512ffcd394eeab9b16eb21be9ef Y = 0x01914a69c5102eff1f674f5d30afeec4bd7fb348ca3e52d96d182ad44fb82305c2fe3d3634a9591afd82de55559c8ea6 G2: X c0 = 0x018480be71c785fec89630a2a3841d01c565f071203e50317ea501f557db6b9b71889f52bb53540274e3e48f7c005196 X c1 = 0x00ea6040e700403170dc5a51b1b140d5532777ee6651cecbe7223ece0799c9de5cf89984bff76fe6b26bfefa6ea16afe Y c0 = 0x00690d665d446f7bd960736bcbb2efb4de03ed7274b49a58e458c282f832d204f2cf88886d8c7c2ef094094409fd4ddf Y c1 = 0x00f8169fd28355189e549da3151a70aa61ef11ac3d591bf12463b01acee304c24279b83f5e52270bd9a1cdd185eb8f93 Pairing parameters: |x| (miller loop scalar) = 0x8508c00000000001 x is negative = false Fine points and encoding of base elements Field elements encoding: To encode points involved in the operation one has to encode elements of the base field and the extension field. Base field element (Fp) is encoded as 64 bytes by performing BigEndian encoding of the corresponding (unsigned) integer (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]). 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 formal 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). If encodings do not follow this spec anywhere during parsing in the precompile the precompile must return an error. Encoding of points in G1/G2: Points in either G1 (in base field) or in G2 (in extension field) are encoded as byte concatenation of encodings of the x and y affine coordinates. Total encoding length for G1 point is thus 128 bytes and for G2 point is 256 bytes. Point of infinity encoding: Also referred as “zero point”. For BLS12 curves point with coordinates (0, 0) (formal zeroes in Fp or Fp2) is not on the curve, so encoding of such point (0, 0) is used as a convention to encode point of infinity. Encoding of scalars for multiplication operation: Scalar for multiplication operation is encoded as 32 bytes by performing BigEndian encoding of the corresponding (unsigned) integer. Corresponding integer is not required to be less than or equal than main subgroup size. ABI for operations ABI for G1 addition 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: - Either of points being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for G1 multiplication G1 multiplication call expects 160 bytes as an input that is interpreted as byte concatenation of encoding of G1 point (128 bytes) and encoding of a scalar value (32 bytes). Output is an encoding of multiplication operation result - single G1 point (128 bytes). Error cases: - Point being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for G1 multiexponentiation G1 multiexponentiation call expects 160*k bytes as an input that is interpreted as byte concatenation of k slices each of them being a byte concatenation of encoding of G1 point (128 bytes) and encoding of a scalar value (32 bytes). Output is an encoding of multiexponentiation operation result - single G1 point (128 bytes). Error cases: - Any of G1 points being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for G2 addition 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 - single G2 point (256 bytes). Error cases: - Either of points being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for G2 multiplication G2 multiplication call expects 288 bytes as an input that is interpreted as byte concatenation of encoding of G2 point (256 bytes) and encoding of a scalar value (32 bytes). Output is an encoding of multiplication operation result - single G2 point (256 bytes). Error cases: - Point being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for G2 multiexponentiation G2 multiexponentiation call expects 288*k 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 multiexponentiation operation result - single G2 point (256 bytes). Error cases: - Any of G2 points being not on the curve must result in error - Field elements encoding rules apply (obviously) - Input has invalid length ABI for pairing Pairing call expects 384*k bytes as an inputs that is interpreted as byte concatenation of k slices. Each slice has the following structure: - 128 bytes of G1 point encoding - 256 bytes of G2 point encoding Output is a 32 bytes where first 31 bytes are equal to 0x00 and the last byte is 0x01 if pairing result is equal to multiplicative identity in a pairing target field and 0x00 otherwise. Error cases: - Invalid encoding of any boolean variable must result in error - Any of G1 or G2 points being not on the curve must result in error - Any of G1 or G2 points are not in the correct subgroup - Field elements encoding rules apply (obviously) - Input has invalid length ABI for mapping Fp element to G1 point Field-to-curve call expects 64 bytes an an input that is interpreted as a an element of the base field. Output of this call is 128 bytes and is G1 point following respective encoding rules. Error cases: - Input has invalid length - Input is not a valid field element ABI for mapping Fp2 element to G2 point Field-to-curve call expects 128 bytes an an input that is interpreted as a an element of the quadratic extension field. Output of this call is 256 bytes and is G2 point following respective encoding rules. Error cases: - Input has invalid length - Input is not a valid field element Prevention of DDoS on error handling This precompile performs extensive computations and in case of any errors during execution it MUST consume all gas from the the gas schedule for the corresponding operation. Gas schedule Assuming a constant 30 MGas/second following prices are suggested. G1 addition 600 gas G1 multiplication 12000 gas G2 addition 4500 gas G2 multiplication 55000 gas G1/G2 Multiexponentiation Multiexponentiations are expected to be performed by the Peppinger algorithm (we can also say that is must be performed by Peppinger 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 multiexponentiation with a discount cup max_discount for k > 128. To avoid non-integer arithmetic 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 single multiplication call cost for G1/G2. Discounts table as a vector of pairs [k, discount]: [[1, 1200], [2, 888], [3, 764], [4, 641], [5, 594], [6, 547], [7, 500], [8, 453], [9, 438], [10, 423], [11, 408], [12, 394], [13, 379], [14, 364], [15, 349], [16, 334], [17, 330], [18, 326], [19, 322], [20, 318], [21, 314], [22, 310], [23, 306], [24, 302], [25, 298], [26, 294], [27, 289], [28, 285], [29, 281], [30, 277], [31, 273], [32, 269], [33, 268], [34, 266], [35, 265], [36, 263], [37, 262], [38, 260], [39, 259], [40, 257], [41, 256], [42, 254], [43, 253], [44, 251], [45, 250], [46, 248], [47, 247], [48, 245], [49, 244], [50, 242], [51, 241], [52, 239], [53, 238], [54, 236], [55, 235], [56, 233], [57, 232], [58, 231], [59, 229], [60, 228], [61, 226], [62, 225], [63, 223], [64, 222], [65, 221], [66, 220], [67, 219], [68, 219], [69, 218], [70, 217], [71, 216], [72, 216], [73, 215], [74, 214], [75, 213], [76, 213], [77, 212], [78, 211], [79, 211], [80, 210], [81, 209], [82, 208], [83, 208], [84, 207], [85, 206], [86, 205], [87, 205], [88, 204], [89, 203], [90, 202], [91, 202], [92, 201], [93, 200], [94, 199], [95, 199], [96, 198], [97, 197], [98, 196], [99, 196], [100, 195], [101, 194], [102, 193], [103, 193], [104, 192], [105, 191], [106, 191], [107, 190], [108, 189], [109, 188], [110, 188], [111, 187], [112, 186], [113, 185], [114, 185], [115, 184], [116, 183], [117, 182], [118, 182], [119, 181], [120, 180], [121, 179], [122, 179], [123, 178], [124, 177], [125, 176], [126, 176], [127, 175], [128, 174]] max_discount = 174 Pairing operation Cost of the pairing operation is 55000*k + 65000 where k is a number of pairs. Fp-to-G1 mapping operation Fp -> G1 mapping is 5500 gas. Fp2-to-G2 mapping operation Fp2 -> G2 mapping is 75000 gas Rationale Motivation section covers a total motivation to have operations over BLS12-377 curve available. We also extend a rationale for move specific fine points. Multiexponentiation as a separate call Explicit separate multiexponentiation operation that allows one to save execution time (so gas) by both the algorithm used (namely Peppinger 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-negigible overhead if e.g. for multiexponentiation of 100 points would have to call the multipication precompile 100 times and addition for 99 times (roughly 138600 would be saved). Backwards Compatibility There are no backward compatibility questions. Important notes Subgroup checks Subgroup check is mandatory during the pairing call. Implementations should use fast subgroup checks: at the time of writing multiplication gas cost is based on double-and-add multiplication method that has a clear “worst case” (all bits are equal to one). For pairing operation it’s expected that implementation uses faster subgroup check, e.g. by using wNAF multiplication method for elliptic curves that is ~ 40% cheaper with windows size equal to 4. (Tested empirically. Savings are due to lower hamming weight of the group order and even lower hamming weight for wNAF. Concretely, subgroup check for both G1 and G2 points in a pair are around 35000 combined). Test Cases 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. Generator for G1 is labeled as G, generator for G2 is labeled as H, otherwise we assume random point on a curve in a correct subgroup. 0 means either scalar zero or point of infinity. 1 means either scalar one or multiplicative identity. group_order is a main subgroup order. e(P, Q) means pairing operation where P is in G1, Q is in G2. Requeired properties for basic ops (add/multiply): - Commutativity: P + Q = Q + P - Additive negation: P + (-P) = 0 - Doubling P + P = 2*P - Subgroup check: group_order * P = 0 - Trivial multiplication check: 1 * P = P - Multiplication by zero: 0 * P = 0 - Multiplication by the unnormalized scalar (scalar + group_order) * P = scalar * P Required properties for pairing operation: - Degeneracy e(P, 0*Q) = e(0*P, Q) = 1 - Bilinearity e(a*P, b*Q) = e(a*b*P, Q) = e(P, a*b*Q) (internal test, not visible through ABI) Test vector for all operations are expanded in this csv files in matter-labs’ 1962 proposol. Reference Implementation There is a various choice of existing implementations of the curve operations. It may require extra work to add an ABI: - Code bases with fixed parameters - Rust: matter-labs - C++: matter-labs - Original implementation linked in Zexe paper in Rust: github.com/scipr-lab/zexe - Standalone in Go: github.com/kilic/bls12-377 Security Considerations 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 Copyright and related rights waived via CC0. Citation Please cite this document as: Alex Vlasov (@shamatar), hujw77 (@hujw77), "EIP-2539: BLS12-377 curve operations [DRAFT]," Ethereum Improvement Proposals, no. 2539, February 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2539. Ethereum Improvement Proposals Ethereum Improvement Proposals ethereum/EIPs Ethereum Improvement Proposals (EIPs) describe standards for the Ethereum platform, including core protocol specifications, client APIs, and contract standards.