Topic: 关于零知识证明 - page 2. (Read 366 times)
最近谷歌联合创始人布林谈到了零知识证明的潜力，这是Zcash隐私选项的基础。根据布林的说法，零知识证明背后的潜力是“令人难以置信的。隐私货币未来会大受欢迎。毕竟政府以后肯定会对加密货币征税。
小白感觉有点云里雾里。
这种否太偏理论了，感觉就是论文或者白皮书里的内容。
啥时能普及些基础知识就好了。
我一看见这标题还以为是找零机制呢，哪个大佬可以普及下找零机制的相关知识。
啥时能普及些基础知识就好了。
我一看见这标题还以为是找零机制呢，哪个大佬可以普及下找零机制的相关知识。
大佬，这篇文章太有技术含量了，挺好的区块链知识干货，看来要多多学习了
写的不错，看完了懂了些基础知识。
零币家族的币还是可以的，有闲钱的可以屯一点，比那些token好多了。
零币家族的币还是可以的，有闲钱的可以屯一点，比那些token好多了。
挺好的区块链知识干货，希望这样的帖子可以多一点。
好文章，谢谢分享
这种技术性的文章还是可以的, 就是概念性的内容太多, 不好太容易理解.
好技术，可是ZEC最近也是跌的一塌糊涂了
论坛里面还是要多些这种稍微有深度的文章，我们接触这么多的加密货币。
最后连基本的加密学都不知道是不是有点搞笑，和人家讨论比特币讨论区块链，讨论啥。。
也许能讨论的就只有价格吧，论坛还是要多看看这样的帖子的。
最后连基本的加密学都不知道是不是有点搞笑，和人家讨论比特币讨论区块链，讨论啥。。
也许能讨论的就只有价格吧，论坛还是要多看看这样的帖子的。
非常好的文章。前面解释得非常明白。不过最好有一点疑问。为什么s和k为什么要找6个人保存呢？这s和k不是Bob随机想出来的么？
学习一下
文章很有深度，但是看完简单，理解难，所以很多人不在乎技术如何如何厉害，只要有狗庄拉盘肯定会赚钱，有资金进入就能炒！有技术的币有信仰的人也会多
近期学习区块链知识的时候也看到了关于零知识证明，从字面去翻译一下这个词：不提供任何相关的信息来达到证明的目的。
当然，这是我在查了一定量的资料之后得出的理解，当我第一次看到这个词的时候，在我脑海里只知道它是一种证明，是一种方法论。
在区块链可解释为 指证明者能够在不向验证者提供信息本身的内容的情况下，使验证者相信某个论断是真实可信的一种技术
当然，这是我在查了一定量的资料之后得出的理解，当我第一次看到这个词的时候，在我脑海里只知道它是一种证明，是一种方法论。
在区块链可解释为 指证明者能够在不向验证者提供信息本身的内容的情况下，使验证者相信某个论断是真实可信的一种技术
什么是零知识证明
零知识证明(Zero—Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用。如果能够将零知识证明用于验证，将可以有效解决许多问题。
零知识证明例子
阿里巴巴被强盗抓住，为了保命，他需要向强盗证明自己拥有打开石门的密码，同时又不能把密码告诉强盗。他想出一个解决办法，先让强盗离开自己一箭之地，距离足够远让强盗无法听到口令，足够近让阿里巴巴无法在强盗的弓箭下逃生。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。
这个整个过程就是零知识证明，证明者能够在不向验证者提供任何有用信息（石门的口令）的情况下，使验证者相信某个论断（阿里巴巴知道打开石门的方法）是正确的。
zk-SNARK
zk-SNARK 它是一种非常适合区块链的零知识验证技术，可以让别人在不知道具体交易内容的情况下验证交易（或者是智能合约函数调用）的有效性。有了zk-SNARK，我们既保留了区块链互相不信任个体间的共识达成问题，又保护了交易隐私，简直就是在众目睽睽下原地隐身。
zk-SNARK的全称是zero-knowledge Succinct Non-Interactive Arguments of Knowledge （零知识，简洁，非交互的知识论证）。
zk-SNARK的应用
在正式深入zk-SNARK的之前，我们不妨先看看它有哪些实际的应用。Zcash 是第一个应用zk-SNARK技术的区块链，它能够提供完全隐私化和加密化的虚拟货币转账。完美解决了老董发工资的难题。
以太坊(Ethereum)目前也在试图把Zcash的隐私交易功能作为一个预编译合约链接到其上的其他智能合约中（由于如果不使用预编译，每个区块的gas限制将无法完成复杂的zk-SNARK运算）。这被称为ZoE (Zcash over Ethereum)，不过即使做了预编译优化，他能提供的隐私验证能力非常有限。
尚未正式发布的Hawk是一个完全采取了zk-SNARK的区块链智能合约部署系统。
当然zk-SNARK所能提供的隐私化交易未来还会有很多其他领域的应用。一个例子是通过区块链进行的拍卖，每个参与竞标的人无需暴露自己的身份和标的具体内容，这将让更多类型的拍卖得以在区块链上实现。另一个例子是匿名选举，投票人无需暴露自己身份就可以在区块链上参与投票。此外，zk-SNARK还可以使能一些“选择性公开”的场景，比如你可以在区块链上证明你在某一个城市而不暴露你的具体位置。
zk-SNARK技术详解
zk-SNARK是一种特别适合区块链的零知识论证 算法（论证与验证并不完全一样，为了简洁，在本文中不对验证和论证作区分）。这里为什么说zk-SNARK特别适合区块链呢？因为zk-SNARK在实现零知识验证的同时还具有以下几个特点：
Succinct （简洁性）：验证者(verifier)只需要少量计算就可以完成验证。这对于区块链非常重要，因为区块链上为了能够快速达到共识，每一个计算步骤不能过于复杂。
Non-interactive (非交互性)：示证者(prover)和验证者(verifier)之间只需要交换极少量的信息即可完成整个验证过程。这对于区块链同样至关重要，因为区块链上节点众多，并且每个节点都需要每一笔对交易进行验证，所以验证过程必须只涉及极少量的信息交换，否则通信成本会非常巨大。
zk-SNARK的使用场景例子
为了理解zk-SNARK是怎么工作的，我们先考虑一个非常简单的场景：Alice想要向Bob证明她知道一组数x和y使得x+y=7，同时不让Bob知道x和y的具体数值。
一个简单的办法是使用一种神奇的“加密函数”E(x)，这种加密函数有三个重要性质：
如果x,y不同，那么它们的加密函数值E(x)和E(y)也不相同。
给定E(x)的值，很难反推出x的值。
给定E(x)和E(y)的值，我们可以很容易地计算出某些关于x,y的加密函数值。比如，我们可以通过E(x)和E(y)计算出E(x+y)的值。
在这里，我们不深入讨论这种加密函数是什么，有一定抽象代数知识的读者可以去查看原始zk-SNARK的论文[1]（事实上，椭圆曲线配对也是zk-SNARK的一个重要创新）。
有了这种加密函数，我们就可以很容易地设计出以下验证方案1.0：
Alice把E(x)和E(y)的数值发给Bob，
Bob通过收到的E(x)和E(y)计算出E(x+y)的值 （利用了加密函数的性质3），
Bob同时计算E(7)的值，如果E(x+y)=E(7)，那么验证通过，否则验证失败。
由于加密函数的性质1，如果E(x+y)=E(7)，则必然x+y=7成立，验证有效；同时由于加密函数的性质2，Bob无法从E(x)，E(y)反推出x，y的具体数值。因此，Alice在不泄露x,y具体数值的情况下向Bob验证了x+y=7。
但是上述方案没有完全实现“零知识”，因为E(x)和E(y)还是泄露了一些关于x和y的信息。比如我们限定x,y为正整数，则Bob可以穷举所有相加为7的数字组合，然后把这些数字组合与收到的E(x), E(y)进行对比，从而获得x,y的具体数值。解决这个问题的方法是Alice产生一个秘密的随机数t，然后发送x+t和y-t的加密函数值E(x+t), E(y-t)给Bob。由于(x+t)+(y-t)=7，所以Bob那里仍可以验证通过，同时由于“随机偏移”t的引入，Bob无论如何也猜不到x,y的真实数值。
于是我们现在有了验证方案2.0：
Alice产生一个随机数t, 并把E(x+t)和E(y-t)的数值发给Bob，
Bob通过收到的E(x+t)和E(y-t)计算出E(x+y)的值，
Bob同时计算E(7)的值，如果E(x+y)=E(7)，那么验证通过，否则验证失败。
以上方案实现了完全的“零知识”验证，看似我们的问题已经解决了，可真的是这样吗？
很可惜并不是！上面这个算法的问题在于它只能验证一些非常简单的知识（不过在实际中这个验证协议已经非常有用，比如RSA加密协议）。而在实际的区块链操作中，需要验证的知识可能是非常复杂的。在很多时候，以上这种仅仅依赖加密函数的方案就不够用了。
接下来我们考虑一个稍微复杂一点的场景：Alice需要向Bob证明她知道一个满足一定性质的秘密多项式P(x)，并且不泄露具体这个多项式P(x)是什么。
注意了，这个多项式验证问题非常重要！我稍后会提到：
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
重要的问题说三遍。
下面我们来看如何修改之前的验证算法来解决多项式验证的问题。
先给大家先补习一下数学知识，一个度为d的多项式P(x)可以写成以下形式：
P(x) = a0 + a1x + a2x2 + … +adxd
为什么之前利用加密函数的方案在这里不能直接套用了呢？一个原因是之前我们只需要验证一组具体的值满足一定性质（如x=1和y=6满足x+y=7），而这里的多项式中x的值可能有无穷多个取值，穷举所有的可能性会消耗大量的计算资源。一个巧妙的办法是与其验证所有可能的取值，我们让Bob随机选一个x的值（如x=s），然后Alice仅仅需要向Bob证明多项式P(x)在x=s这一点的取值P(s)满足某种性质。这个随机取样的方法之所以合理，是因为两个不同的多项式在大多数情况都是不相等的，比如两条不同的直线最多有一个相交的点。如果我们随机取一个点，两个不同的多项式取值相同的概率几乎可以忽略不计。采用这个随机取样的办法，验证工作的计算量就大大降低了，这就是zk-SNARK中 “Succinct （简洁性）”的实现办法。
另外和验证方案2.0一样，Alice需要引入一个“随机偏移” R(s)来使得Bob完全得不到任何关于P(s)的信息。注意P(s)+R(s)必须满足待验证的性质。我们在这里不具体介绍R(s)是如何产生的。
加上这个随机采样的办法，我们得到了验证方案3.0：
Bob向Alice发送一个随机点s，
Alice首先产生一个随机偏移多项式R(x)，然后计算P(s)和R(s)，并且把P(s)+R(s)的加密函数值E(P(s)+R(s))发给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质。
但是验证方案3.0有一个重大缺陷。Bob直接把随机点s的取值发送给了Alice，而P(s)需要满足的性质又是公开的，这就意味着Alice即使不知道多项式P(x)是什么，她也完全可以找一个与P(s)不同但是仍然满足条件的值y，并把y的加密函数值E(y)发给Bob。这种情况Bob仍然会验证通过。怎么处理这个缺陷呢？一个简单的解决办法就是把随机点s加密发给Alice，但是这样做的坏处就是Alice无法计算P(s), R(s)及其加密函数值E(P(s)+R(s))了。为了让Alice仍能计算E(P(s)+R(s))，我们可以让Bob把E(1), E(s), E(s2), ..., E(sd)都发送给Alice。根据加密函数的性质3，Alice是可以根据E(1), E(s), E(s2), ..., E(sd)计算出E(P(s)+R(s))的数值的，同时随机点s的具体数值也没有暴露。
于是我们得到了验证方案4.0：
Bob选取一个随机点s,并向Alice发送一系列加密函数值：E(1), E(s), E(s2), ..., E(sd)，
Alice首先产生一个随机偏移多项式R(x)，然后根据收到的E(1), E(s), E(s2), ..., E(sd)计算E(P(s)+R(s))的值并发送给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质。
不过仔细想想验证方案4.0也有个问题。因为Bob只在一个随机点s进行了验证，Alice完全可能是人品爆发恰好在s这一点蒙对了，而实际并不知道符合条件的多项式P(x)长啥样！那么Bob怎么验证Alice确实知道多项式P(x)，而不是恰好蒙对的呢？答案仍然是随机化！
我们可以让Bob在产生随机点s的同时再产生一个随机数k，然后向Alice同时发送关于s和k的信息。之后Bob要求Alice返回两个数，一个是P(s)的加密值E(P(s))，另一个是kP(s)的加密值E(kP(s))。注意k是一个只有Bob自己知道的秘密随机值，如果Alice可以同时告诉Bob关于P(s)和kP(s)的信息，则证明Alice不是瞎蒙的，而是确实知道P(x)这个多项式长啥样。具体原因是由于一个叫“知识系数假设” (Knowledge of Coefficient Assumption)的数学假设，我在这里就不具体叙述了。
现在我们有了验证方案5.0 （最终方案）：
Bob选取一个随机点s和一个随机系数k,并向Alice发送两串加密函数值：[E(1), E(s), E(s2), ..., E(sd)], [E(k), E(ks), E(ks2), ..., E(ksd)]，
Alice首先产生一个随机偏移多项式R(x)，然后根据收到的[E(1), E(s), E(s2), ..., E(sd)], [E(k), E(ks), E(ks2), ..., E(ksd)]计算E(P(s)+R(s))以及E(kP(s)+kR(s))的值并发送给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质，并且验证收到的另一个加密函数值是不是E(kP(s)+kR(s))。
以上基本就是zk-SNARK的完整验证流程了。不过最后还有几个重要的设计细节需要提一下（相信我，这真的是最后了）。
第一，我们注意到Bob(验证者)需要发送给Alice(示证者)的信息是不随验证内容变化的，因此可以事先在区块链中一次性设置好，之后任何验证过程都可以复用这个设置，验证者不再需要向示证者发送任何信息。这个事先设置好的信息被称为Common Reference String(CRS, 共同参考字符串)。一个重要的考虑是随机点s和随机系数k是必须严格保密的，否则就会有伪造证明通过验证。那么在实际中，这个随机点s和随机系数k是保存的呢？在Zcash的系统里，CRS中存放的实际上只是随机点s和随机系数k的一系列加密值，而s和k的明文则由6个“被充分信任的人”私下保存，这6个人处在地球上6个不同的位置，这些机密的随机数被拆开保存在这6个人手上，只要不是这6个人都变成“坏人”，这些随机数信息就不会被完整恢复。一个有意思的故事是，这6个“被充分信任的人”在最初的时候举行了一个神圣的仪式，共同参与并见证了这个随机点s和随机系数k的产生。
第二，以上我们只是讨论了多项式验证的问题。但是实际我们要验证的交易程序可能是非常复杂的。zk-SNARK提供了一个系统化的方法可以把任何验证程序转化成一个叫Quadratic Span Program (QSP)的多项式验证问题。有兴趣的读者可以阅读参考文献[2]。
zk-SNARK的不足与缺陷
之前说了zk-SNARK那么多的好处，那么它目前有没有什么缺陷呢？那必然是有的。
第一个问题：虽然zk-SNARK通过随机采样的方式大大减小了验证工作的计算量，但是由于需要验证一个较为复杂的多项式性质，其和传统的验证过程相比仍然耗费了更多了计算资源。这仍是目前很多区块链无法承受的计算需求。因此，如何针对zk-SNARK进行计算优化仍是一个开放问题。
第二个问题：我们提到zk-SNARK有一个初始设置的阶段，来生成“绝对机密”的随机信息。目前这些绝密随机信息的生成和保存仍然非常原始（参见之前提到的神秘仪式），很难让人完全放心，也很难进行拓展。比如，未来每一个需要隐私保护的智能合约可能都会有自己的初始随机信息要生成，如何确保这些初始随机信息不会被坏人泄露？同时业界和学术界也在研究如何在zk-SNARK中避免这个让人诟病的初始设置步骤。
如何使用 zk-SNARK 算法
zk-SNARK 算法的主要作者们写了一个 libsnark 库，提供了一些基础组件，zcash 用的零知识证明库就是 libsnark 的一个 fork 版本。我本人刚开始看到这个库时也是一筹莫展，即使在我了解了这么多关于 zk-SNARK 背后的技术知识后。而后，寻得一个作者编写的简单例子，才基本入了门。
参考资料
https://www.jianshu.com/p/b6a14c472cc1?from=timeline
http://news.btc123.com/news/detail?id=8125
https://blockchain.iethpay.com/zkSNARK-intro.html
零知识证明(Zero—Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用。如果能够将零知识证明用于验证，将可以有效解决许多问题。
零知识证明例子
阿里巴巴被强盗抓住，为了保命，他需要向强盗证明自己拥有打开石门的密码，同时又不能把密码告诉强盗。他想出一个解决办法，先让强盗离开自己一箭之地，距离足够远让强盗无法听到口令，足够近让阿里巴巴无法在强盗的弓箭下逃生。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。
这个整个过程就是零知识证明，证明者能够在不向验证者提供任何有用信息（石门的口令）的情况下，使验证者相信某个论断（阿里巴巴知道打开石门的方法）是正确的。
zk-SNARK
zk-SNARK 它是一种非常适合区块链的零知识验证技术，可以让别人在不知道具体交易内容的情况下验证交易（或者是智能合约函数调用）的有效性。有了zk-SNARK，我们既保留了区块链互相不信任个体间的共识达成问题，又保护了交易隐私，简直就是在众目睽睽下原地隐身。
zk-SNARK的全称是zero-knowledge Succinct Non-Interactive Arguments of Knowledge （零知识，简洁，非交互的知识论证）。
zk-SNARK的应用
在正式深入zk-SNARK的之前，我们不妨先看看它有哪些实际的应用。Zcash 是第一个应用zk-SNARK技术的区块链，它能够提供完全隐私化和加密化的虚拟货币转账。完美解决了老董发工资的难题。
以太坊(Ethereum)目前也在试图把Zcash的隐私交易功能作为一个预编译合约链接到其上的其他智能合约中（由于如果不使用预编译，每个区块的gas限制将无法完成复杂的zk-SNARK运算）。这被称为ZoE (Zcash over Ethereum)，不过即使做了预编译优化，他能提供的隐私验证能力非常有限。
尚未正式发布的Hawk是一个完全采取了zk-SNARK的区块链智能合约部署系统。
当然zk-SNARK所能提供的隐私化交易未来还会有很多其他领域的应用。一个例子是通过区块链进行的拍卖，每个参与竞标的人无需暴露自己的身份和标的具体内容，这将让更多类型的拍卖得以在区块链上实现。另一个例子是匿名选举，投票人无需暴露自己身份就可以在区块链上参与投票。此外，zk-SNARK还可以使能一些“选择性公开”的场景，比如你可以在区块链上证明你在某一个城市而不暴露你的具体位置。
zk-SNARK技术详解
zk-SNARK是一种特别适合区块链的零知识论证 算法（论证与验证并不完全一样，为了简洁，在本文中不对验证和论证作区分）。这里为什么说zk-SNARK特别适合区块链呢？因为zk-SNARK在实现零知识验证的同时还具有以下几个特点：
Succinct （简洁性）：验证者(verifier)只需要少量计算就可以完成验证。这对于区块链非常重要，因为区块链上为了能够快速达到共识，每一个计算步骤不能过于复杂。
Non-interactive (非交互性)：示证者(prover)和验证者(verifier)之间只需要交换极少量的信息即可完成整个验证过程。这对于区块链同样至关重要，因为区块链上节点众多，并且每个节点都需要每一笔对交易进行验证，所以验证过程必须只涉及极少量的信息交换，否则通信成本会非常巨大。
zk-SNARK的使用场景例子
为了理解zk-SNARK是怎么工作的，我们先考虑一个非常简单的场景：Alice想要向Bob证明她知道一组数x和y使得x+y=7，同时不让Bob知道x和y的具体数值。
一个简单的办法是使用一种神奇的“加密函数”E(x)，这种加密函数有三个重要性质：
如果x,y不同，那么它们的加密函数值E(x)和E(y)也不相同。
给定E(x)的值，很难反推出x的值。
给定E(x)和E(y)的值，我们可以很容易地计算出某些关于x,y的加密函数值。比如，我们可以通过E(x)和E(y)计算出E(x+y)的值。
在这里，我们不深入讨论这种加密函数是什么，有一定抽象代数知识的读者可以去查看原始zk-SNARK的论文[1]（事实上，椭圆曲线配对也是zk-SNARK的一个重要创新）。
有了这种加密函数，我们就可以很容易地设计出以下验证方案1.0：
Alice把E(x)和E(y)的数值发给Bob，
Bob通过收到的E(x)和E(y)计算出E(x+y)的值 （利用了加密函数的性质3），
Bob同时计算E(7)的值，如果E(x+y)=E(7)，那么验证通过，否则验证失败。
由于加密函数的性质1，如果E(x+y)=E(7)，则必然x+y=7成立，验证有效；同时由于加密函数的性质2，Bob无法从E(x)，E(y)反推出x，y的具体数值。因此，Alice在不泄露x,y具体数值的情况下向Bob验证了x+y=7。
但是上述方案没有完全实现“零知识”，因为E(x)和E(y)还是泄露了一些关于x和y的信息。比如我们限定x,y为正整数，则Bob可以穷举所有相加为7的数字组合，然后把这些数字组合与收到的E(x), E(y)进行对比，从而获得x,y的具体数值。解决这个问题的方法是Alice产生一个秘密的随机数t，然后发送x+t和y-t的加密函数值E(x+t), E(y-t)给Bob。由于(x+t)+(y-t)=7，所以Bob那里仍可以验证通过，同时由于“随机偏移”t的引入，Bob无论如何也猜不到x,y的真实数值。
于是我们现在有了验证方案2.0：
Alice产生一个随机数t, 并把E(x+t)和E(y-t)的数值发给Bob，
Bob通过收到的E(x+t)和E(y-t)计算出E(x+y)的值，
Bob同时计算E(7)的值，如果E(x+y)=E(7)，那么验证通过，否则验证失败。
以上方案实现了完全的“零知识”验证，看似我们的问题已经解决了，可真的是这样吗？
很可惜并不是！上面这个算法的问题在于它只能验证一些非常简单的知识（不过在实际中这个验证协议已经非常有用，比如RSA加密协议）。而在实际的区块链操作中，需要验证的知识可能是非常复杂的。在很多时候，以上这种仅仅依赖加密函数的方案就不够用了。
接下来我们考虑一个稍微复杂一点的场景：Alice需要向Bob证明她知道一个满足一定性质的秘密多项式P(x)，并且不泄露具体这个多项式P(x)是什么。
注意了，这个多项式验证问题非常重要！我稍后会提到：
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
无论多复杂的验证问题都可以最终简化为一个多项式验证问题！
重要的问题说三遍。
下面我们来看如何修改之前的验证算法来解决多项式验证的问题。
先给大家先补习一下数学知识，一个度为d的多项式P(x)可以写成以下形式：
P(x) = a0 + a1x + a2x2 + … +adxd
为什么之前利用加密函数的方案在这里不能直接套用了呢？一个原因是之前我们只需要验证一组具体的值满足一定性质（如x=1和y=6满足x+y=7），而这里的多项式中x的值可能有无穷多个取值，穷举所有的可能性会消耗大量的计算资源。一个巧妙的办法是与其验证所有可能的取值，我们让Bob随机选一个x的值（如x=s），然后Alice仅仅需要向Bob证明多项式P(x)在x=s这一点的取值P(s)满足某种性质。这个随机取样的方法之所以合理，是因为两个不同的多项式在大多数情况都是不相等的，比如两条不同的直线最多有一个相交的点。如果我们随机取一个点，两个不同的多项式取值相同的概率几乎可以忽略不计。采用这个随机取样的办法，验证工作的计算量就大大降低了，这就是zk-SNARK中 “Succinct （简洁性）”的实现办法。
另外和验证方案2.0一样，Alice需要引入一个“随机偏移” R(s)来使得Bob完全得不到任何关于P(s)的信息。注意P(s)+R(s)必须满足待验证的性质。我们在这里不具体介绍R(s)是如何产生的。
加上这个随机采样的办法，我们得到了验证方案3.0：
Bob向Alice发送一个随机点s，
Alice首先产生一个随机偏移多项式R(x)，然后计算P(s)和R(s)，并且把P(s)+R(s)的加密函数值E(P(s)+R(s))发给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质。
但是验证方案3.0有一个重大缺陷。Bob直接把随机点s的取值发送给了Alice，而P(s)需要满足的性质又是公开的，这就意味着Alice即使不知道多项式P(x)是什么，她也完全可以找一个与P(s)不同但是仍然满足条件的值y，并把y的加密函数值E(y)发给Bob。这种情况Bob仍然会验证通过。怎么处理这个缺陷呢？一个简单的解决办法就是把随机点s加密发给Alice，但是这样做的坏处就是Alice无法计算P(s), R(s)及其加密函数值E(P(s)+R(s))了。为了让Alice仍能计算E(P(s)+R(s))，我们可以让Bob把E(1), E(s), E(s2), ..., E(sd)都发送给Alice。根据加密函数的性质3，Alice是可以根据E(1), E(s), E(s2), ..., E(sd)计算出E(P(s)+R(s))的数值的，同时随机点s的具体数值也没有暴露。
于是我们得到了验证方案4.0：
Bob选取一个随机点s,并向Alice发送一系列加密函数值：E(1), E(s), E(s2), ..., E(sd)，
Alice首先产生一个随机偏移多项式R(x)，然后根据收到的E(1), E(s), E(s2), ..., E(sd)计算E(P(s)+R(s))的值并发送给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质。
不过仔细想想验证方案4.0也有个问题。因为Bob只在一个随机点s进行了验证，Alice完全可能是人品爆发恰好在s这一点蒙对了，而实际并不知道符合条件的多项式P(x)长啥样！那么Bob怎么验证Alice确实知道多项式P(x)，而不是恰好蒙对的呢？答案仍然是随机化！
我们可以让Bob在产生随机点s的同时再产生一个随机数k，然后向Alice同时发送关于s和k的信息。之后Bob要求Alice返回两个数，一个是P(s)的加密值E(P(s))，另一个是kP(s)的加密值E(kP(s))。注意k是一个只有Bob自己知道的秘密随机值，如果Alice可以同时告诉Bob关于P(s)和kP(s)的信息，则证明Alice不是瞎蒙的，而是确实知道P(x)这个多项式长啥样。具体原因是由于一个叫“知识系数假设” (Knowledge of Coefficient Assumption)的数学假设，我在这里就不具体叙述了。
现在我们有了验证方案5.0 （最终方案）：
Bob选取一个随机点s和一个随机系数k,并向Alice发送两串加密函数值：[E(1), E(s), E(s2), ..., E(sd)], [E(k), E(ks), E(ks2), ..., E(ksd)]，
Alice首先产生一个随机偏移多项式R(x)，然后根据收到的[E(1), E(s), E(s2), ..., E(sd)], [E(k), E(ks), E(ks2), ..., E(ksd)]计算E(P(s)+R(s))以及E(kP(s)+kR(s))的值并发送给Bob，
Bob验证接收到的加密函数值E(P(s)+R(s))是否满足给定的性质，并且验证收到的另一个加密函数值是不是E(kP(s)+kR(s))。
以上基本就是zk-SNARK的完整验证流程了。不过最后还有几个重要的设计细节需要提一下（相信我，这真的是最后了）。
第一，我们注意到Bob(验证者)需要发送给Alice(示证者)的信息是不随验证内容变化的，因此可以事先在区块链中一次性设置好，之后任何验证过程都可以复用这个设置，验证者不再需要向示证者发送任何信息。这个事先设置好的信息被称为Common Reference String(CRS, 共同参考字符串)。一个重要的考虑是随机点s和随机系数k是必须严格保密的，否则就会有伪造证明通过验证。那么在实际中，这个随机点s和随机系数k是保存的呢？在Zcash的系统里，CRS中存放的实际上只是随机点s和随机系数k的一系列加密值，而s和k的明文则由6个“被充分信任的人”私下保存，这6个人处在地球上6个不同的位置，这些机密的随机数被拆开保存在这6个人手上，只要不是这6个人都变成“坏人”，这些随机数信息就不会被完整恢复。一个有意思的故事是，这6个“被充分信任的人”在最初的时候举行了一个神圣的仪式，共同参与并见证了这个随机点s和随机系数k的产生。
第二，以上我们只是讨论了多项式验证的问题。但是实际我们要验证的交易程序可能是非常复杂的。zk-SNARK提供了一个系统化的方法可以把任何验证程序转化成一个叫Quadratic Span Program (QSP)的多项式验证问题。有兴趣的读者可以阅读参考文献[2]。
zk-SNARK的不足与缺陷
之前说了zk-SNARK那么多的好处，那么它目前有没有什么缺陷呢？那必然是有的。
第一个问题：虽然zk-SNARK通过随机采样的方式大大减小了验证工作的计算量，但是由于需要验证一个较为复杂的多项式性质，其和传统的验证过程相比仍然耗费了更多了计算资源。这仍是目前很多区块链无法承受的计算需求。因此，如何针对zk-SNARK进行计算优化仍是一个开放问题。
第二个问题：我们提到zk-SNARK有一个初始设置的阶段，来生成“绝对机密”的随机信息。目前这些绝密随机信息的生成和保存仍然非常原始（参见之前提到的神秘仪式），很难让人完全放心，也很难进行拓展。比如，未来每一个需要隐私保护的智能合约可能都会有自己的初始随机信息要生成，如何确保这些初始随机信息不会被坏人泄露？同时业界和学术界也在研究如何在zk-SNARK中避免这个让人诟病的初始设置步骤。
如何使用 zk-SNARK 算法
zk-SNARK 算法的主要作者们写了一个 libsnark 库，提供了一些基础组件，zcash 用的零知识证明库就是 libsnark 的一个 fork 版本。我本人刚开始看到这个库时也是一筹莫展，即使在我了解了这么多关于 zk-SNARK 背后的技术知识后。而后，寻得一个作者编写的简单例子，才基本入了门。
参考资料
https://www.jianshu.com/p/b6a14c472cc1?from=timeline
http://news.btc123.com/news/detail?id=8125
https://blockchain.iethpay.com/zkSNARK-intro.html
Jump to: