前言
对于模拟的概念，在之前番外篇就已经提到，嫉妒的记者在不知道洞穴咒语的情况下也拍出了和米克·阿里相同的效果，这个过程就是模拟
这几天理顺了模拟的概念，打算好好讲一下模拟，因为这是一个零知识协议离不开的概念
模拟器与零知识
在介绍模拟之前，先讲一下安全性的定义
假设存在一个理想世界（Ideal World），理想世界中有一个可信第三方，用户将需要计算的数据交给这个可信第三方，可信第三方计算完成后会将结果返回给用户
而真实世界中，事实上是没有这种绝对理想的可信第三方的，即便如微信支付宝，他们只是某种程度上的可信，并以他们的某些资产做担保，使其不能失信，从而达到相对的可信（注意理想世界中是绝对的可信）
真实世界中，用户会完成某些交互，比如交换部分数据，并通过约定好的协议来完成某种计算
而对于理想世界中的攻击者，他可以获取到一个甚至是多个用户的输入和输出信息，对于真实世界中，攻击者可以获取到入侵用户的输入和输出，同时还能获取到交互过程中得到的信息
则从攻击者的角度来看，若真实协议泄露信息不超过理想协议中允许的信息，则称协议是安全的
对于理想协议允许泄露的信息，可以通过模拟器计算得到
在有了模拟器的概念之后，我们认为，从真实协议攻击者的角度上来看，若模拟器提供的信息视角，与真实协议提供的信息视角不可区分，则我们称协议是安全的
这么介绍似乎有些抽象，这里引用郭宇大佬的文章$[1]$的说法来介绍
假设存在理想世界与真实世界，真实世界中的Alice拥有一个图的三染色方案（拥有知识），而在理想世界中，Alice被替换成了一个长相与声音一模一样的个体，我们称替身为Zlice，且Zlice没有知识（有点类似于番外篇中替身演员的行为）
此时，把Bob同时放入这两个世界中，但是Bob并不知道自己当前位于哪个世界，因为他面对的无论是Alice还是Zlice，至少从外貌等方面无法区分
Bob在与Alice或Zlice经过n轮交互后，发现对方都没有作弊，也就是说，位于两个世界中的Bob都认为对方没有欺骗自己，Bob都认为两个世界中的对方拥有知识，从而Bob无法区分自己当前到底是位于理想世界还是现实世界（因为他无法区分自己在与Alice和Zlice两者中的谁进行了交互）
从而引出了零知识的另一个说法：Zlice在没有知识的情况下与Alice不可区分，则协议是零知识的
这里有一个前提，理想世界是算法可构造的，这个算法除了拥有Alice和Bob的公共输入外（公共输入为三染色方案中的图），没有知识作为额外输入，也即零知识
如果真实世界的Alice泄露了信息，则Bob可以立即区分出真实世界与理想世界，因为理想世界的Zlice没有知识，而真实世界的Alice有知识，又因为理想世界与真实世界不可区分，因此可以得出结论：真实世界的Alice没有泄露知识
而理想世界中的Zlice就是模拟器，在理想世界中运行协议就是模拟
上述的说法似乎还是有点绕，简单来说就是，理想世界中的Zlice在没有知识的情况下，采用了某种方法让Bob确信了他有知识，则现实世界中的Alice一定也可以采用相同的方式来欺骗Bob
何为模拟
既然理想世界总的Zlice没有知识，那他要如何骗过Bob呢？
因为是理想世界，这里允许模拟器（也就是Zlice）有一个超能力，称为重绕（rewind），这个超能力可以理解为时光倒流，使得Zlice可以基于未来的一些信息决策现在需要进行的操作
如果不能理解的话，相信大家都玩过虚拟机，虚拟机的快照（snapshot）功能和rewind概念很类似，假设我们用虚拟机做实验，在某一步中某个参数设置错了，那我们就可以通过快照功能，恢复到之前的步骤，从正确的地方开始继续完成我们的实验，而且由于我们在之前的错误中知道了设置错误参数会导致实验失败，那么恢复快照之后我们就可以避免设置这个参数，如此反复多次，最终实验就可以成功
这就是rewind中所谓的基于未来的一些信息决策现在需要进行的操作，也是模拟器的成功欺骗Bob的关键所在
结合之前的图的三染色问题，来进一步的帮助我们理解rewind这个概念
首先，由于Zlice不知道这个图的三染色方案，因此他只能将所有的顶点全部染成灰色，然后用纸片盖好并交给Bob，就像下面这样
之后Bob依然随机选择一条边，假设他选择的是下面这条边
然后到Zlice了，无论是Alice还是Zlice，到这一步的时候，都必须打开Bob选择的边的两侧的顶点，由于Alice有这个图的染色方案，因此他可以毫不犹豫地打开这两个纸片，但是Zlice没有染色方案，而且纸片下面全部都被染成了灰色，一旦打开了纸片，Bob会立即拒绝Zlice
但是Zlice有超能力Rewind，此时他知道了Bob会选择这条边，那么他对Bob做一次Rewind操作，将时间倒回到染色之前
因为Zlice已经知道Bob要选择这条边了，所以在染色的时候，将这条边相连的两个顶点染成不同的颜色，然后再发回给Bob
此时Bob打开纸片后就不会拒绝Zlice了，因为这两条便确实是不同颜色的
如此重复多次，在超能力Rewind的帮助下，Zlice也可以在没有知识的情况下通过Bob的验证
但是这个过程存在一个问题，也就是在Rewind操作执行前和执行后Bob选择的都是同一条边，因此Zlice才可以通过验证
假如Rewind过后Bob选择了一条和之前不同的边呢，比如像下面这样，Zlice进行Rewind操作，然后将Bob选择的边的两个不同顶点染上不同的颜色，但是新一轮中Bob选择了和之前不同的边
那也很好办，再进行一次Rewind，让Bob再选择一次边，重复这个过程，直到Bob选到了正确染色的边为止
例子中的这个图一共有十二条边，因此Bob最多选择13次，就一定会再次选到之前正确染色的那条边，也就是至多需要13次Rewind操作即可
回到零知识
之前提到了，如果理想世界中的Zlice在没有知识的情况下，采用了某种方法让Bob确信了他有知识，则现实世界中的Alice一定也可以采用相同的方式来欺骗Bob，这个方法就是Rewind能力
如果Alice也可以进行Rewind的话，那么就证明了协议是不可靠的（Unsoundness），因为在这种情况下Alice在没有知识的前提下也骗过了Bob，显然现实世界的Alice是没有这种能力的，因此协议是零知识的
需要说明的是，零知识的概念是针对现实世界而言的，理想世界中可以通过Rewind来让Bob相信Zlice有知识，而理想世界和现实世界又是不可区分的，由于Zlice没有知识，因此现实世界中的协议是零知识的
换句话说，如果我们运行模拟器，由模拟器得到了协议的一系列交互信息，这些交互信息中Verifier的请求和现实世界中协议执行过程Verifier的请求是一致的（不可区分），那么协议就是零知识的
（不知道我有没有讲清楚）
没讲清楚的话，咱们换一个说法，这里引入一个新的概念，叫抽知识取器，抽取器可以抽取与他交互的实体的知识，当然抽取器也是针对理想世界而言的，现实世界没有这么多花里胡哨的东西
无论抽取器采用什么方法，只要它能够输出某个知识，那就意味着与抽取器交互的实体是有知识的，但是理想世界的Zlice是没有知识的，那就意味着抽取器不能抽取出知识，又由于两个世界是不可区分的，那就意味着现实世界的Alice一定存在知识
注意，抽取器是针对理想世界而言的，理想世界里面的玩意儿都有一些超能力（比如Rewind），如果说现实世界也有抽取器，那就相当于协议不是零知识的了
（感觉讲的更乱了，还不如第一个例子）
模拟存在的问题
之前的例子提到了，如果Bob每次都选择不同的边，会增加Zlice进行Rewind操作的次数，越多次的Rewind也意味着模拟的效率越低，也就是如果按照之前的方式进行模拟，会产生时间问题，那么如果Bob意识到了，他在和两个世界的Alice交互的时候，虽然他不知道自己在和Zlice交互时自己被Rewind了，但是他感觉到其中一个Alice交互的时间会比另一个更长，因此他可以将这个时间信息作为区分理想世界和现实世界的手段，那就意味着Bob可以区分现实世界和理想世界，那也就是现实世界不再是零知识的了
那么有没有什么方法可以提高效率呢，经过学界的研究，提出了并行模拟的方案，并行模拟可以使得在现实世界协议结束时，理想世界中的模拟操作也随之完成，不会泄露时间信息，确保协议是零知识的
之后再慢慢说这方面的知识（如果我看得懂且我还记得）
后记
本篇博客主要借鉴了郭宇大佬的系列文章$[1-2]$，然后加入了一些自己的理解
模拟的概念定是零知识中不可或缺的概念，理解好模拟这个概念可能更有助于理解零知识系统
于是打算在讲零知识之前简单写一下模拟的概念，因为模拟、模拟器，以及模拟过程中需要的rewind操作，都是论文中很常见的名词，最开始并不理解，自己也是慢慢看论文，看教材和大佬的博客，慢慢理解的，最近在看BIU的密码学冬令营，慢慢学习吧
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$ 从「模拟」理解零知识证明：平行宇宙与时光倒流 —— 探索零知识证明系列（二） - 知乎 (zhihu.com)
$[2]$ 读心术：从零知识证明中提取「知识」——探索零知识证明系列（三） - 知乎 (zhihu.com)
$[3]$ 陈原。计算复杂性理论导引 $[M]$. 西安电子科技大学出版社.
$[4]$ （以）Odeb Goldreich 著；温巧燕，杨义先译。密码学基础 $[M]$. 北京：人民邮电出版社.2003.
$[5]$ Cynthia Dwork, Moni Naor, Amit Sahai:Concurrent Zero-Knowledge. STOC 1998: 409-418
$[6]$ Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291-304
$[7]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center