零知识证明（zk-SNARK）- groth16（一）

全称为 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge，简洁非交互式零知识证明，简洁性使得运行该协议时，即便 statement 非常大，它的 proof 大小也仅有几百个bytes，并且验证一个 proof 的时间可以达到毫秒级别。
这是一个通用的零知识证明协议，可以用作各种证明，如范围证明。
核心方法是通过R1CS，QAP等方法将计算难题变为多项式，将计算结果正确性巧妙转化为了多项式的有特殊解的问题，生成对应proof，然后再运用多项式证明方法，来完成证明与验证。

Non-Interactive Argument of Knowledge of a Polynomial

（注意 计算和参数选取是在域内，即有模运算）

一般多项式的证明

场景如下：Verifier 有一个多项式$f(x)$，Prover 向 Verifer 证明他知道这一个多项式。
假设 Prover 知道的多项式为$p(x)$，那么现在要证明的就是$f(x)=p(x)$，如果这两个多项式的阶数最高为$d$，那么两个多项式代表的曲线将最多有$d$个交点，当 Verifier 随机在一个很大的范围内取一个值$s$的时候，那么$s$和$d$相同的概率会非常低，所以有以下协议

• Verifier 在大范围里随机选择一个值$s$，并且在本地计算$f(s)$，然后把$s$发送给 Prover
• Prover 计算$p(s)$，然后发送给Verifier
• Verifier 验证$f(s)\stackrel{?}{=}p(s)$
  

证明多项式的根

有些多项式是可以分解多个多项式的乘积的，如假设$p(x)=(x-a)(x-b)(x-c)$那么
假设 Prover 有一个多项式$p(x)$，现在他想证明他的多项式持有一部分根（部分多项式），也就是证明他的多项式$p(x)=t(x)h(x)$中包含$t(x)$假设为$(x-a)(x-b)$，而此时的$t(x)$称为目标多项式，是公开的，要注意 Prover 是不能透露原多项式的。那么有以下协议

• Verifier 在大范围内随机取值$s$，计算$t=t(s)$，然后将$s$发送给 Prover
• Proer 计算$h(x)=\frac{p(x)}{t(x)}$,$h(s)$,$p(s)$，然后发送后两个给 Verifier
• Verfier 验证$p(s)\stackrel{?}{=}t(s)h(s)$

显而易见以上变量都局限为整数，如果$p$确实能够整除$t$，那么等式一定是成立的，如果不能，那么式子将存在余式，有极大的概率不是整数。
当然此协议仍然有很大漏洞，比如 Prover 可能完全不知道$p(x)$，但知道公开的$t(x)$，所以可以完全捏造出$h(x)$满足条件。

同态加密

显然我们不能在协议里进行明文的传输，但又需要密文的计算，所以需要一个满足加密和计算两种特性的算法。
同态加密算法$E(x)$，如$E(ax+by)=g^{ax+by}=g^{ax}\cdot g^{by}={\left(g^x\right)}^a\cdot {\left(g^y\right)}^b=E(x{)}^a\cdot E(y{)}^b.$（$g$是生成元），这里基于离散对数难题和 CDH 假设（即给定$g^a,g^b$，得到$g^{ab}$很困难）。显然这是仅仅满足同态加法的同态加密，不支持密文相乘。
那么该算法不支持乘法，仅有一个$s$的情况下，该怎么同态计算多项式呢？显然是不行的，于是想办法把同态乘法转变为同态加法，注意到，多项式$P(x)$可以看作是一组系数和未知数的线性结合，也就是计算出$s$的各个幂次，这需要固定好多项式的阶数$d$，相当于限制了多项式的阶数，这样提前计算出$s^1,\dots ,s^d$，然后计算出多项式的每个部分相加即可。
具体使用如下，

1. Verifier 在大范围里随机选择一个$s$，先计算好$s$的幂次$s^1,\dots ,s^d$，接着计算 $t(s)$，最后$E(1),E(s),\dots ,E(s^d)$并发给 Prover
2. Prover 收到数据后计算，$h(x)=\frac{p(x)}{t(x)}$，然后配合多项式的系数计算$E(p(s))$，$E(h(s))$并发送给Verifier
3. Verifier 进行验证$E(p(s))\stackrel{?}{=}E(t(s))E(h(s))$，即$g^{p(s)}=(g^{h(s)}{)}^{t(s)}$

