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

曾汨   |     |   1432 次阅读

本来是要展开一个叫做「与C.C. Liang共笔系列」,无奈C.C.太忙,最终还是只能自干,不过依旧感谢 C.C. Liang 提供素材跟观念厘清。——作者注

· · ·

data availability(数据可用性) 跟 fraud proof (欺诈证明)对于区块链交易量扩展,是很重要的两项因素。当交易量大意味着数据量就变大(无论是分片或是加大区块大小),而数据量越大,能够运行全节点的人就会越少(因为硬件跟维护成本越高)。举例来说,Ethereum 2.0 有 1024 条链,不可能每个人都把 1024 条的数据都下载下来,更何况,这样也失去分片的意义,但若某节点做分片 A 的 validator,此时,需要跟分片 B 有所互动,不太可能把分片 B 的所有区块都下载下来,太耗时也太占空间,而且若如此设计,最终也会把全部的链都下载下来….。但是,若没有全部的区块那要怎么验证交易呢?!这就是「数据可用性」的重要性。

数据可用性简单来说就是拿不拿得到数据,但不代表拿到的数据的有效的/正确的。那在讨论数据可用性问题之前,先来认识欺诈证明。

在区块链世界中,验证数据方式可以分为有效证明(validity proof)跟欺诈证明两种。有效证明就是现在区块链的运作方式-「验证数据是正确的,才能上链」,也就是当你需要转帐时,矿工需要先验证你的余额是否足够,确认你余额是够的(验证数据是正确的)才会打包。而欺诈证明则是相反,验证者收到交易之后,经过一段时间若没有人提出异议/挑战,那就代表你送出的交易是没问题的,这种方式验证成本相对较低,也因此大部分L2方案选择使用欺诈证明作为数据验证的方式。

而轻节点只下载部分的数据(通常是 block header),要如何能在运作上几乎跟全节点一样可靠呢(‘几乎’是因为轻节点需要额外的一些假设)?就必须借助数据可用性跟欺诈证明的合作。

· · ·

Fishermen

渔夫(fishermen)机制是一种很直觉的设计方式,就是渔夫们观察着网络上的无效数据,发现后送出欺诈证明以得到奖励。

基本的奖惩机制如下,
1.若有人提出无效的欺诈证明,则没收押金,
2.若有人提出有效的欺诈证明,送出无效数据的人会被没收押金,而押金部份当作挑战者(提出欺诈证明的人)的奖励。

但是,这种机制在这个情境会有问题。我们来看以下这两个例子

Case 1:
T1:攻击者 v1 送出不完整的数据(等待被挑战)
T2: v2 送出欺诈证明证明数据是无效的
T3:攻击者 v1 再补送剩下的数据

Case 2:
T1: v1 送出正确的数据
T2:攻击者 v2 发出无效的欺诈证明

-来源: https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding-

如果渔夫打了个盹,没注意到 T2 发生什么事,到了 T3 才来验证,在这样的状况下是无法判断出两个的差异(因为 T3 所能看见的就是 “一份完整的数据” 被提出 “欺诈证明”,不知道其实 case1 是后来补件的)。以上例来说,case1 的 v2 要给奖励吗?

  1. 若给了,则攻击者就可以借由发出无效的欺诈证明来赚钱(因为两者是无法分辨的);
  2. 若要惩罚,那就没有人愿意提出欺诈证明;
  3. 若什么事都不做,则提供了一个免费的 DOS 攻击。因此,这种方式有个根本的问题,就是无法有效遏止攻击者隐藏数据(因为被发现了,再补件即可),也就无法判断节点或是渔夫谁是恶意的。

· · ·

Reed-Solomon Erasure Code

延续上面的问题,若把区块切成 N 个区段(chunks),而轻节点从网络中随机去挑选某 20 个区段来验证是否正确(借由 block header 中的 merkle root 来验证),当 20 个区段都是有正确的,轻节点就接受此块,这个方法有很高的机率可以证明数据是有效的,但这种方式只验证到部分的数据,并不是整个区块,若攻击者伪造的区块只有极少的差距,例如有几十或几百的 bytes,仍有机会避过这样的验证机制。而 erasure code (纠删码)是可以解决这个问题的好方法!

何谓纠删码呢?! 纠删码可以在数据部分遗失的状况下,组回原本的数据(但无法容忍数据的篡改),常用在网络通讯,磁盘阵列或是 DVD。可以想作是在原本的数据,再多加部份的备份,所以丢掉部分数据也没关系。纠删码编码方式有很多种,也分别适用不同领域,这边使用的 RS(Reed-Solomon) 纠删码,是一种原理相较简单的编码方式。概念上就是用 Lagrange 插值方式,长出多余的备份数据。

