零知识证明讲解

摘要：零知识证明系统包括两部分宣称某一命题为真的示证者和确认该命题确实为真的验证者。零知识证明系统也叫做最小泄露证明系统。基于此衍生了集中知名的隐私币，其中零知识证明起到了非常大的作用。下面我们来介绍几种采用了零知识证明的区块链系统。

微信：wuqiong_blockchain      
本文发表在BFTF，请跳转链接： 一文读懂区块链中的零知识证明
本文被选为星球日报头条，请跳转链接： 一文读懂区块链中的零知识证明

零知识证明是一种基于概率的验证方式，验证的内容包括“事实类陈述”和“关于个人知识的陈述”。验证者基于一定的随机性向证明者提出问题，如果都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明系统包括两部分：宣称某一命题为真的示证者(prover)和确认该命题确实为真的验证者(verifier)。证明是通过这两部分之间的交互来执行的。在零知识协议的结尾，验证者只有当命题为真时才会确认。但是，如果示证者宣称一个错误的命题，那么验证者完全可能发现这个错误。

这里我们给出一个有关零知识证明的非常经典的例子，来帮助大家理解：

阿里巴巴被强盗抓住，为了保命，他需要向强盗证明自己拥有打开石门的口令，
同时又不能把密码告诉强盗。他想出一个解决办法，先让强盗离开自己一箭之地，
距离足够远让强盗无法听到口令，足够近让阿里巴巴无法在强盗的弓箭下逃生。
如果强盗举起左手，阿里巴巴就使用口令将石门打开，如果举起右手，就将石门关闭。
阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。如果每次都能正
确打开和关闭大门，则证实阿里巴巴确实知道石门的密码。

这个整个过程就是零知识证明，即证明者能够在不向验证者提供任何有用信息（石门的口令）的情况下，使验证者相信某个论断（阿里巴巴知道打开石门的方法）是正确的。

由此我们可以总结出零知识证明的三个属性：

1、如果语句为真，诚实的验证者（即：正确遵循协议的验证者）将由诚实的证明者确信这一事实。

2、如果语句为假，不排除有概率欺骗者可以说服诚实的验证者它是真的。

3、如果语句为真，证明者的目的就是向验证者证明并使验证者相信自己知道或拥有某一消息，而在证明过程中不可向验证者泄漏任何有关被证明消息的内容。

零知识证明系统也叫做最小泄露证明系统。

中本聪创造性的提出了比特币并且构建了一个去中心化的交易平台，从而去除了长久以来对第三方交易平台的信任依赖，但是与此同时，比特币又需要将所有的交易广播到网络上并通过所有节点达成共识来保证整个系统的安全性，也就是说所有的人都可以看到网络上所有的交易，而原始的比特币协议又并没有对交易发送者和接收者的地址作任何处理，这就导致某些细心的攻击者通过分析一个地址的交易特征并结合一些实际信息，就有可能分析出地址与实际人的对应关系，从而给使用者的隐私带来极大的隐患。基于此衍生了集中知名的隐私币，其中零知识证明起到了非常大的作用。

下面我们来介绍几种采用了零知识证明的区块链系统。

ZCash作为匿名加密货币项目，一开始只是作为比特币的加密匿名层存在，后来因为其优秀的隐私性成为独立的加密货币。与比特币一样，ZCash的总量也是2100万，不同的是它可以实现真正意义上的匿名——各位甚至都不用知道对方有多少钱就能完成交易。

为什么ZCash如何实现真正的匿名和保护隐私？

利用了zk-SNARK技术，也即零知识证明的技术：即使货币的来源与流向信息完全保密，零知识证明技术仍然可以验证花钱的用户确实拥有货币。

公共区块链：ZCash使用公共区块链用于交易的展示，但是它会自动屏蔽掉交易的金额，货币的持有者可以通过查看密钥来观察相关联的信息。

在使用ZCash数字货币进行交易时，它会自动加密交易的原数据；同时交易个体并不需要ZCash节点来保存数据，只需要zk-SNARK来证明其“消费能力”。这主要体现在交易过程中的两点，一可以让别人在不知道具体交易内容的情况下验证交易（或者是智能合约函数调用）的有效性，二交易的详情也可以在公共区块链上消除掉。

这样交易双方似乎从来没出现，而实际交易已经完成了。作为吃瓜群众只知道有交易发生了，但也无法对货币流向进行跟踪。这样便实现了真正的“匿名交易”。

zk-SNARK中的技术实现

同态隐藏

同态隐藏可以一定程度上实现零知识证明。

举例：

A拥有x和y两个秘密的数字，需要向B证明这两个数字的和是7，只需要执行下面三个步骤：

1.A计算f(x)，f(y)，并发送给B
2.因为函数f(x)满足加法同态，B可以通过f(x)，f(y)计算f(x+y)
3.B独立计算f(7)，并验证f(x+y)=f(7)

多项式盲验证

多项式盲验证，即将加法同态的特性利用到多项式中。（此处数学概念比较强，可以只做浅显了解）

假定A知道一个最高d次的多项式P，而B想要知道对应某个s的E(P(s))：

