一文带你相识零学问证实_数字货币

[2021-01-31 21:43:17] 来源：编辑：wangjia 点击量：

评论 点击收藏

导读： ZKP、SNARK 和 STARK 等这些密码学概念随着最近区块链的兴起变得热⻔起来。但是，它们经常会被误解和混用。科普 | 代币授权：密码学货币行业用户体验的最大障碍如果你是 DeFi 深度用户

ZKP、SNARK 和 STARK 等这些密码学概念随着最近区块链的兴起变得热⻔起来。但是，它们经常会被误解和混用。

科普 | 代币授权：密码学货币行业用户体验的最大障碍

如果你是 DeFi 深度用户，你肯定被这个繁琐的流程折磨过无数次了。每当你使用一个新的 dApp，你都需要授权这个 dApp 花费你的代币。

继上一次 Shor 发出了对付出收集中路由问题的周全研讨以后，又有一名酷爱研讨的 Nervos 小伙伴 Cyte 对零学问证实做了细致的研讨。

在这篇文章中，Cyte 会和人人引见零学问证实 (ZKP) 的定义，并将零学问证实与 SNARK 和 STARK 这两个观点举行辨析。

ZKP、SNARK 和 STARK 等这些密码学观点跟着近来区块链的鼓起变得热⻔起来。然则，它们常常会被误会和混用。实在，统统这些观点都属于一个更广义的范畴，叫做证实体系 (Proof System)，或许叫做密码学证实（Cryptographic Proof）。零学问证实和 SNARK、STARK 之间都有交织的部份，但并不相互包含。它们之间的关联可以用一张图来示意。

本文将起首引见证实体系的定义，并议论证实体系的各种性子，重点议论「零学问性」、「学问证实」、「简约性」和「非交互性」。迥殊的，如果一个证实体系具有「零学问性」，那末它就被称为一个「零学问证实」。末了，文章会议论 SNARK 和 STARK 的定义并将其举行比较。

证实体系

一个证实体系 (Proof System) 是一个交互式协定，包含两个介入方 Prover 和 Verifier，以及一个算法 Setup。证实体系的作用是让 Prover 压服 Verifier 置信一件事，我们把这件事叫做一个陈说 (Statement)。

协定入手下手前，须要由或人挪用 Setup 算法。Setup 算法接收一些大众参数作为输入，并输出 Prover 和 Verifier 所需的 Setup 信息，个中 Verifier 获知的信息记为，Prover 获知的信息记为。和的大众部份称为大众参考字符串 (Common Reference String, CRS)。详细由谁、在什么时候挪用 Setup 算法，取决于证实体系的设想。协定一入手下手，Prover 和 Verifier 同时取得输入陈说。Prover 相关于 Verifier 必定要有一些分外的上风，比方更壮大的盘算才能，或许取得了一些分外的输入。除此之外，Prover 和 Verifier 还离别获知了和。Setup 信息猎取的时候取决于证实体系的设想。比方，有多是 Prover 和 Verifier 早就下载好存在各自硬盘里可以重复运用的，也多是协定入手下手前就地输入的。然后 Prover 和 Verifier 入手下手实行证实体系划定的协定。如果 Prover 和 Verifier 都是老实的，那末它们都严厉恪守协定实行。不过，也有大概某一方是歹意的，没有依据协定划定来实行，此时会发作什么事情，取决于证实体系的平安性。如果两方都是歹意的，它们都不恪守协定，那就和这个证实体系没关联了。末了，Verifier 输出 accept 或 reject，示意是不是置信陈说。一个证实体系须要满足两个性子：

完全性 (Completeness)：如果陈说是正确的，而 Prover 和 Verifier 都恪守这个协定，那末 Verifier 以最少的几率输出 accept，这里被称为证实体系的完全性偏差 (Completeness error)

牢靠性 (Soundness)：如果陈说是不正确的，此时 Prover 必定是不老实的，而 Verifier 恪守协定，那末任何 Prover 都不能让 Verifier 输出 accept 的几率凌驾，这个被称为证实体系的牢靠性偏差 (Soundness error)

这两个请求是使得一个证实体系建立的最基本的请求。少了哪一个请求，我们都可以取得相符前提但完全没用的证实体系。比方，如果我们只请求完全性，那就不管 Prover 做什么，Verifier 永久只输出 accept 就好了；如果只请求牢靠性，那就让 Verifier 永久只输出 reject。另外，平常愿望和都不凌驾，而且加起来小于，不然这个证实体系偏差太大，也近乎无用。如果将一个证实体系的牢靠性只对任何盘算才能受限的 Prover 建立，也就是说，盘算才能无穷的对手是有大概诳骗 Verifier 的，此时这个证实体系只要盘算牢靠性 (Computational Soundness)，如许的体系又称为论证体系 (Argument System)。相比之下，对任何 Prover 都平安的牢靠性被称为统计牢靠性 (Statistical Soundness)。

