ethereum.forks.prague.vm.precompiled_contracts.modexpethereum.forks.osaka.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(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
    if base_length > U256(1024):
33
        raise ExceptionalHalt("Mod-exp base length is too large")
34
35
    exp_length = U256.from_be_bytes(buffer_read(data, U256(32), U256(32)))
36
    if exp_length > U256(1024):
37
        raise ExceptionalHalt("Mod-exp exponent length is too large")
38
39
    modulus_length = U256.from_be_bytes(buffer_read(data, U256(64), U256(32)))
40
    if modulus_length > U256(1024):
41
        raise ExceptionalHalt("Mod-exp modulus length is too large")
42
43
    exp_start = U256(96) + base_length
44
45
    exp_head = U256.from_be_bytes(
46
        buffer_read(data, exp_start, min(U256(32), exp_length))
47
    )
48
49
    charge_gas(
50
        evm,
51
        gas_cost(base_length, modulus_length, exp_length, exp_head),
52
    )
53
54
    # OPERATION
55
    if base_length == 0 and modulus_length == 0:
56
        evm.output = Bytes()
57
        return
58
59
    base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length))
60
    exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length))
61
62
    modulus_start = exp_start + exp_length
63
    modulus = Uint.from_be_bytes(
64
        buffer_read(data, modulus_start, modulus_length)
65
    )
66
67
    if modulus == 0:
68
        evm.output = Bytes(b"\x00") * modulus_length
69
    else:
70
        evm.output = pow(base, exp, modulus).to_bytes(
71
            Uint(modulus_length), "big"
72
        )

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:
76
    """
77
    Estimate the complexity of performing a modular exponentiation.
78
79
    Parameters
80
    ----------
81
    base_length :
82
        Length of the array representing the base integer.
83
84
    modulus_length :
85
        Length of the array representing the modulus integer.
86
87
    Returns
88
    -------
89
    complexity : `Uint`
90
        Complexity of performing the operation.
91
92
    """
93
    max_length = max(Uint(base_length), Uint(modulus_length))
94
    words = (max_length + Uint(7)) // Uint(8)
88
    return words ** Uint(2)
95
    complexity = Uint(16)
96
    if max_length > Uint(32):
97
        complexity = Uint(2) * words ** Uint(2)
98
    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:
102
    """
103
    Calculate the number of iterations required to perform a modular
104
    exponentiation.
105
106
    Parameters
107
    ----------
108
    exponent_length :
109
        Length of the array representing the exponent integer.
110
111
    exponent_head :
112
        First 32 bytes of the exponent (with leading zero padding if it is
113
        shorter than 32 bytes), as a U256.
114
115
    Returns
116
    -------
117
    iterations : `Uint`
118
        Number of iterations.
119
120
    """
121
    if exponent_length <= U256(32) and exponent_head == U256(0):
122
        count = Uint(0)
123
    elif exponent_length <= U256(32):
124
        bit_length = exponent_head.bit_length()
125
126
        if bit_length > Uint(0):
127
            bit_length -= Uint(1)
128
129
        count = bit_length
130
    else:
121
        length_part = Uint(8) * (Uint(exponent_length) - Uint(32))
131
        length_part = Uint(16) * (Uint(exponent_length) - Uint(32))
132
        bits_part = exponent_head.bit_length()
133
134
        if bits_part > Uint(0):
135
            bits_part -= Uint(1)
136
137
        count = length_part + bits_part
138
139
    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:
148
    """
149
    Calculate the gas cost of performing a modular exponentiation.
150
151
    Parameters
152
    ----------
153
    base_length :
154
        Length of the array representing the base integer.
155
156
    modulus_length :
157
        Length of the array representing the modulus integer.
158
159
    exponent_length :
160
        Length of the array representing the exponent integer.
161
162
    exponent_head :
163
        First 32 bytes of the exponent (with leading zero padding if it is
164
        shorter than 32 bytes), as a U256.
165
166
    Returns
167
    -------
168
    gas_cost : `Uint`
169
        Gas required for performing the operation.
170
171
    """
172
    multiplication_complexity = complexity(base_length, modulus_length)
173
    iteration_count = iterations(exponent_length, exponent_head)
174
    cost = multiplication_complexity * iteration_count
165
    cost //= GQUADDIVISOR
166
    return max(Uint(200), cost)
175
    return max(Uint(500), cost)