栏目分类
官方正规赢钱手机游戏网站-首页
资讯中心
企业热门
服务与支持
解决方案
客户
项目委托
Vitalik:以太坊现象爆炸问题,多项式应允有计算可惩办 | BTC
发布日期:2022-07-08 12:37    点击次数:75

写在前边:为了应答以太坊的现象爆炸问题,以太坊荟萃首创人Vitalik提议了新的惩办有计算,其提议使用多项式应允(polynomial commitments)有计算来替代默克尔树(Merkle tree),以此大大减少无现象以太坊客户端的见证数据(witnesses)。\r\n

Vitalik:以太坊现象爆炸问题,多项式应允有计算可惩办

\r\n

(图:以太坊荟萃首创人Vitalik Buterin)

\r\n

(教导:著述有许多公式,译文仅供参考,以原文为准)

\r\n以下为译文:

对于这一扣问,这里要感谢许多人提供的匡助,尤其是(1)AZTEC团队向我先容了复制管理( copy constraint)参数、排序参数以及灵验的批边界讲明程序; (2)Datery Khovratovich和Justin Drake在Kate 应允部分提供的有计算,(3)Eli ben Sasson对于FRI提供的响应,以及(4)Justin Drake进行的审查职责。这篇著述仅仅第一次尝试,如若有进一步的紧迫思考,我如实但愿该有计算或者被雷同但更好的诡计所取代。

太烦不看版回想:

咱们建议用称为 多项式应允 (polynomial commitments)的神奇数学来替代默克尔树(Merkle tree)来积贮区块链现象。公正包括:将无现象客户端的见证内容(witnesses)的大小减少到接近于零。这篇著述提议了应用多项式应允进奇迹态积贮所存在的挑战,并提议了具体的构建程序。

 \r\n什么是多项式应允(polynomial commitments)?\r\n 

多项式应允是多项式P(x)的一种‘哈希’,其具有可对哈希引申算术搜检的属性。

举例,在三个多项式P(x),Q(x),R(x)上,给定三个多项式应允h_P = commit(P(x)), h_Q = commit(Q(x)), h_R = commit(R(x)),然后:\r\n\r\n\t如若P(x) + Q(x) = R(x),你不错生成一个讲明(proof),讲明它和h_P, h_Q, h_R的关系(在某些构造中,你不错简便地搜检h_P + h_Q = h_R);\r\n\t如若P(x) * Q(x) = R(x),你不错生成一个讲明(proof),讲明它和h_P, h_Q, h_R的关系;\r\n\t如若P(z) = a ,你不错针对h_P坐蓐一个讲明(称为灵通讲明opening proof或简称opening)\r\n\r\n你不错将多项式应允用作vector应允,雷同于默克尔树(Merkle tree)。多项式应允的一个主要优点是,由于其数学结构的原因,其生成复杂讲明要容易得多(详确解释见下文)。

 \r\n有哪些流行的多项式应允有计算?\r\n 

现时有两个领跑者,它们区别是Kate应允(在这篇著述中搜索 Kate )以及基于FRI的应允。你可能还外传过防弹讲明(Bulletproofs)和DARKs算法,这些是替代型多项式应允有计算。而要了解相关多项式应允的更多信息,YouTube上有相关的内容(part 1,part 2,part 3,以及幻灯片)。

 \r\n多项式应允在以太坊中有哪些容易应用的场景?\r\n 

咱们不错用多项式应允来替换现在区块数据的默克尔根(举例以太坊2.0的分片区块),并用灵通讲明替换默克尔分支(Merkle branches)。这给咱们带来了两个很大的上风。最初,数据可用性搜检会变得容易,况且不会存在诈骗,因为你不错简便地以立时花式(举例一个N次多项式的2N个坐标中的40个)申请灵通。非交互式的托管讲明也可能变得更容易。

其次,劝服多量据片断的轻客户端也变得愈加容易,因为你不错制造一个同期涵盖多个索引的灵考讲明。对于任何集{(x_1, y_1), ..., (x_k, y_k)},界说三个多项式:\r\n\r\n\t通过悉数这些点的插值多项式I(x);\r\n\t在x_1,...,x_k等于0的零多项式Z(x)=(x-x_1)* ... *(x-x_k);\r\n\t商多项式Q(x)=(P(x)-I(x))/Z(x);\r\n\r\n商多项式Q(x)的存在,意味着P(x) - I(x)是Z(x)的倍数,因此P(x)-I(x)为零,其中Z(x) 为零。这意味着对于悉数i,咱们都有P(x_i) - y_i = 0,即P(x_i) = y_i。考证者(verifier)不错生成插值多项式和零多项式。讲明(proof)由对商的应允,加上立时点z上的灵通讲明构成,因此,咱们不错对淘气多个点领有一个常数大小的见证内容(witness)。

这种时间不错为区块数据的屡次造访提供一些公正。可是,其对于一种不同的用例而言,存在的上风就要大得多:讲明区块交游账户witness。平均而言,每个区块会造访数百个账户和存储密钥,这导致潜在的无现象客户端的见证内容大小会有0.5 MB大小。而多项式应允多见证(multi-witness),把柄有计算的不同,不错将区块witness的大小从数万字节减少到几百字节。

 \r\n那咱们不错使用多项式应允来存储现象吗?\r\n 

大体上,咱们是不错的。比拟将现象存储为默克尔树(Merkle tree),咱们遴荐将现象存储为两个多项式S_k(x) 和S_v(x) ,其中S_k(1),...,S_k(N)示意键(key),而S_v(1),.. 。,S_v(N)示意这些键(key)上的值(如若值大于字段大小,则至少示意这些值的哈希值)。