证实体系的其他性子

一个证实体系还可以满足一些其他(并不是必需的)性子

CRS 模子 (CRS model)：如果 Setup 信息是对统统人公然可见的，即 Setup=Setup=Setup，称这个证实体系是在 CRS 模子下的

交互 (Interactive) / 非交互 (Non-interactive)：如果悉数交互历程只要 Prover 向 Verifier 发送一条信息，就称这个体系黑白交互证实体系；不然这个体系就是交互式证实体系

可迁徙 (Transferable) / 可狡赖 (Deniable)：如果陈说是正确的，而且把交互历程发送给其他 Verifier，也可以让其他 Verifier 置信陈说的正确性，这个证实体系就是可迁徙的；不然这个证实体系就是可狡赖的

公然可考证 (Public Verifiable) / 特定考证者 (Designated Verifier)：如果 Setup 是对统统人公然可见的，即任何人都可以成为 Verifier，这个零学问证实体系就是公然可考证的。不然这个体系就是针对特定考证者的

公然随机 (Public coin)：如果 Verifier 的统统音讯的拔取都匀称随机且独立于 Prover 的音讯，就称这个体系是公然随机的

零学问 (Zero-Knowledge)：在陈说是正确的状况下，如果除了的正确性，Verifier 没法从交互中猎取任何其他“学问”，就称这个体系是零学问的

简约性 (Succinctness)：如果这个证实体系是用来证实 NP 言语的，而且证实体系的通讯量比证据还要小，那末这个证实体系就具有简约性

例：证实两个球的色彩差异

Setup 信息：有两个球

陈说：这两个球色彩差异Verifier 盘算才能受限 (蒙上双眼)，Prover 具有一般的目力

Verifier 摆布手各持一个球，展现给 Prover 看。

Verifier 把双手放到背地，接着 (在内心) 随机抛硬币，如果是正面朝上，就交流摆布手里的球，不然不交流。

Verifier 把球拿出来给 Prover 看。

Prover 通知 Verifier 两个球有无交流。

效果：如果 Prover 猜对了，Verifier 输出 accept，不然 Verifier 输出 reject。性子议论完全性如果两球色彩差异，明显 Prover 肯定能以百分之百的几率猜中 Verifier 有无交流球牢靠性如果两球色彩雷同，那末 Prover 只能自觉猜想，只要 1/2 的几率猜中。这个体系的牢靠性偏差为 1/2CRS这个证实体系是在 CRS 模子下的，由于 Setup 信息是公然的交互性这是个交互体系，由于 Prover 和 Verifier 相互发送的信息凌驾一条可迁徙性这个体系是不可迁徙的，即可狡赖的。纵然 Verifier 把交互历程纪录下来展现给其他蒙住眼的人，他们也不能确信两个球色彩差异公然可考证性这个体系是公然可考证的，任何 Verifier 都可以和 Prover 举行这个协定公然随机性这个体系不是公然随机的，由于 Verifier 发送给 Prover 的信息不是匀称随机的零学问性这个体系是零学问的，由于在两个球色彩确切差异的状况下，Prover 的猜想是 Verifier 意料之中的，除了示意陈说 x 的正确性外，没有任何分外学问

主要性

上文中我们给出了证实体系的定义，样例和性子。接下来我们议论证实体系的几个主要的性子。

零学问性

零学问性用来庇护老实的 Prover 不被歹意的 Verifier 诳骗而泄漏证实所需的隐秘证据。

上文中已提到了证实体系的零学问性，将其简朴形貌为 Verifier 没法从交互中猎取任何“学问”。这个形貌是不确切的，由于它并没有给出一个严厉的推断规范。零学问性的定义自身是违直觉的：Prover 明显发送了一些比特数据给 Verifier，为何这个体系会是“零学问”的呢？实际上，“信息”并不等同于“学问”。如果 Verifier 猎取了信息，但取得这些信息并不能让 Verifier 盘算出更多效果，或许说这些信息是 Verifier 本身就可以盘算出来的，那末 Verifier 就没有猎取任何“学问”。在一个证实体系的实行历程当中，Verifier 取得的统统信息包含：；Verifier 本身的随机数；Prover 发送给 Verifier 的统统信息 (记为 )。我们把这些信息称为 Verifier 的“视野”，记为。这些信息是 Verifier 盘算历程当中的统统不肯定性的泉源。肯定了这些信息后，其他的统统都可以肯定性地盘算出来。注意到，是一个随机变量。当 Verifier 与 Prover 实行了证实体系以后，Verifier 会取得这个随机变量的一个样本。如果 Verifier 能在没有 Prover 介入的状况下零丁采样，那末这个体系就是零学问的。我们把采样这个随机变量的算法叫做模拟器 (Simulator)。依据模拟器工作体式格局的差异，有以下差异的定义体式格局：

