非常感谢Alex、Csaba、Dmitry、Mikhail和Potuz进行富有成果的讨论和文章审阅
摘要
以太坊目前的数据可用性（DAS）方法基于里德-所罗门纠错编码和KZG承诺。这个新方案（在此处描述以太坊中更快的区块/数据块传播，由@potuz提出）引入了另一对方法：RLNC（随机线性网络编码）纠错编码和佩德森承诺。它具有一些很好的特性，可以用于考虑替代的数据可用性方法。
本文概述的协议主要勾勒了基于RLNC的数据可用性设计可能是什么样子。这里使用的概念尚未充分验证，更不用说正式证明了。无论如何，如果这些概念被证明是正确的，该算法可以作为原型设计的基础。如果其中一些被证明是不正确的，我们可以调整算法或考虑调整或替换它们。
本文的推理在几个点上与@Csaba最近的帖子重叠：使用FullDASv2加速数据块扩展（使用getBlobs、内存池编码，可能还有RLC）。
_要探索完整的背景，包括推理和讨论评论，请参见本文的扩展版本：https://hackmd.io/@nashatyrev/Bku-ELAA1e_
让我们概述一些取决于 S 和 |\mathbb{C}_q|（系数大小）的数字，假设原始数据大小为 32Mb：| SS | sizeOf(C)（比特） | NN | 向量大小（千字节） | 承诺大小（千字节） | 消息系数大小（千字节） | 消息开销（%%） |
|---|---|---|---|---|---|---|
| 8 | 1 | 64 | 512 | 2 | 0.0625 | 0.01% |
| 8 | 8 | 64 | 512 | 2 | 0.5 | 0.10% |
| 8 | 256 | 64 | 512 | 2 | 16 | 3.13% |
| 16 | 1 | 256 | 128 | 8 | 0.5 | 0.39% |
| 16 | 8 | 256 | 128 | 8 | 4 | 3.13% |
| 16 | 256 | 256 | 128 | 8 | 128 | 100.00% |
| 32 | 1 | 1024 | 32 | 32 | 4 | 12.50% |
| 32 | 8 | 1024 | 32 | 32 | 32 | 100.00% |
| 32 | 256 | 1024 | 32 | 32 | 1024 | 3200.00% |
| 64 | 1 | 4096 | 8 | 128 | 32 | 400.00% |
| 64 | 8 | 4096 | 8 | 128 | 256 | 3200.00% |
| 64 | 256 | 4096 | 8 | 128 | 8192 | 102400.00% |
根据这些数字，基本上不可能在S \ge 64的情况下使用这种算法。如果没有使用小系数（1或8比特）的选项，那么由于系数大小开销，S = 8是有意义的最大分片因子。（在S = 16时，最小节点下载吞吐量将与S = 8相同。）
优点和缺点
优点
- 要传播、保管和采样的总数据大小为原始数据大小的x1（加上系数开销，如果可用小系数则可能很小）（与PeerDAS的x2和FullDAS的x4相比）
- 我们可能有高达32（或可能更大，通过对算法进行一些其他修改）的"分片因子"S，这意味着每个节点只需下载和保管原始数据大小的1/S。（与当前PeerDAS方法中的1/8相比：从64个原始数据中选择8列）
- 只要有S个常规诚实节点成功执行采样，数据就可用且可以恢复
- 采样可以由S个常规节点执行（与当前需要来自不同DAS子网的各种对等节点的DAS采样相比）
- "你采样的就是你保管和服务的"（类似PeerDAS子网采样，但不同于完全分片对等节点采样）。关于对等节点采样方法的担忧在此处描述
- 由于没有列切片，单独的blob可能跨越几个原始数据向量，因此采样过程可能有效地受益于EL blob事务池（又称
engine_getBlobs()） - 没有可能受到女巫攻击的较小子网
- 由于节点需要来自任何对等节点的S条消息，并使用RLNC编码，传输层上的数据重复可能较低
- RLNC + Pedersen可能比RS + KZG消耗更少的资源
缺点
- 承诺和证明大小随分片系数S呈二次增长。
- 如果无法使用较小的系数（未被证明安全），则仅S=8是可行的。
- 仍需估计传播延迟，因为节点可能只在完成自身采样后才传播数据
- 在最佳情况下，采样的最小对等节点数为32（与PeerDAS中的8个相比）
待证明的陈述
上述算法依赖于一些[尚未明确]的陈述，这些陈述目前需要证明：
- 超级节点返回的具有请求的随机系数的有效线性组合，证明响应节点可以访问完整数据（足以恢复的向量）。这个陈述看起来不太难证明
- 如果全节点声称拥有形成系数子空间的基向量，那么如果节点请求来自此子空间的随机向量并获得有效的数据向量，则证明响应节点确实拥有所声称子空间的基向量。证明可以是陈述（1）的泛化
- 在\mathbb{F}_p上的椭圆曲线，其子域\mathbb{C}_2是有意义且安全的。（**根据最新讨论，这似乎并不正确**）
- 用于零RRT采样的RREF基本形式的技巧实际上是有效的。
（这个示例可以提供关于此陈述有效性的一些直觉） - 所描述的算法在完整的
N维空间中均匀分布基向量。存在一个相当小的E（大约1-3），使得任何随机选择的S + E个节点的基向量的秩为N的概率"非常高"。在拜占庭环境中也应如此
