建议和反馈

请填写你的反馈内容

有关数据可用性和擦除编码的说明

2021-02-26 ·1906次阅读 ·读完需要33分钟

原文标题A note on data availability and erasure coding

原文链接https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding

作者:vbuterin

翻译Ada

编辑2018.09.25:查看https://arxiv.org/abs/1809.09044以获得这个的纸质版本。

什么是数据可用性问题?

为了理解数据可用性问题,最好首先从理解欺诈证明的概念入手。 假设攻击者以某种方式进行了无效的阻止(例如,后状态根错误,或者某些事务无效或格式错误)。 然后,可以创建一个欺诈证明,其中包含交易和该州的一些默克尔树数据,并使用它来说服任何轻客户端以及区块链本身该区块无效。 凭直觉,人们可以认为这种欺诈证据仅包含处理该区块所需的部分状态,还有一些散列可以证明所提供的状态的某些部分确实代表了该区块声称要建立的状态。 某个东西的上放。 验证欺诈证据包括使用给定的信息来尝试实际处理该块,并查看处理中是否存在错误; 如果存在,则该块无效。

欺诈的可能性证明理论上允许光客户nearly-full-client-equivalent保证模块,客户端收到不是欺诈(“”,因为该机制有额外要求的光端连接到至少其他诚实节点):如果一个光端接收到一块,然后可以问网络是否有任何欺诈证据,如果没有那一段时间后,光端可以假定块是有效的。

欺诈证明的激励结构很简单:

如果有人发送了无效的欺诈证明,他们将损失全部存款。如果有人发送了有效的欺诈证明,则无效区块的创建者将损失其全部存款,而一小部分将作为奖励提供给欺诈证明创建者。

尽管这种机制很优雅,但它包含一个重要的漏洞:如果攻击者创建了一个(可能有效,可能是无效的)数据块,但未发布100%的数据该怎么办? 即使可以使用简洁的零知识证明来验证正确性,攻击者仍然无法发布不可用的块并将其包含在链中,这仍然很糟糕,因为这种情况使所有其他验证者无法完全计算状态, 或使块与不再可访问的状态部分进行交互。 接受带有未发布数据的有效块还有其他不良后果; 例如,用于原子跨链交换的哈希锁或硬币换数据交易之类的方案依赖于以下假设:发布到区块链的数据将是可公开访问的。

在这里,欺诈证明不是一个解决方案,因为不发布数据不是唯一可归因的错误——在任何方案中,一个节点(“渔夫”)有能力就某些数据不可用发出警报,如果发布者随后发布剩余的数据,所有在当时没有注意到这一特定数据的节点都无法确定是发布者恶意隐瞒数据,还是钓鱼者恶意发出假警报。 

注意,从只检查T3之后数据的人的角度来看,情况1和情况2是无法区分的。

这就产生了一个不可能的选择:

设攻击者进行了一场攻击,他们隐瞒了数据,等待渔民捕获,然后立即释放数据。在这种情况下,渔民的回报是正的吗?如果是这样,恶意渔民发出假警报就是一个资金泵的漏洞。奖励是零吗?如果是这样,这是一个免费DoS漏洞,可以利用它强迫节点下载区块链中的所有数据,使轻客户机或分片的好处失效。奖励是消极的吗?如果是这样,那么渔民就是一种利他行为,所以攻击者只要在经济上比利他的渔民更持久,那么他们就可以自由地包含数据不可用的区块。

消除码作为解决方案

一个自然的解决方案是让轻客户端在接受块的有效性之前都验证它的数据可用性,但这样做的可能性很大。轻客户机可以从一个块中随机选取20个块,尝试从网络下载它们(使用块报头中的Merkle根来验证每个块),并且只有在所有20个请求都得到有效响应时才接受块。如果这个检查通过,假设一个诚实的少数的假设”,有足够的诚实的用户一起做这些检查,诚实的用户正在足够请求下载的大多数块,轻客户端知道有很高的概率,大多数可用的块。

