新2正网代理开户www.hg108.vip)是一个开放皇冠正网即时比分、新2正网代理开户的平台。新2正网代理开户平台(www.hg108.vip)提供最新皇冠登录,皇冠APP下载包含新皇冠体育代理、会员APP,提供皇冠正网代理开户、皇冠正网会员开户业务。

原文题目:An approximate introduction to how zk-SNARKs are possible

原文作者:Vitalik Buterin

原文泉源:vitalik.ca

编者注:说到已往十年来降生的最强密码学手艺,一定免不了提及零知识证实 (zero knowledge proof)。在区块链领域中,它们有两大应用场景:可扩展性和隐私。zk-SNARK 作为其中一种 zkp 手艺,在近几年来也获得了较大的突破,以太坊上泛起了诸如 zkSyncScrollHermez 等此类使用 zk-SNARK 证实的通用扩容解决方案。

然而,实现 zk-SNARK 并不简朴,由于对某个声明天生了 zk-SNARK 证实之后,验证者需要以某种方式检查盘算中的数百万个步骤。多项式答应就是在这里施展其作用,即可以将盘算编码为多项式,然后使用一种特殊类型的多项式“哈希”(多项式答应),以允许验证者在极短的时间内验证多项式等式,即便这些盘算背后的多项式规模无比大。

在本文中,Vitalik 先容了 zk-SNARK 手艺的事情原理和难点,然后注释了多项式以及多项式答应若何让 zk-SNARK 的实现加倍高效。

稀奇谢谢 Dankrad FeistKarl Floersch 以及 Hsiao-wei Wan 的反馈和校对。

已往十年来降生的最强密码学手艺大提要数通用精练零知识证实,通常称为 zk-SNARK(zero knowledge succinct arguments of knowledge)zk-SNARK 允许你天生一个证实 (这个证实是针对一些运算得出的特定输出,可用于对该运算的验证),通过这种方式,纵然底层盘算十分耗时,该证实也可以被快速验证。“ZK”(零知识)为证实新增了一个分外特征:证实可以隐藏盘算的某些输入。

例如,您可以对以下声明天生一个证实:“我知道一个隐秘值,若是你将数字添加到挑选的单词 cow 的末尾,然后对其举行 1 亿次 SHA256 哈希运算,那么输出的哈希值以 0x57d00485aa 开头”。验证者验证该证实的耗时可远小于自行举行 1 亿次哈希运算的耗时,而且证实也不会泄露隐秘值。

在区块链领域中,该手艺有两大应用场景:

  1. 隐私:你可以证实你有权转移某些资产(你收到了该资产,而且你还没有转走),而不透露该资产的泉源。这不会对外泄露生意双方的信息,确保了生意的平安性。

然而,zk-SNARK 是相当庞大的;现实上,就在 2014-17 年,它们还常被称为“月亮数学”。好新闻是,从那时起,协议愈发简化,我们对它们的明白也愈发深入。本篇博客将试图以一种数学水平通俗的人能明白的方式来注释 ZK-SNARKs 的事情原理。

注重,我们将聚焦于可扩展性;一旦有了可扩展性,这些协议的隐私性就相对容易实现,因此我们将在最后回归这个主题。

为什么 ZK-SNARK “会”很难

以开头例子为例:我们有一个数字(我们可以将末尾随着隐秘输入的 “cow” 整体编码为一个整数),我们盘算该数字的 SHA256 哈希,然后重复做 9999999 次,最后我们检查输出的开头。这内里的盘算量稀奇大。

一个“精练(succinct)”证实指的是证实巨细和验证耗时的增久远慢于需验证盘算量的增进。若是我们想要一个“精练”证实,我们就不能要求验证者在每轮哈希中做一些运算(由于那样的话,验证耗时将与盘算量成正比)。相反,验证者必须以某种方式检查整个运算历程,而不必窥视运算历程中的每个部门。

有一种自然的手艺就是随机抽样:让验证者只在 500 个差其余地方检查运算的准确性,若是所有的 500 个检查都通过了,那么以为运算历程的其余部门也也许率没问题?

