EIP-2565 ModExp gas cost recalibration (ModExp Gas Cost)
Final · Fees & gas · EIP status Final · created 2020-03-20
Redefines the gas cost formula for the ModExp precompile (address 0x05) to match its actual computational cost, lowering fees for cryptographic functions that rely on modular exponentiation.
Why it is needed
Modular exponentiation is the computation of raising a large number to a power and then taking the remainder when divided by another number. Several cryptographic techniques, including digital signatures, verifiable delay functions (VDFs), zero-knowledge proofs (SNARKs), and accumulators, rely on this computation. Ethereum provides a built-in feature (precompile) called ModExp to process this computation quickly, but benchmarks revealed that the fee (gas) charged was excessively high relative to the actual time it takes, because the existing gas formula did not accurately estimate the difficulty of the computation. As a result, using these cryptographic functions on Ethereum was inefficient and expensive. This EIP defines a new gas calculation formula that more accurately reflects the actual computational cost, lowering the fee. This makes practical uses such as stronger security and stronger random number generation (VDFs) realistic.
What changes
Today
- Under the EIP-198 formula, gas is charged such that ModExp calls are excessively expensive relative to actual execution time
- The largest test case (modexp_nagydani_5_pow0x10001) costs 285,900 gas
- Using cryptographic functions such as signatures, VDFs, and SNARKs on-chain is burdensome
After EIP-2565
- Gas is calculated using a new formula that better matches actual execution time
- The same test case drops to 87,381 gas
- A minimum cost of 200 gas is set so that very small inputs are not priced excessively cheaply
Who is affected
- Contract and app developers: The call cost of cryptographic functions that use ModExp, such as signature verification, VDFs, SNARKs, and accumulators, drops significantly, making them easier to use in real services.
- Users: Fees for transactions that use these cryptographic functions are lowered.
- Client teams: The gas calculation logic of the ModExp precompile must be replaced with the new formula. A Geth implementation is publicly available.
In depth
Only the gas calculation formula changes
This EIP only changes how the gas cost is calculated for the ModExp precompile at address 0x0000000000000000000000000000000000000005. It takes effect starting at FORK_BLOCK_NUMBER. There is no change to the precompile's input/output interface or its internal arithmetic algorithm, so existing test vectors can be reused as is. The new cost is structured as an approximation of the multiplication complexity multiplied by an approximation of the number of iterations needed to perform the exponentiation. The ModExp precompile itself was introduced by EIP-198, and this EIP presupposes it (requires: 198).
Multiplication complexity: the square of the 8-byte word count
calculate_multiplication_complexity takes max_length as the larger of base_length and modulus_length, divides it by 8 rounding up to get words, and returns words squared (words**2). Dividing by 8 reflects the fact that in multi-precision arithmetic, large numbers are processed as chunks (limbs) of 8 bytes. The EIP-198 formula tried to approximate the difficulty of Karatsuba multiplication, but benchmarks showed this new formula matches actual execution time more closely.
Iteration count: based on the bit length of the exponent
calculate_iteration_count branches into three cases depending on the length and value of the exponent. If exponent_length is 32 bytes or less and exponent is 0, the result is 0; if it is 32 bytes or less, the result is exponent.bit_length() - 1; and if it exceeds 32 bytes, the result is 8 * (exponent_length - 32) plus the bit_length() - 1 of the lower 256 bits of the exponent (exponent & (2**256 - 1)). The final result is max(iteration_count, 1), guaranteeing a minimum of 1. This formula approximates the number of iterations that bigint libraries use in binary exponentiation algorithms for large exponents.
Final gas formula: divisor of 3 and a minimum of 200
The final gas cost is max(200, floor(multiplication_complexity * iteration_count / 3)). Setting the divisor GQUADDIVISOR to 3 keeps the cost of ModExp (in gas per second) still higher than that of other precompiles such as ECRecover. In other words, it is made cheaper while still not being underpriced relative to other precompiles. The minimum value of 200 is a safeguard against the price becoming too low for very small inputs and being exploited.
How this differs from the EIP-198 formula
The EIP-198 complexity function used a piecewise formula for x = max(length_of_MODULUS, length_of_BASE): x**2 if x is 64 or less, x**2 // 4 + 96 * x - 3072 if x is 1024 or less, and x**2 // 16 + 480 * x - 199680 if x is larger. In a regression analysis against execution time, this EIP's new function fit better. The new function's regression line crosses through the test vector points, because execution time differs depending on whether the modulus is even or odd.
How costs change according to test vectors
The existing test vectors are reused as is, with only the pricing updated. Small inputs converge toward the minimum value. modexp_nagydani_1_square drops from 204 to 200, and modexp_nagydani_1_pow0x10001 drops from 3,276 to 341. The mid-sized modexp_nagydani_3_pow0x10001 drops from 30,310 to 5,461, and the largest, modexp_nagydani_5_pow0x10001, drops from 285,900 to 87,381. Overall, cases using larger exponents see larger reductions.
Security considerations and current status
The biggest security consideration is that if the ModExp operation becomes too cheap relative to its actual computation time, it could become a vector for denial-of-service (DoS) attacks. Setting GQUADDIVISOR to 3 to keep the gas-per-second cost higher than other precompiles, and setting a minimum of 200 gas, are safeguards against this. This EIP's status is Final, a finalized specification. A Geth implementation (go-ethereum PR 21607) and a Python reference implementation are publicly available.