Exponential Redundant Calculations in uint256_fast_exp used for EXP opcode

[howlbot-integration]

Lines of code

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/utils/uint256.cairo#L344-L373

Vulnerability details

Impact

The implementation of uint256_fast_exp performs redundant recursive calculations that grow exponentially for certain exponent values, particularly powers of 2. This results in significantly increased Cairo steps consumption (up to ~28,380 extra steps for exponent 128) and consequently higher gas costs. The issue affects the EXP opcode execution in Kakarot's EVM implementation.

The severity is high because:

• While gas costs stays the same, Cairo steps get significantly higher than necessary which the paymaster has to bear.
• The inefficiency grows exponentially with exponent size

Proof of Concept

func uint256_fast_exp{range_check_ptr}(value: Uint256, exponent: Uint256) -> Uint256 {
    alloc_locals;

    let one = Uint256(1, 0);
    let zero = Uint256(0, 0);

    let (exponent_is_zero) = uint256_eq(exponent, zero);
    if (exponent_is_zero != FALSE) {
        return one;
    }

    let (exponent_is_one) = uint256_eq(exponent, one);
    if (exponent_is_one != FALSE) {
        return value;
    }

    let (half_exponent, is_odd) = uint256_unsigned_div_rem(exponent, Uint256(2, 0));
    let pow = uint256_fast_exp(value, half_exponent);

    if (is_odd.low != FALSE) {
        let (res, _) = uint256_mul(pow, pow);
        let (res, _) = uint256_mul(res, value);
        return res;
    }

    let pow = uint256_fast_exp(value, half_exponent);  // Redundant call
    let (res, _) = uint256_mul(pow, pow);
    return res;
}

utils/uint256.cairo:L344-L373

The function makes a redundant recursive call in the even number case. Let's analyze the execution flow for exponent = 8 as an example:

1. Initial call with exponent = 8

   • Calculates half_exponent = 4
   • First recursive call with exponent = 4
   • Second redundant recursive call with exponent = 4

2. For each call with exponent = 4

   • Calculates half_exponent = 2
   • Makes two recursive calls with exponent = 2

3. For each call with exponent = 2

   • Calculates half_exponent = 1
   • Makes two recursive calls with exponent = 1

Total recursive calls:

• Level 1 (8): 1 call
• Level 2 (4): 2 calls
• Level 3 (2): 4 calls
• Level 4 (1): 8 calls

Results in 15 recursive calls instead of the optimal 4 calls!

Cairo steps rough estimation:

Assume operations costs as follows:
- uint256_eq: ~10 steps
- uint256_unsigned_div_rem: ~100 steps
- uint256_mul: ~50 steps

For each regular call we need: two of uint256_eq,uint256_unsigned_div_rem, uint256_mul => 2*10 + 100 + 50 => 170

Current implementation (15 calls):
Level 1 (8):   1 * ~170 = ~170 steps
Level 2 (4):   2 * ~170 = ~340 steps
Level 3 (2):   4 * ~170 = ~680 steps
Level 4 (1):   8 * ~20  = ~160 steps
Total: ~1350 steps

Optimal implementation (4 calls):
Level 1-3:     3 * ~170 = ~510 steps
Level 4:       1 * ~20  = ~20 steps
Total: ~530 steps

Extra steps: ~820
That's 150% extra Cairo steps which is significant 

This inefficiency grows exponentially, for larger powers of 2:

• N = 16: ~2700 extra steps
• N = 32: ~6160 extra steps
• N = 64: ~13520 extra steps
• N = 128: ~28380 extra steps

Note: those are rough estimations, Cairo steps count changes based on the execution trace.

Tools Used

Manual Review

Recommended Mitigation Steps

Remove the redundant recursive call in the even number case and reuse the result from the first call.

Assessed type

Other

[ClementWalter]

Severity: Informative

Comment: This is not a security risk. Only useless computation.

[c4-judge]

dmvt changed the severity to QA (Quality Assurance)

[c4-judge]

dmvt marked the issue as grade-b