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

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

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:
69
    """
70
    Estimate the complexity of performing a modular exponentiation.
71
72
    Parameters
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
    complexity : `Uint`
83
        Complexity of performing the operation.
84
85
    """
86
    max_length = max(Uint(base_length), Uint(modulus_length))
87
    if max_length <= Uint(64):
88
        return max_length ** Uint(2)
89
    elif max_length <= Uint(1024):
90
        return (
91
            max_length ** Uint(2) // Uint(4)
92
            + Uint(96) * max_length
93
            - Uint(3072)
94
        )
95
    else:
96
        return (
97
            max_length ** Uint(2) // Uint(16)
98
            + Uint(480) * max_length
99
            - Uint(199680)
100
        )
87
    words = (max_length + Uint(7)) // Uint(8)
88
    return words ** Uint(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 a U256.

Returns

iterations : Uint Number of iterations.

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

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