本文将向您介绍零知识证明

上一次shor对支付网络中的路由问题进行了全面的研究之后，neurvos的另一个合作伙伴cyte对零知识证明进行了详细的研究。

在本文中，cyte将介绍零知识证明（zkp）的定义，并将零知识证明与snark和stark区分开来。

随着最近区块链的兴起，zkp、snark和stark等加密概念成为热点。然而，它们经常被误解和误用。事实上，所有这些概念都属于一个更广泛的范畴，称为证明系统或密码证明。斯塔克和斯纳克之间没有交叉。它们之间的关系可以用图形表示。

本文首先介绍了证明制度的定义，并讨论了证明制度的各种性质，重点讨论了“零知识”、“知识证明”、“简洁性”和“非交互性”。特别是，如果一个证明系统具有“零知识”，则称之为“零知识证明”。**，本文讨论并比较了Snap和stark的定义。

证明制度

证明系统是一个由两个参与者（验证者和验证者）和一个算法设置组成的交互式协议。证明制度的功能是使证明人说服验证者相信某件事，我们称之为陈述。

在协议开始之前，需要有人调用设置算法。设置算法以一些常用参数为输入，输出验证程序和验证程序所需的设置信息。验证人获得的信息记录为，验证人获得的信息记录为；。和和的公共部分称为公共引用字符串（CRS）。谁和何时调用设置算法取决于证明系统的设计。协议开始时，验证程序和验证程序同时获取输入语句；。Prover必须比verifier有一些额外的优势，比如更强大的算力，或者一些额外的输入；。此外，验证人和验证人分别了解了和；。获取设置信息的时间取决于证明系统的设计。例如，可能已将验证程序和验证程序下载并存储在各自的硬盘中以供重复使用，或者它们可能在协议开始之前被当场输入。然后证明者和验证者开始执行证明系统指定的协议。如果证明人和核查人都是诚实的，那么他们都严格遵守协议。但也有可能是一方恶意不按协议规定执行。这个时候会发生什么取决于证据系统的安全性。如果双方都是恶意的，而且他们不遵守协议，这与证据制度无关。**，验证器输出接受或拒绝，指示是否相信该声明；。证明系统需要满足两个性质

完整性：如果陈述是正确的，并且证明人和验证者遵守本协议，则验证器输出接受的概率至少为，其中称为证明系统的完整性错误

稳健性：如果陈述不正确，证明人必须是不诚实的，并且验证者遵守协议，那么任何证明人都不能使验证器输出接受的概率超过，这就是证明系统的可靠性误差

系统的两个基本要求就是证明。在没有任何要求的情况下，我们可以得到一个符合要求但完全无用的证明制度。例如，如果我们只要求完整性，那么无论验证程序做什么，验证器总是只输出accept；如果只要求可靠性，则让verifier总是只输出reject。此外，一般预计和不超过，总和小于，否则证明系统误差太大，几乎没有用处。如果证明系统的可靠性仅对算力有限的任何证明人有效，也就是说，算力无限的对手可能欺骗验证器。此时，证明系统只具有计算可靠性，也称为论证系统。相比之下，对任何验证程序都安全的可靠性称为统计可靠性。

证明制度的其他性质

证明系统还可以满足一些其他（不必要的）属性

CRS模：如果设置信息对所有人都是公开可见的，即setup=setup=setup，则证明系统属于CRS模

交互/非交互：如果在整个交互过程中只有验证者向验证者发送消息，则该系统称为非交互式证明系统；否则，该系统为交互式证明系统

可转移/可否认：如果陈述是正确的，并且交互过程被发送给其他验证者，也可以使其他验证者相信该陈述的正确性，证明系统是可转让的；否则，证明系统被否定

公共可验证/指定验证者：如果设置对所有人都是公开可见的，即任何人都可以是验证者，则此零知识证明系统是可公开验证的。否则，系统将针对特定的验证器

公共硬币：如果验证器的所有消息都是一致随机的，并且独立于证明者，那么系统就是开放随机的

零知识：当陈述正确时，如果验证者不能从交互中获得除正确性之外的任何其他“知识”，则系统被称为零知识

成功：如果证明系统用于证明NP语言，并且系统的流量小于证据，则证明系统简洁

证明这两个球的颜色不同

设置信息：有两个球

两种颜色的球是不同的。验证器具有有限的算力（蒙眼），并且证明人具有正常的视觉

