阿里巴巴和三染色
阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个地图三染色游戏才能获得宝藏，阿里巴巴知道地图如何三染色，四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道地图三染色的方法呢？
聪明的阿里巴巴很快发现了证明方法：
阿里巴巴先将红绿蓝随机分配三个数字，之后将数字写在纸片上，面朝下盖在地图上。阿里巴巴可以让四十大盗随机选择两个临近的区域进行检验（Verify），翻开盖着的纸片，查看纸片上的数字是否不同。然后阿里巴巴重新给红绿蓝分配三个数字，重复上述的步骤。最后，阿里巴巴可以向四十大盗证明，如果他不知道染色方案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗地图如何染色的情况下，向四十大盗证明了自己知道染色方案。
有的地图是可以三染色的，例如左图；而有的地图无法进行三染色，例如右图。三染色是NPC（NP Complete）问题，NPC问题在多项式时间内可以检验，但不能在多项式时间内求解，并且所有的NP问题都能在多项式时间内规约到NPC问题，NPC问题在zk中起到了重要作用。
阿里巴巴和哈密尔顿回路
这个是瞎编的……但下文确实会出现哈密尔顿回路的故事，寻找哈密尔顿回路也是一个NPC问题（跟三染色一样）。
什么是知识
Goldwasser等人在1985年zk的开创性论文「The knowledge complexity of interactive proof-systems」中对「知识」的定义是「the output of an unfeasible computation」，从中可以提取到两个关键词「output」和「unfeasible computation」。
- 首先，「知识」必须是一个「输出」，不能将我们藏在心里的「信息」称作「知识」；
- 其次，「知识」必须是关于「unfeasible computation」的，否则验证者（Verifier）根本不需要阅读证明者（Prover）的「输出」，如「1+1=2」这种常识，不能说验证者看到证明者输出「1+1=2」，验证者就获得了「知识」，因为即使验证者不看到输出，也能够自行算出「1+1=2」。
什么问题算是「unfeasible」呢？在zk中，一般说NP问题是「unfeasible」。
图灵机
在解释P和NP前，需要先说明「图灵机」。计算机的先驱图灵构想了一种「单带图灵机」，这种机器只执行两种操作：
- 在一条纸带上写上或擦除某个符号；
- 将读取位置，从纸带的一处移动到另一处。
基于这个思想发展出来的机器，被称作图灵机，也称「确定性图灵机」，例如我们日常生活使用的个人电脑；而「不确定性图灵机」在现实并不存在，这是一种理想的产物，为了帮助我们理解NP问题，「不确定性图灵机」在遇到「if - else」等分支语句时，能够同时计算所有的分支。
P&NP
如上图所示，「NP问题」，是确定性图灵机在多项式时间内可以验证的问题，也是不确定性图灵机在多项式时间内可以求解的问题（但这种机器并不存在），例如在上文提到的「阿里巴巴和三染色」中，给定一种涂色方案，确定性图灵机（四十大盗）能够较快地完成验证；而「P问题」是在多项式时间内可以求解的问题。显然「P属于NP」，因为能在多项式时间内求解，一定能在多项式时间内验证，但「P是否等于NP」，依然是一个谜，不过目前大多数科学家选择信仰「P不等于NP」。
观察上图，能帮助理解「知识」的含义，当验证者面对「NP」问题时，如果没有看到「蓝色计算路径」，那么它无法在多项式时间内求解这个问题（因为现实的图灵机是确定性图灵机）；而一旦验证者看到了「蓝色计算路径」，那么它能很快地进行验证，这个「蓝色计算路径」就是「知识」。zk在证明过程中，不能透露关于「蓝色计算路径」的信息，因为一旦验证者看到了「蓝色计算路径」，它就同样能展示给别人看，以此冒充原本的证明者。
