# Curta CTF Puzzle #6: Uncertainty Principle

## Motivation
The objective of the puzzle was to require a methodology of study rather than an intricated understanding of the game, the program is rather easy to understand, but the solution may require competitors to approach it in a programatic way to capture the flag.

Since many contestors were relying on intense fuzzing or symbolic testing, I wanted to create a puzzle that would make disecting the puzzle into it's parts implausible, since any change they made to the core logic, would be modifying the `gasleft()` method. Hence the name of the puzzle **Uncertainty Principle**, and the question that arises:
> **How do we measure something, that the sole act of measurement changes its value?**

## The puzzle

contract EventHorizon is IPuzzle {
    uint256 constant PLANK_CONSTANT = 0x111;
    uint256 constant PLANK_LENGTH = 0xF;
    uint256 constant PHISICAL_SPHERE = type(uint32).max;

    function generate(address _seed) external view returns (uint256) {
        return _gammaFn(uint256(uint160(_seed))) | PLANK_CONSTANT;
    }

    function verify(uint256 _start, uint256 _solution) external view returns (bool) {
        uint256 _axis;
        uint256 _momentum;
        uint256 _position;

        while (_start & PHISICAL_SPHERE > 0) {
            _position = _axis++ * 4;
            _momentum = _gammaFn(_solution) & PLANK_LENGTH << _position;
            for (uint256 _i; _i < _momentum >> _position; _i++) {
                continue;
            }
            _start -= _momentum;
        }

        return true;
    }

    function _gammaFn(uint256 _xyz) internal view returns (uint256) {
        return uint256(keccak256(abi.encodePacked(_xyz, gasleft())));
    }
}

The puzzle logic can be then reduced to escaping the following loop:

while (_start & 0xFFFFFFFF > 0) {
    _position = _axis++ * 4;
    _momentum = keccak256(_solution, gasleft()) & 0xF << _position;
    for (uint256 _i; _i < _momentum >> _position; _i++) {continue}
    _start -= _momentum;
}

Let's first analyze it line by line to understand the challenge:
1) `while(_start & 0xFFFFFFFF > 0){`
The objective of the puzzle is to make the last 8 bytes of `start` be 0, else you'd fall into an infinite loop.
2) `_position = _axis++ * 4;`
The `position` increases by 4 each time, pointing at each of the bytes of `start` from right to left.
3) `_momentum = keccak256(_solution, gasleft()) & 0xF << _position;`
The `momentum` can have a value of 1 byte in 1 position at each time. While `position` increases, `momentum` can have the following values:

0x...0000000X // being X any byte value (from 0x0 to 0xF)
0x...000000X0
0x...00000X00
...

4) `for (uint256 _i; _i < _momentum >> _position; _i++) {continue}`
Depending on the `X` value of `momentum`, enter a loop `X` amount of times (consuming different amounts of gas).
5) `_start -= _momentum`
Substract from `start` the `X` value of the momentum at the position.

**TL/DR**: The objective of the puzzle, is to provide a `solution` such that at each iteration, the keccak of `(solution, gasleft())` will provide a `momentum` such that the last 8 bytes of `start` get substracted to 0.

**Challenge**: `solution` then acts as a key mechanism, that has to align every pin at the same time to make it work, with the difficulty that we cannot know the shape of the following pin, since we cannot know `gasleft()` until we reached it. And also, if one of the pins is not perfectly aligned, instead of reverting (ideal for fuzzing), the transaction will enter a neverending loop called "**the blackhole**". And given that the solution depends on the gas, there are 2 values to be searched by the users, as a both solution and gaslimit need to be properly set.

## Solving it
As stated before, understanding the puzzle is not the hard part, but creating a methodology to solve it without touching it, can become challenging. I'm going to propose a few options on how to approach it, in order to avoid some of the most painful difficulties.

> **To navigate through the event horizon, one must to either have no mass, or to master the gamma function**

### The Theoretical Physicist approach
Given a starting point, lets say `0x......123456789abdcef`, one can know in advance that it's gonna need to enter the loops with the following values:
1. First byte (right to left), perform `15` loops (because of `line (4)` as it has to null the last byte of `start`: `0xF`)
2. Second byte, `14 (0xE)` loops
3. ...
8. Eight byte, `8` loops

Theoretically, since the EVM is very weird but also very deterministic, one could follow each `PUSH, DUP, SWAP, ...` and pre-calculate all of the `gasleft` at each of the steps, and go look for a `solution` that satisfies the following:
1. `keccak(solution, gasleft(1)) & 0x0000000F = 0xF`
2. `keccak(solution, gasleft(2)) & 0x000000F0 = 0xE`
3. `keccak(solution, gasleft(3)) & 0x00000F00 = 0xD`
4. `...`

Since `gasleft(2) = gasleft(1) + 15 loops`, and `gasleft(3) = gasleft(2) + 14 loops`, the `solution` requirement could theoretically be precalculated all at the same time. But when you look deep inside, the EVM is a very misterious machine, and performing such calculations can cause multiple headaches, tho the possible approach is interesting to point out.

### The Experimental Physicist approach
One thing experimental physicists know for sure, is that their experiment doesn't represent the real world, but a controlled representation of the real world. So in a way, modifying the contract to emit the `gasleft()`, can bring a lot of data about how the actual contract behaves.

function _gammaFn(uint256 _xyz) internal view returns (uint256) {
    uint256 _gasLeft = gasleft();
    console.log(_gasLeft);
    return uint256(keccak256(abi.encodePacked(_xyz, _gasLeft)));
}

