2

In the EVM, the MUL opcode costs 5 gas and is used to perform multiplication. For example, the arithmetic behind computing 20 * 30 = 600 should cost 5 gas. The EXP opcode is used to perform exponentiation, and its gas cost is variable and determined by a formula: 10 gas plus 50 times the number of bytes in the exponent. For example, the arithmetic of computing 10^27 should cost 10 + 50 * 1 = 60 gas, while 10^400 would cost 10 + 50 * 2 = 160 gas, since it takes one byte to represent 27<256 = 2^8 and two bytes to represent 400<65536=2^16. So we are basically pricing ~10 multiplication operations for a byte.

We can of course implement our own exponentation algorithm in Solidity/Yul. A common instance used in many DeFi projects being the "exponentiation by squaring" method which computes x^n recursively:

  • If n is even, then x^n = (x^2)^(n/2).

  • If n is odd, then x^n = x * x^(n-1), but then n-1 is even and applying the equation above gives:

    x^n = x * (x^2)^((n-1) / 2).

This calculates x^n in O(log n) instead of O(n) multiplications for the naive repeated multiplication. For example, this is what is in DS-Math library rpow function implements. This method would clearly be more efficient for small numbers, and numbers whose binary representation is "very sparse" but not in general.

My question is:

  1. Does anybody know what is the cost model the Ethereum Foundation based this on? Is there a public study in numerical analysis that ~10 multiplication is the right number?
  2. Is there a good heuristic for when and how to use the EXP opcode in terms of gas cost?
Improve this question

2 Answers 2

Reset to default
3

The gas cost of the MUL opcode is set to 5 units because multiplication is a relatively simple operation that does not require many resources. The gas cost of the EXP opcode is more complex because it is determined by a formula that considers the number of bytes in the exponent. This is because exponentiation is a more complex operation than multiplication, and the amount of resources required to perform exponentiation increases with the size of the exponent.

In terms of using the EXP opcode, a good heuristic is to consider the size of the exponent and the potential gas savings from using the EXP opcode instead of implementing exponentiation using multiplication. For small exponents, using the EXP opcode may not be cost-effective because the gas cost of the opcode will be higher than the cost of performing exponentiation using multiplication. However, for larger exponents, using the EXP opcode may be more cost-effective because it will take fewer multiplications to compute the exponent, resulting in lower overall gas costs.

Improve this answer
1

EIP-160: EXP cost increase simply states "Benchmarks suggest that EXP is currently underpriced by a factor of about 4–8".

Other mentions about the EXP attack I've found are:

Attacks using EXP were in a latter phase of the Shanghai Attacks; the earlier attacks are discussed in:

https://2017.edcon.io/ppt/one/Martin%20Holst%20Swende_The%20%27Shanghai%20%27Attacks_EDCON.pdf

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.