快捷搜索:

Vitalik:ETH状况爆炸问题,多项式承诺策略可解决

写在前面:为了应付ETH的状况爆炸问题,ETH联合开创者Vitalik提出了新的解决方法,其建议用多项式承诺(polynomial commitments)策略来替代默克尔树(Merkle tree),以此大大降低无状况ETH推广客户端的见证数据(witnesses)。

(图:ETH联合开创者Vitalik Buterin)

(提示:文章有不少公式,译文仅供参考,以原文为准)

用映射合并参数

大家根据下面的方法用映射合并参数,假设天天有BLOCKS_PER_DAY个区块。

请注意,C2具备一整天的时间,在此期间它维持不变。大家为其他人产生(S_k,S_)= merge((S_old_k,S_old_),(C2_k,C2_))的证明提供奖励;提供此证明后,大家将承诺(S_k,S_)更新为新值,并将(C2_k,C2_)重置为空。假如S在当天没更新,则大家将C1-gt; C2传输延迟到更新为止;请注意,该协议确实取决于S的更新速度是不是足够快。假如这不可能发生,那样大家可以通过添加更多层缓存的层次结构来解决这个问题。

5、A_k + B_k = U + I

大家预先假设在A_kB_k中没重复,这意味着A_k(i)!= A_j(j)对于范围内的i!= jB_k相同(由于在之前用此算法时已对此进行了验证)。因为IA_kB_k的子集,所以大家已经知晓I也没重复的值。通过用另一个复制约束参数来证明UC_k之间的等价关系,证明了U中没重复项,并证明C_k是已排序且无重复的。大家用一个容易的复制约束参数证明A_k + B_k = U + I声明。

为了证明C_k已排序且没重复,大家证明C_k(x + 1)gt; C_k(x)的范围为0 ... size(C_k)。大家通过生成多项式D_1(x),...,D_16(x),并证明C(x + 1)-C(x)= 1 + D_1(x)+ 2 ** 16 * D_2(x)+ 2 ** 32 * D_3(x)+...来做到这一点。本质上,D_1(z),...,D_16(z)将差异存储在基2**16中。然后,大家生成一个多项式E(x),其满足所有D_1,...,D_16的复制约束与f(x)= x,并且满足 E - E = {0, 1} 限制(对E的2次约束)。大家还检查了E(0)= 0E(size(C_k)* 16 + 65536)= 65535

关于E的约束表明,E中的所有值都夹在0和65535(包括0和65535)之间。对D_i的复制约束,证明D_i(x)中的所有值都在0到65535(含)之间,这证明了它是一个正确的16进制表示,从而证明了C_k(x+1)-C_k(x)事实上是一个正数。

目前,大家需要证明alue(值)。大家添加另一个多项式U_(x),并验证:

目的是在U中,大家先放置来自B的所有值,然后再放置来自A的值,并用相同的置换参数来确保键(key)和值(alue)被正确复制。然后大家验证(C_k,C_)(U,U )的一个置换。

3、I ⊆ A_k

太烦不看版概要:

大家建议用称为“多项式承诺”(polynomial commitments)的神奇数学来替代默克尔树(Merkle tree)来累积区块链状况。好处包括:将无状况推广客户端的见证内容(witnesses)的大小降低到接近于零。这篇文章提出了借助多项式承诺进行状况累积所存在的挑战,并提出了具体的构建办法。

啥是多项式承诺(polynomial commitments)?

多项式承诺是多项式P(x)的一种‘哈希’,其具备可对哈希实行算术检查的属性。

比如,在三个多项式P(x),Q(x),R(x)上,给定三个多项式承诺h_P = commit), h_Q = commit), h_R = commit),然后:

你可以将多项式承诺用作ector承诺,像默克尔树(Merkle tree)。多项式承诺的一个主要优点是,因为其数学结构是什么原因,其生成复杂证明要容易得多(详细讲解见下文)。

有什么时尚的多项式承诺策略?

目前有两个领头羊,它们分别是Kate承诺(在这篇文章中搜索 “Kate”)与基于FRI的承诺。你可能还听说过防弹证明(Bulletproofs)和DARKs算法,这部分是替代多项式承诺策略。而要知道有关多项式承诺的更多信息,YouTube上有有关的内容(part 1,part 2,part 3,与幻灯片)。

多项式承诺在ETH中有什么容易应用的场景?

大家可以用多项式承诺来替换现在区块数据的默克尔根(比如ETH2.0的分片区块),并用开放证明替换默克尔分支(Merkle branches)。这给大家带来了两个非常大的优势。第一,数据可用性检查会变得容易,并且不会存在欺诈,由于你可以容易地以随机方法(比如一个N次多项式的2N个坐标中的40个)请求开放。非交互式的推广托管证明也会变得更容易。

第二,说服多数据片段的轻推广客户端也变得愈加容易,由于你可以制造一个同时涵盖多个索引的有效证明。对于任何集{, ..., },概念三个多项式:

