test_worst_mod()

Documentation for tests/zkevm/test_worst_compute.py::test_worst_mod@64f949d0.

Generate fixtures for these test cases for Prague with:

fill -v tests/zkevm/test_worst_compute.py::test_worst_mod --fork Prague

Test running a block with as many MOD instructions with arguments of the parametrized range. The test program consists of code segments evaluating the "MOD chain": mod[0] = calldataload(0) mod[1] = numerators[indexes[0]] % mod[0] mod[2] = numerators[indexes[1]] % mod[1] ... The "numerators" is a pool of 15 constants pushed to the EVM stack at the program start. The order of accessing the numerators is selected in a way the mod value remains in the range as long as possible.

Source code in tests/zkevm/test_worst_compute.py

@pytest.mark.valid_from("Cancun")
@pytest.mark.parametrize("mod_bits", [255, 191, 127, 63])
@pytest.mark.parametrize("op", [Op.MOD, Op.SMOD])
def test_worst_mod(
    state_test: StateTestFiller,
    pre: Alloc,
    fork: Fork,
    mod_bits: int,
    op: Op,
):
    """
    Test running a block with as many MOD instructions with arguments of the parametrized range.
    The test program consists of code segments evaluating the "MOD chain":
    mod[0] = calldataload(0)
    mod[1] = numerators[indexes[0]] % mod[0]
    mod[2] = numerators[indexes[1]] % mod[1] ...
    The "numerators" is a pool of 15 constants pushed to the EVM stack at the program start.
    The order of accessing the numerators is selected in a way the mod value remains in the range
    as long as possible.
    """
    max_code_size = fork.max_code_size()

    # For SMOD we negate both numerator and modulus. The underlying computation is the same,
    # just the SMOD implementation will have to additionally handle the sign bits.
    # The result stays negative.
    should_negate = op == Op.SMOD

    num_numerators = 15
    numerator_bits = 256 if not should_negate else 255
    numerator_max = 2**numerator_bits - 1
    numerator_min = 2 ** (numerator_bits - 1)

    # Pick the modulus min value so that it is _unlikely_ to drop to the lower word count.
    assert mod_bits >= 63
    mod_min = 2 ** (mod_bits - 63)

    # Select the random seed giving the longest found MOD chain.
    # You can look for a longer one by increasing the numerators_min_len. This will activate
    # the while loop below.
    match op, mod_bits:
        case Op.MOD, 255:
            seed = 20393
            numerators_min_len = 750
        case Op.MOD, 191:
            seed = 25979
            numerators_min_len = 770
        case Op.MOD, 127:
            seed = 17671
            numerators_min_len = 750
        case Op.MOD, 63:
            seed = 29181
            numerators_min_len = 730
        case Op.SMOD, 255:
            seed = 4015
            numerators_min_len = 750
        case Op.SMOD, 191:
            seed = 17355
            numerators_min_len = 750
        case Op.SMOD, 127:
            seed = 897
            numerators_min_len = 750
        case Op.SMOD, 63:
            seed = 7562
            numerators_min_len = 720
        case _:
            raise ValueError(f"{mod_bits}-bit {op} not supported.")

    while True:
        rng = random.Random(seed)

        # Create the list of random numerators.
        numerators = [rng.randint(numerator_min, numerator_max) for _ in range(num_numerators)]

        # Create the random initial modulus.
        initial_mod = rng.randint(2 ** (mod_bits - 1), 2**mod_bits - 1)

        # Evaluate the MOD chain and collect the order of accessing numerators.
        mod = initial_mod
        indexes = []
        while mod >= mod_min:
            results = [n % mod for n in numerators]  # Compute results for each numerator.
            i = max(range(len(results)), key=results.__getitem__)  # And pick the best one.
            mod = results[i]
            indexes.append(i)

        assert len(indexes) > numerators_min_len  # Disable if you want to find longer MOD chains.
        if len(indexes) > numerators_min_len:
            break
        seed += 1
        print(f"{seed=}")

    # TODO: Don't use fixed PUSH32. Let Bytecode helpers to select optimal push opcode.
    code_constant_pool = sum((Op.PUSH32[n] for n in numerators), Bytecode())
    code_prefix = code_constant_pool + Op.JUMPDEST
    code_suffix = Op.JUMP(len(code_constant_pool))
    code_body_len = max_code_size - len(code_prefix) - len(code_suffix)
    code_segment = (
        Op.CALLDATALOAD(0) + sum(make_dup(len(numerators) - i) + op for i in indexes) + Op.POP
    )
    code = (
        code_prefix
        # TODO: Add int * Bytecode support
        + sum(code_segment for _ in range(code_body_len // len(code_segment)))
        + code_suffix
    )
    assert (max_code_size - len(code_segment)) < len(code) <= max_code_size

    env = Environment()

    input_value = initial_mod if not should_negate else neg(initial_mod)
    tx = Transaction(
        to=pre.deploy_contract(code=code),
        data=input_value.to_bytes(32, byteorder="big"),
        gas_limit=env.gas_limit,
        sender=pre.fund_eoa(),
    )

    state_test(
        env=env,
        pre=pre,
        post={},
        tx=tx,
    )

Parametrized Test Cases

The interactive table below is also available as a standalone page.

Fork All Forks Cancun Prague Osaka

Fixture Type All Fixture Types state_test blockchain_test

Test ID (Abbreviated)	op	mod_bits
...fork_Cancun-state_test-op_MOD-mod_bits_255	MOD	255
...fork_Cancun-state_test-op_MOD-mod_bits_191	MOD	191
...fork_Cancun-state_test-op_MOD-mod_bits_127	MOD	127
...fork_Cancun-state_test-op_MOD-mod_bits_63	MOD	63
...fork_Cancun-state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Cancun-state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Cancun-state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Cancun-state_test-op_SMOD-mod_bits_63	SMOD	63
...fork_Cancun-blockchain_test_from_state_test-op_MOD-mod_bits_255	MOD	255
...fork_Cancun-blockchain_test_from_state_test-op_MOD-mod_bits_191	MOD	191
...fork_Cancun-blockchain_test_from_state_test-op_MOD-mod_bits_127	MOD	127
...fork_Cancun-blockchain_test_from_state_test-op_MOD-mod_bits_63	MOD	63
...fork_Cancun-blockchain_test_from_state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Cancun-blockchain_test_from_state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Cancun-blockchain_test_from_state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Cancun-blockchain_test_from_state_test-op_SMOD-mod_bits_63	SMOD	63
...fork_Prague-state_test-op_MOD-mod_bits_255	MOD	255
...fork_Prague-state_test-op_MOD-mod_bits_191	MOD	191
...fork_Prague-state_test-op_MOD-mod_bits_127	MOD	127
...fork_Prague-state_test-op_MOD-mod_bits_63	MOD	63
...fork_Prague-state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Prague-state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Prague-state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Prague-state_test-op_SMOD-mod_bits_63	SMOD	63
...fork_Prague-blockchain_test_from_state_test-op_MOD-mod_bits_255	MOD	255
...fork_Prague-blockchain_test_from_state_test-op_MOD-mod_bits_191	MOD	191
...fork_Prague-blockchain_test_from_state_test-op_MOD-mod_bits_127	MOD	127
...fork_Prague-blockchain_test_from_state_test-op_MOD-mod_bits_63	MOD	63
...fork_Prague-blockchain_test_from_state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Prague-blockchain_test_from_state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Prague-blockchain_test_from_state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Prague-blockchain_test_from_state_test-op_SMOD-mod_bits_63	SMOD	63
...fork_Osaka-state_test-op_MOD-mod_bits_255	MOD	255
...fork_Osaka-state_test-op_MOD-mod_bits_191	MOD	191
...fork_Osaka-state_test-op_MOD-mod_bits_127	MOD	127
...fork_Osaka-state_test-op_MOD-mod_bits_63	MOD	63
...fork_Osaka-state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Osaka-state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Osaka-state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Osaka-state_test-op_SMOD-mod_bits_63	SMOD	63
...fork_Osaka-blockchain_test_from_state_test-op_MOD-mod_bits_255	MOD	255
...fork_Osaka-blockchain_test_from_state_test-op_MOD-mod_bits_191	MOD	191
...fork_Osaka-blockchain_test_from_state_test-op_MOD-mod_bits_127	MOD	127
...fork_Osaka-blockchain_test_from_state_test-op_MOD-mod_bits_63	MOD	63
...fork_Osaka-blockchain_test_from_state_test-op_SMOD-mod_bits_255	SMOD	255
...fork_Osaka-blockchain_test_from_state_test-op_SMOD-mod_bits_191	SMOD	191
...fork_Osaka-blockchain_test_from_state_test-op_SMOD-mod_bits_127	SMOD	127
...fork_Osaka-blockchain_test_from_state_test-op_SMOD-mod_bits_63	SMOD	63