前言在一些情况下，阿蒂斯atis的优势会越发的明显起来，经过市场检验也能够一往无前的发展下去。
本系列的第一篇文章（技术指南 | 理解零知识证明算法之z-），以z-做对照，分别从概念和算法流程上，做了概括性的介绍。建议在阅读本......
前言
本系列的第一篇文章（技术指南 | 理解零知识证明算法之z-），以z-做对照，分别从概念和算法流程上，做了概括性的介绍。建议在阅读本篇文章之前，先阅读下第一篇文章的内容。本篇文章，让我们由浅入深，一起踏上探索z-算法奥秘的旅途。
回顾
在第一篇的文章中讲到，z-算法大体可以分为两个部分：a 和 l d t。本篇我们先详细介绍算法的第一阶段a。
a的整体步骤如下图所示：
那什么是a？具体过程又是什么呢？带着这些疑问，让我们仔细的品味文章后面的内容。
首先，什么是a？
a就是把ci 转化成正式的a 的过程，此步骤有两个目的：第一，把ci 以简洁清晰的方式呈现出来；第二，把ci 嵌入到代数域，为后面多项式的转换做铺垫。a 主要由两部分组成：第一，执行轨迹（图中橙色部分）；第二，多项式约束（图中灰色部分）。
执行轨迹是一个表，表的每一行代表一个单步的运算；多项式约束的构造是和执行轨迹相辅相成的，即当前仅当执行轨迹是正确的，多项式约束会满足执行轨迹的每一行计算。最后把执行轨迹和多项式约束结合组成一个确定的多项式，然后对多项式进行ldt验证。至此，验证ci 的问题转换成了验证确定性多项式ldt的问题。
a
知道了a的整体流程，接下来，我们讨论下具体的过程。为了便于理解，我们用一个简单的例子，来贯穿整个a的过程。
每个人都去过超市，一般超市的收据的内容如下：
现在，好莱坞人气演员b声称：" "。那怎么验证呢？其实很简单，这时另一个人气演员a只要对着收据，每一项累加求和就可以完成验证。那么，这只是一个很简单的例子，事实上，a只需要步，就可以完成验证过程。
试想这样一个场景：毕竟b很有钱，在超市买了样东西，同样，他又声称：" "，这时候，a真的生气了，这怎么验证，按照之前的办法，得大约要算步，闹呢？谁爱干谁干。b心里也心疼a，毕竟那么多年了。心想，有没有什么牛掰的办法能让a用很少的步骤，就能确信我说的是对的呢？于是，b开动了最强大脑模式。
下面，让我们用上面简单的例子，跟随b去寻找这个牛掰的办法。
b心想，你不就是验证最终的总和对不对么？那我就把总和的计算过程列出来，我保证每次的累加都对，那么我最终的结果一定也是对的。于是b在收据上新增了一列，用来保存计算总和过程中的中间值（图中橙棕色部分标注），这就是执行轨迹（图中的橙色部分）。
新增的一列值需要满足，初始化的值为（图中黄色部分）、最终的值和要付的总和相等（图中黄色部分）、中间的每一个值都要等于上一个值加上上一行物品的单价（图中红线部分），这构成了多项式约束（图灰色部分，图左下角部分）。
从图可以看出：
· 多项式约束总共有个，两个是边界约束（多项式索引&;），一个是循环约束（多项式索引）；
· 多项式的大小和执行轨迹的答案小没有关系，即表格的长度即使扩大到，最终的多项式约束仍是这三个，唯一变化的是变量的取值范围而已。
在这里，借用v神的话来描述一下z-：z-s不是一个确定性的算法，它是一大类密码和数学结构，对于不同的应用，具有不同的最优设置。可以理解为，对于不同的问题，具有不同的算术化的方案（在本例中，是加一列值，在其他案例中就不一定适用了），因此要做到具体问题具体分析。
但是有一个共同目标就是，无论是什么问题，得到的执行轨迹最好是用一个loop就可以表示，这样得到的多项式约束也就最为简洁。多项式约束的个数和形式直接影响到了的大小和z-算法的性能，因此，寻找一个最优的设置对于z-算法显得尤为重要。
回归到主题，现在b已经得到了多项式约束和执行轨迹，那么如何把它们转换成一个确定的多项式呢？请看下图：（蓝色箭头代表主流程，红色箭头代表分支）
b首先把关注点切到执行轨迹，可以看到执行轨迹有列，一列是单项价格，一列是价格总和，我们分别对两列的元素进行拉格朗日插值，得到两个函数 (), ()，≤≤。分别对两个函数进行域扩展，得到了在更多的点上的评估，即()，() ，≤≤（从多项式插值，到域扩展，这其实就是r-s的编码过程，它可以实现，原始数据哪怕有一处差异，得到的码字会大不相同；主要目的用于防止证明者作恶，加入证明者作恶，会使得验证者很容易发现）。
然后，b把()，() 和多项式约束等式结合，得到一组确切的多项式约束(图中红色圈所示)，以循环约束多项式为例：
≤≤() - ( -) - ( -) =()
令q() = () - (-) - (-)，则有q() = 、q() = 、q() = 、q() = 、q() = 。
根据已知事实，度为的多项式h()在 = 处为，则存在一个度为-的多项式h`()，满足 (h`()) = (h()) -&;&; h() = h`() * ( - )
因此对于q()，度为，存在一个多项式ψ()，度为，即常量，满足q() = ψ() * ( - )( - )( - )( - )( - )，令目标多项式t() = ( - )( - )( - )( - )( - )，度为，则有：
q() = ψ() * t() ()
验证者a从≤≤随机选择一点，发送给证明者b，要求b返回相应的值，以公式()为例，b需要返回()、(-)、(-)、ψ()，然后a判断等式是否成立，即：
() - ( - ) - ( - ) = ψ() * t() ()
如果等式成立，则a大概率相信执行轨迹是正确的，那么原始计算成立。假如验证者b作恶，将表格中的.改成.，那么q() = () - () - () = . -- . = ，不等于。在这种情况下，观察公式()，等式右边为q()，度为， = 不是零点；等式右侧ψ() * t() ，令g() = ψ() * t()，度为，因为t()在 = 处是零点，所以g()在=处也是点，因此，等式两边实际上是度相等的不同多项式，其交点最多为个，因此在≤≤范围内，只有个值相等，值是不等的，因此随机的从≤≤中选择一个值，验证不通过的概率是.%，如果域扩展的范围更大，则验证不通过的概率将会更接近于。按照同样的逻辑，分别处理边界约束多项式，得到的结果如图所示（图中红色圈所示）。
下面，我们讲讨论如何增加零知识属性。
对于证明者b来讲，执行轨迹是不希望被验证者a看到的，因为它会包含一些重要的信息，因此，限定验证者a只能从≤≤范围内随机选择一个值，进行验证，当然这种限定，双方都是同意的。
存在这样一类问题。当验证者a收到证明者b反馈的值时，如何保证这些值是合法的，确实是通过多项式的形式计算，并且这些多项式是小于某个度的，而不是证明者b仅仅为了验证通过，而生成的随机值？比如如何确保()、(-)、(-)、ψ()是多项式()、()、ψ()分别在 =&;&;=- 上的取值呢，且多项式()、()、ψ()的度小于某个固定值的呢？这些问题将在下一篇文章中给出答案，在此之前，不如先讨论一下，为何多项式的度小于某个固定值就能证明原始执行轨迹是正确的呢？
从以上的例子中，可以看出，当且仅当执行轨迹是正确的时候，q()才会在 取值为 、、、、时，等于。那么q()才可以被目标多项式t()整除，即：ψ() = q() / t() ，(ψ()) = (q()) - 。
从图可以看出，需要验证的多项式的个数是个(红色圈所示)，如果对每一个多项式都进行ldt，那么消耗是很巨大的，因此，可以通过将这些多项式进行线性组合(红色圈所示)，当且仅当每个多项式都满足小于某个度时，其线性组合后的多项式也是小于某个度的，这个条件时充分的，具体的细节见后续的系列章节。
欢迎批评指正，谢谢！！
附录
. 官方介绍文档：:////--
. 官方介绍文档：:////--