基本都是直接copy的fatcat大神的博客 ，大神牛逼！！！

再次声明，本来打算是写一篇看过那么多文章后，对于ZKP的理解的，但是看了fatcat大神的文章和描述后，发现自己再怎么写都是多余的，只能把大神文章中，对于我来说重要的话copy过来，做个记录，也算是对整个zkp逻辑做个梳理。

一段代码生成零知识证明可以分为代码变成多项式阶段，多项式生成承诺两个阶段。

*第一阶段，简单来说就是把代码转换成 a b = c 三元算式的列表（就是写电路），然后套数据公式把三元算式的列表转换成多项式，然后用R1CS&QAP的方式对多项式进行约束；**

第二阶段，先是通过f(x) = h(x)t(x)方程得到zkp的精髓，然后通过同态加密加密随机挑战s的值，然后通过KEA算法引入alpha和双线性映射对保证prover按照规定计算方式计算，而不是拿随机数作恶；然后再通过restup过程生产出s和alpha的同态加密值（因为(g^i)^j的i,j的计算特性，所以会把s，alpha的同态谜加密后的数都计算出来，即：g^0.......g^n； n是多项式的degree，即多项式最大幂），然后再把s，alpha彻底销毁掉，因为verify需要s，alpha，为了解决这个矛盾，就需要利用双线性映射对； 所以在setup阶段，就可以根据f(s), h(s), t(s) 得到一对key。就是proving key和verificaton key。虽然这两个key prover都可以得到，但是prover还是无法作恶，必须乖乖的按照f(x) 【就是知识】原来的多项式一步一步的计算，得到的结果 verfication key才会验证通过；【感觉好绕脑子，直接看结论，完全不符合直觉】

阶段一：代码生成多项式的方法如下（plonk算法）

DAS（数据可用性抽样）和代码等不同的源数据，转换成多项目的方法有一点点不一样，我的理解是都会用到FFT（快速傅立叶变换）；

要想用零知识证明去证明某个东西，我们首先要拥有一个多项式；而这个多项式就是我们要证明的东西的等价转换。那么如何等价转换呢？其实主要分两步：

1. 将要证明的计算过程用数学的方式表示
2. 将这种「数学的表示方式」等价转换成多项式

理论上是有第 1 步的，但现实中已经存在一些零知识证明的框架，并不需要我们特意的去做第 1 步。第 2 步就更不需要我们自己做了，只要用框架提供的方式去写约束代码，框架自己会将约束转换成多项式。（所谓约束代码，是类似「 a * b 必须等于 c 这种」表达方式，我们以后的文章会详细介绍，这里可以先不用过多关注）

这篇文章里，我们只关注第 2 步，即如何用多项式表达问题的「数学的表示方式」。但有可能在不是很理解第 1 步到底是个什么的情况下，我们直接进入到第 2 步，会有一些不踏实，所以这里我们就通过一个简单的例子了解一下。

1. 把代码转换成一系列 a * b = c 三元算式的形式（程序逻辑转换成数学运算）

比如我们有以下一个 rust 函数：

fn foo(w: bool, a: i32, b: i32) -> i32 {
    if w {
        return a * b
    } else {
        return a + b
    }
}

2. 数学运算转换成多项式

一个问题是，如何找到符合上面要求的多项式呢？数学上有很多方法，比如解方程组法；但最常用的还是拉格朗日插值法（Lagrange polynomials）和快速傅利叶变换（Fast Fourier transform），其中快速傅利叶变换在程序实现后应该是性能最好的。这里我们不详细介绍这些方法，只要知道给定 𝑛 个点的坐标，就肯定能求得一个 𝑛−1 阶多项式经过这 𝑛 个点。

我的理解就是把得到的一组乘法等式，直接套现成的数学公式，就可以得到多项式了；

3. R1CS（秩序1的约束系统）& QAP

虽然我们套公式已经得到了多项式，但是为了限制多项式变量，需要对这个多项式进行限制；

fn foo(w: bool, a: i32, b: i32) -> i32 {
    if w {
        return a * b
    } else {
        return a + b
    }
}

因为都是与1进行相乘，所以称之为秩序1的约束系统（我猜的）；

为了方便计算，很多文章把这些方程的系数用行列式来表示；

阶段二，承诺生成

在 verifier 完全什么也不知道的情况下，让 verifier 去验证、然后还能验证成功，我觉得是不可能的。顺着这个思路往下想，那就变成了：我们得让 verifier 知道点什么，让 ta 可以根据知道的这点东西进行验证，但知道的这点东西又不足以让他知道事情的全貌。 具体来说，就是我们得让 verifier 知道 prover 拥有的多项式的一部分，让 ta 可以对多项式进行验证；但 verifier 知道的这部分多项式，不足以让 ta 推导出整个多项式来。

1. 拆分多项式(最本质的核心)

这里就引入了一个随机值S；

2. 互不信任之一：加密随机值（同态加密+取模运算）

真正的取模操作是在有限域中操作的；这里的G也是椭圆曲线有限域的一个生成元，取模操作其实也是椭圆曲线的一个切线；

3. 互不信任之二：KEA

这里就引入了另外一个随机值alpha； 现在我们有了两个随机值S和alpha，这个就是setup的CRS，是必须要销毁的秘密。不然整个ZKP就可以伪造proof；

4. 非交互（setup，CRS）

解决以上问题的方式就是利用双线性映射对。具体逻辑请看大神的整片文章大神文章

最总要的总结如下：

总结（copy另外一个大神的）

文章出处