Polygon zkEVM Binary状态机

1. 引言

前序博客有：

• Polygon zkEVM Arithmetic状态机
• Polygon zkEVM中的常量多项式

Binary状态机为Polygon zkEVM的六个二级状态机之一，该状态机内包含：

• executor part：sm_binary.js：负责生成execution trace，为常量多项式和隐私多项式赋值。
• 验证规则集PIL：binary.pil：定义了约束系统。

相应的test vectors见：binary_test.js：包含了所支持的各类计算的测试集。

Polygon zkEVM Binary状态机针对的是256-bit字符串的二进制运算，当前支持的二进制运算有：

相应的运算定义可参见zkasmcom中的zkasm_parser.jison中：

    | ADD
        {
            $$ = { bin: 1, binOpcode: 0}
        }
    | SUB
        {
            $$ = { bin: 1, binOpcode: 1}
        }
    | LT
        {
            $$ = { bin: 1, binOpcode: 2}
        }
    | SLT
        {
            $$ = { bin: 1, binOpcode: 3}
        }
    | EQ
        {
            $$ = { bin: 1, binOpcode: 4}
        }
    | AND
        {
            $$ = { bin: 1, binOpcode: 5}
        }
    | OR
        {
            $$ = { bin: 1, binOpcode: 6}
        }
    | XOR
        {
            $$ = { bin: 1, binOpcode: 7}
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2. 将256位字符串编码为有符号位和无符号位整数

在理解以上运算规则的工作原理之前，需首先了解zkEVM是如何将256位字符串编码为signed integers和unsigned integers。

以3-bit字符串为例，相应的uint和int编码表示为：【可很容易将其扩展至256-bit字符串】【对于int表示，需注意-4和4具有相同的编码方式。】

ADD和SUB可逐bit运算，如以3-bit string 0b001和0b101（0b表示二进制）为例，逐bit add为：

• 初始$carry=0$，最低有效位相加有：$1+1+carry=1+1+0=0$，因此，下一carry值为$carr{y}^{\prime }=1$。

• 其次，将次低有效位相加，并与前一carry相加，有$0+0+carry=0+0+1=1$，此时，下一carry值为$carr{y}^{\prime }=0$。

• 最后，将最高有效位相加，并与前一carry相加，有$0+1+carry=0+1+0=1$，最终carry值为$carr{y}^{\prime }=0$。

• 最终结果为：$0b001+0b101=0b110$ with $carry=0$。

不过LT（less than）与 SLT（unsigned less than）有所不同，LT按正常顺序直接比较即可，而SLT：

• 1）若最高有效位相同，则按正常顺序直接比较，如101<110，即-3<-2。
• 2）若最高有效位不同，则顺序相反（以0为最高有效位的值更大），如110<001，即-2<1。

而AND/OR/XOR/NOT运算均为bit-wise运算，即可逐位计算，且无需考虑进位（carry）情况：

注意，zkEVM中未单独设置NOT运算符，因NOT运算可看成是与0xff…ff的XOR运算。

3. polygon zkEVM Binary状态机设计思想

polygon zkEVM Binary状态机的executor part：sm_binary.js，负责记录状态机内的每个computation trace，该computation trace可用于证明计算的正确性。
execution trace通常以256-bit字符串来表示，每个正确的execution trace必须满足相应的多项式约束，这些多项式约束定义在PIL代码文件中。

3.1 internal Byte Plookups

Binary状态机内部使用plookups of bytes来表达所有二进制运算。
在其plookups table中，包含了所有可能的input bytes和output byte组合：
$${\text{byte}}_{i{n}_0}\star {\text{byte}}_{i{n}_1}={\text{byte}}_{out},$$
其中$\star$表示所有可能的运算。
当对256-bit字符串进行二进制运算时，某execution trace可 以cycles of 32 steps 来实现一个运算。（因32*8=256）
在每一个step，对应为byte-wise操作 和 ‘carries’ 或其它任何辅助值信息，来构成computation trace。
此外，每个256-bit字符串（2个输入、1个输出）使用8个 32-bit的寄存器来表示。

3.2 Main状态机与Binary状态机的连接

Polygon zkEVM的Main状态机的execution trace 与 Binary状态机的execution trace 之间的约束是通过一个Plookup来连接的——即，当cycle结束（即名为RESET的寄存器为1）时，会对Binary状态机execution trace中的每一行进行运算。该Plookup会检查相应的operation code、输入和输出的256-bit字符串的寄存器 以及 最终的carry。

4. Byte-wise运算

由于Polygon zkEVM Binary状态机选用byte plookups，因此接下来将256-bit运算转换为了byte-wise运算。

将$256$-bit整数$\mathbf{a}$表示为：$(a_{31},\dots ,a_1,a_0)$，即：
$$\mathbf{a}=a_{31}\cdot (2^8{)}^{31}+a_{30}\cdot (2^8{)}^{30}+\cdots +a_1\cdot 2^8+a_0=\sum _{i=31}^0{a}_i\cdot (2^8{)}^i,$$
其中每个$a_i$为一个字节，其取值范围为$0$到$2^8-1$。

如$\mathbf{a}=29967$，将其按byte分解表示为$\mathbf{a}=(0x75,0x0F)$，因$\mathbf{a}=29967=117\cdot 2^8+15$，以16进制表示为：$117\mapsto 0x75$ 以及 $15\mapsto 0x0F$。

4.1 ADD加法运算

将讲述如何将2个256位数字的加法运算 reduce为 a byte-by-byte加法运算，然后使用byte-wise Plookup table。
观察2个byte $a,b$的加法运算，即$a,b$为$[0,2^8-1]$集合中的成员，二者之和$c$可能无法以一个字节来表示。
如$a=0xFF$，$b=0x01$ 则：
$$a+b=0xFF+0x01=0x100.$$
以字节形式表示，$c=0x00$ 且 $carr{y}^{\prime }=1$。即在处理byte add时，需考虑进位。

接下来，考虑2个byte的加法：
如$\mathbf{a}=(a_1,a_0)=(0xFF,0x01)$ and $\mathbf{b}=(b_1,b_0)=(0xF0,0xFF)$：

• 首先对低有效字节相加：
  a 1 + b 1 = 0 x 01 + 0 x F F = c 1 = 0 x 00 , c a r r y 1 = 1.
  a1+b1=0x01+0xFF=c1=0x00,carry1=1." role="presentation">a1+b1carry1=0x01+0xFF=c1=0x00,=1.$$\begin{array}{rl}{a}_1+b_1& =\mathtt{0}\mathtt{x}\mathtt{01}+\mathtt{0}\mathtt{x}\mathtt{F}\mathtt{F}=c_1=\mathtt{0}\mathtt{x}\mathtt{00},\\ carr{y}_1& =1.\end{array}$$
  a1​+b1​carry1​​=0x01+0xFF=c1​=0x00,=1.​
• 然后对次有效字节相加：
  a 2 + b 2 + c a r r y 1 = 0 x F F + 0 x F 0 = c 2 = 0 x F 0 , c a r r y 2 = 1.
  a2+b2+carry1=0xFF+0xF0=c2=0xF0,carry2=1." role="presentation" style="position: relative;">a2+b2+carry1carry2=0xFF+0xF0=c2=0xF0,=1.$$\begin{array}{rl}{a}_2+b_2+carr{y}_1& =\mathtt{0}\mathtt{x}\mathtt{F}\mathtt{F}+\mathtt{0}\mathtt{x}\mathtt{F}\mathtt{0}=c_2=\mathtt{0}\mathtt{x}\mathtt{F}\mathtt{0},\\ carr{y}_2& =1.\end{array}$$
  a2​+b2​+carry1​carry2​​=0xFF+0xF0=c2​=0xF0,=1.​

2字节相加时，对应有如下情况需区分对待：

• 1）若$a_1+b_1<2^8$ 且 $a_2+b_2<2^8$，则$\mathbf{a}+\mathbf{b}$之和可简单表示为：
  $$\mathbf{a}+\mathbf{b}=(a_2+b_2,a_1+b_1).$$

• 2）若$a_1+b_1<2^8$ 但 $a_2+b_2\ge 2^8$, 则 $a_2+b_2$ 无法以单一字节来表示，从而可将$a_2$ 和 $b_2$ 之和表示为：
  $$a_2+b_2=1\cdot 2^8+c_2,$$
  ​ $\mathbf{a}+\mathbf{b}$之和表示为：
  $$\mathbf{a}+\mathbf{b}=(1,c_2,a_1+b_1).$$

• 3）若$a_1+b_1\ge 2^8$，则有：
  $$a_1+b_1=1\cdot 2^8+c_1,$$
  从而有：
  $$\mathbf{a}+\mathbf{b}=(a_2+b_2+1)\cdot 2^8+c_1.$$

  • 3.a）若$a_2+b_2+1\ge 2^8$，则有：
    $$a_2+b_2+1=1\cdot 2^8+c_2.$$
    ​ 最终$\mathbf{a}+\mathbf{b}$之和表示为：
    $$\mathbf{a}+\mathbf{b}=(1,c_2,c_1).$$
  • 3.b）若$a_2+b_2+1<2^8$，则$\mathbf{a}+\mathbf{b}$之和表示为：
    $$\mathbf{a}+\mathbf{b}=(c_2,c_1).$$

对于$256$-bit数字加法，可reduce为类似以上byte-level计算。

4.2 SUB减法运算

减法比加法更具技巧。
如$\mathbf{a}=0x0101$，$\mathbf{b}=0x00FF$，相应的减法表示为：
$$\begin{array}{rl}\mathbf{a}-\mathbf{b}& =(0x01-0x00)\cdot 2^8+(0x01-0xFF)\\ & =(0x01-0x00)\cdot 2^8-2^8+2^8+(0x01-0xFF)\\ & =(0x01-0x00-0x01)\cdot 2^8+0xFF+0x01+0x01-0xFF\\ & =(0x00)\cdot 2^8+0x02\end{array}$$
即最终结果以byte形式表示为：$\mathbf{c}=(c_1,c_0)=(0x00,0x02)$

byte-wise减法运算只需考虑如下2种场景：

• 若$a_i-\text{carry}\ge b_i$，则$a_i-b_i-\text{carry}$提供了$a-b$的第$i$个byte结果表达。
• 若$a_i-\text{carry}<b_i$，则a-b$的第$i$个byte结果表示为：
  $$2^8-b_i+a_i-\text{carry}=255-b_i+a_i-\text{carry}+1.$$

以$a=0x0001FE$，$b=0xFEFFFF$为例，$a-b$结果表示为：
$$c=(0x01,0x01,0xFF)=0x01\cdot 2^{16}+0x01\cdot 2^8+0xFF.$$

4.3 Less Than小于运算

Less Than小于运算是指：

• 若$a<b$，则结果$c=1$；
• 若$a\ge b$，则结果$c=0$。

	// ############################################################
    // COMMIT POLINOMIALS
    // ############################################################
    // opcode = (2  bits) Operation code
    // ============================================================
    // a0-a7, a0-a7, a0-a7
    // 256 bits operations -> 32 Bytes / 4 Bytes (per registry) ->
    //          8 Registries
    // ============================================================
    // freeInA, freeInB, freeInC -> 1 Byte input
    // ============================================================
    // cIn -> Carry In ; cOut -> Carry Out ; lCIn -> Latch Carry in
    // ============================================================
    pol commit freeInA, freeInB, freeInC;
    pol commit a0, a1, a2, a3, a4, a5, a6, a7;
    pol commit b0, b1, b2, b3, b4, b5, b6, b7;
    pol commit c0, c1, c2, c3, c4, c5, c6, c7;
    pol commit opcode;
    pol commit cIn, cOut;
    pol commit lCout,lOpcode;
    pol commit last;
    pol commit useCarry; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22