零知识证明综述 - Githubissues

title: 零知识证明综述 date: 2019-08-20 10:14:16 tags:

密码学

前言

零知识证明看样子是很复杂的一个过程，其实不是，网络上对这个概念的讲解杂七杂八，质量参差不齐，今天我就打算讲一讲有关话题，我会循序渐进，每个小节我会逐渐加深理解难度，然后最后导出工业界的做法。所以读者最终要的是，首先要做到不要畏惧。实在想不明白可以用手稿纸画一画，推一推。我写文章通常的做法会在专业的名词用括号注释英文，目的是让读者不混淆，并且英文搜索到的资料更准确。

研究背景

传统的通信协议中的一个共同弱点就是容易遭遇到信道的窃听，所以零知识证明（又叫零知识协议Zero Knownledge protocol，ZKP）就这样诞生了。目的是构造这样一个系统，该系统中的证明人（Prover）可以在不暴露任何信息（Zero Knowledge）的情况下，让验证者（Verifer）进行验证。简而言之，对于监听者，就是你监听了，也没用，你监听到的信息也推导不出来任何有用的东西。

简介

这里要注意下，虽说到这里反复提到了证明（Proof）这个词，但是这个证明不是数学上的证明，数学证明是严格的，使用自证陈述或从预先建立好的证明中获得陈述。ZKP更类似于人类在信息交换过程中建立一个陈述的动态过程，所以它是互交式的（当然，也有非互交式的，这个到后面会提到，而工业界的zk-SNARK用的就是非互交式的）。

简而言之，在ZKP中，所谓互交式就是证明者（Prover）不为它持有的秘密（Secret）直接提供证据，而是双方在一个互交来回“对话”的过程中证明者（Prover）逐渐的说服验证者（Verfier）他持有某个秘密是真实的。Prover也不用暴露秘密就可以说服对方，这样太好了。比如，我可以宣称对外界粉丝说，刘亦菲是我老婆，也不用把结婚证（Secret）拿出来，就能向粉丝们证明我说的是真的（刘亦菲是我老婆），即真命题。哈哈，结婚证是我的秘密隐私啊，怎么可能拿出来给粉丝看。

ZKP中的参与者

在ZKP中，参与者也就是2方：

Alice （Prover） Alice想向Bob传达某种知识的证明，但是同时又不想暴露她的秘密
Bob （Verifier） Bob向Alice提出一些问题，这有助于让Bob确认Alice是否知道她声称知道的某些东西， Bob无法从这些互动中学到有用的任何东西，即使Bob在欺骗或从事ZKP以外的活动。

一个简单的例子

为了举例，考虑一个由圆形隧道组成的洞穴。与这个洞穴的入口正好相反，有一扇门只能通过密码打开。尽管这种情况可能不是真实的场景，但这个场景演示基本涵盖了ZKP的基本特性，现在Alice知道了这扇门的密码，她想向Bob证明这一点，但又不想把门的密码暴露出来。他们两个人要互动地完成以下任务：

Alice(绿脸)随机选择一个洞穴的分支进去（左或者右都行），这个不能让Bob（黑脸）知道她选择了哪一个分支
站在洞穴入口处的Bob，他随机选择一个分支，然后让Alice从他选择的那个分支出来
如果Alice真的知道门（红色的线条）的密码，没有撒谎的话，她就可以每次做到从Bob选择的分支出来。如果她不知道门的密码，那她在最开始就有百分之50的概率蒙骗过关，随着这样次数的逐渐增加，Alice蒙骗过关的概率越来越低，在达到一个特定的次数的时候，她蒙骗过关的概率可以小到忽略不计了，比中彩票的概率还要小。

这一个例子也展示了ZKP的另一个特性，Bob确信了Alice有门的密码，但是Bob不能使别人相信Alice有门的密码，这个过程只有他两知道，把过程录下来也无济于事，因为录像带可以造假。所有没有任何有用的信息可以暴露给Bob，更不可能流向协议系统之外，只有Alice自己知道门的密码。