商多项式Q(x)的存在,意味着P - IZ(x)的倍数,因此P(x)-I(x)为零,其中Z 为零。这意味着对于所有i,大家都有P - y_i = 0,即P = y_i。验证者(erifier)可以生成插值多项式和零多项式。证明(proof)由对商的承诺,加上随机点z上的开放证明组成,因此,大家可以对任意多个点拥有一个常数大小的见证内容(witness)。

这种技术可以为区块数据的多次访问提供一些好处。然而,其对于一种不一样的用例而言,存在的优势就要大得多:证明区块买卖竞价推广账户witness。平均而言,每一个区块会访问数百个竞价推广账户和存储密钥,这致使潜在的无状况推广客户端的见证内容大小会有0.5 MB大小。而多项式承诺多见证(multi-witness),依据策略的不同,可以将区块witness的大小从数万字节降低到几百字节。

那大家可以用多项式承诺来存储状况吗?

大体上,大家是可以的。相比将状况存储为默克尔树(Merkle tree),大家选择将状况存储为两个多项式S_k S_ ,其中S_k(1),...,S_k(N)表示键(key),而S_(1),.. 。,S_(N)表示这部分键(key)上的值(假如值大于字段大小,则至少表示这部分值的哈希值)。

为了证明键值对(k_1,_1),...,(k_k,_k)是状况的一部分,大家将提供索引 i_1, ..., i_k 并(用上面提到的插值技术)显示与索引匹配的键和值,即k_1 = S_k, ..., k_k = S_k _1 = S_, ..., _k = S_

为了证明某些键(key)的非成员性,可以尝试架构一个奇特的证明,证明键(key)不在S_k(1),…,S_k(N)中。相反,大家仅需对键(key)进行排序,以便证明非成员身份就足以证明两个相邻key的成员身份,一个小于目的key,一个则大于目的key。

而这和Justin Drake提出的用SNARKs/STARKs来压缩witness与有关的想法有着一样的好处,另外一个好处是,因为证明是累加器密码学原生的,而不是构建在累加器密码学上的证明,因此这消除去一个数目级的开销,并移除去对零常识证明友好哈希函数的需要。

1、A_k ⊆ U

从糟糕的FRI中恢复

对于FRI的状况,注意,大概会出现有生活成的FRI在某些地方无效,但这不足以阻止验证。这不会立即导致安全风险,但可能会阻止下一个更新者生成witness。

大家通过以下几种办法来解决这个问题。第一,注意到某些FRI生成错误的人,可提供我们的FRI。假如通过相同的检查,它将被添加到可构建下一次更新的有效FRI列表中。然后,大家可以用交互式计算游戏来测试和惩罚不好的FRI的创建者。第二,他们可提供我们的FRI与STARK来证明其有效,从而立即罚没了无效FRI的创建者。通过FRI生成STARK是很昂贵的,特别是在较大规模时,但如此做是值得的,由于这可以赚取非常大一部分无效建议者的保证金奖励。

因此,大家有了一种机制来用多项式承诺,以此作为一个有效读取和写入witness来存储状况。这使大家可以大幅度降低见证内容(witness)大小,同时也可以带来一些好处,譬如让大家有能力对数据可用性进行检查,与达成关于状况的推广托管证明。

但这里存在着两个大问题:

下面大家将介绍应付这两大问题的解决方法。

高效读取(Efficient reapng)

大家提供了两种解决方法,一种针对Kate承诺而设计,另一种则是针对基于FRI的承诺。不幸的是,这部分策略具备不一样的优缺点,从而会致使不一样的属性。

第一,请注意,对于N次多项式f,有一种策略可生成N个对应于O)时间中每一个q_i = - f) / 的开放证明。

还请注意,大家可以按以下方法合并witness。考虑如此一个事实,q_i只不过一个离开f(x)/(X-i)的子常数(sub-constant)项,一般,已知f/ * ... * )f /(X-x_1),...,f /(X-x_k)用部分分式分解( partial fraction decomposition)的某种线性组合。仅需知晓x坐标就可以确定具体的线性组合:仅需提出一个线性组合c_1 * * ... * + c_2 * * * ... * + ... + c_k * * ... * ,其中没有很数项,这是k个未知数中的k方程组。

给定如此的线性组合,大家得到的东西只是离开f/ * ... * )的一个子常数项(由于所有原始误差都是子常数的,所以线性错误的组合势必是sub-constant),因此它势必是商 f // * ... * ),其等于期望值 - I) / * ... * )

一个可能的挑战是,对于大的状况,一个实质可计算的单一可信设置(比如,100多个独立参与者,因此只须其中任何一个是诚实的,策略就是安全的)是不够大的:比如,PLONK设置只能容纳约3.2 GB。相反,大家可以有一个由多个Kate承诺组成的状况。

