ZKSwap团队解读零知识证明算法之Zk-stark——Arithmetization

前言

本系列的，以 Zk-snark 做对照，分别从概念和算法流程上，做了概括性的介绍。建议在阅读本篇文章之前，先阅读下第一篇文章的内容。本篇文章，让我们由浅入深，一起踏上探索 Zk-stark 算法奥秘的旅途。

回顾

在第一篇的文章中讲到，Zk-stark 算法大体可以分为两个部分：Arithmetization 和 Low Degree Testing。本篇我们先详细介绍算法的第一阶段 Arithmetization。 Arithmetization 的整体步骤如下图所示：

那什么是 Arithmetization ？具体过程又是什么呢？带着这些疑问，让我们仔细的品味文章后面的内容。

首先，什么是 Arithmetization？

Arithmetization 就是把 CI statement 转化成正式的 Algebraic language 的过程，此步骤有两个目的：第一，把 CI statement 以简洁清晰的方式呈现出来；第二，把 CI statement 嵌入到代数域，为后面多项式的转换做铺垫。Arithmetization representation 主要由两部分组成：第一，执行轨迹（图中橙色部分）；第二，多项式约束（图中灰色部分）。执行轨迹是一个表，表的每一行代表一个单步的运算；多项式约束的构造是和执行轨迹相辅相成的，即当前仅当执行轨迹是正确的，多项式约束会满足执行轨迹的每一行计算。最后把执行轨迹和多项式约束结合组成一个确定的多项式，然后对多项式进行 LDT 验证。至此，验证 CI statement 的问题转换成了验证确定性多项式 LDT 的问题。

Arithmetization

知道了 Arithmetization 的整体流程，接下来，我们讨论下具体的过程。为了便于理解，我们用一个简单的例子，来贯穿整个 Arithmetization 的过程。 每个人都去过超市，一般超市的收据的内容如下：

现在，好莱坞人气演员 Bob 声称：”the total sum we should pay at the supermarket was computed correctly”。那怎么验证呢？其实很简单，这时另一个气人演员 Alice 只要对着收据，每一项累加求和就可以完成验证。那么，这只是一个很简单的例子，事实上，Alice 只需要 5 步，就可以完成验证过程。试想这样一个场景：毕竟 Bob 很有钱，在超市买了 1000000 样东西，同样，他又声称：”the total sum we should pay at the supermarket was computed correctly”，这时候，Alice 真的生气了，这怎么验证，按照之前的办法，得大约要算 1000000 步，闹呢？谁爱干谁干。Bob 心里也心疼 Alice，毕竟那么多年了。心想，有没有什么牛掰的办法能让 Alice 用很少的步骤，就能确信我说的是对的呢？于是，Bob 开动了最强大脑模式。 下面，让我们用上面简单的例子，跟随 Bob 去寻找这个牛掰的办法。

Bob 心想，你不就是验证最终的总和对不对么？那我就把总和的计算过程列出来，我保证每次的累加都对，那么我最终的结果一定也是对的。于是 Bob 在收据上新增了一列，用来保存计算总和过程中的中间值（图中橙棕色部分标注），这就是执行轨迹（图 1 中的橙色部分）。新增的一列值需要满足，初始化的值为 0（图 2 中黄色部分）、最终的值和要付的总和相等（图 2 中黄色部分）、中间的每一个值都要等于上一个值加上上一行物品的单价（图 2 中红线部分），这构成了多项式约束（图 1 灰色部分，图 2 左下角部分）。 从图 2 可以看出：

• 多项式约束总共有 3 个，两个是边界约束（多项式索引 1&3），一个是循环约束（多项式索引 2）；
• 多项式的大小和执行轨迹的答案小没有关系，即表格的长度即使扩大到 1000000 ，最终的多项式约束仍是这三个，唯一变化的是变量 x 的取值范围而已。

在这里，借用 V 神的话来描述一下 Zk-stark：Zk-Stark 不是一个确定性的算法，它是一大类密码��数学结构，对于不同的应用，具有不同的最优设置。可以理解为，对于不同的问题，具有不同的算术化的方案（在本例中，是加一列值，在其他案例中就不一定适用了），因此要做到具体问题具体分析。但是有一个共同目标就是，无论是什么问题，得到的执行轨迹最好是用一个 LOOP 就可以表示，这样得到的多项式约束也就最为简洁。多项式约束的个数和形式直接影响到了 proof 的大小和 Zk-stark 算法的性能，因此，寻找一个最优的设置对于 Zk-stark 算法显得尤为重要。 回归到主题，现在 Bob 已经得到了多项式约束和执行轨迹，那么如何把它们转换成一个确定的多项式呢？请看下图：（蓝色箭头代表主流程，红色箭头代表分支）

