Skip to content

Instantly share code, notes, and snippets.

@ynx0

ynx0/Cairo Notes.md

Last active April 22, 2022 21:54
Show Gist options
  • Save ynx0/5c1cfa27a3a1017007fd789e380caa8e to your computer and use it in GitHub Desktop.
Save ynx0/5c1cfa27a3a1017007fd789e380caa8e to your computer and use it in GitHub Desktop.
Download ZIP
abbreviated notes about cairo. like a "crash course" or smtn
Raw
Cairo Notes.md

Cairo Notes

At first glance, Cairo looks like Python but it is really a vm + an assembly language with a lot of sugar on top. Without internalizing, this your headspace will not be in the right place.

Numbers

  • No "machine-type" numbers, only one number type felt or field element which is in the range of $[0, P]$ , where $P$ is some large prime. All arithmetic is done in a Finite Field of integers mod P. Aka, any addition, subtraction or multiplication operation that results in a value above the max representable number $P$ wraps back around.
  • Notably, there is a weird wraparound for divsion because all operations must be invertible. So in regular computer arith., $7 / 2 = 3 \implies 7 = 2 \cdot 3$, highlighting the loss of precision and non-invertibility. But in cairo 7/2 does some wrap around and becomes some huge number.
  • Also apparently checking for evenness has some pitfalls?

Registers

The Cairo VM has only 3 mutable registers

  • ap (allocation pointer) - points to a yet-unused memory cell.
  • fp (frame pointer) - points to the frame of the current function. The addresses of all the function’s arguments and local variables are relative to fp. When a function starts, it is equal to ap but remains the same throughout the scope of a function
  • pc (program counter) - points to the current instruction.

Memory

  • Cairo VM memory is write-once and immutable
  • Assertion is assignment - There is some weird congruency between assigning a value to a memory cell and asserting a memory cell is equal to a value.
  • There is a requirement in the VM spec that if address 7 is accessed, and address 11 is addressed, then at some point the vm must also access addresses 8, 9, and 10 as well. If you skip regions of memories, the compiler reads in garbage
  • The offset $o$ in [ap + o] must be in $[-2^{15}, 2^{15})$
  • Programs are stored in the same memory as data

Example

  • The expression [ap] = [ap - 1] * [fp]; ap++ is read as the following:
    • [ap - 1] - read the value at the address ap - 1
    • [fp] - read the value at the address fp
    • [ap] = [ap - 1] * [fp]; ap++
      • multiply values [ap - 1] and [fp], call it a
      • assert that the value at address ap, that is, [ap], is equal to a, and then increment ap
  • Importantly, ap is a pointer to the "next" unused cell, so asserting that [ap] is equal to something is treated as writing to the cell at address ap because it is empty.

Segments

  • Relocatable values are basically an "intermediate representation" form of memory addresses that are not absolute, of the form <segment>:<offset>. Segment numbers are arbitrary!
  • From the [docs] (https://cairo-lang.org/docs/how_cairo_works/segments.html#relocatable-values):
    • Segment 0: the program segment. This segment contains the compiled bytecode of the program.
    • Segment 1: the execution segment. This segment contains the values saved in memory during the run of the program. these can also be pointers (and thus also relocatable values)
    • Segment 2: the output builtin segment.

Basic Control Flow

https://www.cairo-lang.org/docs/how_cairo_works/program_counter.html#my-loop-exercise

  • There are 4 types of jumps in Cairo
    • Absolute - such as, jmp abs 17 , which in this case simply sets pc to 17.
    • Relative - jmp rel 10, essentially jmp abs pc + 10 (jmp rel 0 is infinite loop)
    • Label - jmp my_label - jumps to a label, with cairo calculating the offset at compile-time
    • Conditional - jmp <label> if [<expr>] != 0.
      • Basically a jnz that looks nice, and allows for "if statements"
      • <expr> is either ap + offset or fp + offset (offset may be omitted)

Nondeterministic computation

  • All this means is that when you generate a proof-trace/proof (by running the cairo program and submitting it to SHARP), instead of being given a problem and trying to manually compute the solution, you create an "answer" variable and nondeterministically inject the answer and instead simply prove that your answer is the correct answer to the problem.
  • Traditional: problem -> computation -> solution (+ proof of correctness based on verifiable steps)
  • Nondeterministic: assumed solution -> simpler computation -> show/prove that solution satisfies problem
  • The nondeterminism is that when you assume the answer, you break out certain guarantees of the cairo vm
  • Nondeterminism is implemented thru inline python snippets that can interact with various parts of the current vm state
  • General Heuristic for non-determinism: if verifying is cheaper than computing, compute the in the hint and then do an assertion. Always need assertions before returning, otherwise, because a malicious actor can execute anything in the hint and still have a valid cairo trace, he can e.g. claim that sqrt(25) => 6, and because there is no cairo level assert before returning the value, the proof would be valid.
  • Always measure performance gains to confirm. This is a good heuristic in general but comes into play a lot because traditional optimization wisdom doesn't always hold, because the characteristics of VM changes the relative cost of different operations

Quirks

  • The ; ap++ is kinda wack, it's special syntax for assignment only and is not normal python
  • Can't do something like 23 * [ap - 1], you must do [ap - 1] * 23
  • As mentioned in [[#Cairo Notes#Numbers]], division and checking for eveneness can be unintuitive
  • As mentioned in [[#Memory]], it is inefficient to access cells that are spread apart, because the VM is required to access/write to all addresses in between.
    • However, when I tested a toy example it didn't appear to be a problem?? (see memskip.cairo)
  • alloc_locals is kinda magical
    • it allows you to use local x = 15 local variables
    • it also automatically inserts implicit variable rebinding statements so that when you call something that modifies an implicit variable and thus revokes it, it will "reset" it (??) back so that it is no longer considered revoked

References (Guides, Code Examples, etc.)

Misc

  • If you don't have the tracer and you only have the memory print, looking at the fp is a good place to start looking for values that make sense
  • Functions must end in jmp or ret statement (or return I suppose)
  • You may need the --layout=small flag in when running cairo-build for some builtins like the range_check to be available.

Compile and run a program

cairo-compile test.cairo --output test_compiled.json

cairo-run --program=test_compiled.json --print_output \
--print_info --relocate_prints \
--tracer # <-- optional but cool. can step thru code with online debugger
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment