ethereum.byzantium.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 = 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:
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 | if max_length <= 64: |
88 | return max_length**2 |
89 | elif max_length <= 1024: |
90 | return max_length**2 // 4 + 96 * max_length - 3072 |
91 | else: |
92 | return max_length**2 // 16 + 480 * max_length - 199680 |
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:
96 | """ |
---|---|
97 | Calculate the number of iterations required to perform a modular |
98 | exponentiation. |
99 |
|
100 | Parameters |
101 | ---------- |
102 |
|
103 | exponent_length : |
104 | Length of the array representing the exponent integer. |
105 |
|
106 | exponent_head : |
107 | First 32 bytes of the exponent (with leading zero padding if it is |
108 | shorter than 32 bytes), as an unsigned integer. |
109 |
|
110 | Returns |
111 | ------- |
112 |
|
113 | iterations : `Uint` |
114 | Number of iterations. |
115 | """ |
116 | if exponent_length < 32: |
117 | adjusted_exp_length = Uint(max(0, exponent_head.bit_length() - 1)) |
118 | else: |
119 | adjusted_exp_length = Uint( |
120 | 8 * (int(exponent_length) - 32) |
121 | + max(0, exponent_head.bit_length() - 1) |
122 | ) |
123 | |
124 | 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:
133 | """ |
---|---|
134 | Calculate the gas cost of performing a modular exponentiation. |
135 |
|
136 | Parameters |
137 | ---------- |
138 |
|
139 | base_length : |
140 | Length of the array representing the base integer. |
141 |
|
142 | modulus_length : |
143 | Length of the array representing the modulus integer. |
144 |
|
145 | exponent_length : |
146 | Length of the array representing the exponent integer. |
147 |
|
148 | exponent_head : |
149 | First 32 bytes of the exponent (with leading zero padding if it is |
150 | shorter than 32 bytes), as an unsigned integer. |
151 |
|
152 | Returns |
153 | ------- |
154 |
|
155 | gas_cost : `Uint` |
156 | Gas required for performing the operation. |
157 | """ |
158 | multiplication_complexity = complexity(base_length, modulus_length) |
159 | iteration_count = iterations(exponent_length, exponent_head) |
160 | cost = multiplication_complexity * iteration_count |
161 | cost //= GQUADDIVISOR |
162 | return cost |