验证者每只手拿着一个球，并将其展示给验证者。

弗利弗把手放在背后，随意地扔硬币。如果是正面朝上，他用左手和右手交换球。否则，他不会。

弗利弗把球传给了普罗弗。

Prover告诉verifier这两个球是否交换过。

结果：如果验证者猜测正确，验证者输出接受，否则验证者输出拒绝。如果两个球的颜色不同，证明器可以*的概率猜测验证器的可靠性。如果两个球的颜色相同，证明者只能盲目猜测，只有1/2的概率是正确的。该系统的可靠性误差为1/2crs。这证明了系统处于CRS模下，因为设置信息是开放的、交互式的，是一个交互式的系统。由于验证者和验证者之间传递的信息不止一条，所以该系统不可移植，也就是说，它是可以依赖的。即使验证者记录了交互过程并向其他蒙着眼睛的人展示，他们也不能确定这两个球是不同颜色的。该系统是可公开验证的，任何验证者都可以用prover来做这个协议来暴露随机性。这个系统不是公开随机的，因为验证者把它发送给证明者，这个系统是零知识的，因为当两个球的颜色真的不同时，验证者期望得到证明者的猜想。除了X语句的正确性外，没有额外的知识

重要性

在上面，我们给出了证明系统的定义、例子和性质。接下来，我们讨论了证明系统的几个重要性质。

零知识

零知识被用来保护诚实的证明人不被恶意验证者欺骗，并泄露需要证明的秘密证据。

证明系统的零知识性已经在前面提到过，简单地说就是验证者不能从交互中获得任何“知识”。这种描述不准确，因为它没有给出严格的标准。零位校验器本身就是一些直观的知识。为什么这个系统是“零知识”？事实上，“信息”并不等于“知识”。如果验证者获得了信息，但是获取的信息不能使验证者计算出更多的结果，或者信息可以由验证者自己计算，那么验证者就没有获得任何“知识”。在证明系统的执行过程中，验证人获得的所有信息包括：验证人自己的随机数；证明人发送给验证人的所有信息（标记为）。我们将此信息称为验证者的“视野”；。这些信息是验证器计算过程中所有不确定性的来源。一旦这些信息确定下来，其他一切都可以确定地计算出来。请注意，它是一个随机变量。当验证器和证明器实现证明系统时，验证器将获得该随机变量的样本。如果验证器可以独立采样而无需验证器，则系统为零知识。我们称随机变量抽样算法为模拟器。根据模拟器的工作模式，有如下不同的定义：

非黑箱模拟器对应的零知识称为非黑箱零知识。这种零知识定义允许每个验证器都有一个“排他的”模拟器，允许模拟器为不同的验证器实现细节定制不同的采样过程。

黑箱模拟器对应于黑箱零知识。这种零知识的定义要求有一个唯一的模拟器，这样它就可以对所有验证器进行采样；。唯一的仿真器无法知道验证器的所有实现细节，只能通过黑盒调用访问验证器。但是，模拟器可以完全控制验证器。仿真器可以确定验证器的随机数量，并输入任何验证程序消息或用于验证程序；。因此，在模拟器的眼中，验证器是一种黑盒确定性算法。

如果模拟器只针对诚实验证者，则对应诚实验证者ZK。由于诚实验证器的行为是完全预期的，模拟器可以自然地使用这些信息，因此模拟器对验证器的访问是非黑盒的。

非黑箱模拟器可以获取更多的信息，因此非黑箱零知识比黑箱零知识更容易建立。诚实的验证者零知识是最容易实现的。至于诚实验证者的零知识，这里的诚实验证者更准确地说是半诚实，或“诚实但好奇”。这种验证器表面上符合协议，但可以私下尝试从消息中提取知识。相反，恶意验证器的行为是完全不受限制的。验证器可能会关闭，发送不符合格式的消息，不按照协议采样，等等。为了证明一个系统满足恶意验证者的零知识，我们需要覆盖所有这些情况。模拟器是一个随机算法，其输出值也是一个随机变量，记录为；。零知识要求这两个随机变量很难区分。然而，“不可区分”一词有很多种版本，从中可以推导出各种关于零知识证明的定义

如果统计上两个变量的统计距离为0，则称其为统计上的零距离，则称其为不可区别的统计知识体系；

如果两个随机变量的分布在计算上是不可区分的，即任何多项式时间的随机对手都不能区分这两个分布，则证明系统称为计算零知识。

