首页 手机兼职平台区块链正文

硬核 | 深化解析零常识证明技能特性

admin 区块链 2020-11-29 20:31:21 6123 0

|Cyte

ShorNervosCyte

在这篇文章中,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 获悉的信息记为 SetupP 。SetupP 和 SetupV 的公共部分称为公共参阅字符串 (Common Reference String, CRS)。详细由谁、在什么时候调用 Setup 算法,取决于证明体系的规划。

协议一开端,Prover 和 Verifier 一同得到输入陈说 x。Prover 相关于 Verifier 必定要有一些额定的优势,例如更强壮的核算才能,或许得到了一些额定的输入 w。除此之外,Prover 和 Verifier 还别离获悉了 SetupP 和 SetupV。Setup 信息获取的时刻取决于证明体系的规划。例如,有或许是 Prover 和 Verifier 早就下载好存在各自硬盘里能够重复运用的,也或许是协议开端前当场输入的。

然后 Prover 和 Verifier 开端履行证明体系规则的协议。假如 Prover 和 Verifier 都是诚笃的,那么它们都严厉恪守协议履行。不过,也有或许某一方是歹意的,没有依照协议规则来履行,此刻会产生什么事情,取决于证明体系的安全性。假如两方都是歹意的,它们都不恪守协议,那就和这个证明体系没联系了。

最终,Verifier 输出 accept 或 reject,表明是否信任陈说 x。

一个证明体系需求满意两个性质:

完整性 (Completeness):假如陈说 x 是正确的,而 Prover 和 Verifier 都恪守这个协议,那么 Verifier 以至少 1- εc 的概率输出 accept,这儿 εc 被称为证明体系的完整性差错 (Completeness error)

可靠性 (Soundness):假如陈说 x 是不正确的,此刻 Prover 必定是不诚笃的,而 Verifier 恪守协议,那么任何 Prover 都不能让 Verifier 输出 accept 的概率超越 εs,这个 εs 被称为证明体系的可靠性差错 (Soundness error)

这两个要求是使得一个证明体系建立的最基本的要求。少了哪个要求,咱们都能够得到契合条件但彻底没用的证明体系。例如,假如咱们只要求完整性,那就不管 Prover 做什么,Verifier 永久只输出 accept 就好了;假如只要求可靠性,那就让 Verifier 永久只输出 reject。此外,一般期望 εs 和 εc都不超越 ,并且加起来小于 ,不然这个证明体系差错太大,也近乎无用。

假如将一个证明体系的可靠性只对任何核算才能受限的 Prover 建立,也便是说,核算才能无限的敌手是有或许诈骗 Verifier 的,此刻这个证明体系只要核算可靠性 (Computational Soundness),这样的体系又称为证明体系 (Argument System)。相比之下,对任何 Prover 都安全的可靠性被称为核算可靠性 (Statistical Soundness)

证明体系的其他性质

一个证明体系还能够满意一些其他 (并非必需的) 性质

  • CRS 模型 (CRS model):假如 Setup 信息是对悉数人揭露可见的,即 Setup=SetupP=SetupV,称这个证明体系是在 CRS 模型下的

  • 交互 (Interactive) / 非交互 (Non-interactive):假如整个交互进程只要 Prover 向 Verifier 发送一条信息,就称这个体系对错交互证明体系;不然这个体系便是交互式证明体系

  • 可搬迁 (Transferable) / 可狡赖 (Deniable):假如陈说 x 是正确的,并且把交互进程发送给其他 Verifier,也能够让其他 Verifier 信任陈说 x 的正确性,这个证明体系便是可搬迁的;不然这个证明体系便是可狡赖的

  • 揭露可验证 (Public Verifiable) / 特定验证者 (Designated Verifier):假如 SetupV 是对悉数人揭露可见的,即任何人都能够成为 Verifier,这个零常识证明体系便是揭露可验证的。不然这个体系便是针对特定验证者的

  • 揭露随机 (Public coin):假如 Verifier 的悉数音讯的选取都均匀随机且独立于 Prover 的音讯,就称这个体系是揭露随机的

  • 零常识 (Zero-Knowledge):在陈说 x 是正确的状况下,假如除了 x 的正确性,Verifier 无法从交互中获取任何其他「常识」,就称这个体系是零常识的

  • 简练性 (Succinctness):假如这个证明体系是用来证明 NP 言语的,并且证明体系的通信量比依据 w 还要小,那么这个证明体系就具有简练性

例:证明两个球的色彩不同

Setup 信息:有两个球

陈说 x :这两个球色彩不同

Verifier 核算才能受限 (蒙上双眼),Prover 具有正常的视力

  1. Verifier 左右手各持一个球,展现给 Prover 看。
  2. Verifier 把双手放到背面,接着 (在心里) 随机抛硬币,假如是正面朝上,就交流左右手里的球,不然不交流。
  3. Verifier 把球拿出来给 Prover 看。
  4. Prover 告知 Verifier 两个球有没有交流。

