ethereum.forks.amsterdam.vm.precompiled_contracts.modexp

Ethereum Virtual Machine (EVM) MODEXP PRECOMPILED CONTRACT.

.. contents:: Table of Contents :backlinks: none :local:

Introduction

Implementation of the MODEXP precompiled contract.

modexp

Calculates (base**exp) % modulus for arbitrary sized base, exp and modulus. The return value is the same length as the modulus.

def modexp(​evm: Evm​) -> None:
25
    <snip>
29
    data = evm.call_data
30
31
    # GAS
32
    base_length = U256.from_be_bytes(buffer_read(data, U256(0), U256(32)))
33
    if base_length > U256(1024):
34
        raise ExceptionalHalt("Mod-exp base length is too large")
35
36
    exp_length = U256.from_be_bytes(buffer_read(data, U256(32), U256(32)))
37
    if exp_length > U256(1024):
38
        raise ExceptionalHalt("Mod-exp exponent length is too large")
39
40
    modulus_length = U256.from_be_bytes(buffer_read(data, U256(64), U256(32)))
41
    if modulus_length > U256(1024):
42
        raise ExceptionalHalt("Mod-exp modulus length is too large")
43
44
    exp_start = U256(96) + base_length
45
46
    exp_head = U256.from_be_bytes(
47
        buffer_read(data, exp_start, min(U256(32), exp_length))
48
    )
49
50
    charge_gas(
51
        evm,
52
        gas_cost(base_length, modulus_length, exp_length, exp_head),
53
    )
54
55
    # OPERATION
56
    if base_length == 0 and modulus_length == 0:
57
        evm.output = Bytes()
58
        return
59
60
    base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length))
61
    exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length))
62
63
    modulus_start = exp_start + exp_length
64
    modulus = Uint.from_be_bytes(
65
        buffer_read(data, modulus_start, modulus_length)
66
    )
67
68
    if modulus == 0:
69
        evm.output = Bytes(b"\x00") * modulus_length
70
    else:
71
        evm.output = pow(base, exp, modulus).to_bytes(
72
            Uint(modulus_length), "big"
73
        )

complexity

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 : Uint Complexity of performing the operation.

def complexity(​base_length: U256, ​​modulus_length: U256​) -> Uint:
77
    <snip>
94
    max_length = max(Uint(base_length), Uint(modulus_length))
95
    words = (max_length + Uint(7)) // Uint(8)
96
    complexity = Uint(16)
97
    if max_length > Uint(32):
98
        complexity = Uint(2) * words ** Uint(2)
99
    return complexity

iterations

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 a U256.

Returns

iterations : Uint Number of iterations.

def iterations(​exponent_length: U256, ​​exponent_head: U256​) -> Uint:
103
    <snip>
122
    if exponent_length <= U256(32) and exponent_head == U256(0):
123
        count = Uint(0)
124
    elif exponent_length <= U256(32):
125
        bit_length = exponent_head.bit_length()
126
127
        if bit_length > Uint(0):
128
            bit_length -= Uint(1)
129
130
        count = bit_length
131
    else:
132
        length_part = Uint(16) * (Uint(exponent_length) - Uint(32))
133
        bits_part = exponent_head.bit_length()
134
135
        if bits_part > Uint(0):
136
            bits_part -= Uint(1)
137
138
        count = length_part + bits_part
139
140
    return max(count, Uint(1))

gas_cost

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 a U256.

Returns

gas_cost : ExecutionGas Gas required for performing the operation.

def gas_cost(​base_length: U256, ​​modulus_length: U256, ​​exponent_length: U256, ​​exponent_head: U256​) -> ExecutionGas:
149
    <snip>
173
    multiplication_complexity = complexity(base_length, modulus_length)
174
    iteration_count = iterations(exponent_length, exponent_head)
175
    cost = multiplication_complexity * iteration_count
176
    return ExecutionGas(max(Uint(500), cost))