Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

以太坊 2.0 轻节点的数据可用性

牙忍喊适索
213 0 0
本来是要展开一个叫做「与C.C. Liang共笔系列」,无奈C.C.太忙,最终还是只能自干,不过依旧感谢 C.C. Liang 提供素材跟观念厘清。——作者注· · ·data availability(数据可用性) 跟 fraud proof (欺诈证明)对于区块链交易量扩展,是很重要的两项因素。当交易量大意味着数据量就变大(无论是分片或是加大区块大小),而数据量越大,能够运行全节点的人就会越少(因为硬件跟维护成本越高)。举例来说,Ethereum 2.0 有 1024 条链,不可能每个人都把 1024 条的数据都下载下来,更何况,这样也失去分片的意义,但若某节点做分片 A 的 validator,此时,需要跟分片 B 有所互动,不太可能把分片 B 的所有区块都下载下来,太耗时也太占空间,而且若如此设计,最终也会把全部的链都下载下来….。但是,若没有全部的区块那要怎么验证交易呢?!这就是「数据可用性」的重要性。; C# a- Q+ m$ k+ P
数据可用性简单来说就是拿不拿得到数据,但不代表拿到的数据的有效的/正确的。那在讨论数据可用性问题之前,先来认识欺诈证明。
9 N0 \$ ^2 k  b; N在区块链世界中,验证数据方式可以分为有效证明(validity proof)跟欺诈证明两种。有效证明就是现在区块链的运作方式-「验证数据是正确的,才能上链」,也就是当你需要转帐时,矿工需要先验证你的余额是否足够,确认你余额是够的(验证数据是正确的)才会打包。而欺诈证明则是相反,验证者收到交易之后,经过一段时间若没有人提出异议/挑战,那就代表你送出的交易是没问题的,这种方式验证成本相对较低,也因此大部分L2方案选择使用欺诈证明作为数据验证的方式。" n8 S0 R- H  e* K" z* N) ]2 P
而轻节点只下载部分的数据(通常是 block header),要如何能在运作上几乎跟全节点一样可靠呢(‘几乎’是因为轻节点需要额外的一些假设)?就必须借助数据可用性跟欺诈证明的合作。" ?2 ^/ n; V) U& `- S
· · ·Fishermen渔夫(fishermen)机制是一种很直觉的设计方式,就是渔夫们观察着网络上的无效数据,发现后送出欺诈证明以得到奖励。
4 Y2 P6 n0 [- y2 P$ ~# o基本的奖惩机制如下,
' C+ }2 e0 K7 @2 g. w0 B1.若有人提出无效的欺诈证明,则没收押金,2.若有人提出有效的欺诈证明,送出无效数据的人会被没收押金,而押金部份当作挑战者(提出欺诈证明的人)的奖励。但是,这种机制在这个情境会有问题。我们来看以下这两个例子
& u  t' V) S( W/ C* I0 QCase 1: . I4 r2 K( i% ~- i5 h1 O2 K
T1:攻击者 v1 送出不完整的数据(等待被挑战)T2: v2 送出欺诈证明证明数据是无效的T3:攻击者 v1 再补送剩下的数据Case 2: 6 S# ?( `( ^5 ]
T1: v1 送出正确的数据T2:攻击者 v2 发出无效的欺诈证明
0 M' r' ?. r0 r0 {/ d! u% b-来源: https://github.com/ethereum/research/wiki/A-note-on->如果渔夫打了个盹,没注意到 T2 发生什么事,到了 T3 才来验证,在这样的状况下是无法判断出两个的差异(因为 T3 所能看见的就是 “一份完整的数据” 被提出 “欺诈证明”,不知道其实 case1 是后来补件的)。以上例来说,case1 的 v2 要给奖励吗?若给了,则攻击者就可以借由发出无效的欺诈证明来赚钱(因为两者是无法分辨的);若要惩罚,那就没有人愿意提出欺诈证明;若什么事都不做,则提供了一个免费的 DOS 攻击。因此,这种方式有个根本的问题,就是无法有效遏止攻击者隐藏数据(因为被发现了,再补件即可),也就无法判断节点或是渔夫谁是恶意的。· · ·Reed-Solomon Erasure Code延续上面的问题,若把区块切成 N 个区段(chunks),而轻节点从网络中随机去挑选某 20 个区段来验证是否正确(借由 block header 中的 merkle root 来验证),当 20 个区段都是有正确的,轻节点就接受此块,这个方法有很高的机率可以证明数据是有效的,但这种方式只验证到部分的数据,并不是整个区块,若攻击者伪造的区块只有极少的差距,例如有几十或几百的 bytes,仍有机会避过这样的验证机制。而 erasure code (纠删码)是可以解决这个问题的好方法!9 V6 ^: E+ V% [( u9 {
何谓纠删码呢?! 纠删码可以在数据部分遗失的状况下,组回原本的数据(但无法容忍数据的篡改),常用在网络通讯,磁盘阵列或是 DVD。可以想作是在原本的数据,再多加部份的备份,所以丢掉部分数据也没关系。纠删码编码方式有很多种,也分别适用不同领域,这边使用的 RS(Reed-Solomon) 纠删码,是一种原理相较简单的编码方式。概念上就是用 Lagrange 插值方式,长出多余的备份数据。
/ W4 k* i8 @; p0 x假设,把区块分成 M 个区段,借由 RS 纠删码把数据延伸为 N 个区段(N > M),因此只要 N 个中的 M 个就可以把数据还原,所以若有节点不提供数据或是部分数据遗失了,仍可还原区块做验证。0 e; M" ]5 f, a' c3 ]: A" k
这边做一个简单的计算,先假设最简单的状况 M=N,区块大小 1MB,每 256bytes 切成一个区段,所以可得 4096(M=4096) 个区段,然后,将全部区段组成一个 merkle tree(会有12层)。接着,随机取 20 个区段来验证,数据量将是8 o1 O$ G$ w! d* W  S! O2 M! m
20 branches * (256 bytes + 12 Merkle tree intermediate hashes * 32 bytes per hash) = 12,800 bytes而欺诈证明的大小约是 1.5MB。
7 d! E. D2 ^% _* d/ G1 @) r8 }如果将数据延伸到多维度,例如二维。数据将变为 sqrt(M)*sqrt(M) 的正方形(x = 0 ~ sqrt(M)-1, y = 0 ~ sqrt(M)-1),接着使用二维 RS 纠删码将数据延伸一倍,可得 N = 2*sqrt(M),如下:
9 Y: b, |3 h) x# [6 u( T而 merkle tree 的数量从原本的一个变成 4*sqrt(M) 个(每个栏列皆为一个 merkle tree,如下图所示)' n+ J5 E9 E: Q  ~7 u
接着,回到上面的例子,1MB 的区块,每 256bytes 为一个区段,所以可以得到 64x64 的正方形,共有 4*64个merkle tree,但是取样数就需要有 48 个,因此数据量为:9 N4 _9 Z' n/ w7 u' M6 w1 U/ P
48 branches * (256 bytes + 6 Merkle tree intermediate hashes * 32 bytes per hash)+ (128 Merkle roots * 32 bytes per hash) = 25,600 bytes 而欺诈证明的大小约为 12KB。) \, ~$ i, ?' X4 O# Q) K
这里我们看到,数据量虽然变大了,但是欺诈证明的数据大幅减少了,而且因为 merkle tree 的层数减少许多,在效能上也有大幅的提升。下图是论文中对于取样数, 区段数量跟轻节点数的表格(s : 取样数,k : sqrt(M)),有兴趣可以看论文中的公式推导。
; t+ \1 }# v" @6 x-来源: https://arxiv.org/pdf/1809.09044.pdf-· · ·但若在一般的网络模式下,会知道自己的邻居们(peer nodes)是谁,所以对攻击者来说,就有空间操控,某个轻节点来问数据就故意不给,或是有时给有时不给等等的扰乱轻节点取得数据的稳定性。因此会需要搭配洋葱网络服用,攻击者就无法针对特定的轻节点作扰乱。再加上欺诈证明的挑战,在整个设计中只需要保证网络中有一个诚实节点即可。
* K8 S; V/ U( ~& D3 v· · ·而全节点跟轻节点的沟通程序如下图:有新区块产生,轻节点会收到某个全节点的通知,并且提供 block header 跟上述的每个栏/列的 merkle root轻节点会随机挑选 (x, y) 值给不同的全节点(x,y 分别对应二维纠删码的列跟栏)全节点接收到 (x, y) 座标后,提供对应的区段,并注明此数据区块是栏还是列(因为同一个座标可以取栏或是列的数据),若此全节点没数据,就继续广播给其他全节点轻节点接受到数据后,验证区块的 merkle root 和1.所提供的是否一致,若为一致,则标记为正确的数据,并等待挑战(欺诈证明)
) p# o' w' E, ?这是目前 Ethereum 2.0 light client的提案,#1194是针对数据可得性证明效率不足的讨论,主要的问题在于,二维的纠删码让处理的数据量变大,也增加网络传输的负荷,再加上 EIP1559,将使得区块平均的负载量约只有 50%,也就意味着需要填很多的 0,让二维纠删码徒增很多无意义的数据,这也是目前尚未解决的问题。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

牙忍喊适索 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    9