请注意，零知识的定义只要求难以区分正确陈述的、和的分布。对于虚假陈述，我们不关心验证者能获得什么样的知识，因为在这种情况下，证明者本身是不诚实的，不需要保护它。换言之，由于prover不符合协议，即使设计良好，我们的协议也无法对其进行保护。但是，尽管零知识不会对错误时的分布做出任何假设，但如果从错误抽样中获得的概率与正确情况的概率有显著差异，我们可以判断是否正确。这意味着只能来自普通NP语言。因此，对于困难的NP问题，如果将错误的输入到模拟器中，则获得的结果也可以用相同的概率进行验证。这不是零知识和可靠性之间的矛盾吗？换句话说，为什么prover不能调用仿真器来欺骗验证器的错误呢？事实上，prover无法控制验证器，因此无法为模拟器提供采样所需的资源。实际上，恶意验证程序可以调用仿真器，但这对它无效，因为模拟器的输出中的不是与验证程序交互的验证器的随机数。此外，模拟器的输出可能与验证器接收到的输出不同，这可能导致验证失败。然而，prover调用的仿真器不能得到随机的验证器数目，这足以保证安全性，因此在交互式证明中，即使是固定常数也可以。

知识证明

如果证明者需要“知道”一些信息以通过验证者的验证，这个系统称为知识证明。知识证明可以看作是可靠性的增强版本。知识证明也有一个叫做知识论证的计算版本。

知识证明系统通常用于证明NP语言。NP语言是指一组元素属于的集合，这可以通过证据来证明，也就是说，有一个多项式时间算法可以确定是否属于。通用证明系统使证明人能够向验证者证明；。知识证明系统使证明人不仅能证明，而且能证明证明人“知道”；。也就是说，即使证明人不知道对应的，也很难验证。与上一节讨论的零知识类似，“知识”也需要严格定义。程序P“知道”数据如何定义？想象一下在虚拟机中运行这个程序，它的随机数可以由我们随机分配。在整个运行过程中，虚拟机可以记录CPU状态和所有内存读写操作的完整历史记录。如果程序“知道”，我们应该始终从这些记录中提取信息。实际上，这是理解提取器的直观方法。提取器是一种算法，它可以与提取的程序同时运行，并且可以访问提取程序的内部状态。**输出提取结果。上面描述的提取器是一个非黑盒提取器，因为它可以访问所提取程序的内部状态。非黑盒提取器的算法必须随着被抽取程序的变化而变化。因此，证明系统是知识证明，其定义为：“对于任何证明人，都有一个提取器，它与同时执行，并可以访问的内部状态。如果和、和和和相互作用，则将输出满足条件的输出。”与零知识定义中的模拟器类似，提取器也可以用黑盒的方式定义。提取器无法访问程序的内部状态，但它可以调用程序、控制其随机数并读取其输出。我们引入一个代币来表示提取器以黑盒方式访问一对验证程序和验证程序。黑盒提取器只需要一个用于所有验证程序，因此知识证明可以定义为：“有一个提取器，对于任何验证程序，如果和输出接受，则将输出满足条件。”

简单

用于表示NP语言的实例，并用存在的语言表示证据。成功是一个线性函数，它证明系统所需的流量低于系统所需的流量。换言之，验证者和验证者实现了这种证明系统，比验证者直接发送给验证者节省了通信带宽。有时，简单性可能要求验证者在证明系统中比在验证中执行更少的计算；。简而言之，简单性要求系统被证明是有效的。

我们可能需要一个简明的证据，证明系统的流量达到对数水平或更低，也就是说；。然而，简单性的要求会带来安全性的损失。因为如果业务量低至对数级，则prover的消息组合所在的整个空间可能会在时间内耗尽。但是，系统的可靠性要求验证人无法找到验证器可以传递给虚假陈述的内容；。如果可以验证没有通过验证的根本原因，则可以保证可靠性。但是这样，我们可以通过穷尽法来判断合法性，那么就不是一个难题，排除了一般的NP语言。如果我们想要一个通用的NP证明系统，我们必须允许少量可验证的语言，即使是错误的语言；。在这种情况下，我们只能引入一个额外的安全参数来放宽流量的大小，使穷举的复杂度达到，这至少达到了计算的可靠性。同时，业务量相对于仍然是对数的，因此简单性得到满足。综上所述，对于一般NP语言，简明证明系统（对数级）只能是论证系统。

