零知识协议（三）：何为交互系统
P=NP?
在上一篇文章中谈到了交互式证明中，验证任务的复杂性与定理证明任务的复杂性之间的不对称性构成了交互式证明系统的基础，而这个不对称性可以通过一个称为NP的复杂类刻画出来，有的文献资料也将NP类视为一类证明系统，对于任意语言L∈NP，都有一个形如x∈L的结论证明的有效验证过程
说得稍微简单一点，就是实践中想要证明的所有论断都可以表述为是否是NP中的成员的声明
在基于NP类构建简单的零知识交互系统之前，先简单介绍一下P类与NP类
- P类（Polynomially Class）：P类是一个DTM（确定型图灵机）在多项式时间内可判定的语言构成的类
- NP类（Nondeterministic Polynomially Class）：NP类是一个NDTM（非确定性图灵机）在多项式时间内可判定的语言构成的类
P类和NP类似乎只差了一个字母N，但实际上这两个概念有天壤之别（至少从计算复杂度的角度来说是这样的），对于上述的表述，咱们将概念拆解开来讲解
首先是多项式时间，通常多项式时间指的是在最坏的情况下的运行时间不超过给定输入的一个先验多项式，这个概念一时半会儿讲不清楚，碍于篇幅有限不在此展开讲（其实是懒），可以很不严谨地将多项式时间理解为很容易地，就可以了
其次是判定，对于一个语言属于这个类，判定的意思是接受还是拒绝这个语言属于这个类，简而言之就是，我说了一句话，由你来判定我说的是真话还是谎话，如果你认为我说的是真话，就意味着你接受我的这句话，否则拒绝我说的这句话
然后是确定型图灵机（DTM，Deterministic Turing machine）与非确定型图灵机（NDTM，Non-Deterministic Turing machine），两者都是图灵机，区别在于确定型图灵机的每一步都是唯一确定的（状态转移唯一），对于这样的图灵机，只要每次都向其提供一个相同的输入，其运行完毕后总会得到相同的输出（相同输入下，其判定的结果总是相同的），而非确定性图灵机是一种在某个时刻可能存在多个步骤的图灵机（状态转移不唯一），此时NDTM可以随便选择一个步骤，并按照选择的步骤继续往下执行，依此类推直到运行结束，因此两者的区别在于：对于某个时刻，其下一步的操作是否是唯一的
可能这么描述过于复杂了，简而言之就是，NDTM在计算一个问题的时候，它可以一直猜（随机选择状态转移），直到猜到你想要的那个答案为止，需要注意的是，猜的时间要在多项式时间内
然后把多项式时间的概念和图灵机捏起来，之前对于P和NP的表述可以大致地转化成下面这样
- P中的语言可以被
很容易地算出来 - NP中的语言可以被
很容易地猜出来
可以结合下面这个图来理解一下，NDTM的计算树中的每一步都有多个可能，依此类推，直到叶节点
但是如果把NP的每一种可能都列出来，然后再让DTM去算不也可以吗？
确实可以，但是请注意之前的表述，说的是一个DTM可判定，注意一个，如果说把NDTM能猜到的所有可能的结果都列出来（也即列出上图中NDTM所有的由根节点出发到叶节点的路径），那时间就不是多项式时间了，因为NDTM在某个步骤时，它的下一步可能有多个（至少两个）可选的执行步骤，此时可能不再是我们期望的多项式
但是区别在于如果说我事先选定了NDTM的一个运行分支（上图中由根节点出发，到某一叶节点的一条路径），那我们可以用一个DTM来运行这个分支（也就是用DTM来判定这个语言），因为这个分支每一步都是唯一确定的，因此如果用DTM判来定，它可以很容易地算完，并验证这个分支是否正确（接受或拒绝）
既然DTM不能很容易地求解NP问题中所有的分支，但是DTM又可以很容易地求解其中的某一个分支，那是不是可以再将P和NP的表述再改一下
- P可以由一个DTM
很容易地判定 - NP可以由一个DTM
很容易地验证
这里判定和验证可能表述的不是很清楚，直白一点的表述就是，对于一个问题，如果他是P类问题，那我可以很容易地算出满足问题要求的一个结果，如果他是NP类问题，我可以很容易地检查某个已知的是否满足题目的要求
对于上述的内容，组成了目前世纪难题之一，P?=NP，也即NP是否也可以很容易地算出来，当然这就是题外话了，不是本系列讨论的重点
在基于NP问题可以很容易地验证的基础上，回到我们之前提到的证明与验证任务的不对称性，因为求解NP问题是一个很难的过程，但是又可以很容易地验证其结果，因此就可以用NP问题构造交互式证明系统
举一些P问题和NP问的例子可能会有助于帮助理解
P问题：冒泡排序，快速排序，图的欧拉性判定
NP问题：大合数素因子分解，旅行商问题
因此基于NP问题可以构建一个交互式证明系统，或者零知识交互系统，什么是交互系统呢，接下来简单介绍一下
交互式证明系统
对于本节的内容，打算先写一些比较严谨的定义，然后再转换为简单的理解，先从Goldwasser、Micali和Rackoff三位大佬定义的交互式证明系统的计算模型开始讲起
交互式证明系统（Interactice Prove Systems，IP），其基本模型可以表示为(P,V)，其中P是示证者，也就是之前提到的Prover，V为验证者Verifier，在一般情况下，协议(P,V)用于证明一种语言的成员归属命题（也就是上面说的NP问题，用图灵机判定一个语言的归属问题），其中语言在{0,1}^*^上
然后设L是{0,1}^*^上的一种语言，对于成员归属实例$x\in L $，P和V必须共享输入x，因此x称为公共输入，证明实例以(P,V)(x)表示，P和V通过通信信道联系，并通过过其进行交互，交换一系列的信息，这些信息表示为$a_1,b_1,a_2,b_2,...,a_l,b_l$，这一系列的信息称为证明副本，其中包括P所传输的信息，即示证者副本，还有验证者的副本，两者的副本长度均为l，且每个元素|a~i~|和|b~i~|都关于|x|的一个多项式有界，证明实例需要在关于|x|的多项式时间内终止
一旦协议终止，输入应该是accept或者reject，分别代表对于P声称的x∈L，V接受或者拒绝，也即$(P,V)(x)\in\{Accept,Reject\}$
需要强调的是，(P,V)是一个概率系统，对每个x而言，输出值(P,V)(x)是关于公共输入x、P的秘密输入值、P和V的一些随机输入值的一个随机变量
然后接下来是形式化定义一个交互式证明系统
设L是{0,1}^*^上的语言，IP协议(P,V)称为L的一个交互式证明系统，如果
$$ Pr[(P,V)(x)=Accept\ | \ x\in L]\leq ε \\ 且\\ Pr[(P,V)(x)=Accept\ | \ x\notin L]\leq \delta $$
其中，参数ε和δ满足
$$ ε \in(\frac{1}{2},1 ] \ \ ,\ \ \delta \in [0,\frac{1}{2}) $$
概率空间为(P,V)的所有输入值和P与V的所有随机输入值，其中参数ε为(P,V)的完全性概率，其含义为如果有$x\in L $，则V将至少以概率ε接受该证明，δ称为(P,V)的正确性概率，也即如果$x\notin L$，则V将至多以概率δ接受该证明
好了，说了一大段话，看起来好像很复杂，其实一点都不复杂，简单归纳一下，记住下面这几个概念就好了
- 示证者Prover记为P，验证者Verifier记为V
- P和V有一个公共输入，记为x
- P和V交换的信息记为证明副本
- 对于交互结束后，系统输出Accept或Reject
- 如果P是诚实的（P声明$x\in L $且确实有$x\in L $），则V接受P的说法（系统输出Accept）的概率大于1/2
- 如果P是恶意的（P声明$x\in L $，但实际上$x\notin L $），则V接受P的说法（系统输出Reject）的概率小于1/2
可简单了是吧
虽然定义上写的两个参数的界都是1/2，但实际上可以证明是1/2的关于|x|的任意多项式次幂，也就是下面这个式子
$$ 2^{-poly(|x|)} $$
不懂不重要，知道有这么回事就行，如果对证明感兴趣的话，可以看Goldreich大佬亲自写的这本书Foundations of Cryptography Basic Tools$[3]$，这里不再废话了（其实是我看不懂)
讲了这么多太理论的的东西，讲点比较实在的吧，现有的交互式证明系统采用的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问题（或者NP-hard问题，NP-C问题）构建一个零知识交互系统
但是在构造过程中，需要万分小心，以防止知识的泄露，不难发现，上述介绍的三个例子，Bob每次都只能在Alice给定的任务中选择其中的一项让Alice完成（G3C是|E|条边选1，哈密顿图是2选1，数独是3选1），因此Bob每次都只能从Alice那里收到一些关于她的知识的一些信息，然而每次Bob与Alice交互时，Alice都要重新打乱她的知识，从而Bob每次得到的信息都不足以让他拼凑出一个知识
而最后让Bob相信Alice拥有知识的是多次执行后，将Alice欺骗他的概率降低到一个可以忽略的数，因此实际上Alice和Bob之间需要很多次的交互
那问题来了，有没有什么方法可以降低交互的次数呢，或者说得更绝对一些，有没有什么方法可以使得Alice和Bob之间不产生交互，就让Bob相信Alice拥有某些知识，实际上是有的，称为NIZK，非交互式零知识证明系统，在之后的文章慢慢介绍
后记
这篇博客写的比较长，感觉自己理解了这些内容，但是没有表述清楚，尤其是前两节内容，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]$.西安电子科技大学出版社.