原文作者：JoachimNeuJoachim-Ne，Paradigm研究实习生、斯坦福大学区块链科学博士
原文编译：隔夜的粥
任何L1区块链的核心职责是保证数据可用性。这种保证对于客户端能够解释L1区块链本身至关重要，并且它也是更高层应用的基础。为此，一种经常被讨论的技术会用于数据可用性验证的随机抽样，正如MustafaAl-Bassam、AlbertoSonnino以及VitalikButerin在2018年发表的一篇论文中所推广的那样。该技术是Celestia区块链的核心，并被提出通过「Danksharding」包含在权益证明以太坊中。
这篇博文的目的是解释数据可用性采样的基础、它所依赖的模型，以及在实践中实施该技术时所面临的挑战与未解决的问题。我们希望这篇文章能够吸引研究人员关注这个问题，并激发解决一些突出挑战的新想法。
问题
有人生成了一个数据区块。他们声称已经向「公众」提供了数据。你的目标是检查可用性声明，即，如果需要，你是否真的能够获得数据？
数据的可用性至关重要，基于欺诈证明的乐观系统，例如Optimism，需要数据可用性进行验证，甚至基于有效性证明的系统，例如StarkNet或Aztec，它们也需要数据可用性以确保活跃性。
对于迄今为止的问题表述，有一个简单的「幼稚」测试过程，这也是比特币等早期系统隐式采用的：只需下载整个数据块。如果你成功了，你就知道它是可用的，而如果你没有成功，你就会认为它不可用。然而，现在我们希望测试数据的可用性，而不需要自己下载太多的数据，比如因为数据量超出了我们的处理能力，或者因为在我们实际上不感兴趣的数据上花费大量带宽来验证其可用性似乎很浪费。在这一点上，我们需要一个模型来阐明仅下载或保留「部分数据」的「含义」。
模型
计算机科学中的一种常见方法是首先在具有相当丰富设施的模型中描述一项新技术，并随后解释如何实现该模型。我们对DAS采用了类似的方法，但正如我们将看到的，当我们尝试实例化模型时会弹出有趣的开放式研发问题。
在我们的模型中，在一个黑暗的房间里有一个公告板。首先，区块生产者进入房间，并有机会在公告板上写一些信息。当区块生产者退出时，他可以给你一小段信息。你带着一个手电筒进入房间，手电筒的光束很窄，电池电量很低，所以你只能在公告板的几个不同位置阅读文字。你的目标是让自己相信区块生产者确实在公告板上留下了足够的信息，这样如果你打开灯并阅读完整的公告板，你就可以恢复文件。
起初，这个问题似乎很棘手：我们可以要求区块生产者在公告板上写下完整的文件。现在考虑两种可能性：要么区块生产者诚实地写下整个文件，要么区块生产者行为不当，其漏掉了一小部分信息，使得整个文件不可用。通过仅在几个位置检查公告板，你无法可靠地区分出这两种情况，因此，你无法准确地检查数据可用性。我们需要一种新的方法！
解决方案
这就是里德-所罗门纠删码发挥作用的地方。让我们简单回顾一下，简单来说，纠删码的工作方式如下：k个信息块组成的向量被编码成一个n个编码块的向量。编码的比率R=k/n衡量了编码引入的冗余。随后，从编码块的某些子集中，我们可以解码原始信息块。
如果编码是最大距离可分的，那么原始信息块可以从编码块大小的任何子集中恢复，这是一个有用的效率和鲁棒性保证。里德-所罗门码是一种流行的MDS编码家族，其工作原理如下。记住，在学校里，你可能知道两点唯一地决定一条线：
这是因为一条线可以描述为具有两个系数的1次多项式：y=a1xa0。事实上，这一观点可以推广：任何次数的多项式t-1，它对应于描述多项式
的一组系数
，由多项式通过的任何t个点唯一确定。换句话说：一旦知道多项式在不同位置的求值，就可以在任何其他位置获得其求值。
里德-所罗门码就是基于这种洞察力构建的。对于编码，我们从k个信息块
开始，构造相关的多项式
，并在不同的x坐标上对其进行求值以获得编码块。现在，由于上述见解，这些编码块中的任何k个都允许我们唯一地恢复k-1次多项式，并读取系数以获得原始信息块。瞧！
回到我们的数据可用性问题：我们不再要求区块生产者在公告板上写下原始文件，而是要求他将文件分成k个块，使用Reed-Solomon码对它们进行编码，例如，速率R=1/2，并将n=2k编码块写入公告板。现在让我们假设区块生产者至少诚实地遵循编码。再次考虑两种情况：生产者行为诚实并写下所有块，或者生产者行为不端并希望保持文件不可用。回想一下，我们可以从n=2k个编码块中的任何k个恢复原始文件。所以为了保持文件不可用，区块生产者最多可以写入k-1个块。换句话说，现在至少有k1，超过n=2k个编码块的一半将丢失！
但是现在这两种情况，一个写满的公告板和一个半空的公告板，很容易区分：你在少数r个随机抽样的位置检查公告板，如果每个采样位置都有其各自的块，则认为该文件可用，如果任何采样位置为空，则该文件不可用。请注意，如果文件不可用，因此一半的公告板是空的，你错误地认为文件可用的概率小于
，即在r中呈指数级小。
存在的挑战
给定的「暗室公告板」模型是非常简单的。现在让我们考虑一下模型：组件代表什么？我们可以在真实的计算机系统中实现它们吗？如何实现？
事实上，为了帮助发现理论与实践之间的差距，我们已经使用「奇怪的」「暗室中的公告板」模型解释了问题和解决方案，其中的隐喻与真实的计算系统几乎没有相似之处。这是为了鼓励你思考现实世界和模型世界的各个方面是如何对应的，以及它们是如何实现的。如果你的模型中有一些部分无法转化为计算机/网络/协议等价物，那么你知道还有一些事情要做，可能是你的理解还有问题，也可能是开放的研究问题！；）
这是一个非详尽的挑战集合，对于其中一些挑战，社区多年来已经找到了合理的答案，而另一些仍然是开放的研究问题。
挑战A：如何确保公告板上的块实际上是由提议者写的？考虑采样块在网络上以任何形式传输到采样节点时的变化。这是一小段信息的来源，当生产者离开并且采样节点进入暗室时，区块生产者可以将其传递给采样节点。在实践中，这被实现为对写入公告板的原始内容的绑定向量承诺，并作为区块头的一部分进行共享。给出承诺后，区块生产者可以在公告板上留下每个编码块的证明，以表明该块确实是由区块生产者编写的。第三方无法在传输过程中更改块，因为承诺方案不允许为修改的块伪造有效证明。请注意，这本身并不排除区块生产者在公告板上写入无效/不一致的块，我们接下来将讨论这一点。
挑战B：确保区块生成者纠删码正确。在上述方案中，我们假设区块生产者正确地编码信息块，因此纠删码的保证成立，也就是说，从足够的编码块中，实际上可以恢复信息块。换句话说，区块生产者所能做的就是保留块，但不能将我们与无效块混淆。在实践中，有三种常见的排除无效编码的方法：
欺诈证明。这种方法依赖于这样一个事实，即一些采样节点足够强大，可以对如此多的块进行采样，以至于它们可以发现块编码中的不一致，并发布无效的编码欺诈证明，以将所讨论的文件标记为不可用。这方面的工作旨在最小化节点必须检查的块数量以检测欺诈。
多项式承诺。该方法使用KZG多项式承诺作为包含在区块头中的绑定向量承诺来解决挑战A。多项式承诺允许根据对未编码信息块的承诺直接验证Reed-Solomon编码块，因此没有无效编码的空间。可以这样想：向量承诺和Reed-Solomon编码在多项式承诺中是不可分割的。
有效性证明。可以使用密码学证明系统来证明向量承诺提交的编码块的正确纠删码。这种方法是一种很好的教学「心理模型」，并且对于所使用的纠删码来说是通用的，但在相当长的一段时间内可能效率不高。
挑战C：公告板是「什么」以及「在哪里」？提议者如何「写」到上面？在我们讨论公告板「是什么」和「在哪里」、提议者如何「写入」它以及验证者如何从中「读取」/「采样」之前，让我们回顾一下两种基本P2P网络原语的众所周知的缺点：
1、基于低量级泛洪的发布-订阅gossip网络，例如GossipSub，其中通信被组织成不同的「广播组」，参与者可以加入并向其发送消息：
在任意对抗行为下不安全；
常见的变体甚至不提供Sybil抵抗机制
通常无法保证参与者的组成员身份与其他参与者的隐私
如果有大量主题且每个主题的订阅者很少，则通信往往变得不可靠
2、分布式哈希表(DHT)，例如Kademlia，其中每个参与者存储哈希表中存储的全部数据的一部分，参与者可以快速确定到存储特定信息的对等体的短路径：
也不是拜占庭容错
事实上，DHT在对抗行为的恢复能力方面比gossip协议差得多：gossip协议「仅」要求由诚实节点形成的子图是连接的，这样信息可以从任何诚实节点到达所有诚实节点。而在DHT中，信息是专门沿着路径路由的，当查询到达其路径上的对手节点时，查询可能会失败。
也不提供Sybil抵抗机制
哪些参与者存储或请求哪些信息的隐私不受保障
考虑到这一点，我们可以回到关于如何实现公告板及其读/写操作的中心问题。编码块存储在哪里？它们如何到达那里？社区正在考虑的三种主要方法是：
GOSSIP：使用一个gossip网络分散编码块。例如，每个编码块可能有一个主题，负责存储某个块的节点可以订阅相应的主题。
DHT：将编码块上传到DHT中。然后，DHT将「自动」为每个参与者分配他们应该存储的块。
REPLICATE:来自附近副本的样本。一些节点存储数据的完整副本，并将块请求提供给采样节点。
这些方法的挑战是：
如何确保「公告板上有足够的空间」开始，以及公告板的所有部分随着时间的推移而保持在线？在一个真正无许可的系统中，这将特别棘手，因此大部分节点可能是对抗性的并且可能在瞬间消失。幸运的是，在区块链环境中，通常存在一些Sybil抵抗机制，并可用于建立声誉，甚至进行攻击，但关于如何利用Sybil抵抗机制来保护对等网络层，还有很多细节有待确定。
在前一点上进行扩展，因为网络是共识的基础，因此是所谓拜占庭容错系统的基础，网络层本身最好是BFT——但如前所述，流行的gossip或DHT协议并非如此。
最后，一些人认为，从长远来看，节点应该存储或转发不超过一个区块的一小部分，否则可扩展性和支持相对「弱」参与者的可能性是有限的。这与REPLICATE是对立的。对于GOSSIP，这需要大量的广播组，每个广播组都有少量订阅者，在这种情况下，gossip协议往往变得不那么可靠。在任何情况下，上述方法都会带来开销，例如，代表其他节点转发数据块的带宽不得超过单个节点的预算。
挑战D：我们「如何」实施随机抽样？这个问题有两个方面：期望的块如何在网络中定位和传输，以及如何确保采样相对于对手「保持随机」，即，对抗性区块生产者没有机会根据谁查询哪些块来自适应地改变其策略。
当然，直接从区块生成者那里进行采样不是一个可行的选择，因为这需要来自区块生产者的高带宽，并且如果每个人都知道区块生产者的网络地址，则会产生相关的拒绝服务向量。
另一种方法是在使用上述方法之一分散块后从swarm「群」中采样。具体来说：
在使用GOSSIP或DHT分散块之后，DHT可能会方便地路由采样请求和随机采样块，但这会带来上面讨论的挑战，最明显的是缺乏BFT和隐私。
或者，在GOSSIP下，每个节点都可以订阅与其想要采样的块相对应的主题——但存在上述挑战：除了缺乏BFT和隐私之外，拥有大量主题而每个订阅者都很少会导致不可靠的通信。
REPLICATE可以在「来自区块生产者的样本」和「来自群体的样本」之间进行折衷，其中从数据的完整副本中抽取块，并在网络对等方之间识别副本。
请注意，上面只解决了采样，而不是将来任何时候从公告板「阅读」。具体来说，GOSSIP本质上实现了一个临时公告板，而DHT实现了一个永久公告板。通常，我们需要的是一个永久性公告板，为此，GOSSIP必须辅以DHT来路由块，这会带来上述挑战。而REPLICATE会立即实现永久公告板。
下表说明了不同P2P协议来实现模型的不同情况。具体地说，面向gossip的方法有两种变体，一种使用gossip对块进行采样，另一种使用DHT对块进行采样。相比之下，面向DHT的方法完全依赖于DHT进行所有相关操作。在面向replication的方法中，每个节点使用请求/响应协议从附近的完整副本中读取/采样块。它有效地使用gossip进行块的初始传播，尽管两个对等方之间的gossipping在技术上可以通过请求/响应协议来实现。
此外，在上述所有技术中，「谁采样了什么」被泄露给了攻击者，因此攻击者可以通过自己的行为自适应地削弱/促进某些节点采样的块传播，从而某些节点相信该块是可用的。虽然早期的工作表明只有少数节点可以被，但这是不可取的。或者，早期的工作假设匿名网络通信，这在实践中至少会带来相当大的性能损失，如果不是完全不切实际的话。
挑战E：如何「修复」公告板的内容？也就是说，如果编码块丢失，它是如何恢复的？简单的修复涉及解码和重新编码，因此会带来相当大的通信和计算负担，特别是对于常见的Reed-Solomon纠删码。谁来承担这个负担？他们如何得到补偿？如何避免恶意区块生产者通过保留一些编码块，并迫使节点花费资源进行昂贵的修复来伤害采样节点？分布式维修方案呢？修复所需的块是如何检索到的，这回到了上一点关于将来从公告板上「读取」的问题。
挑战F：激励。如果采样是免费的，如何防止拒绝服务向量？如果抽样需要付费，如何同时做到完全匿名？那些在对等网络中存储公告板、路由信息或执行诸如块修复之类的维护任务的人如何获得补偿？
另一种模型
为了完整起见，我们简要提及一个稍微不同的模型，DAS实现了稍微不同的保证。即使没有匿名和可靠的网络，攻击者也最多可一定数量的诚实节点，使其相信不可用的文件可用。否则，它将不得不释放如此多的块，以便从诚实节点获得的所有块的联合中恢复文件。该模型的优点是，网络所需的属性更容易实现。缺点是对单个用户没有具体的保证，并且目前还不清楚如何收集诚实节点获得的所有样本并恢复文件。
未来的研究与发展方向
根据这篇博文中提出的观察和论点，我们认为以下将是未来关于数据可用性研究和开发的一些有趣方向：
显然，为了保护网络层，一些Sybil抵抗机制是必要的。方便的是，共识层正好提供了这一点，例如，以权益证明的形式。因此，在网络层上重用共识层的Sybil抵抗机制似乎是很自然的，例如从验证器集中在gossip协议中采样一个节点。虽然这可能不会立即保护非积极共识参与者的节点的网络，但它可以帮助在共识节点之间建立安全的「主干」，并随后可能成为为每个人提供更好安全的垫脚石。这条道路上合乎逻辑的下一步，将是仔细分析共识和网络与这种共享的Sybil抵抗机制的相互作用。
改进的gossip和DHT协议：
拜占庭容错(BFT)，特别是使用共识层常见的Sybil抵抗机制
效率
隐私保证
修复机制：
以分布式方式实施修复
研究和设计相关的激励措施
致谢：特别感谢MustafaAl-Bassam、DannyRyan、DankradFeist、SreeramKannan、SrivatsanSridhar、LeiYang、DanRobinson、GeorgiosKonstantopoulos以及DanLee对本文早期草稿提供的富有成果的讨论和反馈，并感谢AchalSrinivasan提供了漂亮的插图。
原文链接
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。