非黑盒模拟器，相对应的零学问性叫做非黑盒零学问。这个零学问的定义许可每一个 Verifier 都存在一个“独家定制”的模拟器，这类定义许可模拟器针对差异的 Verifier 的完成细节来定制差异的采样历程。

黑盒模拟器，对应的就是黑盒零学问。这个零学问的定义请求存在唯一的模拟器，使得对统统的 Verifier，它都可以采样出。这个唯一的模拟器不大概晓得统统 Verifier 的详细完成细节，所以它只能经由过程黑盒挪用的体式格局来接见 Verifier。不过，模拟器对 Verifier 具有完全的掌握权。模拟器可以决议 Verifier 的随机数，并给 Verifier 输入任何的 Prover 音讯或。所以，在模拟器的眼里，Verifier 是一个黑盒的肯定性算法。

如果模拟器只针对老实 Verifier，对应的是老实 Verifier 零学问 (Honest Verifier ZK)。由于老实 Verifier 的行动是完全在预期中的，模拟器天然可以运用这些信息，因而这个模拟器对 Verifier 的接见黑白黑盒的。

非黑盒模拟器接见到的信息更多，所以非黑盒零学问性比黑盒零学问性更轻易建立。而老实 Verifier 零学问是最轻易完成的。关于老实 Verifier 零学问，这里的老实 Verifier 更正确地说是半老实 (Semi-Honest) 的，或许说“老实但猎奇的”。如许的 Verifier 外表上会恪守协定，但有大概私下里试图从音讯中提取学问。相比之下，歹意 Verifier 的行动是完全不受限定的。Verifier 大概宕机、发送不相符花样的音讯、不按协定划定的散布采样，等等。要证实一个体系对歹意的 Verifier 满足零学问性，就要把统统这些状况都掩盖到。模拟器是一个随机算法，它的输出值也是一个随机变量，记为。零学问性请求和这两个随机变量难以辨别。不过，“难以辨别”这个词也有许多种版本，由此可以推出零学问证实的多种定义：

如果两个随机变量的散布是统计不可辨别的，也就是它们的统计间隔 (Statistical Distance) 可疏忽，就称这个证实体系是统计零学问 (Statistically Zero-Knowledge) 的；如果统计间隔就是 0，又叫做圆满零学问 (Perfect Zero-Knowledge) 的；

如果两个随机变量的散布是盘算不可辨别的，也就是任何多项式时候的随机对手都没法辨别这两个散布，就称这个证实体系是盘算零学问 (Computationally Zero-Knowledge)的。

注意到，零学问的定义中，只请求关于正确的陈说，和的散布难以辨别。关于毛病的陈说，我们并不体贴 Verifier 可以猎取什么学问，由于这类状况下 Prover 自身就是不老实的，没有必要去庇护它，或许说，Prover 既然不恪守协定，那我们的协定设想得再好也庇护不到它。不过，虽然是毛病的状况下，零学问性对的散布不做任何假定，但如果输入毛病的采样取得的被 Verifier 考证经由过程的几率和正确的状况下有明显差异的话，我们就可以借此推断的正确性。这就意味着只能来自一个寻常的 NP 言语。所以，关于难题的 NP 问题，把毛病的输入给模拟器，取得的也可以以一样的几率被考证经由过程。这么一来，零学问性和牢靠性岂不是抵牾的？换句话说，关于毛病的，Prover 为何不能挪用模拟器来诳骗 Verifier？实际上，Prover 不能掌握 Verifier，它也就不能为模拟器供应采样所须要的资本。确实，一个歹意的 Prover 可以去挪用模拟器，然则这对它来讲没用，由于模拟器输出的中的并不是正在与 Prover 交互的 Verifier 的随机数。另外，模拟器输出的也大概和 Verifier 收到的差异而致使考证不经由过程。不过，Prover 调起的模拟器没法猎取 Verifier 的随机数，这已充足保证平安性了，所以交互式证实中纵然是牢固常量也没问题。

学问证实

如果请求 Prover 必需“晓得”一些信息才能让 Verifier 考证经由过程，这个体系就被称为学问证实 (Proof of Knowledge)。学问证实可以看作牢靠性的加强版。学问证实也有盘算意义下的版本，叫做学问论证 (Argument of Knowledge)。

