Inefficient Loop in resolveMultiCategoricalMarket

[hats-bug-reporter[bot]]

Github username: -- Twitter username: -- Submission hash (on-chain): 0x77ee24350a655413bf98d9ea3159cc5e0dd986056e3ebc395afa590f8bb38c40 Severity: low

Description:

Details

The RealityProxy contract resolves prediction markets. The resolveMultiCategoricalMarket function handles the resolution of multi-categorical markets, where the outcome can be a combination of multiple choices from a list of options.

The function uses a loop to check if all the payouts in the outcome array are zero. This loop iterates through all numOutcomes, even if a non-zero payout is found early in the loop. This is inefficient because it continues iterating unnecessarily after finding a non-zero payout.

Code Snippet

// ... inside resolveMultiCategoricalMarket ...

bool allZeroes = true;

for (uint256 i = 0; i < numOutcomes; i++) {
    payouts[i] = (answer >> i) & 1;
    allZeroes = allZeroes && payouts[i] == 0; // Inefficient check
}

if (allZeroes) {
    // invalid result.
    payouts[numOutcomes] = 1;
}

Impact

This inefficient loop can increase gas costs, especially for markets with a large number of outcomes. While the impact might be negligible for small markets, it can become significant for markets with many outcomes or when resolving a large number of markets in a batch.

Scenario

• A multi-categorical market is created with 10 outcomes.
• The answer from Realitio indicates that only the first outcome is correct.
• The loop in resolveMultiCategoricalMarket iterates through all 10 outcomes to check for zeroes, even though it could stop after the first iteration since payouts[0] would be 1.
• This unnecessary iteration wastes gas and increases the overall cost of resolving the market.

Fix

Optimize the loop by adding a break statement to exit the loop as soon as a non-zero payout is found:

// ... inside resolveMultiCategoricalMarket ...

bool allZeroes = true;

for (uint256 i = 0; i < numOutcomes; i++) {
    payouts[i] = (answer >> i) & 1;
    if (payouts[i] != 0) {
        allZeroes = false;
        break; // Exit the loop if a non-zero payout is found
    }
}

if (allZeroes) {
    // invalid result.
    payouts[numOutcomes] = 1;
}

Test

it("should terminate the loop early if a non-zero payout is found", async function () {
    // ... (test setup from your existing resolveMultiCategoricalMarket test) ...

    // Submit an answer where the first outcome is correct (non-zero payout)
    const answer = 1; 
    await realitio.submitAnswer(
        (await market.questionsIds())[0],
        ethers.toBeHex(BigInt(answer), 32),
        0,
        { value: ethers.parseEther(MIN_BOND) }
    );

    // ... (rest of the test logic) ...

    // Check that the payouts array has 1 at the first index and 0 for the rest
    const expectedPayouts = Array(multiCategoricalMarketParams.outcomes.length + 1).fill(0);
    expectedPayouts[0] = 1; // First outcome is correct
    expect(eventPayouts.map(Number)).to.deep.equal(expectedPayouts); 
});

This test submits an answer where the first outcome is correct. The optimized loop should terminate after the first iteration, and the resulting payouts array should reflect this. While not a direct measure of gas savings, it demonstrates the improved loop logic.

[clesaege]

First, are excluded:

• Gas optimization.

Second, the loop does not just check that all is 0, its main job is to assign the payouts. Moreover it's quite efficient, as due to short-circuiting rules, if allZeroes is false, payouts[i] == 0 will not be evaluated.