零知识证明学习笔记：背景与渊源 | 火星科技帖

副标题：斯坦福学者的零知识证明学习笔记（一）

本文作者东泽是安必科技社区的小伙伴。 目前就读于斯坦福大学，研究方向为密码学。 本系列文章出自作者对斯坦福著名课程《CS 251：加密货币与区块链技术》的学习笔记。 该课程的讲师是密码学大师Dan Boneh。

上学期在斯坦福，我跟随 Dan Boneh 学习了区块链和数字货币相关的技术。 与以往的课程不同，今年的课程增加了一个新的章节，叫做零知识证明。 可爱的Dan和他的硕士phd Ben Fisch轮流给我们上课，用了两周的时间讲解完零知识zkSNARK的由来、概念和实现。

这两天期末考试结束后，复习的过程中我在脑海里一次又一次地重温整个班级，觉得最精彩的部分就是零知识证明。 趁着假期，总结一下，分享给大家。

前言

初稿写完，分享给朋友Proofread时，发现很多朋友反映背景知识不够。 所以我在开始之前添加了这个额外的部分，标记理解本文所需的背景阅读：

Merkle 树/Merkle 证明：

比特币交易：

UTXO模型：

一些基本的加解密概念：

看完序言，我们就可以开始正文了。

要说零知识证明真正走入大家的视野，还得从比特币说起。

比特币的缺点

如果你熟悉比特币，你应该知道在比特币网络上，每一笔交易都是公开的。

如果A想付给B一笔钱，那么A会用喇叭向全网宣布她要创建一个新的交易（Tx），这个交易的受益人是B的公钥（P2PK），或者a公钥的散列 (P2PKH)。 B只要看到这笔交易，就可以用自己的私钥进行数字签名，证明自己确实是公钥的拥有者，从而花掉这笔钱。

当A提交支付给B的交易时，作为网络旁观者的M，只能看到一串乱码地址aaaaa向一串乱码地址bbbbb支付x币。 然后B给C汇款的时候，只能看到bbbbb给ccccc汇了一笔钱。 我们可以看到比特币中的交易是强关联的。 虽然不知道是谁把钱发给了谁，但顺藤摸瓜可以发现很多交易链。

如果每个用户都乖乖地来回汇款，比特币其实还是比较安全的。

一旦用户识破，不想玩了，想去交易所套现，那么整个链条的交易信息就会暴露。 交易所通常有KYC（Know Your Customer）政策，每个用户兑换数字货币和法币都必须经过实名认证。 一旦C从ccccc地址提款跑路，交易所就掌握了bbbbb已经给C打款的事实，如果C涉嫌洗钱，这时候你只需要静静等待B提现即可，然后抓住它。

美国已经有很多公司在做比特币的交易链分析，比如Chainalysis。

想必到这里，大家也能感受到比特币的不足之处了：随机生成的支付公钥只是一种错觉（网名）。 你所做的一切都是完全可见的，完全没有隐私。 这就好比有人用自己的网名在贴吧发帖批评别人，然后有人用密保找手机号，再用手机号找注册的实名，所以是一个要充实的真理。

匿名与假名

我们对隐私的理解其实分为两种。

第一种是Anonymous，即用户不需要透露任何与自己有关的信息。 它就像学校里的忏悔墙。 你永远不会知道是谁写的，反正上面写了字。

第二种是假名（Pseudonymous），即用户通过自己创建的假名发布信息，比如贴吧。 如果不了解用户，就无法建立网名与真名的联系，也不认识发帖人。 是谁。

由此分析，比特币其实是一种假名机制：每个用户会随机生成自己的公钥（假名），通过公钥地址接收资金。 这就好比A/B/C/D这四个人分别化名小明/小红/二狗/小刚在网上匿名交易，只要D在任何一个环节（比如交易所提现）暴露身份，那么小明/小红/二狗和D的关系马上就要曝光了。

我们可以从这两种方式来探讨如何增强比特币的保密性。

CoinJoin增加隐私的方法