Bob 首先把关注点切到执行轨迹，可以看到执行轨迹有 2 列，一列是单项价格，一列是价格总和，我们分别对两列的元素进行拉格朗日插值，得到两个函数 f(x), w(x)，0≤ x ≤5。分别对两个函数进行域扩展，得到了在更多的点上的评估，即 f(x)，w(x) ，0≤ x ≤10000（从多项式插值，到域扩展，这其实就是 Reed-Solomen 的编码过程，它可以实现，原始数据哪怕有一处差异，得到的码字会大不相同；主要目的用于防止证明者作恶，加入证明者作恶，会使得验证者很容易发现）。

然后，Bob 把 f(x)，w(x) 和多项式约束等式结合，得到一组确切的多项式约束(图中红色圈 2 所示)，以循环约束多项式为例：

1 ≤ x ≤ 5 w(x) – f(x -1) – w(x -1) = 0 (1)

令 Q(x) = w(x) – f(x-1) – w(x-1)，则有 Q(1) = 0、Q(2) = 0、Q(3) = 0、Q(4) = 0、Q(5) = 0。

根据已知事实，度为 d 的多项式 H(x) 在 x=n 处为 0，则存在一个度为 d-1 的多项式 H(x), 满足 d (H(x)) = d(H(x)) – 1 && H(x) = H`(x) * (x – n)

因此对于 Q(x)，度为 5，存在一个多项式 Ψ(x)，度为 0，即常量，满足 Q(x) = Ψ(x) * (x – 1)(x – 2)(x – 3)(x – 4)(x – 5)，令目标多项式 T(x) = (x – 1)(x – 2)(x – 3)(x – 4)(x – 5)，度为 5，则有：

Q(x) = Ψ(x) * T(x) (2)

验证者 Alice 从 0≤x≤10000 随机选择一点 a，发送给证明者 Bob，要求 Bob 返回相应的值，以公式 (2) 为例，Bob 需要返回 w(a)、w(a-1)、f(a-1)、Ψ(a)，然后 Alice 判断等式是否成立，即：

w(a) – f(a – 1) – w(a – 1) = Ψ(a) * T(a) (3)

如果等式成立，则 Alice 大概率相信执行轨迹是正确的，那么原始计算成立。假如验证者Bob作恶，讲表格中的 4.98 改成 5.98 把，那么 Q(1) = w(1) – w(0) – f(0) = 5.98 – 0 – 4.98 = 1，不等于 0。在这种情况下，观察公式(2)，等式右边为 Q(x)，度为5，x = 1不是零点；等式右侧 Ψ(x) * T(x) ，令G(x) = Ψ(x) * T(x)，度为 5，因为 T(x)在 x = 1 处是零点，所以 G(x) 在 x=1 处也是 0 点，因此，等式两边实际上是度相等的不同多项式，其交点最多为 5 个，因此在 0≤ x ≤10000 范围内，只有 5 个值相等，9995 值是不等的，因此随机的从 0≤ x ≤10000 中选择一个值，验证不通过的概率是 99.95%，如果域扩展的范围更大，则验证不通过的概率将会更接近于 1。按照同样的逻辑，分别处理边界约束多项式，得到的结果如图所示（图中红色圈 3 所示）。

下面，我们讲讨论如何增加零知识属性。

对于证明者 Bob 来讲，执行轨迹是不希望被验证者 Alice 看到的，因为它会包含一些重要的信息，因此，限定验证者 Alice 只能从 6 ≤ x ≤ 10000 范围内随机选择一个值，进行验证，当然这种限定，双方都是同意的。

存在这样一类问题。当验证者 Alice 收到证明者 Bob 反馈的值时，如何保证这些值是合法的，确实是通过多项式的形式计算，并且这些多项式是小于某个度的，而不是证明者Bob仅仅为了验证通过，而生成的随机值？比如如何确保 w(a)、w(a-1)、f(a-1)、Ψ(a) 是多项式 w(x)、f(x)、Ψ(x) 分别在 x = a && x = a – 1 上的取值呢，且多项式 w(x)、f(x)、Ψ(x) 的度小于某个固定值的呢？这些问题将在下一篇文章中给出答案，在此之前，不如先讨论一下，为何多项式的度小于某个固定值就能证明原始执行轨迹式正确的呢？

从以上的例子中，可以看出，当且仅当执行轨迹是正确的时候，Q(x) 才会在 x 取值为 1、2、3、4、5 时，等于 0。那么 Q(x) 才可以被目标多项式 T(x) 整除，即：Ψ(x) = Q(x) / T(x) ，d(Ψ(x)) = d(Q(x)) – 5。

从图 3 可以看出，需要验证的多项式的个数时 5 个(红色圈 4 所示)，如果对每一个多项式都进行 LDT，那么消耗是很巨大的，因此，可以通过将这些多项式进行线性组合(红色圈 5 所示)，当且仅当每个多项式都满足小于某个度时，其线性组合后的多项式也是小于某个度的，这个条件时充分的，具体的细节见后续的系列章节。