（接上回书，地址https://xie.infoq.cn/article/b39a20bda8904cfb0da06e915?from=message）



1.3 零知识证明原理

零知识证明概念最早出现在1985年，后来成为密码学的研究课题，在这一技术下，验证者可以验证证明者的某个观点是真实的，且证明者无须提供、也不会泄露除了该观点是正确的之外的任何信息。



举个例子，四十大盗抓住了阿里巴巴，想让阿里巴巴带路，但是他不想泄漏自己的密码“芝麻开门”，于是他跟四十大盗商量：



我有一个办法，你们不需要知道咒语就可以确定我是知道开门密码的。这样，你们离我一箭之地，用弓箭指着我，你们举起右手我就念密码打开石门，举起左手我就念密码关上石门，如果我做不到或逃跑，你们就用弓箭射死我。



强盗觉得反正我可以达到我的目的就可以了，于是开始验证阿里巴巴的咒语。强盗举起右手，只见阿里巴巴嘴动了几下，石门打开了，强盗又举起了右手，阿里巴巴嘴巴动了几下之后，石门又关上了。强盗还是有点不信，说不准是巧合呢，于是不断换着左右手，阿里巴巴总能在收到指令之后，让石门或开或关。最后，所有强盗都相信阿里巴巴知道开石门、关石门的密码，不再怀疑。



阿里巴巴的这个方案，就是“零知识证明”能力的体现。阿里巴巴向四十大盗表明他知道某种秘密，不仅能使大盗完全确信他的确知道这个秘密，同时还保证一丁点秘密也不泄露给大盗。



与其说是一种技术，倒不如说是一种理念，零知识证明在概念上有点像信息安全领域的零信任模型，在零信任模型中，终端上、网络上、后台服务都设置有控制点，把点串起来，形成一整套访问控制机制。零知识证明也是类似，它是一组综合运用数学多项式转换、模糊计算/同态加密、模运算、哈希、随机数挑战等技术为一体的套件，目的只有一个，就是只向外界传达我具有xx数据这样一个信息，而不泄露具体数据。



实践中，零知识证明系统可以分为交互式和非交互式，交互式是指验证者在交互中提供一个或若干个「随机数」来挑战，由证明者根据随机数提供答案，直到验证者认为证明者缺失拥有某信息或确实不具备某信息，满意为止；非交互式（ Non-Interactive Zero Knowledge，简称 NIZK）是为了改善交互式验证时间长、验证周期复杂的问题而出现的，验证过程只有「一轮」，而且可以直接广播给所有验证者，让他们自行验证，不管是时间上还是空间上，都有革命性的提升。

1.3.1 交互式ZKP原理

我们来看一个例子：

Alice和Bob分别代表证明者和验证者，Alice需要向Bob证明他知道数据a，但又不能直接把a透露给Bob。



其中，private表示私钥，是只有Alice才知道的内容，可以像身份证一样代表Alice的身份；public表示公钥，是与private成对出现的内容，可以公布出去给任何人看，参与计算；G是双方都知道的一个椭圆曲线的点，之所以选择椭圆曲线，完全是信息安全的需要，可以简单理解为，在公式R=r*G中，知道G可以很容易算出R，但知道R、G却很难算出r，椭圆曲线上不止是除法这么简单，这是单向函数的一个特点，计算不可逆。



不要被这一堆字母给迷惑了，流程是这样的：

Alice：选择一个随机数r，然后计算出R=r*G，将R发送给Bob；

Bob：返回一个随机数c，这样，Alice有了参数r、c、sk、G，Bob有了参数R、c、PK、G；

Alice：计算z=r+c*sk，将结算结果z发送给Bob；

Bob：将z*G，然后把计算结果，与自己计算的R+c*PK进行比较。Alice提供的a没有问题的话，z*G应该等于（r+c*sk）*G，等于r*G+c*sk*G，等于R+c*PK。



就这样，通过椭圆曲线这个单向函数，以及交互的机制，达到了证明对方身份、防篡改以及不传递a却证明Alice有a这样一个信息。这个方式是Schnorr机制的一种实现方式，也叫Sigma protocol，是一种经典的交互式ZKP。

1.3.2 交互式ZKP的缺点

我们用一个有一点点数据含量的例子来表示交互式ZKP方案的复杂性，地图三染色问题。



所谓地图三染色问题，是指用三种颜色染色一个地图，保证任意两个相邻的国家/地区被涂上不同的颜色。假设Alice 手里有一个地图三染色的答案。现在 Alice 想向 Bob 她有答案，但是又不想让 Bob 知道这个答案。Alice 要怎么做呢？



1. Alice 先对染过色的图进行一些「变换」，把颜色做一次大挪移，例如把所有的绿色变成橙色，把所有的蓝色变成绿色，把所有的绿色变成橙色。然后 Alice 得到了一个新的染色答案，这时候她把新的图的每一个顶点都用纸片盖上，然后出示给 Bob 看。



1. 这时候 Bob 要采用随机大法验证了，他挑选了一条“边”，所谓随机就是不让 Alice 提前预测到的随机数。假设 Bob 挑选的是最下面的一条边，然后告诉 Alice。



