ethereum.berlin.vm.precompiled_contracts.modexpethereum.london.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.

GQUADDIVISOR

20
GQUADDIVISOR = 3

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:
24
    """
25
    Calculates `(base**exp) % modulus` for arbitrary sized `base`, `exp` and.
26
    `modulus`. The return value is the same length as the modulus.
27
    """
28
    data = evm.message.data
29
30
    # GAS
31
    base_length = U256.from_be_bytes(buffer_read(data, U256(0), U256(32)))
32
    exp_length = U256.from_be_bytes(buffer_read(data, U256(32), U256(32)))
33
    modulus_length = U256.from_be_bytes(buffer_read(data, U256(64), U256(32)))
34
35
    exp_start = U256(96) + base_length
36
37
    exp_head = Uint.from_be_bytes(
38
        buffer_read(data, exp_start, min(U256(32), exp_length))
39
    )
40
41
    charge_gas(
42
        evm,
43
        gas_cost(base_length, modulus_length, exp_length, exp_head),
44
    )
45
46
    # OPERATION
47
    if base_length == 0 and modulus_length == 0:
48
        evm.output = Bytes()
49
        return
50
51
    base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length))
52
    exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length))
53
54
    modulus_start = exp_start + exp_length
55
    modulus = Uint.from_be_bytes(
56
        buffer_read(data, modulus_start, modulus_length)
57
    )
58
59
    if modulus == 0:
60
        evm.output = Bytes(b"\x00") * modulus_length
61
    else:
62
        evm.output = Uint(pow(base, exp, modulus)).to_bytes(
63
            modulus_length, "big"
64
        )

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:
68
    """
69
    Estimate the complexity of performing a modular exponentiation.
70
71
    Parameters
72
    ----------
73
74
    base_length :
75
        Length of the array representing the base integer.
76
77
    modulus_length :
78
        Length of the array representing the modulus integer.
79
80
    Returns
81
    -------
82
83
    complexity : `Uint`
84
        Complexity of performing the operation.
85
    """
86
    max_length = max(Uint(base_length), Uint(modulus_length))
87
    words = (max_length + 7) // 8
88
    return words**2

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 an unsigned integer.

Returns

iterations : Uint Number of iterations.

def iterations(​exponent_length: U256, ​​exponent_head: Uint​) -> Uint:
92
    """
93
    Calculate the number of iterations required to perform a modular
94
    exponentiation.
95
96
    Parameters
97
    ----------
98
99
    exponent_length :
100
        Length of the array representing the exponent integer.
101
102
    exponent_head :
103
        First 32 bytes of the exponent (with leading zero padding if it is
104
        shorter than 32 bytes), as an unsigned integer.
105
106
    Returns
107
    -------
108
109
    iterations : `Uint`
110
        Number of iterations.
111
    """
112
    if exponent_length <= 32 and exponent_head == 0:
113
        count = Uint(0)
114
    elif exponent_length <= 32:
115
        bit_length = Uint(exponent_head.bit_length())
116
117
        if bit_length > 0:
118
            bit_length -= 1
119
120
        count = bit_length
121
    else:
122
        length_part = 8 * (Uint(exponent_length) - 32)
123
        bits_part = Uint(exponent_head.bit_length())
124
125
        if bits_part > 0:
126
            bits_part -= 1
127
128
        count = length_part + bits_part
129
130
    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 an unsigned integer.

Returns

gas_cost : Uint Gas required for performing the operation.

def gas_cost(​base_length: U256, ​​modulus_length: U256, ​​exponent_length: U256, ​​exponent_head: Uint​) -> Uint:
139
    """
140
    Calculate the gas cost of performing a modular exponentiation.
141
142
    Parameters
143
    ----------
144
145
    base_length :
146
        Length of the array representing the base integer.
147
148
    modulus_length :
149
        Length of the array representing the modulus integer.
150
151
    exponent_length :
152
        Length of the array representing the exponent integer.
153
154
    exponent_head :
155
        First 32 bytes of the exponent (with leading zero padding if it is
156
        shorter than 32 bytes), as an unsigned integer.
157
158
    Returns
159
    -------
160
161
    gas_cost : `Uint`
162
        Gas required for performing the operation.
163
    """
164
    multiplication_complexity = complexity(base_length, modulus_length)
165
    iteration_count = iterations(exponent_length, exponent_head)
166
    cost = multiplication_complexity * iteration_count
167
    cost //= GQUADDIVISOR
168
    return max(Uint(200), cost)