零知识证明介绍
最后更新于
最后更新于
作者：吴寿鹤区块链早期先行者
关于零知识证明是什么，也许你不一定很了解，但说到应用零知识证明技术的区块链产品，你也许并不陌生。zcash就是使用零知识证明技术的隐私币，以太坊上的混币合约也是零知识证明技术的一个应用，还有在今年比较热门的链下扩容技术zkRollup也是零知识证明技术的一个应用。这时你也许会很好奇零知识证明究竟是一个什么样的技术，为什么既可以用在隐私方面，也可以用于扩容。在接下来一个系列的文章中将为你一一介绍，从零知识证明的概念一直到零知识证明背后的密码学实现。
零知识证明的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifier）相信某个论断是正确的。
为了理解上面这段话的含义，接下来给出一个有关零知识证明的非常经典的例子：
Alice是色盲，Bob不是色盲，在Bob手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于Alice是色盲，所以Alice无法分辨这两个球是否是一样的，Bob需要向Alice证明这两个球是不一样的。在这里，Alice被称为验证者，他需要验证Bob的陈述正确与否，Bob被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），Bob需要在Alice不能获得两个球的颜色的情况下，向Alice证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。
Alice当Bob的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样Bob就看不到Alice手上的球了，Alice在背后随机交换左右手上的球，交换完成后Alice将手伸出，并询问Bob两个球是否交换过位置，如果Bob能看到球上的颜色，那么每次Alice换过球的位置后，Bob都能正确回答出Alice的问题。
第一次，Alice偷偷交换了手中球的位置，然后Alice问Bob是否交换了球的位置，如果Bob回答Yes，那么Alice有50%的概率相信Bob是可以区分这两个球的颜色，因为Bob有1/2的概率蒙对，所以Alice可以在进行一次测试。如果Bob回答No，那么Alice可以肯定Bob不能区分两个球的颜色。
第二次，Alice没有交换手中球的位置，然后Alice问Bob是否交换了球的位置。如果Bob回答No，那么Alice有75%的概率相信Bob是可以区分两个球的颜色。
这是上述情况的概率树：
第一次迭代后，Alice可以说Bob陈述的断言为真的概率为50％。如果Bob第二次回答正确，那么Alice可以说Bob陈述为真的概率达75％。在第三次迭代后，它将是87.5％。如果连续n次Bob都通过了检查，则Alice有1-(1/2)^n 的概率可以认为 Bob 说的是真的，这两个球的确是有红蓝两种颜色。
零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover)提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈诉骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。
根据零知识证明的定义可以得知零知识证明具有以下三个重要的性质：
完备性（Completeness）：只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。；
可靠性（Soundness）：如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。
零知识性（Zero-Knowledge）：证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。
在此示例中，如果Bob的拥有分别球颜色的知识，则Bob每次都会正确回答。这称为完备性。如果Bob不具备分别球颜色的相关知识，则Bob无法分辨Alice是否调换了球。这称为可靠性。在此协议中，Alice无法看到球的颜色。这称为零知识性。
交互式零知识证明协议依赖于验证者的随机尝试，需要证明者和验证者进行多次交互才能完成。非交互式零知识证明（Non-Interactive Zero-Knowledge, NIZK）将交互次数减少到一次，可实现离线证明和公开验证。在区块链等零知识证明应用场景中，非交互的性质是必须的，因为在区块链系统中，不能假设双方一直在线进行交互，在区块链网络上，证明者只要向全网广播一条证明交易，网络上的矿工在将这条交易打包到区块中的时候就帮验证者完成了零知识证明的校验。
数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
Alice为了向Bob证明他已经解决了一个数独难题，为此Alice创建了一个防篡改的机器。Alice将生成好的数独答案放入到机器中，机器可以向Bob发送证明。Alice的机器遵循以下公开可验证的协议：
首先，Alice在机器中放入尚未被解决的原始数独题目，数独中的谜题卡片三张正面朝上，例如，单元格C3具有3张正面朝上的9号卡片。
接下来，Alice上机器将他的答案正面朝下放置在相应的单元格上，同样也是每个单元格放三张。
最后Bob向机器获取证明，机器返回给Bob27个袋子：
机器将数独中每一行9张卡片取出，并分别混淆后放入一个袋子中，一共有9行，所以9个袋子
机器将数独中每一列9张卡片取出，并分别混淆后放入一个袋子中，一共有9列，所以9个袋子
机器将数独中每个粗线宫（3*3）内卡片取出，并分别混淆后放入一个袋子中，一共有9个，所以9个袋子
Bob分别对这27个袋子进行检查，如果每个袋子中的卡片都包含数字1到9，而且没有任何数字丢失或重复，那么Bob可以确认Alice的确解开了数独，并且Bob并没有从机器返回的证明中获取任何关于数独解的知识，因为机器返回给Bob袋子中的数据是被随机打乱的。
零知识证明的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifier）相信某个论断是正确的。
从零知识证明定义中可以提取到两个关键词：“不泄露信息”，“证明论断有效”，基于这两个特点扩展出零知识证明在区块链上的两大应用场景：
隐私：在隐私场景中，我们可以借助零知识证明的“不泄露信息”特性，在不泄漏交易的细节（接收方，发送方，交易余额）的情况下证明区块链上的资产转移是有效的。
扩容：在扩容场景中，我们不太需要关注零知识证明技术的“不泄露信息”这个特性，我们的关注重点是它的“证明论断有效”这个特性，由于链上资源是有限的，所以我们需要把大量的计算迁移到链下进行，因此需要有一种技术能够证明这些在链下发生的动作是可信的，零知识证明正好可以帮助我们做链下可信计算的背书。
在目前主流的公链，如比特币、以太坊上，从创世块开始，每个账号之间的交易信息都是公开记录在区块链上，这样做的好处是可以有效解决加密货币双花的问题，矿工可以溯源，校验每笔交易的余额是否足够。坏处是一旦某个账号的身份暴露了，那么第三方就可以追踪到这个账号的以往所有历史交易，甚至还可以反推出这个账号可能控制的其他账号，从这一点来说是相当缺乏隐私的。
要让交易在不泄漏交易相关细节的情况下可以被验证，这正是零知识证明解决的问题。要了解零知识证明是如何解决链上交易隐私的问题，可以参考以下两篇文章。
混币的原理参考：
17年出现了一款非常火爆的Dapp应用叫加密猫，加密猫曾造成以太坊主网大规模的拥堵，造成拥堵的原因是以太坊当时的TPS只有15，这意味着以太坊每秒只能处理15笔交易，如此低的TPS严重限制了区块链应用的大规模落地，所以有人开始研究区块链扩容的问题，目的就是为了提高链上的TPS。但区块链扩容受到Vitalik提出的不可能三角的限制，不可能三角是指区块链系统设计无法同时兼顾可扩展性，去中心化和安全性，三者只能取其二。这是一个很让人失望的结论，但我们必须知道，一切事物都有自己的边界，公链不应该做所有的事情，公链应该做它该做的事情：“公链是以最高效率达成共识的工具，能够以最低成本来构建信任”。作为共识的工具，信任的引擎，公链不应该为了可扩展性放弃去中心化与安全性。那么公链的TPS这么低，该怎么使用呢？我们是否可以将大量的工作放到链下去解决，仅仅将最重要的数据提交到区块链主链上，让所有节点都能够验证这些链下的工作都是准确可靠的呢？社会的发展带来的是更精细化的分工，区块链的技术发展也是如此，在底层区块链（Layer1）上构建一个扩展层（Layer2)，Layer1来保证安全和去中心化，绝对可靠、可信；它能做到全球共识，并作为“加密法院”，通过智能合约设计的规则进行仲裁，以经济激励的形式将信任传递到Layer2 上，而Layer2追求极致的性能，它只能做到局部共识，但是能够满足各类商业场景的需求。
ZK-Rollup就是基于零知识证明的二层扩容方案， ZK-Rollup方案起源于18年下半年，由Barry Whitehat和Vitalik先后提出。关于zkRollup介绍参考下面这篇文章：
运行过以太坊全节点的人都会有这样的感受：“同步以太坊全节点的过程太痛苦了”，往往同步以太坊全节点需要花费几天的时间，目前以太坊全节点已经达到399,45Gb。全节点对存储资源要求这样高，以至于很多个人电脑的硬盘空间和带宽都达不到运行全节点的要求，所以全节点变成了只有少部分实体能够运行的，区块链逐渐从去中心化变成了中心化运行。 etherscan以太坊全节点统计网址
全节点同步时间长的原因如下：
全节点数据量太大，下载几百GB的数据需要很长时间。
验证同步到本地的区块是否正确需要花费时间，因为有恶意节点会发送无效的区块。
在同步全节点过程中，为了验证链的正确性，需要从创世区块开始依次重放每个交易，然后验证计算出的账户状态是否与同步的状态相同。这不仅耗时，同时也是一种资源浪费，因为在你之前已有无数节点重复了相同的计算工作。我们之所以要重放每个区块的原因是：“我们目前判断一个计算是否正确执行的方法只有重新做一次这个计算，然后比较两者的结果是否相等”。有了零知识证明我们就不需要重复计算区块每个交易了，因为零知识证明可以帮助我们校验每个区块中的交易是否被正确执行。
目前有一个项目Coda，它采用零知识证明的方式将区块大小控制在22kB，且Coda的区块大小是固定的，不会随着时间增长而变大（递归零知识证明），从安全性角度来说，Coda的安全性不会低于传统区块链。
零知识证明压缩链上数据的好处：
不需要做重复的计算验证区块状态，减少计算资源浪费
区块链大小只有22k方便存储，同步，验证
由于运行Coda全节点的需要的资源少，所以区块链网络将有更多活跃节点，提升了去中心化程度
递归零知识证明生成：使用前一个状态的proof以及当前交易作为输入，接下来验证前一个状态的proof以及当前交易是否有效，如果全部验证通过，程序会输出一个新的状态及一个proof，过程如下图所示：
递归零知识证明验证：只要验证前一个状态的proof就可以验证整个链的状态，比如：当验证proof #5状态是正确的，相当于递归验证了proof #4，proof #3。
Trusted Set-up（可信设置）：是否需要可信设置
Speed（Verifier + prover）：证明者生成证明和验证者验证证明所花费的时间总和。
Proof Size：生成零知识证明的大小
Quantum Resistant（抗量子）：是否抗量子攻击，在未来量子计算可能会对现有的加密算法带来威胁，
1985 年，零知识证明Zero-Knowledge Proof - 由 S.Goldwasser、 S.Micali 及 C.Rackoff 首次提出。
2010年，Groth实现了首个基于椭圆曲线双线性映射全能的，常数大小的非交互式零知识证明协议。后来这个协议经过不断优化，最终成为区块链著名的零知识证明协议SNARKs。
2013年，Pinocchio协议实现了分钟级别证明，毫秒级别验证，证明大小不到300字节，将零知识证明从理论带到了应用。后来Zcash使用的SNARKs正是基于Pinocchio的改进版。
2014 年，名为Zerocash的加密货币则使用了一种特殊的零知识证明工具zk-SNARKs （ Zero-Knowledge Succinct Non-interactive Arguments of Knowledge ) 实现了对交易金额、交易双方的完全隐藏，更注重于隐私，以及对交易透明的可控性。
2017 年， Zerocash 团队提出将 zk-SNARKs 与智能合约相互结合的方案，使交易能在众目睽睽下隐身，打造保护隐私的智能合约。
目前，为了解决零知识证明技术的广泛应用需求，产生了多个用于实现zk-SNARK 零知识证明协议工程化的开源算法库，包括 libsnark、bellman、ZoKrates 等等。
libsnark是一个基于C++语言的zk-SNARK工程开发算法库，由SCIPR Lab开发和维护，开发者中包含参与多篇zk-SNARK学术论文的共同作者。libsnark实现了近年来多个主流的zk-SNARK论文方案，其中最为常用的包括BCTV14a和Groth16方案。
libsnark实现了zk-SNARK算法的黑盒化，提供高度抽象的编程接口，使开发者无需掌握算法细节即可直接进行工程开发。此外，libsnark还提供了实际应用中的常见基础功能库，可辅助开发者进行复杂证明的组合实现。以在匿名数字货币Zcash中的应用为开端，libsnark奠定了零知识证明技术从理论研究到大规模工程应用的基础。
在Zcash项目中，最初采用libsnark算法库实现zk-SNARK零知识证明。在2018年升级到Sapling版本时，由于之前采用的libsnark版本较老，其中关于椭圆曲线和zk-SNARK方案的选择都已不是当时的最优选项，Zcash改为使用自研的bellman算法库。bellman是Zcash团队基于Rust语言实现的zk-SNARK算法库，支持Groth16论文方案，目前主要在Zcash项目中应用。
ZoKrates是一个部分基于libsnark、部分采用Rust语言重写的zk-SNARK实现工具，默认支持Groth16方案，开发者需要使用一种自建的脚本语言进行代码编写，目前在实际工程中仅用于在以太坊智能合约上部署支持零知识证明的应用。
在使用零知识证明时，不会降低安全性；
具有完整隐秘性；
安全性依赖于未解决的数学难题（如离散对数、大整数因子分解、平方根等等）；
生成零知识证明需要大量的算力
部分协议需要可信设置
部分协议不能抗量子计算
