原文：Data Availability Sampling: From Basics to Open Problems —— joachimneu

译者：Evelyn｜W3.Hitchhiker

任何 layer 1 区块链的核心责任都是保证数据可用性。这一保证对于客户能够解释 layer 1 区块链本身是至关重要的，同时也是更高层应用（如rollups）的基础。为此，一种经常被讨论的技术是用于数据可用性验证的随机采样，出现于由 Mustafa Al-Bassam、Alberto Sonnino 和 Vitalik Buterin 在 2018 年的一篇论文中，并被推广。该技术是 Celestia 区块链的核心，并被提议与“Danksharding”一起纳入以太坊权益证明（PoS）中。

这篇博文的目的是解释数据可用性采样（DAS）的基本原理，它所依赖的模型，以及在实践中实施该技术时的挑战和未解决问题。我们希望这篇文章能给研究人员 "吃下一剂药丸"，吸引他们关注这个问题，并激发新的想法来解决一些悬而未决的挑战（参考最近以太坊基金会的提案请求）。

有人（如 L1 区块提议者或 L2 排序者）产生了一个数据块。他们声称已经向 "公众 "证明了该数据是可用的。你的目标是检查可用性的说法，也就是说，如果你需要，你是否真的能够获得这些数据？

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

对于到目前为止的问题表述，有一个简单的 "幼稚"测试程序，像比特币这样的早期系统也隐含地采用：只需要下载整个数据块便能进行验证。如果你成功了，你就知道它是可用的；如果你没有成功，你就认为它不可用。然而现在，我们想在不用自己下载过多数据的情况下测试数据的可用性，例如，因为数据大到我们无法处理，或者因为 "仅仅 "为了验证数据的可用性而在我们并不真正感兴趣的数据上花费大量带宽似乎十分浪费。在这一点上，我们需要一个模型来阐明只下载或保留 "部分数据 "的 "含义"。

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

在我们的模型中，在一个黑暗的房间里有一个公告板（见下面的漫画）。首先，区块生产者进入房间，并获得在公告板上写下一些信息的机会。当区块生产者退出时，它可以给你（验证者）一小段的信息（其大小与原始数据不呈线性比例）。你带着手电筒进入房间，手电筒的光束很窄，而且电池电量不足，所以你只能读取到公告板上很少的几个明显位置的文字。而你的目标是让自己相信，区块链生产者确实在公告板上留下了充足的信息，所以如果你打开灯，阅读完整的公告板，你将能够恢复文件。

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

这就是 Reed-Solomon 码发挥作用的地方。让我们简单地回顾一下这些内容。在高层次上，纠删码的工作原理是这样的：一个由 k 个信息块组成的向量被编码成一个由 n 个编码块组成的（更长的！）向量。编码的比率 R = k/n 衡量了编码所引入的冗余。随后，我们可以从编码块的某些子集中解码出原始信息块。

如果编码是最大距离可分的（MDS），那么原始的 k 个信息块可以从任何大小为 k 的编码块子集中恢复出来，这是一个有用的效率和鲁棒性保证。Reed-Solomon 码是一个流行的 MDS 编码系列，其工作原理如下。记得在学校里，你可能学过两点唯一决定一条线。

这是因为一条直线可以被描述为一个有两个系数的1次多项式：y = a1x+a0（现在我们假设各点有不同的 x 坐标）。事实上，这一见解可以被概括为：任何次数为t-1的多项式，对应于描述多项式

的一组系数

，由该多项式经过的任何 t 个点（有不同的 x 坐标）唯一决定。换句话说：一旦你知道多项式在 t 个不同位置的求值，你就可以得到它在任何其他位置的求值（首先恢复多项式，然后求值）。

Reed-Solomon 码就是根据这一观点建立的。对于编码，我们从 k 个信息块

开始，构建相关的多项式

，并在 n 个不同的 x 坐标上对其进行求值，从而得到编码的信息块。现在，由于上述见解，这些编码块中的任何 k 都允许我们唯一地恢复 k-1 次的多项式，并读出系数以获得原始信息块。Voilà!

