鲁棒分布式数组 - 数据可用性采样的可能安全网络

作者： 丹克拉德·费斯特，戈特弗里德·赫罗尔德，马克·西姆金，本尼迪克特·瓦格纳

数据可用性采样（DAS）是以太坊路线图的核心组件。它使客户端能够验证数据可用性，而无需任何单一客户端下载整个数据集。DAS通过让客户端从点对点网络中随机检索冗余编码数据的部分来运作。虽然DAS的密码学和编码方面最近经历了正式分析，但点对点网络层仍未得到充分探索，缺乏安全定义和高效、可证明安全的构造。

在我们的工作中，我们通过引入一种可作为DAS网络层的新型分布式数据结构来解决这一空白，我们称之为鲁棒分布式数组。
我们的工作包括两个部分：

1. 我们给出了一个形式化模型，严格定义了DAS的网络解决方案在安全性方面应该实现的目标。我们将由此产生的分布式数据结构称为鲁棒分布式数组。
2. 我们提出了一个简单且高效的构造，并正式证明它满足我们的定义。我们的构造在无需许可的网络中运行，即使大多数参与者是恶意的，也能保持安全。具体而言，我们仅假设在足够大的时间间隔内有足够多的绝对数量的诚实方在线，而不管网络中有多少恶意方。特别是，我们避免了任何诚实多数假设。容忍不诚实多数很重要，因为DAS是以太坊安全性的关键组件，即使在不诚实多数的情况下也应该保持。我们在论文的引言中对此进行了更详细的解释。

论文包含形式化定义（第3节）以及构造及其分析（第4节）。

直观地说，我们的安全概念（定义4）表示，对于大多数索引ii，如果一方在某个时间将数据xx存储在位置ii，并在最小延迟后另一方尝试检索存储在位置ii的数据，这确实会返回xx。

这种安全概念意味着相应的非分布式数据结构简单地是一个数组，因此得名。我们的构造在不要求每个参与者存储所有数据的情况下实现了这一点。

关于所有细节，包括非正式概述，我们参考论文。