一文读懂首个零知识证明协议：二次剩余

本文作者胡鹏，来自安比技术社区小伙伴。区块链行业从业者，隐私计算实验室研究员。毕业于北航计算机专业，过去两年参与设计研发了托管数十亿加密资产的管理平台。信仰技术与理性，坚信区块链会重塑互联网和社会的形态。

人类对很多概念的认识是漫长的、不断更新且曲折的。即使今天很多人看了零知识证明的定义，还是会一头雾水。不用担心，提出这个概念的图灵奖级别论文《交互证明系统的知识复杂度》(GMR[85])，曾连续四次被业界顶级的计算理论研讨会STOC拒绝。看来不只是我们，那个时代最聪明的头脑们同样难以理解这篇极为重要的论文所蕴含的深刻意义。

在《不可思议的零知识证明》一文中，我们通过三个小故事介绍了零知识证明里面的重要概念：红绿色盲游戏（交互和随机性），阿里巴巴洞穴（模拟器），旅行中的数学家（非交互和公开验证）。但从直觉到严格的定义、证明之间，需要一些新的工具和方法论。这些由GMR[85]第一次给出，并且在之后得到广泛的研究和推广。第一个正式的零知识证明协议是二次剩余(Quadratic Residue)的判定，通过它，我们介绍零知识证明中的工具——计算不可区分(computationally indistinguable)和模拟范式(simulation paradigm)，并且给出必要的证明。

背景知识

二次剩余是数论里面历史悠久的问题，起源于同余理论的研究。高斯在《算术研究》中，第一次系统的研究了剩余理论，总结了包括欧拉、费马、勒让德等前人的理论成果。

在自然数的领域里面，余数(remainder)和模数(modulus)指的都是公式a = nq + r 中的r；在高斯引入了同余符号≡后，则这个公式可以等价的写成a ≡ r (mod n)。

定义：如果存在整数x，使得 a ≡ x^k (mod n)，则x叫做a模n的(k次)原根，其中当k = 2时，则称a是模n的二次剩余。

比如 12 ≡ 25 ≡ 5^2 (mod 13)。这种幂形式显然吸引了高斯的兴趣，在他的著作中研究了包括一次同余、二次同余以及高次同余等关系。在后面的文章后我们还将提到同余与群论的关系。

二次剩余问题，即给定互为质数的a, n(否则，a ≡ 0 (mod n))，判断a是否是模n的二次剩余(是否存在模平方根x)。人们在寻找这个问题的算法时，发现它的难度等价于整数分解难题(integer factoring)。当n是质数时，存在多项式时间算法，但n是合数时，则找不到多项式时间的算法。二次剩余问题是一个NP问题。

二次剩余问题的零知识证明协议

GMR[85]利用二次剩余问题构造了第一个零知识证明协议，来解决以下问题：Alice声称”a是模n的二次剩余“，她可以直接展示模平方根x(或者是n的因数分解)，但她不想泄漏除了“a是模n的二次剩余“外的任何信息；Bob一方面想着避免被Alice欺骗，另外一方面，可能也想尽办法想在和Alice的交流中获得“额外的信息”。

尽管上述采用了Alice和Bob这样的人格化比喻，但所有的计算机协议的执行者实际都是运行在计算机上的程序。在理论分析中，一般采用图灵机模型(Turing Machine，TM)。也就是说Alice，Bob是两台TM。其中Alice作为证明者(prover)被认为有无限计算资源，所以她能够计算出模平方根，或者说能够解答NP问题；Bob作为验证者(verifier)，受限于计算资源，无法破解出模平方根x，否则他就能自己判断Alice的声称是否为真了。

Alice对Bob说，有两个公式:

s ≡ r^2 (mod n)

as ≡ (xr)^2 (mod n)

如果s和as都是模n的二次剩余，那么 a也是模n的二次剩余。但我不会一次性全展示给你，我每次随机生成第一个公式，然后乘以a得到第二个公式，并且按照你抛硬币的结果随机展示其中一个：如果你抛到0，我就给你公式1的模平方根r；如果你抛到1，我就给你公式2的模平方根rx。下面是协议的示意图：

运行这个协议m次，如果Alice成功通过check，则以 1-(1/2)^m的概率说服Bob。那么我们看下这个协议要满足的目的：

如果Alice能计算出模平方根x，则她能够完成任意次挑战；

如果Alice不能计算出模平方根x，则她无论采用什么策略，也会以极大概率被Bob拒绝；

不管Bob采用什么策略，也无法从Alice这里得到“a是模n的二次剩余“外的任何信息；

其中：

显而易见，

由于Alice不知道Bob会抛到什么结果，则她无法通过操纵第一步中的s来通过测试(如果她知道是0，则会生成s ≡ r^2 (mod n)，如果她知道是1，她可以通过生成s ≡ r^2/a (mod n)，这样发送的w就是r，也能通过检查)；