该流程甚至可以通过使用 Fiat-Shamir 启发式(Fiat-Shamir heuristic)转化为非交互式证实:证实者盘算运算历程的默克尔根,基于默克尔根伪随机地选取 500 个索引,并提供对应的 500 个默克尔分支。焦颔首脑是证实者并不知道将要展现哪些分支,直到他们已经对数据天生了“答应”。若是恶意证实者在领会到需要检查哪些索引后试图改动数据,那么这会改变默克尔根的值,而这将导致一组新随机索引被选出,这将需要再次去改动数据…让恶意证实者陷入无休止的循环中,无法杀青目的。

但不幸的是,简朴地随机抽查运算历程存在一个致命的缺陷:运算历程自己并不结实。若是恶意证实者在盘算历程中的某个位置翻转一个比特,可以导致一个完全差其余效果,而随机抽样验证者险些永远不会发现。

只需一次有意的插入错误,就会导致盘算得出完全错误的效果,而这险些不会被随机检查所捕捉。

若是要提出一个 zk-SNARK 协议,那么许多人会走到上面这步,然后陷入逆境,最终放弃。不但独查看每个盘算片断的情形下,验证者事实若何才气够校验每个盘算片断?事实证实,有一个绝妙的解决方案。

多项式

多项式是一类特殊的代数表达式,具有以下形式:

也就是说,它们是有限个形式为 cxk 的项之和。

多项式有许多有趣的特征。但这里,我们将聚焦于多项式的一个特征:多项式是一个可以包罗无限信息量(多项式显然可视为一个整数列表)的单一数学工具上。面的第四个示例包罗 tau 的 816 位的信息,而且我们能够很容易地想象出一个包罗更多信息量的多项式。

此外,多项式间的单个等式就能够示意无限个数间的方程。例如,思量等式 A(x)+B(x)=C(x)。若是该等式是准确的,那么下面也是准确的:

  • A(0)+B(0)=C(0)

  • A(1)+B(1)=C(1)

  • A(2)+B(2)=C(2)

  • A(3)+B(3)=C(3)

可以类推到每个可能的下标。甚至,你可以组织专程示意一组数字的多项式,这样你就可以一次性地检查众多等式。例如,假设您想检查:

  • 12 + 1 = 13

  • 10 + 8 = 18

  • 15 + 8 = 23

  • 15 + 13 = 28

您可以使用一个名为拉格朗日插值的方式来组织多项式:A(x) 在某些特定下标聚集(例如 (0,1,2,3) 上的输出为 (12,10,15,15)),B(x) 在相同下标上的输出为 (1,8,8,13),云云类推。准确地说,以下是响应的多项式:

用这些多项式校验等式 A(x)+B(x)=C(x) 相当于同时校验上述四个等式。

将多项式与自身举行对照

甚至,你可以用一个简朴的多项式等式来校验相同多项式的大量相邻取值的关系。这稍微更进一步。假设您想校验,对于给定的多项式 F,在整数局限 {0,1…98} 内知足 F(x+2)=F(x)+F(x+1)(因此,若是您还校验F(0)=F(1)=1,那么 F(100) 将是第 100 个斐波拉契数)。

作为多项式,F(x+2)−F(x+1)−F(x) 不会正好为零,由于它在 x={0,1…98} 局限外的取值是不受限的。但我们可以做一些巧妙的处置。一样平常而言,有这样一条定则:若是多项式 P 在某些聚集 S={x1,x2…xn} 上的取值为零,那么可以示意为 P(x)=Z(x)∗H(x) 的形式,其中 Z(x)=(xx1)∗(xx2)∗…∗(xxn),而且 H(x) 也是一个多项式。换句话说,在某个聚集上值为零的任一多项式可以示意为在相同聚集上值为零的最简(最低阶)多项式的(多项式)倍数。

为什么会这样?这实在是多项式长除法的一个巧妙的推论:因式定理(the factor theorem)。我们知道,当用 Z(x) 除 P(x) 时,我们将获得商 Q(x) 和余数 R(x),知足 P(x)=Z(x)∗Q(x)+R(x),其中余数 R(x) 的阶严酷小于 Z(x)。由于我们知道多项式 P 在聚集 S 上的取值为零,这意味着多项式 R 在聚集 S 上的取值也必须为零。因此,我们可以通过多项式插值简朴地皮算 R(x),由于它是一个阶至多为 n−1 的多项式,而我们知道其中的 n 个取值(聚集 S 上的取值为零)。使用上述所有零值举行插值获得零多项式,因此,R(x)=0,H(x)=Q(x)。(译者注,一个有 n 个解的 <=n−1 次多项式必为零多项式)