但是,仅保留几百个字节的数据,仍然会发生非常危险的攻击,并且这种攻击仍然会席卷大多数进行此类检查的客户端。 为了解决这个问题,我们使用擦除码。 擦除码允许将M个长块的数据块扩展为N个长块的数据块(可以是任意大小),这样N个块中的M个都可以用来恢复原始数据。 我们要求块提交到该扩展数据的Merkle根,并要求轻量级客户端概率检查大多数扩展数据是否可用。

如果大部分扩展数据都可用,轻客户端就会知道以下三种情况之一是正确的:

整个扩展数据可用,擦除代码正确构建,并且该块有效。

整个扩展数据可用,擦除代码正确构建,但该块无效。

整个扩展数据都可用,但是擦除代码的构造不正确。

在情况(1)中,该阻止有效,并且轻客户端可以接受它。 在情况(2)中,预计其他一些节点将快速构造并中继欺诈证明。 在情况(3)中,还可以预期其他一些节点将快速构建并中继一种特殊的欺诈证明,该欺诈证明表明擦除代码的构建不正确。 如果轻客在一段时间内未收到任何欺诈证据,则将其视为该封禁实际上有效的证据。

有关实现所有这些逻辑的示例代码,请参见此处。

优化

如果使用最简单的一种Reed-Solomon码,那么上述方案中欺诈证明的大小将等于整个擦除代码的大小。 欺诈证明仅由M Merkle证明组成; 证明检查算法验证证明,然后使用这M个块计算剩余的块,并检查整个块集合的Merkle根是否等于原始Merkle根。 如果不是,则代码格式错误。

以下是使用256字节块将一维Reed-Solomon代码应用于256 KB1 MB数据的一些近似统计信息:

轻客户端证明的大小(256 KB): 20个分支*(256字节+ 10 Merkle树中间散列*每个散列32字节)= 11520字节 

轻客户端证明的大小(1 MB): 20个分支*(256字节+ 12 Merkle树中间散列*每个散列32字节)= 12800字节 

c++编码所花费的时间(256kb): 2.4

 c++编码花费的时间(1 MB): 21

 验证欺诈证明所需时间(256kb): 2.4

 验证欺诈证明的时间(1mb): 21

 欺诈证明大小(256kb): ~256- 512kb

 防伪大小(1mb): ~1- 2mb

计算时间包括部分优化; 使用Karatsuba乘法可将约3/4Lagrange插值加速到次二次运行时,尽管多点评估仍在二次时间内完成; 这是因为已发现用于多点评估的次二次算法既较难实施,而且常数因子也较高,因此,实施它们被认为是较不值得的权衡。 以上运行时也可以在单个内核上完成; 所有涉及的算法都是高度可并行化的,并且对GPU非常友好,因此可以进一步提高速度。

我们还可以更进一步,使纠删代码多维度化。在一个简单的Reed-Solomon代码中,原始数据被解释为一组点,表示在x=0, x=1…x = m - 1;扩展数据的过程包括使用拉格朗日插值来计算多项式的系数,然后在x=M…x = n - 1。我们可以改进这一点,将数据解释为一个正方形,表示一个多项式在(x=0, y=0)处的求值……(x = sqrt (M) 1, y = sqrt (M) 1)。然后这个正方形可以扩展到更大的正方形,直到(x=2*√(M)-1, y=2*√(M)-1)这减少了证明计算的计算复杂度,因为涉及的多项式的次数较低,也减少了欺诈证明的大小。

在这样的模型中,我们为所涉及的数据结构增加了更多的复杂性。首先,我们现在有4 *√(M)默克尔根,而不是一个默克尔根,每一行一个默克尔根,每列一个默克尔根。轻客户机需要下载所有这些数据,作为轻客户机证明的一部分。对于一个带有256字节块的1mb文件(例如。原始文件中的4096块以64x64的形状存在,所以扩展版本中是128x128),这将包含25632字节的散列,或证明中的8192个额外字节。此外,为了补偿二维erasure代码更加脆弱的事实,所需的分支数量从20增加到48。有利的一面是,默克尔分支的规模更小。

