1#![cfg_attr(not(feature = "std"), no_std)]
19#![allow(clippy::comparison_chain)]
20#![warn(unused_crate_dependencies)]
21
22extern crate alloc;
23
24use alloc::{vec, vec::Vec};
25use core::cmp::max;
26
27use num::{BigUint, FromPrimitive, Integer, One, ToPrimitive, Zero};
28
29use fp_evm::{
30 ExitError, ExitSucceed, Precompile, PrecompileFailure, PrecompileHandle, PrecompileOutput,
31 PrecompileResult,
32};
33
34pub struct Modexp;
35
36const MIN_GAS_COST: u64 = 200;
37
38fn calculate_gas_cost(
41 base_length: u64,
42 mod_length: u64,
43 exponent: &BigUint,
44 exponent_bytes: &[u8],
45 mod_is_even: bool,
46) -> u64 {
47 fn calculate_multiplication_complexity(base_length: u64, mod_length: u64) -> u64 {
48 let max_length = max(base_length, mod_length);
49 let mut words = max_length / 8;
50 if max_length % 8 > 0 {
51 words += 1;
52 }
53
54 words * words
59 }
60
61 fn calculate_iteration_count(exponent: &BigUint, exponent_bytes: &[u8]) -> u64 {
62 let mut iteration_count: u64 = 0;
63 let exp_length = exponent_bytes.len() as u64;
64
65 if exp_length <= 32 && exponent.is_zero() {
66 iteration_count = 0;
67 } else if exp_length <= 32 {
68 iteration_count = exponent.bits() - 1;
69 } else if exp_length > 32 {
70 let exponent_head = BigUint::from_bytes_be(&exponent_bytes[..32]);
83
84 iteration_count = (8 * (exp_length - 32)) + exponent_head.bits() - 1;
85 }
86
87 max(iteration_count, 1)
88 }
89
90 let multiplication_complexity = calculate_multiplication_complexity(base_length, mod_length);
91 let iteration_count = calculate_iteration_count(exponent, exponent_bytes);
92 max(
93 MIN_GAS_COST,
94 multiplication_complexity * iteration_count / 3,
95 )
96 .saturating_mul(if mod_is_even { 20 } else { 1 })
97}
98
99fn read_input(source: &[u8], target: &mut [u8], source_offset: &mut usize) {
101 let offset = *source_offset;
104 *source_offset += target.len();
105
106 if source.len() <= offset {
108 return;
109 }
110
111 let len = core::cmp::min(target.len(), source.len() - offset);
113 target[..len].copy_from_slice(&source[offset..][..len]);
114}
115
116impl Precompile for Modexp {
133 fn execute(handle: &mut impl PrecompileHandle) -> PrecompileResult {
134 let input = handle.input();
135 let mut input_offset = 0;
136
137 let mut base_len_buf = [0u8; 32];
140 read_input(input, &mut base_len_buf, &mut input_offset);
141 let mut exp_len_buf = [0u8; 32];
142 read_input(input, &mut exp_len_buf, &mut input_offset);
143 let mut mod_len_buf = [0u8; 32];
144 read_input(input, &mut mod_len_buf, &mut input_offset);
145
146 let max_size_big = BigUint::from_u32(1024).expect("can't create BigUint");
148
149 let base_len_big = BigUint::from_bytes_be(&base_len_buf);
150 if base_len_big > max_size_big {
151 return Err(PrecompileFailure::Error {
152 exit_status: ExitError::Other("unreasonably large base length".into()),
153 });
154 }
155
156 let exp_len_big = BigUint::from_bytes_be(&exp_len_buf);
157 if exp_len_big > max_size_big {
158 return Err(PrecompileFailure::Error {
159 exit_status: ExitError::Other("unreasonably large exponent length".into()),
160 });
161 }
162
163 let mod_len_big = BigUint::from_bytes_be(&mod_len_buf);
164 if mod_len_big > max_size_big {
165 return Err(PrecompileFailure::Error {
166 exit_status: ExitError::Other("unreasonably large modulus length".into()),
167 });
168 }
169
170 let base_len = base_len_big.to_usize().expect("base_len out of bounds");
172 let exp_len = exp_len_big.to_usize().expect("exp_len out of bounds");
173 let mod_len = mod_len_big.to_usize().expect("mod_len out of bounds");
174
175 if mod_len == 0 {
177 return Ok(PrecompileOutput {
178 exit_status: ExitSucceed::Returned,
179 output: vec![],
180 });
181 }
182
183 let r = if base_len == 0 && mod_len == 0 {
185 handle.record_cost(MIN_GAS_COST)?;
186 BigUint::zero()
187 } else {
188 let mut base_buf = vec![0u8; base_len];
190 read_input(input, &mut base_buf, &mut input_offset);
191 let base = BigUint::from_bytes_be(&base_buf);
192
193 let mut exp_buf = vec![0u8; exp_len];
194 read_input(input, &mut exp_buf, &mut input_offset);
195 let exponent = BigUint::from_bytes_be(&exp_buf);
196
197 let mut mod_buf = vec![0u8; mod_len];
198 read_input(input, &mut mod_buf, &mut input_offset);
199 let modulus = BigUint::from_bytes_be(&mod_buf);
200
201 let gas_cost = calculate_gas_cost(
203 base_len as u64,
204 mod_len as u64,
205 &exponent,
206 &exp_buf,
207 modulus.is_even(),
208 );
209
210 handle.record_cost(gas_cost)?;
211
212 if modulus.is_zero() || modulus.is_one() {
213 BigUint::zero()
214 } else {
215 base.modpow(&exponent, &modulus)
216 }
217 };
218
219 let bytes = r.to_bytes_be();
221
222 if bytes.len() == mod_len {
225 Ok(PrecompileOutput {
226 exit_status: ExitSucceed::Returned,
227 output: bytes.to_vec(),
228 })
229 } else if bytes.len() < mod_len {
230 let mut ret = Vec::with_capacity(mod_len);
231 ret.extend(core::iter::repeat_n(0, mod_len - bytes.len()));
232 ret.extend_from_slice(&bytes[..]);
233 Ok(PrecompileOutput {
234 exit_status: ExitSucceed::Returned,
235 output: ret.to_vec(),
236 })
237 } else {
238 Err(PrecompileFailure::Error {
239 exit_status: ExitError::Other("failed".into()),
240 })
241 }
242 }
243}
244
245#[cfg(test)]
246mod tests {
247 use super::*;
248 extern crate hex;
249 use fp_evm::Context;
250 use pallet_evm_test_vector_support::{test_precompile_test_vectors, MockHandle};
251
252 #[test]
253 fn process_consensus_tests() -> Result<(), String> {
254 test_precompile_test_vectors::<Modexp>("../testdata/modexp_eip2565.json")?;
255 Ok(())
256 }
257
258 #[test]
259 fn test_empty_input() {
260 let input = Vec::new();
261
262 let cost: u64 = 1;
263
264 let context: Context = Context {
265 address: Default::default(),
266 caller: Default::default(),
267 apparent_value: From::from(0),
268 };
269
270 let mut handle = MockHandle::new(input, Some(cost), context);
271
272 match Modexp::execute(&mut handle) {
273 Ok(precompile_result) => {
274 assert_eq!(precompile_result.output.len(), 0);
275 }
276 Err(_) => {
277 panic!("Modexp::execute() returned error"); }
279 }
280 }
281
282 #[test]
283 fn test_insufficient_input() {
284 let input = hex::decode(
285 "0000000000000000000000000000000000000000000000000000000000000001\
286 0000000000000000000000000000000000000000000000000000000000000001\
287 0000000000000000000000000000000000000000000000000000000000000001",
288 )
289 .expect("Decode failed");
290
291 let cost: u64 = 1;
292
293 let context: Context = Context {
294 address: Default::default(),
295 caller: Default::default(),
296 apparent_value: From::from(0),
297 };
298
299 let mut handle = MockHandle::new(input, Some(cost), context);
300
301 match Modexp::execute(&mut handle) {
302 Ok(precompile_result) => {
303 assert_eq!(precompile_result.output.len(), 1);
304 assert_eq!(precompile_result.output, vec![0x00]);
305 }
306 Err(_) => {
307 panic!("Modexp::execute() returned error"); }
309 }
310 }
311
312 #[test]
313 fn test_excessive_input() -> Result<(), PrecompileFailure> {
314 let input = hex::decode(
315 "1000000000000000000000000000000000000000000000000000000000000001\
316 0000000000000000000000000000000000000000000000000000000000000001\
317 0000000000000000000000000000000000000000000000000000000000000001",
318 )
319 .expect("Decode failed");
320
321 let cost: u64 = 1;
322
323 let context: Context = Context {
324 address: Default::default(),
325 caller: Default::default(),
326 apparent_value: From::from(0),
327 };
328
329 let mut handle = MockHandle::new(input, Some(cost), context);
330
331 match Modexp::execute(&mut handle) {
332 Ok(_) => {
333 panic!("Test not expected to pass");
334 }
335 Err(e) => {
336 assert_eq!(
337 e,
338 PrecompileFailure::Error {
339 exit_status: ExitError::Other("unreasonably large base length".into())
340 }
341 );
342 Ok(())
343 }
344 }
345 }
346
347 #[test]
348 fn test_simple_inputs() {
349 let input = hex::decode(
350 "0000000000000000000000000000000000000000000000000000000000000001\
351 0000000000000000000000000000000000000000000000000000000000000001\
352 0000000000000000000000000000000000000000000000000000000000000001\
353 03\
354 05\
355 07",
356 )
357 .expect("Decode failed");
358
359 let cost: u64 = 100000;
362
363 let context: Context = Context {
364 address: Default::default(),
365 caller: Default::default(),
366 apparent_value: From::from(0),
367 };
368
369 let mut handle = MockHandle::new(input, Some(cost), context);
370
371 match Modexp::execute(&mut handle) {
372 Ok(precompile_result) => {
373 assert_eq!(precompile_result.output.len(), 1); let result = BigUint::from_bytes_be(&precompile_result.output[..]);
375 let expected = BigUint::parse_bytes(b"5", 10).unwrap();
376 assert_eq!(result, expected);
377 }
378 Err(_) => {
379 panic!("Modexp::execute() returned error"); }
381 }
382 }
383
384 #[test]
385 fn test_large_inputs() {
386 let input = hex::decode(
387 "0000000000000000000000000000000000000000000000000000000000000020\
388 0000000000000000000000000000000000000000000000000000000000000020\
389 0000000000000000000000000000000000000000000000000000000000000020\
390 000000000000000000000000000000000000000000000000000000000000EA5F\
391 0000000000000000000000000000000000000000000000000000000000000015\
392 0000000000000000000000000000000000000000000000000000000000003874",
393 )
394 .expect("Decode failed");
395
396 let cost: u64 = 100000;
399
400 let context: Context = Context {
401 address: Default::default(),
402 caller: Default::default(),
403 apparent_value: From::from(0),
404 };
405
406 let mut handle = MockHandle::new(input, Some(cost), context);
407
408 match Modexp::execute(&mut handle) {
409 Ok(precompile_result) => {
410 assert_eq!(precompile_result.output.len(), 32); let result = BigUint::from_bytes_be(&precompile_result.output[..]);
412 let expected = BigUint::parse_bytes(b"10055", 10).unwrap();
413 assert_eq!(result, expected);
414 }
415 Err(_) => {
416 panic!("Modexp::execute() returned error"); }
418 }
419 }
420
421 #[test]
422 fn test_large_computation() {
423 let input = hex::decode(
424 "0000000000000000000000000000000000000000000000000000000000000001\
425 0000000000000000000000000000000000000000000000000000000000000020\
426 0000000000000000000000000000000000000000000000000000000000000020\
427 03\
428 fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e\
429 fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
430 )
431 .expect("Decode failed");
432
433 let cost: u64 = 100000;
434
435 let context: Context = Context {
436 address: Default::default(),
437 caller: Default::default(),
438 apparent_value: From::from(0),
439 };
440
441 let mut handle = MockHandle::new(input, Some(cost), context);
442
443 match Modexp::execute(&mut handle) {
444 Ok(precompile_result) => {
445 assert_eq!(precompile_result.output.len(), 32); let result = BigUint::from_bytes_be(&precompile_result.output[..]);
447 let expected = BigUint::parse_bytes(b"1", 10).unwrap();
448 assert_eq!(result, expected);
449 }
450 Err(_) => {
451 panic!("Modexp::execute() returned error"); }
453 }
454 }
455
456 #[test]
457 fn test_zero_exp_with_33_length() {
458 let input = vec![
467 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
468 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
469 0, 0, 0, 0, 0, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
470 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
471 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
472 ];
473
474 let cost: u64 = 100000;
475
476 let context: Context = Context {
477 address: Default::default(),
478 caller: Default::default(),
479 apparent_value: From::from(0),
480 };
481
482 let mut handle = MockHandle::new(input, Some(cost), context);
483
484 let precompile_result =
485 Modexp::execute(&mut handle).expect("Modexp::execute() returned error");
486
487 assert_eq!(precompile_result.output.len(), 1); let result = BigUint::from_bytes_be(&precompile_result.output[..]);
489 let expected = BigUint::parse_bytes(b"0", 10).unwrap();
490 assert_eq!(result, expected);
491 }
492
493 #[test]
494 fn test_long_exp_gas_cost_matches_specs() {
495 let input = vec![
496 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
497 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
498 0, 0, 0, 0, 0, 38, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
499 0, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
500 16, 0, 0, 0, 255, 255, 255, 2, 0, 0, 179, 0, 0, 2, 0, 0, 122, 0, 0, 0, 0, 0, 0, 0, 0,
501 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
502 0, 0, 0, 0, 0, 0, 0, 0, 255, 251, 0, 0, 0, 0, 4, 38, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
503 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
504 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
505 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
506 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 255, 255, 255, 2, 0, 0, 179, 0, 0, 0, 0, 0, 0, 0, 0,
507 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
508 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255,
509 255, 255, 255, 249,
510 ];
511
512 let context: Context = Context {
513 address: Default::default(),
514 caller: Default::default(),
515 apparent_value: From::from(0),
516 };
517
518 let mut handle = MockHandle::new(input, Some(100_000), context);
519
520 let _ = Modexp::execute(&mut handle).expect("Modexp::execute() returned error");
521
522 assert_eq!(handle.gas_used, 7104 * 20); }
524}