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