SCRY区块链知识讲堂 第12讲：零知识证明（ZKP, Zero Knowledge Proofs）

前言：零知识证明是一种特殊的交互式证明，其中证明者知道问题的答案，他需要向验证者证明“他知道答案”这一事实，但是要求验证者不能获得答案的任何信息。

来源：pixabay

当今密码学世界中最酷炫的一件事，莫过于那些优美又神秘的专有名词。“零知识”就是这样一个热词，受尽追捧。

可太过受欢迎也未必是件好事，俗话说，人怕出名猪怕壮，因为“零知识”的概念如此吸引眼球，以至于导致了许多的错误理解和误用。许多人将零知识和“非常非常安全”划上了等号，还将它与加密系统或匿名网络联系起来——这些东西实上与真正的零知识协议毫无关系。

零知识证明是密码学家设计出来的最强大的工具之一，但同时，理解它的人也不多。今天，我将试着以通俗易懂的表达方式来介绍什么是“零知识证明”，并解释到底是什么让它如此特别。

一、零知识的起源

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

Shafi Goldwasser, Silvio Micali and Charles Rackoff|维基百科、IACR

零知识证明这个问题不是单纯的理论思考，而是在真实、具体的应用中，会面到临的问题。

我举个例子，在现实生活中，大家用账号密码的方式登录微信、微博等社交软件时，在输入密码后，APP会把你的密码发送给服务器（当然，这里应该会加密后再发送的），然后和服务器中的密码进行比对，一样的话，就可以成功登陆了。

可这里有个问题。大家发现了吗？实际上，服务器知道我们的密码。

大多数系统就是以这样糟糕的方式进行“证明”的，因此，如何保障密码安全呢？可能只有祈祷服务器不会遭受攻击了。

二、一个“真实世界”的案例上面那样讨论，可能还比较抽象。为了让大家能有更具体的概念，现在我们举个“真正的”零知识证明例子。请大家配合我想象一下，现在我是一个电信业巨头，跟随“一带一路”，积极参与到非洲地区的电信网络建设中来。现在我要部署一个新的蜂窝电信网络。（这里我还是解释一下为什么叫蜂窝网络吧。大家看下面第一张图，是移动网络拓扑图，有没有很像下边的蜂窝呢？对！名字就是这样来的）蜂窝网络作者：Mozzerati|维基百科https://zh.wikipedia.org/wiki/%E8%9C%82%E7%AA%9D%E7%BD%91%E7%BB%9C#/media/File:Frequency_reuse.svg

真正的蜂窝?作者：umsiedlungen|Pixabay

而今天为了方便讲述，把网络架构图这样展示，如下。图中的每个顶点代表一个无线电塔，每一条连线代表无线电塔信号两两重叠的区域，这意味着连线上的信号会互相干扰。（相邻两个电塔（小区），信号频率相同，产生的同信道干扰）。

为了避免这样的干扰，在设计网络架构时，我就想到了用三种不同的频率来部署。不过现在，我有了新的挑战！这个挑战来自我该如何部署不同的频率，使得相邻的每两个电塔不具有相同频率。我们现在用不同颜色来表示不同频率，可以很快找到一种解决方案如下图所示。可能有很多了解过的朋友已经发现，我刚才讲的就是著名的算法问题——三色问题。大家也就知道，这个问题有趣的地方在：某些非常庞大的网路中，我们很难找到解，甚至连证明问题有解都办不到。如果只是上面给的这种示例图，我们用手就能轻松找出解。但如果今天我的无线通信网络规模特别复杂而庞大，我以我所能调配的计算资源都无法找到解答的情况下，我该怎么办？我还可以把这个问题“外包”给拥有更庞大算力的人呀！比如去找谷歌帮忙啊。但这又会导致一个问题。谷歌找到了有效着色方法，因此耗费了大量的算力。不过在我得到有效方法之前，我是不打算付钱的。同样，谷歌在收到钱之前，也不会愿意给我着色方法的副本的。以此，我们双方陷入了僵局。（这里不讨论现实中情况，毕竟律师和账户托管可以解决。但我们今天是来表述密码学的，所以解决困境，需要疯狂一点的技术手段。）

三、一种疯狂的技术手段现在有一个大仓库、大量的蜡笔和纸张。哦，对了，还得有C位选手——帽子！下面是运作原理。1、我进入仓库，在地板上铺满纸张，并在空白的纸上画出电塔图；2、谷歌工程师进来，蜡笔中随机选三种颜色，然后照着他们已经算出来的解决方案进行着色（颜色不重要，方案有效就行）。着色完成后，每个纸上的电塔用帽子盖住，然后离开仓库。我回到仓库，看到下图。很显然，谷歌的方案我是看不出来的，我也不知道他们的方案是否有效为了消除我的疑虑，谷歌工程师告诉我，可以随机选择其中一条线，然后要求他们揭开对应的帽子，这样我就能看到他们着色方案的一小部分了。如下所示。谷歌工程师方案没问题的话，这两种颜色一定是不相同的。但我这时候会想，万一只是碰巧呢？在目前条件下谷歌仍有很大的可能是给了我一个无效的着色方案。假设一共有X条边，在仅仅是经过以此揭开帽子的观察后，我仍有高达 (X-1)/X 的概率被骗。好了，谷歌也不想浪费了大量算力的方案，却得不到付款。就让我再一次，重新进行观察。刚刚的运作原理，谷歌工程师再按照方案做一遍，只是蜡笔的颜色，换了。我这时候再随机选择一条线，然后谷歌工程师揭开帽子，进行验证。这次情况会好些，我对他们有了更多的信心，但骗我的概率依然存在，概率为 [(X-1)/X]* [(X-1)/X]（在1000条线的情况下，大约有99.8%的可能性，还是比较高。）不过好在，这个挑战可以一直进行下去，不断重复以上操作，直到我们相信为止。不过还是别这样了，太麻烦了，这时候还是写段代码来验证以上逻辑更加方便。事实上，我被骗的概率是一直存在的，但我可以把这概率降低到一个程度（进行X^2次挑战），那时候，谷歌只剩下微不足道的概率可以骗我，这概率低到我大可以放心付款。

来源：pixabay

在这整个过程中，不只有我需要保护，谷歌也需要。所以，在我进行“无数次”挑战时（随机选出一条线来验证的过程），我是无法推敲谷歌耗费了大量的算力得出的着色方案的，因为每次验证后，他们都会换三种颜色。我获得的信息，对我来说，毫无帮助，每次挑战的结果也无法被串联起来。这就是零知识证明。

四、零知识证明特性零知识证明有三个特性，任何零知识都必须满足。简单来说：1、完整性(Completeness)。如果谷歌说的真话，那么他们最终能说服我（至少让我相信可能性非常高）。2、安全性(Soundness)。只有当他们说的是真话时，谷歌才有可能说服我。3、零知识性(Zero-knowledgeness)。我无法从中获得任何关于谷歌解决方案的信息。来源：pixabay

五、区块链上的零知识证明

比特币和以太坊都是用公共地址来代替当事方的真实身份，使交易部分匿名，公众只知道发送和接收的地址以及交易的数量。然而，可以通过区块链上可用的各种信息（如交互记录）找出地址的真实身份，因此存在暴露隐私的可能。零知识证明，可以在发送方、接收方和其他交易细节都保持匿名的情况下，保证交易有效。ZCash可能是成功实现零知识证明的最著名的区块链项目之一。Zcash实现了ZKP的修改版本，被称为zk-SNARKS，代表Zero-Knowledge Succinct Non-Interactive Argument of Knowledge（零知识简明非交互式知识证明）。具体技术细节，大家可以自行查看哦。关于零知识证明，还有一个非常经典的例子，可以更好的帮助大家理解：阿里巴巴被强盗抓住，为了保命，他需要向强盗证明自己拥有打开石门的口令，同时又不能把密码告诉强盗。他想出一个解决办法，先让强盗离开自己一箭之地，距离足够远让强盗无法听到口令，足够近让阿里巴巴无法在强盗的弓箭下逃生。如果强盗举起左手，阿里巴巴就使用口令将石门打开，如果举起右手，就将石门关闭。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。如果每次都能正确打开和关闭大门，则证实阿里巴巴确实知道石门的密码。这个整个过程就是零知识证明，即证明者能够在不向验证者提供任何有用信息（石门的口令）的情况下，使验证者相信某个论断（阿里巴巴知道打开石门的方法）是正确的。好了，关于零知识证明就说到这里了，全文试着用两个例子来试图向大家说明什么是零知识证明，希望大家看了之后，能对零知识证明有一定了解。

延伸阅读The Incredible Machine（来自：Medium作者：Aviv Zohar）https://medium.com/qed-it/the-incredible-machine-4d1270d7363a

参考1、 交互式证明系统（维基百科）https://zh.wikipedia.org/wiki/%E4%BA%A4%E4%BA%92%E5%BC%8F%E8%AF%81%E6%98%8E%E7%B3%BB%E7%BB%9F#%E9%9B%B6%E7%9F%A5%E8%AF%86%E8%AF%81%E6%98%8E%EF%BC%88Zero-knowledge_proofs%EF%BC%89

2、A?Few Thoughts on Cryptographic Engineering（Matthew Green，约翰·霍普金斯大学的密码学家、教授）

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

3、A Few Thoughts on Cryptographic Engineering, Part 2（Matthew Green，约翰·霍普金斯大学的密码学家、教授）

https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/

4、一文读懂区块链中的零知识证明（BFTF技术社区联盟）https://www.odaily.com/post/5133827

—-

编译者/作者：scry

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。