学问证实体系通常是用来证实 NP 言语的。一个 NP 言语是指一个鸠合，使得元素属于可以由一个证据来证实，即存在一个多项式时候的算法可以剖断是不是是属于的正当证据。一般的证实体系使得 Prover 可以向 Verifier 证实。而学问证实体系使得 Prover 可以向 Verifier 证实的不仅是，还可以证实 Prover “晓得” 。也就是说，纵然，如果 Prover 不晓得对应的，也难以考证经由过程。和上一节议论的零学问性相似，“学问性”也须要严厉的定义。一个程序 P “晓得”数据，究竟该如何定义呢？设想一下把这个程序运转在一个虚拟机里，它的随机数是可以由我们随便指定的。它的悉数运转历程当中，CPU 状况的完全历史纪录，以及统统的内存读写操纵，都可以由虚拟机纪录下来。如果这个程序“晓得” ，我们总该从这些纪录中提掏出的信息吧。实际上，这就是提取器 (Extractor) 的一种直观的明白体式格局。提取器就是一个算法，它可以和被提取的程序同时运转，并可以接见到被提取的程序的内部状况。末了，它可以输出提取的效果。上面形貌的提取器黑白黑盒提取器，由于它可以接见被提取程序的内部状况。非黑盒提取器的算法必定要跟着被提取程序的差异而变化。所以，一个证实体系是一个学问证实，是如许定义的：“关于恣意 Prover ，存在一个提取器，它和同时实行，并可以接见到的内部状况。如果和交互后输出 accept，那末就会输出满足前提的。”相似于零学问定义中的模拟器，提取器也可以用黑盒的体式格局定义。提取器没法接见程序的内部状况，但可以挪用这个程序，掌握这个程序的随机数，并读取这个程序的输出。我们引入如许一个暗号，示意提取器经由过程黑盒的体式格局接见一对 Prover 和 Verifier 的交互历程。黑盒提取器对统统的 Prover 只须要有一个就够了，所以学问性证实就可以以下定义：“存在一个提取器，关于恣意 Prover ，如果和交互后输出 accept，那末就会输出满足前提的。”

用示意一个 NP 言语的实例，示意存在言语中的证据。简约性 (Succinctness) 是指一个证实体系所需的通讯量低于的线性函数。换句话说，Prover 和 Verifier 实行这个证实体系，比 Prover 直接把发送给 Verifier，还要节约通讯带宽。有时候，简约性还大概请求 Verifier 在证实体系中的盘算量要低于考证。总之，简约性请求证实体系在效力方面有上风。

我们大概会愿望一个简约证实体系的通讯量到达对数级别或更低，即。但是如许的简约性请求会带来平安性的丧失。由于如果通讯量低达对数级别，那末 Prover 的音讯组合地点的悉数空间是可以在时候内穷举的。但是，体系的牢靠性请求，关于毛病的陈说， Prover 不能找到让 Verifier 考证经由过程的。如果可以考证经由过程的压根不存在，如许确切可以保证牢靠性。但如许就可以经由过程穷举来推断的正当性，那末就不是一个难题问题，这就排除了平常的 NP 言语。如果我们想要平常的 NP 言语的证实体系，我们必需许可纵然关于毛病的，也存在少许的可以考证经由过程的。这类状况下，我们只能分外引入一个平安参数，将通讯量的大小放宽为，使得穷举的复杂度到达，如许最少完成了盘算意义下的牢靠性。同时，通讯量相关于仍然是对数级别的，所以满足了简约性。综上，关于平常的 NP 言语，(对数级别的) 简约证实体系只能是论证体系。

非交互性

非交互性 (Non-Interactivity) 是指证实体系的悉数交互只要 Prover 向 Verifier 发送的一条音讯，这个音讯叫做一个证实，记为。非交互性可以带来许多的方便，为证实体系带来更多的运用场景。比方，在区块链体系中，非交互性的零学问证实可以附在生意业务中，供任何人随时检验，而不须要生意业务的作者随时在线与考证者交互。

