More EVM Puzzles - Part 1

May 24, 2022 by patrickd

Dalton Sweeney (opens in a new tab) has recently published his own collection of EVM puzzles: "10 more EVM puzzles" (opens in a new tab)! Promising to be even more challenging than the ones of Franco Victorio (opens in a new tab)'s original collection (opens in a new tab). Since we've solved all the other one's on this blog already and they've been good fun, let's do these too!

Note that it's probably best to read my previous blog posts first, or that you've already solved the original version yourself, since I'll not explain all of the opcodes that were already discussed there in detail again.

Puzzle #1

00      36      CALLDATASIZE
01      34      CALLVALUE
02      0A      EXP
03      56      JUMP
04      FE      INVALID
05      FE      INVALID
06      FE      INVALID
... (all INVALID opcodes) ...
3D      FE      INVALID
3E      FE      INVALID
3F      FE      INVALID
40      5B      JUMPDEST
41      58      PC
42      36      CALLDATASIZE
43      01      ADD
44      56      JUMP
45      FE      INVALID
46      FE      INVALID
47      5B      JUMPDEST
48      00      STOP

? Enter the value to send:
? Enter the calldata:

The first puzzle is already quite complex, but as usual, we know that the goal is to ensure that the transaction doesn't revert, meaning it needs to reach the STOP opcode. And since there are each two JUMP and JUMPDEST opcodes, we most likely need to make sure to send a transaction that will ensure that both destinations are successfully jumped to.

A JUMP consumes one item from the stack: The offset it should jump to, at which location needs to be a JUMPDEST opcode.

The first 4 lines can be rewritten to the following pseudocode: jumpTo(CALLVALUE ** CALLDATASIZE) - and first thing to wonder about is: Can we jump directly to the last JUMPDEST skipping half of the challenge? Well, its offset is at 0x47 which is 71 in decimal, so sending a wei value of 71 and 1 byte as calldata should work? (because 71**1=71)

? Enter the value to send: 71
? Enter the calldata: 0x01

Puzzle solved!

Indeed! That worked, but it's kind of cheating so let's take a look at how this was probably intended to be solved and first jump to the JUMPDEST at 0x40 which is 64 - that means we can actually send any power of 2 that results in 64: 2*6, 4*3, 8**2

After jumping there, the Program Counter's current value is pushed on the stack with the PC opcode. The handy (opens in a new tab) website tells us that this is "the value of the program counter prior to the increment corresponding to this instruction". So the Program Counter is basically a simple integer offset within the EVM that always keeps increasing by 1 while working through the contract's bytecode, except when it hits some kind of jump that overwrites the offset to point to a different location. We'll get the PC opcodes own address here, which is 0x41.

This is then added to CALLDATASIZE and this sum becomes the offset the following JUMP will take us to. So to get to the final JUMPDEST at 0x47 we need to add 6 to the PC opcode's location at 0x41. That means we need a CALLDATASIZE of 6 and we already know that we can send 2**6 to keep the first jump working.

? Enter the value to send: 2
? Enter the calldata: 0x010203040506

Puzzle solved!

It appears we have now found the intended solution!

Puzzle #2

00      36        CALLDATASIZE
01      6000      PUSH1 00
03      6000      PUSH1 00
05      37        CALLDATACOPY
06      36        CALLDATASIZE
07      6000      PUSH1 00
09      6000      PUSH1 00
0B      F0        CREATE
0C      6000      PUSH1 00
0E      80        DUP1
0F      80        DUP1
10      80        DUP1
11      80        DUP1
12      94        SWAP5
13      5A        GAS
14      F1        CALL
15      3D        RETURNDATASIZE
16      600A      PUSH1 0A
18      14        EQ
19      601F      PUSH1 1F
1B      57        JUMPI
1C      FE        INVALID
1D      FE        INVALID
1E      FE        INVALID
1F      5B        JUMPDEST
20      00        STOP

? Enter the calldata:

The CREATE opcode, previously reserved for the most challenging puzzles, is back and that already in the second one! This makes the puzzle a whole lot more intimidating, but the goal hasn't changed: Make a jump to the one and final JUMPDEST at offset 0x1F.

This offset is already pushed onto the stack as target before the JUMPI, so what we have to do is making sure that the jump condition is met and the second item on the stack is a non-zero value. For that to be the case RETURNDATASIZE needs to be equal to 0x0A. That means the size of the output data resulting from the previous CALL opcode should be 10 bytes long.

To understand what's happening with the CREATE and CALL opcodes, it's best to look at how the stack builds up and what each item will end up being used for:

01      6000      PUSH1 00       [0x0, CALLDATASIZE]
03      6000      PUSH1 00       [0x0, 0x0, CALLDATASIZE]
05      37        CALLDATACOPY   []
07      6000      PUSH1 00       [0x0, CALLDATASIZE]
09      6000      PUSH1 00       [0x0, 0x0, CALLDATASIZE]
0B      F0        CREATE         [ADDRESS]

First of all CALLDATACOPY copies calldata to memory at offset 0x0 from the calldata starting at offset 0x0. The size of this copy operation is CALLDATASIZE, meaning the entirety of the calldata we send is copied to memory.

After that, CREATE is executed with an ether value of zero (0x0) to send to the new contract, and to use the entirety of the calldata that we have just copied to memory at offset 0x0 as construction bytecode.

So whatever we send as calldata will be executed as construction bytecode. And whatever the result of that is will be deployed as a smart contract. And finally we'll have the address of it as the top item on our stack.

0C      6000      PUSH1 00       [0x0, ADDRESS]
0E      80        DUP1           [0x0, 0x0, ADDRESS]
0F      80        DUP1           [0x0, 0x0, 0x0, ADDRESS]
10      80        DUP1           [0x0, 0x0, 0x0, 0x0, ADDRESS]
11      80        DUP1           [0x0, 0x0, 0x0, 0x0, 0x0, ADDRESS]
12      94        SWAP5          [ADDRESS, 0x0, 0x0, 0x0, 0x0, 0x0]
13      5A        GAS            [GAS, ADDRESS, 0x0, 0x0, 0x0, 0x0, 0x0]
14      F1        CALL           [SUCCESS]

This contract is then called with all of the gas that is still available at this point. All of the zeros the stack was filled with, tell CALL that there are no arguments to copy from memory (as new calldata for the call to the new contract) and that none of the return data should be copied to memory either. And finally, we'll have either 1 or 0 on the stack, telling us whether the call succeeded.

But this success value isn't actually used. Instead, it gets the size of the data that was returned by the previous call with RETURNDATASIZE (data which is buffered somewhere for us within the EVM).

So in summary: We need to send bytecode as calldata, that'll return a contract, that'll return 10 bytes of data when called.

First: We need to build a runtime bytecode that returns 10 bytes.

00      600A      PUSH1 0A        [0x0A]
02      6000      PUSH1 00        [0x00, 0x0A] (offset, size)
04      F3        RETURN          []

We don't actually have to write anything to memory first in order to return it. Since the memory is already zero-initialized we can just return 10 zeros from it.

Runtime bytecode: 0x600A6000F3

Second: We need to build a construction bytecode that returns our runtime bytecode.

00      64600A6000F3      PUSH5 600A6000F3        [0x600A6000F3]
06      6000              PUSH1 00                [0x0, 0x600A6000F3] (offset, value)
08      52                MSTORE                  []
00      600A              PUSH1 0A                [0x0A]
02      601B              PUSH1 1B                [0x1B, 0x0A] (offset, size)
04      F3                RETURN                  []

Here we're writing the bytecode to memory and then we return it. You might wonder why the starting offset of the return data begins at 0x1B although we stored the runtime bytecode at 0x0 - that's because it'll look like this is memory: 0x000000000000000000000000000000000000000000000000000000600A6000F3.

We have to skip the 27 zeros that are at the beginning of the value to reach the bytecode. We could have prevented that using PUSH32 0x600A6000F3000000000000000000000000000000000000000000000000000000, but that'd have significantly increased the construction bytecode's size.

Construction bytecode: 0x64600A6000F3600052600A601BF3

? Enter the calldata: 0x64600A6000F3600052600A601BF3

Puzzle solved!

But that was somewhat boring, right? Wouldn't it be more fun if we only had one bytecode.. bytecode that returns itself and can be used for both construction and runtime.. and is 10 bytes long?

We can actually do that quite easily because with the CODECOPY opcode the bytecode can copy itself:

00      600A      PUSH1 0A        [0x0A]
02      6000      PUSH1 00        [0x00, 0x0A]
04      6000      PUSH1 00        [0x00, 0x00, 0x0A] (destOffset, offset, size)
06      39        CODECOPY        []
07      600A      PUSH1 0A        [0x0A]
09      6000      PUSH1 00        [0x00, 0x0A] (offset, size)
0B      F3        RETURN          []

This is 12 bytes long though, so we have to do some optimizations. A simple one is using duplication opcodes instead of pushing duplicate items onto the stack:

00      600A      PUSH1 0A        [0x0A]
02      80        DUP1            [0x0A, 0x0A]
03      6000      PUSH1 00        [0x00, 0x0A, 0x0A]
05      80        DUP1            [0x00, 0x00, 0x0A, 0x0A] (destOffset, offset, size), size
06      39        CODECOPY        [0x0A]
07      6000      PUSH1 00        [0x00, 0x0A] (offset, size)
09      F3        RETURN          []

The bytecode is now exactly 10 bytes long and able to deploy itself:

? Enter the calldata: 0x600A80600080396000F3

Puzzle solved!

This was a lot of stuff and we're only 2 puzzles in, so let's not overdo it and make it a series instead!