EIP-3026 BW6-761 curve operations
No call decision · Security & privacy · EIP status Stagnant · created 2020-10-05
Adds seven precompiles for BW6-761 elliptic curve operations, making it cheaper to verify on-chain zkSNARK proofs that have been aggregated into a single proof.
Why it is needed
Performing one-layer composition that verifies a zkSNARK proof once more inside another proof requires a lot of specific elliptic curve operations on-chain, and implementing this with general EVM operations makes gas costs excessively high. Currently Zexe handles this composition with the BLS12-377 and CP6-782 curve pair, but CP6-782 operations are slow, making verification costly. BW6-761 can be used as an outer curve for BLS12-377 and is known to be 30 times faster than CP6-782 for Groth16 proof verification. This EIP adds precompiles for BW6-761 specific operations so this speed advantage can actually be used on-chain.
What changes
Today
- One-step proof composition is handled with the CP6-782 curve, so operations are slow
- The EVM has no BW6-761 specific operations, so implementing them with general opcodes consumes a lot of gas
- Point operations and pairings must be implemented by hand at the smart contract level
After EIP-3026
- Adds 7 precompiles: BW6_G1_ADD/MUL/MULTIEXP, BW6_G2_ADD/MUL/MULTIEXP, BW6_PAIRING
- Groth16-style proofs based on BW6-761 can be verified with far less gas than with CP6-782
- Providing multiexponentiation as a separate precompile cuts the overhead of repeated CALLs
Who is affected
- zkSNARK proof system developers: Zexe-style one-layer proof composition can be verified on-chain at lower gas cost.
- Ethereum client teams: They need to implement the 7 precompiles along with a dedicated gas schedule and error handling rules.
- L2 and privacy projects: The cost of verifying proofs that use the BLS12-377/BW6-761 curve pair is reduced.
In depth
Curve and twist parameters
The BW6-761 curve has the form y^2=x^3-1 with A=0, and B is the 762-bit modulus value specified in the original text. The base field modulus is 762 bits (96 bytes) and the main subgroup order is 377 bits. The extension is built as Fp3=Fp[u]/(u^3+4), and the twist is M-type, with twist curve B coefficients c0=0x4, c1=0x0. The pairing is computed as e(P,Q)=(ML1(P,Q)*ML2(P,Q)^q)^FE, using two Miller loops (ML1, ML2) and a final exponentiation (FE), with loop_count_1=0x8508c00000000002 and loop_count_2=0x23ed1347970dec008a442f991fffffffffffffffffffffff, both positive. The G1 and G2 generator coordinates are also specified explicitly in the original text.
Encoding rule
Base field elements (Fp) are encoded as 96-byte big-endian integers and must be smaller than the base field modulus. Both G1 and G2 points are represented in affine coordinates (x,y) and encoded as 192 bytes by concatenating the two field elements. Because BW6-761 also defines G2 over the base field using an M-twist, the G1 and G2 point encodings have the same length. The coordinate (0,0) is not a point on the curve, so by convention it represents the point at infinity. Scalars for multiplication and multiexponentiation operations are encoded as 64-byte big-endian values; although the subgroup order is only 377 bits (48 bytes), 64 bytes was chosen to align with a 32-byte-unit ABI, and scalar values larger than the subgroup order are allowed. Precompiles must revert if encoding rules are violated.
The 7 precompiles and their ABI
The proposed addresses are BW6_G1_ADD(0x1e), BW6_G1_MUL(0x1f), BW6_G1_MULTIEXP(0x20), BW6_G2_ADD(0x21), BW6_G2_MUL(0x22), BW6_G2_MULTIEXP(0x23), BW6_PAIRING(0x24), and these are not yet finalized. G1/G2 ADD take two points (192 bytes each, 384 bytes total) as input and return a 192-byte result. MUL takes a point (192 bytes) and a scalar (64 bytes) combined into 256 bytes. G1 MULTIEXP takes k concatenated (point + 64-byte scalar) pairs, i.e. 256*k bytes, while G2 MULTIEXP takes k (point + 48-byte scalar) pairs per the original text, i.e. 240*k bytes. PAIRING takes k pairs of (192-byte G1 point + 192-byte G2 point), i.e. 384*k bytes, and returns a 32-byte value of 1 if the pairing result equals the multiplicative identity of the target field, or 0 otherwise. It is an error if a point is not on the curve or does not belong to the correct subgroup.
Gas schedule
G1/G2 ADD each cost 180 gas, and G1/G2 MUL each cost 64000 gas. MULTIEXP applies a discount table based on the number of points k, computed as cost = k * multiplication_cost * discount / 1000, using discount 1266 for k=1 and max_discount 150 for k=128 or more. This design reduces CALL overhead: processing 100 points with 100 multiplication precompile calls and 99 addition calls would incur about 138600 gas of overhead on its own. The pairing cost is 120000*k + 320000 gas for k pairs. Gas figures follow the estimation strategy of EIP-1962, assuming a constant of 30 MGas/s based on measured times and gas prices for ECRECOVER (43.5 MGas/s) and BNPAIR (16.5 MGas/s), using average execution times measured across several implementations.
Error handling and no constant-time requirement
Because curve operations are computationally expensive, if an error occurs such as invalid input or a point not being on the curve or in the subgroup, the operation must consume all gas allotted to it. This rule prevents using errors to trigger repeated low-gas calls as a DDoS vector. The original text also states explicitly that this precompile is not required to run as a constant-time algorithm, leaving timing-attack prevention as an implementation choice.
Status and relationship
This EIP's status is Stagnant, and it specifies EIP-2539 (BLS12-377 curve operations) as a requirement, with BW6-761 used as the outer curve for BLS12-377. It was written to supersede an existing proposal from matter-labs, replacing CP6-782 with BW6-761 in the BLS12-377/CP6-782 combination that Zexe used. The provided call records contain no discussion of whether this EIP will be included in a fork.