Ethereum Virtual Machine (EVM) MODEXP PRECOMPILED CONTRACT
Table of Contents
Introduction
Implementation of the MODEXP precompiled contract.
Module Contents
Functions
Calculates (base**exp) % modulus for arbitary sized base, exp and. |
|
Estimate the complexity of performing Karatsuba multiplication.a modular exponentiation. |
|
Calculate the number of iterations required to perform a modular |
|
Calculate the gas cost of performing a modular exponentiation. |
Attributes
Module Details
GQUADDIVISOR
- GQUADDIVISOR
GQUADDIVISOR = Uint(20)3
modexp
- modexp(evm)
Calculates (base**exp) % modulus for arbitary sized base, exp and. modulus. The return value is the same length as the modulus.
def modexp(evm: Evm) -> None: data = evm.message.data # GAS base_length = U256.from_be_bytes(buffer_read(data, U256(0), U256(32))) exp_length = U256.from_be_bytes(buffer_read(data, U256(32), U256(32))) modulus_length = U256.from_be_bytes(buffer_read(data, U256(64), U256(32))) exp_start = U256(96) + base_length modulus_start = exp_start + exp_length exp_head = U256.from_be_bytes(Uint.from_be_bytes( buffer_read(data, exp_start, min(U256(32), exp_length)) ) charge_gas( evm, gas_cost(base_length, modulus_length, exp_length, exp_head), ) # OPERATION if exp_length < 32: adjusted_exp_lengthbase_length == 0 and modulus_length == 0: evm.output = Uint(max(0, exp_head.bit_length() - 1))Bytes() return base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length)) exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length)) modulus = Uint.from_be_bytes( buffer_read(data, modulus_start, modulus_length) ) if modulus == 0: evm.output = Bytes(b"\x00") * modulus_length else: adjusted_exp_lengthevm.output = Uint( 8 * (int(exp_length) - 32) + max(0, exp_head.bit_length() - 1)Uint(pow(base, exp, modulus)).to_bytes( modulus_length, "big" ) charge_gas( evm, ( get_mult_complexity(Uint(max(base_length, modulus_length))) * max(adjusted_exp_length, Uint(1)) ) // GQUADDIVISOR, ) # OPERATION if base_length == 0 and modulus_length == 0: evm.output = Bytes() return base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length)) exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length)) modulus = Uint.from_be_bytes( buffer_read(data, modulus_start, modulus_length) ) if modulus == 0: evm.output = Bytes(b"\x00") * modulus_length else: evm.output = Uint(pow(base, exp, modulus)).to_bytes( modulus_length, "big" )
get_mult_complexity
- get_mult_complexity(x)
Estimate the complexity of performing Karatsuba multiplication.
def get_mult_complexity(x: Uint) -> Uint:
if x <= 64:
return x**2
elif x <= 1024:
return x**2 // 4 + 96 * x - 3072
else:
return x**2 // 16 + 480 * x - 199680
complexity
- complexity(base_length, modulus_length)
Estimate the complexity of performing a modular exponentiation.
- Parameters
base_length – Length of the array representing the base integer.
modulus_length – Length of the array representing the modulus integer.
- Returns
complexity – Complexity of performing the operation.
- Return type
Uint
def complexity(base_length: U256, modulus_length: U256) -> Uint:
max_length = max(Uint(base_length), Uint(modulus_length))
words = (max_length + 7) // 8
return words**2
iterations
- iterations(exponent_length, exponent_head)
Calculate the number of iterations required to perform a modular exponentiation.
- Parameters
exponent_length – Length of the array representing the exponent integer.
exponent_head – First 32 bytes of the exponent (with leading zero padding if it is shorter than 32 bytes), as an unsigned integer.
- Returns
iterations – Number of iterations.
- Return type
Uint
def iterations(exponent_length: U256, exponent_head: Uint) -> Uint:
if exponent_length <= 32 and exponent_head == 0:
count = Uint(0)
elif exponent_length <= 32:
bit_length = Uint(exponent_head.bit_length())
if bit_length > 0:
bit_length -= 1
count = bit_length
else:
length_part = 8 * (Uint(exponent_length) - 32)
bits_part = Uint(exponent_head.bit_length())
if bits_part > 0:
bits_part -= 1
count = length_part + bits_part
return max(count, Uint(1))
gas_cost
- gas_cost(base_length, modulus_length, exponent_length, exponent_head)
Calculate the gas cost of performing a modular exponentiation.
- Parameters
base_length – Length of the array representing the base integer.
modulus_length – Length of the array representing the modulus integer.
exponent_length – Length of the array representing the exponent integer.
exponent_head – First 32 bytes of the exponent (with leading zero padding if it is shorter than 32 bytes), as an unsigned integer.
- Returns
gas_cost – Gas required for performing the operation.
- Return type
Uint
def gas_cost(
base_length: U256,
modulus_length: U256,
exponent_length: U256,
exponent_head: Uint,
) -> Uint:
multiplication_complexity = complexity(base_length, modulus_length)
iteration_count = iterations(exponent_length, exponent_head)
cost = multiplication_complexity * iteration_count
cost //= GQUADDIVISOR
return max(Uint(200), cost)