Why does this Cairo program put powers of 2 in the memory?

Here are some leading questions that can help you reach the answer. Answers to the questions after a break:

1. Where does the jmp rel -1 instruction jump to?
2. What does the target instruction do? What happens after it?
3. How did this instruction end up in the program section of the memory?

1. jmp rel -1 is encoded in the memory at addresses 5-6. When it is executed, we have pc = 5, thus after the jump we will execute the instruction at pc = 4, which is 0x48307fff7fff8000.
2. This bytecode encodes the instruction [ap] = [ap - 1] + [ap - 1]; ap++ (to check, you can manually decode the flags and offsets [Edit: see below], or simply write a cairo program with this instruction and see what it compiles to). After it is executed, pc is increased by 1, so we again execute jmp rel -1, and so on in an infinite loop. It should be clear why this fills the memory with powers of 2 (the first 2, at address 10, was written by the [fp + 1] = 2; ap++ instruction).
3. The instruction [fp] = 5201798304953761792; ap++ has an immediate argument (the right hand side, 5201798304953761792). Instructions with immediate arguments are encoded as two field elements in the memory, the first encoding the general instruction (e.g. [fp] = imm; ap++), and the second being the immediate value itself. This immediate value is thus written in address 4, and indeed 5201798304953761792 is the same as 0x48307fff7fff8000. Similarly, the 2 at address 2 is the immediate argument of the instruction [fp + 1] = 2, and the -1 at address 6 is the immediate of jmp rel -1.

To summarize, this strange behavior is due to the relative jump moving to an address of an immediate value and parsing it as a standalone instruction. Normally this wouldn't occur, since pc is incremented by 2 after executing an instruction with an immediate value, and by 1 when executing an instruction without one, so it always continues to the next compiled instruction. The unlabeled jump was necessary here to reach this unexpected program counter.

How can one manually decode the flags and offsets of 0x48307fff7fff8000? Consulting the Cairo whitepaper (mostly pages 50-59), we see that the lower three 16-bit words encode offsets offdst = 0, offop0 = offop1 = -1 (the values 0x8000, 0x7fff, 0x7fff are offset by 215, or alternatively can be considered as signed integers, as detailed on page 51). The flag word is 0x4830, which has 4 flags set to 1 and the rest are 0: the set flags, from least to most, are f4, f5, f11 and f14, which correspond to the flags OP1_AP, RES_ADD, AP_ADD1 and OPCODE_ASSERT_EQ (according to page 58). Let us explore the meaning of these flags (derived from the constraints listed in pages 58-59):

• The OP1_AP flag means operand 1 is taken relative to ap, with offset offop1, i.e. op1 = [ap - 1]. Operand 0 and dst are also relative to ap by default (when the relevant flags are not set), and including the above offsets we see that op0 = [ap - 1], dst = [ap].
• The RES_ADD flag means the operation between op0 and op1 is addition, i.e. the constraint res = [ap - 1] + [ap - 1] is enforced.
• The OPCODE_ASSERT_EQ flag means this is as equality assertion command, which means res will be equaled to dst by enforcing dst - res = 0, which we now see is equivalent to [ap] = [ap - 1] + [ap - 1].
• Finally, the AP_ADD1 flag simply means ap is advanced by 1, which corresponds to the ap++ part of the command.

Taken all together, we get the command [ap] = [ap - 1] + [ap - 1]; ap++ as claimed.

ㅤ This answer was originally posted on Stack Overflow