前言
我们学数学时都知道计算题和证明题的区别，证明就是知道条件和结论，根据一定的规则或标准，由公理和定理推导出结论的过程。对应到编程中即知道输入和输出，证明输出是由输入计算所得。
零知识证明是一种不泄露输入并且能直接证明输出正确的算法。zkSNARK则是目前零知识证明算法中验证效率最高的算法，所以在区块链上有很好的应用场景。
DxChain一直积极探索存储证明等技术，零知识证明也是我们重点研究的方向之一。在这系列文章中我们会尽可能详细直白的介绍零知识证明，第一篇我们从基本原理开始，后续系列将介绍实际应用中需要做的优化，让我们能够对零知识证明有比较完整的认识。
1. 零知识证明有什么用
大概了解了什么是零知识证明，但是它有什么用，它能做到哪些一般算法做不到的事？下面对零知识证明的应用场景列举一二：
1）关于数据存储证明：在区块链分布式存储中，当我们需要验证矿工的存储能力时，为了防止矿工作弊，需要让他们参与大量的计算，但是验证时又需要能快速有效地验证，零知识证明正好具有这样的特性，Filecoin共识的底层就是zkSNARK。
2）关于隐私数据的声明：某个软件需要用户芝麻信用分大于700，但是用户不希望泄露自己的信用分750，又想证明自己有资格使用该软件。
3）匿名认证：用户持有私钥，平台只保存用户提交的私钥哈希值。用户登录时只需要证明自己持有的私钥所生成的哈希值在平台的哈希值列表中即可登录，不需要向平台提交其他信息。
4）计算外包：将高成本的计算外包出去，只需要对计算结果进行快速验证，是一种零信任计算。
从上面的应用场景来看，在解决数据存储和隐私保护方面，零知识证明有着极大的应用前景，尤其是区块链，验证链上的数据往往需要多个节点共同参与，零知识证明不但可以快速验证，还能很好的保护隐私数据。
zkSNARK的核心是多项式证明，接下来我们从最简单的问题开始，先了解多项式的零知识证明，然后试着将一般的算法程序转为多项式进行证明。本系列文章会尽量简单直观的介绍数学原理，读者只需要有基本的数学知识即可，但零知识证明的原理还是会有一些抽象，如果不理解可以多读一两遍。下面请大家准备好笔和纸，让我们开始吧~
2. 证明的媒介-多项式
假设Alice知道一组长度为10的数组，Alice声称10位数都置为了1，Bob一次只能验证一位。想要验证Alice的声明就要进行抽样验证，抽样一次验证正确则可信度为1/10，如果要达到95%以上的可信度则需要抽样10次，如果这个数组长度达到几百万，那抽样验证效率就非常低。如何做到对一组数验证一次就可以达到95%以上的可信度？
我们来看通过多项式验证。
例如：f(x) = x^3 – 6x^2 + 11x – 6，这个多项式最高为3次方，则称它的阶为3。多项式的特性是两个阶都为d的不相等多项式，它们的交点个数不会超过d。
比如将原来多项式稍微修改一下变为x^3 – 6x^2 + 10x – 5，两个多项式的图像如下图：
我们可以令两个多项式相等来找到它们的交点，得出 x = 1，即两个多项式只有一个交点(1, 0)。
对于这两个多项式，最多有三个不同的x取值可以让结果相等（实际这里只有一个），其他任意取值的x导致的计算结果都不相同。因此当一个Prover（证明者）声称他知道Verifier（验证者）也知道的多项式，即他知道该多项式的系数（知道所有n个系数即可确定一个n阶多项式），这里阶数越高系数越多，无论系数多少个，他们都可以按下面的协议进行验证：
Verifier选择一个随机值r并在本地计算多项式的结果
Verifier将r传给Prover，并让Prover计算相关的多项式结果
Prover代入r到多项式计算并将结果返回给Verifier
Verifier检查本地计算结果和Prover返回的结果是否相等，如果相等则说明Prover的陈述有较高可信度
比如将r的取值范围定为[1, 10^77]，多项式阶数为d，P和V计算得到不同结果的数量可以有10^77-d个，因此如果他们多项式不相等，则碰巧计算结果相等的概率为d/10^77，我们认为几乎不可能。
这里只需要验证一次就可以达到几乎100%的可信度，所以zkSNARK的核心就是用多项式作为证明媒介。
3. 证明多项式的知识
如上所述，多项式的知识就是它的系数。如果一个人说他知道一个多项式（例如：c1x^1 + c0=0），就意味着他知道多项式的系数c1、c0。
一个比较简单的定理是，任意一个多项式只要有解，就可以分解成多个线性多项式（一阶多项式的图像是直线所以叫线性多项式)，即可以将任意多项式看成其因式的乘积：
(x – a0)(x – a1)…(x – an) = 0
只要任意一个因式为0则整个多项式等于0，也就是所有x=a0,a1…an都是多项式的解。
了解了这些，接下来让我们看看这样一个证明问题：V想要找一个包含解x=1和x=2的多项式，P声称自己知道这样一个多项式，他需要向V证明他知道，但是不希望V马上知道答案。
假设P知道的多项式为x^3 – 3x^2 + 2x = x(x-1)(x-2)，他要证明多项式p(x)包含两个解x=1和x=2，令t = (x-1)(x-2)，则只需要证明p(x) = h(x) * t(x)
这里h(x) = p(x) / t(x) ，如果不能计算出这样的h(x)，也就意味p(x)不包含t(x)，会有余数（关于多项式除法可以参考[pik14]）。
这里计算出h(x) = x，没有余数。说明Prover可以证明他知道这样一个多项式包含解x=1和x=2。
接下来实践一遍验证过程：
Verifier随机挑选一个数r = 23，计算t = (23 – 1)(23 – 2) = 462，将r发给Prover
Prover计算得到h(x) = p(x)/t(x) = x，分别计算p(r) = p(23) = 10626，h(r) = h(23) = 23，将p(r)和h(r)发给Verifier
Verifier验证p = h * t : 10626 = 23 * 462 是正确的，验证通过
这里如果Prover不知道具体的p(x)，则不能计算出匹配的h(x)，返回的数值就不会验证通过。完成验证后Verifier不知道具体的p(x)和h(x)，但是可以确定Prover知道这样一个多项式，包含解x=1和x=2。
4. 一般程序到多项式-zkSNARK
上面我们讲了如何证明多项式的知识，接下来只需要将证明一般的程序问题转为证明多项式就可以解决大部分场景的证明问题了。
我们用一个简单问题来走一遍：证明你知道三次方程x^3 + x + 5 == 35的解(答案是3)，前提是不透露这个解。
第一步：拍平
拍平就是将任意复杂的表达式转换为只有两种运算形式（加法和乘法）。
这里说的任意复杂的问题是指计算机在有限时间内能解决的计算问题，加法和乘法可以表示其他的运算法则，比如证明a-b=c，因为证明问题我们是知道结果c的，所以只需要写成b+c=a就可以，其他比如除法、比较大小等都可以表示，这里不作展开。
上述方程拍平可以得到：
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
可以看出来，拍平后的表达式与原始方程是等价的。
第二步：转为R1CS
一阶约束系统R1CS（rank-1 contraint system）是描述向量组之间的约束关系。其实上面的方程或者拍平的表达式就是一种约束系统，这种约束关系确定了只有特定的x满足约束条件，这里x=3就是满足约束的解，将x=3代入拍平后的表达式可以得到一组解向量s：
[~one, x, ~out, sym_1, y, sym_2]
= [1, 3, 35, 9, 27, 30]
拍平后的四行表达式，每一行是一个乘法门（加法是乘常数1），即一个约束。用R1CS描述原方程就是有四个约束，每一个乘法门约束关系我们都用A*B-C=0表示。例如第一个约束sym_1 = x * x，表示为R1CS为一个向量组：
A: [0, 1, 0, 0, 0, 0]
B: [0, 1, 0, 0, 0, 0]
C: [0, 0, 0, 1, 0, 0]
将解向量代入应该是满足这一个约束的（3 * 3 – 9 = 0），如下图所示
这里是将解向量代入验证，用来表示约束关系只需要a、b、c三个向量，所以将四个约束全部表示出来得到如下R1CS向量组：
A:
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B:
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C:
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
可以看出来，我们将乘法门左向量都放到A组，右向量都放到B组，输出向量都在C组。到这里我们就成功将一个计算问题转换成了R1CS，接下来要做的就是证明我们的解满足这个约束关系。我们不能像上图那样把解带进去验证四次，这样的证明不能零知识也不够简洁，所以下一步还需要将R1CS转为多项式。
第三步：R1CS转为QAP
要将这些向量转为QAP(quadratic arithmetic program)，需要先了解一下拉格朗日插值定理：
经过n个点(x1, y1)、(x2, y2)…(xn, yn)的n-1阶多项式为：
比如点(1,2) (2,2) (3,4)对应的多项式为：
知道怎么用这个公式之后，我们开始将上一步的R1CS转为QAP。对于ABC三组向量，每组的六个变量分别对应一个多项式，多项式经过四个点，取横坐标x=1,2,3,4，纵坐标为向量的值，进行拉格朗日插值：
例如(1, 0) (2, 0) (3, 0) (4, 5) 插值后的多项式为0.833x^3 – 5x^2+9.166x -5，将多项式的系数按幂升序排列，于是有全部的QAP：
A:
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B:
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C:
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
此时如果将x=1代入上面18个多项式，可以得到第一个约束的三个先向量，再将x=2,3,4分别代入可以恢复出所有的R1CS。我们可以验证，当且仅当x=1、2、3、4时，下面关系都是成立的：
设Z(x)=(x-1)(x-2)(x-3)(x-4),则有A(x) * B(x) – C(x) = H * Z(x)
参考上面多项式证明中讲的一致性原理，这里原始方程x^3 + x + 5 ==35的解3决定了A、B、C多项式的系数，我们要验证的就是Prover知道详细的A(x)、B(x)、C(x)的具体数值，Verifier通过发起随机数挑战就可以验证Prover知道原方程的解，但是Verifier自始至终无法得到原方程的解。
5. 总结
至此我们理解了zkSNARK的基本原理，这里也能看出，一个简单的方程要做到零知识证明需要相对较多的计算，但是证明的效率却很高。如果希望更快速高效的进行链上验证，包括解决小数误差的影响，就要用到有限域和椭圆曲线等。后面的系列我们会介绍如何继续优化zkSNARK，让它可以实际应用起来。
附录
[Pik14] – Scott Pike. Dividing by a Polynomial. 2014.
url:http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html
[But16] – Vitalik Buterin. Quadratic Arithmetic Programs: from Zero to Hero. 2016.
url:https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
[But17] – Vitalik Buterin. zk-SNARKs: Under the Hood. 2017.
url:https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6