ethereum.istanbul.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 | """ |
---|---|
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 = Uint.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 |
|
75 | base_length : |
76 | Length of the array representing the base integer. |
77 |
|
78 | modulus_length : |
79 | Length of the array representing the modulus integer. |
80 |
|
81 | Returns |
82 | ------- |
83 |
|
84 | complexity : `Uint` |
85 | Complexity of performing the operation. |
86 | """ |
87 | max_length = max(Uint(base_length), Uint(modulus_length)) |
88 | if max_length <= Uint(64): |
89 | return max_length ** Uint(2) |
90 | elif max_length <= Uint(1024): |
91 | return ( |
92 | max_length ** Uint(2) // Uint(4) |
93 | + Uint(96) * max_length |
94 | - Uint(3072) |
95 | ) |
96 | else: |
97 | return ( |
98 | max_length ** Uint(2) // Uint(16) |
99 | + Uint(480) * max_length |
100 | - Uint(199680) |
101 | ) |
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:
105 | """ |
---|---|
106 | Calculate the number of iterations required to perform a modular |
107 | exponentiation. |
108 |
|
109 | Parameters |
110 | ---------- |
111 |
|
112 | exponent_length : |
113 | Length of the array representing the exponent integer. |
114 |
|
115 | exponent_head : |
116 | First 32 bytes of the exponent (with leading zero padding if it is |
117 | shorter than 32 bytes), as an unsigned integer. |
118 |
|
119 | Returns |
120 | ------- |
121 |
|
122 | iterations : `Uint` |
123 | Number of iterations. |
124 | """ |
125 | if exponent_length < U256(32): |
126 | adjusted_exp_length = Uint(max(0, int(exponent_head.bit_length()) - 1)) |
127 | else: |
128 | adjusted_exp_length = Uint( |
129 | 8 * (int(exponent_length) - 32) |
130 | + max(0, int(exponent_head.bit_length()) - 1) |
131 | ) |
132 | |
133 | 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 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:
142 | """ |
---|---|
143 | Calculate the gas cost of performing a modular exponentiation. |
144 |
|
145 | Parameters |
146 | ---------- |
147 |
|
148 | base_length : |
149 | Length of the array representing the base integer. |
150 |
|
151 | modulus_length : |
152 | Length of the array representing the modulus integer. |
153 |
|
154 | exponent_length : |
155 | Length of the array representing the exponent integer. |
156 |
|
157 | exponent_head : |
158 | First 32 bytes of the exponent (with leading zero padding if it is |
159 | shorter than 32 bytes), as an unsigned integer. |
160 |
|
161 | Returns |
162 | ------- |
163 |
|
164 | gas_cost : `Uint` |
165 | Gas required for performing the operation. |
166 | """ |
167 | multiplication_complexity = complexity(base_length, modulus_length) |
168 | iteration_count = iterations(exponent_length, exponent_head) |
169 | cost = multiplication_complexity * iteration_count |
170 | cost //= GQUADDIVISOR |
171 | return cost |