撰文： 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 提供了漂亮的插圖。