1. 这时候 Alice 揭开这条边两端的纸片，让 Bob 验证，Bob 发现这两个顶点的颜色是不同的，那么 Bob 认为这次检验同构。这时候，Bob 只看到了图的局部，但不足以说服他Alice有完整的答案，也许恰好 Alice 蒙对了呢？其它没暴露的顶点可能是胡乱染色的。



1. Bob 可以要求 Alice 再来一遍，Alice 再次把颜色做一次变换，把蓝色改成紫色，改绿色改成棕色，把橙色改成灰色，然后把所有的顶点盖上纸片。然后 Bob 再挑选一条边，如下图所示，选择的是一条竖着的边，然后让 Alice 揭开纸片看看，如果这时候 Bob 再次发现这条边两端的顶点颜色不同，那么 Bob 就有一次得到验证信息。如此往复，直到Bob满意为止。



1. 经过反复多次重复这三个步骤，可以让 Alice 作弊并能成功骗过 Bob 的概率会以指数级的方式减小，无限趋近于零。在这个过程中，Alice并没有把完整的染色方案告诉Bob，Bob也无法依靠拿到的一次次的局部方案，拼凑出整个方案。



信息含量大的数据，往往需要更多的交互，才能保证验证者相信证明者的能力。时间上，验证周期较长，空间上，验证的部位较多，尽管交互验证是一种很好的零知识证明方式，但注定走不远，应用场景受限，也正是因为这个，出现了非交互式ZKP。

1.3.3 非交互式ZKP原理

还是拿例子解释，跟前面一样，Alice和Bob分别代表证明者和验证者，Alice需要向Bob证明他知道数据a，但又不能直接把a透露给Bob。



上图流程是这样的：

Alice：选择随机数r，并依次计算R、c、z。（1）R=r*G；（2）c=Hash(R,PK)，Hash函数也是一种单向函数，不能根据输出倒推输入，可根据输入参数计算出一个固定长度的、独一无二的结果。哪怕输入参数的值变一个比特位，输出值也会发生变化；（3）z=r+c*sk；

Alice：向Bob发送(R,z)；

Bob：自行计算Hash(PK,R)；将Alice传递来的z，与G相乘，验证其结果与R+（c*PK）的值是否相等。如果Alice确实知道数据a，那么z*G应该等于（r+c*sk）*G 等于 r*G+c*sk*G 等于 R+c*PK 。



与1.3.1流程中第二步不同的是，Bob在这里不再需要给出一个随机的挑战数c，而是让Alice用c=Hash(PK,R)这个式子来计算这个挑战数，主动给出，从而使得非交互式ZKP流程简化到只有一步。哈希函数的引入，也能够实现Alice无法造假、参与计算挑战的目的。



整个过程中Alice并未暴露自己的数据a，且Bob无法通过正常手段或作弊手段获取Alice的数据，且c的值与Alice的公钥、私钥、随机数直接相关，给出某一个具体的随机数，可以得到固定的c值，这体现了一种随机数的映射关系，叫做“随机数预言机”。



除了上述机制以外，目前比较常用的非交互式ZKP主要是zk-SNARKs，主要利用了多项式因式分解、哈希函数、同态加密等技术手段，达到验证者对证明者的采样点进行验证的目的，可以公布出去供所有验证者进行验证，同时，验证点采用同态加密技术隐藏起来，任何具体的数据都不暴露出来。

1.3.4 随机数的重要性

对上述机制深入理解不难发现，在协议中产生的随机数 r 保证了数据 a 的保密性，r不应自带或带出a的任何数据特性，因为任何一个秘密和一个符合“一致性分布”的数算数运算之后的结果仍然符合“一致性分布”，这就增加了被猜测的可能性。



随机数r能保证数据a的保密性，但既然r是Alice自己产生的，如何能保证r不是Alice“制造的”？保证Bob不被欺骗？



• 在交互式ZKP中，是通过在交互过程中的第二步，由Bob发出一个随机数c来实现的，Alice无法预测c值，所以不能提前制造满足运算结果的输入。

• 在非交互式ZKP中，看上去所有参数都是Alice发过去的，所以应该能够制造出骗过Bob的随机数吧？——答案是：不能。我们推导一下：Bob是要验证z*G =（r+c*sk）*G = r*G+c*sk*G = R+c*PK ，如果要制造的话，就是要伪造出一个c=（z*G-R）/ PK，由于HASH函数的不可逆性，即便能够计算出c，r也是无法逆运算出来的。也就是说，依靠哈希函数，c实现了“随机性”。



除了在零知识证明中的应用，随机数在协议、机制中的应用处处可见，且非常重要。比如国密算法就要求，国密三级必须使用硬件产生随机数，随机数的种子一定要放到硬件中去，软件实现的加密模块，最多只能达到国密二级的要求。



主打匿名性的区块链加密货币ZCash里用到了ZKP来保证交易双方和交易金额的匿名性，ZCash团队甚至不惜代价去切尔诺贝利核事故发生地取来了带有核辐射的废料，然后在高空中用利用核辐射来生成随机数。

2、应用场景分析

前文对同态加密、多方计算、零知识证明进行了介绍，为了说得清楚，期间穿插了很多例子，但归根到底还是想要说明白这些技术可以怎么用，用到什么地方、什么应用场景，接下来将就这一主题展开分析。

（待续）