pallet_evm_precompile_modexp/
lib.rs

1// This file is part of Frontier.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18#![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
38// Calculate gas cost according to EIP 2565:
39// https://eips.ethereum.org/EIPS/eip-2565
40fn 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		// Note: can't overflow because we take words to be some u64 value / 8, which is
55		// necessarily less than sqrt(u64::MAX).
56		// Additionally, both base_length and mod_length are bounded to 1024, so this has
57		// an upper bound of roughly (1024 / 8) squared
58		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			// from the EIP spec:
71			// (8 * (exp_length - 32)) + ((exponent & (2**256 - 1)).bit_length() - 1)
72			//
73			// Notes:
74			// * exp_length is bounded to 1024 and is > 32
75			// * exponent can be zero, so we subtract 1 after adding the other terms (whose sum
76			//   must be > 0)
77			// * the addition can't overflow because the terms are both capped at roughly
78			//   8 * max size of exp_length (1024)
79			// * the EIP spec is written in python, in which (exponent & (2**256 - 1)) takes the
80			//   FIRST 32 bytes. However this `BigUint` `&` operator takes the LAST 32 bytes.
81			//   We thus instead take the bytes manually.
82			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
99/// Copy bytes from input to target.
100fn read_input(source: &[u8], target: &mut [u8], source_offset: &mut usize) {
101	// We move the offset by the len of the target, regardless of what we
102	// actually copy.
103	let offset = *source_offset;
104	*source_offset += target.len();
105
106	// Out of bounds, nothing to copy.
107	if source.len() <= offset {
108		return;
109	}
110
111	// Find len to copy up to target len, but not out of bounds.
112	let len = core::cmp::min(target.len(), source.len() - offset);
113	target[..len].copy_from_slice(&source[offset..][..len]);
114}
115
116// ModExp expects the following as inputs:
117// 1) 32 bytes expressing the length of base
118// 2) 32 bytes expressing the length of exponent
119// 3) 32 bytes expressing the length of modulus
120// 4) base, size as described above
121// 5) exponent, size as described above
122// 6) modulus, size as described above
123//
124//
125// NOTE: input sizes are bound to 1024 bytes, with the expectation
126//       that gas limits would be applied before actual computation.
127//
128//       maximum stack size will also prevent abuse.
129//
130//       see: https://eips.ethereum.org/EIPS/eip-198
131
132impl Precompile for Modexp {
133	fn execute(handle: &mut impl PrecompileHandle) -> PrecompileResult {
134		let input = handle.input();
135		let mut input_offset = 0;
136
137		// Yellowpaper: whenever the input is too short, the missing bytes are
138		// considered to be zero.
139		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		// reasonable assumption: this must fit within the Ethereum EVM's max stack size
147		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		// bounds check handled above
171		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 is 0 output must be empty
176		if mod_len == 0 {
177			return Ok(PrecompileOutput {
178				exit_status: ExitSucceed::Returned,
179				output: vec![],
180			});
181		}
182
183		// Gas formula allows arbitrary large exp_len when base and modulus are empty, so we need to handle empty base first.
184		let r = if base_len == 0 && mod_len == 0 {
185			handle.record_cost(MIN_GAS_COST)?;
186			BigUint::zero()
187		} else {
188			// read the numbers themselves.
189			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			// do our gas accounting
202			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		// write output to given memory, left padded and same length as the modulus.
220		let bytes = r.to_bytes_be();
221
222		// always true except in the case of zero-length modulus, which leads to
223		// output of length and value 1.
224		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"); // TODO: how to pass error on?
278			}
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"); // TODO: how to pass error on?
308			}
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		// 3 ^ 5 % 7 == 5
360
361		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); // should be same length as mod
374				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"); // TODO: how to pass error on?
380			}
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		// 59999 ^ 21 % 14452 = 10055
397
398		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); // should be same length as mod
411				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"); // TODO: how to pass error on?
417			}
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); // should be same length as mod
446				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"); // TODO: how to pass error on?
452			}
453		}
454	}
455
456	#[test]
457	fn test_zero_exp_with_33_length() {
458		// This is a regression test which ensures that the 'iteration_count' calculation
459		// in 'calculate_iteration_count' cannot underflow.
460		//
461		// In debug mode, this underflow could cause a panic. Otherwise, it causes N**0 to
462		// be calculated at more-than-normal expense.
463		//
464		// TODO: cite security advisory
465
466		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); // should be same length as mod
488		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); // gas used when ran in geth (x20)
523	}
524}