回到我们的数据可用性问题：我们现在不再要求区块生产者在公告板上写下原始文件，而是要求它将文件切分成 k 个小块，用比率为 R=1/2 的 Reed-Solomon 码对它们进行编码，并将 n=2k 编码块写到公告板上。现在我们假设区块生产者至少诚实地遵循编码（我们将在后面看到如何解除这一假设）。再考虑一下这两种情况：要么生产者行为很诚实，写下了所有的块，要么生产者行为不端，想保持文件不可用。回顾一下，我们可以从 n=2k 个编码块中的任何 k 个来恢复原始文件。因此，为了保持文件不可用，区块生产者最多可以写入 k-1 个块。换句话说，现在至少有 k+1 个，也就是 n=2k 个编码块中的一半以上，将被丢失！

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

，即在 r 中呈指数级减小。

这是非常简单的（在给定的 "黑房间中的公告板 "模式中）。让我们思考一下这个模型。这些组件代表什么？我们能在一个真正的计算机系统中实现它们吗，如何实现？

事实上，为了帮助各位发现理论与实践之间的差距，我们用那种 "奇怪的""黑房间里的公告板 "的模型来解释问题和解决方案，其隐喻与真实的计算系统几乎没有任何相似之处。这是为了鼓励你思考真实世界和模型世界的各个方面是如何相对应的，以及它们可能（无法）是如何实现的。如果你剩下的模型碎片还不能转化为计算机/网络/协议的等价物，你就知道还有一些事情要做（这可能是你理解上的差距，或者是开放的研究问题！;)

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

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

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

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

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

• **有效性证明。**一个可以用来证明向量承诺提交的编码块是正确纠删码的加密证明系统。这种方法是一个很好的教学 "心理模型"，并且在所采用的纠删码方面是通用的，但在相当长的一段时间内可能是低效率的。

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

• 基于低量级泛洪的发布-订阅 gossip 网络，如 GossipSub，其中通信被组织成不同的 "广播组"（"主题"），参与者可以加入（"订阅"）并发送消息（"发布"）到：

  • 在任意（"拜占庭"）对抗行为（例如，日蚀攻击、Sybil 攻击、对等发现攻击）下不安全

  • 常见的变体甚至不提供抗 Sybil 抵抗机制

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

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

• 分布式哈希表（DHT），如 Kademlia，每个参与者都存储了哈希表中存储的全部数据的一部分，参与者可以快速确定通往存储特定信息的对等方的最短路径。

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

  • 事实上，DHT 在抵御对抗行为方面的表现比 gossip 协议差很多。Gossip 协议 "只 "要求由诚实节点（以及诚实节点之间的边）形成的子图是连接的，因此信息可以从任何诚实节点到达所有诚实节点。在 DHT 中，信息是专门沿着路径路由的，查询一旦到达路径上的对抗节点就可能失败。

  • 也不提供 Sybil 抵抗机制

  • 参与者存储或请求信息的隐私不被保障（不被其他参与者的好奇心所影响）。

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

• **GOSSIP：使用一个gossip网络来分散编码块。**例如，每个编码块可以有一个主题，而负责存储某个块的节点可以订阅相应的主题。

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

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

这些方法所面临的挑战是：

• 如何确保 "公告板上有足够的空间 "开始（即有足够的参与者订阅了 GOSSIP 的每个主题，或者每个节点可以存储它在 DHT 下需要存储的所有块），并确保公告板的所有部分都在随着节点的变化和时间的推移而保持在线？(理想情况下，为了确保可扩展性，我们甚至希望存储能被有效地利用，也就是说，在诚实的节点存储的内容中不应该有太多的冗余）。在一个真正的无需许可系统中，这将是特别棘手的，在这个系统中，节点来来去去，也许没有 Sybil 抵抗机制，所以大部分的节点可能是对抗性的，也可能在瞬间消失。幸运的是，在区块链背景下，通常会有一些 Sybil 抵抗机制（如 PoS），可以用来建立信誉甚至进行攻击，但如何利用 Sybil 抵抗机制来保证 P2P 网络层的安全，其中还有许多细节有待确定。

• 根据前面的观点，由于网络是共识的基础，因此也是拜占庭容错（BFT）系统的基石，网络层本身最好是BFT —— 但正如前面所见，流行的 gossip 或 DHT 协议（如 GossipSub 或 Kademlia）并非如此。 (即使是 REPLICATE 也可能面临这种挑战，因为 DHT 可能仍然用于网络堆栈的其他部分，例如，用于对等节点的发现；但在这一点上，DHT 的挑战成为一般网络层的关注点，而不是专门针对数据可用性采样。）

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

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

• 当然，直接从区块生产者那里采样并不是一个可行的选择，因为这需要区块生产者的高带宽，而且如果区块生产者的网络地址被所有人知道的话，还会产生相关的拒绝服务向量。(可以通过 DHT 和 REPLICATE 的视角观察到一些涉及到从区块生产者那里提取的混合结构）。

• 另一种方法是在使用上述方法之一（GOSSIP 或 DHT）分散大块后，从 "swarm "中采样。具体来说：

  • 在使用 GOSSIP 或 DHT 分散块之后，DHT 在路由采样请求和随机采样块时会很方便，但这也带来了上面讨论的挑战，最明显的是缺乏BFT和隐私。

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

• 在 "从区块生产者中采样 "和 "从 swarm 中采样 "之间，可以用 REPLICATE 进行折衷，即从数据的完整副本中采样，而副本是在网络对等方中进行识别。

请注意，上面只解决了采样（现在从公告板上 "读"），而没有解决在未来任何时候从公告板上 "读"的问题。具体来说，GOSSIP 本质上实现了一个临时的公告板（只能在其内容被写入/散布时被读取/采样），而 DHT 实现了一个永久的公告板（也可以在很久之后被读取/采样）。通常情况下，人们希望有一个永久的公告板（永久的要求从 "天 "到 "永远 "不等，取决于具体的设计），为此，GOSSIP 必须使用 DHT 来路由块，这就带来了上述的挑战。REPLICATE 马上就实现了一个永久性的公告板。

下表说明了通常建议使用哪些 P2P 协议来实现模型的不同功能。具体来说，面向 gossip 的方法有两种变体，一种是使用 gossip 对块进行采样，另一种是使用 DHT 对块进行采样，而在这两种情况下，先使用 gossip 将块写在公告板上，然后再使用 DHT 从公告板上 "读取"。相比之下，面向 DHT 的方法完全依靠 DHT 来完成所有相关的操作。在面向 replication 的方法中，每个节点使用请求/响应协议，从附近的完整副本中读取/采样块。尽管两个对等方之间的 gossipping 在技术上可能是通过请求/响应协议实现的，但它有效地使用了gossip 来进行块的初始传播。

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

**挑战 E：如何 "修复 "公告板的内容？**也就是说，如果一个编码块丢失了（例如因为存储该块的节点离线了，这是如何发现的？），如何修复它？简单的修复涉及到解码和重新编码，因此带来了相当大的通信和计算负担，特别是对于常见的 Reed-Solomon 纠删码。谁来承担这一重任？他们是如何得到补偿的？如何避免一个恶意的区块生产者通过保留几个编码块来破坏采样节点，并迫使节点在昂贵的修复上花费资源？分布式修复方案呢？甚至如何检索修复所需的块？这又回到了之前关于未来从公告板 "读取 "的观点。

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

为了完整起见，我们简要地提到一个稍微不同的模型，DAS 实现了一个稍微不同的保证。即使没有匿名和可靠的网络，攻击者最多可以欺骗一定数量的诚实节点，使其相信一个不可用的文件是可用的。否则，它将不得不释放如此多的块，以便从诚实节点获得的所有块的联合中可以恢复该文件。这种模式的优点是，从网络中要求的属性更容易实现（特别是在 P2P 网络被攻击者破坏的情况下）。缺点是对个人用户没有具体的保证（你可能是少数被骗的人之一！），而且仍然不清楚如何收集所有由诚实节点获得的样本并恢复文件（特别是当 P2P 网络被对手攻击时）。

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

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

• 改进的 gossip 和 DHT 协议：（参考本调查报告）

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

  • 效率（特别是对于 BFT 变体，到目前为止，这些变体有相当大的成本和/或较低的对抗复原能力）。

  • 隐私保证（改进的保证，以及更好的效率/更低的成本）。

• 修复机制：

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

  • 研究和设计相关的激励机制