回到我们的例子上,若是我们有一个编码了斐波那契数的多项式 F(因此,在 x={0,1…98} 上知足 F(x+2)=F(x)+F(x+1),那么我可以通过证实多项式 P(x)= F(x+2)−F(x+1)−F(x) 在该局限的取值为零来向你证实 F 确实知足该条件: H(x)=(F(x+2)−F(x+1)−F(x))/Z(x),其中 Z(x)=(x−0)∗(x−1)∗…∗(x−98).

你可以自行盘算 Z(x)(理想情形下会被提前盘算出来),检查该等式,若是检查通过,那么 F(x) 简直知足条件!

现在,退一步,注意一下我们做了什么。我们将一个步长 100 的盘算(盘算第 100 个斐波那契数)转换为单个多项式等式。固然,证实第 N 个斐波那契数的取值意义不大,尤其是由于斐波那契数具有闭合形式。但你可以使用完全相同的底层手艺,只需一些分外的多项式和更庞大的等式,就可以对随便步长的随便盘算举行编码。

现在,若是存在一种使用多项式校验等式的方式,而且这种方式比检查每个系数快得多…

多项式答应

再一次,事实证实,这样的方式是存在的:多项式答应最好把多项式答应看作一种对多项式举行“哈希”的特殊方式,该哈希拥有分外特征,即你可以通过校验多项式哈希间的等式来校验多项式间的等式。差异多项式答应方案在适用等式类型上有着差其余特点。

下面是一些常见的例子,您可以使用种种多项式答应方案(我们使用com(P)来示意“对多项式 P 的答应”):

  • 相加:给定 com(P)、com(Q) 和 com(R),检查是否知足 P+Q=R

  • 相乘:给定 com(P)、com(Q) 和 com(R),检查是否知足 PQ=R

  • 在某个点上求值:给定 com(P)、wz 和一个弥补证实(或“见证”)Q,验证 P(w)=z

值得注重的是,这些原语可以相互组合。若是支持加法和乘法,那么你可以这样盘算:为了证实 P(w)=z,你可以组织出 Q(x)=

(P(x)−z)/(xw), 然后验证者可以验证:

这行得通是由于若是存在这样一个多项式 Q(x),那么 P(x)−z=Q(x)∗(xw),这意味着P(x)−zw 处即是零(由于 xww 处即是零),因此 P(x) 在 w 处即是 z

若是你能盘算出某点的取值,那么你可以举行种种校验。这是由于有一个数字定明白释:大要上,若是一些包罗了一些多项式的等式在一个随机选择的下标下确立,那么对多项式整体而言等式基本为真。因此,若是我们只有一个证实某点取值的机制,那么我们就可以通过一个交互式游戏举行验证,如我们的方程 P(x+2)−P(x+1)−P(x)=Z(x)∗H(x):

,

联博统计

,

三公大吃计算公式www.eth108.vip)(三公大吃小)是用以太坊区块高度哈希值开奖的棋牌游戏,有别于传统三公开船(三公大吃小)棋牌游戏,三公开船(三公大吃小)绝对公平,结果绝对无法预测。三公开船(三公大吃小)由玩家PK,平台不参与。

,

www.u-healer.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。

,

正如前面提到的,我们可以使用 Fiat-Shamir 启发式使其转化为非交互式:证实者可以令 r=hash(com(P), com(H))(其中 hash 是任一加密哈希函数;它不需要拥有任何特殊属性)并盘算 r。证实者不能通过挑选只“相符”特定 r 的 P 和 H 来举行“诓骗行为”,由于他们在选取 P 和 H 时不知道 r!

