ZKSwap团队深入解读零知识证明算法之Zk-stark（七）：Low Degree Testing

前言

本系列的第二篇文章，以超市收据为例，描述了 Arithmetization 的具体过程。本文将以另外一个例子为基础，在回顾 Arithmetization 过程的同时，将内容引申到多项式的 LDT 过程。

新的实例

Alice Claim：“我有 1000000 个数，他们都在 [0,9] 范围内”。为了方便验证者 Bob 验证，Alice 首先要对 Claim 进行 Arithmetization 转换。过程如下图 1 所示(图中：黑色箭头代表主流程，红色箭头代表附加说明信息，黄色圈对应下面详细说明的索引)。

下面具体说明一下对应流程：

1. 首先生成执行轨迹(EXCUTE TRACE)，事实上，它是一张表，总共有 1000000 行（实际上，为了达到零知识的目的，还需要在执行轨迹后面增加一些随机值，具体数量是由证明者和验证者统一协调决定的，作为一个扩展，不具体讲述）；
2. 生成多项式约束(Polynomial Constrains)，多项式约束满足执行轨迹的每一行(个人理解：步骤 1，2 没有一定的先后依赖关系，只是习惯上先生成执行轨迹，再生成约束多项式)；
3. 对执行轨迹进行插值，得到一个度小于 1000000 的多项式 P(x)、x 取值[1,1000,000]，并计算更多点上的值，x 取值范围扩大到11000000000；假如，证明者有一个值不在[0,9] 范围内(图中红线 1/2 所示)，假如就是第 1000000个点，它实际的值是 13，大于 9，其插值后的曲线 G(x) 如图所示，图中 P(x) 为有效曲线，G(x) 为无效曲线。可以看出，两条曲线在变量 x 取值 [1,1000000000] 范围内，最多有 1000000个交点，即有1000000000 – 1000000 个点不同，这很重要。
4. 将插值后的多项式 P(x) 和多项式约束进行组合变换，最终得到的形式为：

Q(P(x)) = Ψ(x) * T(x)，其中 T(x) = (x – 1)(x – 2)……(x – 1000000)，x 取值[1,1000000000]

其中，d(Q(P(x))) = 10000000、d(Ψ(x)) = 10000000 – 1000,000、d(T(x)) = 1000000；

1. 至此，问题就转化成了，Alice 宣称“多项式等式在变量x取值[1,1000000000]范围内成立”的问题。那么验证者 Bob 该如何验证呢？具体过程如下（图中红线 3/4 所示）： a. 证明者 Alice 在本地计算多项式P(x)、Ψ(x)在所有点上的取值，对！从1至1000000000，并形成一个默克尔树； b. 验证者 Bob 随机的从[1,1000,000000]内选取一个值 ρ，并发送给证明者Alice，要求其返回对应的信息（事实上为了达到零知识的目的，只允许从[1000,000,1000,000,000]上随机选择一点）； c. 证明者 Alice 返回 P(ρ)、Ψ(ρ)、root、AuthorizedPath(P(ρ)、Ψ(ρ))给验证者Bob； d. 验证者Bob首先根据默克尔树验证路径验证值 P(ρ)、Ψ(ρ)的有效性，然后等式Q(P(ρ)) = Ψ(ρ) * T(ρ)，如果成立，则验证通过；

完整性分析：如果验证者 Alice 是诚实的，那么等式 Q(P(x))一定会被目标多项式 T(x)整除，因此必定存在一个 d(Ψ(x)) = d(Q(P(x))) – d(T(x)) 的多项式 Ψ(x)，满足Q(P(x)) = Ψ(x) * T(x)，因此对于任意的 x，取值在[1,1000,000,000]之间，等式都会成立；

可靠性分析：如果验证者 Alice 是不诚实的，即类似于步骤 3 里的假设，在x = 1000,000上，P(x)的取值为 13，那么Q(P(1000,000)) != 0，但是等式右边，T(1000,000) = 0，因此Q(P(x)) != Ψ(x) * T(x)，即等式两边是不相等的多项式，其交点最多有 10,000,000 个，因此通过一次随机选取，其验证通过的概率仅为10,000,000/1000,000,000 = 1/100 = 0.01，经过k次验证，其验证通过的概率仅是 1- 10(^-2k)；

• 上述的验证过程为交互式的，如果是非交互式的，可以利 Fiat-Shamir heuristic 进行变换，以默克尔树的根作为随机源，生成要查询的随机点；

LDT

我们忽略了一种攻击方式，即针对每一个数 x，证明者都随机生成 p，然后根据 Ψ(x) = Q(p) / T(x)，这些点不在任何一个度小于 1000000 的多项式上，但是可以通过验证者验证。如下图 2 所示：

