ethereum.forks.constantinople.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)

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.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
    if base_length > U256.MAX_VALUE - U256(96):
37
        # The exponent would start past the end of any input, where every
38
        # byte reads as zero.
39
        exp_head = U256(0)
40
    else:
41
        exp_head = U256.from_be_bytes(
42
            buffer_read(
43
                data, U256(96) + base_length, min(U256(32), exp_length)
44
            )
45
        )
46
47
    charge_gas(
48
        evm,
49
        gas_cost(base_length, modulus_length, exp_length, exp_head),
50
    )
51
52
    # OPERATION
53
    if base_length == 0 and modulus_length == 0:
54
        evm.output = Bytes()
55
        return
56
57
    exp_start = U256(96) + base_length
58
    base = Uint.from_be_bytes(buffer_read(data, U256(96), base_length))
59
    exp = Uint.from_be_bytes(buffer_read(data, exp_start, exp_length))
60
61
    modulus_start = exp_start + exp_length
62
    modulus = Uint.from_be_bytes(
63
        buffer_read(data, modulus_start, modulus_length)
64
    )
65
66
    if modulus == 0:
67
        evm.output = Bytes(b"\x00") * modulus_length
68
    else:
69
        evm.output = pow(base, exp, modulus).to_bytes(
70
            Uint(modulus_length), "big"
71
        )

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:
75
    <snip>
92
    max_length = max(Uint(base_length), Uint(modulus_length))
93
    if max_length <= Uint(64):
94
        return max_length ** Uint(2)
95
    elif max_length <= Uint(1024):
96
        return (
97
            max_length ** Uint(2) // Uint(4)
98
            + Uint(96) * max_length
99
            - Uint(3072)
100
        )
101
    else:
102
        return (
103
            max_length ** Uint(2) // Uint(16)
104
            + Uint(480) * max_length
105
            - Uint(199680)
106
        )

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:
110
    <snip>
129
    if exponent_length < U256(32):
130
        adjusted_exp_length = Uint(max(0, int(exponent_head.bit_length()) - 1))
131
    else:
132
        adjusted_exp_length = Uint(
133
            8 * (int(exponent_length) - 32)
134
            + max(0, int(exponent_head.bit_length()) - 1)
135
        )
136
137
    return max(adjusted_exp_length, 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:
146
    <snip>
170
    multiplication_complexity = complexity(base_length, modulus_length)
171
    iteration_count = iterations(exponent_length, exponent_head)
172
    cost = multiplication_complexity * iteration_count
173
    cost //= GQUADDIVISOR
174
    return cost