bug: exponentiation will run indef. for high exponent - Issue Imported from Kakarot Cairo0

[Eikix]

Bug Report

Kakarot version: ee6458a

Current behavior:
Given a high exponent value when calling the EXP opcode, the transaction will run out of resources. This is due to the fact that we don't use the fast powering algorithm for high exponent values. See code below:
https://github.com/kkrt-labs/kakarot/blob/95df46cf88a4225d26e7a642fe2d149b41c55249/src/kakarot/instructions/stop_and_arithmetic_operations.cairo#L462-L466

Expected behavior:
Exponentiation should work for high value of exponent.

Steps to reproduce:

• clone ef-tests: https://github.com/kkrt-labs/ef-tests
• generate katana dump of kakarot system and move the .katana folder to your ef-tests directory
• run

TARGET=expPower256_d0g0v0_Shanghai cargo test -p ef-testing --features ef-tests -- --nocapture

Failing output should be:

2023-08-25T09:40:07.242339Z  WARN katana_core::backend::executor: Transaction execution error: "Error in the called contract (0x04e2460d0debdacdde372cb598b4e4403939ca112c8720e1c2aca13f6ac09b9a):
Error at pc=0:7:
Got an exception while executing a hint.
Cairo traceback (most recent call last):
Unknown location (pc=0:163)
Unknown location (pc=0:149)

Error in the called contract (0x04e2460d0debdacdde372cb598b4e4403939ca112c8720e1c2aca13f6ac09b9a):
Error at pc=0:31:
Got an exception while executing a hint.
Cairo traceback (most recent call last):
Unknown location (pc=0:4606)
Unknown location (pc=0:4545)
Unknown location (pc=0:4374)
Unknown location (pc=0:376)

Error in the called contract (0x049c085e55e5ab05ea46e16706720852421e86c1f8aeeab2be257313c4e290f4):
Error at pc=0:490:
Could not reach the end of the program. RunResources has no remaining steps.
Cairo traceback (most recent call last):
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18120)
Unknown location (pc=0:18022)
Unknown location (pc=0:17250)
Unknown location (pc=0:9424)
"
[!] Case ~/code/rust/ef-tests/crates/ef-testing/ethereum-tests/BlockchainTests/GeneralStateTests/VMTests/vmArithmeticTest/expPower256.json failed (description: expPower256): Test failed: failed test expPower256_d0g0v0_Shanghai: expected storage value 0x0000000000000000000000000000000000000000000000000000000000000001, got 0x0000000000000000000000000000000000000000000000000000000000000000

[Eikix]

This issue applies to Kakarot SSJ as well, we chose an algorithm in O(n) instead of O(log(n)) because for reasonably small values, division is more expensive than recursively multiplying more times in Cairo.

impl U256ExpModImpl of ExponentiationModulo<u256> {
    fn pow_mod(self: u256, mut exponent: u256) -> u256 {
        if self == 0 {
            return 0;
        }
        let mut result = 1;
        loop {
            if exponent == 0 {
                break;
            }
            let (new_result, _) = u256_overflow_mul(result, self);
            result = new_result;
            exponent -= 1;
        };
        result
    }
}

impl U256ExpImpl of Exponentiation<u256> {
    fn pow(self: u256, exp: u256) -> u256 {
        if self == 0 {
            return 0;
        }
        if exp == 0 {
            return 1;
        } else {
            return self * Exponentiation::pow(self, exp - 1);
        }
    }
}

[enitrat]

solution -> codegen tests comparing pow and fpow for multiple exponents values. Draw the curves, find the inflexion point, produce report in discussions

[Eikix]

Important update: we are gathering some bugs in the Kakarot v0 codebase, we need to make sure each issue and each PR in Kakarot-ssj is aware of the lists of known bugs. Look at this link everytime you take an issue and check your issue isn't targeted by a known bug.

[Eikix]

Important update: we are gathering some bugs in the Kakarot v0 codebase, we need to make sure each issue and each PR in Kakarot-ssj is aware of the lists of known bugs. Look at this tracking issue everytime you take an issue and check your issue isn't targeted by a known bug. Will add this reminder in many places to make sure we keep track of known bugs.

[greged93]

@enitrat are you working on this? I can take over otherwise

[Eikix]

You can take it, @enitrat is working on sstore rn

[greged93]

So I ran $2^x$ for x in $[0; 100]$, here is the result. Based on this I think using fast powering algorithm for any exponant higher than 10 should be safe.

[enitrat]

nice!

[Eikix]

Sounds good to open a PR and perform "either or" techniques depending if n > 10 or <

[enitrat]

since fpow uses div we can't have fast exponentiation for felts

[greged93]

I was checking the codebase: do we need pow for felts? I see it's only used for bitshift but I'm not sure we need bitshift either for felt.

[enitrat]

It looks like Felt252WrappingBitshiftImpl and U128WrappingBitshiftImpl aren't used - only U256WrappingBitshift is used which makes sense in an EVM world.

It also looks like only U256WrappingPow is used - I propose that we clean unused implems from the codebase. I think these implems became useless once we moved to hardcoded POW_2 constant, and we haven't cleaned them. So not having pow for felt252 doesn't matter anymore 😄