非常感謝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的機率"非常高"。在拜占庭環境中也應如此
