原文标题:《零常识证明最简介绍:前史、原理、完结》
撰文:DeGate

暗码学能够说是区块链技能的基石,而其间的零常识证明更是由于深度符合区块链的技能特色,而得到了广泛的运用和重视。

本文旨在用最简略的语言和方法,向咱们介绍零常识证明相关的前史、概念、原理、技能完结以及开展现状。

那么让咱们开端吧。

前史和起源

暗码学是一门能够追溯到 2000 多年前的陈旧学问,其开展前史首要能够划分为以下几个阶段:

古典暗码学

这一时期的暗码学首要被运用于军事范畴,如何有用的传递密文,又能避免被敌人截获后破解,是其首要考量。16 世纪由法国人创造的「维吉尼亚暗码」是古典暗码理论开展上的一个重要里程碑,它运用一个词组作为密钥,词组中每一个字母都将确定一个替换表,「维吉尼亚暗码」循环的运用每一个替换表完结明文字母到密文字母的变化。

  • 明文:ilovebitcoin

  • 密钥:satoshi

简明理解零知识证明历史、原理与发展现状

关于第一个字母 i,取第 i 行第 s 列,得到 A;第二个字母 l,取第 l 行第 a 列,得到 L…顺次循环,最后得到密文:ALHJWIQLCHWF。可见,在不知道密钥的前提下,不凭借核算机现已非常难以破解这样的暗码。

近代暗码学

这一阶段真正的开端源于香农在 20 世纪 40 时代末宣布的一系列论文,特别是 1949 年的「Communication Theory of Secrecy Systems (保密体系通讯理论)」,把已有数千年前史的暗码学面向了基于信息论的科学轨道,暗码学终于从艺术转向科学。

这一时期的重要突破是 DES 的呈现,直至今日也只能用穷举法对其进行破解。DES 加密算法风行国际,并在金融等商业范畴得到了广泛的运用。

现代暗码学

1977 年,麻省理工学院的 Ron Rivest、Adi Shamir、Leonard Adleman 提出的非对称加密算法 RSA,有用的处理了密钥传送的问题,标志着暗码学进入了百家争鸣的现代阶段。

简明理解零知识证明历史、原理与发展现状

1989 年,由麻省理工学院研究人员 Goldwasser、Micali 及 Rackoff 提出了「零常识证明」的概念,其时的他们必定不曾想到,若干年后呈现的区块链技能完全激活了零常识证明的运用,而零常识证明则为区块链技能供给了一种绝佳的处理方案。零常识证明的办法特色和区块链技能的体系特色达成了完美的符合。

零常识证明及 zkSNARK

零常识证明是指,在不揭晓我所知道或具有的某样东西的前提下,向别人证明我有很大概率的确知道或具有这样东西。

zkSNARK 则是在区块链中运用最广泛的一种零常识证明,其全称是「zero-knowledge Succinct Non-Interactive Arguments of Knowledge (简练非交互式零常识证明)」。

光听界说,咱们必定一头雾水,本节将借用一个比如,尽可能接地气的向咱们介绍这两个概念。

Alice、Bob 和 Charlie 都是数独爱好者,所谓数独是这样一种游戏,玩家需求根据 9×9 盘面上的已知数字,推理出一切剩余空格的数字,并满意每一行、每一列、每一个粗线宫(3x3)的数字均含 1 到 9,且不重复。

简明理解零知识证明历史、原理与发展现状

有一天 Alice 规划了一道巨难的数独标题来考 Bob 和 Charlie,Bob 苦思冥想了几天也做不出,便向 Alice 抱怨这必定是道无解的标题。Alice 不想将实践的解告知 Bob,可是又需求证明她的确知道解,所以她规划了一种巧妙的「零常识证明」的方法。

  • 证明(The Proof )

Alice 拿出 81 (9x9)张空白的卡片,并在每张纸上写上 1-9 中的一个数字,接着她将代表谜面的卡片数字面朝上、代表谜底的卡片数字面朝下都放在桌上,并组成了 9x9 的矩阵。

简明理解零知识证明历史、原理与发展现状

  • 随机应战(The Random Challenge)

接下来怎样让 Bob 供认这便是正确的解呢?很简略,由 Bob 随机挑选行、列或是粗线宫中的一种进行验证,假如挑选行,则将这 81 张卡片按 9 行别离放到 9 个麻布袋中,摇匀并保证卡片次序打乱。

简明理解零知识证明历史、原理与发展现状

  • 验证(The Verify)

简明理解零知识证明历史、原理与发展现状

  • 简练(Succinct)

虽然数独游戏有 3 种状况需求验证(行、列、粗线宫),但每次验证时 Bob 实践只需求验证其间的一种,这有用减少了验证工作量,供给给验证者的实践是一个比原命题小的多的证明,这便是所谓的简练。

  • 重复(Repeat)

