test_mod_arithmetic()¶

@pytest.mark.repricing(mod_bits=191)
@pytest.mark.parametrize("mod_bits", [255, 191, 127, 63])
@pytest.mark.parametrize("opcode", [Op.ADDMOD, Op.MULMOD])
def test_mod_arithmetic(
    benchmark_test: BenchmarkTestFiller,
    pre: Alloc,
    fork: Fork,
    mod_bits: int,
    opcode: Op,
    gas_benchmark_value: int,
) -> None:
    """
    Benchmark ADDMOD and MULMOD instructions.

    The program consists of code segments evaluating the "op chain":
    mod[0] = calldataload(0)
    mod[1] = (fixed_arg op args[indexes[0]]) % mod[0]
    mod[2] = (fixed_arg op args[indexes[1]]) % mod[1]
    The "args" is a pool of 15 constants pushed to the EVM stack at the program
    start.
    The "fixed_arg" is the 0xFF...FF constant added to the EVM stack by PUSH32
    just before executing the "op".
    The order of accessing the numerators is selected in a way the mod value
    remains in the range as long as possible.
    """
    fixed_arg = 2**256 - 1
    num_args = 15

    max_code_size = fork.max_code_size()

    # 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 op chain. You can look
    # for a longer one by increasing the op_chain_len. This will activate the
    # while loop below.
    op_chain_len = 666
    match opcode, mod_bits:
        case Op.ADDMOD, 255:
            seed = 4
        case Op.ADDMOD, 191:
            seed = 2
        case Op.ADDMOD, 127:
            seed = 2
        case Op.ADDMOD, 63:
            seed = 64
        case Op.MULMOD, 255:
            seed = 5
        case Op.MULMOD, 191:
            seed = 389
        case Op.MULMOD, 127:
            seed = 5
        case Op.MULMOD, 63:
            # For this setup we were not able to find an op-chain longer than
            # 600.
            seed = 4193
            op_chain_len = 600
        case _:
            raise ValueError(f"{mod_bits}-bit {opcode} not supported.")

    while True:
        rng = random.Random(seed)
        args = [rng.randint(2**255, 2**256 - 1) for _ in range(num_args)]
        initial_mod = rng.randint(2 ** (mod_bits - 1), 2**mod_bits - 1)

        # Evaluate the op chain and collect the order of accessing numerators.
        op_fn = operator.add if opcode == Op.ADDMOD else operator.mul
        mod = initial_mod
        indexes: list[int] = []
        while mod >= mod_min and len(indexes) < op_chain_len:
            results = [op_fn(a, fixed_arg) % mod for a in args]
            # 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 op chains.
        assert len(indexes) == op_chain_len
        if len(indexes) == op_chain_len:
            break
        seed += 1
        print(f"{seed=}")

    code_constant_pool = sum((Op.PUSH32[n] for n in args), Bytecode())
    code_segment = (
        Op.CALLDATALOAD(0)
        + sum(
            make_dup(len(args) - i) + Op.PUSH32[fixed_arg] + opcode
            for i in indexes
        )
        + Op.POP
    )

    code_prefix = code_constant_pool + Op.JUMPDEST
    code_suffix = Op.JUMP(len(code_constant_pool))
    overhead = len(code_prefix) + len(code_suffix)
    num_segments = (max_code_size - overhead) // len(code_segment)
    code = code_prefix + code_segment * num_segments + code_suffix
    assert len(code) <= max_code_size

    tx = Transaction(
        to=pre.deploy_contract(code=code),
        data=initial_mod.to_bytes(32, byteorder="big"),
        gas_limit=gas_benchmark_value,
        sender=pre.fund_eoa(),
    )

    benchmark_test(
        tx=tx,
    )