Cairo - 指令

1. 指令结构

Cairo CPU原生支持的word是一个域元素，而这个域是特征值大于。每个指令会占用1到2个word，如果指令后面跟着立即值（[ap] = "12345678"）则该指令占用2个word，并且值存在第二个word里。每个指令的第一个word由以下元素组成：

• [ bit0..15]：目的地址偏移量，代表值 
• [ bit16..31]：op0地址偏移量，代表值
• [ bit32..47]：op1地址偏移量，代表值
• dst reg[ bit48]：目的地址偏移的基寄存器， ap or fp；
• op0 reg[ bit49]：op0地址偏移的基寄存器， ap or fp；

2. 状态转换

状态转换函数代表了一个通用的状态转换单元（由于它包含了所有指令类型的处理逻辑），而一个计算通常会分解成多个连续执行的指令，因此我们需要：

a. 确保指令的内容，以及指令执行前后的状态的有效性（比如满足一定的范围校验，和状态一致性校验）

b. 确保执行的指令是一个有效的指令

2.1 转换逻辑

如果指令执行前后的状态是一致的，那么其状态的更新一定是按照以下逻辑执行：

2.2 指令校验

如图1所示，一个指令由以下元素组成：

注意：我们并没有为指令的15bit flags分别分配15个长度为 N 的virtual column，而是用一个长度为16N的virtual column 来表示，它满足：

3. 指令示例

3.1 断言相等

断言相等指令可以用下述语法表示：

它确保了公式两边是相等的，否则程序的执行将会被返回。

等式左边往往来自或者，右边有一些可能的形式(和可以是fp或ap，∘可以是加法或乘法，imm可以是任何固定的字段元素)：

Note2：除法和减法可以分别表示为具有不同操作数顺序的乘法和加法。

assert指令可以被认为是一条赋值指令，其中一边是已知的，另一边是未知的。例如[ap]=4可以被认为是断言的[ap]值为4，或者根据上下文将[ap]赋值为4。

图4给出了断言相等指令的一些示例，以及每个指令对应的标志值：

解释 指令 [fp + 1] = 5：

◦ 为assert指令 => opcode = 4 

◦ next_ap = ap => ap_update = 00 = 0 

◦ next_pc = pc + instruction_size => pc_update = 000 = 0 

◦ op0和op1没有add or mul => res_logic(res) = 00 = 0 

◦ 存在立即数 => op1_src(op1) = 001 = 1 

◦ 立即数地址指令地址相邻 => off_op1 = 1 

◦ 等式左边[fp + 1] => dst_reg(dst) = 1 

◦ 等式左边[fp + 1] => off_dst = 1 

◦ op0_reg/ off_op0 => inital value(1/-1) //因为这个指令用不到这些flags，所以填充默认值

3.2 条件和非条件跳转 

jmp 指令允许更改程序计数器 pc 的值。 

Cairo支持相对跳转（其操作数代表相对当前pc的偏移）和绝对跳转 - 分别用关键字rel和abs表示；jmp指令或许是有条件的，比如当某个内存单元的值不为0时，触发jmp指令。

指令的语法如下所示： 

# Unconditional jumps. 

jmp abs < address >

jmp rel < offset >

# Conditional jumps. 

jmp rel < offset > if < op >! 

图5给出了 jmp 指令的一些示例，以及每个指令对应的标志值：

解释 指令 jmp rel [ap +1] + [fp - 7]： 

◦ 为jmp指令 => opcode = 0

◦ next_ap = ap => ap_update = b00 = 0 

◦ next_pc = pc + res=> pc_update = b010 = 2 

◦ res = op0 + op1 => res_logic(res) = b01 = 1

◦ op1: [fp - 7] => op1_src(op1) = b010 = 2 

◦ op1: [fp - 7] => off_op1 = -7 

◦ op0: [ap + 1] => op0_src(op0) = 0 

◦ op0: [ap + 1] => off_op0 = 1 

◦ dst_reg/ off_dst => inital value(1/-1) ///因为这个指令用不到这些flags，所以填充默认值

3.3 call 和 ret 

call和ret指令允许实现函数堆栈。 call指令更新程序计数器(pc)和帧指针(fp)寄存器。程序计数器的更新类似于 jmp 指令。之前 fp 的值被写入[ap] ，以允许 ret 指令将 fp 的值重置为调用之前的值；类似地，返回的pc (调用指令后面指令的地址)被写到 [ap+1] ，以允许 ret 指令跳回并继续执行调用指令后面的代码的执行。由于写入了两个存储单元，ap 向前进了2，fp 被设置为新的 ap。

指令的语法如下：

call abs < address >

call rel  < offset >

ret

图6给出了 call 和 ret 指令的一些示例，以及每个指令对应的标志值：

解释 指令 call abs [fp + 4]：

◦ 为call指令 => opcode = 0 

◦ next_ap = ap => ap_update = b00 = 0 

◦ next_pc = res => pc_update = b001 = 1 

◦ res = op1 => res_logic(res) = b00 = 0 

◦ op1: [fp + 4] => op1_src(op1) = b010 = 2 

◦ op1: [fp + 4] => off_op1 = 4 

◦ op0_reg/ off_op0 => inital value(0/1) ///因为这个指令用不到这些flags，所以填充默认值 

◦ dst_reg/ off_dst => inital value(0/0) ///因为这个指令用不到这些flags，所以填充默认值

3.4 高级 ap 

指令 ap + = < op > 通过给定的操作数增加 ap 的值。 

图7给出了高级 ap 指令的一些示，以及每个指令对应的标志：

解释 指令 ap += 123： 

◦ 为advancing ap指令 => opcode = 0 

◦ next_ap = ap + res => ap_update = b01 = 1

◦ next_pc = pc + instruction_size => pc_update = b000 = 0 

◦ res = op1 => res_logic(res) = b00 = 0 

◦ op1 = 123 => op1_src(op1) = b001 = 1 

◦ op1 = 123 => off_op1 = 1 

◦ op0_reg/ off_op0 => inital value(1/-1) ///因为这个指令用不到这些flags，所以填充默认值 

◦ dst_reg/ off_dst => inital value(1/-1) ///因为这个指令用不到这些flags，所以填充默认值

参考

Specification for Cairo：https://arxiv.org/pdf/2109.14534.pdf

关于我们

Sin7Y成立于2021年，由顶尖的区块链开发者和密码学工程师组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。

微信公众号：Sin7Y

GitHub：Sin7Y

Twitter：@Sin7Y_Labs

Medium：Sin7Y

Mirror：Sin7Y

HackMD：Sin7Y

HackerNoon：Sin7Y

Email：contact@sin7y.org