之后重复这个随机验证进程,咱们假定 Alice 命运很好,每次都能提早猜中 Bob 会挑选哪种验证方法,并以此来模仿一个解,那么她经过 1 次验证的概率为 1/3,经过 2 次验证的概率为 1/9,经过 10 次验证概率就只要 1/59049 了。在不厌其烦的进行了 20 次验证之后,Bob 无奈的供认,Alice 是真的知道这个答案的解,由于 Alice 凭命运经过验证的概率只要 35 亿分之一!(这也是为何咱们说零常识证明是在概率上成立的证明)

  • 模仿(The Simulation)

这个时分,Charlie 也来向 Alice 抱怨这个标题的无解,Alice 和 Bob 又重复了刚才的证明,没想到却没有得到 Charlie 的认可。Charlie 提出了这个证明中的漏洞,假如 Bob 和 Alice 是一伙的,每次 Bob 都会提早告知 Alice 他要挑选的验证方法,那么 Alice 就能够很简单的在没有解的状况下模仿出一个证明来经过这些测验。

  • 非交互式证明(Non-Interactive Proofs)

不行能让每个持有这种怀疑的人都重复一遍 Bob 进行的随机验证,所以三个小伙伴规划了一台奇特的机器,Alice 只需求提交一次卡片,这台机器就能够依照初始设置好的验证序列,自动化的对这些卡片进行重复验证。验证从交互式的,变成了非交互式的。这儿咱们要注意,并不是说非交互式证明就没有重复随机实验这个进程。实践上,只不过是随机点不由验证者给出,而是由一个可信的第三方在初始化阶段就给出,这样一来,证明者就能够直接给出证明,验证者只需求验证证明即可,验证者和证明者之间不再需求交互。

简明理解零知识证明历史、原理与发展现状

  • 可信设置典礼(Trusted Setup Ceremony)

其间最有趣也最重要的环节便是验证序列的初始设置。在机器启动前,会有一排设置旋钮,经过这些旋钮能够选定每一轮的验证方法。在设置这些旋钮时,每个人顺次进入放置机器的房间,挑选一个旋钮并设置好,之后就用一个铁盒子完全焊死这个旋钮,让其他人无法看见也无法改动这个旋钮的挑选。为了让初始设置尽可能的可信,小伙伴们邀请了镇长、小学校长和警察局长这三位小镇上最德高望重的长者来参加设置典礼,咱们都相信他们必定不行能参加作假,因而他们称之为「可信任的初始设置典礼」。

简明理解零知识证明历史、原理与发展现状

一台数独游戏的简练非交互式零常识证明机,诞生了!

zkSNARK 的技能完结

经过上一节咱们现已弄明白了零常识证明和 zkSNARK 的基本概念和原理,这一节咱们再来一窥 zkSNARK 的技能完结。能够说整个完结进程相当的繁琐晦涩,且需求必定的背景常识,因而本末节只力图讲清楚其间心思维,而不拘泥于过分杂乱的数学推导。

咱们从一个方程式开端,X^3 + X + 5 = 35,显然解是 3。那么现在,证明者如何向验证者证明自己知道方程的解是 3,而又不告知验证者这个解呢?

首要,咱们将方程转化为核算机语言,这很简单完结:

y = x*3
return x + y + 5

接着,咱们将上面的代码拍平。所谓将代码拍平,是指让代码一次只做一件事,形如 x = y op z。

拍平后,代码变成以下语句:

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym2 + 5

然后,咱们引进 R1CS 一阶束缚体系(rank-1 constraint system),R1CS 是一个由三向量组(a, b, c)组成的序列,一起有一个解向量 s,s 满意 s·a * s·b - s·c = 0。

在本例中,s 的结构为(~one\, x\, ~out\, sym_1\, y\, sym_2),可见其由一个特别的 ~one、方程的解 x、方程的输出 ~out 和一系列中心变量(拍平后的语句等号左边的变量)构成,其顺序不重要,只要保证有序即可。

咱们把语句改换成如下方法,来方便咱们求解 abc:

x * x - sym_1 = 0
sym_1 * x - y = 0
y + x - sym_2 = 0
sym_2 + 5 - ~out = 0

咱们很简单得出第一个式子对应的三个向量:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

推导进程其实很简略,咱们知道要满意 s·a * s·b - s·c = 0,那么对应第一个式子 x * x - sym_1 = 0,只需求 s·a = x、s·b = x、s·c = sym_1 即可,而 s =(~one\, x\, ~out\, sym_1\, y\, sym_2),那么 a 只要在 x 的方位等于 1,其余方位等于 0,即得出(0,1,0,0,0,0)。

咱们可能对上面一系列眼花缭乱的改换感到不可思议,咱们究竟在做什么?这儿要揭晓谜底了,咱们对每个式子验证 s·a * s·b - s·c = 0,其本质是在验证每一步都得到了正确的核算,也即假如咱们能够验证每一步都是正确的,那么最终成果也必定是正确的。