非交互性

非交互性是指证明系统的整体交互作用，只是证明人向验证者发送的一条信息。此邮件称为证明，并标记为；。非交互性给证明系统带来了很多便利，也带来了更多的应用场景。例如，在区块链系统中，非交互式零知识证明可以附加到交易上，供任何人随时检查，而不需要交易作者随时在线与验证者互动。

任何NP语言都有一个非交互的证明协议，即证明者直接向验证者发送证据，证明是知识证明。因此，构建一个简单的非交互证明系统并不重要。非交互只有结合前面讨论的两个属性（即零知识或简洁性）才是有趣的。非交互零知识（nisk）是零知识与非交互知识的结合。正如我们前面提到的，当我们讨论零知识时，零知识与可靠性不矛盾的原因是，所谓模拟器采样中的验证器与与验证程序交互的随机数不同。然而，对于非交互零知识，我们需要重新审视这个推理过程。在交互证明中，随机数的验证器可以验证传递的验证消息，如果直接移动到随机数的验证器，验证很可能失败。因此，在交互证明中，正确性不是全局的，而是取决于。在非交互证明中，证明器不接收来自验证器的任何消息，因此证明器的计算不使用验证器的随机数；。因此，为了证明系统的完整性，可以对大多数验证器随机数进行诚实证明输出的验证。因此，非交互证明中的正确性是全局的，不取决于任何。由于对知识的要求为零，验证者的视觉与模拟器的输出不可区分。这意味着，如果您单独查看它们的一些组件，它们是无法区分的。也就是说，在和中，两者之间是无法区分的。因此，恶意验证程序可以调用模拟器输出；。这在交互验证中不是问题，恶意认证程序只获得有关a和仅适用的权利。然而，在非交互证明中，正确性并不取决于它，它将带来安全问题。此时，这取决于发挥作用。尽管正确性不再取决于，但它确实如此。为了可靠性，我们希望给定的和声明很难计算出能够通过验证的数据；。虽然模拟器在给定a时可以同时输出一对，但很难计算前者，然后计算后者。如何做到这一点将在下面的文章中详细解释。如上所述，简洁性证明制度必须是论证制度。结合非交互性，有一个简洁的非交互论证（snarg）。事实上，符合snarg定义的系统早在2000年就由米卡利构建，这个名字后来才产生。如果snarg同时是知识的论点，那么它就被称为简洁的非交互知识论证（snark）。snark的名字最初是由bcct12创建的，现在它已经成为零知识证明领域中***的概念之一。其实，网罗只是简洁而非互动的，不一定是零知识。如果知识为零，则应称为zksnark。另一个经常提到的概念是刻板的。它只不过是一个不同于网罗的词，但有许多不同。让我们比较一下这两个概念。公共地面：

它们都是知识论证（Ark），也就是说，它们只在计算意义上是可靠的，证明是智力的

区别：

snark的“s”是简单的，而Stark的“s”是可伸缩性。在简单性的基础上，它还要求证明者的复杂度至多为拟线性，即设置的计算复杂度最多为对数

透明度：stark不需要可信的第三方设置；snark没有这个限制

非交互性：snark必须是非交互性的，stark没有这个限制

可以看出，snark唯一的附加限制是非交互性。然而，通过Fiat-Shamir变换，stark可以转化为非交互式证明，而转化的结果必然是一个陷阱。从这个意义上说，斯塔克可以看作是snark的一个子集。以上对snark和stark的定义就是这两个名词的广义含义。狭义上，它们分别指两种具体的结构方案。其中，snark是指一系列基于QAP和以groth16方案为代表的双线性对的zksnark施工方案。从狭义上讲，斯塔克具体指的是本·萨森等人在2018年提出的基于air和fri的计划。

摘要

本文介绍了证明系统的定义，讨论了证明系统的各种性质，重点讨论了“零知识”、“知识证明”、“简洁性”和“非交互性”。说明了如何用模拟器定义零知识，如何用提取器定义知识证明。**，对snark和stark进行了讨论和比较。

参考资料

Goldreich.《密码学基础》，第1卷。基本工具。2001

ZKPROVE社区。ZKPROVE社区参考。2019https://docs.zkproof.org/reference.pdf

Yehuda Lindell.如何模拟它-模拟验证技术教程。2018

Eli Ben Sasson。寒武纪密码证明的爆炸。https://nakamoto.com/cambrian-explosion-of-crypto-proof/