大纲

• 1. 介绍
• 2. 问题
• 3. 模型
• 4. （理论）解决方案
• 5. （实践）挑战
• 6. 另一个模型
• 7. 未来研究与发展方向

介绍

任何 layer-1 区块链的核心责任之一是保证 数据可用性(data availability)。这一保证对客户端能够理解 layer-1 区块链本身是至关重要的，也是像 rollups 这样的更高层应用的基础。为此，一个经常被讨论的技术是 数据可用性验证的随机采样，该技术在2018年由 Mustafa Al-Bassam, Alberto Sonnino, 和 Vitalik Buterin 的论文 中被广泛传播。该技术是 Celestia 区块链的核心，并被提议纳入权益证明（PoS）以太坊的“Danksharding”。

本文的目的是解释数据可用性采样（DAS）的基本知识、其所基于的模型以及在实践中实现该技术时面临的挑战和开放问题。我们希望这篇文章能够激发研究者的兴趣，吸引他们关注这一问题，并推动新的想法以解决一些突出挑战（参见 以太坊基金会近期的提案请求）。

问题

某些人（例如一个 layer-1 区块提议者或 layer-2 排序器）产生了一块数据。他们声称已将其“提供给”公众。你的目标是检查可用性声明，即如果你需要获得数据，实际上能否获得它？

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

到目前为止，对于问题的表述有一个简单的“天真的”测试程序，早期系统如比特币隐式采用：只需尝试下载整个数据块。如果你成功，你就知道它是可用的；如果你未成功，你则认为它不可用。然而，现在我们希望测试数据可用性 而不自己下载太多数据，例如，因为数据超过了我们能够处理的大小，或者因为在我们实际上不关心的数据上花费大量带宽“仅仅”是为了验证其可用性似乎是浪费。在这一点上，我们需要一个模型来澄清仅“部分数据”的下载或保留意味着什么。

模型

计算机科学中的一种常见做法是首先在一个具有相当充裕功能的模型中描述一种新技术；随后再解释如何实现该模型。我们在此采用类似于 DAS 的方式，然而，正如我们将看到的，当我们试图实例化模型时，会出现有趣的开放 R&D 问题。

在我们的模型中，有一个在黑暗房间里的公告板（见下面的漫画）。首先，区块生产者进入房间，并有机会在公告板上写一些信息。当区块生产者离开时，它可以给你，即验证者，提供一小块信息（大小不与原始数据线性增长）。你进入房间时带着一个光束非常狭窄且电量不足的手电筒，因此你只能读取公告板上很少的不同位置的内容。你的目标是让自己相信，区块生产者确实在公告板上留下了足够的信息，以便如果你打开灯并读取完整的公告板，你将能够恢复该文件。

乍一看，这似乎有些棘手：我们可以要求区块生产者在公告板上写下完整的文件。现在考虑两种可能性：或者生产者诚实地写下完整的文件，或者生产者不当行为并遗漏了某个小块信息，从而使文件整体不可用。通过仅检查公告板上少数地点，你无法可靠地区分这两种情况——因此，你无法可靠地检查数据可用性。我们需要一种新方法！

（理论）解决方案

在这里，纠错的 Reed-Solomon 码发挥作用。让我们稍作绕道来回顾一下这些内容。从高层次来看，纠错编码的工作方式是这样的：一个 k 个 信息块 被编码为一个（更长的）n 个 编码块 的向量。编码的 速率 $ R = k / n $ 衡量了码所引入的冗余。随后，我们可以从某些编码块的子集中 解码 原始信息块。

如果代码是 最大距离可分（MDS），那么原始 k 个信息块可以从任意 k 个编码块的子集恢复，这是一个有用的效率和健壮性保证。Reed-Solomon 码是一种流行的 MDS 码家族，其运作方式如下。记得在学校的时候你可能学过两个点唯一决定一条直线：

这是因为一条直线可以用一个包含两个系数的阶数为 1 的多项式表示：$ y = a_1 x + a_0 $

（假设目前为止这些点具有不同的 x 坐标）。实际上，这一洞察可以推广：任何阶数为 $ t - 1 $ 的多项式，与描述该多项式的系数 $ {ai}{i=0}^{t-1} $ 相对应，由该多项式经过的任意 t 个点唯一确定。换句话说：一旦你知道该多项式在 t 个不同位置的评估结果，你就可以通过首先恢复多项式然后评估它来获取它在任何其他位置的评估结果。

Reed-Solomon 码便是基于这一洞察构建的。在编码时，我们从 k 个信息块 $ {ai}{i=0}^{k-1} $ 开始，构造关联多项式 $ f(X) = \sum_{i=0}^{k-1} a_i X^i $

，并在 n 个不同的 x 坐标处对其进行评估，以获取编码块。由于上述洞察，这些编码块中的任何 k 个都能唯一恢复阶数为 k-1 的多项式，通过读取系数来获取原始信息块。瞧！

回到我们的数据可用性问题：我们现在要求区块生产者将文件切成 k 个块，使用一个比如说速率为 $ R = 1/2 $ 的 Reed-Solomon 码进行编码，并将 n = 2k 个编码块写入公告板。假设目前为止区块生产者至少在编码方面诚实，我们稍后将看到如何使这一假设得以兑现。再次考虑这两种情况：生产者要么诚实并写下所有的块，或者生产者行为不当，想要让文件不可用。请记住，我们可以从 2k 个编码块中恢复原始文件中的任何 k 个。因此，为了使文件不可用，区块生产者最多能写下 $ k - 1 $ 个块。换句话说，现在至少需要有 k + 1，即超过一半的 2k 个编码块会丢失！

但现在，这两种情况，即完整写入的公告板和半空的公告板，很容易区分：你可以在少数随机抽样的位置检查公告板，若每个抽样位置都有相应的块，则认为文件可用；若任何抽样位置为空，则认为文件不可用。注意，如果文件不可用，因此公告板中（超过）一半的内容为空，你错误地认为文件可用的概率是 $ < 2^{-r} $，即在 r 上是指数级的小。

（实践）挑战

这在给定的“黑暗房间中的公告板”模型中简单明了。让我们考虑这个模型：组成部分代表什么？我们可以在真正的计算机系统中实现它们吗，如何实现？

事实上，为了帮助识别理论和实践之间的差距，我们使用“奇怪”的“黑暗房间中的公告板”模型来解释问题和解决方案，其隐喻与真实计算系统几乎没有相似之处。这是为了促使你思考真实和模型世界的某些方面如何对应，以及它们如何可能（不）实现。如果你留有模型中的部分尚未能够翻译成计算机/网络/协议等效的内容，你会知道还有待完成的事情——这可能是你理解上的差距，或者开放的研究问题！ ;)

以下是一些挑战的非详尽集合，其中一些有社区多年来找到合理答案，而其他则仍然是开放研究问题。

挑战 A：如何确保公告板上的块实际上是由提议者写的？ 想想在网络中经过的采样块的修改。这是区块生产者在离开时可以传递给采样节点的小块信息。当区块生产者离开时，采样节点进入黑暗室时，这一小块信息起到了作用。在实践中，这实现为一个 绑定向量承诺（想想 Merkle 树）到写入公告板的原始内容，它作为区块头的一部分共享。基于该承诺，区块生产者可以在公告板上留下每个编码块的证明，显示这些块确实是由区块生产者写的。这些块在传输中无法被第三方更改，因为承诺方案不允许伪造修改块的有效证明。注意，这本身并不阻止区块生产者在公告板上写入无效/不一致的块，我们接下来会讨论这一点。

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

• 欺诈证明。 该方法依赖于一些采样节点足够强大，以至于对如此多的块进行采样，从而能够发现编码的一致性，并发出 无效编码欺诈证明，以标记有问题的文件为不可用。对此类工作的目标是最小化节点要检查（并作为欺诈证明转发）以检测欺诈的块数（参见 最初的 Al-Bassam/Sonnino/Buterin 论文为此使用 2D Reed-Solomon 码）。
• 多项式承诺。 该方法使用 KZG 多项式承诺 作为包含在区块头中的绑定向量承诺来解决挑战 A。多项式承诺允许根据对未编码的 信息 块的承诺直接验证 Reed-Solomon 编码 块，因此无无效编码的余地。可以将其视为：向量承诺和 Reed-Solomon 编码在多项式承诺中是不可分离的。
• 有效性证明。 可以使用一个密码证明系统来证明向量承诺承诺的编码块的正确擦除编码。这种方法是一个良好的教学“心理模型”，并在擦除编码的选择上是通用的，但在相当长的时间内不太实际，效率低下。

挑战 C：“公告板”是什么？“在哪里”？提议者如何“写入”公告板？ 在我们讨论“公告板”是什么以及“在哪里”，提议者如何将内容写入公告板，以及验证者如何从中“读取”/“采样”之前，让我们回顾两种基本点对点网络原语的显著缺陷：

• 低度发布-订阅的泛洪式 gossip 网络，例如 GossipSub，其中通信组织为不同的“广播组”（“主题”），参与者可以加入（“订阅”）并发送消息（“发布”）：
  • 在任意（“拜占庭”）对手行为下并不安全（例如，侵犯攻击、Sybil 攻击、对节点发现的攻击）
  • 常见变种甚至没有提供 Sybil 抵抗机制
  • 参与者的组成员身份的隐私通常得不到保证（实际上，组成员身份通常会通知对等方，以避免他们转发不需要的主题的网络流量）
  • 如果每个主题都有少数订阅者，那么通信的可靠性往往会下降（因为订阅特定主题的节点子图可能无法连接，从而导致泛洪失败）
• 分布式哈希表（DHT），例如 Kademlia，其中每个参与者存储哈希表中存储的一部分整体数据，参与者可以快速确定存储特定信息的节点的短路径：
  • 也不是拜占庭容错的（例如，诚实参与者请求的不当路由、网络形成/维护的攻击）
  • 实际上，DHT 在对抗性行为的弹性方面比 gossip 协议差得多：gossip 协议“仅仅”要求诚实节点所形成的子图（及诚实节点之间的边）是连通的，从而信息可以从任何诚实节点到达所有诚实节点。而在 DHT 中，信息是沿着路径进行特定路由的，并且每当查询到达路径上的对抗节点时可能会失败。
  • 同样没有提供 Sybil 抵抗机制
  • 存储或请求哪个参与者片段的信息（以避免其他参与者的好奇目光）并不保证隐私

考虑到这一点，我们可以回到如何实现公告板及其读写操作的核心问题上。编码块存储在哪里？它们如何到达那里？当前存在三种突出的考虑方法：

• GOSSIP：通过 gossip 网络分散编码块。 例如，每个编码块都可以有一个主题，负责存储某个块的节点可以订阅相应的主题。
• DHT：将编码块上传到 DHT。 然后 DHT 可以“自动”将每个参与者分配给他们应存储的块。
• REPLICATE：从附近的副本进行采样。 某些节点存储完整（或部分）数据的副本，并为采样节点提供块请求服务。

这些方法面临的挑战包括：

• 如何确保“公告板上总有足够的空间”在开始时（即每个参与者都已订阅 GOSSIP 中的每个主题，或每个节点可以存储其需存储的所有块），以及所有公告板的部分在节点更替时保持在线？（理想情况下，为确保可扩展性，我们甚至希望存储被高效利用，即诚实节点存储的内容之间不应有太多冗余。）这在一个真正不受许可的系统中尤其棘手，因为节点不断加入和离开，且无法提供 Sybil 抵抗机制，因此大多数节点可以是对抗性的，并能够瞬间消失。幸运的是，在区块链环境中，通常存在某种 Sybil 抵抗机制（例如 PoS），可用于建立声誉或甚至削减，但关于如何利用 Sybil 抵抗机制在对等网络层上确保安全仍有许多细节待确定。
• 扩展前一点，由于网络支撑共识，因此被视为应具有拜占庭容错（BFT）系统的基石，因此网络层本身应该是 BFT——但如前所述，流行的 gossip 或 DHT 协议如 GossipSub 或 Kademlia 并非如此。(即使 REPLICATE 也可能面临此挑战，因为 DHT 可能仍在网络堆栈的其他部分的使用，例如用于节点发现；但此刻 DHT 面临的挑战成为网络层的一般关切，而不是特定于数据可用性采样。)
• 最后，有些人认为，从长远来看，节点所应存储或转发的区块不能超过相对较小的部分，否则可扩展性和支持相对“弱”参与者（例如去中心化）的可能性就受限。这与 REPLICATE 相对立。对于 GOSSIP，这需要大量的广播组（“主题”），每个主题下都有少量的订阅者，在这种情况下，gossip 协议的可靠性往往会下降。无论如何，以上方法确实额外带来开销，例如在为其他节点转发块时的带宽费用，这必须不超过单个节点的预算。

挑战 D：“如何”实现随机采样？ 这个问题有两个方面：如何在网络中找到并传输所需的块（即，如何从公告板“读取”），以及如何确保采样与对手保持“随机”，即对手区块生产者无法（过多）适应性改变其策略，具体取决于谁查询了哪些块。

• 显然，直接向区块生产者采样并不是可行的选择，因为这将对区块生产者要求极高的带宽，并可能导致拒绝服务矢量，如果区块生产者的网络地址被每个人知道的话。（某些涉及从区块生产者提取的混合构造可以从 DHT 和 REPLICATE 的角度考虑。）
• 另一种方法是通过以上提到的方法（GOSSIP 或 DHT）在“群体”中采样。当块通过 GOSSIP 或 DHT 传播后，DHT 可能能够方便查询采样请求并返回随机采样的块——但这带来了前面讨论的挑战，尤其是缺乏 BFT 和隐私。
• 另外，在 GOSSIP 下，每个节点可以订阅其希望采样的块对应的主题，但面临上述挑战：除了缺乏 BFT 和隐私，众多主题每个只少量的订阅者会导致通信不可靠。
• REPLICATE 提供了一种折衷方案，在该方案中，块是从完整数据的副本中采样的，副本在网络对等体之间被识别。

请注意，上述问题仅解决了采样（从公告板 现在 的“读取”），而未解决“在未来的任何时间从公告板读取”的问题。具体而言，GOSSIP 实际上实现了一个 短暂的 公告板（只能在其内容被写入/传播时读取/采样），而 DHT 实现了一个 永久的 公告板（也可以在之后的时间进行读取/采样）。通常，所需的是一个永久公告板（其持久性要求从“天”到“永远”不等，具体取决于设计的确切情况），为此 GOSSIP 必须与 DHT 结合使用，以便路由块，但由此面临前面讨论的挑战。REPLICATE 则立即实现一个永久公告板。

下表显示了常见点对点协议如何实现模型中的功能。具体而言，面向 gossip 的方法有两个变体，一个使用 gossip 来采样块，另一个使用 DHT 来采样块，而在这两种情况下，“块被写到公告板”通过 gossip 处理，“在稍后时刻从公告板读取”则使用 DHT。相反，DHT 导向的方法完全依赖于 DHT 来处理所有涉及的操作。在基于副本的协议中，每个节点从附近的完整副本读取/采样块，使用请求/响应协议。它有效地使用 gossip 来初步分发块，尽管两个对等体之间的 gossip 技术上也可能通过请求/响应协议实现。

此外，在所有上述技术中，“谁采样什么”至少部分会泄漏给对手，从而使对手能够通过自身的行为适应性地削弱/促进某些节点采样的块传播，因此欺骗某些节点相信区块（不可）用。尽管 早期的工作表明，只有少数节点可能被欺骗，但这并不理想。或者说 早期的工作假设匿名的网络通信，这种想法在实践中至少带来了相当大的性能损失，甚至直接变得不切实际。

挑战 E：如何“修复”公告板的内容？ 也就是说，如果一个编码块丢失（例如，因为存储该块的节点已下线；如何检测这一点？），如何恢复？天真的修复涉及解码和重新编码，因此对通信和计算造成了相当大的负担，特别是对于常见的 Reed-Solomon 纠错码。谁承担这一负担？他们如何获得补偿？如何避免恶意区块生产者通过保留一些编码块来给采样节点造成困扰，从而迫使节点为昂贵的修复支出资源？那分布式修复机制呢？如何检索必需的块以进行修复，回到关于“在未来”从公告板读取的前一点。

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

另一个模型

为完整起见，我们简要提到一个稍微不同的模型，在该模型中，DAS 能够实现稍微不同的保证。即使没有匿名和可靠的网络，对手也只能欺骗一定数量的诚实节点，让他们相信不可用的文件是可用的。否则，它就必须释放如此多的块，以至于在所有诚实节点获取的块的并集中可以恢复文件。这种模型的优势在于网络所需的属性更易实现（特别是在对手颠覆对等网络时）。缺点是无法为个别用户提供具体保证（你可能正好位于被欺骗的少数人中！），并且仍然不清楚如何收集所有诚实节点获得的样本并恢复文件（特别是在对手颠覆对等网络时）。

未来研究与发展方向

基于本文中提出的观察和论点，我们认为以下将是未来研究和发展的几个有趣方向：

• 看起来某种 Sybil 抵抗机制对于保护网络层是必要的（目前大概地说，网络协议经常隐式依赖于 IP 地址的稀缺性，具体参见 GossipSub v1.1 的对等评分）。方便的是，共识层正好提供了这一点，例如，以权益证明的形式。因此，将共识层的 Sybil 抵抗机制重用到网络层似乎是自然的，例如，从验证器集中在 gossip 协议中随机取样自己的对等体（从而“继承”共识的诚实多数假设的力量）。尽管这可能不会立即保护那些不参与活跃共识的节点的网络，但它可以帮助在共识节点之间建立安全的“主干”（从而增强共识的安全性），并随后或许成为为每个人实现更好安全的踏脚石。在这条道路上的逻辑下一步将是仔细分析共识与这样共享的 Sybil 抵抗机制间的相互作用（这是近期朝这一方向迈出的第一步）。
• 改善 gossip 和 DHT 协议：（参见 这项调查）
  • 拜占庭容错（BFT），特别是使用通常在共识层找到的 Sybil 抵抗机制
  • 效率（特别是对于 BFT 变体，迄今为止具有相当大的开销和/或低抗敌弹性）
  • 隐私保证（改善保障，更好的效率/更低的额外开销）
• 修复机制：
  • 以分布式方式实现修复（带有局部性的纠错码？）
  • 研究和设计相关激励机制

如果你在上述任何方向上工作（或有兴趣工作），我非常希望听到你的消息！你可以通过-twitter 联系我： @jneu_net。

• 原文链接： paradigm.xyz/2022/08/das...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～