以上的每一步,看似都在舍近求远,由于 s 里本身就包含了方程的解 x,验证者只需把 x 代入就能进行验证。但从另一个角度看,经过这一系列的转换,咱们构建了一种将证明和验证别离的方法。在证明进程中,证明者需求知道解并生成一系列中心成果,而验证者则只需求验证其一系列成果构成的解向量是否满意一系列束缚,而不需求关怀这个解到底是多少。

现在只剩一个问题留下处理,便是能否经过一种方法,让验证者看不到裸着的解 x,一起仍然能够进行验证进程。答案是必定的,借由椭圆曲线、双线性对运算和指数常识假定这一系列数学手段咱们就能够做到这一点,由于其推导进程过于杂乱,本文不做赘述。整个 zkSNARK 的技能完结流程参见下图,需求了解更多细节的同学能够阅读参考资料中给出的 Vitalik 的文章。

简明理解零知识证明历史、原理与发展现状

零常识证明开展现状

零常识证明协议

零常识证明目前有如下几种协议,每个协议代表一条完结零常识证明的路途,不同路途最后会发生不一样的效果。

简明理解零知识证明历史、原理与发展现状

其间,安全性最高的是 STARKs 算法,其不依赖数学难题假定,具有抗量子性,并完结了通明通用字符串;Proof size 最小的 snarks 协议是 groth16 算法;Plonk 是 SNARK 协议中的一个算法,Proof size 和安全性处于适中状态。

SNARKs 协议算法

作为区块链技能中运用最广泛的 SNARKs,现已开展出了诸多各具特色的协议算法:

  • Groth16:Groth16 是目前最快、数据量最小的 zk-SNARK,被用于 Zcash 等。Groth16 的 CRS (the Common Reference String)不是通用的,其设置需求绑定到一个特定的电路。由于其速度和证明的小数据量,因而常常被新的 zk-SNARK 拿来比较性能。

Groth16 论文链接

  • Sonic:Sonic 是一种早期的通用 zk-SNARK 协议,支撑通用、可升级的参考字符串,论文宣布于 2019 年 1 月。Sonic 的证明巨细固定,可是验证成本高,理论上能够将多个证明分批验证以取得更好的性能。下面罗列的许多新的 zk-SNARK 都是基于 Sonic。

Sonic 论文链接

  • Fractal:Fractal 是一种允许递归的 zk-SNARK。经过对电路的预处理完结了通明设置。证明最大 250KB,这比其他构建生成的证明都要大的多。

Fractal 论文链接

  • Halo:Halo 支撑递归证据安排,无需可信设置,与其他新的 zk-SNARK 构建不同,Halo 的验证时刻是线性的。

Halo 论文链接

  • SuperSonic:Sonic 的改进版,是第一个在验证时刻和证明数据量方面实用化的通明 zk-SNARK。

SuperSonic 论文链接

  • Marlin:Sonic 的改进版,证明时刻缩短 10 倍,验证时刻缩短 4 倍。

Marlin 论文链接

  • Plonk:Sonic 的改进版,证明时刻缩短 5 倍。

Plonk 论文链接

硬件成本

当时零常识证明缺乏专用硬件,导致硬件成本偏高,租用云服务器满负荷下成本约为 0.002 元 / 笔,有空载状况下约为 0.02 元 / 笔。Vetalik 曾提出一个想象,当以太坊一致机制改为 PoS,不需求那么多挖矿硬件后,这些算力能够经改造后转向支撑零常识证明,这可能有用下降零常识证明的运转成本。

写在最后

现在,零常识证明现已在区块链范畴大放异彩,包括第一个完结 zkSNARK 的匿名加密货币 Zcash (ZEC)、Layer2 的首要处理方案 zk Rollup 等等。

DeGate 团队也将在产品完结中大量运用零常识证明,藉由其强大特性,咱们将 Orderbook 的撮合买卖转到 MatchNode (Layer3)中进行,运用户能够实时的挂单、撤单和成交,且其间挂单撤单免费;之后再将订单批量成果生成证明,传回 Layer2 上进行验证,这让 DeGate 在继承以太坊安全性的一起,既能够躲藏下单关键信息又能够有用下降 Layer2 上的 Gas 费消耗。而咱们的最终目标是,无论在操作体验上,还是手续费消耗上,都使 DeGate 到达比美中心化买卖所的水平。

视野开拓

我们需要时间来了解自己,找出自己感兴趣的东西。只有在做一些使自己充满热情和力量的事情时,我们才是真正处于最好的状态,才能使金钱滚滚而来。 我们需要时间来做出一个原则性的决定,尽自己的义务去履行这个决定。因此,每个人都必须在生活中明确地做出决定:是想优化自己还是削弱自己。 优化自己指的是,学习如何以最佳的方式来运用时间、方法、才能、金钱以及与他人合作,其目的是达到最优结果。如果你想优化你的生活,你就应该不断努力成为你能成为的最优秀的人。 相反,大多数人都毫无计划地生活着,同时也削弱了自己。他们尝试过一种得过且过的生活。 他们不了解自己的天赋,当机会出现时,他们也识别不出来。-《财务自由之路》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注