数据可用性抽样：从基础到未解决的问题

任何第 1 层区块链的核心职责是保证数据可用性。这种保证对于客户端能够解释第 1 层区块链本身以及作为更高层应用程序（如汇总）的基础至关重要。为此，一种经常讨论的技术是用于数据可用性验证的随机抽样，正如Mustafa Al-Bassam、Alberto Sonnino 和 Vitalik Buterin在 2018 年的一篇论文中所推广的那样。这项技术是 Celestia 区块链的核心，并提出通过“Danksharding”包含在权益证明 (PoS) 以太坊中。

这篇博文的目的是解释数据可用性抽样 (DAS) 的基础知识、它所依赖的模型，以及在实践中实施该技术时面临的挑战和未解决的问题。我们希望这篇文章可以“打动”研究人员，吸引他们关注这个问题，并激发新的想法来解决一些突出的挑战

某人（例如第 1 层区块提议者或第 2 层排序者）已经产生了一个数据块。他们声称已将其“提供”给“公众”。您的目标是检查可用性声明，即如果需要，您是否真的能够获取数据？

数据的可用性至关重要。乐观的基于防欺诈的系统，如Optimism，需要数据可用性来进行验证，甚至基于有效性证明的系统，如StarkNet或Aztec，也需要数据可用性以确保活性（例如，证明资产所有权以用于 rollup 的逃生舱口或强制交易包含机制）。

对于到目前为止的问题表述，有一个简单的“天真”测试程序，比特币等早期系统隐式采用了该程序：只需尝试下载整个数据块。如果你成功了，你就知道它是可用的；如果你没有成功，你认为它不可用。然而，现在我们想要测试数据的可用性，而不是自己下载太多数据，例如，因为数据比我们可以处理的大，或者因为在我们实际上不感兴趣的数据上花费大量带宽似乎很浪费，“仅”验证其可用性。在这一点上，我们需要一个模型来阐明下载或仅保留“部分数据”的“含义”。

模型

计算机科学中的一种常见方法是首先在具有相当大设施的模型中描述新技术；并随后解释如何实现该模型。我们对 DAS 采取了类似的方法，但正如我们将看到的，当我们尝试实例化模型时会弹出有趣的开放式研发问题。

在我们的模型中，暗室中有一个公告板（见下面的漫画）。首先，区块生产者进入房间并有机会在公告板上写下一些信息。当区块生产者退出时，它可以给你，验证者，一小段信息（大小不与原始数据成线性比例）。您带着光束非常窄且电池电量低的手电筒进入房间，因此您只能阅读布告栏上很少几个不同位置的文字。你的目标是让自己相信区块生产者确实在公告板上留下了足够的信息，这样如果你打开灯并阅读完整的公告板，你就能够恢复文件。

起初，这似乎很棘手：我们可以要求区块生产者在公告板上写下完整的文件。现在考虑两种可能性：要么生产者诚实行事并写下完整的文件，要么生产者行为不端并遗漏了一小部分信息，导致整个文件不可用。通过仅检查几个位置的公告板，您无法可靠地区分这两种情况——因此，您无法可靠地检查数据可用性。我们需要一种新方法！

理论解决方案

这就是擦除纠正的里德-所罗门码发挥作用的地方。让我们简单地回顾一下这些。在高层次上，擦除纠正码的工作原理是这样的。一个由k个信息块组成的向量被编码成一个由n个编码块组成的（更长的！）向量。编码的速率R=K/N，衡量编码所引入的冗余度。随后，我们可以从编码块的某些子集中解码出原始信息块。

