ethereum.gray_glacier.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:
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 | words = (max_length + Uint(7)) // Uint(8) |
89 | 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 an unsigned integer.
Returns
iterations : Uint
Number of iterations.
def iterations(exponent_length: U256, exponent_head: Uint) -> Uint:
93 | """ |
---|---|
94 | Calculate the number of iterations required to perform a modular |
95 | exponentiation. |
96 |
|
97 | Parameters |
98 | ---------- |
99 |
|
100 | exponent_length : |
101 | Length of the array representing the exponent integer. |
102 |
|
103 | exponent_head : |
104 | First 32 bytes of the exponent (with leading zero padding if it is |
105 | shorter than 32 bytes), as an unsigned integer. |
106 |
|
107 | Returns |
108 | ------- |
109 |
|
110 | iterations : `Uint` |
111 | Number of iterations. |
112 | """ |
113 | if exponent_length <= U256(32) and exponent_head == U256(0): |
114 | count = Uint(0) |
115 | elif exponent_length <= U256(32): |
116 | bit_length = Uint(exponent_head.bit_length()) |
117 |
|
118 | if bit_length > Uint(0): |
119 | bit_length -= Uint(1) |
120 |
|
121 | count = bit_length |
122 | else: |
123 | length_part = Uint(8) * (Uint(exponent_length) - Uint(32)) |
124 | bits_part = Uint(exponent_head.bit_length()) |
125 |
|
126 | if bits_part > Uint(0): |
127 | bits_part -= Uint(1) |
128 |
|
129 | count = length_part + bits_part |
130 | |
131 | 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:
140 | """ |
---|---|
141 | Calculate the gas cost of performing a modular exponentiation. |
142 |
|
143 | Parameters |
144 | ---------- |
145 |
|
146 | base_length : |
147 | Length of the array representing the base integer. |
148 |
|
149 | modulus_length : |
150 | Length of the array representing the modulus integer. |
151 |
|
152 | exponent_length : |
153 | Length of the array representing the exponent integer. |
154 |
|
155 | exponent_head : |
156 | First 32 bytes of the exponent (with leading zero padding if it is |
157 | shorter than 32 bytes), as an unsigned integer. |
158 |
|
159 | Returns |
160 | ------- |
161 |
|
162 | gas_cost : `Uint` |
163 | Gas required for performing the operation. |
164 | """ |
165 | multiplication_complexity = complexity(base_length, modulus_length) |
166 | iteration_count = iterations(exponent_length, exponent_head) |
167 | cost = multiplication_complexity * iteration_count |
168 | cost //= GQUADDIVISOR |
169 | return max(Uint(200), cost) |