从图3可以看出，需要验证的多项式的个数是5个(赤色圈4所示)，假如对每一个多项式都举办LDT，那么耗损是很庞大的，因此，可以通过将这些多项式举办线性组合(赤色圈5所示)，当且仅当每个多项式都满意小于某个度时，其线性组合后的多项式也是小于某个度的，这个条件时充实的，详细的细节见后续的系列章节。
存在这样一类问题。当验证者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)的度小于某个牢靠值的呢？这些问题将在下一篇文章中给出谜底，在此之前，不如先接头一下，为何多项式的度小于某个牢靠值就能证明原始执行轨迹是正确的呢？
Arithmetization就是把CI statement转化成正式的Algebraic language的进程，此步调有两个目标：第一，把CI statement以简捷清晰的方法泛起出来；第二，把CI statement嵌入到代数域，为后头多项式的转换做铺垫。Arithmetization representation主要由两部门构成：第一，执行轨迹（图中橙色部门）；第二，多项式约束（图中灰色部门）。
回首
执行轨迹是一个表，表的每一行代表一个单步的运算；多项式约束的结构是和执行轨迹相辅相成的，即当前仅当执行轨迹是正确的，多项式约束会满意执行轨迹的每一行计较。最后把执行轨迹和多项式约束团结构成一个确定的多项式，然后对多项式举办LDT验证。至此，验证CI statement的问题转换成了验证确定性多项式LDT的问题。
按照已知事实，度为d的多项式H(x)在x = n处为0，则存在一个度为d-1的多项式H`(x)，满意 d(H`(x)) = d(H(x)) – 1 && H(x) = H`(x) * (x – n)
· 多项式的巨细和执行轨迹的谜底小没有干系，即表格的长度纵然扩大到1000000，最终的多项式约束仍是这三个，独一变革的是变量x的取值范畴罢了。
从图2可以看出：
从以上的例子中，可以看出，当且仅当执行轨迹是正确的时候，Q(x)才会在x 取值为 1、2、3、4、5时，便是0。那么Q(x)才可以被方针多项式T(x)整除，即：Ψ(x) = Q(x) / T(x) ，d(Ψ(x)) = d(Q(x)) – 5。
下面，让我们用上面简朴的例子，跟从Bob去寻找这个牛掰的步伐。
此刻，好莱坞人气演员Bob声称：”the total sum we should pay at the supermarket was computed correctly”。那怎么验证呢？其实很简朴，这时另一小我私家气演员Alice只要对着收据，每一项累加求和就可以完成验证。那么，这只是一个很简朴的例子，事实上，Alice只需要5步，就可以完成验证进程。
新增的一列值需要满意，初始化的值为0（图2中黄色部门）、最终的值和要付的总和相等（图2中黄色部门）、中间的每一个值都要便是上一个值加上上一行物品的单价（图2中红线部门），这组成了多项式约束（图1灰色部门，图2左下角部门）。
知道了Arithmetization的整体流程，接下来，，我们接头下详细的进程。为了便于领略，我们用一个简朴的例子，来贯串整个Arithmetization的进程。
每小我私家都去过超市，一般超市的收据的内容如下：假如等式创立，则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首先把存眷点切到执行轨迹，可以看到执行轨迹有2列，一列是单项价值，一列是价值总和，我们别离对两列的元素举办拉格朗日插值，获得两个函数 f(x), w(x)，0≤x≤5。别离对两个函数举办域扩展，获得了在更多的点上的评估，即f(x)，w(x) ，0≤x≤10000（从多项式插值，到域扩展，这其实就是Reed-Solomen的编码进程，它可以实现，原始数据哪怕有一处差别，获得的码字会大不沟通；主要目标用于防备证明者作恶，插手证明者作恶，会使得验证者很容易发明）。
可是有一个配合方针就是，无论是什么问题，获得的执行轨迹最好是用一个LOOP就可以暗示，这样获得的多项式约束也就最为简捷。多项式约束的个数和形式直接影响到了proof的巨细和Zk-stark算法的机能，因此，寻找一个最优的配置对付Zk-stark算法显得尤为重要。
w(a) – f(a – 1) – w(a – 1) = Ψ(a) * T(a) (3)
1 ≤ x ≤ 5 w(x) – f(x -1) – w(x -1) = 0 (1)
因此对付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，则有：
首先，什么是Arithmetization？
验证者Alice从0≤x≤10000随机选择一点a，发送给证明者Bob，要求Bob返回相应的值，以公式(2)为例，Bob需要返回w(a)、w(a-1)、f(a-1)、Ψ(a)，然后Alice判定等式是否创立，即：
那什么是Arithmetization？详细进程又是什么呢？带着这些疑问，让我们仔细的咀嚼文章后头的内容。 Arithmetization的整体步调如下图所示：
本系列的第一篇文章（技能指南 | 领略零常识证明算法之Zk-stark），以Zk-snark做比较，别离从观念和算法流程上，做了归纳综合性的先容。发起在阅读本篇文章之前，先阅读下第一篇文章的内容。本篇文章，让我们由浅入深，一起踏上摸索Zk-stark算法机密的旅途。
下面，我们讲接头如何增加零常识属性。
接待品评指正，感谢！！
Q(x) = Ψ(x) * T(x) (2)
在这里，借用V神的话来描写一下Zk-stark：Zk-Stark不是一个确定性的算法，它是一大类暗码和数学布局，对付差异的应用，具有差异的最优配置。可以领略为，对付差异的问题，具有差异的算术化的方案（在本例中，是加一列值，在其他案例中就不必然合用了），因此要做到详细问题详细阐明。
· 多项式约束总共有3个，两个是界线约束（多项式索引1&3），一个是轮回约束（多项式索引2）；
在第一篇的文章中讲到，Zk-stark算法概略可以分为两个部门：Arithmetization 和 Low Degree Testing。本篇我们先具体先容算法的第一阶段Arithmetization。
附录
回归到主题，此刻Bob已经获得了多项式约束和执行轨迹，那么如何把它们转换成一个确定的多项式呢？请看下图：（蓝色箭头代表主流程，赤色箭头代表分支）
媒介
1. 官方先容文档：https://medium.com/starkware/arithmetization-i-15c046390862
试想这样一个场景：究竟Bob很有钱，在超市买了1000000样对象，同样，他又声称：”the total sum we should pay at the supermarket was computed correctly”，这时候，Alice真的生气了，这怎么验证，凭据之前的步伐，得约莫要算1000000步，闹呢？谁爱干谁干。Bob心里也心疼Alice，究竟那么多年了。心想，有没有什么牛掰的步伐能让Alice用很少的步调，就能确信我说的是对的呢？于是，Bob开动了最强大脑模式。
Bob心想，你不就是验证最终的总和对差池么？那我就把总和的计较进程列出来，我担保每次的累加都对，那么我最终的功效必然也是对的。于是Bob在收据上新增了一列，用来生存计较总和进程中的中间值（图中橙棕色部门标注），这就是执行轨迹（图1中的橙色部门）。
Arithmetization
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