由于A给B的支付别人会看到，C给D的支付也会被别人看到，所以有人想到说干脆把四个人ABCD全部扔到一笔交易中。 因为比特币交易可以有多个输入和输出，旁观者会看到在一个交易中，aaaaa 和 ccccc 都投入了 x 个币，然后 bbbbb 和 ddddd 收到了钱。 这样即使交易所知道这些地址对应ABCD四个人，也很难分清谁从谁那里收了钱。

如果两组交易仍然太容易识别怎么办？ 二不够四，四不够八，依此类推。 将各人的交易结合在一起，混淆视听，无法追踪。 这是 CoinJoin。

CoinJoin的缺点是什么？ 事实上，混合多笔交易并不能完美防止人被别人抓到，只能说是降低了一路被抓到的概率。 还有一个很重要的一点，如果要混合AB和CD交易，那么他们的交易量必须是一样的。 如果A支付给B 10000个币，C支付给D一个币，我们只需要看输入和输出，就可以立即将一个CoinJoin交易拆分成两个独立的交易。 因此，混合匹配交易金额相近的交易也是CoinJoin实现时不可忽视的难点。

从上述分类来看，CoinJoin只是对现有比特币系统的一种风骚操作，其本质仍然是一种假名机制。

Confidential Transaction（私人交易/CT）

既然隐藏我是谁这么麻烦，人们开始思考：如果我们不隐藏交易涉及的公钥，我们也可以隐藏交易金额。 当A给B转钱的时候，即使B暴露了，全网也不知道A给了B多少钱。

如果这个操作能够实现，那么我们甚至可以用比特币来支付工资。 大家只能看到你每个月的工资到了，却不知道你赚了多少。

要实现该方法，首先要了解一种特殊的加密算法：同态加密。

一句话，同态加密是一种特殊的加密算法，可以让密文保持其原有的数学性质。

我们可以假设存在一种加密方法E，如果E是加法同态的，则E(a) + E(b) = E(a+b)。 相反，如果乘法是同态的，则 E(a) x E(b) = E(axb)。

由于本文是一篇关于zkp的科普文章，具体的实现方法我们就不详细了解了。 我们只需要明白，椭圆加密方程和RSA中的大数模都具有一定的同态性质。

佩德森承诺

转到隐藏卷的主题。 如果 A 的余额为 100 个硬币，并向 B 支付 10 个硬币，则交易如下所示：

结合上面提到的加法同态，如果我们有一个加法同态的加密方法E，我们可以将这个交易转化为：

只要第一个数等于最后两个数之和，旁观者看不到最后的交易量，但不得不承认，A确实把一部分钱给了B，然后一部分钱还给了A。 这种方法称为佩德森承诺（Pederson Commitment），它隐藏了数据本身，但证明了数据之间的关系。

负数漏洞

读到这里，有些朋友会发现一个巨大的漏洞：佩德森虽然承诺要证明数字之间的关系，但他并没有限制任何数字的取值范围！ 也就是说，A可以耍花招，提交一笔交易，说要付-100个币给B，然后“找”给自己200个币。 这样，等式仍然成立。 A可以用它无限印钱，从而破坏整个系统。

如何避免负数的存在？ 除了 Pederson 的承诺，我们还需要另一套证明来证明所有交易中的数字都是正数。 换句话说比特币模拟器，所有交易中的数字都被限制在从 0 到 2^256（正整数的最大值）的范围（Range Proof）内。

听起来并不难，最简单的方法无疑是公开所有这些数字。 但这违背了隐藏交易量的前提。 所以我们只好另辟蹊径，即不暴露原数，还要证明它们的特性（取值在0到2^256之间）。 这听起来像一个点吗？ 别着急，我们再来看一个问题。

所有权漏洞

在我们继续之前，我想快速指出这个协议中实际上存在一个巨大的漏洞：未知所有权。

了解比特币的朋友可能知道，在创建比特币交易时，需要提供输入交易的UTXO Txid，这样可以快速验证要付给B的A是否真的有钱。

但是现在，我们还没有提到任何关于指向之前交易的事情。 也就是说，因为全网都不知道A花了多少钱，所以A可以简单的把输入的数字改成几万、几万，然后全都叫给自己，偷偷给自己铸币。

如何解决这个问题呢？ 有两种选择。

