Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文
关于这一研究,这里要感谢很多人提供的帮助,尤其是(1)AZTEC团队向我介绍了复制约束( copy constraint)参数、排序参数以及有效的批范围证明方法; (2)Datery Khovratovich和Justin Drake在Kate 承诺部分提供的方案,(3)Eli ben Sasson关于FRI提供的反馈,以及(4)Justin Drake进行的审查工作。这篇文章只是第一次尝试,如果有进一步的重要思考,我确实希望该方案能够被类似但更好的计划所取代。
" M9 [9 N$ w9 e% |# K9 O太烦不看版总结:( E  D3 w" ~9 T( Q. w( F  H
我们建议用称为“多项式承诺”(polynomial commitments)的神奇数学来替代默克尔树(Merkle tree)来累积区块链状态。好处包括:将无状态客户端的见证内容(witnesses)的大小减少到接近于零。这篇文章提出了利用多项式承诺进行状态累积所存在的挑战,并提出了具体的构建方法。
3 r: [8 E- f. ~0 u什么是多项式承诺(polynomial commitments)? - C; z3 l/ d* P# Q& p
多项式承诺是多项式P(x)的一种‘哈希’,其具有可对哈希执行算术检查的属性。/ b" {- t/ I0 N* h
例如,在三个多项式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)。多项式承诺的一个主要优点是,由于其数学结构的原因,其生成复杂证明要容易得多(详细解释见下文)。
    ! V. U# ]3 V' b4 s0 y& g. C  F8 i有哪些流行的多项式承诺方案?
    ( h8 u% P6 t: I. V当前有两个领跑者,它们分别是Kate承诺(在这篇文章中搜索 “Kate”)以及基于FRI的承诺。你可能还听说过防弹证明(Bulletproofs)和DARKs算法,这些是替代型多项式承诺方案。而要了解有关多项式承诺的更多信息,YouTube上有相关的内容(part 1,part 2,part 3,以及幻灯片)。; s- S% \* n$ z( u
    多项式承诺在以太坊中有哪些容易应用的场景? 1 _7 o* p( a" z2 z/ {4 f8 W" N6 _
    我们可以用多项式承诺来替换目前区块数据的默克尔根(例如以太坊2.0的分片区块),并用开放证明替换默克尔分支(Merkle branches)。这给我们带来了两个很大的优势。首先,数据可用性检查会变得容易,并且不会存在欺诈,因为你可以简单地以随机方式(例如一个N次多项式的2N个坐标中的40个)请求开放。非交互式的托管证明也可能变得更容易。
    # D3 o. N: c: Q6 y+ E' w其次,说服多数据片段的轻客户端也变得更加容易,因为你可以制造一个同时涵盖多个索引的有效证明。对于任何集{(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)。
    5 A6 h# D  w" H' w0 i这种技术可以为区块数据的多次访问提供一些好处。然而,其对于一种不同的用例而言,存在的优势就要大得多:证明区块交易账户witness。平均而言,每个区块会访问数百个账户和存储密钥,这导致潜在的无状态客户端的见证内容大小会有0.5 MB大小。而多项式承诺多见证(multi-witness),根据方案的不同,可以将区块witness的大小从数万字节减少到几百字节。# Q+ Y) Y; x0 Y5 R( d) T& n
    那我们可以使用多项式承诺来存储状态吗?
    9 Z$ ]/ s' `. _大体上,我们是可以的。相比将状态存储为默克尔树(Merkle tree),我们选择将状态存储为两个多项式S_k(x) 和S_v(x) ,其中S_k(1),...,S_k(N)表示键(key),而S_v(1),.. 。,S_v(N)表示这些键(key)上的值(如果值大于字段大小,则至少表示这些值的哈希值)。
    ; ^4 ^1 p* j" C; @" E为了证明键值对(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)。, M! y% f5 S) t  K3 t3 M4 p; N
    为了证明某些键(key)的非成员性,可以尝试构造一个奇特的证明,证明键(key)不在S_k(1),…,S_k(N)中。相反,我们只需对键(key)进行排序,以便证明非成员身份就足以证明两个相邻key的成员身份,一个小于目标key,一个则大于目标key。
    ) _' R$ R5 a& x! r+ r而这和Justin Drake提出的使用SNARKs/STARKs来压缩witness以及相关的想法有着相似的好处,另外一个好处是,由于证明是累加器密码学原生的,而不是构建在累加器密码学上的证明,因此这消除了一个数量级的开销,并移除了对零知识证明友好哈希函数的需求2 g& W% _( T( z) D4 D, |1 t' r
    但这里存在着两个大问题:
  • 为k个密钥生成witness需要的时间是O(N),其中N是状态的大小。而预计N对应的状态数据会有大约50 GB,因此在单个区块中生成这样的证明是不实际的;
  • 2、用k个新值更新S_k(x)和S_v(x) 花费的时间也需要O(N)。这在单个区块中是不切实际的,特别是考虑到诸如witness更新和重新排序之类的复杂性。下面我们将介绍应对这两大问题的解决方案。
      [+ N, \1 a6 F6 Y高效读取(Efficient reading) 9 I3 l/ D" b! u8 [# b9 E4 F
    我们提供了两种解决方案,一种针对Kate承诺而设计,另一种则是针对基于FRI的承诺。不幸的是,这些方案具有不同的优点和缺点,从而会导致不同的属性。
    + D# I! I: M; A( N' e1、Kate承诺首先,请注意,对于N次多项式f,有一种方案可生成N个对应于O(N * log(N))时间中每个q_i(x) = (f(x) - f(i)) / (X - i)的开放证明。
    $ d3 [0 y( _: r还请注意,我们可以按以下方式合并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方程组。
    2 m; H$ r  u! w4 \7 ~给定这样的线性组合,我们得到的东西仅是离开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))。( k. d( M6 D8 h6 V; g. C* d* h8 S
    一个可能的挑战是,对于大的状态,一个实际可计算的单一可信设置(例如,100多个独立参与者,因此只要其中任何一个是诚实的,方案就是安全的)是不够大的:例如,PLONK设置只能容纳约3.2 GB。相反,我们可以有一个由多个Kate承诺组成的状态。( N9 @, W* h+ A: q' U+ N# D
    我们对很多承诺作如下单一witness。为证明0 M- {* P/ J% F& U: A/ b
    ,首先让 (这是fi和1的线性组合,因此验证者verifier可以实时计算此承诺)。witness是;如果Q是一个多项式,则F实际上在那些位置为零,因此fi在其位置具有期望值。2、基于FRI的承诺我们将状态存储在一个二维多项式F(x,y)的求值中(每个变量的阶数为sqrt(N)),并致力于对4*sqrt(N) by 4*sqrt(N) square求值F。8 U1 F/ Z" l# @
    我们将所有我们关心的值存储在位置 (x, x**sqrt(N)),因此它们都具有唯一的x坐标。(请注意,在很多情况下,这些位置会超出我们承诺求值的4*sqrt(N) by 4*sqrt(N) square,而这无关紧要。)0 z) a" k% L8 w& x' a; F
    为了证明在一组点x_1, ..., x_k上的求值,我们构造了一个k次多项式路径(x),其在x_i处的求值为x_i ** sqrt(N)。
    ) a' g' a/ M) l- s然后,我们创建一个多项式h(t) = F(t, path(t)),其中包含对(x_i, y_i)的所有期望求值,并且具有k*(1+sqrt(N))次。
    $ |$ h1 }, w9 S( T6 ^) J  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))。
    9 c8 }% Q4 f* a# O! M- k/ H- X, S使用二维多项式的原因是,这确保了我们不必对所有F进行任何计算;相反,我们只需要对我们选择的随机30行F进行计算(即30*sqrt(N)),加上阶为 p * (sqrt(N) + 1)的h,创建FRI进行的计算大约为p * sqrt(N) 。可以将此技术扩展到二维以上的多项式,以将sqrt因子降低到更低的指数。. r5 C# m8 ?3 ~. C: o4 P
    高效写入(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天的值;* W/ O' j- X( L: g7 T5 N
    我们将使用的方法如下。为了从状态中读取一些键k,我们将依次读取C1, C2, S 。如果键位于某C1_k(x)处,则对应的值C1_v(x)存储该值,如果键位于C2_k(x),则C2_v(x)存储该值,依此类推,如果键位于S_k(x),则S_v(x)存储该值。如果这些检查都没有返回键,则该值为0。
    8 ?9 l) M$ u  Q! d/ k复制约束(copy constraint)参数的简介 ' `! k' i; h: e% V) p
    复制约束参数,是我们将使用的witness更新证明的关键组成部分;有关复制约束参数如何工作的详细信息,请参见此处。简而言之,该想法是选择一个随机r,并生成一个“累加”多项式ACC(x),其中ACC(0)= 1 且ACC(x + 1)= ACC(x)*(r + P(x))。你可以通过开放读取ACC(y) / ACC(x),来读取x .... y-1范围内的点累加器。你可以使用这些累加器值,将这些求值与其他求值集(作为多集)进行比较,而无需考虑排列。
    / n: R9 h- w  j+ m你还可以通过设置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的主张。) l" R4 H) K* r/ T7 G7 @% Q' p2 C; c
    为了证明子集,我们可以做相同的事情,除了我们还要提供一个指标多项式ind(x),证明该ind(x)在整个范围内等于0或1,并设置ACC(x + 1)= ACC(x )*(ind(x)*(r + P(x))+(1-ind(x)))(即,如果指标为1,则在每一步乘以r + P(x),否则不使用累加器值)。0 E  h8 M# {+ }# R# V0 M# F5 _
    小结:
  • 我们可以证明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)值当然不计算在内。
    ) |2 v8 ~* [7 H  \' _3 I+ Y5 |/ q映射合并参数(Map merging argument)
    0 o; o/ |( c) u为了更新缓存,我们使用了“映射合并参数”。给定两个映射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视为集合,我们首先需要展示:
    ( b! X, R) K1 b5 r5 ]( L1、A_k ? U;
    . T( R' Z; t/ q- k8 S% q2、B_k ? U;
    % B! _/ `3 D. A% ~3 K4 v! r3、I ? A_k;" D" q1 W$ o- f, I
    4、I ? B_k;3 B& L4 {$ H& p5 J" @; E
    5、A_k + B_k = U + I;
    6 C( @( P7 q0 r9 y3 W我们预先假设在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声明。  A6 b* B, c3 _" n* ?
    为了证明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。
    6 U( P& w& e* W: e: y: y关于E的约束表明,E中的所有值都夹在0和65535(包括0和65535)之间。对D_i的复制约束,证明D_i(x)中的所有值都在0到65535(含)之间,这证明了它是一个正确的16进制表示,从而证明了C_k(x+1)-C_k(x)实际上是一个正数。
      A' ~" j7 E+ U) S1 a9 C8 _# C: W& F3 ^: h现在,我们需要证明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)的一个置换。
    # n& {) M& R& }9 ]) @' T" G6 O- w使用映射合并参数 : t- j8 J* H* `) k
    我们按照下面的方式使用映射合并参数,假设每天有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的更新速度是否足够快。如果这不可能发生,那么我们可以通过添加更多层缓存的层次结构来解决这个问题。! G( C7 T0 p2 p. S8 R) W# v
    从糟糕的FRI中恢复
    ' ?' x1 R+ \$ C* I/ v2 ]  j对于FRI的情况,注意,有可能会出现有人生成的FRI在某些位置无效,但这不足以阻止验证。这不会立即造成安全风险,但可能会阻止下一个更新者生成witness。
    ) o. D$ V# {. q: d+ H. E. A% {我们通过以下几种方法来解决这个问题。首先,注意到某些FRI生成错误的人,可提供自己的FRI。如果通过相同的检查,它将被添加到可构建下一次更新的有效FRI列表中。然后,我们可以使用交互式计算游戏来检测和惩罚不良FRI的创建者。其次,他们可提供自己的FRI以及STARK来证明其有效,从而立即罚没了无效FRI的创建者。通过FRI生成STARK是非常昂贵的,尤其是在较大规模时,但这样做是值得的,因为这可以赚取很大一部分无效提议者的保证金奖励。
    " L4 }, [& E1 D- `) E# J因此,我们有了一种机制来使用多项式承诺,以此作为一个有效读取和写入witness来存储状态。这使我们能够大幅度减少见证内容(witness)大小,同时也可以带来一些好处,比如让我们有能力对数据可用性进行检查,以及实现关于状态的托管证明
  • BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
    声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    成为第一个吐槽的人

    万象争辉1 初中生
    • 粉丝

      0

    • 关注

      0

    • 主题

      27