Calling resolveClaim() can unexpectedly fail due to non-constant gas cost of delete

[qizhou]

Describe the bug

optimism/packages/contracts-bedrock/src/dispute/FaultDisputeGame.sol

Line 414 in 546fb2c

delete subgames[_claimIndex];

The line delete subgames[_claimIndex]; will delete all subgames given _claimIndex. However, the cost of the delete operation in solidity is non-constant, where each of the items in the array will take about 5000 gas to delete. The following lists the gas cost with the number of items in the array (tested in remix Shanghai):

Items	Execution Gas	Diff
0	2847
1	10702	7855
2	15757	5055
3	20812	5055
4	25867	5055
5	30922	5055
6	35977	5055
7	41032	5055

Given block limit 30e6, creating 6000 subgames of a claim will block the claim from resolving forever.

To Reproduce
The following code can be used to check the non-constant gas cost of delete:

pragma solidity >=0.8.2 <0.9.0;

contract SubgameDelete {
    mapping(uint256 => uint256[]) public subgames;

    function addSubgame(uint256 game, uint256 subgame) public {
        subgames[game].push(subgame);
    }

    function removeGame(uint256 game) public {
        delete subgames[game];
    }

    function gameLen(uint256 game) public view returns (uint256) {
        return subgames[game].length;
    }
}

Expected behavior

The gas cot of resolveClaim() should be O(1).

Use another variable to check if the subgame is solved consistently (e.g., ClaimData.bond == uint128.max) without deleting the array.

Screenshots
If applicable, add screenshots to help explain your problem.

System Specs:

• OS:
• Package Version (or commit hash):

Additional context
Add any other context about the problem here.

[qizhou]

The for-loop in the resolveClaim() may have a similar issue

optimism/packages/contracts-bedrock/src/dispute/FaultDisputeGame.sol

Line 394 in 546fb2c

for (uint256 i = 0; i < challengeIndices.length; ++i) {

(although with bond, such attack will be much more expensive)

[clabby]

Thanks for the issue! Great spot, and glad that people are already taking a look at these contracts. This is a known issue, but was pushed aside for a bit due to the cost-to-grief. We'll likely make some improvements here based on your suggestions to improve readability and make this path more FV friendly 😄

This issue would prevent the game from resolving, locking all bonds up within the game above the subgame that's bricked. However, it would not cause the game to resolve incorrectly - it would effectively be bricked due to all sub-games not being resolved.

The impact of this is low-medium in severity, and the attack is costly for the malicious party:

• If the game proposes a correct output and the game gets bricked, anyone can come along and just create a new output proposal, which costs on average $10-15. The one with the 6k+ subgames on a node won't finalize, but that's no problem - withdrawers could re-prove their withdrawal against a future game's output root. To sustain the DoS, the attacker would need to get 1 claim w/ 6k+ subgames in each dispute game that is active.
• If the game proposes an incorrect output, the game can never finalize anyways since all subgames of the root can't be resolved. There's no incentive for a malicious actor to perform this attack on a game with a malicious root claim.

Bonds are not currently defined in the getRequiredBond function, but early work on them suggests that they will be fairly high to cover the costs of hardware and to maintain a high probability of collateralization between the time of creation and a possible counter. Let's say they're 2 ETH per interaction - not including execution or native transaction costs associated with the creation of the 6,000 subgames, it would cost the attacker $28,092,120 USD to create the 6,000 subgames in that single dispute game alone at today's spot ETH price. The honest actors would still be able to counter and take the bonds of these 6,000 subgames, unless the counters themselves had 6,000 more responses, since credit is accumulated as each subgame is resolved + subgames are resolved bottom-up. This creates a very uneven incentive - since the honest actors will always respond to these spammed sub-games up until the instruction step at the leaves, the attacker would have to continue bricking claims lower and lower, for far more money than the honest challenger had to pay.

[tynes]

@clabby We should ensure there is a section in the specs that includes your reasoning as to why this is safe. It will help to centralize the source of truth for the design in a single place