Arithmetization是零知识证明算法 可把CI statement转化成Algebraic language

2019-11-25 13:10:48
来源: 腾讯

  【摘要】 前言本系列的第一篇文章(技术指南 | 理解零知识证明算法之Zk-stark),以Zk-snark做对照,分别从概念和算法流程上,做了概括性的介绍。建议在阅读本篇文章之前,

前言

本系列的第一篇文章(技术指南 | 理解零知识证明算法之Zk-stark),以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所示),当且仅当每个多项式都满足小于某个度时,其线性组合后的多项式也是小于某个度的,这个条件时充分的,具体的细节见后续的系列章节。(江小白)