Writing EVM Logic in Opcodes, Deploying Opcode Logic On-Chain

All code for this example is available on GitHub.

QuillHash has a really fun Capture-the-Flag (CTF) series going right now for EVM-based challenges. One called Collatz Puzzle in particular requires some low-level EVM work that I couldn’t find great resources for elsewhere, so am recording those learnings as they apply to the CTF here.

This piece will demonstrate how to write logic in opcodes and how to use Assembly to deploy that logic directly on-chain.

Note: Before we get started, I can’t recommend the site evm.codes enough. It was instrumental in debugging and stepping through opcode-based logic, and I almost certainly would have given up on this challenge without it.

Identifying the Problem to Solve

The success criteria for this CTF reads:

Make a successful call to the callMe function.

The challenge code is below for reference:

contract CollatzPuzzle is ICollatz {
  function collatzIteration(uint256 n) public pure override returns (uint256) {
    if (n % 2 == 0) {
      return n / 2;
    } else {
      return 3 * n + 1;
    }
  }

  function callMe(address addr) external view returns (bool) {
    // check code size
    uint256 size;
    assembly {
      size := extcodesize(addr)
    }
    require(size > 0 && size <= 32, "bad code size!");

    // check results to be matching
    uint p;
    uint q;
    for (uint256 n = 1; n < 200; n++) {
      // local result
      p = n;
      for (uint256 i = 0; i < 5; i++) {
        p = collatzIteration(p);
      }
      // your result
      q = n;
      for (uint256 i = 0; i < 5; i++) {
        q = ICollatz(addr).collatzIteration{gas: 100}(q);
      }
      require(p == q, "result mismatch!");
    }

    return true;
  }
}

So the very first step, before writing any code, is to understand the conditions under which a call to that function would be successful. The requirestatements are your best friend here. There are two of them, suggesting there are two checks that the code must pass during execution.

The first is that the codesize has to be less than 32 bytes (require(size > 0 && size ≤ 32, “bad code size!”);), and the second is that the the values p and q must match (require(p==q, “result mismatch!");).

The first requirement is conceptually straightforward — the code needs to be small.

The second requires some more analysis to understand the action we need to take. Diving deeper into the for loop where p and q get compared, we see that p is calculated using the collatzIteration function, while q is calculated by making a call out to ICollatz(addr).collatzIteration(q) and takes less than 100 gas. Practically, this means that the contract at addr needs to contain logic that will return the same value that collatzIteration would, given the same input.

Note: The experienced Solidity dev might think to use delegatecall to deploy a contract of minimal size that calls more complex logic elsewhere. However, the gas limit of 100 defined in the CollatzPuzzle code makes that approach infeasible, as delegateCall takes 100 gas on its own.

To summarize, at this point we know we have to:

1. Write code that mimics the logic of the function `collatzIteration`,

2. that is 32 bytes or less in size,

3. deployed as a smart contract

Encoding Logic into Opcodes

Right off the bat, we know 32 bytes is too small to deploy with standard Solidity, or even Yul. And so, writing in opcodes is the right tool for the job. Recall the `collatzIteration` functionality: for any even value of _n_, return _n / 2_. For odd values, return _(3 * n) + 1_. We also know that the call will be coming from an external contract, which means there will need to be an element of loading calldata into memory as well.

To summarize, the basic flow looks something like this:

• Load calldata
• Determine if calldata value is even or odd
• If even, divide by 2. If odd, multiply by 3 and add 1
• Return value produced by above logic

After some trial and error, we arrive at one possible solution:

0x6004356002810660105760011c6017565b6003026001015b60005260206000f3 // 32 bytes exactly

The explanations for what each of those opcodes do are in the table below.

The source data for the above table is here.

With this bytestring, we have fulfilled requirements (1) and (2) of mimicking the logic of collatzIteration in 32 bytes or less. The next step is deploying it, making it callable by CollatzPuzzle.

Deploying Bytecode

The next hurdle is deploying the code on-chain. Due to the construction of the EVM, it is not as easy as copy/pasting the raw code into an address, though — more opcodes and Assembly are required to deploy the code we want.

One such solution for doing so is below.

0x6026600c60003960206000f3 // 12 bytes

With accompanying explanations:

The source data for the above table is here.

Putting it together, we just need to load the code into contiguous memory and use the create function to deploy it.

address contractAddress; // used as return value
...
assembly {
    let ptr := mload(0x40)
    mstore(ptr, 0x6026600c60003960206000f36004356002810660105760011c6017565b600302)
    mstore(add(ptr, 0x20), 0x6001015b60005260206000f30000000000000000000000000000000000000000)
    contractAddress := create(0, ptr, 44)
}

The secret sauce in these deployment instructions is the CODECOPY opcode, which copies a portion of the code in the current execution context into memory. Because of the create function, the only thing in the execution context is the code at memory location ptr ~ ptr + 44, or the deployment code + our collatzIteration bytecode.

Essentially we are saying “copy 0x26 (32) bytes of code from the bytestring 0x6026600c60003960206000f36004356002810660105760011c6017565b6003026001015b60005260206000f3, starting at location 0x0c (12)". The opcodes afterwards set up the correct code to be returned, which results in the creation of the smart contract at address contractAddress.

Testing

To test, I deployed assembly above within a function called deployExploiterContract(), which returns the address that contains the bytecode. I passed that in as the argument to collatzPuzzle.callMe(address) and it returned true. Clone the code in the GitHub repository and try for yourself!