Polygon zkEVM Arithmetic状态机
1. 引言
Polygon zkEVM中将某类特定的计算表示为状态机。
Arithmetic状态机为Polygon zkEVM的6个二级状态机之一，主要由2大部分组成：
- 1）Executor部分：有2个版本，Javascript版本 和 C/C++版本。https://github.com/0xPolygonHermez/zkevm-proverjs/tree/main/src/sm/sm_arith。
- 2）验证规则集（a set of verification rules）程序部分：以PIL语言实现，见 https://github.com/0xPolygonHermez/zkevm-proverjs/blob/main/pil/arith.pil。
Polygon zkEVM的Arithmetic状态机主要是基于Secp256K1椭圆曲线E（ y 2 = x 3 + 7 y^2=x^3+7 y2=x3+7，基域为 p = 2 256 − 2 32 − 2 9 − 2 8 − 2 7 − 2 6 − 2 4 − 1 p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1 p=2256−232−29−28−27−26−24−1）上的如下运算：
- 1）域内加法和乘法等运算： x 1 ⋅ y 1 + x 2 = y 2 ⋅ 2 256 + y 3 x_1\cdot y_1+x_2=y_2\cdot 2^{256}+y_3 x1⋅y1+x2=y2⋅2256+y3。若 y 1 = 0 y_1=0 y1=0，则表示的是field addition运算；若 x 2 = 0 x_2=0 x2=0，则表示的是field multiplication运算。
- 2）椭圆曲线点加运算：椭圆曲线上2个不同点
P
=
(
x
1
,
y
1
)
,
Q
=
(
x
2
,
y
2
)
P=(x_1,y_1),Q=(x_2,y_2)
P=(x1,y1),Q=(x2,y2)，
x
1
≠
x
2
x_1\neq x_2
x1=x2,
P
+
Q
=
(
x
3
,
y
3
)
P+Q=(x_3,y_3)
P+Q=(x3,y3)计算为：
x 3 = s 2 − x 1 − x 2 , x_3=s^2-x_1-x_2, x3=s2−x1−x2,
y 3 = s ( x 1 − x 3 ) − y 1 y_3=s(x_1-x_3)-y_1 y3=s(x1−x3)−y1
其中 s = y 2 − y 1 x 2 − x 1 s=\frac{y_2-y_1}{x_2-x_1} s=x2−x1y2−y1。 - 3）椭圆曲线点倍加运算：椭圆曲线上点
P
=
(
x
1
,
y
1
)
P=(x_1,y_1)
P=(x1,y1)，,
2
P
=
P
+
P
=
(
x
3
,
y
3
)
2P=P+P=(x_3,y_3)
2P=P+P=(x3,y3)计算为：
x 3 = s 2 − 2 x 1 , x_3=s^2-2x_1, x3=s2−2x1,
y 3 = s ( x 1 − x 3 ) − y 1 y_3=s(x_1-x_3)-y_1 y3=s(x1−x3)−y1
其中 s = 3 x 1 2 2 y 1 s=\frac{3x_1^2}{2y_1} s=2y13x12。
将以上运算以约束形式表示为：
EQ
0
:
x
1
⋅
y
1
+
x
2
−
y
2
⋅
2
256
−
y
3
=
0
,
EQ
1
:
s
⋅
x
2
−
s
⋅
x
1
−
y
2
+
y
1
+
q
0
⋅
p
=
0
,
EQ
2
:
2
⋅
s
⋅
y
1
−
3
⋅
x
1
⋅
x
1
+
q
0
⋅
p
=
0
,
EQ
3
:
s
⋅
s
−
x
1
−
x
2
−
x
3
+
q
1
⋅
p
=
0
,
EQ
4
:
s
⋅
x
1
−
s
⋅
x
3
−
y
1
−
y
3
+
q
2
⋅
p
=
0
,
\begin{aligned} \text{EQ}_0 \colon \quad &x_1 \cdot y_1 + x_2 - y_2 \cdot 2^{256} - y_3 = 0, \\ \text{EQ}_1 \colon \quad &s \cdot x_2 - s \cdot x_1 -y_2 + y_1 + q_0 \cdot p = 0, \\ \text{EQ}_2 \colon \quad & 2 \cdot s \cdot y_1 - 3 \cdot x_1 \cdot x_1 + q_0 \cdot p = 0, \\ \text{EQ}_3 \colon \quad & s \cdot s - x_1 - x_2 - x_3 + q_1 \cdot p = 0, \\ \text{EQ}_4 \colon \quad & s \cdot x_1 - s \cdot x_3 - y_1 - y_3 + q_2 \cdot p = 0, \end{aligned}
EQ0:EQ1:EQ2:EQ3:EQ4:x1⋅y1+x2−y2⋅2256−y3=0,s⋅x2−s⋅x1−y2+y1+q0⋅p=0,2⋅s⋅y1−3⋅x1⋅x1+q0⋅p=0,s⋅s−x1−x2−x3+q1⋅p=0,s⋅x1−s⋅x3−y1−y3+q2⋅p=0,
其中
q
0
,
q
1
,
q
2
∈
Z
q_0,q_1,q_2 \in \mathbb{Z}
q0,q1,q2∈Z为整数，使得以上等式成立。这种表达可避免对
p
p
p做除法运算。
这些约束对应3个可能的计算场景：
- 若 E Q 0 EQ_0 EQ0激活，则其它等式失效；
- 若 E Q 1 , E Q 3 , E Q 4 EQ_1,EQ_3,EQ_4 EQ1,EQ3,EQ4激活，则 E Q 0 , E Q 2 EQ_0,EQ_2 EQ0,EQ2等式失效；
- 若 E Q 2 , E Q 3 , E Q 4 EQ_2,EQ_3,EQ_4 EQ2,EQ3,EQ4激活，则 E Q 0 , E Q 1 EQ_0,EQ_1 EQ0,EQ1等式失效。
由于在以上任意场景下， E Q 1 EQ_1 EQ1和 E Q 2 EQ_2 EQ2最多只能激活一个，因此二者可“共享”相同的 q 0 q_0 q0。
为实现以上运算，Arithmetic状态机内需包含以下寄存器：
x
1
,
y
1
,
x
2
,
y
2
,
x
3
,
y
3
,
s
,
q
0
,
q
1
,
q
2
x_1,y_1,x_2,y_2,x_3,y_3,s,q_0,q_1,q_2
x1,y1,x2,y2,x3,y3,s,q0,q1,q2
这些寄存器均为256-bit field elements，实际构建时，将每个寄存器切分为16个子寄存器，每个子寄存器容量为16-bit（2个字节），为此，PIL中的定义为：
pol commit x1[16];
pol commit y1[16];
pol commit x2[16];
pol commit y2[16];
pol commit x3[16];
pol commit y3[16];
pol commit s[16];
pol commit q0[16];
pol commit q1[16];
pol commit q2[16];
附录：Polygon Hermez 2.0 zkEVM系列博客
- ZK-Rollups工作原理
- Polygon zkEVM——Hermez 2.0简介
- Polygon zkEVM网络节点
- Polygon zkEVM 基本概念
- Polygon zkEVM Prover
- Polygon zkEVM工具——PIL和CIRCOM
- Polygon zkEVM节点代码解析
- Polygon zkEVM的pil-stark Fibonacci状态机初体验
- Polygon zkEVM的pil-stark Fibonacci状态机代码解析
- Polygon zkEVM PIL编译器——pilcom 代码解析