ZKP的特性

所以ZKP的特性可以总结如下：

验证者（Verifier）无法从协议中学习到任何有用的知识。这是ZKP的核心特性，也就是说零数量的知识被暴露出来。当然有个类似的协议叫最小披露协议（Minimum Disclosure Protocol），它适当放宽了这个特性要求，试图暴露一个尽可能最小的知识出去。
证明者（Prover）无法欺骗验证者（Verifier）。随着协议互交轮次的数量提高，Prover欺骗Verifier的概率急剧降低，慢慢小到可以忽略不计。
验证者（Verifier）也无法欺骗证明者（Prover）。即使验证者不遵守协议规则，验证者也无法从协议中获取任何信息，验证者只能慢慢确信证明者陈述的某个命题是真的。
验证者（Verifier）无法向外界证明证明者（Prover）所说的是真的。比如，我（Prover）通过ZKP向某个刘亦菲的粉丝（Verifier）证明了刘亦菲是我老婆，但是这个粉丝（Verifier）不能向其他粉丝证明刘亦菲是我老婆。只有天知地知，你知我知。

好的，接下来在引出ZKP的定义之前，我们需要讨论一些诸如此类证明系统一些必要属性，这些属性包括正确性和完备性。

互交式证明系统

零知识协议是交互式证明系统的实例之一，其中证明者和验证者互相交换挑战，然后响应，通常依赖于允许他们保密的随机数（理想情况下，公平投币的结果）。正如我们前面所说，在这种情况下，证明是概率的，而不是数学意义上那种绝对的。这些证明只需要在一定的有界概率下才是正确的（尽管这个概率可以任意接近100%）。交互证明有时被称为协议证明。

用于识别的交互证明可以被表述为知识的证明。Prover有一个秘密（记为s），他希望通过正确地回答出需要秘密s作为依据推导而出的知识才能回答Verifier的提问，使Verifier相信Prover他知道s。值得注意的是，证明s的知识与证明s的存在性是完全不同的，例如，证明某个x是模n的二次剩余与证明x的平方根模n的知识是不同的，表示出来就是 k^2 = x mod n 给定x和n，如果k在该二次同余方程下有解，那么则得出 k = square(x) mod n。（实在不明白搜二次剩余，数论的东西）

如果一个交互式的证明具有完备性和可靠性，那么它就是知识证明。

完备性的定义(Completeness Property)

如果给定一个诚实的Prover和一个诚实的Verifier，协议以几乎100%的概率成功（即，Verifier接受Prover的声明），则交互式证明协议是完备的。当然，几乎100%的定义取决于应用，但通常意味着失败的概率在这个场景下并不具有实际意义。（也就是低到可以忽略了）

当然，还可以用形式化点的方式来描述，设Prover和Verifier是一对互交的概率图灵机，随机变量<P(i),V(j)>(x)表示图灵机Verifier与Prover完成互交问答后的输出（这个输出是一个概率值），<>其中x为它们的公共输入，所以可以化简为<P(i),V(j)>(x) = 1表示V接受P给出的证明，<P(i),V(j)>(x) = 0表示V拒绝P给出的证明。其中i，j都是P和V各自的随机输入变量（均匀独立的）。<P,V>这对互交图灵机表示语言L的互交证明系统。

Probability（<P(i),V(j)>(x) = 1） > 1 - c(|x|) 其中函数c表示完备性错误概率，可忽略。 x属于语言L

以上式子表示完备性成功的概率极大。

可靠性的定义(Soundness Property)

如果存在具有以下性质的期望多项式时间算法m，则交互式证明协议是可靠的：如果不诚实的Prover能够以不可忽略的概率与Verfier成功执行协议（成功概率极大，反过来就是说失败率极小），则m可用于从该Prover中提取知识（本质上等同于Prover的秘密）以几乎100%的概率允许随后（下一轮，依次递推）的协议执行

