Hi Guest

More contents, please log on!

Bitmere.com 区块链前沿 Content
关于这一研究,这里要感谢很多人提供的帮助,尤其是(1)AZTEC团队向我介绍了复制约束( copy constraint)参数、排序参数以及有效的批范围证明方法; (2)Datery Khovratovich和Justin Drake在Kate 承诺部分提供的方案,(3)Eli ben Sasson关于FRI提供的反馈,以及(4)Justin Drake进行的审查工作。这篇文章只是第一次尝试,如果有进一步的重要思考,我确实希望该方案能够被类似但更好的计划所取代。
太烦不看版总结:
我们建议用称为“多项式承诺”(polynomial commitments)的神奇数学来替代默克尔树(Merkle tree)来累积区块链状态。好处包括:将无状态客户端的见证内容(witnesses)的大小减少到接近于零。这篇文章提出了利用多项式承诺进行状态累积所存在的挑战,并提出了具体的构建方法。
什么是多项式承诺(polynomial commitments)?
多项式承诺是多项式P(x)的一种‘哈希’,其具有可对哈希执行算术检查的属性。
例如,在三个多项式P(x),Q(x),R(x)上,给定三个多项式承诺h_P = commit(P(x)), h_Q = commit(Q(x)), h_R = commit(R(x)),然后:
  • 如果P(x) + Q(x) = R(x),你可以生成一个证明(proof),证明它和h_P, h_Q, h_R的关系(在某些构造中,你可以简单地检查h_P + h_Q = h_R);
  • 如果P(x) * Q(x) = R(x),你可以生成一个证明(proof),证明它和h_P, h_Q, h_R的关系;
  • 如果P(z) = a ,你可以针对h_P生产一个证明(称为开放证明opening proof或简称opening)你可以将多项式承诺用作vector承诺,类似于默克尔树(Merkle tree)。多项式承诺的一个主要优点是,由于其数学结构的原因,其生成复杂证明要容易得多(详细解释见下文)。
    有哪些流行的多项式承诺方案?
    当前有两个领跑者,它们分别是Kate承诺(在这篇文章中搜索 “Kate”)以及基于FRI的承诺。你可能还听说过防弹证明(Bulletproofs)和DARKs算法,这些是替代型多项式承诺方案。而要了解有关多项式承诺的更多信息,YouTube上有相关的内容(part 1,part 2,part 3,以及幻灯片)。
    多项式承诺在以太坊中有哪些容易应用的场景?
    我们可以用多项式承诺来替换目前区块数据的默克尔根(例如以太坊2.0的分片区块),并用开放证明替换默克尔分支(Merkle branches)。这给我们带来了两个很大的优势。首先,数据可用性检查会变得容易,并且不会存在欺诈,因为你可以简单地以随机方式(例如一个N次多项式的2N个坐标中的40个)请求开放。非交互式的托管证明也可能变得更容易。
    其次,说服多数据片段的轻客户端也变得更加容易,因为你可以制造一个同时涵盖多个索引的有效证明。对于任何集{(x_1, y_1), ..., (x_k, y_k)},定义三个多项式:
  • 通过所有这些点的插值多项式I(x);
  • 在x_1,...,x_k等于0的零多项式Z(x)=(x-x_1)* ... *(x-x_k);
  • 商多项式Q(x)=(P(x)-I(x))/Z(x);商多项式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的大小从数万字节减少到几百字节。
    那我们可以使用多项式承诺来存储状态吗?
    大体上,我们是可以的。相比将状态存储为默克尔树(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以及相关的想法有着相似的好处,另外一个好处是,由于证明是累加器密码学原生的,而不是构建在累加器密码学上的证明,因此这消除了一个数量级的开销,并移除了对零知识证明友好哈希函数的需求
    但这里存在着两个大问题:
  • 为k个密钥生成witness需要的时间是O(N),其中N是状态的大小。而预计N对应的状态数据会有大约50 GB,因此在单个区块中生成这样的证明是不实际的;
  • 2、用k个新值更新S_k(x)和S_v(x) 花费的时间也需要O(N)。这在单个区块中是不切实际的,特别是考虑到诸如witness更新和重新排序之类的复杂性。下面我们将介绍应对这两大问题的解决方案。
    高效读取(Efficient reading)
    我们提供了两种解决方案,一种针对Kate承诺而设计,另一种则是针对基于FRI的承诺。不幸的是,这些方案具有不同的优点和缺点,从而会导致不同的属性。
    1、Kate承诺首先,请注意,对于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。为证明
    ,首先让 (这是fi和1的线性组合,因此验证者verifier可以实时计算此承诺)。witness是;如果Q是一个多项式,则F实际上在那些位置为零,因此fi在其位置具有期望值。2、基于FRI的承诺我们将状态存储在一个二维多项式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)。
    然后,我们创建一个多项式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因子降低到更低的指数。
    高效写入(Efficient writing)我们通过一系列的承诺,来解决与更新包含整个状态的单个承诺相关的挑战,较大的承诺,其更新频率也就较低:
  • 区块本身,具有“读取见证”(R_k(x), R_v(x))和“写入见证”(W_k(x),W_v(x)),表示要写入状态的值。注意,我们可以设置W_k = R_k,并在运行时计算W_v。
  • 第一个缓存C1 =(C1_k(x),C1_v(x))存储最近一天的更新内容;
  • 第二个缓存C2等于前一天的最后一个C1;
  • 满状态S = (S_k(x),S_v(x))包含时间超过1-2天的值;
    我们将使用的方法如下。为了从状态中读取一些键k,我们将依次读取C1, C2, S 。如果键位于某C1_k(x)处,则对应的值C1_v(x)存储该值,如果键位于C2_k(x),则C2_v(x)存储该值,依此类推,如果键位于S_k(x),则S_v(x)存储该值。如果这些检查都没有返回键,则该值为0。
    复制约束(copy constraint)参数的简介
    复制约束参数,是我们将使用的witness更新证明的关键组成部分;有关复制约束参数如何工作的详细信息,请参见此处。简而言之,该想法是选择一个随机r,并生成一个“累加”多项式ACC(x),其中ACC(0)= 1 且ACC(x + 1)= ACC(x)*(r + P(x))。你可以通过开放读取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(x),证明该ind(x)在整个范围内等于0或1,并设置ACC(x + 1)= ACC(x )*(ind(x)*(r + P(x))+(1-ind(x)))(即,如果指标为1,则在每一步乘以r + P(x),否则不使用累加器值)。
    小结:
  • 我们可以证明a和b之间的P(x)求值,是a和b(或某些不同的c和d)之间Q(x)求值的置换;
  • 我们可以证明a和b之间的P(x)求值,是a和b(或一些不同的c和d)之间Q(x)求值置换的子集;
  • 我们可以证明P(x)和Q(x)的求值,是R(x)和S(x)置换,其中P-> Q和R-> S是相同的置换;在下面的内容中,除非明确说明,否则我们将偷懒地表述为“P是Q的置换”,意思是“P在0和k之间的求值,是Q在0和k之间对适当k求值的置换”。请注意,下面的内容中,我们还会涉及到每个witness的“大小”,以确定我们接受的任何C_k中的坐标,而超出范围的C_k(x)值当然不计算在内。
    映射合并参数(Map merging argument)
    为了更新缓存,我们使用了“映射合并参数”。给定两个映射A=(A_k(x),A_v(x))和B=(B_k(x),B_v(x)),生成合并映射C=(C_k(x),C_v(x))以便:
  • C_k中的键被分类;
  • 对于0
  • 对于0 我们用一系列复制约束参数来实现这一点。首先,我们生成两个辅助多项式U(x),I(x),它们分别表示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(i)!= A_j(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(x + 1)> 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(x+1) - E(x) = {0, 1} 限制(对E的2次约束)。我们还检查了E(0)= 0以及E(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)实际上是一个正数。
    现在,我们需要证明value(值)。我们添加另一个多项式U_v(x),并验证:
  • 在0...size(B)的(U, U_v)等于在0...size(B)的 (B_k, B_v);
  • 在size(B) ... size(A)+size(B) 的(U, U_v) ,是(A_k,A_v)在0...size(A)的一个子集;目标是在U中,我们先放置来自B的所有值,然后再放置来自A的值,并使用相同的置换参数来确保键(key)和值(value)被正确复制。然后我们验证(C_k,C_v)是(U,U v)的一个置换。
    使用映射合并参数
    我们按照下面的方式使用映射合并参数,假设每天有BLOCKS_PER_DAY个区块。
  • 如果block.number % BLOCKS_PER_DAY != 0,我们验证(C1_k, C1_v) = merge((W_k, W_v), (C1_old_k, C1_old_v))(将区块合并到C1);
  • 如果block.number % BLOCKS_PER_DAY == 0,我们验证(C1_k, C1_v) = (W_k, W_v) 以及(C2_k, C2_v) = (C1_old_k, C1_old_v) (也就是说,我们“清除” C1并将其内容移入C2);请注意,C2具有一整天的时间,在此期间它保持不变。我们为任何人产生(S_k,S_v)= merge((S_old_k,S_old_v),(C2_k,C2_v))的证明提供奖励;提供此证明后,我们将承诺(S_k,S_v)更新为新值,并将(C2_k,C2_v)重置为空。如果S在当天没有更新,则我们将C1-> C2传输延迟到更新为止;请注意,该协议确实取决于S的更新速度是否足够快。如果这不可能发生,那么我们可以通过添加更多层缓存的层次结构来解决这个问题。
    从糟糕的FRI中恢复
    对于FRI的情况,注意,有可能会出现有人生成的FRI在某些位置无效,但这不足以阻止验证。这不会立即造成安全风险,但可能会阻止下一个更新者生成witness。
    我们通过以下几种方法来解决这个问题。首先,注意到某些FRI生成错误的人,可提供自己的FRI。如果通过相同的检查,它将被添加到可构建下一次更新的有效FRI列表中。然后,我们可以使用交互式计算游戏来检测和惩罚不良FRI的创建者。其次,他们可提供自己的FRI以及STARK来证明其有效,从而立即罚没了无效FRI的创建者。通过FRI生成STARK是非常昂贵的,尤其是在较大规模时,但这样做是值得的,因为这可以赚取很大一部分无效提议者的保证金奖励。
    因此,我们有了一种机制来使用多项式承诺,以此作为一个有效读取和写入witness来存储状态。这使我们能够大幅度减少见证内容(witness)大小,同时也可以带来一些好处,比如让我们有能力对数据可用性进行检查,以及实现关于状态的托管证明
  • BitMere.com is Information release platform,just provides information storage space services.
    The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
    You have to log in before you can reply Login | 立即注册

    Points Rules

    Write the first review

    万象争辉1 初中生
    • Follow

      0

    • Following

      0

    • Articles

      21

    Promoted