test_worst_mod()

Documentation for tests/benchmark/test_worst_compute.py::test_worst_mod@e9958ed2.

Generate fixtures for these test cases for Osaka with:

fill -v tests/benchmark/test_worst_compute.py::test_worst_mod -m benchmark

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/benchmark/test_worst_compute.py

@pytest.mark.parametrize("mod_bits", [255, 191, 127, 63])
@pytest.mark.parametrize("op", [Op.MOD, Op.SMOD])
def test_worst_mod(
    benchmark_test: BenchmarkTestFiller,
    mod_bits: int,
    op: Op,
) -> None:
    """
    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.
    """
    # 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:
            # Compute results for each numerator.
            results = [n % mod for n in numerators]
            # And pick the best one.
            i = max(range(len(results)), key=results.__getitem__)
            mod = results[i]
            indexes.append(i)

        # Disable if you want to find longer MOD chains.
        assert len(indexes) > numerators_min_len
        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.
    setup = sum((Op.PUSH32[n] for n in numerators), Bytecode())
    attack_block = (
        Op.CALLDATALOAD(0) + sum(make_dup(len(numerators) - i) + op for i in indexes) + Op.POP
    )

    input_value = initial_mod if not should_negate else neg(initial_mod)
    benchmark_test(
        code_generator=JumpLoopGenerator(
            setup=setup,
            attack_block=attack_block,
            tx_kwargs={"data": input_value.to_bytes(32, byteorder="big")},
        ),
    )

Parametrized Test Cases

This test case is only parametrized by fork.

Fork All Forks Prague Osaka

Fixture Type All Fixture Types blockchain_test

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