** KCA（The Knowledge of Coefficient Test and Assumption）**

上面的协议的还是有很大漏洞，比如 Prover 在计算多项式的时候，没有采用多项式的格式（常数系数和未知数的线性组合），而是使用了另外的方法，算法找到一个满足$z_p=(z_h{)}^{t(s)}$的两个值$z_p,z_h$去替代掉$g^{p(s)},g^{h(s)}$，也就是根本没用多项式，直接仿造了满足条件的结果。
这里就需要对 Prover 进行限制，让他必须使用满足条件的多项式，限定为常数，也限定了指数，不能随意改变指数。所以KCA也可以叫做KEA(Knowledge of exponent)
思路如下，
定义一对元素$(a,b=\alpha \cdot a)$（称为一个$\alpha$-对）,$\alpha \cdot a$表示$\alpha$个$a$相加，也就是$a^{\alpha }$，那么一个KC流程如下具体如下，

1. 首先Verifier会随机选择一个非零的$\alpha$，计算$b=\alpha \cdot a$，定义这是一个$\alpha -shift$。
2. Verifier 发送这个 challenge pair $(a,b)$给 Prover。
3. 这时候 Prover 会 respond 一对不一样，但具有相同性质的 pair $(a^{\prime },b^{\prime })$，它应当是$\alpha -shift$
4. 如果收到的是一个$\alpha -shift$，那么Verifier 接受这个response

注意，这是满足DL问题的， Prover 是很难找到一个$\alpha$，那么她该如何构造新的$\alpha -shift$呢？一个显而易见的方式是，Prover 选择一个常数系数$\gamma$，直接构造$(a^{\prime },b^{\prime })=\gamma (a,b)$。
假设 Verifier 发送的不是一个，而是是$d$组$\alpha -shift$，那么 Prover 也将选择一组系数$c_1,\dots ,c_d$，respond 一个
$(a^{\prime },b^{\prime })=({\sum }_{i=1}^d{c}_i{a}_i,{\sum }_{i=1}^d{c}_i{b}_i)$，显然该对也是满足$\alpha -shift$。如果把 Verifier 发的内容优化一下，就构成了KCA。

Blind Evaluation of Polynomials Verifiable Protocol

完整的多项式盲验证协议。
解决整个问题需要满足的两个性质：

• **Blindness：**也就是 Prover 不能获取到$s$，同样 Verifier 也不能拿到$p(x)$（同态）。
• **Verifiability：**也就是得确保 Prover 发的$E(p(x))$确实是用某个多项式$p(x)$计算的，而不是完全不相关的数据（KCA）

那么使用KCA对前面协议进行优化如下，

1. Verifier 随机选择$\alpha$（非0）和$s$，然后计算$t(s)$，接着构造$\alpha -shift$$(g,g^{\alpha }),(g^s,g^{\alpha \cdot s}),\dots ,(g^{s^d},g^{\alpha \cdot s^d})$
2. Prover 则使用多项式$p(x)$的系数$c_1,\dots ,c_d$，然后计算$E(h(s))$以及$(E(p(s)),E(\alpha p(s)))=(g^{{\sum }_{i=1}^d{c}_i{s}^i},g^{{\sum }_{i=1}^d{c}_i\alpha \cdot s^d})$，发送给Verifier
3. Verifier进行验证$E(p(s))\stackrel{?}{=}E(\alpha p(s))$和$E(p(s))\stackrel{?}{=}E(t(s))E(h(s))$即可

该方案也可以解决前面的问题，即Prover 不能随意构造满足类似$z_p=(z_h{)}^{t(s)}$的$h(s)$，这样会很容易不满足$\alpha -shift$的限制条件。

Parings and bilinear map