我们希望在验证的过程中，A只知道P，不知道s，B只知道s，不知道P，可以通过下面方式实现：

1.对s的每个指数，B计算E(1)，E(s)，...，E(sd)，并发送给A
2.A知道多项式的所有系数，可以利用同态特性计算P(s)，并回送给B

KCA（Knowledge of Coefficient Test and Assumption）以及完整的多项式盲验证

上面提供的多项式盲验证方式有一个致命的问题，就是B根本没法验证A是真正利用多项式P(s)去计算结果，也就是说无法证明A真正知道这个多项式P(X)。KCA继续完善了上面的验证。

。。。。。此处省略三千字数学算法讲解。。。。。。。

总之：

通过加法同态，我们可以实现加法隐藏，让B在不知道x和y的情况下，
校验x+y的值。进一步，通过多项式盲验证，我们可以在不暴露多项
式P(X)的情况下，让B校验任意给定s对应的P(s)。

任意计算转换到多项式证明

从多项式推广到任意计算的盲验证。最终我们把原算式的证明转化成为多项式的证明，只要证明多项式，即可验证原算式。

匹诺曹协议

最后一步的验证流程。

门罗币（Monero）作为目前加密数字货币中代表性的一种，在保证交易的隐私性方面应用着极其巧妙的密码学技术。

门罗币的两个属性

不可链接性（Unlinkability）：无法证明两个交易是发送给同一个人的，也就是无法知道交易的接收者是谁。

不可追踪性（Untraceability）：无法知道交易的发送者是谁。

门罗币的技术实现

Stealth Addresses (隐蔽地址)

在门罗币中，每次发送者要发起一笔交易时，先利用接收者的公钥信息计算出一个一次性临时中间地址，然后将金额发送到这个中间地址，接收者再利用自己的公私钥信息找到那笔交易，从而进行花费，这样网络上其他的用户包括矿工等就无法确定中间地址到底属于谁的，但依然可以验证交易的有效性，而由于这个地址又是一次性的，每次都重新随机产生的，攻击者也就无法对真实的发送者接收者作任何关联。

假设Alice想给Bob转一笔账，对于Bob来说压力是非常大的，因为他需要扫描区块链上的所有的交易，然后计算相应的信息进行对比才能找到发给自己的交易。门罗币为此提出了一个改进的方案，就是Bob可以将他私钥的一半(a,B)交给一个第三方，从而授权第三方来帮忙检查区块链上所有属于Bob的交易，也就减轻了Bob的压力，但最终还是只有Bob能花费。

2.One-time Ring Signature (一次性环签名)

简而言之，环签名要做的就是将签名者的公钥和另外一个公钥集合（但不知道私钥）进行混合，然后再对消息进行签名，这样对于签名验证者（任何人都可以验证）来说，无法区分混合后集合中哪一个公钥对应的是真正的签名者。

下面主要介绍一下门罗币中采用的环签名技术的整个流程：

第一步，密钥生成（GEN）
签名者首先随机选择一个私钥x，然后计算对应的公钥。同时还计算另外一个公钥。这个公钥I称之为“密钥镜像”（key image），对于每一个签名来说这个密钥镜像是唯一的，所以后面也被用来判断签名是否之前出现过。

第二步，签名（SIG）
首先签名者随机选择一个包含n个元素的公钥集合，然后和自己的公钥进行混合产生混合后的集合S，假设混合后签名者的公钥在S中的下标为s，那么他的公钥就是Ps。然后签名者再从[1，l-1]中随机选择{qi, i = 0,...,n}和{wi, i=0,...,n,i!=s}，然后再计算一个非交互式的挑战(non-interactive challenge)。
这里非交互式是相对与交互式零知识证明中的挑战而言的，在交互式中这个挑战是验证者随机选取的一个值，而因为在区块链中交易双方只能通过区块链来进行传递信息，而不能直接进行交互，所以这里选择非交互式零知识证明。而需要这个挑战的原因是避免证明者伪造证据来欺骗验证者的情况出现。

第三部，签名验证（VER）
验证者要验证签名的有效性，首先计算然后验证。如果等式成立，然后运行LNK来验证签名是否使用过；如果等式不成立，说明签名是非法的。

第四步，重复校验（LNK）
这要求系统必须维护一个包含所有签名的镜像的集合，然后对于每一个新的签名，通过判断它的镜像是否在集合中，来判断该签名是否之前出现过。注意在这一步之前，先要通过上一步的签名验证过程。

门罗币通过隐蔽地址来保证不可链接性，通过环签名来保证不可追踪性，从而给用户的交易信息提供了很好的隐私性。但同时我们也可以发现，在隐蔽地址时获取incoming transaction方面给用户带来很大的压力，而且公私钥的长度也变为了原来的两倍，环签名时对于混淆公钥的选择要保证一定的随机性，签名的产生和验证过程复杂度都明显增加了，这些都是需要改进的地方。

去年12月，门罗团队宣布在协议中整合Bulletproofs机制。门罗团队表示，部署这项技术能够减少80%的交易容量，后续还将降低80%的交易费用，整体上能够提供“更大的存储空间、更合理的验证时间以及更低的费用”。