用形式化的方式来说就是：

B代表任意的Prover，也就是可以认为是不诚实的Prover

Probability（<B(i),V(j)>(x) = 1） < s(|x|) 其中函数s为可靠性错误概率，可忽略。x不属于语言L

以上式子表示可靠性失败的概率极小。

所以总而言之，可以这么说，对于任意的Verifier，存在一个多项式时间的算法m（x）（通常成为模拟器），使得Verifier在互交过程中得到的所有信息都可以直接利用算法m（x）模拟出来，也就是说Verifier从Prover那里得到的所有信息都可以用算法m计算得到。简而言之就是，Verifier没有从Prover那里获得任何额外的信息。

因为想冒充Prover就必须拥有这个secret，所以协议的可靠性就是靠提供与secret的等价的知识证明来保证的，这个属性条件保证了不诚实（作恶，假冒）的Prover成功。所以又可以反向得出一个方法，就是，证明某个协议是正确的标准方法就是是假设有一个不诚实（作恶，假冒）的Prover能够成功地执行该协议，并说明他是如何在多项式时间内计算出secret的。

这种“知识证明”思想是零知识证明的基础。然而，很明显，这两个属性都没有提到零知识本身。此外，ZKP还应该具有这样的属性，即在Prover和Verifier之间不应该传递Verifier没有Prover的帮助来识别的知识量。换句话说就是，Prover和Verifier之间传播的知识都是经过Prover认同的。此属性简单地称为零知识属性，将在引入模拟器的概念后定义，如下所述。

模拟器

让我们再考虑一下之前Alice和Bob洞穴例子。假设Bob给他的朋友Jack发了一盘录像带，上面是他和Alice一起证明所采取的一系列步骤。我们将这种磁带称为证据的一个视图（或记录本）。Jack指Bob伯伪造录音带，很明显Bob不能做任何事情来说服Jack。Bob没有任何不可伪造的、不可否认的证据，来证明Alice确实知道门的密码。Bob所能做的就是让Alice再次为Jack演示一遍，Jack将为Alice挑选她出来的分支序列，比如左右左右左（这保证了随机性）。如果有一种方法可以伪造一个与真实的证据不可区分的证据（比如录像带），我们就说有一个模拟器可以模拟所讨论的证据。

相当于模拟器就是那个录像机，录像机就是那个多项式算法m。多项式算法m生成的结果就是那个录像带，录像带就是视图。

模拟器（simulator）

模拟器是一种方法或算法过程（多项式算法m，），它生成的假（生成不需要Prover参与）视图与证明的真（生成时需要Prover参与）视图是不可区分的。也就是说，无论录像带真假，反正Jack是看不出来真假的，只能一股脑认为是假的，没办法，只有他自己与Alice跑协议去，自己去验证。

所以模拟器这个概念是上述零知识属性定义的关键。

零知识属性（zero knowledge property）

如果存在证明的模拟器，则知识证明具有零知识属性。

这使得文章前面几节所描述的内容都用上了，意思是说，在zkp的上下文中，Verifier除了获得secret的有效性之外，不会获得有关该secret的更多信息。此外，这类协议的一个非常理想的特性是，Prover参与协议的次数不会改变模拟攻击成功的机会。这样零知识属性使我们可以得到如下零知识证明的定义。

零知识证明

零知识证明是同时具有零知识属性的知识证明。

零知识证明的基本定义外延

还有一些基本定义的外延是比较重要的，需要了解。

说如果一个交互式证明是零知识的，那么存在一个simulator（算法m），使得Verifier与真正的Prover交互产生的证明副本（录像带）的整体分布（ensemble distribution）和与一个simulator交互产生的证明副本（录像带）的整体分布等价。

完全零知识（Perfect Zero knowledge）