直觉上来看，Bob抛到0，返回r；抛到1，返回rx，Bob无法从s ≡ r^2 (mod n)中计算出r，无法获取x。

分析3并不能叫人满意，因为按照定义，Bob不仅不会得知x，也不能获得除命题为真外的“任何“信息。如何证明一个协议真的做到了零知识泄漏呢？

如何证明「零知识」

Bob作为验证者，在零知识证明协议运行过程中，能够“看到”的信息包括Alice发过来每条记录(transcript)以及自己的抛硬币结果(local coins)，即view = {tanscript, local coins}。如果存在某个计算资源和Bob一样的图灵机S，能够独立的通过某个算法在概率多项式时间内模拟一个view'，view和view'无法区分。那么Bob实际可以自己在家运行这个协议获得等价的信息，那么Alice在交互证明中除了说服Bob命题为真外，没有泄漏任何信息。

上面有两个概念需要严格的定义，「无法区分」和「模拟」：

「无法区分」是个日常表达，记住上面的Alice, Bob, S都是图灵机，它们并不关心对象间是否真的相同，只关心在计算模型和算法下能否观察到差别；即运行某个概率多项式时间的算法——叫做区分器(Distinguisher)，对view和view'的分布判断的概率之差可以忽略不记，这种性质叫做 「计算不可区分性」(computationally indistinguishable)：

P是Prover(即Alice)，V* 是所有的Verifier(包括诚实和恶意的Bob)，S是Simulator，D是Distinguisher，V*, S, D都是概率多项式时间的图灵机，w是P的私有信息(或者说是P能够计算得到的，而V无法计算出来)，x是共有输入(a, n)，在这里即“a是模n的二次剩余“这个命题，negl表示差异可忽略不计的(negligible)。

上面的「模拟器」S最容易让人误解的地方在于，view和view'计算不可区分，那么Bob岂不是也会被S说服？这种误解来源于把S看作是协议中Alice的角色，S产生view'的过程并不是Alice和Bob按照零知识证明协议交互产生view的过程；S是一个独立运行的程序，只要能证明它能够在概率多项式时间生成这个view'就可以了，无须和Bob交互。

同样由于这个原因，Bob只可能在和Alice交互过程中被说服，而产生的view无法再去说服另外一个Bob'。即Bob对Bob'说：我确信Alice是知道模平方根x，你看这是我们俩对话的view。Bob‘无法对此采信，因为Bob可以通过模拟生成view'来糊弄他，他必须自己去和Alice进行交互证明才能被说服。这种局限导致零知识证明不具备公开验证(publicly verifiable)的性质，这也说明一般意义上的数字签名（digital signature)并不是[完美的]零知识证明，这在后面介绍非交互零知识证明(NIZK)再进一步讨论。

有个上面两个概念，我们可以来构造一个「模拟器」S(a, n)：

首先，这个程序存在概率多项式时间算法模拟随机变量的生成，包括抛硬币和生成s；程序终止(halt)并打印结果的概率是1/2，尽管可能存在循环但依旧可以在多项式时间内终止。综上，即S(x)可以在多项式时间内完成；

其次，要证明这个程序生成的视图{s, b , w}与零知识证明系统生成的视图计算不可区分：

s和交互证明中的第一条消息都是随机生成的，不可区分；

b和交互证明中Bob的抛硬币都是随机的，不可区分；

w的构造方法保证了即使S并没有关于x的信息，w在Bob看来是合法的，w与交互证明中Alice的第三条信息不可区分；

在更严格的证明过程中，还会引入一个辅助工具——混合模拟器S'(a, n, x)，它是一个计算能力与Prover相同，但执行路径与S(a, n)等价的程序，感兴趣的读者可以去查阅原始论文。顺序(sequential)重复上面的模拟器m次，则能够得到一组完整的view'，可以证明以上性质仍旧适用(即对sequential composition是闭合的)。

到目前为止，我们完整的介绍了第一个零知识证明协议的背景知识、构造以及证明，终于可以得到一个严格的定义：交互证明系统<P, V>是零知识的，当且仅当存在概率多项式时间的模拟器S，使得：

其中x是P要证明的命题，L是某类命题的集合，z是抛硬币的结果，w是只有P拥有(或能计算出)的私有信息，V*指所有的验证者。无论V采用什么抛硬币策略z与P交互，S都可以同样使用z来复现出来一个不可区分的版本。

看到这里的读者，相信你已经有了从数学上准确理解零知识证明的能力了，下一篇文章我们将讨论非交互和可公开验证的零知识证明协议(NIZK)

(w),>

参考

Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291-304

—-

编译者/作者：安比技术社区

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。