假设,把区块分成 M 个区段,借由 RS 纠删码把数据延伸为 N 个区段(N > M),因此只要 N 个中的 M 个就可以把数据还原,所以若有节点不提供数据或是部分数据遗失了,仍可还原区块做验证。

这边做一个简单的计算,先假设最简单的状况 M=N,区块大小 1MB,每 256bytes 切成一个区段,所以可得 4096(M=4096) 个区段,然后,将全部区段组成一个 merkle tree(会有12层)。接着,随机取 20 个区段来验证,数据量将是

20 branches * (256 bytes + 12 Merkle tree intermediate hashes * 32 bytes per hash) = 12,800 bytes

而欺诈证明的大小约是 1.5MB

如果将数据延伸到多维度,例如二维。数据将变为 sqrt(M)*sqrt(M) 的正方形(x = 0 ~ sqrt(M)-1, y = 0 ~ sqrt(M)-1),接着使用二维 RS 纠删码将数据延伸一倍,可得 N = 2*sqrt(M),如下:

而 merkle tree 的数量从原本的一个变成 4*sqrt(M) 个(每个栏列皆为一个 merkle tree,如下图所示)

接着,回到上面的例子,1MB 的区块,每 256bytes 为一个区段,所以可以得到 64x64 的正方形,共有 4*64个merkle tree,但是取样数就需要有 48 个,因此数据量为:

48 branches * (256 bytes + 6 Merkle tree intermediate hashes * 32 bytes per hash)+ (128 Merkle roots * 32 bytes per hash) = 25,600 bytes 

而欺诈证明的大小约为 12KB。

这里我们看到,数据量虽然变大了,但是欺诈证明的数据大幅减少了,而且因为 merkle tree 的层数减少许多,在效能上也有大幅的提升。下图是论文中对于取样数, 区段数量跟轻节点数的表格(s : 取样数,k : sqrt(M)),有兴趣可以看论文中的公式推导。

-来源: https://arxiv.org/pdf/1809.09044.pdf-

· · ·

但若在一般的网络模式下,会知道自己的邻居们(peer nodes)是谁,所以对攻击者来说,就有空间操控,某个轻节点来问数据就故意不给,或是有时给有时不给等等的扰乱轻节点取得数据的稳定性。因此会需要搭配洋葱网络服用,攻击者就无法针对特定的轻节点作扰乱。再加上欺诈证明的挑战,在整个设计中只需要保证网络中有一个诚实节点即可。

· · ·

而全节点跟轻节点的沟通程序如下图:

  1. 有新区块产生,轻节点会收到某个全节点的通知,并且提供 block header 跟上述的每个栏/列的 merkle root
  2. 轻节点会随机挑选 (x, y) 值给不同的全节点(x,y 分别对应二维纠删码的列跟栏)
  3. 全节点接收到 (x, y) 座标后,提供对应的区段,并注明此数据区块是栏还是列(因为同一个座标可以取栏或是列的数据),若此全节点没数据,就继续广播给其他全节点
  4. 轻节点接受到数据后,验证区块的 merkle root 和1.所提供的是否一致,若为一致,则标记为正确的数据,并等待挑战(欺诈证明)

这是目前 Ethereum 2.0 light client的提案#1194是针对数据可得性证明效率不足的讨论,主要的问题在于,二维的纠删码让处理的数据量变大,也增加网络传输的负荷,再加上 EIP1559,将使得区块平均的负载量约只有 50%,也就意味着需要填很多的 0,让二维纠删码徒增很多无意义的数据,这也是目前尚未解决的问题。

如果文章有错误的地方,欢迎纠正,若有说明不清的也欢迎提出。

· · ·

感谢Ethereum Foundation Researcher, C.C. Liang(梁智程)的协助及建议,才能使文章顺利完成。

参考:
A note on data availability and erasure coding
Fraud and Data Availability Proofs
Unsolved Problems in Blockchain Sharding
欺诈证明与有效证明


原文链接: https://medium.com/taipei-ethereum-meetup/data-availability-on-ethereum-2-0-light-node-dc55c6455df6
作者: Kimi Wu

本文首发于 Taipei Ethereum Meetup 的 Medium 站,EthFans 经授权转载,为符合大陆读者的习惯,进行了简繁转换并将部分术语改为习惯用法。


你可能还会喜欢:

Echo | 以太坊简介(注释版)
干货 | 分片的理念与挑战,Part-2:区块链分片悬而未决的问题
科普 | Cosmos 区块链的工作原理,Part-2:如何跨链,为何要跨链?

 
0 人喜欢