ZKSwap 团队解析零常识证明算法之 Zk-STARK (二): Arithmetization
本文摘要:撰文:ZKSwap菜鸟前言本系列的第一篇文章,以Zk-snark做对照,分别从定义和算法步骤上,做了概括性的介绍。

Q = Ψ * T

验证者 Alice 从 0≤x≤10000 随机选择一点 a,发送给证明者 Bob,需要 Bob 返回相应的值,以公式 为例,Bob 需要返回 w、w、f、Ψ,然后 Alice 判断等式是不是成立,即:

撰文:ZKSwah3 菜鸟

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 可以看出:

在这里,借用 V 神的话来描述一下 Zk-stark:Zk-Stark 不是一个确定性的算法,它是一大类密码��数学结构,对于不一样的应用,具备不一样的最佳设置。可以理解为,对于不一样的问题,具备不一样的算术化的策略(在本例中,是加一列值,在其他案例中就不肯定适用了),因此要做到具体问题具体剖析。但有一个一同目的就是,无论是那些问题,得到的实行轨迹最好是用一个 LOOP 就可以表示,如此得到的多项式约束也就最为简单。多项式约束的个数和形式直接影响到了 proof 的大小和 Zk-stark 算法的性能,因此,探寻一个最佳的设置对于 Zk-stark 算法看上去非常重要。 回归到主题,目前 Bob 已经得到了多项式约束和实行轨迹,那样怎么样把它们转换成一个确定的多项式呢?请看下图:(蓝色箭头代表主步骤,红色箭头代表分支)

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

然后,Bob 把 f,w 和多项式约束等式结合,得到一组确切的多项式约束 ,以循环约束多项式为例:

w – f – w = Ψ * T

假如等式成立,则 Alice 大概率相信实行轨迹是正确的,那样原始计算成立。倘若验证者 Bob 作恶,讲表格中的 4.98 改成 5.98 把,那样 Q = w – w – f = 5.98 – 0 – 4.98 = 1,不等于 0。在这样的情况下,察看公式 ,等式右侧为 Q,度为 5,x = 1 不是零点;等式右边 Ψ * T ,令 G = Ψ * T,度为 5,由于 T 在 x = 1 处是零点,所以 G 在 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、w、f、Ψ 是多项式 w、f、Ψ 分别在 x = a AMPLAMPL x = a – 1 上的取值呢,且多项式 w、f、Ψ 的度小于某个固定值的呢?这部分问题将在下一篇文章中给出答案,在此之前,不如先讨论一下,为什么多项式的度小于某个固定值就能证明原始实行轨迹式正确的呢?

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

从图 3 可以看出,需要验证的多项式的个数时 5 个 ,假如对每个多项式都进行 LDT,那样消耗是非常巨大的,因此,可以通过将这部分多项式进行线性组合 ,当且仅当每一个多项式都满足小于某个度时,其线性组合后的多项式也是小于某个度的,这个条件时充分的,具体的细则见后续的系列章节。

出处链接:zks.org

第一,啥是 Arithmetization?

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

1 ≤ x ≤ 5 w – f – w = 0

令 Q = w – f – w,则有 Q = 0、Q = 0、Q = 0、Q = 0、Q = 0。

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

因此对于 Q,度为 5,存在一个多项式 Ψ,度为 0,即常量,满足 Q = Ψ * ,令目的多项式 T = ,度为 5,则有:

回顾

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

那啥是 Arithmetization ?具体过程又是什么呢?携带这部分疑问,让大家仔细的品味文章后面的内容。

前言

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