比特币:Vitalik:以太坊状态爆炸问题,多项式承诺方案可解决

写在前面:为了应对以太坊的状态爆炸问题,以太坊联合创始人Vitalik提出了新的解决方案,其提议使用多项式承诺方案来替代默克尔树,以此大大减少无状态以太坊客户端的见证数据。

以下为译文:

关于这一研究,这里要感谢很多人提供的帮助,尤其是AZTEC团队向我介绍了复制约束参数、排序参数以及有效的批范围证明方法;DateryKhovratovich和JustinDrake在Kate承诺部分提供的方案,ElibenSasson关于FRI提供的反馈,以及JustinDrake进行的审查工作。这篇文章只是第一次尝试,如果有进一步的重要思考,我确实希望该方案能够被类似但更好的计划所取代。

太烦不看版总结:

我们建议用称为“多项式承诺”的神奇数学来替代默克尔树来累积区块链状态。好处包括:将无状态客户端的见证内容的大小减少到接近于零。这篇文章提出了利用多项式承诺进行状态累积所存在的挑战,并提出了具体的构建方法。

什么是多项式承诺?

多项式承诺是多项式P的一种‘哈希’,其具有可对哈希执行算术检查的属性。

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

如果P(x)+Q(x)=R(x),你可以生成一个证明,证明它和h_P,h_Q,h_R的关系;

如果P(x)*Q(x)=R(x),你可以生成一个证明,证明它和h_P,h_Q,h_R的关系;

如果P(z)=a,你可以针对h_P生产一个证明

你可以将多项式承诺用作vector承诺,类似于默克尔树。多项式承诺的一个主要优点是,由于其数学结构的原因,其生成复杂证明要容易得多。

有哪些流行的多项式承诺方案?

当前有两个领跑者,它们分别是Kate承诺以及基于FRI的承诺。你可能还听说过防弹证明和DARKs算法,这些是替代型多项式承诺方案。而要了解有关多项式承诺的更多信息,YouTube上有相关的内容。

MetisDAO发布新项目ZKM:7月13日消息,以太坊扩容解决方案MetisDAO发布其孵化的新项目ZKM。ZKM将在年底前上线测试网,将现有的OptimisticRollup升级为HybridRollup,实现及时提款(原来OP的提款期为7天)并确保安全性。

ZKM采用MIPS指令集,从CPU级别实现所有虚拟机(VMs)和应用的零知识证明(ZKP)安全性,并支持多种区块链智能合约引擎。此外,ZKM的即插即用特性使开发者无需更改代码库即可应用ZKP,降低采用成本。借助以太坊的大型分散安全基础设施,ZKM可以验证所有区块链和非区块链交易。[2023/7/13 10:53:33]

多项式承诺在以太坊中有哪些容易应用的场景?

我们可以用多项式承诺来替换目前区块数据的默克尔根,并用开放证明替换默克尔分支。这给我们带来了两个很大的优势。首先,数据可用性检查会变得容易,并且不会存在欺诈,因为你可以简单地以随机方式请求开放。非交互式的托管证明也可能变得更容易。

其次,说服多数据片段的轻客户端也变得更加容易,因为你可以制造一个同时涵盖多个索引的有效证明。对于任何集{(x_1,y_1),...,(x_k,y_k。,定义三个多项式:

通过所有这些点的插值多项式I(x);

在x_1,...,x_k等于0的零多项式Z=*...*;

商多项式Q=-I)/Z;

商多项式

Q的存在,意味着

P(x)-I(x)是

Z的倍数,因此

P-I为零,其中

Z(x)为零。这意味着对于所有

i,我们都有

P(x_i)-y_i=0,即

P(x_i)=y_i。验证者可以生成插值多项式和零多项式。证明由对商的承诺,加上随机点

z上的开放证明组成,因此,我们可以对任意多个点拥有一个常数大小的见证内容。

这种技术可以为区块数据的多次访问提供一些好处。然而,其对于一种不同的用例而言,存在的优势就要大得多:证明区块交易账户witness。平均而言,每个区块会访问数百个账户和存储密钥,这导致潜在的无状态客户端的见证内容大小会有0.5MB大小。而多项式承诺多见证,根据方案的不同,可以将区块witness的大小从数万字节减少到几百字节。

灰度CEO:预计将于第三季度末获悉能否将GBTC转换为现货比特币ETF:4月27日消息,Grayscale(灰度)CEO Michael Sonnenshein 在 CoinDesk2023 共识大会上表示,预计在今年第三季度末得知公司能否将价值 175 亿美元的灰度比特币信托(GBTC)转换为现货比特币 ETF。这一转换请求去年曾被 SEC 拒绝。[2023/4/27 14:31:27]

那我们可以使用多项式承诺来存储状态吗?

大体上,我们是可以的。相比将状态存储为默克尔树,我们选择将状态存储为两个多项式S_k(x)和S_v(x),其中S_k,...,S_k表示键,而S_v,..。,S_v表示这些键上的值。

为了证明键值对,...,是状态的一部分,我们将提供索引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)。

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

而这和JustinDrake提出的使用SNARKs/STARKs来压缩witness以及相关的想法有着相似的好处,另外一个好处是,由于证明是累加器密码学原生的,而不是构建在累加器密码学上的证明,因此这消除了一个数量级的开销,并移除了对零知识证明友好哈希函数的需求。

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

为k个密钥生成witness需要的时间是O,其中N是状态的大小。而预计N对应的状态数据会有大约50GB,因此在单个区块中生成这样的证明是不实际的;

2、用k个新值更新S_k(x)和S_v(x)花费的时间也需要O。这在单个区块中是不切实际的,特别是考虑到诸如witness更新和重新排序之类的复杂性。

下面我们将介绍应对这两大问题的解决方案。

高效读取

我们提供了两种解决方案,一种针对Kate承诺而设计,另一种则是针对基于FRI的承诺。不幸的是,这些方案具有不同的优点和缺点,从而会导致不同的属性。

Do Kwon律师拟将护照造假案上诉至最高法院 引渡进程或将拖延:金色财经报道,Terraform Labs创始人Do Kwon在黑山的法律代表Voislav Zetsevich律师在接受采访时表示,对于Do Kwon涉护照造假案,其已对一审判决向高等法院提起上诉,若败诉,还会将此案上诉至最高法院以寻求最终判决,他们将尽可能行使自卫权。该媒体评论称,这意味着实际引渡或需要相当长的时间。律师还提及,如果Do Kwon因护照造假案被判处最高5年徒刑,他可能会被遣返到另一个国家并在那里服刑。[2023/3/29 13:32:19]

1、Kate承诺

首先,请注意,对于N次多项式f,有一种方案可生成N个对应于

O(N*log(N))时间中每个

q_i(x)=(f(x)-f(i))/(X-i)的开放证明。

还请注意,我们可以按以下方式合并witness。考虑这样一个事实,q_i(x)只是一个离开f/的子常数项,通常,已知f/((X-x_1)*...*(X-x_k))是f/,...,f/使用部分分式分解的某种线性组合。只需知道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))的一个子常数项,因此它必然是商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))。

一个可能的挑战是,对于大的状态,一个实际可计算的单一可信设置是不够大的:例如,PLONK设置只能容纳约3.2GB。相反,我们可以有一个由多个Kate承诺组成的状态。

我们对很多承诺作如下单一witness。为证明,首先让。witness是;如果Q是一个多项式,则F实际上在那些位置为零,因此fi在其位置具有期望值。

2、基于FRI的承诺

我们将状态存储在一个二维多项式

F的求值中(每个变量的阶数为

sqrt),并致力于对

4*sqrt(N)by4*sqrt(N)square求值

F。

我们将所有我们关心的值存储在位置(x,x**sqrt(N)),因此它们都具有唯一的x坐标。

为了证明在一组点x_1,...,x_k上的求值,我们构造了一个k次多项式路径,其在x_i处的求值为x_i**sqrt。

然后,我们创建一个多项式

h(t)=F(t,path(t)),其中包含对

(x_i,y_i)的所有期望求值,并且具有

k*)次。

我们在求值域中选择随机的30列c_1...c_k,对于每列查询30个随机行。我们承诺于h,为z_i=h(c_i)提供一个多开口,并对列商(R_i-z_i)/(X-path(c_i))进行FRI随机线性组合,以验证h的声明值是正确的,因此h(t)实际上等于F(t,path(t))。

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

高效写入

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

区块本身,具有“读取见证”(R_k(x),R_v(x))和“写入见证”,W_v),表示要写入状态的值。注意,我们可以设置W_k=R_k,并在运行时计算W_v。

第一个缓存C1=,C1_v)存储最近一天的更新内容;

第二个缓存C2等于前一天的最后一个C1;

满状态S=,S_v)包含时间超过1-2天的值;

我们将使用的方法如下。为了从状态中读取一些键k,我们将依次读取

C1,

C2,

S。如果键位于某

C1_k处,则对应的值

C1_v存储该值,如果键位于

C2_k,则

C2_v存储该值,依此类推,如果键位于

S_k,则

S_v存储该值。如果这些检查都没有返回键,则该值为0。

复制约束参数的简介

复制约束参数,是我们将使用的witness更新证明的关键组成部分;有关复制约束参数如何工作的详细信息,请参见此处。简而言之,该想法是选择一个随机r,并生成一个“累加”多项式ACC,其中ACC=1且ACC=ACC*)。你可以通过开放读取ACC(y)/ACC(x),来读取x....y-1范围内的点累加器。你可以使用这些累加器值,将这些求值与其他求值集进行比较,而无需考虑排列。

你还可以通过设置

ACC(x+1)=ACC(x)*(r+P_1(x)+r2*P_2(x))来证明某些随机

r和

r2的求值元组(即多集

{(P_1(0),P_2(0)),(P_1(1),P_2(1)),...})的等价性。多项式承诺可有效用于证明有关ACC的主张。

为了证明子集,我们可以做相同的事情,除了我们还要提供一个指标多项式ind,证明该ind(x)在整个范围内等于0或1,并设置ACC=ACC**)+)),否则不使用累加器值)。

小结:

我们可以证明a和b之间的P求值,是a和b之间Q求值的置换;

我们可以证明a和b之间的P求值,是a和b之间Q求值置换的子集;

我们可以证明P和Q的求值,是R和S置换,其中P->Q和R->S是相同的置换;

在下面的内容中,除非明确说明,否则我们将偷懒地表述为“P是Q的置换”,意思是“P在0和k之间的求值,是Q在0和k之间对适当k求值的置换”。请注意,下面的内容中,我们还会涉及到每个witness的“大小”,以确定我们接受的任何

C_k中的坐标,而超出范围的

C_k值当然不计算在内。

映射合并参数

为了更新缓存,我们使用了“映射合并参数”。给定两个映射A=,A_v)和B=,B_v),生成合并映射C=,C_v)以便:

C_k中的键被分类;

对于0<=i<size(B),(B_k(i),B_v(i))在C中;

对于0<=i<size(A),仅当A_k(i)不在B的求值集之内时,(A_k(i),A_v(i))在C中;

我们用一系列复制约束参数来实现这一点。首先,我们生成两个辅助多项式

U,

I,它们分别表示

A_k和

B_k的“并集”和“交集”。将

A_k,B_k,C_k,U,I视为集合,我们首先需要展示:

1、A_k?U;

2、B_k?U;

3、I?A_k;

4、I?B_k;

5、A_k+B_k=U+I;

我们预先假设在A_k和B_k中没有重复,这意味着A_k!=A_j对于范围内的i!=j与B_k相同。由于I是A_k和B_k的子集,所以我们已经知道I也没有重复的值。通过使用另一个复制约束参数来证明U和C_k之间的等价关系,证明了U中没有重复项,并证明C_k是已排序且无重复的。我们用一个简单的复制约束参数证明A_k+B_k=U+I声明。

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

关于E的约束表明,E中的所有值都夹在0和65535之间。对

D_i的复制约束,证明

D_i中的所有值都在0到65535之间,这证明了它是一个正确的16进制表示,从而证明了

C_k-C_k实际上是一个正数。

现在,我们需要证明value。我们添加另一个多项式U_v,并验证:

在0...size(B)的(U,U_v)等于在0...size(B)的(B_k,B_v);

在size(B)...size(A)+size(B)的(U,U_v),是在0...size(A)的一个子集;

目标是在

U中,我们先放置来自

B的所有值,然后再放置来自

A的值,并使用相同的置换参数来确保键和值被正确复制。然后我们验证

的一个置换。

使用映射合并参数

我们按照下面的方式使用映射合并参数,假设每天有BLOCKS_PER_DAY个区块。

如果block.number%BLOCKS_PER_DAY!=0,我们验证(C1_k,C1_v)=merge((W_k,W_v),(C1_old_k,C1_old_v));

如果block.number%BLOCKS_PER_DAY==0,我们验证(C1_k,C1_v)=(W_k,W_v)以及(C2_k,C2_v)=(C1_old_k,C1_old_v);

请注意,C2具有一整天的时间,在此期间它保持不变。我们为任何人产生

=merge,)的证明提供奖励;提供此证明后,我们将承诺

更新为新值,并将

重置为空。如果

S在当天没有更新,则我们将

C1->C2传输延迟到更新为止;请注意,该协议确实取决于

S的更新速度是否足够快。如果这不可能发生,那么我们可以通过添加更多层缓存的层次结构来解决这个问题。

从糟糕的FRI中恢复

对于FRI的情况,注意,有可能会出现有人生成的FRI在某些位置无效,但这不足以阻止验证。这不会立即造成安全风险,但可能会阻止下一个更新者生成witness。

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

因此,我们有了一种机制来使用多项式承诺,以此作为一个有效读取和写入witness来存储状态。这使我们能够大幅度减少见证内容大小,同时也可以带来一些好处,比如让我们有能力对数据可用性进行检查,以及实现关于状态的托管证明。

今后的工作

提出FRI证明,要求少于900次查询;

从理论上讲,如果你预先计算并存储拉格朗日基,理论上可以快速更新Kate承诺。这是否可以扩展到快速更新所有witness,以及为键值映射而不是一个vector工作?

郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。

链链资讯

[0:15ms0-2:62ms