Cairo VM
Cairo VM 是一个非常精简的虚拟机模型，它没有类似于x86的通用寄存器（%eax, %ebx 等等），并且它仅仅只支持有限域Fp上加法和乘法 (p = 0x800000000000011000000000000000000000000000000000000000000000001)， 这篇文档提到了stark-curve 的参数设置。
Q1: 可能大家会好奇，仅仅只有加法、乘法，怎么就能够实现各种算术函数呢?
- 减法：
a - b = a + (b * (-1)) - 布尔约束：
a*(1-a) = 0 - 布尔运算:
a & b = a*b - 比特分解（bit-decompose）: 比如得到一个
u32的32个比特，a = \sum_{i=0}^{31} 2^i * a_i；当然有更好的方法来实现这个功能，如使用builtin()。
Cairo 的加法指令和乘法指令的操作数都在内存上，Cairo 的内存比较特殊，是只读的（immutable）。这和大部分的虚拟机都不一样，比如：
- EVM 的操作数通常是放在 stack 上，而 stack 是可以修改的；
- x86 架构的操作数是在通用寄存器中。
大家可能会好奇，那么如何实现赋值（assignment）呢？
需要为赋值语句的左侧的变量 lhs 分配一个新的内存，然后使用assert_eq 建立这个新变量 lhs 与旧变量 rhs 之间的相等关系。
我们举个例子来说明，比如：
# equivalent to assert_eq(b, 3)
b = 3
# equivalent to assert_eq(a, b+1)
a = b+1
# will alloc a new memory space for `a`(we call it `a2`) on the left side
# equivalent to assert_eq(a2, a+15)
a = a + 15
Cairo VM Instruction Set
Cairo VM 的指令集是
-
assert_eq：实现算术表达式；
一个复杂的算术表达式会对应多条 VM 指令；例如，
y = x^3 + 23*x^2 + 45*x + 67 # the above compound expression is equivalent to 5 bytecodes, they cost 5 memory slots # 1*x+23 [ap] = [ap-1] + 23; ap++ # (1*x+23)*x [ap] = [ap-1]*[ap-2]; ap++ # (x+23)*x + 45 [ap] = [ap-1] + 45; ap++ # ((x+23)*x + 45)*x [ap] = [ap-1]*[ap-4]; ap++ # ((x+23)*x + 45)*x + 67 [ap] = [ap-1] + 67; ap++ -
call/ret: 函数调用
-
jmp/jmpi: 条件跳转，用于支持控制流
在本节，我会以 call/ret 为例，讲解一下Cairo VM指令集如何支持 函数调用 这一实用功能。
-
假设，函数A 的栈帧指针（stack frame pointer）为
fp； -
假设，函数B 在执行到
call B之前的 allocation pointer 为ap； -
函数 B 的栈帧指针为
new_fp = ap + 2； -
在函数 A 中调用函数 B 之前，需要先把入参放到
[new_fp - 3], [new_fp - 4], ...等区域中； -
将函数 A 的stack frame pointer 的值保存到
[new_fp-2] -
将函数 A 中在
call指令之后的那条指令的地址保存到[new_fp-1] -
当函数 B 结束执行之后，就可以通过读取
[new_fp - 1]然后更新pc，读取[new_fp-2来更新fp，回到函数 A 的执行。
以下图所示的函数调用示例，函数 f 调用了函数 g，函数g 调用了两次 h。需要注意的是，调用两次 h，产生的栈帧并没有重合（通常在x86架构中，它们的栈帧是要重合的）。
上述示例调用的栈帧如下图所示。
更多技术细节，大家可以看一下 Cairo VM 的白皮书[1]。
Cairo 语言
从以上对 Cairo VM 的介绍，大家不难发现，Cairo 汇编代码其实比较简陋，我们开发者不可能手写Cairo assembly code。所以，我们在开发真实应用时，使用的是 cairo 语言，这个语言的词法形式与python类似。