这样做的主要好处是,欺诈证明的大小要低得多:欺诈证明现在由单个行或列中的M个值以及这些值的Merkle证明组成,并且验证证明的过程包括恢复从这些值中丢失数据,计算出Merkle根,并表明这与提供的Merkle根不匹配。 请注意,欺诈证明者可以完全自由地选择所提供的Merkle证明来自行还是列的Merkle树; 这样,欺诈证明就可以涵盖格式错误的行和列以及行和列Merkle树之间的不一致。

现在我们展示新的统计数据,仍然是256字节的块,分别为1 MB(4096)4 MB(16384)。注意,这些都是估算值;完全实现这一点的算法还没有完全实现。

轻客户端证明的尺寸1 MB):48个分支*256个字节+ 6Merkle树中间哈希*每个哈希32个字节)+128Merkle*每个哈希32个字节)= 25600个字节

轻客户端证明的尺寸4 MB):48个分支*256个字节+ 7Merkle树中间哈希*每个哈希32个字节)+256Merkle*每个哈希32个字节)= 31232个字节

C ++编码所花费的时间(1 MB):7.5

C ++编码所花费的时间(4 MB):43.45

验证欺诈证明所花费的时间(1 MB):<0.01

验证欺诈证明所花费的时间(4 MB):<0.01

欺诈证明的最大尺寸1 MB):6Merkle树中间哈希*每个哈希32个字节* 64个元素= 12288个字节

欺诈证明的最大尺寸4 MB):7Merkle树中间哈希*每个哈希32个字节* 128个元素= 28672个字节 

如何将其整合到一个完整的机制中,以实现区块链中的数据可用性和欺诈证明?

一种简单而通用的方法如下。 每个顶级块都将包含擦除编码数据的Merkle根。 数据将是构成某些规范序列化形式的顶级块的全部数据,包括每个分片的内容。 每当块中可能存在可变长度的部分时,要么用零字节填充它们直到最大可能的长度(例如,由块大小或气体限制确定),要么在编码数据的开头添加表格 用于表示每个块的开始和结束。

然后将有两种欺诈证明。 第一种是擦除代码本身的欺诈证明,这取决于所使用的特定算法。 第二种是欺诈证明,表明在擦除编码的Merkle根中提交的数据未遵循协议的规则。 例如,如果协议规则规定bazook应等于kabloogmareez的级联的sha3,并且块的规范编码将bazook放置在字节1000 ... 1031,则kabloog 在字节50000 ... 50999mareez在字节55000 ... 55999处,则可以进行证明,其中包括来自擦除编码Merkle根的Merkle分支,该分支指向bazookkabloogmareez,并且可以验证 三个值不符合协议规定的关系。

这与可检索性证明基本上是不一样吗?

有点,但也不完全是。PoR协议的工作原理如下。Alice创建了一个文件,将它发送给Bob,然后Bob用一些技巧(通常也包括擦除编码和随机抽样)Alice证明他仍然拥有这个文件。有时候,Bob需要向Carol证明,而不是Alice, AliceCarol之间可以共享哪些信息是有限制的。这些协议通常涉及mac,或者在更高级的情况下包括椭圆曲线在内的各种部分同态方案。在所有情况下,都假定Alice是可信的,也就是说,我们假定Alice添加的任何检查数据都是正确添加的,文件实际上是存在的,并且Alice给卡罗尔的任何类型的公钥都是正确生成的。

在我们的模型中,(潜在的对手)Bob本身就是创建文件的人。BobCarol提交了一小段数据(例如,erase编码的数据的Merkle),并且Carol正在寻求Merkle根确实代表了一段数据,它是正确构造的,并且该数据是可检索的。除了她自己之外,卡罗尔不相信任何人,并且确保存在足够多的其他卡罗尔也在进行抽查,他们可以在数据中找到漏洞,或者可以下载整个文件。

一个关键想要的属性是共识——如果对某些文件的卡罗尔验证算法返回TRUE,并且我们假设网络中有足够的验证客户端,那么David也很有可能,可能在一段时间后基于网络延迟,对同一个文件返回TRUE;不同的参与者不可能对结果永远持不同意见,即使鲍勃恶意地收集和发布数据。

要让这些证明变得非常大,比如几千兆字节,有什么挑战?

目前有两大挑战。

如果我们简单地采用二维方案并尝试使其具有更高的维度,那么进入轻客户端证明的中间Merkle根的数量将变得非常大,而不是将那些Merkle根直接包含在轻客户端证明中 ,我们为它们提供了另一个数据可用性证明,这将需要较少数量的Merkle根。

如果证明非常大,那么我们就不能依靠单个节点来制作整个证明。 相反,我们将需要依靠某种协作生成。 但是,这使得故障识别更加困难。 如果X行与Y列或Z轴不匹配,并且两者是由不同的验证程序完成的,我们如何确定是谁的错? 这可能是可以解决的,例如,通过使验证者指向行//轴的合理性。 它们使用的现有值的位掩码,然后可以用来推断出哪一方出错了,但这增加了该方案的复杂性。

邻近证明可以帮助吗?

是的。 邻近证明是可以添加到Merkle根的简短证明,以概率(在Fiat-Shamir的意义上)证明Merkle树中至少有很大一部分(例如90%)的数据在同一根上 低阶多项式。 有关PoP如何工作的详细说明,请参见https://vitalik.ca/general/2017/11/22/starks_part_2.html

可以创建一个邻近证明,证明某些具有2N值的Merkle根接近90N多项式,这证明该数据接近某些唯一的数据集(N值)。 用户可以验证该证明,还可以随机下载树的分支样本以概率地验证例如至少80%的数据可用。 在这种情况下,通过相同测试的任何两个用户肯定将至少具有N * 1.44值,他们可以使用它们来恢复原始数据(也许可以使用Berlekamp-Welch算法消除错误),并且存在 确保这两个用户恢复的数据相同。

这种方法带来的一个困难是,并非所有的Merkle分支都将指向底层数据,因为接近性证明可以容忍少量故障。 因此,要证明任何特定数据的隶属关系,都需要增加一个接近度证明,并证明该Merkle分支表示的值在相同的低次多项式上。 因此,这最终不如下面所述的其他解决方案...

SNARKSTARK可以提供帮助吗?

是的。 SNARKSTARK可用于创建简洁(即O1)大小)的证明,证明数据的Merkle根是正确构造的,同时证明了在块中执行的状态转换是有效的。 这使我们在概念上使验证块的过程非常简单。

假设标头的格式为(prev_state_roottx_rootpost_state_rootproofsig ...),其中proofSTARK。 证明将证明tx_root是某些数据的Merkle树根,其中一部分数据是一组事务,而另一部分数据是该数据正确形成的擦除代码; 这也将证明在prev_state_root之上执行这些事务将导致post_state_root作为最终状态根哈希。 请注意,要创建STARK,创建者将需要提供作为见证人访问的所有Merkle树节点,但是此数据不需要进入STARK本身。

为了验证一个块,客户只需要下载标题,验证STARK,然后随机采样擦除编码数据的一些Merkle分支。

可以使用递归STARK(即证明其他STARK有效性的STARK)创建更高级的机制,从而允许协作创建擦除编码数据,从而解决了上述第二个问题。 从理论上讲,这种方案的可伸缩性的唯一上限是网络周围的节点愿意自愿可靠地存储的数据量。

攻击者是否可以通过释放完整的不可用块来绕开此方案,而是在客户端查询它们时仅释放单个数据位,从而规避此方案?

有点,但有局限性。假设一个块有4 MB的数据,每个轻客户端做20个查询,每个查询256字节。在整个网络,如果光有不到820的客户,那么它确实是,攻击者可以做这样的攻击,光和欺骗每一个客户相信可用的块当现实中没有足够的数据来重建整个出版(在现实中,你需要~ 1140光客户弥补重叠,和更多的如果擦除二维代码)。此外,如果擦除代码是欺诈的,那么这种欺诈可能永远不会被发现。

因此,该计划取决于两个诚实的少数派假设:

存在足够诚实的轻量级客户端,以至于他们的数据可用性证明请求的交集绝大多数都可能等于足够的擦除编码数据来恢复整个事情。

如果有足够的诚实节点发现擦除代码的任何部分都是欺诈性的,它们将生成并转发欺诈证明。

现在,即使有超过1140个诚实的轻型客户端,攻击者也可以决定回答其中前1000个客户端的请求,然后停止响应请求,从而欺骗了几个节点。 可以通过匿名洋葱路由网络分别发送每个请求来解决此问题,从而使攻击者无法分辨哪些请求来自同一节点。 如果部分彼此信任的节点(即彼此可能互不信任)可能也会在彼此的请求失败时互相闲聊,从而允许其他节点尝试自己发出请求。 这样,如果一个块被大部分节点拒绝,则它将被所有节点拒绝。

比起让所有人下载并验证所有内容,这感觉有点不稳定。

这是不完美的,但请注意,如果正确构建了设计,则许多问题必须立即出错以使方案失败。 一个设计良好的可伸缩数据可用性验证方案将在每个数据上签名一个随机选择的验证者委员会,因此诚实多数模型和诚实客户少数假设都将需要失败才能使不可用数据通过。 就是说,确保数据不会散播得太细,以至于诚实的少数派客户假设成为现实问题,这可能是该方案确实存在的主要可扩展性限制; 即使它适用于千兆字节块,也不适用于PB块。


声明:作为区块链技术信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与链客社区官方立场无关。
评论(0)问答(0)
请先登录或注册

请先登陆或注册

相关推荐

柏林硬分叉对以太坊 Gas 影响几何?

原文标题:《柏林硬分叉对 Gas 影响几何?》撰文:Franco Victorio翻译:ETH 中文站柏林硬分叉已于 4 月 14 日在主网上线,引入了四份 EIP 。其中的两份 (EIP-2929 ......
Blockchain · 2021-04-16
189阅读 · 0赞赏 · 0问答

矿工和套利机器人,如何在以太坊网络里进行打劫?

以太坊发展到今天,币价一路攀升,生态越来越繁荣,朝着世界计算机的宏伟目标奔跑的脚步也越来越快。以太坊发展的好,不仅仅对炒币者来讲可以大赚一笔,对于矿工来讲更是一本万利,毕竟挖矿不用太担心币价,无非就是......
Long · 2021-04-15
180阅读 · 0赞赏 · 0问答

Matter Labs: L2突破性扩展

(Zksync的合作伙伴,Zksync是Matter Labs的产品)以太坊L1(一层网络)即将大规模迁移到第L2层。随着协议从以太坊基础层转移到乐观汇总和与EVM兼容的zkRollups上,许多人希......
Aier · 2021-04-14
282阅读 · 0赞赏 · 0问答

原始无序MEV时代到来

设想一种情形:用户在 AMM 类型的 DEX 上做交易,无论设置什么滑点,最终都会在你能接受的最差价格上成交。这可能是个对用户来说很可怕的场景。TLDR;目前的 MEV-Geth 实现机制改变了原本网......
奔跑的元 · 2021-04-13
286阅读 · 0赞赏 · 0问答

dYdX 推出 Layer 2 主网,快速了解新功能及特点

dYdX Layer 2 不仅大幅降低了手续费,还支持快速提现功能,用户无需等待 Layer 2 交易被打包到以太坊区块链上。原文标题:《通告 | dYdX 推出 Layer 2 主网》撰文......
Blockchain · 2021-04-13
297阅读 · 0赞赏 · 0问答

V神提到的作为以太坊可扩展性未来的分片是什么?

文章来源:https://www.jinse.com/blockchain/1057950.html 4月7日,V神的网站更新了一篇名为《分片为何如此出色:揭开技术属性的神秘面纱》的文章,其中提到:分......
Rooney · 2021-04-13
465阅读 · 0赞赏 · 0问答

4304.0

LK币

19

粉丝

122

笔记

感谢"区块技术花"

这篇精彩的笔记,目前已经帮助

  • 0
  • 1
  • 9
  • 0
  • 6
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

公司名称:北京链客行科技有限公司

联系方式:010-67707199

ICP备案号:京ICP备18032136号

Copyright:链客区块链技术问答社区 版权所有

感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!