第一种解决方案是继续引入比特币的交易机制，将上次私人交易的输出作为交易的输入。 这种思路有点像问题的转化。 我这次交易用的是上一笔交易的结果，所以只要上一笔交易没问题，我的交易也就没问题。

这是先有鸡还是先有蛋的问题，如何创建第一笔私密交易没有问题？

我们可以通过特殊的交易，将普通币转化为私人产出。 这个交易的输入是一个已有的交易id（比特币UTXO），然后输出就变成了私有输出。 通过这种方式，我们想到了最早的鸡蛋。 （ZCash的匿名交易就是这个原理）

第二种方案是证明A的输入确实属于A。在以太坊这样的系统中，有一个World State的概念。 世界状态是整个链上所有用户和智能合约当前的余额和状态。 一般来说，一个完整的节点会保留整个世界状态（规模较大），而轻节点只需要保存世界状态的Merkle Commit。

除了提交佩德森承诺和区间证明之外，我们还提供额外的证明来证明交易中输入的数字与A在原始世界状态下的余额是一致的。 我们可以使用 Merkle Proof 来实现这个证明。

但是如果我们直接提交Merkle Proof，所有旁观者都可以看到A的交易输入，这就违反了隐私交易的前提。 还是那句话：我们还是要借用上面说的神秘算法——它不仅可以隐藏答案本身（A的余额），还可以证明这个数确实属于世界状态。

ZCash：全匿名

当CT概念被提出时，很多人不满现状，不禁感慨：要是连自己的名字都能隐去就好了。

于是提出了ZeroCoin/ZeroCash的概念：基于CT，但增加了一种新的机制，可以使交易用户匿名。 这下吃瓜群众C真是惊呆了。 他看到网上漂浮着一串乱码，但他不知道那是什么，但他不得不相信这是真的。

ZCash是一种基于ZeroCoin/ZeroCash协议实现的数字货币，可以实现完全匿名交易。 在这里我不会过多介绍，但我仍然依赖旧的密码学工具：Pederson promises、区间证明、Merkle 证明，以及我们一直在谈论的黑魔法：那些不暴露答案本身的. 证明。

等了好久，终于要说重头戏了：这种本身不揭示答案的证明称为零知识证明。

零知识证明 (zkSNARK)

相信看完上面的大家对我们要解决的问题有了一个大概的了解。

我们想证明像0这样的数字之间的关系

在讲这个话题之前，我想换个思路，把这个话题分成两部分：零知识（zk）和证明（SNARK）。

按照惯例，先说定义和应用，再说说如何实现。

证明（SNARK）

让我们从证明开始。

SNARK的全称是Succinct Non-interactive ARgument of Knowledge。 这个名词由三个维度组成：

简短（Succinct）：证明本身要足够简短，最好验证证明是O(logN)甚至O(1)的复杂度。

Non-interactive：整个过程没有任何交互，也就是说prover可以把一串乱码扔到你的桌子上然后离开，你以后可以通过验证这串乱码来验证他的身份。 证明。

知识论据：这东西比较晦涩。 但大体的意思是，你要证明的东西必须能够表达知识（Proof of Knowledge）。 PoK的证明涉及到一个更抽象的概念——抽取器（Extractor）。 具体内容可以参考郭宇先生的文章。 但是一句话，你证明的东西是有价值的，是通过计算得到的，而不是去乱搞其他东西。

看完定义我们会发现仅仅能够实现SNARK就已经很强大了，尤其是在简洁性方面。

我们马上可以想到一个应用：如果第三方机构在自己的数据库中存储了大量（PB级）的数据。 如果政府机构要审计他们的数据库，确保每个数据点都没有问题，一般情况下，他们可能要逐行读取，读取每一PB的数据，看时间的尽头。 这时，SNARK突然出现。 O(1)或O(logN)的大小和时间充分证明了这个庞大的数据库中每条数据都没有问题。 想想都有点小激动。 大多数人认为这是完全不可能的：几千万个数字的准确性如何仅凭几个数字就可以验证？

留下悬念，以后再说。

零知识（zk）

让我们回到零知识（zero knowledge）。