如果代码是最大距离可分离（MDS），那么原始信息块可以从任何大小的子集恢复编码块，有用的效率和稳健性保证。Reed-Solomon 代码是一个流行的 MDS 代码系列，其工作方式如下。记得在学校你可能学过两点唯一确定一条线，这是因为一条线可以描述为具有两个系数的1次多项式:y=a1x+ao(现在假设这些点具有不同的x坐标)。事实上，这种见解可以推广:任何次数的多项式t-1，对应于系数集{ai} 描述多项式f(X) = ∑aXi,由任何唯一确定t多项式通过的点(具有不同的x坐标)。换句话说:一旦你知道多项式在t不同的位置，您可以在任何其他位置获得它的评估(通过首先恢复多项式，然后评估它)。

Reed-Solomon 代码就是基于这种洞察力构建的。对于编码，我们从k信息块{a;}'-1构造相关的多项式f(X) = ∑ aX，并在n不同的x坐标，以获得编码块。现在，由于上述洞察力，这些任何 k 编码块允许我们唯一地恢复度多项式 k-1.并读取系数以获得原始信息块。瞧!

回到我们的数据可用性问题：我们现在不要求块生产者在公告板上写下原始文件，而是要求它把文件剪切成 k 块，使用 Reed-Solomon 代码对它们进行编码，比如速率 R = 1/2 ，并写下 n = 2k 编码块到公告板。让我们假设现在区块生产者至少诚实地遵循编码——我们稍后将看到如何解除这个假设。再次考虑这两种情况：要么生产者诚实行事并记下所有块，要么生产者行为不端并希望保持文件不可用。回想一下，我们可以从任何 n = 2k 编码块文件中恢复原始文件 k 。所以为了保持文件不可用，块生产者最多可以写入k -1 块。也就是说，现在至少 k + 1, 超过一半 n = 2k 编码块，将丢失！

但是现在这两种情况，一个写满的公告牌和一个半空的公告牌，很容易区分：你在一个小数字上检查公告牌 r 随机采样的位置，如果每个采样位置都有其各自的块，则认为文件可用，如果任何采样位置为空，则认为该文件不可用。请注意，如果该文件不可用，因此（超过）一半的公告板是空的，则您错误地认为该文件可用的概率小于 2 的 -r 次方。

实际挑战

这非常简单——在给定的“暗室公告板”模型中。让我们考虑一下模型：组件代表什么？我们可以在真实的计算机系统中实现它们吗？如何实现？

事实上，为了帮助找出理论与实践之间的差距，我们已经使用“奇怪的”“暗室公告板”模型解释了问题和解决方案，其中的隐喻与真实的计算系统几乎没有相似之处。这是为了鼓励您反思真实世界和模型世界的各个方面是如何对应的，以及它们可能（或不）如何实现。如果您还剩下无法转化为计算机/网络/协议等价物的模型部分，您就知道还有一些事情要做——这可能是您理解上的差距，或者是开放的研究问题！;)

这里是一个非详尽的挑战集合，对于其中的一些，社区多年来已经找到了合理的答案，而另一些仍然是开放的研究问题。

挑战A：如何保证布告栏上的区块都是提案人写的？考虑采样块在网络上以任何形式传输到采样节点时的变化。这是小块信息的来源，当生产者离开并且采样节点进入暗室时，块生产者可以将其传递给采样节点。在实践中，这被实现为一个绑定向量承诺（想想Merkle 树) 写入公告板的原始内容，并作为区块头的一部分进行共享。有了承诺，区块生产者就可以在公告板上留下每个编码块的证明，以表明该区块确实是由区块生产者编写的。第三方不能在传输过程中更改块，因为承诺方案不允许为修改后的块伪造有效证明。请注意，这本身并不排除块生产者在公告板上写入无效/不一致的块，我们接下来将解决这个问题。

挑战 B：强制区块生产者正确擦除编码。我们在上述方案中假设块生产者正确编码信息块，因此纠删码的保证成立，因此实际上可以从足够多的编码块中恢复信息块。换句话说，块生产者所能做的就是保留块，而不是用无效块来混淆我们。在实践中，通常讨论三种排除无效编码的方法：

