前言
上一篇文章中，讲了这么多太理论的的东西，讲点比较实在的吧，现有的交互式证明系统采用的NP问题有很多，主要有如下几个：图着色问题，图的哈密顿性判定，旅行商问题等等，接下来简单介绍一下前面两个，然后再讲一个比较好玩的
给你一些颜料吧——图的三染色问题
交互式证明系统的一个经典实现方式，就是图的三染色问题（Graph 3 Coloring，G3C）
首先需要说明的是，G3C问题是一个NPC问题，NPC问题指的是这个问题本身是个NP问题，且所有的NP问题都可以归约到这个问题（感兴趣的小伙伴可以查阅归约），也就是说G3C问题本身也是个NP问题，接下来简单介绍一下这个问题
给定一个无向图G=(V,E)，其中V代表图的顶点的集合，E为边的集合，现在对图中的每一个顶点染色，可选的颜色有三种，要求由每一条边确定的两个点所染的颜色不相同，比如像下面这个图
现在我们基于G3C问题来构建一个交互式证明系统，假设Alice是Prover的身份，Bob是Verifier的身份，现在Alice知道下面这个图的一个三染色方案，且要向Bob证明她知道这个方案，但是又不告诉Bob这个染色方案，接下来讲一下如何实现的
首先Alice先对这个图的顶点的颜色做一次随机变换，比如说将所有的蓝色都变成红色，所有的绿色都变成蓝色，所有的红色都变成绿色，这样Alice得到了一个新的图，相当于Alice得到了一个新的图的三染色答案（注意，只改变顶点的颜色，而不改变原来顶点与边之间的关系）
如果说初始的图是上面这个图，那么做完随机变换后就是下面这个图
做完变换之后，Alice拿纸片把所有的定点盖住，然后将这个新的图出示给Bob看，Bob看到的内容和下面这个图一样
然后Bob此时需要随机挑选他看到的这个图的一条边（注意，这里一定是随机挑选的，不能是Alice提前知道的），假设Bob挑选的是下面标为红色的这条边
接下来，Alice将这条边两端顶点的纸片打开，让Bob检查这条边两端的顶点的颜色是否是不同的，如果是，则本次检查通过，否则直接拒绝Alice
但是思考一个问题，此时Bob只看到了整个图的一条边，并没有看到所有的顶点的染色情况，因此Bob此时会认为，或许Alice只是随心所欲地染色，然后运气特别好，又让他选到了恰好颜色不同的那条边，但是其他的边存在重复颜色的情况
严谨一点的说法，这叫差错，因此Alice为了尽可能减小这种差错，使得Bob以一个极高的可能性相信Alice确实有这个图的三染色答案，因此Alice需要再次执行上面的步骤
因此Alice再次将顶点的颜色做一次变换，这次Alice将所有的红色变成黑色，所有的蓝色变成白色，所有的绿色变成红色，这样又得到了一个新的三染色答案，然后用纸片盖住所有的顶点，再次出示给Bob看，就像下面这样
然后Bob再次随机挑选一条边，检查边的两端顶点是否是不相同的颜色，如果是，则本次检查通过，否则直接拒绝Alice
这时候Bob会认为，一次是运气好，两次是巧合，那三次五次呢？八次十次呢？如果Bob头铁，他可以和Alice玩100次这个游戏，但是在每次游戏中，Alice作弊（或者说运气好）的概率会呈指数级减小，假设Bob经过了n轮游戏，此时Alice作弊的概率应该如下
$$ Pr[Alice不知道这个图的三染色答案]<(1-\frac{1}{|E|})^n $$
其中|E|代表图中边的数量，n为进行游戏的轮数，$(1-\frac{1}{|E|})$的意思是，因为每次Bob只检查了所有|E|条边中的一条，而整个图中还有|E|-1条边没有检查，因此Alice作弊的概率为$(1-\frac{1}{|E|})$
只要每进行一次游戏，则Alice骗过Bob的可能性会再次减小，直到减小到某个程度的时候，Bob可能就得重新考虑一下了，或许他得相信Alice确实有这个图的三染色答案，但是每次Bob和Alice进行游戏时，Bob总是可以获得一些关于这个图的信息，但是并没有获得知识（回顾一下之前讲的信息和知识的区别）
是不是很巧妙，确实，通过图的三染色问题来构建交互式证明是一个很好的方案，也比较容易理解，接下来讲一个进阶版的，需要用到图的哈密顿性
一条回到原点的路——哈密顿回路
首先介绍一下哈密顿回路与哈密顿图，不太清楚相关概念的可以看一下图论的知识
哈密顿回路：在图G中经过每个顶点一次且仅一次的一条通路，称为哈密顿回路
哈密顿图：存在至少一个哈密顿回路的图称为哈密顿图
回路的意思就是起点与终点是同一个点，哈密顿回路就是从某一点出发，经过每个点一次且仅一次，最终又回到这个出发点的一条路径
和G3C问题一样，图的哈密顿性问题也是一个NPC问题，可以用于构建交互式证明系统，需要注意的是，使用的是判定的是图的哈密顿性，而非判定图的欧拉性，因为判定图的欧拉性问题是一个P问题，只需要遍历每个点，检查该点的入度和出度是否满足某个关系即可，对于可以看到整个图的Bob而言，他可以自己检查这个图是否是欧拉图，而没有与Alice交互的必要，因此采用的是图的哈密顿性判定问题
接下来就讲一下如何基于这个问题构建交互式证明系统
首先Alice和Bob都共同知道一张图G（V，E），但是Alice知道这张图中存在一条哈密顿回路，也即Alice知道这张图是哈密顿图，但是Alice既不希望告诉Bob这条通路的具体走法，又希望向Bob证明他知道，因此Alice可以这么操作
Step1：首先将这个图G做一次随机置换，并对其顶点进行移动，改变其标号，得到一个新的图，记为H（或者说找到一个图G的同构H），然后将H发送给Bob
同构的意思可以简单理解为：随便拖动顶点，不改变顶点与边的关系，得到的一个新图，这个图和原图同构，比如说下面这两个图同构
感兴趣的小伙伴可以拿画图软件试一下，如何通过拖动右侧的图的顶点将其还原为左侧的图
Step2：此时Alice和Bob都知道两张图G和H，但是对于图G而言，Alice还知道G中的一条哈密顿回路，此时Bob向Alice随机的向Alice发出下面两个请求中的其中一个（只能一个，不能两个同时）
- Bob请求Alice证明G和H'同构
- Bob请求出示H中的一条哈密顿回路
Step3：根据Bob发起的请求，Alice完成对应的任务
- Alice证明图G和H同构，但不出示H上的哈密顿回路
- Alice出示H上的哈密顿回路，但是不证明图G与H同构
因为G和H同构的特性，G中存在哈密顿回路，则H中也存在相应的哈密顿回路，但是由于H不是G，因此如果Bob向Alice发起请求1的话，Bob可以看到原来的图，但是并不知道其存在哈密顿通路，若Bob向Alice发起请求2的话，则Bob能看到哈密顿回路，但是并不知道原来的图是什么（Alice出示的是图H中的哈密顿回路）
然后和之前一样的，一次是运气好，两次是巧合，只要重复执行上述三个步骤n次，且n足够大，则Alice欺骗Bob的概率就会变得足够小，使得Bob相信Alice知道这个图的一条哈密顿回路，但是需要注意的是，每次执行Alice都会重新对图G做一次随机置换，也就是Step1中的随机置换要重新做，确保本次置换与之前的置换不相同，否则Bob可能可以获得一些知识，做完随机置换后继续执行协议即可
虽然Alice不知道Bob会选择两个请求的哪一个，但是Bob每次只能选择一个请求，而每一个请求都只会向Bob透露一点信息
或许这个交互式系统涉及到一些图论的知识点，比较难懂，接下来再介绍一个简单一点的，更能帮助我们理解交互式证明系统
做个数独动动脑子
Alice和Bob都喜欢玩数独，这天，Alice给Bob出了一道9x9的数独题，但是Bob做了很久都没有做出来，Bob不相信，觉得这道数独题无解，觉得Alice在拿他开玩笑，但是Alice说：“其实这道题是有解的，而且我知道这个题的一个解，但是我打算用零知识证明的方式告诉你”
玩过数独的小伙伴都知道，数独需要玩家补全一个没有完全填入数字的表格，对于9x9的数独，将9x9个格子划分成9个3x3的小方格，向其中填入1~9这九个数字，并确保每一行，每一列，每一个3x3的小方格内均只包含1~9这九个数字，比如下面这个图就是一个数独题
Alice为了向Bob证明他确实有这个数独题的答案，他先将9x9=81张卡片，写上对应的答案，然后按接下来的步骤操作
Step1：Alice将81张卡片写上答案，并按照9x9的大小排列好，然后背面朝上出示给Bob看
Step2：Bob选择下列三个请求的其中一个（三选一）
- 请求Alice以行展示结果
- 请求Alice以列展示结果
- 请求Alice以3x3小方格展示结果
Step3：Alice根据Bob的请求，完成下列任务
- Alice将每一行的九张卡片，分别放入九个不同的布袋，并且摇晃均匀
- Alice将每一列的九张卡片，分别放入九个不同的布袋，并且摇晃均匀
- Alice将每一个3x3小方格的九张卡片，分别放入九个不同的布袋，并且摇晃均匀
Step4：Bob检查九个布袋，是否有且仅有九张卡片，且这九张卡片正好是写上1~9这九个数字，且无重复
和之前一样，Alice事先不知道Bob会选择以何种方式展示结果，但是由于Alice将卡片背面朝上放置，且每次装入布袋后摇晃均匀，Bob也不知道原始的卡片是如何排列的
由于Bob每次请求Alice都是三选一，每次Alice可以成功骗过Bob的概率都是1/3，Bob还是会认为，一次巧合，两次运气好，重复这四个步骤足够多次，就可以将Alice欺骗他的概率降到一个可以忽略不计的数，从而使Bob相信Alice知道这个数独题的答案
后记
这篇博客写的比较长，感觉自己理解了这些内容，但是没有表述清楚，尤其是前两节内容，NP问题和交互式证明的部分
研究生上过的每一堂课，老师都会说，看懂了不一定真懂了，能讲明白了才是真的懂了，这个角度看来，我确实没有真的懂了
写博客好难啊，尤其是这种有点hardcore的内容，陈原教授的计算复杂性[7]，开学看到现在，看了好久没怎么看懂，计算理论属实难懂，但是又是整个计算机科学的基石，还得花时间啊
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
[1] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.
[2] 初识「零知识」与「证明」—— 探索零知识证明系列（一） - 知乎 (zhihu.com)
[3] （英）Wenbo Mao著；王继林，伍前红等译.现代密码学理论与实践[M].北京：电子工业出版社.2004.
[4] （以）Odeb Goldreich著；温巧燕，杨义先译.密码学基础[M].北京：人民邮电出版社.2003.
[5] 计算复杂性（6）——世界难题：非确定型图灵机，NP类 - 知乎 (zhihu.com)
[6] 零知识证明系列（0）：从数独游戏说起 - 知乎 (zhihu.com)
[7] 陈原.计算复杂性理论导引[M].西安电子科技大学出版社.