大家对不少承诺作如下单一witness。为证明,第一让(这是fi和1的线性组合,因此验证者erifier可以实时计算此承诺)。witness是;假如Q是一个多项式,则F事实上在那些地方为零,因此fi在其地方具备期望值。

大家将状况存储在一个二维多项式F(x,y)的求值中(每一个变量的阶数为sqrt(N)),并致力于对4*sqrt by 4*sqrt square求值F

大家将所有大家关心的值存储在地方 ),因此它们都具备唯一的x坐标。(请注意,在不少状况下,这部分地方会超出大家承诺求值的4*sqrt by 4*sqrt square,而这不重要。)

为了证明在一组点x_1, ..., x_k上的求值,大家架构了一个k次多项式路径(x),其在x_i处的求值为x_i ** sqrt(N)

然后,大家创建一个多项式h = F),其中包含对的所有期望求值,并且具备k*(1+sqrt(N))次。

大家在求值域中选择随机的30列c_1 ... c_k,对于每列查看30个随机行。大家承诺于h(用FRI证明它事实上是一个多项式),为z_i = h提供一个多开口(multi-opening),并对列商 / )进行FRI随机线性组合,以验证h(c_i)的声明值是正确的,因此h 事实上等于F)

用二维多项式是什么原因,这确保了大家不必对所有F进行任何计算;相反,大家仅需对大家选择的随机30行F进行计算(即30*sqrt(N)),加上阶为 p * + 1)h,创建FRI进行的计算大约为p * sqrt 。可以将此技术扩展到二维以上的多项式,以将sqrt因子减少到更低的指数。

大家通过一系列的承诺,来解决与更新包含整个状况的单个承诺有关的挑战,较大的承诺,其更新频率也就较低:

大家将用的办法如下。为了从状况中读取一些键k,大家将依次读取C1, C2, S 。假如键坐落于某C1_k(x)处,则对应的值C1_(x)存储该值,假如键坐落于C2_k(x),则C2_(x)存储该值,依此类推,假如键坐落于S_k(x),则S_(x)存储该值。假如这部分检查都没返回键,则该值为0。

复制约束(copy constraint)参数的简介

复制约束参数,是大家将用的witness更新证明的重要组成部分;有关复制约束参数怎么样工作的详细情况,请参见此处。简而言之,该想法是选择一个随机r,并生成一个“累加”多项式ACC(x),其中ACC(0)= 1 ACC(x + 1)= ACC(x)*(r + P(x))。你可以通过开放读取ACC / ACC,来读取x .... y-1范围内的点累加器。你可以用这部分累加器值,将这部分求值与其他求值集(作为多集)进行比较,而不需要考虑排列。

你还可以通过设置ACC = ACC * + r2 * P_2) 来证明某些随机rr2的求值元组(即多集{, P_2), , P_2), ...})的等价性。多项式承诺可有功用于证明有关ACC的倡导。

为了证明子集,大家可以做相同的事情,除去大家还要提供一个指标多项式ind(x),证明该ind在整个范围内等于0或1,并设置ACC(x + 1)= ACC(x )*(ind(x)*(r + P(x))+(1-ind(x)))(即,假如指标为1,则在每一步乘以r + P(x),不然不用累加器值)。

2、B_k ⊆ U

以下为译文:

关于这一研究,这里要感谢大多数人提供的帮忙,特别是(1)AZTEC团队向我介绍了复制约束( copy constraint)参数、排序参数与有效的批范围证明办法; (2)Datery Khoratoich和Justin Drake在Kate 承诺部分提供的策略,(3)Eli ben Sasson关于FRI提供的反馈,与(4)Justin Drake进行的审查工作。这篇文章只不过首次尝试,假如有进一步的要紧考虑,我确实期望该策略可以被类似但更好的计划所取代。

小结:

在下面的内容中,除非明确说明,不然大家将偷懒地表述为“P是Q的置换”,意思是“P在0和k之间的求值,是Q在0和k之间对适合k求值的置换”请注意,下面的内容中,大家还会涉及到每一个witness的“大小”,以确定大家同意的任何C_k中的坐标,而超出范围的C_k(x)值当然不计算在内。

映射合并参数(Map merging argument)

为了更新缓存,大家用了“映射合并参数”给定两个映射A=(A_k(x),A_(x))B=(B_k(x),B_(x)),生成合并映射C=(C_k(x),C_(x))以便:

大家用一系列复制约束参数来达成这一点。第一,大家生成两个辅助多项式U(x)I(x),它们分别表示A_kB_k的“并集”和“交集”将A_k,B_k,C_k,U,I视为集合,大家第一需要展示:

4、I ⊆ B_k

以后的工作

  1. 提出FRI证明,需要少于900次查看(更正式地讲,安全参数小于平方);
  2. 从理论上讲,假如你预先计算并存储拉格朗日基(Lagrange basis),理论上可以迅速更新 Kate承诺。这能否扩展到(i)迅速更新所有witness,与(2)为键值映射而不是一个ector工作?

您可能还会对下面的文章感兴趣: