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 evm.codes (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:
00 36 CALLDATASIZE [CALLDATASIZE]
01 6000 PUSH1 00 [0x0, CALLDATASIZE]
03 6000 PUSH1 00 [0x0, 0x0, CALLDATASIZE]
05 37 CALLDATACOPY []
06 36 CALLDATASIZE [CALLDATASIZE]
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!