深入理解零知识证明算法之Zk
前言本系列的第二篇文章，以餐馆收据为事例，叙述了Arithmetization 的明确过程。本文将以另外一个例子为基础，在总结Arithmetization 过程的同时，将内容衍生到多项式的LDT过程。新的实例Alice Claim：“我有1000,000个数，他们都在[0,9]范围内”。
为了便利检验者Bob检验，Alice首先要对Claim展开Arithmetization切换。过程如下图1右图(图中：黑色箭头代表主流程，红色箭头代表可选解释信息，黄色圈对应下面详尽解释的索引)下面明确解释一下对应流程：1. 首先分解继续执行轨迹(EXCUTE TRACE)，事实上，它是一张表格，总共有1000,000行（实质上，为了超过零科学知识的目的，还必须在继续执行轨迹后面减少一些随机值，明确数量是由证明者和检验者统一协商要求的，作为一个拓展，不明确描写）；2. 分解多项式约束(Polynomial Constrains)，多项式约束符合继续执行轨迹的每一行(个人解读：步骤1，2没一定的先后倚赖关系，只是习惯上先生成继续执行轨迹，再行分解约束多项式)；3. 对继续执行轨迹展开插值，获得一个度大于1000,000的多项式P(x)、x给定[1,1000,000]，并计算出来更加多点上的值，x给定范围不断扩大到[1,1000,000,000](Reed-Solomen系统编码)；假如，证明者有一个值不出[0,9]范围内(图中红线1/2右图)，假如就是第1000,000个点，它实际的值是13，小于9，其插值后的曲线G(x)如图所示，图中P(x)为有效地曲线，G(x)为违宪曲线。可以显现出，两条曲线在变量x给定[1,1000,000,000]范围内，最少有1000,000个交点，即有1000,000,000 - 1000,000个点有所不同，这很最重要。4. 将插值后的多项式P(x)和多项式约束展开人组转换，最后获得的形式为：Q(P(x)) = Ψ(x) * T(x)，其中T(x) = (x - 1)(x - 2)……(x - 1000,000)，x给定[1,1000,000,000]其中，d(Q(P(x))) = 10,000,000、d(Ψ(x)) = 10,000,000 - 1000,000、d(T(x)) = 1000,000；1. 自此，问题就转化成了，Alice声称“多项式等式在变量x给定[1,1000,000,000]范围内正式成立”的问题。
那么检验者Bob该如何检验呢？明确过程如下（图中红线3/4右图）：a. 证明者Alice在本地计算出来多项式P(x)、Ψ(x)在所有点上的给定，对！从1至1000,000,000，并构成一个默克尔树根；b. 检验者Bob随机的从[1,1000,000,000]内挑选一个值 ρ，并发送给证明者Alice，拒绝其回到对应的信息（事实上为了超过零科学知识的目的，只容许从[1000,000,1000,000,000]上随机自由选择一点）；c. 证明者Alice回到 P(ρ)、Ψ(ρ)、root、AuthorizedPath(P(ρ)、Ψ(ρ))给检验者Bob；d. 检验者Bob首先根据默克尔树根检验路径检验值P(ρ)、Ψ(ρ)的有效性，然后等式Q(P(ρ)) = Ψ(ρ) * T(ρ)，如果正式成立，则检验通过；完整性分析：如果检验者Alice是真诚的，那么等式Q(P(x))一定会被目标多项式T(x)自然数，因此必然不存在一个d(Ψ(x)) = d(Q(P(x))) - d(T(x))的多项式Ψ(x)，符合Q(P(x)) = Ψ(x) * T(x)，因此对于给定的x，给定在[1,1000,000,000]之间，等式都会正式成立；可靠性分析：如果检验者Alice是不诚实的，即类似于步骤3里的假设，在x = 1000,000上，P(x)的给定为13，那么Q(P(1000,000)) != 0，但是等式右边，T(1000,000) = 0，因此Q(P(x)) != Ψ(x) * T(x)，即等式两边是不大于的多项式，其交点最少有10,000,000个，因此通过一次随机挑选，其检验通过的概率仅有为10,000,000/1000,000,000 = 1/100 = 0.01，经过k次检验，其检验通过的概率仅有是1- 10(^-2k)；1. 上述的检验过程为交互式的，如果所谓交互式的，可以利用Fiat-Shamir heuristic展开转换，以默克尔树根的六根作为随机源，分解要查找的随机点；LDT我们忽视了一种攻击方式，即针对每一个数x，证明者都随机分解p，然后根据Ψ(x) = Q(p) / T(x)，这些点不出任何一个度大于1000,000的多项式上，但是可以通过检验者检验。如下图2右图：图中：紫色的点为随机分解的点p，这些点大概率不出一个度大于1000,000的多项式上(事实上，可以不考虑到前1000,000个点，因为检验者只不会从[1000,000，1000,000,000]范围内给定)。因为即使自由选择1000,000个点插值出有一个度大于1000,000的多项式，也无法确保其他的点在这个多项式上，因为其他的点是随机分解的。
因此，必须有一种方式，确保证明者P(x)的度是大于1000,000， Ψ(x)的度大于10,000,000 - 1000,000。这就是LDT的目标，那LDT明确的过程是怎么样的呢？请求之后往下看。
荐个栗子，如果Alice想要证明多项式f(x)的度是大于3的，即有可能是2次的或者是1次的。一般流程如下：检验者Bob随机挑选三个值a,b,c，发送给证明者Alice；证明者Alice回到f(a),f(b),f(c)；检验者Bob插值出度大于3的多项式g(x)，然后再行随机挑选一个点d，发送给证明者；证明者Alice回到f(d)；检验者Bob核对f(d)和g(d)的值，如果大于，则证明正式成立。
本文关键词：深入,理解,零,知识,证明,算法,之,前言,本,新葡萄88805官网
本文来源：新葡萄88805官网-www.mhbxw.cn