事实上，零知识只是在这个 SNARK 证明的基础上增加了一个要求：整个证明本身不能透露任何与要证明的答案相关的数据。 官方对零知识概念的定义很晦涩，引入了模拟器（Simulator）的概念。 详细的介绍可以参考郭宇老师的文章，这里就提一下。 一句话，无论黑客在零知识证明中看起来多么聪明，他也提取不出任何与答案本身相关的信息。

回到这个政府审计数据库的概念，我们可以假设这个数据库就是公司的纳税情况。 政府必须保证税收数据必须准确，但对于企业来说，他们不希望检查人员看到他们日常的业务流程，因为这可能涉及商业秘密。 这时候光靠 SNARK 是不够的，我们需要 zkSNARK 来实现：

它可以证明我如实纳税，我不会向你展示我所做的每笔交易的详细信息。

零知识证明的应用

有了 zkSNARK，我们能做什么？

首先是可以实现上述隐私交易（Confidential Transaction）。 ZCash 的隐私交易机制是基于 zkSNARK 实现的。 这样一来，数字货币交易就变得更加安全。

第二个是我们可以利用这个技术更好的解决区块链效率的问题。 现在区块链扩容无疑有几种方法：牺牲共识强度来提高出块速度，启用侧链，或者类似于闪电网络的离线点对点通道。

其实还有一个思路叫Rollup。 Rollup的概念大概是主链负载太大，所以我们多开几个小服务器，也可以接收交易，做交易鉴权，然后把一段时间内积累的所有交易批量更新到主链。 但是，如果更新过程还需要向主链发送大量的交易信息，那么这个Rollup的意义就不存在了，也不会减轻主链的任何负担。 这时候SNARK就派上用场了：通过SNARK（可以是zk，也可以不是），Rollup服务器可以向主链提交一个很短的证明，证明大量的交易都是可以的，主链只需要按照 final 结果，加减一些 UTXO 就大功告成了。 通过ZK Rollup，我们可以大大降低主链的负载，将更多的验证外包给其他地方。

第三件事，我们可以真正实现对第三方的交易。

假设A是做机器学习研究的，但是没有好电脑，打算把训练模型的任务外包给B。三天后，B告诉A他跑完了，需要先让A付钱在为她提供训练有素的模型之前。 A 担心 B 没有诚实的训练模型，而是随机生成一些随机数并打包，所以他希望 B 在付款前向 A 验证模型。 B担心A拿到模型后偷偷抄袭，然后不给钱就直接拉黑他。

面对这类问题，传统的解决方案是委托第三方，或者在链上设计智能合约来完成数据和货币的验证和交换。 现在有了zkSNARK，B可以直接提交一个用于模型训练的zkSNARK给A，证明他真的老老实实跑了三天，没有作弊。 A 快速验证通过后，您就可以放心转账了。

第四件事，我们可以完全转移数据所有权。

假设银行的账户余额数据库是一个SQL表，那么1亿个客户就有1亿行记录。 每年，银行都需要花费大量资金来维护如此庞大的数据系统。 如果每个人都可以把自己的一行记录移动到本地，维护自己的账户数据，那么银行就不用花一分钱了。 银行之所以不这样做，是因为用户极有可能篡改自己的数据牟利，把100元变成100万。

zkSNARK 只能保证数据本身不会有问题。 我们可以想象一个分布式银行，每个人的存款余额都存储在自己的电脑里。 当A要给B转账时，她需要向全网提交一个zkSNARK来证明自己账户中的余额被正确扣除，从而保证A老老实实从自己的余额中扣除转账金额。 B入账时，也会提交一个余额增加对应的zkSNARK。

我们可以把这个概念应用到各个领域，社交网络、银行、健康、财务审计、企业税务等等。 通过zkSNARK比特币模拟器，服务商无需为大量数据的存储付费，用户也无需担心自己的隐私被窃取。

未完待续

由于篇幅原因，这次就到此为止吧。 想必看到这里，大家对为什么需要零知识证明以及零知识证明有多么强大有了更深刻的理解。

下一篇文章开头，我会写得更深入一点，主要讨论zkSNARK的具体结构。

PS：本文中零知识证明和zkSNARK互换使用。 但实际上zkSNARK只是比较经典的零知识证明协议之一，后面还会介绍很多其他的协议。