快速回首

  • ZK-SNARK很难,由于验证者需要以某种方式检查盘算中的数百万个步骤,而无需直接地检查每个单独的步骤(由于这会十分耗时)。

  • 我们通过将盘算编码为多项式来解决这个问题。

  • 单个多项式可以包罗无限大的信息量,而且单个多项式表达式(例如,P(x+2)−P(x+1)−P(x)=Z(x)∗H(x))可以代表无限个数间的方程。

  • 若是你可以验证多项式等式,那么你同时在隐式地验证所有的数值等式(用任何现实 x 下标替换多项式中的 x)。

  • 我们使用一种特殊类型的多项式“哈希”,称为多项式答应,以允许我们在极短时间内验证多项式等式,纵然背后的多项式规模异常大。

那么,这些神奇的多项式哈希是若何事情的?

现在有三种被普遍使用的主流方案:bulletproofs, Kate and FRI

  • 这里是Dankrad Feist对Kate答应的形貌:https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html

  • 这里是curve25519-dalek团队对bulletproofs的形貌:https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html,而这里是我的图解:https://twitter.com/VitalikButerin/status/1371844878968176647

  • 这里是对FRI的形貌,我写的…:https://vitalik.ca/general/2017/11/22/starks_part_2.html

哇,哇,别主要。试着简朴地解说其中一个,不要把我带到更恐怖的链接上

忠实说,它们没有那么简朴。这就是为什么所有的这些数学理论直到 2015 年左右才真正崛起的缘故。

请?

在我看来,FRI 是最容易明白透的(若是你愿意把椭圆曲线配对 elliptic curve pairings 看作黑盒,Kate 会更容易明白,但配对确实很庞大,以是总体来说我以为 FRI 更简朴)。

以下是 FRI 事情原理的简化版(简朴起见,免去真正协议中的许多技巧和优化)。假设你有一个阶小于n的多项式 P。对 P 的答应是某组预选下标取值的默克尔根(例如,{0,1…8n−1} ,只管这并不是最高效的选取方式)。现在我们需要分外添加一些器械来证实这组取值来自一个阶小于 n 的多项式。(译者注,需要验证多项式阶小于 n 的缘故原由是保证作恶者通过随机抽样概率尽可能低,给定多项式 P,一个基本拟合 P 的另一个多项式 Q,也是能通过随机抽样的,但 Q 的特点是其阶要足够大才气乐成)

我们要求证实者提供 Q(x) 和 R(x) 的 Merkle 根。然后,我们天生一个随机数 r,并要求证实者提供一个“随机线性组合”S(x)=Q(x)+rR(x)。

我们伪随机抽样了一大组下标(像之前一样,使用提供的Merkle根作为随机种子),并要求证实者在这些下标处提供 PQRS 的 Merkle 分支。在每个提供的下标处,我们校验:

若是我们做了足够校验,那么我们可以确信 S(x) 的“预期”值与“提供”值最多(例如,1%)是差其余。

从这里最先,我们简朴地用 S 重复上面的游戏,逐步“降低”我们体贴的多项式的阶,直到多项式的阶低到我们可以直接校验的水平。

和前面的示例一样,这里的“Bob”是一个抽象看法,对密码学家在头脑上论证协议异常有用。事实上,Alice 自己天生了完整证实,为了防止她作弊,我们使用 Fiat-Shamir:我们凭证此前证实中天生的数据的哈希随机选取每个样本的下标或 r 值。

(在该简化协议中)一个对 P 完整的“FRI答应”包罗:

流程中的每步都可能会引入一些“误差”,但若是您举行了足够多的检查,那么总误差将低到你可以证实 P(x) 在至少 80% 的下标处即是一个阶小于 n 的多项式。这足以知足我们用例的需求:若是你想在 zk-SNARK 中作弊,你需要对少数值举行多项式答应,其多项式的取值会在多处差异于真正阶小于 n 的多项式,因此任何对其举行 FRI 答应的实验都市失败。

此外,您仔细检查一下,FRI 答应中工具的总数和巨细是 O(log阶),因此,对于大型多项式,答应现实上比多项式自己小得多。

为了检查这类差异多项式答应间的等式(例如,给定对 ABC 的 FRI 答应,检查 A(x)+B(x)=C(x)),只需简朴地随机选择许多下标,要求验证者提供在每个多项式的这些下标处的 Merkle 分支,并验证等式在每个下标处确立刻可。