欺诈证据。这种方法依赖于这样一个事实，即一些采样节点足够强大，可以对如此多的块进行采样，以至于它们可以发现块编码中的不一致，并发出无效的编码欺诈证明，将有问题的文件标记为不可用。这一行的工作旨在最大限度地减少节点必须检查的块数（并作为欺诈证明的一部分转发）以检测欺诈（参见原始的 Al-Bassam/Sonnino/Buterin 论文为此使用 2D Reed-Solomon 代码原因）。

多项式承诺。这种方法使用KZG 多项式承诺作为包含在块头中的绑定向量承诺来解决挑战 A。多项式承诺允许基于对未编码信息块的承诺直接验证 Reed-Solomon编码块，因此没有留下无效空间编码。将其视为：向量承诺和 Reed-Solomon 编码在多项式承诺中是不可分割的。

有效性证明。可以使用密码证明系统来证明向量承诺承诺编码块的正确擦除编码。这种方法是一种很好的教学“心智模型”，并且就所使用的纠删码而言是通用的，但在相当长的一段时间内可能效率低下，不切实际。

挑战C：布告栏是“什么”和“哪里”？提议者如何“写入”它？在我们讨论公告板“是什么”和“哪里”，提议者如何“写入”它，以及验证者如何从它“读取”/“采样”之前，让我们回顾一下两个基本的众所周知的缺点点对点网络原语：

基于低度泛洪的发布-订阅八卦网络，例如GossipSub，其中通信被组织成不同的“广播组”（“主题”），参与者可以加入（“订阅”）并将消息（“发布”）发送到：

在任意（“拜占庭”）对抗行为（例如，日蚀攻击、女巫攻击、对等发现攻击）下不安全

常见变体甚至不提供女巫抵抗机制

通常不保证参与者的组成员身份对其他参与者的隐私（事实上，组成员身份通常会传达给对等方，以避免他们转发不需要的主题的网络流量）

如果有大量的主题，每个主题的订阅者很少，通信往往会变得不可靠（因为订阅特定主题的节点的子图可能不再连接，因此泛洪可能会失败）

分布式哈希表 (DHT) ，例如Kademlia，其中每个参与者存储一部分存储在哈希表中的整体数据，参与者可以快速确定到存储特定信息的对等点的短路径：

也不是拜占庭容错的（例如，诚实参与者请求的不适当路由，对网络形成/维护的攻击）

关于【数据可用性抽样：从基础到未解决的问题】的延伸阅读

• 长推：数据可用性(DA) 如何工作以及各有何不同？

  本文重点在eigenlayer的EigenDA和DA L1链，如@CelestiaOrg或@AvailProject，之间的比较

• 长推：数据可用性与数据存储有什么不同？

  数据存储就像罐头食品，数据可用性是自助餐

事实上，DHT 在对抗性行为方面的表现比八卦协议差得多：八卦协议“只”要求由诚实节点（以及诚实节点之间的边）形成的子图是连接的，以便信息可以从任何诚实节点到达所有诚实的节点。在分布式哈希表中，信息是专门沿着路径路由的，只要查询到达其路径上的敌对节点，查询就会失败。

也不提供女巫抵抗机制

不保证哪个参与者存储或请求哪条信息（从其他参与者的好奇眼中）的隐私

考虑到这一点，我们可以回到关于如何实现公告板及其读/写操作的中心问题。编码块存储在哪里？他们如何到达那里？正在考虑的三种主要方法是：

八卦：使用八卦网络分散编码块。例如，每个编码块可能有一个主题，负责存储某个块的节点可以订阅相应的主题。

DHT：将编码块上传到 DHT。然后 DHT 将“自动”分配给每个参与者他们应该存储的块。

REPLICATE：来自附近副本的样本。一些节点存储数据的完整（或部分）副本，并将块请求提供给采样节点。

这些方法的挑战是：

