EIP-198 Big integer modular exponentiation precompile (Big integer modular exponentiation)
Final · EVM & execution · EIP status Final · created 2017-01-30
Adds a precompile at address 0x05 that computes big integer modular exponentiation (BASE**EXPONENT % MODULUS). This allows integer-theory-based cryptography such as RSA verification to be used efficiently inside the EVM.
Why it is needed
For an Ethereum smart contract to verify an RSA signature, it needs to raise a very large number to a power and then take the remainder, that is, modular exponentiation. However, performing this kind of big-number arithmetic with only the EVM's (Ethereum Virtual Machine) basic instructions is difficult. The original text also notes that addition and subtraction are already efficient enough using algorithms inside the EVM and so do not need a precompile, but argues exponentiation should be provided separately. This EIP provides modular exponentiation in the form of a precompile, a contract that clients implement natively in advance. This lets RSA verification and other integer-theory-based cryptography be used efficiently inside the EVM, and multiplication can also be handled by this single precompile using the identity a*b = ((a+b)**2 - (a-b)**2) / 4.
What changes
Today
- There is no efficient way inside the EVM to compute modular exponentiation of arbitrary-length big integers
- Integer-theory-based cryptography such as RSA verification is difficult to use in contracts
After EIP-198
- The precompile at address 0x05 computes BASE**EXPONENT % MODULUS in a single call
- RSA verification and other integer-theory-based cryptography can be used inside the EVM
- Commonly used exponents such as 2, 3, and 65537 are priced fairly and low thanks to bit-based gas calculation
Who is affected
- Contract developer: RSA signature verification or integer-theory-based cryptographic logic can be implemented with a single precompile call.
- Client teams: The precompile at address 0x05 and the gas formula (mult_complexity, ADJUSTED_EXPONENT_LENGTH) must be implemented exactly as specified.
- Users: On-chain services that interoperate with existing cryptographic systems such as RSA can be used at lower cost.
In depth
Input format and padding rules
The input order is <length_of_BASE> <length_of_EXPONENT> <length_of_MODULUS> <BASE> <EXPONENT> <MODULUS>. Each length field is a 32-byte left-padded integer indicating the number of bytes the following value occupies. The calldata is treated as if followed by an infinite sequence of zero bytes, and any remaining data is ignored. So if length_of_BASE is 0, no data is read for base at all, and the very next byte is interpreted as EXPONENT. If the modulus data is only a single byte 0x80 but its declared length is 32, it is zero-padded and read as 2**255. The output returns (BASE**EXPONENT) % MODULUS as a byte array the same length as the modulus.
Gas formula and GQUADDIVISOR
Gas consumption is floor(mult_complexity(max(length_of_MODULUS, length_of_BASE)) * max(ADJUSTED_EXPONENT_LENGTH, 1) / GQUADDIVISOR). GQUADDIVISOR is 20. That is, the multiplication difficulty of whichever is longer between the base and the modulus is multiplied by the effective bit length of the exponent, then divided by 20. Inputs large enough that they would exceed available gas simply do not execute. The original text gives an example where the modulus length is declared as 2**256 - 1, explaining that it is impossible to supply enough gas for such a computation, so it fails immediately.
Computing ADJUSTED_EXPONENT_LENGTH
A value that measures the effective size of the exponent in bits. If length_of_EXPONENT is 32 or less and all bits of EXPONENT are 0, it returns 0. If length_of_EXPONENT is 32 or less, it returns the index of the highest set bit of EXPONENT (1 -> 0, 2 -> 1, 3 -> 1, 255 -> 7, 256 -> 8). If length_of_EXPONENT exceeds 32, it adds the index of the highest set bit of the first 32 bytes to 8 * (length_of_EXPONENT - 32). For example, for a 100-byte exponent \x00\x00\x01\x00.....\x00, it is 8 * (100 - 32) + 253 = 797. If the first 32 bytes are all 0, it returns exactly 8 * (length_of_EXPONENT - 32).
The mult_complexity function
A function that approximates the difficulty of Karatsuba multiplication, as used by major big-integer libraries. It returns 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 for larger x. As input size grows, the coefficient of the squared term shrinks, so cost scales more gently than a simple square.
Cost example: the EXP opcode and RSA
For an example using a 32-byte exponent, the gas is mult_complexity(32) * 255 / 20 = 13056, about 8 times what the same computation would cost via the EXP opcode. A 4096-bit RSA exponentiation costs 22,853,376 gas in the worst case, but actual RSA verification usually uses exponent 3 or 65537, reducing it to 5,580 and 89,292 gas respectively. This is exactly why the exponent is calculated by bit length rather than byte length: to fairly charge exponent 2, used in multiplication, and 3 and 65537, used in RSA verification.
Design intent: RSA verification and reuse for multiplication
The purpose of this precompile is to let RSA verification and other integer-theory-based cryptography be used efficiently inside the EVM. Addition and subtraction precompiles were not added because algorithms inside the EVM are already efficient enough. Big integer multiplication can also be handled by this precompile using the identity a * b = ((a + b)**2 - (a - b)**2) / 4. This EIP's status is Final, a finalized spec.