【 BlockChain 】零知识证明

【 BlockChain 】零知识证明

一、零知识证明起源

“零知识”的概念最早在80年代由麻省理工学院的研究人员 Shafi Goldwasser，Silvio Micali 和 Charles Rackoff 所提出。当时这些人正在研究与交互证明系统相关的问题——即一种理论系统，使得甲方（证明者）可以和乙方（验证者）交换信息，并借此说服乙方接受（通过验证）某个数学论述为真 [作者注1]。

在Goldwasser等人之前，这个领域的研究工作主要聚焦在加强证明系统的可靠性（Soundness）。也就是说原先大家都假设，会有恶意的证明者试图耍手段，误导验证者接受错误的论述。但 Goldwasser 等人却从另一个角度思考了这个问题：如果我们压根就不相信验证者，该怎么办/p>

更具体的来说，他们更关心信息泄露的问题。他们抛出了这样的思考：“在验证者的验证过程中，究竟会获取多少单纯验证论述真假无需知道的额外信息。”

这里要强调一下，这个问题不是单纯的理论思考，而是在真实、具体的应用中，会面到临的问题。

我们举个例子，假设今天在真实世界有个客户端想要使用密码登录web服务器，在“真实世界”的标准操作流程中，包含将密码以哈希形式储存在客户端。我们可以将”登录“这个动作视作某种证明——也就是我们要能够提供一串输入，这串输入经过哈希运算后的值与密码的哈希相同（因为哈希运算的单向性，这串输入只能是我们的密码）。但这有个问题是：客户端实际上知道我们的密码。

大多数系统以这种绝对最糟糕的方式进行“证明”——客户端直接将原始密码发送给服务器，服务器重新计算密码哈希并将其与存储值进行比较。这里的问题很明显：在协议结束时，服务器已经取得我们的明文密码。 因此，保障现代密码安全很大程度上要祈祷服务器不会遭受攻击。

Goldwasser，Micali 和 Rackoff 等人提出了一种全新的方法来完成“证明”。如果零知识证明真的可行，它将允许我们在证明某些数学陈述为真的同时，保证不会有任何不相关的信息被透露出去。

二、零知识证明理解

通俗的来讲，零知识证明就是我让你相信我说的一句话或一个结论而不需要向你透露任何有关该结论的有用信息.举个简单的例子，比如说凡尔赛文学，我可以再不向你透露我有多少资产的前提下让你相信我非常有钱，毕竟财产总数是我的私人信息，我不想告诉任何人。

下面通过三个小故事简单的进行对零知识证明的理解：

①阿里巴巴与四十大盗

有一天，阿里巴巴被强盗抓住了，强盗向他索要开启山洞大门的咒语。

但此时阿里巴巴面临一个两难的问题，如果把密码告诉强盗，自己就没有利用价值了，最后肯定会被杀。

如果不告诉强盗咒语，强盗以为自己不知道咒语，自己还是会被杀。

怎么能做到让他们相信自己确实知道咒语，但是还不能让他们知道咒语是什么。

这确实是一个很难的问题，但是阿里巴巴想出了一个好办法。

他对强盗头领提议说，你们离我30米远，然后用弓箭指着我，当你举起双手后，我就念咒语开启山洞大门；当你把双手放下后，我就念咒语关上山洞大门，如果我要是逃跑，你们就用弓箭射死我。

对于强盗头领来说，这显然是个好主意，于是照办。

强盗头领先是举起双手，看到阿里巴巴动了动嘴皮子，门就开了，然后放下双手，阿里巴巴又动了动嘴皮子，门就关了。

显然，强盗相信了阿里巴巴。

这样，阿里巴巴在没有告诉强盗头领开门咒语的情况下，又向强盗证明了，自己是知道开门咒语的。

②地图着色问题

如何用三种颜色染色一个地图，保证任意两个相邻的地区都是不同的颜色。我们把这个「地图三染色问题」转变成一个「连通图的顶点三染色问题」。假设每个地区都有一个首府（节点），然后把相邻的节点连接起来，这样地图染色问题可以变成一个连通图的顶点染色问题。

下面我们设计一个交互协议：

• 「证明者」Alice
• 「验证者」 Bob

