a16z：關於數據可用性抽樣和 danksharding 的概述及改進建議
發表於 2023-04-28 15:33 作者： Defi之道
原文：A16z
編譯：GWEI Research
Danksharding 是一種用於擴展未來版本以太坊鏈上數據量的方法。這次升級的目標是確保鏈上的數據在首次發布時就能被歸檔方訪問。它通過一種叫做數據可用性採樣（簡稱 DAS）的技術來實現這一目標。
在這篇文章中，我們將研究 Danksharding 中的數據可用性是如何工作的，並對底層技術提出一些修改建議。特別地，我們探討了一種可能改進數據恢復的小改動：當前的方案需要 75% 的份額來恢復一個區塊，而這項修改可能將此界限降低到 25%。
Protodanksharding
Danksharding 計劃在 Protodanksharding（EIP-4844）之後推出。Protodanksharding 將通過引入一種名爲“攜帶數據塊交易”的新交易類型，使客戶端能夠將更多數據寫入區塊鏈。最初，這種新交易類型將攜帶多達四個數據塊，每個數據塊最大爲 128 KB（每個 32 字節的 4096 個字段元素），每個區塊可添加多達 512 KB 的額外數據（平均目標爲 256 KB），而目前以太坊的區塊大小平均爲 100 KB。
這些數據塊將被處理得不同：
（一）它們只會被存儲一段有限的時間，比如 30-60 天；
（二）盡管這些數據是交易數據的一部分，但智能合約無法直接訪問這些數據。相反，智能合約只能訪問到數據塊數據的一個簡短承諾，稱爲 DATAHASH。驗證者承擔的額外負擔似乎是可以接受的：驗證者目前存儲不到 100 GB 的數據以維護區塊鏈的狀態。在 protodanksharding 之後，他們將不得不額外存儲 50-100 GB 的數據。
緊接着將推出 Danksharding。它將通過增加每個區塊的數據塊數量上限，將客戶端可用的數據提高 60 倍。區塊將從每個區塊 0.5 MB 增長到 30 MB。但是，因爲驗證者不能被迫存儲 60 倍的數據，數據將在它們之間分散，使得每個驗證者只存儲一小部分數據。然而，他們可以通過數據可用性採樣（DAS）協議就他們是否共同存儲所有數據達成共識。
這些數據塊的定價將通過類似於 EIP-1559 的機制進行，並且將以每字節約 1 個數據-gas 爲目標。當前最便宜的替代品 Calldata 的價格爲每字節 16 gas。但由於有兩個不同的費用市場，這些費用無法直接比較。Roll-up 客戶端將從這些升級中受益，因爲目前超過 90% 的客戶端費用用於支付以太坊數據費。
其他項目，如 Celestia 和 EigenLayer，也採用 DAS 技術來增加可用的數據空間。這些設計比完全分片的以太坊網絡要簡單得多。
數據可用性採樣的目標
我們描述這個方案，假設採用了提議者-構建者分離（PBS）設計：
客戶端將其攜帶數據塊的交易提交給區塊構建者。
區塊構建者通過選擇 N 個客戶端數據塊來形成一個區塊 B。數據塊編號爲 i，附帶一個由發送它的客戶端籤名的簡短承諾 Ci。讓 C =（C1，...，CN）是區塊 B 中所有 N 個籤名承諾的列表。
區塊構建者將他們提議的區塊提交給當前的區塊提議者（驗證者之一）。區塊提議者選擇其中一個區塊並將其原樣發布到網絡上。
挑战在於確保稍後可以重建區塊B。爲此，構建者將區塊在 V 個驗證者的大型網絡中進行復制。可以要求每個驗證者都存儲整個區塊，但這被認爲太昂貴。相反，區塊構建者：
使用糾刪碼將區塊B編碼成更大的區塊E；
將區塊E分成V個重疊的片段P1，...，PV；
將一對（Pi，C）發送給編號爲i的驗證者。
每個驗證者檢查它接收到的片段Pi是否與籤名承諾列表C一致。區塊構建者爲驗證者提供證明以方便這些檢查。
有了這個設置，數據可用性採樣方案有兩個協議：
採樣協議在採樣驗證者和驗證者集之間運行。採樣驗證者將列表C作爲輸入，並從驗證者集合中隨機請求區塊E的元素。如果採樣驗證者收到了所有請求的元素，並且都與C一致，它將輸出成功。
重構協議在重構代理和驗證者集之間運行。重構代理將C作爲輸入，從驗證者集請求區塊E的元素。一旦收集到超過75%的元素，且所有元素都有效，重構代理計算並輸出區塊B。 （我們在下面討論了一種可能減少重建所需元素數量的方法。）
要求是，如果採樣驗證者輸出成功，那么只要輸入超過四分之三的元素，重構代理將輸出區塊B。只要提供足夠的元素，即使提供的元素是對抗性選擇的，重構也應該成功。
總之，以下各方參與到Danksharding中：
客戶端：將數據塊（可以是交易或捆綁包）發送給構建者。
構建者：創建區塊並將此區塊的片段發送給驗證者。
區塊提議者（驗證者之一）：將區塊發布到網絡。
採樣驗證者（任何一個驗證者）：運行採樣協議，如果協議輸出成功，則對區塊頭進行籤名。
重構代理：在需要時與整個驗證者集合進行交互以重構先前發布的區塊。如果驗證者回應超過四分之三的有效元素，重構將成功。
糾刪編碼和多項式承諾
接下來我們解釋該方案的兩個構建模塊：糾刪編碼和多項式承諾。
構建模塊#1：糾刪編碼
糾刪編碼可以追溯到20世紀60年代，它的產生是爲了滿足在損耗信道上傳輸信息的需求。在danksharding中，它被用來防止驗證者丟失數據片段。該技術將數據從N個元素擴展到M個元素（M > N），以便可以從擴展數據的任何完整的N個元素中重建原始數據。想象一下，將N個元素（原始數據）編碼成M = 2N個元素，並將一個編碼元素分給2N個驗證者。如果大多數驗證者都是誠實的，他們就可以共同重建原始數據。這種技術可以防止任何一半驗證者的崩潰故障。通過在下一節中討論的多項式承諾，可以擴展以防止一半驗證者的拜佔庭行爲。
以下是擴展的詳細過程。要將數據從N個字段元素d1、d2、...、dN ∈ ?p擴展到M個編碼元素e1、e2、...、eM ∈ ?p，我們對滿足p(i) = di（對於i = 1、...、N）的唯一N - 1次多項式p(x)進行插值。然後在M個點上評估多項式：ei = (i,p(i))，對於i = 1，...，M。使用拉格朗日插值從M個編碼元素中的任何N個元素重建原始多項式p(x)。這種擴展方法稱爲Reed-Solomon編碼或低次多項式擴展。
構建模塊#2：多項式承諾
多項式承諾是DAS方案的一個構建模塊。它允許方案做兩件事：
使用短承諾字符串C，承諾一個?p[X]中的有界度D的單變量多項式p。
在給定點x ∈ ?p處打开已承諾的多項式。
更准確地說，給定x,y ∈ ?p，承諾者可以創建一個簡短的證明π，證明已承諾的多項式p滿足p(x) = y，且其次數最多爲D。證明π針對承諾字符串C和值x、y進行驗證。這個π被稱爲評估證明。
安全性保證承諾與多項式綁定，且敵手不能創建虛假證明。
這裏可以使用一些實用的多項式承諾方案。Danksharding使用KZG承諾方案，該方案需要一個可信設置儀式來生成公共參數（稱爲SRS），但具有常數大小的承諾和常數大小的評估證明。KZG承諾具有以下幾個特點，使其特別適合danksharding：
承諾是同態的：如果C1是對p1的承諾，C2是對p2的承諾，那么C1 + C2是對p1 + p2的承諾；
承諾是唯一的：如果兩個人獨立計算對多項式p的承諾，他們會得到相同的承諾；
評估證明是同態的：對於給定的x，如果π1是一個證明，證明p1(x) = y1，π2是一個證明，證明p2(x) = y2，那么π1 + π2就是一個證明，證明（p1 + p2)(x) = y1 + y2。
現在我們可以解釋客戶端如何承諾其數據塊。首先，客戶端將數據塊解釋爲m個字段元素d1，...，dm ∈ ?p的向量，其中m ≤ 4096。接下來，它插入一個單變量多項式p ∈ ?p[X]，其次數最多爲m - 1，滿足p(i) = di，對於i = 1，...，m。（技術上說，danksharding使用1、ω、ω2，...、ωm-1 ∈ ?p作爲評估點，其中ω ∈ ?p是m次單位根，以及一個反向位排序；這是出於效率考慮，但爲了簡單起見，我們在這裏不考慮。）最後，客戶端構建多項式p的KZG多項式承諾。它對承諾進行籤名，並將承諾-籤名對發送給構建者。這個過程需要公共參數（SRS），包含4096個群元素。
數據分散
接下來，我們解釋區塊構建者如何編碼一個區塊並將其分成片段發送給驗證者。取某個256位素數p。區塊構建者執行以下操作：
輸入：一個danksharding區塊B可以包含多達256個數據塊（比protodanksharding多64倍），每個數據塊是一個?p中的4096個元素的向量。因此，我們可以將一個區塊表示爲一個256 × 4096的?p元素矩陣。這個矩陣的每一行對應一個客戶端的數據塊。請注意，每個客戶端都向構建者發送一個B的行以及該行的已籤名KZG多項式承諾。構建者收集256個已籤名的多項式承諾C0，...，C255，每行一個承諾。
步驟1：構建者插入一個雙變量多項式d(X,Y)，使得d(i,j) = B[i,j]，對於i = 0，...，255和j = 0，...，4095。這個雙變量多項式在X方向上的次數最多爲255，在Y方向上的次數最多爲4095。
步驟2：構建者使用上述糾刪編碼方法將塊在每個方向上擴展兩倍。也就是說，它通過設置E[i,j] ← d(i,j)爲i = 0，...，511和j = 0，...，8191，形成一個512 × 8192的字段元素矩陣E。下圖說明了這一點。
步驟3：構建者驗證每個已籤名的Ci是否是對一元多項式di(Y) := d(i,Y)的KZG承諾，對於所有i=0，...，255。注意多項式di(Y)是B的第i行的插值，因此必須與客戶端i提交的多項式相同。構建者拒絕所有Ci格式不正確的數據塊。
現在，構建者使用C = (C0, . . . , C255)作爲對區塊B的承諾，或更確切地說，是對雙變量多項式d(X,Y)的承諾。
讓我們證明C = (C0, . . . , C255)確實是對多項式d(X,Y)的多項式承諾。對於給定的x,y,z ∈ ?p，讓我們構造一個評估證明，使驗證者確信d(x,y) = z相對於承諾C。由於d(X,Y)中X的次數最多爲255，因此只依賴於x的常數λ0，...，λ255 ∈ ?p滿足
d(x,Y) = λ0 · d(0,Y) + . . . + λ255 · d(255,Y)。
然後，根據KZG承諾的同態性質可得
Cx := λ0 · C0 + . . . + λ255 · C255
是對一元多項式dx(Y) := d(x,Y)的KZG承諾。因此，驗證者可以從C中自行構建Cx。讓π成爲多項式dx(Y)的KZG評估證明，使驗證者確信在承諾Cx下，dx(y) = z。這個π是在點(x,y)處對d(X,Y)的所需評估證明。
這個論證表明C是對d(X,Y)的多項式承諾。值得注意的是，雖然每個客戶端獨立於其他客戶端籤名B的一行，但所有客戶端籤名的集合充當了對d(X,Y)多項式承諾的籤名。
步驟4：在這個DAS方案中，通信的最小單位是一個樣本，它是一個16元素的行向量。將512 × 8192元素的矩陣E視爲512 × 512樣本的方陣。設V爲驗證者的數量。然後，區塊構建者將矩陣E分解爲V個重疊片段P1，...，PV，其中Pi包含E中恰好兩行兩列的樣本，這些樣本是從512行和512列的樣本中隨機選擇的。因此，Pi包含2 × 512 × 16 + 2 × 8192 = 9216個?p中的字段元素。這比完整的區塊B小得多，B大約有一百萬個字段元素。以太坊的驗證者數量最少爲128（目前約爲500,000），因此存在足夠的驗證者確保整個區塊得到充分覆蓋。
步驟5：區塊構建者將三元組(Pi, C, πi)發送給驗證者i，其中πi是Pi中所有元素的評估證明列表：Pi中兩行和兩列樣本中每個單元格d(x,y)的一個證明。πi中的證明使驗證者能夠驗證Pi中的每個字段元素與承諾C一致。
在danksharding中，驗證者的數量可以大大超過區塊中的列或行的數量。因此，某些列和行可能由多個驗證者存儲。因此，danksharding使用復制和Reed-Solomon糾刪編碼確保數據可以重構。
完整區塊的重構
當重構代理需要重構整個區塊時，它擁有C，並要求驗證者集合將其片段發送給它。作爲回應，誠實的驗證者i發送(Pi, πi)。重構代理檢查πi中的开放證明，如果有效，它接受Pi中的值。因此，拜佔庭式驗證者無法發送虛假數據。然而，拜佔庭式驗證者可能拒絕發送他們的數據，不回應重構代理。
當某些數據丟失時，danksharding需要至少75%的矩陣E來重構區塊。由於驗證者僅存儲完整的行和列，最壞的情況是以下情況，即75% - ε的區塊元素已存在，但無法重構缺失的元素。
要理解爲什么在這種情況下數據無法重構，請注意存在一個非零的雙變量多項式δ(X,Y)，它在整個“存在”的區域上的取值爲零，並且在X和Y上具有所需的度限制。因此，在重構過程中，無法判斷缺失的白色區域是來自正確的多項式d(X,Y)還是多項式d(X,Y) + δ(X,Y)；兩個多項式在現有數據上一致。因此，當缺失的數據遵循這種模式（最多到行和列的排列）時，無法重構缺失的數據。請注意，如果驗證者刪除了部分數據，從而成爲“拜佔庭式”，它會刪除所有數據，包括兩行和兩列。
所以，在最壞的情況下，不到75%的區塊是不夠的。然而，當75%或更多的區塊存在時，通過簡單的貪婪算法保證重構成功。
重構算法：重構通過迭代地找到一個具有至少50%可用元素的不完整行（或列），並使用單變量插值來重構行（或列）的缺失元素。要了解爲什么這個過程最終會重構整個區塊，讓我們假設區塊仍然缺少一些元素，但我們找不到可以重構的行或列。這意味着每行和每列要么具有<50%的可用元素，要么已滿（具有100%的可用元素）。讓我們選擇任何不完整的行；它具有>50%的不可用元素，通過這些元素的列也必須具有>50%的不可用元素，這立即意味着區塊>25%的不可用，這與原始假設相矛盾。
爲了使一個區塊無法重構，對手需要攻擊至少15/16的驗證者集。在這種情況下，攻擊者會選擇要擦除的象限，並攻擊那些在該象限中至少有一個行或一個列的驗證者。
驗證者數據的本地重構
假設一個誠實的驗證者i崩潰並丟失了其數據。當它重新上线時，它希望重構其兩行和兩列Pi以及开放證明πi。Danksharding允許驗證者在不重構整個區塊的情況下執行此操作。驗證者可以從存儲相同確切點集的另一個驗證者那裏下載其數據，或者從其他驗證者那裏獲取其行（或列）的50%元素，並通過單變量插值重構剩余的行。這個過程不需要進行完整的重構。
例如，假設一個驗證者存儲了至少50%的第42列，但不到100%，它需要重構缺失的元素。也就是說，驗證者持有對(i,42) ∈ (?, ?)的所有i ∈ S的配對(E(i,42), πi)，其中S是一個集合，滿足256 ≤ |S| < 512。爲了重構缺失的配對，驗證者執行以下操作：
在?域上使用拉格朗日插值構造一個多項式p(x)，其次數爲255，使得對於所有i ∈ S，p(i) = E(i,42)。
評估多項式以獲得缺失的元素：對於所有i ∈ {0..511}\S，E(i,42) := p(i)。請注意，這些點保證位於一個255度的多項式上，因爲驗證者已經根據承諾C檢查過它們。
通過在指數上進行多項式插值，用多重取冪獲得缺失的證明：對於{0..511}\S中的所有i，計算πi := ∑j∈S πj · Λj,S(i)，其中Λj,S(i)是拉格朗日系數Λj,S(i) := ∏k∈S,k≠j(i – k)/(j – k)。
步驟3利用了KZG多項式承諾具有同態證明的事實。據我們所知，KZG是唯一具有此屬性的多項式承諾方案。
在danksharding中進行數據可用性抽樣
爲了確定擴展區塊E中是否有足夠的數據可用於重構原始區塊B，抽樣客戶端查詢E的隨機樣本。對於每個查詢，它得到一個樣本（16個元素的行向量）和一個評估證明，以根據承諾C檢查樣本。如果所有查詢都成功回答，客戶端將接受數據作爲可用。如果客戶端總共進行了Q次查詢，那么它錯誤地接受不可用的數據的概率爲(3/4)^Q，隨着查詢次數Q的增加，這個概率呈指數級下降。比率3/4對應於上一節中的75%重構閾值。
在以太坊網絡中，將由三種類型的參與者進行抽樣：(i) 無法承擔全部存儲blob數據的完整節點，(ii) 輕客戶端，以及 (iii) 驗證者本身。驗證者在投票確認區塊及其前驅之前，必須證明數據是可用的。每個時代都有固定的驗證者集，它們被隨機地分成32個委員會。每個委員會被分配到一個時代的12秒時段（每個時代有32個時段）。預計每個時段會確認一個區塊。每個驗證者都會收到每個區塊的片段（2行和2列的樣本），即使在驗證者不是證明委員會成員的區塊上也是如此。此外，每個驗證者都會對當前區塊和所有之前的區塊進行抽樣，以確保所有區塊在選擇一個區塊進行依據分叉選擇規則的證明之前都是有效的且可用的。
協議保證數據在一個32個時段的時代內，即6分鐘內可用。其他方法，如可檢索性證明或激勵機制，可以幫助確保數據在更長的時間內可用，例如，在blob數據過期之前應該保持可用的30-60天內。
一個25%重建的提案 在本節中，我們解釋如何在只有25%的數據可用的情況下實現重建（與上文中解釋的當前danksharding的75%相比）。
當可用點的分數低於75%時，貪婪的按列和按行的一元插值可能會失敗。相反，我們建議通過雙變量多項式插值直接進行重建。在這種情況下，即使E的點只有25%可用，也可以實現完全重建。然而，這需要對驗證器分配片段的方式進行一些修改。我們建議讓每個驗證器分配存儲：
一個完整的行（512個樣本），一個完整的列（512個樣本），以及 一個隨機（或僞隨機）分布在矩陣E周圍的1024個樣本的集合。 每個驗證器的總存儲需求保持不變，但現在即使少於75%的樣本可用，也可以進行重建。此外，多個驗證器存儲相同的點集，因此，如果任何驗證器需要重建其片段，它可以向存儲完全相同片段的任何其他驗證器請求。如果沒有這樣的驗證器可用，它可以進行局部或完全重建以獲取其片段。
這種混合方案在比辛特驗證器數量較少的情況下允許便宜的重建，使得E的樣本超過75%可用。在不愉快的情況下，當拜佔庭驗證器的數量變得過高時，由於樣本在矩陣E中的隨機分散，可以從只有25%的樣本中使用完全雙變量插值進行數據重建。
雙變量插值可以簡單地通過求解多項式系數上的线性方程組來實現。這種簡單方法需要構建一個220 × 220場元素的插值矩陣（32TB）。這相當大，但並非不可行。然而，還有更好的方法可以使用。（例如，參見P.J.Olver-2016的調查報告。）雖然雙變量插值的成本不菲，但它只在恢復點的分數低於75%時需要，可以作爲一種安全措施。爲了啓用此安全措施，danksharding需要稍微修改以按照上述方式將片段分配給驗證器。
帶有IPA承諾的Danksharding
前述構造的主要缺點是KZG多項式承諾方案需要可信設置。否則，該方案非常快速。然而，可信設置通常需要大量的工作和協調（我們關於鏈上KZG設置的工作可以幫助簡化未來項目的儀式）。一些其他多項式承諾方案不需要可信設置（例如Bulletproofs），盡管它們沒有用於驗證器在重建其需要存儲的數據時的效率所需的同態證明（正如Vitalik所指出的）。
然而，可以修改構造，以避免同態證明的需求並仍然具有輕量級驗證器。高層次的思路是讓區塊構建者計算區塊矩陣E的列的承諾。通過這種方法，驗證器不需要重建列證明；他們只需自己完全重建列，然後根據列承諾從頭开始重新計算證明。通過共識，驗證器將確保他們在相同的列承諾集上達成一致。
具體而言，步驟1-4與上文中解釋的danksharding相同。然而，步驟5是不同的。
步驟5：區塊構建者計算B的列的多項式承諾：將它們表示爲T =（T0，T1，...，T4095），每個Tj都是對d（X，j）的承諾（具體來說，它可以是Pedersen向量承諾，針對d（X，j）的系數向量）。接下來，它創建一個證明，證明C和T承諾了相同的矩陣，方法如下。區塊構建者選擇一個（僞）隨機點（x̂，ŷ），使用承諾的同構性來插值計算列承諾Tŷ，得到一元多項式d（X，ŷ）以及行承諾Cx̂，得到一元多項式d（x̂，Y），並創建兩個證明：πx̂ - 針對Cx̂的d（x̂，ŷ）的多項式求值證明，以及πŷ - 針對Tŷ的d（x̂，ŷ）的多項式求值證明。點（x̂，ŷ）對所有驗證器是通用的，可以從隨機信標輸出中獲得，或者用Fiat-Shamir變換生成僞隨機。然後，區塊構建者向驗證器i發送（Pi，C，T，πx̂，πŷ，d（x̂，ŷ）），其中Pi是E的兩行和兩列。在此構造中，構建者不計算任何證明。
驗證器驗證證明πx̂，πŷ，以捕獲惡意區塊構建者生成錯誤的列承諾T。然後，驗證器重新提交Pi中的兩行和兩列，並驗證它們是否與C和T中的相應元素匹配。如果Pi中的行（表示爲x）位於原始矩陣B的範圍內：x ∈ {0..255}，驗證器只需驗證承諾是否與C中的相應元素Cx匹配；但是，如果行位於擴展部分：x ∈ 256..511，驗證器首先通過C中的承諾插值以獲得Cx：
Cx := λ0 · C0 + . . . + λ255 · C255
請注意，插值是可能的，因爲IPA承諾（盡管它們的證明不是）是同態的。驗證器以類似的方式針對T驗證Pi的列，並在需要時進行插值。
在此構造中，區塊構建者無需爲驗證器計算證明。驗證器可以自己計算所有證明。然而，找出一種高效算法一次計算大量證明（類似於KZG的方式，或使用Vitalik的IPA思想）是一個有趣的研究問題。
正如我們所看到的，這種方法的主要瓶頸是對採樣客戶端的效率損失，因爲基於IPA方案的證明大小是對數的（與KZG的常數大小相反）。此外，採樣客戶端可能需要下載列承諾，除了行承諾之外，導致通信开銷。然而，我們認爲這是一個值得進一步探索的有前景的方向。
使用Merkle承諾的Danksharding Vitalik最近探討的另一種可行方法是使用Merkle承諾而不是多項式承諾來避免可信設置。Merkle承諾不是多項式承諾方案，因此與擦除編碼一起使用更具挑战性。區塊構建者將擦除編碼數據，並通過Merkle樹根對擴展數據進行承諾。主要挑战是在不下載全部數據的情況下檢測錯誤擴展的數據。欺詐證明可用於解決這個問題，但這依賴於一個客戶端能下載全部數據，檢查它是否正確擦除編碼並正確承諾，並在發現問題時通過提供欺詐證明發出警報。
或者，可以使用FRI證明來檢查Merkle樹的葉子是否接近Reed-Solomon碼字（即檢查Merkle承諾基礎數據是否正確擦除編碼）。採樣客戶端將檢查FRI證明，並通過請求它們的Merk爾證明來對足夠比例的葉子進行採樣，以確保數據可用且可以重建。
數據可用性採樣及其具體實例danksharding將降低數據存儲成本，從而實現更具可擴展性和更便宜的區塊鏈。DAS的編碼方面是一個潛在的研究豐富領域，有許多可能的探索方向。我們提出了一種可能的途徑：改進重建協議以使用較少的樣本（25％而不是75％）。另一個令人興奮的方向是探索不需要可信設置的替代承諾方案。
標題：a16z：關於數據可用性抽樣和 danksharding 的概述及改進建議
地址：https://www.coinsdeep.com/article/12874.html
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。