成果:假如 Prover 猜对了,Verifier 输出 accept,不然 Verifier 输出 reject。

硬核 | 深化解析零常识证明技能特性

重要性质

上文中咱们给出了证明体系的界说,样例和性质。接下来咱们评证分明体系的几个重要的性质。

零常识性

零常识性用来维护诚笃的 Prover 不被歹意的 Verifier 诈骗而走漏证明所需的隐秘依据。

上文中现已说到了证明体系的零常识性,将其简略描绘为 Verifier 无法从交互中获取任何「常识」。这个描绘是不确切的,由于它并没有给出一个严厉的判别规范。

零常识性的界说自身是违直觉的:Prover 分明发送了一些比特数据给 Verifier,为什么这个体系会是「零常识」的呢?

实际上,「信息」并不等同于「常识」。假如 Verifier 获取了信息,但取得这些信息并不能让 Verifier 核算出更多成果,或许说这些信息是 Verifier 自己就能够核算出来的,那么 Verifier 就没有获取任何「常识」。

在一个证明体系的履行进程中,Verifier 取得的悉数信息包含:SetupV;Verifier 自己的随机数 r;Prover 发送给 Verifier 的悉数信息 (记为 p)。咱们把这些信息称为 Verifier 的「视界」,记为 ViewV = (SetupV,r,p)。这些信息是 Verifier 核算进程中的悉数不确认性的来历。确认了这些信息后,其他的悉数都能够确认性地核算出来。

注意到,ViewV 是一个随机变量。当 Verifier 与 Prover 履行了证明体系之后,Verifier 会取得这个随机变量的一个样本。假如 Verifier 能在没有 Prover 参加的状况下单独采样 ViewV,那么这个体系便是零常识的。

咱们把采样 这个随机变量的算法叫做模拟器 (Simulator)。依据模拟器工作方法的不同,有如下不同的界说方法:

  1. 非黑盒模拟器,相对应的零常识性叫做非黑盒零常识。这个零常识的界说答应每个 Verifier 都存在一个「独家定制」的模拟器,这种界说答应模拟器针对不同的 Verifier 的完成细节来定制不同的采样进程。
  2. 黑盒模拟器,对应的便是黑盒零常识。这个零常识的界说要求存在仅有的模拟器,使得对悉数的 Verifier,它都能够采样出 SetupV 。这个仅有的模拟器不或许知道悉数 Verifier 的详细完成细节,所以它只能经过黑盒调用的方法来拜访 Verifier。不过,模拟器对 Verifier 具有彻底的操控权。模拟器能够决议 Verifier 的随机数 r,并给 Verifier 输入任何的 Prover 音讯或 SetupV 。所以,在模拟器的眼里,Verifier 是一个黑盒确实认性算法。
  3. 假如模拟器只针对诚笃 Verifier,对应的是诚笃 Verifier 零常识 (Honest Verifier ZK)。由于诚笃 Verifier 的行为是彻底在预期中的,模拟器天然能够使用这些信息,因而这个模拟器对 Verifier 的拜访对错黑盒的。

非黑盒模拟器拜访到的信息更多,所以非黑盒零常识性比黑盒零常识性更简单建立。而诚笃 Verifier 零常识是最简单完成的。

关于诚笃 Verifier 零常识,这儿的诚笃 Verifier 更精确地说是半诚笃 (Semi-Honest) 的,或许说「诚笃但猎奇的」。这样的 Verifier 外表上会恪守协议,但有或许私下里企图从音讯中提取常识。

相比之下,歹意 Verifier 的行为是彻底不受约束的。Verifier 或许宕机、发送不契合格局的音讯、不按协议规则的散布采样,等等。要证明一个体系对歹意的 Verifier 满意零常识性,就要把悉数这些状况都掩盖到。

模拟器是一个随机算法,它的输出值也是一个随机变量,记为 SimV。零常识性要求 ViewV 和 SimV 这两个随机变量难以差异。不过,「难以差异」这个词也有许多种版别,由此能够推出零常识证明的多种界说:

  • 假如两个随机变量的散布是核算不行差异的,也便是它们的核算间隔 (Statistical Distance) 可疏忽,就称这个证明体系是核算零常识 (Statistically Zero-Knowledge)的;假如核算间隔便是 0,又叫做完美零常识 (Perfect Zero-Knowledge)的;

  • 假如两个随机变量的散布是核算不行差异的,也便是任何多项式时刻的随机敌手都无法差异这两个散布,就称这个证明体系是核算零常识 (Computationally Zero-Knowledge)的。

注意到,零常识的界说中,只要求关于正确的陈说 x, ViewV 和 SimV 的散布难以差异。关于过错的陈说,咱们并不关怀 Verifier 能够获取什么常识,由于这种状况下 Prover 自身便是不诚笃的,没有必要去维护它,或许说,Prover 已然不恪守协议,那咱们的协议规划得再好也维护不到它。

不过,尽管 是过错的状况下,零常识性对 SimV 的散布不做任何假定,但假如输入过错的 x 采样得到的 SimV 被 Verifier 验证经过的概率和 x 正确的状况下有明显不同的话,咱们就能够借此判别 x 的正确性。这就意味着 x 只能来自一个普通的 NP 言语。所以,关于困难的 NP 问题,把过错的 x 输入给模拟器,得到的 SimV 也能够以相同的概率被验证经过。

这么一来,零常识性和可靠性岂不是对立的?换句话说,关于过错的 x,Prover 为什么不能调用模拟器来诈骗 Verifier?实际上,Prover 不能操控 Verifier,它也就不能为模拟器供给采样 SimV 所需求的资源。确实,一个歹意的 Prover 能够去调用模拟器,可是这对它来说没用,由于模拟器输出的 SimV中的 r 并不是正在与 Prover 交互的 Verifier 的随机数。此外,模拟器输出的 SetupV也或许和 Verifier 收到的 SetupV 不同而导致验证不经过。不过,Prover 调起的模拟器无法获取 Verifier 的随机数,这现已满意确保安全性了,所以交互式证明中 SetupV 即使是固定常量也没问题。

常识证明

假如要求 Prover 有必要「知道」一些信息才能让 Verifier 验证经过,这个体系就被称为常识证明 (Proof of Knowledge)。常识证明能够看做可靠性的加强版。常识证明也有核算含义下的版别,叫做常识证明 (Argument of Knowledge)

常识证明体系通常是用来证明 NP 言语的。一个 NP 言语是指一个调集 L,使得元素 x 归于 L 能够由一个依据 w 来证明,即存在一个多项式时刻的算法能够断定 w 是否是 x 归于 L 的合法依据。

硬核 | 深化解析零常识证明技能特性

简练性

硬核 | 深化解析零常识证明技能特性

综上,关于一般的 NP 言语,(对数等级的) 简练证明体系只能是证明体系。

非交互性

非交互性 (Non-Interactivity)是指证明体系的悉数交互只要 Prover 向 Verifier 发送的一条音讯,这个音讯叫做一个证明,记为π 。非交互性能够带来许多的便当,为证明体系带来更多的使用场景。例如,在区块链体系中,非交互性的零常识证明能够附在买卖中,供任何人随时查验,而不需求买卖的作者随时在线与验证者交互。

任何 NP 言语都天然具有一个非交互证明协议,也便是 Prover 直接将依据发送给 Verifier,并且这个证明是常识证明。所以,结构一个单纯具有非交互性的证明体系含义不大。非交互性只要和前面评论的两个性质,即零常识性或简练性组合起来才有意思。

非交互性 + 零常识

将零常识性和非交互性结合起来,就有了非交互零常识 (Non-Interactive Zero-Knowledge, NIZK)

咱们之前在评论零常识性时讲到,零常识性之所以和可靠性不对立,是由于调用模拟器采样的 SimV 中的 r 大概率和与 Prover 交互的 Verifier 的随机数不同。可是,关于非交互零常识,咱们要从头审视一下这个推理进程。

在交互证明中,一个随机数为 r1 的 Verifier 能够验证经过的 Prover 音讯 p,直接搬到随机数为 r2 的 Verifier 那里就很或许验证不经过了。所以,在交互式证明中,p 的正确性不是大局的,而是依靠 r 的。

而在非交互证明中,Prover 没有收到 Verifier 的任何音讯,所以 Prover 的核算进程没有用到 Verifier 的随机数 r。所以,为了到达证明体系的完整性,诚笃的 Prover 输出的 p,关于大部分 Verifier 随机数 都是能验证经过的。所以,非交互证明中的 p 的正确性是大局的,不依靠任何 r。

硬核 | 深化解析零常识证明技能特性

非交互性 + 简练性

上文说到,简练性的证明体系必定是证明体系。结合非交互性,就有了简练非交互式证明 (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 比 STARK 仅有多出的约束就对错交互性。尽管如此,经过后续文章即将介绍的 Fiat-Shamir 改换,STARK 一般都能够转化为非交互证明,转化的成果必定是一个 SNARK。在这种含义上,能够把 STARK 看做 SNARK 的子集。

上述 SNARK 和 STARK 的界说是这两个名词的广义寓意。狭义上,它们别离指代两个详细的结构计划。其间 SNARK 指的是以 Groth16 计划为代表的一系列根据 QAP 和双线性对的 zkSNARK 结构计划。而 STARK 在狭义上就专门指代 Ben-Sasson 等人在 2018 年提出的根据 AIR 和 FRI 的那一个计划。

小结

SNARKSTARK

mp.weixin.qq.com

版权声明

本文仅代表作者观点,不代表网赚之家本站立场。
本文系作者授权发表,未经许可,不得转载。

评论