任何 NP 言语都天然具有一个非交互证实协定，也就是 Prover 直接将证据发送给 Verifier，而且这个证实是学问证实。所以，组织一个纯真具有非交互性的证实体系意义不大。非交互性只要和前面议论的两个性子，即零学问性或简约性组合起来才有意义。非交互性 + 零学问将零学问性和非交互性连系起来，就有了非交互零学问 (Non-Interactive Zero-Knowledge, NIZK)。我们之前在议论零学问性时讲到，零学问性之所以和牢靠性不抵牾，是由于挪用模拟器采样的中的大几率和与 Prover 交互的 Verifier 的随机数差异。然则，关于非交互零学问，我们要从新审阅一下这个推理历程。在交互证实中，一个随机数为的 Verifier 可以考证经由过程的 Prover 音讯，直接搬到随机数为的 Verifier 那边就很大概考证不经由过程了。所以，在交互式证实中，的正确性不是全局的，而是依靠的。而在非交互证实中，Prover 没有收到 Verifier 的任何音讯，所以 Prover 的盘算历程没有用到 Verifier 的随机数。所以，为了到达证实体系的完全性，老实的 Prover 输出的，关于大部份 Verifier 随机数都是能考证经由过程的。所以，非交互证实中的的正确性是全局的，不依靠任何。零学问性请求，Verifier 的视野和模拟器的输出不可辨别。这意味着，如果零丁视察这它们部份重量，它们也是不可辨别的。即和中的也是不可辨别的。所以，一个歹意的 Prover 可以挪用模拟器来输出。这在交互式证实中不成问题，歹意的 Prover 仅仅是取得了关于某个正确的罢了。但在非交互证实中，的正确性是不依靠的，就会带来平安问题。这时候，就要轮到发挥作用了。虽然的正确性不再依靠于，但照样依靠于的。为了牢靠性，我们愿望，给定和陈说难以盘算出可以经由过程考证的。虽然模拟器在给定时可以同时输出一对，然则难以先盘算前者再盘算后者。详细是如何做到这一点的，后续文章中引见详细计划时会细致解说。非交互性 + 简约性上文提到，简约性的证实体系必定是论证体系。连系非交互性，就有了简约非交互式论证 (Succinct Non-interactive ARGument, SNARG)。实际上，满足 SNARG 定义的体系早在 2000 年就由 Micali 组织出来了，而这个名字是厥后才涌现的。如果一个 SNARG 同时是一个学问论证，它就被称为简约非交互式学问性论证 (Succinct Non-interactive ARgument of Knowledge, SNARK)。SNARK 这个称号由论文 BCCT12 开创，如今已成为零学问证实范畴最热点的观点之一。实在 SNARK 只具有简约性和非交互性，并不肯定具有零学问性。如果有零学问性，应当叫 zkSNARK。STARK 和 SNARK 辨析另一个常常和 SNARK 一同提到的观点是 STARK。它和 SNARK 只要一字之差，但有许多差异。下面我们比较一下这两个观点。共同点：

都是学问论证 (ARK)，即只要盘算意义下的牢靠性，且证实是学问性的

区分：

SNARK 的 “S” 是简约性 (Succintness)，而 STARK 的 “S” 是可扩展性 (Scalability)，它在简约性的基础上还请求 Prover 复杂度至多是拟线性 (Quasi-linear) 的，即，而 Setup 的盘算复杂度最多是对数的

透明性 (Transparent)：STARK 不须要可托第三方 Setup；而 SNARK 没有这个限定

非交互性 (Non-Interactivity)：SNARK 肯定黑白交互的，而 STARK 没有这个限定

可以看出，SNARK 比 STARK 唯一多出的限定就黑白交互性。尽管如此，经由过程后续文章将要引见的 Fiat-Shamir 变更，STARK 平常都可以转化为非交互证实，转化的效果必定是一个 SNARK。在这类意义上，可以把 STARK 看作 SNARK 的子集。上述 SNARK 和 STARK 的定义是这两个名词的广义涵义。狭义上，它们离别指代两个详细的组织计划。个中 SNARK 指的是以 Groth16 计划为代表的一系列基于 QAP 和双线性对的 zkSNARK 组织计划。而 STARK 在狭义上就特地指代 Ben-Sasson 等人在 2018 年提出的基于 AIR 和 FRI 的那一个计划。

小结

本文引见了证实体系的定义，并议论了证实体系的各种性子，重点议论了“零学问性”、“学问证实”、“简约性”和“非交互性”，诠释了如何用模拟器来定义零学问性，以及用提取器来定义学问性证实。末了，文章议论并比较了 SNARK 和 STARK。

参考资料

Goldreich. Foundations of Cryptography, Volume 1. Basic Tools. 2001.

ZKProof Community. ZKProof Community Reference. 2019. https://docs.zkproof.org/reference.pdf

Yehuda Lindell. How To Simulate It – A Tutorial on the Simulation Proof Technique. 2018.

Eli Ben-Sasson. A Cambrian Explosion of Crypto Proofs. https://nakamoto.com/cambrian-explosion-of-crypto-proofs/