人类对很多概念的认识是漫长的、不断更新且曲折的。即使今天很多人看了零知识证明的定义，还是会一头雾水。不用担心，提出这个概念的图灵奖级别论......从新的数据可以看出，阿蒂斯atis虚拟币挖矿市场影响力越来也大，产品占有率也相对的增多，未来很有潜力。
人类对很多概念的认识是漫长的、不断更新且曲折的。即使今天很多人看了零知识证明的定义，还是会一头雾水。不用担心，提出这个概念的图灵奖级别论文《交互证明系统的知识复杂度》(gmr[])，曾连续四次被业界顶级的计算理论研讨会stoc拒绝。看来不只是我们，那个时代最聪明的头脑们同样难以理解这篇极为重要的论文所蕴含的深刻意义。
在《不可思议的零知识证明》一文中，我们通过三个小故事介绍了零知识证明里面的重要概念：红绿色盲游戏（交互和随机性），阿里巴巴洞穴（模拟器），旅行中的数学家（非交互和公开验证）。但从直觉到严格的定义、证明之间，需要一些新的工具和方法论。这些由gmr[]第一次给出，并且在之后得到广泛的研究和推广。第一个正式的零知识证明协议是二次剩余(q r)的判定，通过它，我们介绍零知识证明中的工具——计算不可区分( )和模拟范式( )，并且给出必要的证明。
背景知识
二次剩余是数论里面历史悠久的问题，起源于同余理论的研究。高斯在《算术研究》中，第一次系统的研究了剩余理论，总结了包括欧拉、费马、勒让德等前人的理论成果。
在自然数的领域里面，余数()和模数()指的都是公式 =+中的；在高斯引入了同余符号≡后，则这个公式可以等价的写成 ≡( )。
定义：如果存在整数，使得≡ ^ ( )，则叫做模的(次)原根，其中当 = 时，则称是模的二次剩余。
比如≡≡ ^ ( )。这种幂形式显然吸引了高斯的兴趣，在他的著作中研究了包括一次同余、二次同余以及高次同余等关系。在后面的文章后我们还将提到同余与群论的关系。
二次剩余问题，即给定互为质数的, (否则， ≡( ))，判断是否是模的二次剩余(是否存在模平方根)。人们在寻找这个问题的算法时，发现它的难度等价于整数分解难题( )。当是质数时，存在多项式时间算法，但是合数时，则找不到多项式时间的算法。二次剩余问题是一个np问题。
二次剩余问题的零知识证明协议
gmr[]利用二次剩余问题构造了第一个零知识证明协议，来解决以下问题：a声称”是模的二次剩余“，她可以直接展示模平方根(或者是的因数分解)，但她不想泄漏除了“是模的二次剩余“外的任何信息；b一方面想着避免被a欺骗，另外一方面，可能也想尽办法想在和a的交流中获得“额外的信息”。
尽管上述采用了a和b这样的人格化比喻，但所有的计算机协议的执行者实际都是运行在计算机上的程序。在理论分析中，一般采用图灵机模型(t m，tm)。也就是说a，b是两台tm。其中a作为证明者()被认为有无限计算资源，所以她能够计算出模平方根，或者说能够解答np问题；b作为验证者()，受限于计算资源，无法破解出模平方根，否则他就能自己判断a的声称是否为真了。
a对b说，有两个公式:
≡ ^ ( )
≡ ()^ ( )
如果和都是模的二次剩余，那么 也是模的二次剩余。但我不会一次性全展示给你，我每次随机生成第一个公式，然后乘以得到第二个公式，并且按照你抛硬币的结果随机展示其中一个：如果你抛到，我就给你公式的模平方根；如果你抛到，我就给你公式的模平方根。下面是协议的示意图：
运行这个协议次，如果a成功通过，则以 -(/)^的概率说服b。那么我们看下这个协议要满足的目的：
. 如果a能计算出模平方根，则她能够完成任意次挑战；
. 如果a不能计算出模平方根，则她无论采用什么策略，也会以极大概率被b拒绝；
. 不管b采用什么策略，也无法从a这里得到“是模的二次剩余“外的任何信息；
其中：
. 显而易见，
. 由于a不知道b会抛到什么结果，则她无法通过操纵第一步中的来通过测试(如果她知道是，则会生成 ≡ ^ ( )，如果她知道是，她可以通过生成 ≡ ^/ ( )，这样发送的就是，也能通过检查)；
. 直觉上来看，b抛到，返回；抛到，返回，b无法从 ≡ ^ ( )中计算出，无法获取。
分析并不能叫人满意，因为按照定义，b不仅不会得知，也不能获得除命题为真外的“任何“信息。如何证明一个协议真的做到了零知识泄漏呢？
如何证明「零知识」
b作为验证者，在零知识证明协议运行过程中，能够“看到”的信息包括a发过来每条记录()以及自己的抛硬币结果( )，即 = {,}。如果存在某个计算资源和b一样的图灵机s，能够独立的通过某个算法在概率多项式时间内模拟一个'，和'无法区分。那么b实际可以自己在家运行这个协议获得等价的信息，那么a在交互证明中除了说服b命题为真外，没有泄漏任何信息。
上面有两个概念需要严格的定义，「无法区分」和「模拟」：
· 「无法区分」是个日常表达，记住上面的a, b, s都是图灵机，它们并不关心对象间是否真的相同，只关心在计算模型和算法下能否观察到差别；即运行某个概率多项式时间的算法——叫做区分器(d)，对和'的分布判断的概率之差可以忽略不记，这种性质叫做 「计算不可区分性」( )：
p是p(即a)，v* 是所有的v(包括诚实和恶意的b)，s是s，d是d，v*, s, d都是概率多项式时间的图灵机，是p的私有信息(或者说是p能够计算得到的，而v无法计算出来)，是共有输入(, )，在这里即“是模的二次剩余“这个命题，表示差异可忽略不计的()。
· 上面的「模拟器」s最容易让人误解的地方在于，和'计算不可区分，那么b岂不是也会被s说服？这种误解来源于把s看作是协议中a的角色，s产生'的过程并不是a和b按照零知识证明协议交互产生的过程；s是一个独立运行的程序，只要能证明它能够在概率多项式时间生成这个'就可以了，无须和b交互。
同样由于这个原因，b只可能在和a交互过程中被说服，而产生的无法再去说服另外一个b'。即b对b'说：我确信a是知道模平方根，你看这是我们俩对话的。b‘无法对此采信，因为b可以通过模拟生成'来糊弄他，他必须自己去和a进行交互证明才能被说服。这种局限导致零知识证明不具备公开验证( )的性质，这也说明一般意义上的数字签名（ )并不是[完美的]零知识证明，这在后面介绍非交互零知识证明(nizk)再进一步讨论。
有个上面两个概念，我们可以来构造一个「模拟器」s(, )：
首先，这个程序存在概率多项式时间算法模拟随机变量的生成，包括抛硬币和生成；程序终止()并打印结果的概率是/，尽管可能存在循环但依旧可以在多项式时间内终止。综上，即s()可以在多项式时间内完成；
其次，要证明这个程序生成的视图{,, }与零知识证明系统生成的视图计算不可区分：
. 和交互证明中的第一条消息都是随机生成的，不可区分；
. 和交互证明中b的抛硬币都是随机的，不可区分；
. 的构造方法保证了即使s并没有关于的信息，在b看来是合法的，与交互证明中a的第三条信息不可区分；
在更严格的证明过程中，还会引入一个辅助工具——混合模拟器s'(, , )，它是一个计算能力与p相同，但执行路径与s(, )等价的程序，感兴趣的读者可以去查阅原始论文。顺序()重复上面的模拟器次，则能够得到一组完整的'，可以证明以上性质仍旧适用(即对 是闭合的)。
到目前为止，我们完整的介绍了第一个零知识证明协议的背景知识、构造以及证明，终于可以得到一个严格的定义：交互证明系统&, v&;是零知识的，当且仅当存在概率多项式时间的模拟器s，使得：
其中是p要证明的命题，l是某类命题的集合，是抛硬币的结果，是只有p拥有(或能计算出)的私有信息，v*指所有的验证者。无论v采用什么抛硬币策略与p交互，s都可以同样使用来复现出来一个不可区分的版本。
看到这里的读者，相信你已经有了从数学上准确理解零知识证明的能力了，下一篇文章我们将讨论非交互和可公开验证的零知识证明协议(nizk)
参考
s g, s m, c r: t k ci p-s (e a). stoc : -