前言据悉，atis阿蒂斯的数据表现越来越好，极具参考价值，很可能成为行业的风向标。
本系列的第二篇文章，以超市收据为例，描述了a 的具体过程。本文将以另外一个例子为基础，在回顾a 过程的同时，将内容引......
前言
本系列的第二篇文章，以超市收据为例，描述了a 的具体过程。本文将以另外一个例子为基础，在回顾a 过程的同时，将内容引申到多项式的ldt过程。
新的实例
a c：“我有,个数，他们都在[,]范围内”。为了方便验证者b验证，a首先要对c进行a转换。过程如下图所示(图中：黑色箭头代表主流程，红色箭头代表附加说明信息，黄色圈对应下面详细说明的索引)
下面具体说明一下对应流程：
. 首先生成执行轨迹(excute trace)，事实上，它是一张表，总共有,行（实际上，为了达到零知识的目的，还需要在执行轨迹后面增加一些随机值，具体数量是由证明者和验证者统一协调决定的，作为一个扩展，不具体讲述）；
. 生成多项式约束(p c)，多项式约束满足执行轨迹的每一行(个人理解：步骤，没有一定的先后依赖关系，只是习惯上先生成执行轨迹，再生成约束多项式)；
. 对执行轨迹进行插值，得到一个度小于,的多项式p()、取值[,,]，并计算更多点上的值，取值范围扩大到[,,,](r-s系统编码)；假如，证明者有一个值不在[,]范围内(图中红线/所示)，假如就是第,个点，它实际的值是，大于，其插值后的曲线g()如图所示，图中p()为有效曲线，g()为无效曲线。可以看出，两条曲线在变量取值[,,,]范围内，最多有,个交点，即有,, - ,个点不同，这很重要。
. 将插值后的多项式p()和多项式约束进行组合变换，最终得到的形式为：
q(p()) = ψ() * t()，其中t() = ( - )( - )……( - ,)，取值[,,,]
其中，(q(p())) = ,,、(ψ()) = ,, - ,、(t()) = ,；
. 至此，问题就转化成了，a宣称“多项式等式在变量取值[,,,]范围内成立”的问题。那么验证者b该如何验证呢？具体过程如下（图中红线/所示）：
. 证明者a在本地计算多项式p()、ψ()在所有点上的取值，对！从至,,，并形成一个默克尔树；
. 验证者b随机的从[,,,]内选取一个值 ρ，并发送给证明者a，要求其返回对应的信息（事实上为了达到零知识的目的，只允许从[,,,,]上随机选择一点）；
. 证明者a返回 p(ρ)、ψ(ρ)、、ap(p(ρ)、ψ(ρ))给验证者b；
. 验证者b首先根据默克尔树验证路径验证值p(ρ)、ψ(ρ)的有效性，然后等式q(p(ρ)) = ψ(ρ) * t(ρ)，如果成立，则验证通过；
完整性分析：如果验证者a是诚实的，那么等式q(p())一定会被目标多项式t()整除，因此必定存在一个(ψ()) = (q(p())) - (t())的多项式ψ()，满足q(p()) = ψ() * t()，因此对于任意的，取值在[,,,]之间，等式都会成立；
可靠性分析：如果验证者a是不诚实的，即类似于步骤里的假设，在 = ,上，p()的取值为，那么q(p(,)) != ，但是等式右边，t(,) = ，因此q(p()) != ψ() * t()，即等式两边是不相等的多项式，其交点最多有,,个，因此通过一次随机选取，其验证通过的概率仅为,,/,, = / = .，经过次验证，其验证通过的概率仅是- (^-)；
. 上述的验证过程为交互式的，如果是非交互式的，可以利用f-s 进行变换，以默克尔树的根作为随机源，生成要查询的随机点；
ldt
我们忽略了一种攻击方式，即针对每一个数，证明者都随机生成，然后根据ψ() = q() / t()，这些点不在任何一个度小于,的多项式上，但是可以通过验证者验证。如下图所示：
图中：紫色的点为随机生成的点，这些点大概率不在一个度小于,的多项式上(事实上，可以不考虑前,个点，因为验证者只会从[,，,,]范围内取值)。因为即使选择,个点插值出一个度小于,的多项式，也不能保证其他的点在这个多项式上，因为其他的点是随机生成的。因此，需要有一种方式，保证证明者p()的度是小于,， ψ()的度小于,, - ,。这就是ldt的目标，那ldt具体的过程是怎么样的呢？请继续往下看。
举个栗子，如果a想证明多项式()的度是小于的，即有可能是次的或者是次的。一般流程如下：
验证者b随机选取三个值,,，发送给证明者a；
证明者a返回(),(),()；
验证者b插值出度小于的多项式()，然后再随机选取一个点，发送给证明者；
证明者a返回()；
验证者b比对()和()的值，如果相等，则证明成立。
回归到一般情况，其过程可以用下图表示：
可以看出，如果d很大，a和b交互的次数则为d+次，复杂度很高；有没有一种办法，使得两者之间交互的次数小于d的情况下，使得验证者相信多项式的度是小于d的，直接返回小于d个点肯定是不行的，因为那不能唯一确定一个度小于d的多项式，因此需要证明者需要额外发送一些辅助信息。
下面我们以p()为例，详细阐述这个过程(事实上，应该是证明p()和ψ()的线性组合小于,, - ,，本文重点是ldt，因此只以p()为例，这并不影响对ldt的理解)。
. 假如p() =+ ^ + ^ + ^ =+ ^ +* ^ + ^*(^)^;
. 此时，我们找到一个二维多项式g(, )，取值范围分别是[, ]、[, ]，满足：
. g(, ) =+ ^ + *+ ^*^ 可以发现，当 = ^时，满足：
. g(, ) = g(, ^) =+ ^ +* ^ + *(^)^ = p()
. 如果我们能证明g(, )相对的,的最高度都是小于，因为p() = g(, ^)上，因此可以相信p()的度小于,；
如图所示：
验证者把所有的点都计算好（没错，总共^个点，吓死bb了），形成一颗默克尔树。验证者随机选择一行和一列，如图中红线/所示，对于每一列，它是由关于的度小于的多项式生成，对于每一行，它是由关于的度小于的多项式生成。验证者从行/列中随机选择个点，用来验证对应行/列上的点是否在度小于的多项式上，需要注意的是，因为p()的点都在上图的对角线上，因此我们要确保每一行/列对应的对角线上的点也在对应的度小于的多项式上，即个里面一定要包含对角线的点。
可靠性分析：如果原始多项式的度实际上是小于^ +，即 p() =+ ^ + ^ + ^ ，那么对应的g(, )为g(, ) =+ ^ + *+ ^*^ ，即，对于每一个，g(, )是关于的一元多项式函数，且度 &; ，因此下图中的每一列所有点都是在度 &; 的多项式上，而不在 &; 的多项式式上。所以如果证明者任然宣称多项式p()的度 &; , ，则会验证失败，其他场景是同样的道理
那有没有可能恶意证明者仍以g(, ) =+ ^ + *+ ^*^ 的形式去生成证据呢？这样会验证通过吗？
我们知道，我们在验证时着重强调了对角线上的那一点一定要在多项式上，我们知道，此时对角线对应的多项式形式是
p() =+ ^ ++ ^ ，而实际的p()，我们在这里标记为p`() ，其形式是：
p`() =+ ^ + ^ + ^
因此，如果验证者恰好选择的点是两个多项式的交点，则会验证通过，事实上，两个多项式最多有, 左右个交点，但是由于随机选取的点不是证明者自己选取，是由默克尔树的根为种子随机生成，因此证明者没有机会作恶，去可以选取那些能通过验证的点。
由于总共由^个点，因此随机选取一个点，能验证成功的概率为^ / ^ = ^(-)，如果选择行，则成功的概率仅为^(-)。
以上可以看出，验证者和证明者只需要交互 ** 个点，就可以完成验证，假如 = ，则 **=&;&; ^。
. 虽然上述实现了在交互次数小于d的情况下，完整ldt验证，但是证明者的复杂度过于庞大，至少^的复杂度远远大于原始的计算，因此需要一些优化方案，降低复杂度。话不多说，直接引入有限域，毕竟在实际项目中，我们可不希望数值本身过于庞大。直接引用费马小定理的结论：在有限域内，如果满足( - ) 能被整除，则映射 =&; ^的像只有( -) /+ 个。下图以 = ，映射=&; ^为例：
图中，红色为^在有限域内的象，总共由( - ) / += 个。同时我们可以发现，^和^的像一致，^和^的像一致，以此类推，^和^的像一致，记住这个现象，对下一张图的理解有帮助。
因此，在本例中，我们选择一个素数 = ,,，其满足：
为素数
-能被整除
要大于^
因此，在有限域内， =&; ^的像在内有( -) /= ,个，因此图可以变成图的形式：
可以看出，列坐标变成了^个元素，对角线变成了平行的线条，总共有个。还记得上面费马小定理结论的特殊现象吗？这就是对角线这种分布的原因，读者试着去理解(可能读者会觉得，对角线应该是锯齿形，不是这种平行的形式，也许你是对的，但是这并不影响验证流程)。此时证明者的复杂度已经从^ 减少到了^次方，证明和验证过程和步骤描述的仍然一致。
. 还能不能继续优化呢？答案是肯定的。回想起前面所述的验证过程，对于每一行/列，验证者都要获取个点进行插值得出一个度小于的多项式，仔细观察图，对于每一行，原始数据里不就是有个数么？那我们干脆选这些点插值出一个度小于的多项式，然后只需要随机让证明者再计算任何一列，并且证明沿着列上的点都在度小于的多项式上，并且列上的点也在对应的利用原始数据插值出的行多项式上。此时，证明者复杂度从^减少到了^次方。
. 总结：个人理解，从步骤到步骤，其实是pcp到iop的选择过程。
. pcp要求证明者生成全部的证据，然后验证者多次随机选取其中的某一部分进行验证，但是这样，证明者的复杂度仍然很高；
. iop要求证明者不用生成全部的证据，根据多次的交互，每次生成只需生成部分证据，使得证明的复杂度和d呈近似线性关系；
证明者复杂度已经降低到了与d呈拟线性关系，验证者的复杂度虽然是亚线性，交互次数已经低于d，但是能不能优化到更低呢？基于证明复杂度的最优设置，我们继续探索验证复杂度的优化之路，回顾p() =+ ^ + ^ + ^ =+ *(^)^ + *(^)^ + *(^)*，令g(, ) =+ *^ + *^ + *^，则当 = ^时，有g(, ) = g(, ^) =+ *(^)^ + *(^)^ + *(^)* = p()。
最终的图应如下图所示：
从图中可知：
· 证明则复杂度仍为^次方；
· 每一行上的点都在度 &; 的多项式上，因为当取固定值时，g(, )就是关于的一次多项式；
· 每一列上的点都在度 &; d/的多项式上，证明者需要证明这个多项式是小于d/的，假定这个多项式为p()，这个时候，并非验证者选取大于d/个点去验证，因为验证复杂度仍然不够低，而是对这一列再一次用到类似于p()的处理过程，如图中下面的图所示，以此循环，直到可以直接判断列上的多项式的度为止，类似于行。
总结
至此，本篇文章就结束了，总结下来，本文主要阐述了以下几个内容：
如何转换问题形式 -- a
为何需要ldt -- 为了验证简洁
ldt的大概过程 -- 二分法验证，类似于fft
降低ldt的复杂度 -- 有限域+iop
至于ldt的详细过程，将留给本系列的最后一篇，敬请关注。