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

ZKSwap团队解读零知识证明算法之(六)Zk-stark:Arithmetization

前言

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

回顾

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

ZKSwap团队解读零知识证明算法之(六)Zk-stark:Arithmetization

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

首先,什么是 Arithmetization?

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

Arithmetization

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

ZKSwap团队解读零知识证明算法之(六)Zk-stark: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 去寻找这个牛掰的办法。

ZKSwap团队解读零知识证明算法之(六)Zk-stark:Arithmetization

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 已经得到了多项式约束和执行轨迹,那么如何把它们转换成一个确定的多项式呢?请看下图:(蓝色箭头代表主流程,红色箭头代表分支)

ZKSwap团队解读零知识证明算法之(六)Zk-stark:Arithmetization

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 所示),当且仅当每个多项式都满足小于某个度时,其线性组合后的多项式也是小于某个度的,这个条件时充分的,具体的细节见后续的系列章节。

赞(0) 打赏
转载请注明出处:okex交易所官网 » ZKSwap团队解读零知识证明算法之(六)Zk-stark:Arithmetization
分享到: 更多 (0)

评论 抢沙发

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

okex网注册教程和交易流程

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

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

支付宝扫一扫打赏

微信扫一扫打赏