图中：紫色的点为随机生成的点 p，这些点大概率不在一个度小于 1000,000 的多项式上(事实上，可以不考虑前 1000,000 个点，因为验证者只会从[1000,000，1000,000,000]范围内取值)。因为即使选择 1000,000 个点插值出一个度小于 1000,000 的多项式，也不能保证其他的点在这个多项式上，因为其他的点是随机生成的。因此，需要有一种方式，保证证明者 P(x)的度是小于 1000,000， Ψ(x)的度小于10,000,000 – 1000,000。这就是 LDT 的目标，那 LDT 具体的过程是怎么样的呢？请继续往下看。

举个栗子，如果 Alice 想证明多项式 f(x) 的度是小于 3 的，即有可能是 2 次的或者是1次的。一般流程如下：

1. 验证者 Bob 随机选取三个值 a,b,c，发送给证明者 Alice；
2. 证明者 Alice 返回 f(a),f(b),f(c)；
3. 验证者 Bob 插值出度小于 3 的多项式 g(x)，然后再随机选取一个点 d，发送给证明者；
4. 证明者 Alice 返回f(d)；
5. 验证者 Bob 比对 f(d)和g(d)的值，如果相等，则证明成立。

回归到一般情况，其过程可以用下图 3 表示：

可以看出，如果 D 很大，Alice 和 Bob 交互的次数则为 D+k 次，复杂度很高；有没有一种办法，使得两者之间交互的次数小于 D 的情况下，使得验证者相信多项式的度是小于 D 的，直接返回小于 D 个点肯定是不行的，因为那不能唯一确定一个度小于 D 的多项式，因此需要证明者需要额外发送一些辅助信息。下面我们以 P(x)为例，详细阐述这个过程(事实上，应该是证明 P(x) 和 Ψ(x) 的线性组合小于 10,000,000 – 1000,000，本文重点是 LDT，因此只以 P(x) 为例，这并不影响对 LDT 的理解)。

假如 P(x) = x + x^999 + x^1001 + x^999999 = x + x^999 + x * x^1000 + x^999*(x^1000)^999;

此时，我们找到一个二维多项式 G(x, y)，取值范围分别是[0, 999999999]、[01000, 9999999991000]，满足： G(x, y) = x + x^999 +x * y + x^999y^999 可以发现，当y = x^1000时，满足： G(x, y) = G(x, x^1000) = x + x^999 + x * x^1000 + x999(x^1000)^999 = P(x) 如果我们能证明 G(x, y) 相对的 x,y 的最高度都是小于 1000，因为P(x) = G(x, x^1000)上，因此可以相信 P(x) 的度小于 1000000；如图 4 所示：

验证者把所有的点都计算好（没错，总共 10^18 个点），形成一颗默克尔树。验证者随机选择一行和一列，如图中红线 1/2 所示，对于每一列，它是由关于y的度小于 1000 的多项式生成，对于每一行，它是由关于x的度小于 1000 的多项式生成。验证者从行/列中随机选择 1010 个点，用来验证对应行/列上的点是否在度小于 1000 的多项式上，需要注意的是，因为 P(x)的点都在上图的对角线上，因此我们要确保每一行/列对应的对角线上的点也在对应的度小于 1000 的多项式上，即 1010 个里面一定要包含对角线的点。

可靠性分析：如果原始多项式的度实际上是小于 10^6 +10999，即 P(x) = x + x^999 + x^1001 + x^1010999 ，那么对应的 G(x, y) 为 G(x, y) = x + x^999 +x * y + x^999*y^1010 ，即，对于每一个 x，G(x, y) 是关于 y 的一元多项式函数，且度 d < 1010，因此下图中的每一列所有点都是在度 d < 1010 的多项式上，而不在 d < 1000的多项式式上。所以如果证明者任然宣称多项式 P(x) 的度 d < 1000,000 ，则会验证失败，其他场景是同样的道理

那有没有可能恶意证明者仍以 G(x, y) = x + x^999 +x * y + x^999*y^999 的形式去生成证据呢？这样会验证通过吗？

我们知道，我们在验证时着重强调了对角线上的那一点一定要在多项式上，我们知道，此时对角线对应的多项式形式是：

P(x) = x + x^999 + x1001 + x^999999 ，而实际的 P(x)，我们在这里标记为 P`(x) ，其形式是：

P`(x) = x + x^999 + x^1001 + x^1010999

因此，如果验证者恰好选择的点是两个多项式的交点，则会验证通过，事实上，两个多项式最多有 1000,000 左右个交点，但是由于随机选取的点不是证明者自己选取，是由默克尔树的根为种子随机生成，因此证明者没有机会作恶，去可以选取那些能通过验证的点。

由于总共由 10^9 个点，因此随机选取一个点，能验证成功的概率为 10^6 / 10^9 = 10^(-3)，如果选择 k 行，则成功的概率仅为 10^(-3k)。

以上可以看出，验证者和证明者只需要交互 1010 * 2 * k 个点，就可以完成验证，假如k = 10，则 1010 * 2 * 10 = 20100 << 10^6。

• 虽然上述实现了在交互次数小于 D 的情况下，完整 LDT 验证，但是证明者的复杂度过于庞大，至少 10^18 的复杂度远远大于原始的计算，因此需要一些优化方案，降低复杂度。话不多说，直接引入有限域，毕竟在实际项目中，我们可不希望数值本身过于庞大。直接引用费马小定理的结论：在有限域p内，如果满足(p – 1) 能被 k 整除，则映射 x => x^k的像只有(p -1) / k + 1个。下图 5 以 p = 17，映射 x=> x^2 为例：

图中，红色为 x^2 在有限域 p 内的象，总共由(p – 1) /2 + 1 = 9 个。同时我们可以发现，9^2 和 8^2 的像一致，10^2 和 7^2 的像一致，以此类推，16^2 和 1^2 的像一致，记住这个现象，对下一张图的理解有帮助。

因此，在本例中，我们选择一个素数 p = 1000,005,001，其满足：

• 为素数
• p – 1 能被 1000 整除
• p 要大于 10^9

因此，在有限域 p 内，x => x^1000 的像在 p 内有(p -1) / 1000 = 1000005个，因此图 4 可以变成图 6 的形式：

可以看出，列坐标变成了 10^6 个元素，对角线变成了平行的线条，总共有 1000 个。还记得上面费马小定理结论的特殊现象吗？这就是对角线这种分布的原因，读者试着去理解(可能读者会觉得，对角线应该是锯齿形，不是这种平行的形式，也许你是对的，但是这并不影响验证流程)。此时证明者的复杂度已经从 10^18 减少到了 10^15 次方，证明和验证过程和步骤 3 描述的仍然一致。

1. 还能不能继续优化呢？答案是肯定的。回想起前面所述的验证过程，对于每一行/列，验证者都要获取 1000 个点进行插值得出一个度小于 1000 的多项式，仔细观察图 6，对于每一行，原始数据里不就是有 1000 个数么？那我们干脆选这些点插值出一个度小于1000 的多项式，然后只需要随机让证明者再计算任何一列，并且证明沿着列上的点都在度小于 1000 的多项式上，并且列上的点也在对应的利用原始数据插值出的行多项式上。此时，证明者复杂度从 10^15 减少到了 10^9 次方。
2. 总结：个人理解，从步骤 1 到步骤 5，其实是 PCP 到 IOP 的选择过程。 a. PCP 要求证明者生成全部的证据，然后验证者多次随机选取其中的某一部分进行验证，但是这样，证明者的复杂度仍然很高； b. IOP 要求证明者不用生成全部的证据，根据多次的交互，每次生成只需生成部分证据，使得证明的复杂度和 D 呈近似线性关系；
3. 证明者复杂度已经降低到了与 D 呈拟线性关系，验证者的复杂度虽然是亚线性，交互次数已经低于 D，但是能不能优化到更低呢？基于证明复杂度的最优设置，我们继续探索验证复杂度的优化之路，回顾 P(x) = x + x^999 + x^1001 + x^999999 = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)499999，令G(x, y) = x + xy^499 + xy^500 + xy^499999，则当 y = x^2时，有 G(x, y) = G(x, x^2) = x + x*(x^2)^499 + x*(x^2)^500 + x*(x^2)*499999 = P(x)。

最终的图应如下图 7 所示：

从图中可知：

• 证明则复杂度仍为 10^9 次方；
• 每一行上的点都在度 d < 2 的多项式上，因为当 y 取固定值时，G(x, y)就是关于 x 的一次多项式；
• 每一列上的点都在度 d < D/2 的多项式上，证明者需要证明这个多项式是小于 D/2 的，假定这个多项式为 P1(x)，这个时候，并非验证者选取大于 D/2 个点去验证，因为验证复杂度仍然不够低，而是对这一列再一次用到类似于 P(x) 的处理过程，如图7中下面的图所示，以此循环，直到可以直接判断列上的多项式的度为止，类似于行。

总结

至此，本篇文章就结束了，总结下来，本文主要阐述了以下几个内容：

• 如何转换问题形式 — Arithmetization
• 为何需要 LDT — 为了验证简洁
• LDT 的大概过程 — 二分法验证，类似于 FFT
• 降低 LDT 的复杂度 — 有限域 +IOP