Alice 手里有一个地图三染色的答案，请见下图。这个图总共有 6 个顶点，9 条边。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xi0C2Olx-1645409350086)(https://lkk2lqq.com/picture/map1.png)]

现在 Alice 想证明给 Bob 她有答案，但是又不想让 Bob 知道这个答案。Alice 要怎么做呢/p>

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

假设 Bob 挑选的是最下面的一条边，然后告诉 Alice。

Alice 再次把颜色做一次变换，把蓝色改成紫色，改绿色改成棕色，把橙色改成灰色，然后把所有的顶点盖上纸片。然后 Bob 再挑选一条边，比如像上图一样，选择的是一条竖着的边，然后让 Alice 揭开纸片看看，如果这时候 Bob 再次发现这条边两端的顶点颜色不同，那么 Bob 这时候已经有点动摇了，可能 Alice 真的有这个染色答案。可是，两次仍然不够，Bob 还想再多来几遍。

那么经过反复多次重复这三个步骤，可以让 Alice 作弊并能成功骗过 Bob 的概率会以指数级的方式减小。假设经过 轮之后，Alice 作弊的概率为

下图来源物质实验室，是对三种技术的进一步对比，相对来说SNARKs发展时间更长，积累的资料更多，更易学习，所以后文所述内容以SNARKs为主。

四、零知识证明应用

零知识证明可以解决的问题

• 零知识证明技术可以解决数据的信任问题，计算的信任问题。

• 零知识证明技术可以「模拟」出一个第三方，来保证某一个论断是可信的。

零知识证明应用

• 数据的隐私保护：在一个数据表格中，多多少少都有一些信息不想被暴露，比如当年我的成绩单，我只想向人证明，我的成绩及格了，但是我不想让别人知道我到底考了61分还是62分，这会很尴尬。我没有心脏病，但是保险公司需要了解这一点，但是我不想让保险公司知道我的隐私信息。那我可以证明给保险公司看，我没有心脏病，但是病历的全部并不需要暴露。我是一家企业，我想向银行贷款，我只想向银行证明我具备健康的业务与还款能力，但是我不想让银行知道我们的一些商业秘密。
• 计算压缩与区块链扩容：在众多的区块链扩容技术中，Vitalik 采用 zkSNARK 技术能够给现有的以太坊框架带来几十倍的性能提升。因为有了计算的证明，同样一个计算就没必要重复多次了，在传统的区块链架构中，同样的计算被重复多次，比如签名的校验，交易合法性校验，智能合约的执行等等。这些计算过程都可以被零知识证明技术进行压缩。
• 端到端的通讯加密：用户之间可以互相发消息，但是不用担心服务器拿到所有的消息记录，同时消息也可以按照服务器的要求，出示相应的零知识证明，比如消息的来源、与发送的目的地。
• 身份认证：用户可以向网站证明，他拥有私钥，或者知道某个只要用户自己才知道的秘密答案，而网站并不需要知道，但是网站可以通过验证这个零知识证明， 从而确认用户的身份
• 去中心化存储：服务器可以向用户证明他们的数据被妥善保存，并且不泄露数据的任何内容。
• 信用记录：信用记录是另一个可以充分发挥零知识证明优势的领域，用户可以有选择性的向另一方出示自己的信用记录，一方面可以有选择的出示满足对方要求的记录分数，同时证明信用记录的真实性。
• 构造完全公平的线上数字化商品的交易协议。
• 更多的例子，可以是任何形式的数据共享，数据处理与数据传输。

零知识证明实例

（目前本人对这几个项目的研究还尚浅，这里先完全引用前人栽的树，后续有所研究再来补充）

第一个场景：ZCash项目

Zcash项目，大家都知道是“隐私交易”。Zcash代表了zkSNARK的一个应用方向：隐私。隐私有不同的程度，ZCash的隐私交易指的是隐藏交易的发送方，接收方以及交易金额。Zcash已经经历过三个版本：Sprout，Overwinter， Sapling。这三个版本本质上都没有太大的变化，只是支持的功能更多，生成证明更快，体验更好。

某个用户需要消费某个cm，必须向区块链提供零知识证明：

① 他知道一个Note，并能生成一个cm，而且这个cm在以rt为树根的Merkle树上

② 用同样的Note信息，能生成一个nullfier，而且这个nullfier之前没有生成过。

以上只是最简单的概括Zcash零知识证明的大体思路，ZCash的设计非常复杂和严谨，有很多细节。顺便说一句，理解ZCash，只需要看ZCash的白皮书protocol.pdf。理解了白皮书的设计，看源代码非常直接。这就是零知识证明的一个重要的运用方向 – 隐私，现实中还有很多应用类似技术的项目：EYBlockchain(EY，安永)，Quorum(JPMorgan)。

第二个场景：Filecoin项目

Filecoin是存储行业比较热门的项目。Filecoin想搭建一个去中心化的存储交易平台。去中心化的存储，有个核心问题，怎么证明存储提供方，真实有效的存储了指定的数据。Filecoin是通过PoREP以及PoST算法实现的（其中就包括零知识证明）。PoREP是数据存储证明算法（证明用户数据被正确的处理）。PoRep算法的全称是ZigZag-DRG-PoRep。

每一层的输入称为d（data），每一层的VDE的结果称为r（replica）。对每一层的输入，建构默克尔树，树根为comm_d, 整个树的数据结构称为tree_d。对每一层的输出，建构默克尔树，树根为comm_r，整个树的数据结构称为tree_r。简单的说，PoREP通过零知识证明，证明每一层的数据都经过VDE计算生成，并提供最后结果的Merkle树的树根。在数据处理并存储后，每隔一段时间，需要提交存在性证明，也就是PoST算法。PoST算法的基本思想，随机挑选一个Merkle树的叶子节点位置，需要提供出一条Merkle路径的零知识证明。

这个零知识证明的第二个应用方向：链上数据压缩。PoREP算法，通过零知识证明证明数据已经正确处理，并提供了处理后数据形成的Merkle树的树根。PoST，每隔一段时间，随机抽选一个叶子数据，需要存储提供者在一定的时间内提供从该叶子数据到Merkle树根的路径证明。如果，处理完的数据没有保存在一个可靠的存储上，无法在合理的时间内重建整个Merkle树，也就无法提供证明。

第三个场景：Loopring DEX 3.0项目

从2017年，路印从“环路撮合”的最初设计，经过了1.0，2.0以及3.0的三个大的版本的协议升级。1.0/2.0，相对来说，受限以太坊本身性能的限制，交易流程复杂，体验和中心化交易所相比，有较大的差距。路印协议3.0，通过零知识证明技术（ZKP），在zk Rollup的基础上，结合DEX的业务场景开发设计，兼顾去中心化和交易性能。

相对1.0，2.0来说，路印协议3.0采用零知识证明（ZKP）技术，将所有的撮合逻辑都在链下完成。每一笔撮合（Settlement）都会生成证明并提交到链上，证明链下的撮合正确无误。路印协议采用和以太一致的“账户”模型，所有的账户的“状态”（余额）都记录在链下。所有和状态相关的操作，都是在链下更改，提交Proof到链上记录。因为存在链上链下的状态同步，账户的任何操作有三个状态：

1. Committed （操作已经提交）

2. Verified （该操作已经提供了相应的Proof）

3. Finalized（之前的所有的操作都已经提交正确的Proof）

以用户Deposit“充值”的操作为例：

Account是一层，Balance是一层，Trade History是一层。这几层一起组成了整个账户链下的状态。

路印3.0，采用的是zkSNARK的Groth16算法提供零知识证明。针对每种操作，Relay都会提供对应的ZKP证明电路。以链下撮合为例，相应的电路证明的逻辑如下：

其他还有一些有意思的项目：

Coda（零知识递归证明）

Mixer（混币）

zkPOD（通过零知识证明实现通用数据的交易）

五、零知识证明开源仓库及介绍

下面介绍几个热度比较高的零知识证明实现仓库及其源码分析文章，很多的零知识项目都是基于这几个仓库的代码做的。

libsnark

libsnark 是实现一个 C++ 版本的零知识证明库。

仓库链接：https://github.com/scipr-lab/libsnark

源代码分析：https://mp.weixin.qq.com/s/UHqpfl6ImVwa4HtsiksqJA

实战：https://zhuanlan.zhihu.com/p/46477111

bellman

bellman是Zcash团队用Rust语言开发的一个zk-SNARK软件库，实现了Groth16 算法。

仓库链接：https://github.com/zkcrypto/bellman

源代码分析：https://mp.weixin.qq.com/s/NvX11tNSEpV1DR-3PwpIAQ

snarkjs

snarkjs是实现一个 javascript 版本的零知识证明库，实现了 Groth16。

仓库链接：https://github.com/iden3/snarkjs

六、zkSNARK安全问题

• zkSNARK 合约「输入假名」漏洞致众多混币项目爆雷
• 硬核！360高级安全专家彭峙酿以Zcash为例，谈零知识性证明的安全和隐私问题
• 如何利用 Groth16 的漏洞伪造证明

七、参考资料与补充

参考资料

Shafi Goldwasser

Silvio Micali

零知识证明初探

初识「零知识」与「证明」

零知识证明学术网站

零知识证明：抛砖引玉中文版part1

零知识证明：抛砖引玉中文版part2

白话零知识证明

零知识证明学习资源汇总

零知识证明 – zk-SNARK应用场景分析

零知识证明隐私保护原理

补充

看过诸多资料后，这里我想推荐两个个人认为很不错的零知识研究大佬的公众号：

安比实验室

星想法

另外就是物质实验室的github仓库：

https://github.com/matter-labs/awesome-zero-knowledge-proofs

补充两篇文章

零知识证明：从入门到实践

zkSNARKs白皮书

来源：KAZIMIYA