欢迎光临
OKEX交易所使用教程

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

前言

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

新的实例

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

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

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

  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 所示:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

图中:紫色的点为随机生成的点 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 表示:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

可以看出,如果 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 所示:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

验证者把所有的点都计算好(没错,总共 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 为例:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

图中,红色为 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 的形式:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

可以看出,列坐标变成了 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 所示:

ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing

从图中可知:

  • 证明则复杂度仍为 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
赞(0) 打赏
转载请注明出处:okex交易所官网 » ZKSwap团队深入解读零知识证明算法之Zk-stark(七):Low Degree Testing
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

okex网注册教程和交易流程

联系QQ:87300288数字货币QQ交流群

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