如果真实和模拟的记录本（录像带）彼此之间完全不可区分，则协议称为完全零知识。即两个分布完全等价，这个定义是好理解的，但却是最苛刻的。

统计零知识（Statistical Zero Knowledge）

如果真实和模拟的记录本（录像带）的概率分布之间存在可忽略的差异，则协议是统计零知识。两个分布是统计闭合的（statistical close）。统计闭这个名词，它是说两个分布本身相差很小很小（可忽略）

计算零知识（Computational Zero Knowledge）

如果受限于概率多项式时间测试的观察者不能区分真实和模拟的记录本（录像带），则协议的计算零知识。即两个分布多项式不可区分。

所以，完全零知识强于 > 统计零知识强于 > 计算零知识

显然，计算零知识是对基本概念的采取的是一个最宽松的限制。尽管如此，它仍然是非常有用的，因为在实践中，“攻击者”通常被认为拥有对我们的系统进行攻击的多项式时间能力。已经定义了其他外延，例如非交互式零知识协议，其中Prover不必在场以使Verifier相信其知识。本文将不讨论这些外延。

还有其他类型的证明虽然不是零知识的，但是也不是没用到零知识和最小披露协议。这些证明中与零知识证明的区别变化仅仅是在协议执行过程中，允许从Prover流向Verifier的信息量和信息类型在可控或很小的范围内。

对互交式证明系统的总结评论

很明显，零知识性和可靠性在系统所呈现的安全级别上是不稳定的。对于一个给定的协议来说，依赖于计算困难的问题对其安全性至关重要。对于最见的问题（如大整数分解、背包问题、离散对数等）没有证明，因此使用它们的系统的安全性直接取决于计算复杂性领域的未来发展。这种类型的系统通常被称为可证明安全的。

在零知识技术（ZKP）和公钥（PKP）技术之间的差异可以得到一些优劣比较，这些是：

使用时没有降级：重复使用ZKP不会出现降级。ZKP也能抵抗选定的文本攻击。这导致了一个不可证明安全的ZKP被认为是取代可证明安全的Public Key Protocol的。
效率：ZKP通常比PKP效率低。在某些需要确保（硬或软）实时计算的应用环境中，这是需要考虑的一个重要因素
未经验证的假设：大多数ZKP和PKP依赖于相同的假设（二次剩余、因子分解、离散对数等）

NP ∈ ZKP

本节简要介绍了计算复杂性类的P问题和NP问题。这对于理解每一个NP问题都有与之相关的零知识证明这一结论是很有必要性的。这一结论的证明将在本节末尾通过证明NP完全问题（NPC）的解的知识的简单协议来概述。简单来说就是，每一个NP问题都可以用来构造零知识证明协议。

NPC问题介绍

还是先来回顾下P问题，NP问题，NP-Complete问题，NP-hard问题这四个概念的关系吧。

如下图，每个概念会逐一讲解：

首先，P问题中的P是指多项式时间复杂度（Polynomial time）。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。也就是说，对于某一个程序，其处理某一个特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

多项式就不用解释了，学习过微积分的都会讲这个概念，像O(1),O(ln(n)),O(n^a)等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置；另一种像是O(a^n)和O(n!)等，它是非多项式级的复杂度，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常非常小（没有实用性）。

P问题，能在多项式时间内找到解的问题。一般我们在LeetCode上刷的题通常都是P问题，都能在多项式时间内找到正解。所有P问题都是NP问题，能多项式地解决一个问题，必然能多项式地验证一个问题的解。
NP问题，在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题，但NP类问题不一定属于P类问题。比如，哈密顿回路（Hamilton Cycle）就是NP问题，当然，它也是NPC问题。
NPC问题，NP问题中的特殊存在，所有的NP问题都可以归约（归约就是做一次或多次多项式时间的变换）到它。没有人能够找出求解NPC问题的多项式时间的算法，同时也没有人能够证明对于这类问题不存在多项式时间算法。正是由于NPC的存在，才使大多数人相信 P ！= NP。

