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