前面的协议基本实现了诚实两方之间的交互方案，相关的 proof 仅仅在两方之间有效，无法重复使用，但在实际运用中，存在这恶意的多方的情况，这显然不符合实际。所以，需要让一些秘密参数变得可重复使用甚至公开，而且足够可信以防止滥用。
首先考虑将 Verifier 生成的$(t(s),\alpha )$进行加密保护，防止泄露。如果采用前面的同态加密，那么在后面的乘法计算中就会涉及到同态的乘法 ，但是前面用的同态算法不支持同态乘法。那么必须用到类似乘法的时候应该怎么办呢？这时候就引入了椭圆双曲线映射。
Parings 是能够将一个集合里的两个加密输入确定性的映射到另一个集合里的一个输出的一种乘法表示函数。
即：$e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$满足以下性质
$\begin{array}{rl}e({\mathrm{g}}_1^{\mathrm{a}},{\mathrm{g}}_2^{\mathrm{b}})& =\mathrm{e}({\mathrm{g}}_1,{\mathrm{g}}_2{)}^{\mathrm{ab}}=\mathrm{e}({\mathrm{g}}_1^{\mathrm{ab}},{\mathrm{g}}_2)=\mathrm{e}({\mathrm{g}}_1,{\mathrm{g}}_2^{\mathrm{ab}})\end{array}$
$\begin{array}{rl}e({\mathrm{g}}_1^{\mathrm{a}},{\mathrm{g}}_2^{\mathrm{b}})e({\mathrm{g}}_1^{\mathrm{c}},{\mathrm{g}}_2^{\mathrm{d}})& =\mathrm{e}({\mathrm{g}}_1,{\mathrm{g}}_2{)}^{\mathrm{ab}+\mathrm{cd}}\end{array}$
其意义在于，将某个群中的一对元素映射到一个新的群，当且仅当两个原像对应指数的积相同其像也相同。并且，该函数要求是可计算的（即不需要用暴力搜索等方式），它能够验证一对（加密后的）数据的乘积是否和另一对相同（虽然算不出这个乘积）
接下来将协议的计算放到满足Parings的椭圆曲线群上来。

Multiple Parties Composite Common Reference String

首先引入一个可信的第三方来随机生成$s$和$\alpha$，并且计算出CRS（Common Reference String），共证明和验证两部分，都是公开的（ i ∈ { 0 , … , d } i \in \{0,\dots,d\} i∈{0,…,d}），接着需要删除掉$s$和$\alpha$。

• Proving Key：$E(s^i),E(\alpha s^i)=g^{s^i},g^{\alpha s^i}$
• Verification Key：$E(t(s)),E(\alpha )=g^{t(s)},g^{\alpha }$

接着基于CRS，让 Prover 和 Verifier 仅仅通过CRS就能完成协议。继续优化协议如下，（下面简化$p=p(s),t,h$也类似）

• 对于 Prover 来说，公开的CRS中已经包含了第一步的内容，接下来是利用 Proving Key 来计算出$E(h(s))$和$(E(p(s)),E(\alpha p(s)))$
• 对于Verifier来说，是利用CRS中的 Verfication来进行验证（$p^{\prime }=\alpha p$）
  • 首先验证$p=t\cdot h$，即$e(g^p,g^1)=e(g^t,g^h)=e(g,g{)}^p=e(g,g{)}^{t\cdot h}$
  • 然后验证$\alpha -shift$，即$e(g^p,g^{\alpha })=e(g^{p^{\prime }},g)$

注意：这里也暴露出两个问题，

1. Proving Key 中的$E(\alpha )$是公开的，也就是对于 Prover 来说 ，他是可以打破多项式的限制条件的。
2. 引入了一个可信第三方，但更复杂的现实中不能保证第三方不存在恶意，比如不销毁 trusted setup 的随机秘密，这一旦暴露会导致任何人都可以伪造证明。

于是 ZKSNARK 引入了多方联合的setup，每个人用自己的私钥$(\alpha ,s)$和前一个人生成的 CRS 作为输入生成一个新的 CRS，只要保证有一个人销毁了私钥，就能保证最终的CRS是安全的。具体实现如下，
假设有三方 Alice,Bob,Carol 参与，仅需要使用同态乘法让每个人的私钥相加即可

同理参与方 Carol 公开后也可以进行验证。

完整的简短非交互式的多项式证明方案

这里用 { g s i } i ∈ [ d ] \{g^{s^i}\}_{i\in[d]} {gsi}i∈[d]​代表$s^1,\dots ,s^d$
首先确定好目标多项式$t(x)$和 prover 的多项式的阶数$d$，prover 需要证明他持有的多项式里含有$t(x)$。
具体如下

参考

浅谈零知识证明：背景与起源
zcash官方科普
Exploring Elliptic Curve Pairings
Quadratic Arithmetic Programs: from Zero to Hero
Why and how zk-SNARK works
ZKSNARK介绍
李威翰,张宗洋,周子博等.简洁非交互零知识证明综述[J].密码学报,2022,9(03):379-447.DOI:10.13868/j.cnki.jcr.000525.