为了讲明键值对(k_1,v_1),...,(k_k,v_k)是现象的一部分,咱们将提供索引 i_1, ..., i_k 并(使用上头提到的插值时间)披露与索引匹配的键和值,即k_1 = S_k(i_1), ..., k_k = S_k(i_k) 和 v_1 = S_v(i_1), ..., v_k = S_v(i_k)。

为了讲明某些键(key)的非成员性,不错尝试构造一个奇特的讲明,讲明键(key)不在S_k(1),…,S_k(N)中。违抗,咱们只需对键(key)进行排序,以便讲明非成员身份就足以讲明两个相邻key的成员身份,一个小于主义key,一个则大于主义key。

而这和Justin Drake提议的使用SNARKs/STARKs来压缩witness以及相关的办法有着雷同的公正,另外一个公正是,由于讲明是累加器密码学原生的,而不是构建在累加器密码学上的讲明,因此这排斥了一个数目级的支出,并移除了对零常识讲明友好哈希函数的需求。

但这里存在着两个大问题:\r\n\r\n\t为k个密钥生成witness需要的时辰是O(N),其中N是现象的大小。而展望N对应的现象数据会有约莫50 GB,因此在单个区块中生成这么的讲明是子虚际的;\r\n\t2、用k个新值更新S_k(x)和S_v(x) 消费的时辰也需要O(N)。这在单个区块中是不切本色的,极端是斟酌到诸如witness更新和再行排序之类的复杂性。\r\n\r\n底下咱们将先容应答这两大问题的惩办有计算。

 \r\n高效读取(Efficient reading)\r\n 

咱们提供了两种惩办有计算,一种针对Kate应允而联想,另一种则是针对基于FRI的应允。苦难的是,这些有计算具有不同的优点和污点,从而会导致不同的属性。\r\n1、Kate应允\r\n最初,请肃肃,对于N次多项式f,有一种有计算可生成N个对应于O(N * log(N))时辰中每个q_i(x) = (f(x) - f(i)) / (X - i)的灵通讲明。

还请肃肃,咱们不错按以下花式团结witness。斟酌这么一个事实,q_i(x)仅仅一个离开f(x)/(X-i)的子常数(sub-constant)项,常常,已知f/((X - x_1) * ... * (X - x_k))是f /(X-x_1),...,f /(X-x_k)使用部分分式瓦解( partial fraction decomposition)的某种线性组合。只需表示x坐标就不错深信具体的线性组合:只需提议一个线性组合c_1 * (x - x_2) * ... * (x - x_k) + c_2 * (x - x_1) * (x - x_3) * ... * (x - x_k) + ... + c_k * (x - x_1) * ... * (x - x_{k-1}),其中不存在相等数项,这是k个未知数中的k方程组。

给定这么的线性组合,咱们获取的东西仅是离开f/((x - x_1) * ... * (x - x_k))的一个子常数项(因为悉数原始症结都是子常数的,是以线性异常的组合势必是sub-constant),因此它势必是商 f(x) // ((x - x_1) * ... * (x - x_k)),其等于盼愿值(f(x) - I(x_1 ... x_k, y_1 ... y_k)) / ((x - x_1) * ... * (x - x_k))。

一个可能的挑战是,对于大的现象,一个本色可计较的单一真正建筑(举例,100多个寂然参与者,因此唯有其中任何一个是本分的,有计算等于安全的)是不够大的:举例,PLONK建筑只可容纳约3.2 GB。违抗,咱们不错有一个由多个Kate应允构成的现象。

咱们对许多应允作如下单一witness。为讲明Vitalik:以太坊现象爆炸问题,可用多项式应允有计算惩办,最初让\r\nVitalik:以太坊现象爆炸问题,可用多项式应允有计算惩办(这是fi和1的线性组合,因此考证者verifier不错及时计较此应允)。witness是p7;如若Q是一个多项式,则F本色上在那些位置为零,因此fi在其位置具有盼愿值。\r\n2、基于FRI的应允\r\n咱们将现象存储在一个二维多项式F(x,y)的求值中(每个变量的阶数为sqrt(N)),并竭力于于于对4*sqrt(N) by 4*sqrt(N) square求值F。

咱们将悉数咱们热心的值存储在位置 (x, x**sqrt(N)),因此它们都具有独一的x坐标。(请肃肃,在很厚情况下,这些位置会超出咱们应允求值的4*sqrt(N) by 4*sqrt(N) square,而这不关深广。)

为了讲明在一组点x_1, ..., x_k上的求值,咱们构造了一个k次多项式旅途(x),其在x_i处的求值为x_i ** sqrt(N)。\r\n

Vitalik:以太坊现象爆炸问题,可用多项式应允有计算惩办

\r\n然后,咱们创建一个多项式h(t) = F(t, path(t)),其中包含对(x_i, y_i)的悉数盼愿求值,况且具有k*(1+sqrt(N))次。

咱们在求值域中遴荐立时的30列c_1 ... c_k,对于每列查询30个立时行。咱们应允于h(使用FRI讲明它本色上是一个多项式),为z_i = h(c_i)提供一个多启齿(multi-opening),并对列商 (R_i - z_i) / (X - path(c_i))进行FRI立时线性组合,以考证h(c_i)的声明值是正确的,因此h(t) 本色上等于F(t, path(t))。

使用二维多项式的原因是,这确保了咱们无须对悉数F进行任何计较;违抗,咱们只需要对咱们遴荐的立时30行F进行计较(即30*sqrt(N)),加上阶为 p * (sqrt(N) + 1)的h,创建FRI进行的计较约莫为p * sqrt(N) 。不错将此时间推广到二维以上的多项式,以将sqrt因子缩短到更低的指数。\r\n高效写入(Efficient writing)\r\n咱们通过一系列的应允,来惩办与更新包含