区块链与密码学全民课堂第10-1讲：白话零知识证明

导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

【本课堂内容全部选编自PlatON首席密码学家、武汉大学国家网络安全学院教授、博士生导师何德彪教授的《区块链与密码学》授课讲义、教材及互联网，版权归属其原作者所有，如有侵权请立即与我们联系，我们将及时处理。】

10-1 零知识证明的概念

零知识证明（Zero—Knowledge Proof），是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。零知识证明必须包括两个方面，一方为证明者P，另一方为验证者V。证明者试图向验证者证明某个论断是正确的，或者证明者拥有某个知识，却不向验证者透露任何有用的消息。

零知识证明目前在密码学中得到了广泛的应用，尤其是在认证协议、数字签名方面。我们用举例的方式来简单地说明零知识证明的概念。

-数独解的零知识证明-

小明和小红很喜欢玩数独游戏，平日里他们相互给对方出题做。有一天，小明出了一道很难的数独题，可小红花了很长时间都没有解出来。于是，她就怀疑小明出的这道题没有解，认为小明再耍她。但是，小明信誓旦旦地说这个题有解，并且他知道这个解。小红就问“你怎么证明有解？”

那么小明要如何证明呢？

方法1：用数学模型来证明。缺点：复杂，难以理解； 

方法2：用正确答案来证明。缺点：小红知道答案了。

有没有一种方法，既能够让小红相信小明知道答案，又不告诉小红答案呢？

有，用零知识证明的方法来证明该数独题目有解。

下面，将展示小明的零知识证明方法：

步骤一：承诺

小明拿出81张空白的卡片，并按照解的排列将1~9中的数字写到卡片上。之后，将代表谜底的卡片，数字面朝下放在桌上；代表谜面的卡片，则数字面朝上放在桌上。

在此过程中，小红不能够偷看。（亦可以由小明预先准备好）

步骤二：随机挑战

在小明放好卡片后，小红想打开卡片揭晓谜底。但是，小明不允许，因为他不想让小红知道答案（通过承诺获取答案是不被允许的）。那么，小红就会质疑小明的答案，她会按照数独的规则来检验答案。如果答案是正确的，那么必然会满足规则：每行（row）/每列（column）/每个九宫格（block）是由1~9的数字组成，且不可重复。小红就按照以上的任何一种规则来验证。小红将其随机选取的验证规则发送给小明。

步骤三：响应

小明收到小红的验证挑战（不妨设验证规则为按行验证）后，他将每一行的卡片收集放入一个麻布袋中并打乱。所有卡片都被收完放在了9个麻布袋里。

小明接着把这9个麻布袋交给小红。（放卡片的过程是被小红监视的）

步骤四：验证

小红打开9个袋子，分别验证每个袋子是不是包含1~9的卡片。

• 如果全是，那么验证通过，即小明可能知道解。（是可能知道，而不是确定知道）

• 如果不是，那么验证失败，即小明不知道解。

小红问：这样就能证明？？小明可以事先准备9个这样的袋子啊。

小明答疑：袋子中卡片的打包是在我承诺的组合上完成的，我事先不知道你会选择哪个规则来验证。

如果我按照行规则准备了卡片，当你选列规则的时候，我就会失败的。也就是说，我不知道答案的话，我是可能失败的。

重复证明（Repeat Times）+零知识（Zero Knowledge）

小明与小红每执行一次上述的证明过程，小红都有1/3的概率抓获没有答案的小明。换而言之，小明没有答案并且通过小红验证的可能性只有1/3（即小明猜测到了小红要选择的挑战规则）。

但是，小红还是不服气。她觉得可能性太大了，于是她让小明重复证明n次，直到她觉得小明猜测成功概率非常非常，即1/3^n非常小。

问题：小红知道部分答案了吗？

小红答疑：这么多次试验下来，我还是不知道真正的题解。我只知道每次小明放置卡片的排列里很大几率每行每列每个九宫格确实都是没有重复的数字，这就说明很大概率这题是有解的，而且小明很大概率确实知道这题的解。

非交互式扩展（Non-Interactive ）

有了这个证明方法后，小明和小红就养成了通过零知识证明去证明给对方看自己知道某题解的习惯。

可是，新的问题来了。小明如何向所有人证明他的题解呢？让小红来挑战？那么，有人就会怀疑，小红配合小明来作弊。

于是，小明又发明了一个「零知识数独非交互式证明机」。

自动化证明，无需人为交互：

小明只要把卡片放在传送带上，机器会自动选择按行，或列，或九宫格来收取卡片，放到袋子里打乱顺序，然后把袋子通过传送带再送出来。然后小明就可以当着镜头的面拆开袋子展示里面的卡片。

挑战随机产生+非人为控制：

这台机器有一个控制面板，打开里面是一串旋钮，这些旋钮用来指示每次试验的选择（行，列， 九宫格）。

可信初始设置（Trusted Setup）

当然，还有很多喜欢「抬杠」的人。他们认为，这个机器是小明和小红做的，他们可以在里面设置后门，或者他们知道控制面板随机序列的方式。这样，小明也能够作弊。

没办法，小明只有开直播，让大家看到他如何安装这个机器的，并且公布机器的随机序列产生方式如何，只要观众怀疑的，小明都需要将其公开解释。这一过程，就可以称之为「可信任的初始设置仪式（trusted setup ceremony）」。

至此，一个比较完整的零知识证明方法构造完成。在此过程中，出现了零知识证明的一些概念：

• 证明：什么是交互证明系统？

• 什么是非交互式证明系统？

• 零知识：什么是知识？什么信息包含知识？

• 证明的安全属性包含什么？

•  保障系统可信的条件有哪些？

我们会在接下来的课程中解答，今天的课程就到这里啦，下节课我们将继续学习零知识证明中的概念，敬请期待！

同学们可以关注PlatON公众号，持续学习哦。我们下节课见啦。