如何确保“公告板上有足够的空间”开始（即，有足够的参与者订阅了GOSSIP中的每个主题，或者每个节点可以存储它需要存储在DHT下的所有块)，并且公告板的所有部分都保持在线，因为节点会随着时间的推移而流失？（理想情况下，为了确保可扩展性，我们甚至希望有效地使用存储，即，诚实节点存储的内容之间不应有太多冗余。）这在节点来来去去的真正无许可系统中尤其棘手，并且那里可能没有女巫抵抗机制，因此绝大多数节点可能具有对抗性并可能立即消失。幸运的是，在区块链环境中，通常存在一些 Sybil 抵抗机制（例如 PoS），可用于建立声誉甚至削减，但关于如何利用 Sybil 抵抗机制来保护对等网络安全的许多细节仍有待确定。对等网络层。

扩展前一点，由于网络是共识的基础，因此是所谓的拜占庭容错 (BFT) 系统的基石，网络层本身最好是 BFT——但如前所述，流行的情况并非如此八卦或 DHT 协议，例如 GossipSub 或 Kademlia。（即使是REPLICATE也可能面临这一挑战，因为 DHT 可能仍用于网络堆栈的其他部分，例如，用于对等发现；但此时 DHT 的挑战成为一个普遍的网络层问题，而不是特定于数据可用性采样.)

最后，一些人认为，从长远来看，节点应该存储或转发不超过块的一小部分，否则可扩展性和支持相对“弱”参与者（参见去中心化）的可能性是有限的。这与REPLICATE是对立的。对于GOSSIP，这需要大量的广播组（“主题”），每个广播组都有少量订阅者，在这种情况下，八卦协议往往变得不那么可靠。在任何情况下，上述方法都伴随着开销，例如，代表其他节点转发块的带宽，这不能超过单个节点的预算。

挑战 D：我们“如何”实施随机抽样？这个问题有两个方面：所需的块是如何在网络中定位和传输的（即，如何从公告板上“读取”），以及如何确保采样相对于对手“保持随机”，即，对抗性区块生产者没有（太多）机会根据谁查询哪些块来自适应地改变其策略。

当然，直接从区块生产者那里采样不是一个可行的选择，因为这需要区块生产者的高带宽，如果每个人都知道区块生产者的网络地址，则相关的拒绝服务向量。（一些涉及从块生产者拉取的混合结构可以通过DHT和REPLICATE的镜头来查看。）

另一种方法是在使用上述方法之一（GOSSIP或DHT）分散块后从“群”中采样。具体来说：

在使用GOSSIP或DHT分散块后，DHT 可能会派上用场来路由采样请求和随机采样的块——但这会带来上面讨论的挑战，最明显的是缺乏 BFT 和隐私。

或者，在GOSSIP下，每个节点都可以订阅与它想要采样的块相对应的主题——但面临上面讨论的挑战：除了缺乏 BFT 和隐私之外，拥有大量主题而每个订阅者很少会导致通信不可靠。

使用REPLICATE可以在“来自块生产者的样本”和“来自群体的样本”之间做出折衷，其中块是从数据的完整副本中采样的，并且副本在网络对等点之间被识别。

注意，上面只解决了采样（“现在从公告板读取” ），而不是在未来任何时候从公告板“读取” 。具体来说，GOSSIP本质上实现了一个临时公告板（只能在其内容被写入/传播时读取/采样），而 DHT 实现了一个永久公告板（也可以在很久以后读取/采样）。通常，需要一个永久性的公告板（永久性要求从“天”到“永远”不等，具体取决于具体设计），为此GOSSIP必须辅以 DHT 来路由块，这与上述挑战。REPLICATE立即实现永久公告板。

下表说明了通常提出哪些对等协议来实现模型的哪些功能。具体来说，面向八卦的方法有两种变体，一种使用八卦对块进行采样，另一种使用 DHT 对块进行采样，而在这两种情况下，“块都写在公告板上”使用八卦和“从中读取”稍后使用 DHT 的时间点。相比之下，面向 DHT 的方法完全依赖于 DHT 来处理所有相关操作。在面向复制的方法中，每个节点使用请求/响应协议从附近的完整副本读取/采样块。它有效地使用八卦进行块的初始传播，尽管两个对等点之间的八卦在技术上可以通过请求/响应协议实现。

此外，在上述所有技术中，“who samples what”被泄露（至少部分）给对手，因此对手可以通过自己的行为自适应地削弱/促进某些节点采样的块的传播，从而欺骗某些节点相信该块是（不）可用的。虽然早期的工作表明只有少数节点可以被欺骗，但这是不可取的。或者，早期的作品假设匿名网络通信，这在实践中至少会带来相当大的性能损失，如果不是完全不切实际的话。

挑战E：如何“修复”看板的内容？也就是说，如果编码块丢失（例如，因为存储该块的节点已经脱机；甚至如何检测到？），它如何恢复？朴素修复涉及解码和重新编码，因此造成相当大的通信和计算负担，特别是对于常见的 Reed-Solomon 纠删码。谁来承担这个重担？他们如何得到补偿？如何避免恶意区块生产者通过扣留一些编码块并迫使节点花费资源进行昂贵的修复来破坏采样节点？分布式修复方案呢？修复所需要的chunk又是如何取回的，回到之前关于未来从棋盘上“读”的那一点。

挑战 F：激励。如果采样是免费的，如何防止拒绝服务向量？如果采样需要付费（如何实现？），如何同时做到完全匿名？那些存储（部分）公告板、对等网络中的路由信息或执行块修复等维护任务的人员如何获得补偿？

另一个模型

为了完整起见，我们简要提及一个略有不同的模型，DAS 为其实现了略有不同的保证。即使没有匿名和可靠的网络，对手也最多可以欺骗一定数量的诚实节点，让他们相信不可用的文件是可用的。否则，它将不得不释放如此多的块，以至于可以从诚实节点获得的所有块的联合中恢复文件。该模型的优点是网络所需的属性更容易实现（特别是当对等网络已被对手破坏时）。缺点是对单个用户没有具体的保证（你可能是少数被骗的人之一！），并且仍然不清楚如何收集诚实节点获得的所有样本并恢复文件

未来研发方向

基于这篇博文中提出的观察和论点，我们认为以下将是未来研究和开发的一些有趣方向：

似乎很明显，一些女巫抵抗机制对于保护网络层是必要的（现在，可以说，为此目的，网络协议通常隐含地依赖于 IP 地址的稀缺性，例如参见 GossipSub v1.1 的同行评分）。方便的是，共识层恰好提供了这一点，例如，以股权证明的形式。因此，在网络层重用共识层的 Sybil 抵抗机制似乎很自然，例如从验证者集合中的 gossip 协议中采样一个人的同行（并因此“继承”共识的诚实多数假设的力量）。虽然这可能不会立即保护不是积极共识参与者的节点的网络，但它可以帮助在共识节点之间建立一个安全的“骨干”（从而加强共识安全性），随后可能成为为每个人提供更好安全的垫脚石。这条道路上合乎逻辑的下一步是仔细分析共识和网络与这种共享的女巫抵抗机制的相互作用（这是最近朝着这个方向迈出的第一步）。

改进的八卦和 DHT 协议：（参见本调查）

拜占庭容错（BFT），特别是使用共识层上常见的女巫抵抗机制

效率（特别是对于拜占庭容错变体，到目前为止，它具有相当大的开销和/或较低的对抗弹性）

隐私保证（改进的保证，更高的效率/更低的开销）

修复机制：

以分布式方式实施修复（具有局部性的纠删码？）

研究设计相关激励措施

免责声明：本文仅代表作者个人观点，不代表链观CHAINLOOK立场，不承担法律责任。文章及观点也不构成投资意见。请用户理性看待市场风险，以及遵守所在国家和地区的相关法律法规。
图文来源：joachimneu，如有侵权请联系删除。转载或引用请注明文章出处！

标签：DAS数据可用性抽样