NPC问题首先要是一个NP问题。
其次，所有NP问题都能归约到它

之前说到归约，比如问题A能归约到问题B，那么用问题B的解法，一定能解决问题A，虽然解决问题B的时间复杂度 >= 解决A的时间复杂度。这样不停的从小的NP问题归约上去，最终会归约到NPC问题，相当与树结构的根节点（终极存在）。所以，NPC问题的时间复杂度 >= NP问题的复杂度。NPC问题是最难的。

比如，哈密顿回路也可以归约到旅行商问题（Travelling Salesman Problem），所以旅行商问题也被证明是NPC问题了。所以，NPC问题只有暴力搜索了，一般是图论相关的问题，动不动就会搞出这么个事儿来。所以涉及到图相关的问题一般比较复杂。

NP-Hard问题，NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条。

NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。NPC问题一定是NP-Hard的问题。NP-hard一般是属于不在研究范畴内，但是它可能比NPC问题更难，它放宽了限制。比如，这篇论文的证明，星际争霸可能是NP-Hard的。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。

如果存在非均匀的多项式加密方案，那么每个NP语言都有一个互交式的计算零知识证明系统。因为NPC语言都有一个零知识证明系统，比如地图3着色（G3C）。因为G3C是个NPC问题，所以任何NP问题都可以归约到G3C问题，最后得出，所有的NP问题，都有一个与之关联的零知识证明系统。

G3C ∈ ZKP

注，下面提到的“图”是指数据结构所说的图，边也是图的边（edge）。

G3C所谓的着色也是给不同的图的节点（node）着色，不是给边（edge）着色，这点要明确。

假设Prover希望说服一个Verifier知道他对某一图（graph）是用三种不同的颜色着色的，而且不能直接完全暴露出整个图的着色状态。Prover可以按照|E^n|个阶段（其中E是图的边的个数）的顺序执行操作，每个阶段包含以下步骤：

1.Prover随意（随机）排列三种颜色，这使得Prover能够在重复这些步骤的过程中隐藏真实的色彩。
2.Prover的着色色彩对Verifier是不可见的，是隐藏的。（需要用到一些加密手段）
3.Verifier随意（随机）选择图（graph）的一条边（edge）。
4.Prover把选中的边连接的两个节点的颜色暴露出来给Verifier查看。
5.Verifier确定两个节点的颜色是否合法，比如节点颜色是否不同。
重复步骤1

其中，|E^n|中的n是，进行所有步骤的轮次，当n进行的足够多的时候，Verifier确信Prover所说的是真命题的概率会越来越大。概率是 1 - （1 / E）^n。当跟足够大时，概率就很接近100%了。

反过来说，（1 / E）^n就是Prover欺骗Verifier的概率随着n的变大会逐渐变小，哪有这么好的运气每次都欺骗成功？如果地图不是三种颜色的，而是四种，那么每一轮Prover欺骗Verifier的概率就是（1 / E）。

如果还看不明白以上步骤，那么MIT某个网页上有地图三着色的Demo演示，可以鼠标操作，你扮演一个Verifier，这样会让你理解更直观些。如果网页挂了，请搜索Interactive zero knowledge 3-colorability demonstration。

从上面的步骤可以看出来，G3C它是计算零知识证明系统。这也再次肯定了，每个NP语言（问题）都有与之相关的一个计算零知识证明系统。

应用

接下来，我将介绍真正的零知识系统的工作机制，也就是业界做法，ZKP的一个主要应用之一就是获得一个认证的保密目标（显而易见，这就是ZKP最直观的理解）。ZKP系统可以很好地解决金融或其他安全关键应用程序中的安全问题，在这些应用程序中，比如，智能卡等系统不够安全。智能卡容易受逆向工程的影响，被“破解”。如果利用ZKP，逆向工程也无法提取重要信息。可以实现零知识证明系统来抵御此类攻击。此外，ZKP系统可以在不同程度上来适配应用。

以下我会用两个例子说明问题，第一个是关于ZKP做认证的（身份认证），第二个是用来证明（ZKP上下文中的证明，非数学证明）图同构（graph isomorphisms）的系统。

Feige-Fiat-Shamir（FFS）身份鉴别算法

这个算法是最著名的身份的零知识证明，是由Feige，Fiat，Shamir这三个人从他们发明的鉴别和数字签名的方案改进过来的。1986年7月9号，这三个设计者递交了一份美国专利申请。但是由于其算法有军事上潜在的应用，由专利改成了保密的密令，就是此成果将严格保密，否则判两年监禁，罚款2W。但是设计者不是美国公民，这种要求太不可思议了，而且所有的工作都是在以色列进行的，跟美国毫无关系。这消息传遍了整个学术界和出版界。两天内，密令被取消，然而没有得到任何官方解释。由此可体现，这个算法刚出来就那么牛逼。这些题外故事有兴趣可以看wiki。当然这个算法是互交式的，不是非互交的。

和之前的例子差不多，这里的目标是让Alice通过展示她对某个秘密s的了解，来向Bob证明她的身份。通过这些授权的公共数据，这些秘密s是与Alice相关联的。FFS系统的安全性取决于提取未知因子分解的平方根模大复合整数的假设，这个问题是困难的。如果这个假设的困难没了，那么也就不安全了。

身份的Feige-Fiat-Shamir零知识证明

预先计算（setup阶段）：在发放私钥之前，仲裁者（一个可信，独立的实体）随机选取一个模数n，n为两个大素数的乘积。实际上，n是512到1024 bit的数值。n必须至少为512bit，并尽可能接近1024 bit。为了生成Alice的公钥和私钥对，可信仲裁者选取一个数v，v对模n的二次剩余。也就是说，x^2 ≡ v (mod n)有一个解，且v^-1 mod n存在。v就是Alice的公钥，然后计算，s ≡ sqrt(v^-1) （mod n）的最小s，将它作为Alice的私钥。

这样，该零知识证明的协议就正式开始了(n和v公开)：

Alice选取一个随机数r，r < n, 接着计算x = r^2 mod n，并将x发送给Bob。
Bob发送一个随机位b给Alice。（注意是一个随机位，bit）
如果b = 0, Alice将y = r s^b mod n，也就是y = r mod n发给Bob; 如果b = 1, Alice计算y = r s^b mod n，并将y = r * s mod n发送给Bob。
如果b = 0, Bob验证y^2≡xv^b (mod n), 可以简化为y^2 ≡ x (mod n), 因为y ≡ r (mod n), 所以 r^2 ≡ x (mod n), x ≡ r^2 (mod n), 以证实Alice知道sqrt(x) ≡ r (mod n)；如果b = 1. Bob验证y^2 ≡ x v^b (mod n), 化简为y^2 ≡ x v (mod n), 因为y ≡ r s (mod n), 所以 y^2 ≡ r^2 s ^2 (mod n), 又因为x ≡ r^2 (mod n),推出y^2 ≡ x s^2 (mod n), 又因为s^2 ≡ v^-1 (mod n), 所以, y^2 ≡ x v^-1,并最终推出 x ≡ y^2 v (mod n)，以证实Alice知道y ≡ sqrt(v^-1 * x) (mod n)

上面的协议跑一轮就是单次鉴定，如果随着重复次数越来越多，Alice欺骗Bob的概率会大大减小。直到Bob确信Alice知道s（私钥）。当然，要注意一点，第一步的随机数r随着每轮都需要不同。不能使用相同的。

这个方案协议还可以优化成并行版本，并减少互交轮次，再此不作进一步介绍。

图同构

（To be continued）

AlexiaChen / AlexiaChen.github.io

零知识证明综述 #3

密码学

前言