Finding the solution to the above puzzle is much easier than the previous one, and forces the user to understand the implications of such challenge. While solving this one, the user may encounter a few insights that may become helpful to solve the actual problem.

The methodology to solve this puzzle can be later replicated by reading the `gasleft` from the memory stack instead of the `console.log`. In the end, the user will have to iteratively do:
- measure `gasleft(1)`
- find solution so that `keccak(solution, gasleft(1)) = 0x_______F`
- measure `gasleft(2)`
- find solution so that `(1) & keccak(solution, gasleft(2)) = 0x______E_`
- measure `gasleft(3)`
- find solution so that `(1) & (2) & keccak(solution, gasleft(3)) = 0x_____D__`
- `...`

When the user have created the test scenario and tools to calculate the solutions for the modified puzzle, then calculating it from the original one is only 1 debugger and 8 iterative solution calculations away. With debugging tools such as https://remix.ethereum.org/, one can access the memory slot to know what was `gasleft()` returning at each step, and redo the `solution` calculation.

### The Solidity Engineer approach
Something pleasing to notice is that the `start` point is generated via the following formula:

function generate(address _userAddress) external view returns (uint256) {
    return keccak256(_userAddress, gasleft()) | 0x111;
}

Where the `0x111` was clearly put there to avoid a lucky address to generate a starting point with 8 trailing 0s, avoiding the whole loop in the first entrance (as massless objects aren't dragged by the blackhole). But a smart user can know that by tweaking the gasleft (number between ~100k and 30M), he can score a `start` point such that some of the **left bytes of the 8-trailing-bytes** are 0, finalizing the loop earlier (for ex. `start = 0xabcdef12345|00000111` would only require 3 `0x1` loops).

One can calculate that there are high chances of a precise `gasleft` value providing 4 (or up to 5 if lucky) leading `0s`. So the first challenge would be to arrive to the `start` generation point with that precise `gasleft`.

- calculate `gasLeft` for lucky address
- simulate tx with `gasLimit = gasLeft`
- measure from the memory slot the arriving `gasleft`
- calculate `gasDelta = desiredGasLeft - gasLeft`
- re-simulate tx with `gasLimit = desiredGasLeft + gasDelta`
> **Notice**: because of EIP-150, and Curta contract calling the generate method, the actual gas sent is 63/64 of the gas that the execution has at the time of `puzzle.generate(msg.sender)`, so tweaking the `gasLimit` may require some calculations or iterations
- repeat until `desiredGasLeft = gasLeft`

Having set one of the unknown parameters (`initialGas`), one needs to define the other unknown (`solution`) such that the other 4 bytes are substracted. So one can know that there is a 1/65.536 possibility that a random seed would be correct. Given that the gas sent is <30M, and that the possibilities are relatively high, fuzzing becomes a good enough tool to approaching this problem.

### Shadowy Super Coder approach
Is it possible to solve all within Foundry fuzzing? Without going into the deepness of the debugger? Let's give it a try:

One of the painful challenges of the puzzle is the "**spooky action at distance**" that both the `generate` and `verify` methods have. One needs to coordinate the execution at the same time, since changing the `generate` has an effect on the posterior `verify` call.

Fuzzing is a great tool, but is not the best to do in a E2E test, where the RPC is usually having to process the whole tx, thousands of times until reaching the desired outcome. And we want to maintain everything in a controlled scenario. So maybe the best thing to do is to fork Curta contract altogether, using `vm.etch` to even have it on the exact contract address, to avoid changes in gas because of the leading `0s` of its address.

If one decides to fork Curta, one can also modify:

puzzle.verify(puzzle.generate(msg.sender), _solution)

Into:

console.log(puzzle.generate(msg.sender))

> **Notice**: the `puzzle.verify` part is posterior to `puzzle.generate` so it shouldn't have any effect on the gas consumption up to that point.

And call `Curta.solve{gaslimit: x}({puzzle:6, solution:0xffff...})` to fuzz `x` the first of the unknowns of the puzzle, requiring the return to have `0s` on the left side of the last 8 bytes. Then, rollbacking Curta to the original, one can verify that the `start` point should be the same for the `gaslimit` sent (as no previous opcodes were modified), and can decide to fuzz the `solution`, leaving to the fuzzer test all the complexity of "measuring gasleft" at every point.

This approach might bring some implications to be considered:
- since the failing outcome is an infinite loop, for fuzzing, perhaps is more convenient to have a 200k gas limit and need to perform 4 iterations (1/65k probability of scoring), than have a 30m gas limit and need to perform 3 iterations (1/4k probability of scoring)
- because of the amount of the leading `0s` of the `solution` modifies the gas spenditure, one can request `solution >= 1<<255`, to maintain the spenditure because of `solution` fixed (**Notice**, there's a reason why this particular solver decided to fuzz his solution with preceding bytes, instead of fuzzing from scratch).

### Conclusions
Either of the mentioned methodologies can guide the player through the blackhole, without getting stuck at the event horizon. Since Curta is a race to capture the flag, there's no ideal roadmap to follow, but the one the user feels more comfortable with.

### Comments
I had a great time thinking about this game, I wanted to create something which solution was Turing complete, and that would force y'all to approach it in a scientific mindset. To be honest I was planning to raise it to `uint42`, but figured out that 8 bytes would be challenging enough to achieve such goal, without the need of a lot of processing hours to get the right seed. I do hope you had a good time trying to coordinate the `generate` and `verify` entanglement, I was really surpised about the speed of the answers it got, and got really sorry for that one guy who sent 5M gaslimit to get stuck in the event horizon, twice.