bug: ADDMOD performs operations MOD 2^256

[greged93]

Bug Report

Kakarot version: ee6458a

Current behavior:
The add mod opcode performs addition of two uint256, without handling the one bit carry returned by the uint256_add. This causes the addition to be performed modulo 2^256, which shouldn't be the case (see Ethereum yellow paper opcode ADDMOD).

Expected behavior:

kakarot/src/kakarot/instructions/stop_and_arithmetic_operations.cairo

Lines 320 to 333 in ee6458a

	// Stack input:
	// 0 - a: number.
	// 1 - b: number.
	// 1 - c: modulo.
	let stack = ctx.stack;
	let (stack, popped) = Stack.pop_n(self=stack, n=3);
	let a = popped[0];
	let b = popped[1];
	let c = popped[2];
	// Compute the addition
	let (result, _) = uint256_add(a, b);
	// Compute the modulo
	let (_, rem) = uint256_unsigned_div_rem(result, c);

The add mod opcode should return the operation (a+b)%c, without subjecting the intermediate result a+b to modulo 2^256. However, since the bit carry from uint256_add isn't used, the operation is performed modulo 2^256.

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

RUN_SPECIFIC_TESTS=addmod_d10g0v0_Shanghai cargo test -p ef-testing --features ef-tests -- --nocapture

This test will fail due to the incorrect addition performed modulo 2^256:
https://github.com/ethereum/tests/blob/develop/src/GeneralStateTestsFiller/VMTests/vmArithmeticTest/addmodFiller.yml#L109

Indeed, in our case, the performed operation is: (-1 + -2) % 5 = ((0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe) % 2^256) % 5 = (0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd % 2^256) % 5 = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd % 5 = 3.

Failing output should be:

[!] Case /Users/greg/code/rust/ef-tests/crates/ef-testing/ethereum-tests/BlockchainTests/GeneralStateTests/VMTests/vmArithmeticTest/addmod.json failed (description: addmod): Test failed: failed test addmod_d10g0v0_Shanghai: expected storage value 0x0000000000000000000000000000000000000000000000000000000000000004, got 0x0000000000000000000000000000000000000000000000000000000000000003

[Eikix]

A duplicate of #678, but let's keep this one, it's more detailed

[feltroidprime]

can do add mod in 15 steps for 10 XMR if you want