上面形貌的是一种效率极低的协议;有许多代数技巧可以将协议效率提高约 100 倍,若是你想要一个切实可行的协议,好比在区块链生意中使用,你需要使用这些技巧。稀奇是,例如,QR 现实上不是需要的,由于若是你异常伶俐地选择取值点,你可以直接从 P 的取值重构出所需 QR 的取值。然则上面的形貌应该足以让你确信多项式答应从原理上是可行的。

有限域

由于数字的“回环”方式,模运算有时被称为“时钟数学”

通过模运算,我们缔造了一个全新的算术系统,它和传统算术一样是自洽的。因此,我们可以讨论该域中的所有同类结构,包罗我们在“通例数学”中讨论的多项式。密码学家喜欢使用模数学(或者,更一样平常的,“有限域”),由于任何模运算效果的巨细都市有界-无论你做什么,值都不会“超出”聚集 {0,1,2…p−1}。纵然盘算有限域中一个一百万次多项式,也不会得出一个聚集以外的值。

将盘算转化为一组多项式等式更具意义的例子?

隐私

但这里有一个问题:我们怎么知道对 P(x) 和 R(x) 的答应不会“泄露”信息(使得能够展现我们试图隐藏的 P(64) 简直切值)?

这里有些好新闻:这些证实是对大量的数据和盘算天生的小证实。因此,一样平常来说,证实往往不够大,只能露出一点点信息。但我们能从“只有一点点”推进到“零”吗?幸运的是,我们可以。

在这里,一个相当通用的技巧是往多项式添加一些“模糊因子”。当我们选定P时,将 Z(x) 的小倍数加到多项式中(即,取随机 E(X),令 P′(x)=P(x)+Z(x)∗E(x))。这并不会影响命题的准确性(事实上,P′ 在“在盘算发生”的下标处的值与 P 相同,因此它仍是有用的转义版本),但它可以在答应中添加足够多的分外“噪声”,使得任何余下信息不能恢复。此外,对于 FRI,主要的是不要对盘算发生局限的随机点举行采样(在本例中为 {0…64} )。(译者注,这样纵然是同样的多项式也会让人猜不到)

我们能再回首一下吗??

  • 最优异的三类多项式答应是 FRI、Kate 和 bulletProof。

  • Kate在看法上是最简朴的,但它依赖于异常庞大的椭圆曲线配对“黑盒”。

  • FRI很酷,由于它只依赖哈希;它的事情原理是将多项式逐渐归约为阶越来越低的多项式,并在每步举行随机抽样检查,使用 Merkle 分支来证实等价性。

  • 为了防止单个值巨细的膨胀,我们不在整数上做算术运算和多项式运算,而是在有限域上做所有事情(通常是对一些素数 p 举行模运算)

  • 多项式答应自然支持隐私珍爱,由于天生的证实已经比多项式小得多了,因此多项式答应只能露出多项式中一点点信息。但我们可以往多项式添加一些随机性,将露出的信息从“一点点”削减到“零”。

哪些问题仍在研究当中?

  • 优化 FRI:已经有许多涉及全心挑选的取值域的优化,“DEEP-FRI”,以及一系列其他让 FRI更高效的技巧。Starkware 及其他人正在研究这块。

  • 将盘算编码为多项式的更佳方式:找出将涉及哈希函数、内存接见和其他特征的庞大盘算编码为多项式等式的最高效方式仍是一个挑战。在这方面已经取得了很大的希望(例如,见 PLOOKUP),但我们仍需更多的希望,稀奇是若是我们想将通用虚拟机执行编码为多项式的话。

  • 增量可验证盘算:若是随着盘算继续能够高效地“扩展”证实,那就太好了。这在“单证实者”情形下很有价值,而且在“多证实者”的情形下也很有价值,稀奇对于差异介入者确立区块的区块链而言。最近一些在这方面的事情,请参见 Halo。

查看更多 环球UG声明:该文看法仅代表作者自己,与本平台无关。转载请注明:以太坊高度(www.326681.com)_Vitalik:多项式答应若何让 zk-SNARK 的实现加倍高效?
发布评论

分享到:

新2查账网址(www.hg108.vip):陈茂波:香港特区政府感谢中证监进一步扩展互联互通安排
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。