區塊鏈擴容的關鍵欺詐和資料可用性證明，在這篇論文中，作者們提出、實施並評估了一個完整的欺詐和資料可用性證明方案，並且根據附加的假設：網路中至少有一個誠實全節點在最大網路延遲內傳播欺詐證明，並且網路中具有最小數量的輕客戶端來共同恢復區塊，它使得輕客戶端幾乎可以得到全節點級別的安全保障。
(圖片來自：Institut Friedland)
1 倫敦大學學院
{m.albassam,a.sonnino}@cs.ucl.ac.uk
2 以太坊研究組織
摘要：輕客戶端，也被我們稱為簡單支付驗證(SPV)客戶端，這類節點只需下載區塊鏈中一小部分的資料，並使用間接的手段來驗證給定區塊鏈是有效的。通常，它們假設區塊鏈共識演算法所支援的鏈只包含有效區，並且大多數區塊生產者都是誠實的，而不是去驗證區塊資料。透過降低這類客戶端來接收由全節點生成的，表明違反協議規則的欺詐證明，並將其和概率抽樣技術相結合，以驗證區塊中所有資料實際是可用於下載的，我們可以淘汰掉多數人誠實的假設，相反地，對重播資料的最小數量誠實節點，提出了更弱的假設。欺詐和資料可用性證明，是區塊鏈鏈上擴容的關鍵(例如，透過分片技術或大區塊)，同時確保鏈上資料的可用性和有效性。
我們提出、實施並評估了一個新的欺詐證明，以及一個資料可用性證明系統。
一、引言和動機
隨著密碼貨幣和智慧合約平臺被廣泛採用，我們在實踐過程中已經看到了區塊鏈的可擴充套件性限制問題。由於比特幣交易的平均費用一度高達20美元 [19.28]，很多流行的比特幣支付服務停止接受了比特幣支付方式[26]，而以太坊流行的CryptoKitties(加密貓)[6]智慧合約一度造成以太坊網路未確認交易積壓增長了6倍[40]。由於區塊鏈鏈上空間是受到限制的，例如比特幣的區塊大小限制 [2]或以太坊的區塊gas限制[41]，使用者們就需要為交易納入區塊鏈而支付更高的交易費用。
雖然擴大鏈上容量限制將產生更高的交易吞吐量，但人們會擔心這種方式會降低區塊鏈的去中心化及安全性，因為這會導致增加完全下載和驗證區塊鏈所需的資源，從而導致更少的使用者能夠負擔得起獨立驗證區塊鏈的全節點，這就要求使用者轉而去執行輕客戶端，該客戶端假設是有遵循區塊鏈協議規則的共識演算法 [23]。
輕客戶端在正常情況下的執行是良好的，但當多數人的共識(例如礦工或區塊生產者)是不誠實的時候，輕客戶端的安全保證就是較弱的。例如，儘管在比特幣或以太坊網路中的多數非誠實節點，目前只能審查、反轉或重新排序交易，如果所有的客戶端都使用的是輕節點，大多數共識將能夠相互勾結，產生包含憑空創造貨幣的交易區塊，而輕節點將無法檢測到這一點。另一方面，全節點將立即拒絕那些無效區塊。
因此，各種集中於鏈外擴容的技術解決方案嘗試在興起，例如支付通道[31]，其中參與者在鏈外簽署交易，並最終在鏈上進行餘額結算。支付通道也已擴充套件到了狀態通道 [25]。然而，由於開通和結算通道涉及到了鏈上交易，因此鏈上擴容對於支付和狀態通道的大規模採用而言，仍然是必要的[3].
在這篇論文中，我們透過使輕客戶端能夠接收和驗證來自全節點的無效區塊欺詐證明，以降低鏈上擴容與安全性之間的權衡，這樣它們也可以拒絕它們，前提是，假設至少有一個誠實全節點願意生成在最大網路延遲的情況下傳播的欺詐證明。
我們還設計了一個資料可用性證明系統，這是對欺詐證明的必要補充，以便輕客戶端能夠保證全節點生成欺詐證明所需的區塊資料是可用的，鑑於有少量的誠實輕客戶端要重建區塊中的丟失資料。我們對自己的總體設計進行了實施，同時評估了安全性和效率。
我們的工作還涉及了區塊鏈分片擴容方案 [1.7.20]，而在一個分片系統中，網路中不需要有節點下載並驗證所有分片的狀態，因此，我們就需要欺詐證明從惡意分片中檢測出無效區塊。
二、背景
2.1 區塊鏈模型
簡單地從字面上講，區塊鏈的資料結構是由區塊串聯成鏈組成的。每一個區塊包含兩個部分：一個區塊頭以及一個交易列表。區塊頭除了儲存其它後設資料之外，它還會儲存之前區塊的雜湊值(從而實現鏈的特性)，以及包含區塊所有交易的默克爾樹(Merkle tree)根。
區塊鏈網路擁有一種共識演算法 [3] ，以確定一旦發生分叉時，我們應該支援哪一條鏈，例如，如果使用的是工作量證明 [26]演算法，那麼累積工作最多的那條鏈會得到承認。它們還具有一組協議規則，規定鏈的哪些交易是有效的，因此包含無效交易的區塊永遠不會被共識演算法所青睞，實際上，這些無效交易區塊也應該會被拒絕。
而所謂全節點，會下載區塊鏈中的所有區塊頭及交易列表資訊，並根據一些協議規則驗證這些交易是否是有效的。
而輕客戶端只需下載區塊頭資訊，並假定交易列表中的交易是符合協議規則的。輕客戶端根據共識規則驗證區塊，而不是根據協議規則，因此其假定共識規則是誠實的。輕客戶端可以從全節點中接收Merkle證明，其中一筆特定的交易或狀態物件被包含在區塊頭中。
目前有兩種主要型別的區塊鏈交易模型：未花費交易輸出 (UTXO)模型以及帳戶模型。基於UTXO模型區塊鏈的交易(例如比特幣)，包含了對先前交易的引用，其中哪些幣是他們希望去‘花費’的。由於單筆交易可能將幣向多個地址傳送，一筆交易具有很多的‘輸出’，因此，新的交易包含了對這些特定輸出的引用。每一個輸出只能夠花費一次。
另一方面，基於帳戶模型的區塊鏈(例如以太坊)，則相對更容易使用(雖然有時在應用並行處理技術時會顯得更復雜)，因為這種模型下，每筆交易會簡單地指定從一個地址到另一個地址，而不會引用先前的交易。在以太坊中，區塊頭還包含Merkle樹根(包含狀態)，其包含了驗證下一個區塊所需要的‘當前’資訊;在以太坊當中，這包含了系統中所有帳戶和合約的平衡、程式碼及永久儲存。
2.2 默克爾樹(Merkle Tree)和稀疏默克爾樹(Sparse Merkle Tree)
默克爾樹是一種二叉樹，其中每個非葉節點(non-leaf node)透過其子節點連線的加密雜湊值標記。而默克爾樹的根，是對所有葉節點中所有條目的的一個保證。這就允許了給出一些默克爾樹根的默克爾證明，這些證明能夠表明一個葉節點是默克爾樹的一部分。
某些葉節點的默克爾證明，是由葉節點的祖節點及祖節點同胞中間節點組成的，直到樹的根，從而形成子樹，該子樹的Merkle根可以被重新計算，以驗證Merkle證明是有效的。一棵擁有n葉節點的梅克爾樹，其Merkle證明的大小和驗證時間是O(log(n))。
而所謂的稀疏默克爾樹 [12. 21] ，是指那些擁有n葉節點的默克爾樹，而其中的n是一個非常大的數字(例如，n = 2^256)，但幾乎所有的節點都具有相同的預設值(例如，0)。如果k個節點的值是非零點，那麼在默克爾樹的每個中間層，將有一個最大值k的非零值，並且所有其它值都會是該級別的相同預設值：底層為0.L1 = H(0. 0)，第一個中間層為L1 = H(0. 0)，第二個中間層為L2 = H(L1. L1) ，依此類推。
因此，儘管默克爾樹中的節點數呈指數增長，但樹的根還是可以透過O(k × log(n)) 時間進行計算的。稀疏默克爾樹允許對鍵值圖進行保證，其中的值可以在O(log(n)) 時間內進行更新、插入或刪除操作。如果構造地簡單，則特定鍵值條目的Merkle證明，就是log(n)的大小，如果中間節點的同胞節點具有預設值是不需要顯示的，那麼我們可以將其壓縮至log(k) 大小。
像瑞波和以太坊這樣的系統，目前所使用的是帕特麗夏樹(Patricia tree) [35.41]，而不是稀疏默克爾樹;我們在本文中使用稀疏默克爾樹為例，是因為它們會更簡單。
2.3 擦除碼與裡德-所羅門碼(RS 碼)
擦除碼是在位擦除(而非位錯誤)假設下工作的糾錯碼[14.30];特別是，使用者知道哪些位是必須被重建的。糾錯碼會把長度為k的訊息轉換為長度為n > k的更長的訊息，從而可以從n個符號的子集恢復原始訊息。
裡德-所羅門碼[39]具有多種應用，它是被研究最多的糾錯碼種類之一。一個RS 碼透過將長為k的訊息作為某些有限域(素數域和二元域是最常用的)元素x0.x1.…,xk−1列表來編碼資料，對多項式 P(x) 進行插值處理，其中 P(i) = xi，其中0 ≤ i < k，然後用xk,xk+1.…,xn−1來延伸這個列表，其中xi = P(i)。
這個多項式P可使用諸如拉格朗日插值(Lagrange interpolation)技術，或者諸如快速傅立葉變換法(Fast Fourier transform)這類更最佳化、更高階的技術，從這個較長列表中的任何k字元中恢復，而知道P之後，我們就可以恢復原始訊息。RS 編碼可以檢測並校正高達(n−k)/2 種錯誤，或者是錯誤和擦除的組合。
透過各種方式 [34.37.42]，RS碼已被推廣到了多維碼[13.36]。在一個d維碼中，訊息被編碼成大小為k × k × … × k的正方形或立方體或混合立方體，而一個多維多項式P (x1. x2. …, xd)是在P(i1.i2.…,in) = xi1.i2…,in處進行插入，這個多項式將擴充套件到更大的n×n×…×n正方形或立方體或超立方體。
三、假設與威脅模型
在我們提出的網路和威脅模型下，我們的欺詐證明(第四章內容)和資料可用性證明(第五章內容)是可以適用的。
3.1 準備工作
我們提出了一些原語，而在論文的其餘部分，我們將會使用到這些原語。
1、–hash(x)是一種加密安全雜湊函式，它會返回X的摘要(例如SHA-256);
2、– root(L) 會返回專案L列表的Merkle根;
3、– {e → r} 指出了Merkle證明，其中元素e是根為r的Merkle樹的成員;
4、– VerifyMerkleProof(e, {e → r}, r, n, i)是當Merkle證明有效時，它會返回“true”值，其它情況則會返回“false”值，其中n表示基礎樹中元素的總數，而i是樹中E的索引。這驗證了e是在i索引當中的，及其成員資格;
5、– {k, v → r} 指出了一個Merkle證明，其中鍵值對k, v是根為r的稀疏Merkle樹的一個成員。
3.2 區塊鏈模型
我們假設了一個通用區塊鏈體系結構，其中區塊鏈是由區塊頭H = (h0.h2.…,hn)組成的雜湊鏈組成的。每一個區塊鏈頭hi包含了Ti交易列表的Merkle根txRooti，這樣root(Ti) 就等於 txRooti 。假設一個節點從網路中下載了交易 Ni的列表，如果(i) root(Ni) = ri，並且(ii) 給出一些有效性函式 。那麼我們認為區塊頭hi是有效的。
valid(T, S) ∈ {true, false}
其中T是交易列表，而S是區塊鏈的狀態，那麼valid(Ti,Si−1)必須返回“true”值，其中Si是在Ti中所有交易之後區塊鏈的狀態。我們假設valid(T,S)需要O(n) 時間來執行，其中的n是T列表中的交易數。
在第四章第二節中，我們將解釋基於UTXO(例如比特幣)以及帳戶模型(例如以太坊)的區塊鏈如何以用這個模型來表示。
目標：我們的目的是向客戶端證明，對於給定的區塊頭hi，valid(Ti, Si−i)在少於O(n)時間及少於O(n)空間的情況下會返回“ false”值，這依靠的是儘可能少的安全假設。
3.3網路模型
我們假設了一個由兩種型別節點所組成的網路：
1、全節點。這些節點會下載並驗證整個區塊鏈。誠實的全節點會儲存和重播它們下載到其它全節點的有效區塊，並將與有效區塊相關聯的區塊頭廣播給輕客戶端。這些節點當中，有一些可能會參與共識(透過生產區塊)。
2、輕客戶端。這些節點的計算能力和網路頻寬太低，無法下載和驗證整個區塊鏈。它們從全節點那裡接收區塊頭資訊，並根據要求，Merkle證明是證明某些交易或狀態是區塊頭的一部分。
我們假設了一個網路拓撲，如圖1所示;全節點之間會互相通訊，而輕節點客戶端則會和全節點進行通訊，但輕節點之間並不會互相通訊。此外，我們假設了一最大值的的延遲 &網路，這樣的情況下，如果一個誠實節點可以連線到網路，並在時間T下載一些資料(例如一個區塊)，那麼它會保證其它誠實節點將在T‘≤T+&的時間做同樣的事。
圖片1: 網路模型 ：全節點之間會相互通訊，但輕節點只會和全節點通訊
3.4 威脅模型
我們在威脅模型中做出瞭如下假設：
1、區塊和共識。區塊頭可能會由敵對參與者建立，因此可能是無效的，並且不存在我們可依賴的誠實多數共識參與節點;
2、全節點。全節點可能是不誠實的，例如，它們可能不會中繼資訊(例如欺詐證明)，或者它們可能會中繼無效區塊。然而，我們假設至少有一個誠實全節點連線到網路(即，它是線上狀態的，它願意生成和傳播欺詐證明，並且不受日食攻擊(eclipse attack)[18])
3、輕客戶端。我們假設每個輕客戶端會連線至少一個誠實的全節點。對於資料可用性證明，我們假設最小數量的誠實輕客戶端允許區塊的重構。具體的數目取決於系統的引數，我們將在第五章第六節中進行具體分析。
四、欺詐證明
圖片2:網路級欺詐證明系統的結構概述
4.1 區塊結構
為了支援高效的欺詐證明，有必要設計一個支援欺詐證明的區塊鏈資料結構。該模型的擴充套件描述詳見第三章第二節部分，在區塊高度i的區塊頭hi包含了以下元素：
1、prevHashi ：區塊鏈中先前區塊頭的雜湊;
2、dataRooti：區塊中包含資料(例如交易)的Merkle樹根 ;
3、dataLengthi：由dataRooti所表示的葉節點的數量;
4、stateRooti ：區塊鏈狀態的稀疏Merkle樹的根(詳見第四章第二節);
5、additionalDatai：網路可能需要附加的任意資料(例如在工作量證明網路中，這可以包括隨機數和目標難度閾值);
此外，每個區塊頭blockHashi = hash(hi)的雜湊，也會由客戶端和節點儲存。
請注意，典型的區塊鏈具有包含在區塊頭中的交易Merkle根。我們將其抽象化成“資料的Merkle根”，並命名為dataRooti，正如我們將在第四章第三節內容中看到的，以及包括在區塊資料中的交易，我們還需要納入中間狀態根。
4.2 狀態根以及執行跟蹤構造(State Root and Execution Trace Construction )
為了例項化一個基於上述第三章第二節內容中描述的狀態模型的區塊鏈，我們使用了稀疏Merkle樹，並將狀態表示為key值map。我們解釋了UTXO模型和帳戶模型的區塊鏈如何可在這樣的模型上進行例項化：
1、基於UTXO模型的。map中的key是交易輸出識別符號，例如hash(hash(d)||i)，其中d是交易的資料，而i則是d中涉及的輸出的索引。每一個key的值是每個交易輸出識別符號的狀態：要麼未使用(1)或者不存在(0.預設值)。
2、基於帳戶模型。其已經有了一個key值map，其中的key是帳戶或儲存變數，而值是帳戶餘額或變數的值;
狀態將需要跟蹤所有和區塊處理相關的資料，包括例如在每次交易之後，支付給當前區塊建立者的累積交易費用。
我們在第三章第二節內容中定義了一個函式轉換的變體，稱之為rootTransition，它不需要整個狀態樹，而是隻需要交易讀取或修改所需的狀態樹的狀態根以及Merkle證明部分(我們稱之為“驗證”部分，或簡稱為w)這些Merkle證明被有效地表示為具有相同根的同一狀態樹的子樹。
rootTransition(stateRoot,t,w) ∈ {stateRoot′,err}
驗證部分w是由一組key值對及其相關在狀態樹中的稀疏Merkle證明所組成的，其中，
w={(k1.v1.{k1.v1 →stateRoot}),(k2.v2.{k2.v2 → stateRoot}), …, (kn, vn, {kn, vn → stateRoot})}.
在對w所示的狀態部分執行t之後，如果t 修改了任何狀態，那麼可以透過使用修改後的葉節點計算新子樹的根，來生成新的結果stateRoot′。如果w是無效的，並且不包含在執行期間t所需的所有狀態部分，則會返回“err”;
4.3 資料根和週期(Data Root and Periods)
圖片3: 256位元組share的例子
由一個包含交易的區塊的dataRooti所表示的資料，並排列成固定大小的資料塊，我們稱之為‘share’，散佈在中間狀態根，我們稱之為交易之間的‘trace’。我們把trace(ji)表示為區塊i中第j箇中間狀態根。我們有必要將資料安排到固定大小的shares當中，以允許我們的資料可用性證明(詳見第五章內容)。資料樹中的每一個子葉都代表一個share。
因為一個share可能不會包含整個交易，而是隻包含交易的一部分(如圖3所示)，我們可以保留每個share中的第一個位元組，作為在share中開始的第一筆交易的起始位置，或者如果沒有交易在這個share中開始，則保留0.這允許協議訊息解析器不需要區塊中所有交易的情況下，就能夠建立訊息邊界。
給定一個share列表( sh0. sh2. …, shn )，我們定義了一個parseShares函式，該函式解析了這些share並輸出一個t訊息 (m0. m1. …, mt)的有序列表，這些訊息要麼是交易，要麼是中間狀態根。
例如，在某些區塊i的中間部分的某些share實施
注意，由於區塊資料不一定在每筆交易後都包含中間狀態根，因此，我們假定了一個‘週期規則’，即定義中間狀態根的協議規則，應該被納入區塊資料當中。例如，該規則可以每次執行至少p筆交易，或者b子節或者 g gas(例如以太坊 [41])。
注意，如果沒有前狀態根被解析，那麼traCEX可以為”nil”(零)，因為如果區塊中的第一條訊息正在被解析，那麼就可能會發生這樣的情況，因此，前狀態根是先前區塊stateRooti−i的狀態根。同樣的，如果沒有後狀態根被解析，那麼trace(x+1)也可以是零。換言之，如果區塊中的最後一個訊息被解析，後狀態根將是stateRooti;
4.4 無效狀態轉移的證明(Proof of Invalid State Transition)
一個有缺陷的，或者惡意的礦工，可能會提供不正確的stateRooti。我們可以使用dataRooti中提供的執行跟蹤來證明執行跟蹤的某些部分是無效的。
我們定義了一個VerifyTransitionFraudProof函式，及其相關引數，用於驗證從全節點那接收的欺詐證明。如果欺詐證明是有效的，那麼擁有這個欺詐證明的區塊將永久被客戶端拒絕。
如果下列的條件得到滿足，VerifyTransitionFraudProof返回的值就是“true”，其它情況則會返回“false”值;
4.5 交易費用
正如我們在本章第2節部分中所討論的，狀態將需要跟蹤與區塊處理相關的所有資料。一個區塊生產者可以嘗試收集比區塊交易能夠承受的更多的交易費用。為了讓欺詐證明能夠檢測到這一點，我們可以在狀態樹中引入一個特殊的key，我們稱之為費用( fee)，它表示應用每筆交易後區塊中累積的費用，並且在應用交易之後被重置為0.其中區塊生產者會收取這些費用。
五、資料可用性證明
惡意區塊生產者可以透過扣留驗算dataRooti所需的資料，並且僅釋放出區塊頭資訊，來阻止全節點生成欺詐證明。然後，區塊生產者只能在區塊釋出很久之後釋放資料(其中可能包括無效交易或狀態轉換)，並使得區塊無效。這將導致未來區塊賬本的交易回滾。因此，輕客戶端必須要有一定程度的保證，即資料匹配dataRooti確實可用於網路。
我們提出了一種基於裡德所羅門(RS)擦除編碼的資料可用性方案，其中輕客戶端請求資料的隨機share，以獲得高概率的保證，所有與Merkle樹根相關的資料是可用的。該方案假定有足夠多誠實的輕客戶端做出相同的請求，使得網路可以恢復資料，當輕客戶端將這些share上傳到全節點時，如果一個全節點並沒有完整的請求資料。對於輕客戶端來說，確保所有交易資料都是可用的，這是最為重要的，因為只需扣留幾個位元組，就可以在一個區塊中隱藏一筆無效交易。
我們會在本章第7節內容中定義以下的合理性和一致性，並對它們進行分析。
定義1(穩固性Soundness )：如果一個誠實輕客戶端接受了一個可用的區塊，則至少有一個誠實全節點具備完整的區塊資料，或者在一些已知的最大延遲k∗δ的情況下，具有完整區塊資料，其中δ是最大網路延遲。
定義2(一致性 Agreement)：如果一個誠實輕客戶端接受了一個可用的區塊，那麼所有其它誠實輕客戶端將在一些已知的最大 延遲 k∗δ的情況下，接受該區塊是可用的，其中δ是最大網路延遲。
5.1 稻草人1維裡德所羅門可用性方案(Strawman 1D Reed-Solomon Availability Scheme)
為了讓大家更好的瞭解，我們首先描述了一個基於標準裡德所羅門(RS)編碼的稻草人資料可用性方案。
一個區塊生產者編譯了一個包含k個share的資料區塊，並使用RS編碼，以及在擴充套件資料上計算一個Merkle根(dataRooti)，以此將資料擴充套件到2k share，其中每個分葉對應一個share。
當輕客戶端接收到具有此dataRooti的區塊頭時，它們將隨機地從dataRooti所表示的Merkle樹中取樣出share，而一旦它收到所有要求的share時，將只接收一個區塊。如果一個敵對區塊生產者建立了超過超過50%比例的不可用share，使得整個資料不可恢復(回憶下第二章第三節內容中提到的，RS碼允許從任何t share中恢復2t的share)，則一個客戶端有50%的機會在第一次抽取活動中隨機抽到一個不可用的share，兩次抽取後有25%的機會，三次抽取後有12.5%的機會，依此類推，如果它們用替代者來抽籤(在完整的方案中，它們將在沒有替換的情況下進行抽籤，因此概率甚至會更低。)
注意，為了使該方案工作，網路中必須要有足夠的輕客戶端來抽樣足夠的share，使得區塊生產者將需要釋放超過50%的share，以便透過所有輕客戶端的取樣挑戰，從而可以恢復完整的區塊。在本章第六節內容中，我們提供了深入的概率和安全性分析。
該方案的問題是，一個敵對區塊生產者可能會錯誤地構造擴充套件資料，因此，即使有超過50%的資料是可用的，不完整的區塊也無法從擴充套件資料中得到恢復。
而使用標準RS編碼，使得擴充套件資料是無效的欺詐證明，是原始資料本身，由於客戶端將不得不重新編碼本地所有資料，以驗證給定擴充套件資料的不匹配，因此，它需要關於區塊大小的O(n)資料。因此，我們改為使用了多維編碼，如本章第二節內容所述，以便將錯誤生成程式碼的證明限制在特定軸上(而不是整個資料)，將證明大小減小到
其中d是編碼的維數。為了簡單起見，本文只考慮二維的RS編碼，但實際我們的方案可以推廣到更高的維度。
我們在第七章第一節內容中，會提到簡潔的計算證明可以替代多維編碼，成為這個問題的未來解決方案。
5.2 二維RS編碼Merkle樹構造
圖片4:二維RS編碼圖。
原始資料初始排列成k×k矩陣，然後應用多次RS編碼，將其擴充套件成2k × 2k矩陣。
一棵二維RS編碼Merkle樹可以是如下資料塊構造：
請注意，儘管可以從dataRooti向單個share呈現一個Merkle證明，重要的是要注意Merkle樹具有2^x的子葉，而行與列根的 Merkle子樹是獨立於dataRooti構造的。因此，在VerifyMerkleProof周圍必須有一個稱為VerifyShareMerkleProof的封裝函式，該函式具有相同的引數，它會涉入到帳戶，考慮底層Merkle樹如何處理不平衡數的子葉;這可能會涉及為路徑的不同部分呼叫兩次VerifyMerkleProof函式，或者抵銷索引。
如果我們只關心dataRooti的行和列根，而不是實際的share，那麼在驗證行或列根的Merkle證明時，我們可以假設dataRooti 具有2×matrixWidthi的子葉。
一個輕客戶端或全節點能夠透過重新計算步驟4.從所有行和列根重構dataRooti 。為了獲得資料可用性保證，所有輕客戶端至少應該下載重構dataRooti所需的所有行和列根，並檢查步驟4是否被正確計算，因為正如我們將在本章第五節內容中看到的，它們必鬚生成錯誤擴充套件資料的欺詐證明。
儘管如此，我們將所有行根和列根表示為單個dataRooti，以允許無需下載行列根的“超輕”客戶端，但是這些客戶端無法保證資料可用性，因此不能充分受益於允許欺詐證明的安全增加。
5.3 隨機抽樣和網路區塊恢復
為了使2維RS矩陣中的任何share不可恢復，那麼在2k share當中，至少有 (k + 1)^2 share必須是不可用的(參加定理1)。因此，當輕客戶端從網路接收到新的區塊頭時，它們應該從擴充套件矩陣中隨機取樣0 < s < (k + 1)^2 份獨特的share，並且只有當它們接收到所有share時才會接收區塊。此外，輕客戶端向網路傳遞它們已經收到的share，以便誠實的全節點可以恢復整個區塊。
輕客戶端與它連線的全節點之間的協議如下：
5.4 選擇性Share披露
如果一個區塊生產者按輕客戶端的要求，有選擇地釋放share，並且最多為(k + 1)^2 share,那麼他們可能違反了客戶端的穩固屬性(定義1)，該客戶端請求2k share當中的第一部分(k + 1)^2 share，因為他們將接受這些區塊作為可用的，儘管它們是不可恢復的。
如果假設一個增強的網路模型，其中有足夠多數量的誠實客戶端做出請求，使得多於 (k + 1)^2 share被採用，並且每一個針對share的樣本請求是匿名的(即，樣本請求不能連線到同一個客戶端)，並且每個樣本請求被接收的分佈是均勻隨機的，(例如使用混合網路[9])則可以減輕這一點。由於網路不能將不同的share樣本請求連線到同一個客戶端，share就不能根據每個客戶端隨機性地釋放。
因此，我們假設了兩個可進行樣本請求的網路連線模型，我們將在安全分析部分對其進行分析：
1、標準模型。樣本請求可連線到產生它們的客戶端，並且它們被接收的順序是可預測的(例如，它們按照傳送的順序被接收)。
2、增強模型。不同的樣本請求不能連線到相同的客戶端，並且網路接收它們的順序較其它請求是一致隨機的。
5.5 錯誤生成擴充套件資料的欺詐證明(Fraud Proofs of Incorrectly Generated Extended Data)
如果全節點有足夠的share來恢復特定的矩陣行或列，並且在這樣做之後，檢測到恢復的資料不匹配其相應的行或列根，則它必須傳播由該行或列中足夠share組成的欺詐證明，以便能夠恢復它，以及每個share的Merkle證明。總而言之，欺詐證明驗證者需要核查 (i)證明者在同一行或列中給出的所有share ，以及 (ii)恢復的行或列，是否與區塊中的行或列根相匹配。
讓我們來恢復一個函式，它獲取了share列表及其在行或列中的位置 ((sh0.pos0),(sh2.pos1),…,(shk,posk))，然後擴充套件行或列2k的長度。如果share是不可恢復的，則函式輸出那些完全恢復的share(sh0. sh2. …, sh2k) 或者為“ err ”。
recover(((sh0. pos0), (sh2. pos1), …, (shk, posk)), 2k) ∈ {(sh0. sh2. …, sh2k), err}
當滿足以下所有條件時，則VerifyCodecFraudProof返回“ true”值：
請注意，全節點可以指定行或列中的share Merkle證明。
5.6 抽樣安全性分析
對於第五章內容中提供的資料可用性方案，我們將介紹其如何為輕客戶端提供了區塊資料可用性的高度保證。
不可恢復的最少不可用Share(Minimum Unavailable Shares for Unrecoverability)定理1中指出，如果惡意區塊生產者扣留至少k + 1行或列的k + 1 share，則資料將是不可恢復的;這使得總共 (k + 1)^2 數量的share會被扣留;
圖片5 ：定理1的圖解，如果至少有 k + 1行或列中k + 1的share是不可用的，則資料就是不可恢復的。
定理1 。在圖4所示的2k × 2k矩陣E中，如果至少有k + 1列或行具有至少k + 1的不可用share，則資料就是不可恢復的。在這種情況下，必須是不可恢復的share的最小數量為(k + 1)^2;
證明：假設惡意的區塊生產者希望使2k×2k矩陣E中的Ei,j share變得不可恢復，(回想一下，RS編碼允許從任何k share當中恢復所有2k share);區塊生產者必須(i)從行 Ei,∗中讓至少 k + 1 share變得不可恢復，並且 (ii) 從列 E∗,j 中讓至少 k + 1 share變得不可恢復;
讓我們從 (i)開始論述：區塊生產者至少要從行 Ei,∗中扣留k + 1 share。然而，這些k + 1中的每一個扣留share (Ei,c1 , . . . , Ei,ck+1 ) ∈ Ei,∗ 可以從它們各自的列E∗,c1. E∗,c2…, E∗,ck+1中 恢復。因此，區塊生產者還必須要從這些列中扣留至少k + 1的share。這意味著區塊生產者需要扣留的share數為 (k + 1) ∗ (k + 1) = (k + 1)^2.
然而，(i) 透過矩陣的對稱性等價於 (ii)，並且實際上是在相同的share上進行操作;在矩陣E上執行(i)等價於對矩陣E的轉換上執行(ii)。
不可恢復區塊檢測。定理2陳述了單個經客戶端將以不可恢復性的最小不可用share對矩陣中至少一個不可用share進行取樣的概率，從而檢測一個區塊可能是不可恢復的。
定理2.給定一個2k × 2k矩陣E，如圖4所示，其中 (k + 1)^2 個share是不可用的。如果一個參與者隨機從矩陣E中抽樣0 < s < (k + 1)^2 個share，那麼至少有一個不可用share的抽樣概率是：
證明。我們假設這個2k × 2k矩陣E包含了q個不可用share，如果參與者執行s次試驗 (0 < s < (k + 1)^2),則找到0個不可用share的概率為：
等式(2)的分子，計算的是不可用share集合
中計算選擇的s的方法數量。分母計算的是從樣本總數中
挑選任何s樣本的方法數量。
然後，我們可以從等式(2)容易地計算出找到至少一個不可用share的概率p1(X ≥ 1)
我們可以透過設定q = (k + 1)^2.將其重寫為等式(1);
圖6：等式(1)的繪圖 ，概率P1(X ≥ 1)抽樣 share的數量變化(計算 k = 32 和 k = 256)。
圖7:share大小與矩陣(k)大小的變化。
圖6顯示了這種概率如何隨k = 32 和 k = 256 的s個樣本而變化;每個輕客戶端在進行3次取樣後約有60%的概率至少有一個不可用share(即分別查詢k = 32時，區塊share的概率為0.07%，k = 256時，區塊share的概率為0.001%)，在15次取樣後，這個概率超過了99%(即分別查詢k = 16時，區塊share的概率為0.4%，k = 256時，區塊share的概率為0.005%)。圖7顯示，輕客戶端必須下載大約3.6 KB share才能檢測到不完整的區塊，對於k = 32時，這個概率超過99%，而k = 256時，大約為57 位元組的share。
等式(6)顯示了一個顯而易見的結果：對於較大的k值，概率p1(X ≥ 1)幾乎與 k無關了;因此具有大的矩陣大小(即，k ≥ 128)是實用的，因此這減少了輕客戶端必須下載的資料量。
根據第五章第四節中描述的增強模型，惡意區塊生產者可以基於它們查詢的的share來統計連線的輕客戶端;即，假設輕客戶端永遠不會請求兩次相同的share，區塊生產者可以以此推斷對相同share的任何請求都來自不同的客戶端。為了緩解此問題，輕客戶端可以透過多次執行替換取樣，並且僅在取樣到唯一值時才會停止。
多客戶端不可恢復區塊檢測。定理3 ，在一個具有不可恢復性最小不可用share的矩陣當中，從c個輕客戶端樣本中捕獲超過cˆ樣本，並且至少有一個不可用share的概率。
定理3.給定一個2k × 2k矩陣 E，如圖4所示，其中有 (k + 1)^2 share是不可用的。如果有c位參與者從矩陣E中隨機抽樣出0 < s < (k + 1)^2份share，則超過cˆ參與者樣本，至少有一個不可用share的概率是：
其中p1(X ≥ 1)是由等式(1)給出的。
證明：首先我們計算了cˆ位參與者樣本至少有一個不可用share的概率，這個概率是透過二項式概率質量函式計算得出的：
其中p1(X ≥ 1)是由等式(1)給出的，等式(8)描述了cˆ 位參與者成功取樣到至少一個不可用share的概率。這可以看作是觀察cˆ每一次以成功率 p1發生的概率，以及以成功率1 − p1發生的(c − cˆ)失敗率;這些成功和失敗排序的可能方法有 (c cˆ)種。
等式(8)很容易地就可以擴充套件到等式(9)中的二項式累積分佈函式，即在j = 1. . . . cˆ的情況下，觀測到最多cˆ成功觀測的概率和。
因此，觀察到多於cˆ的成功概率由下面的等式(10)給出，它是作為等式(7)的擴充套件。
圖8:等式(7)的製圖，描述了輕客戶端cˆ數目的變化，其中pc(Y > cˆ) ≥ 0.99隨著取樣大小S。客戶端總數固定於c = 1000.矩陣大小為k=64. 128. 256;等式(7)幾乎與k無關，如等式(6)所示。
圖8顯示了輕客戶端cˆ的數量變化，其中pc(Y > cˆ) ≥ 0.99隨取樣大小S。客戶端總數固定於c = 1000.矩陣大小為k=64. 128. 256;等式(7)幾乎與k無關，如等式(6)所示。該圖可用於確定具有高概率(pc(Y > cˆ) ≥ 0.99)的不完全矩陣的輕客戶端數量，並且當s增加到15以上時，幾乎沒有增益。
恢復和選擇性 Share披露(Recovery and Selective Share Disclosure)。推論一給出了輕客戶端集體取樣足夠share以恢復2k × 2k矩陣中每一個share的可能性。
如果輕客戶端集體取樣了除 (k + 1)^2 之外的所有不同share，則區塊生產者不能在不允許網路恢復整個矩陣的情況下，釋放任何更多的share;根據定理1.輕客戶端至少需要收集：
份不同的share(隨機選擇)，以確定能夠恢復2k × 2k矩陣。因此，我們感興趣的是，輕客戶端每次取樣s份不同share，共同取樣至少γ 份不同 share的概率，這個概率由推論1表示。
定理4 。 (Euler [15]) 從n個元素集中取樣不同元素的數量。
推論1.給定如圖4所示的2k × 2k矩陣E，其中每c位參與者隨機地從矩陣E中抽取不同的share。參與者集體抽取至少γ = k(3k − 2)不同 share的概率是pe(Z ≥ γ)
證明。推論1可透過把λ = n−γ 和 n = (2k)^2代入定理4.以實現容易的證明。
圖9. 推論1的圖示，概率值 pe(Z ≥ γ) 與客戶端(c)在s 和 k值不同的情況下發生的變化
與等式(7)相反，圖9表明 pe(Z ≥ γ) 依賴於矩陣的 k大小。
表一：針對不同的k 值和s值，達到 pe(Z ≥ γ) > 0.99所需的最小輕客戶端 (c) 的數量。由於評估定理4對於k的大值可能會非常消耗資源，所以我們取了接近值。
5.7屬性安全性分析
標準模型
推論2 。在標準模型下，區塊生產者不能導致穩固性(定義1)以及一致性(定義2)，無法讓超過c的誠實客戶端概率低於p1(X ≥ 1) ，其中c是由概率分佈pe(Z ≥ γ)來確定的。
證明。推論1表明，在概率pe(Z ≥ γ)的情況下，c個誠實客戶端將取樣足夠的share，以共同恢復整個區塊。誠實的客戶端會向全節點傳播這些 share，然後這些節點之間彼此會互相傳播，並且在k × δ內，至少有一個誠實全節點將隨後恢復完整區塊資料，因此，以每個客戶端1 − p1(X ≥ 1) 的可能性(當所有區塊資料可用時，區塊生產者不透過客戶端隨機取樣挑戰的概率)就可以滿足穩固性。
如果資料可用，並且沒有客戶端收到錯誤生成的擴充套件資料欺詐證明，那麼也不會有其他客戶端會收到欺詐證明。我們假設網路中至少有一個誠實的全節點，並且誠實的輕客戶端不會暴露於日食攻擊( eclipse attack)之下，從而滿足每個客戶端1 − p1(X ≥ 1) 的概率。
由於在第五章第四節中描述的選擇性share披露攻擊，這意味著區塊生產者可以違反第一批c客戶端發出的樣本請求的可靠性和一致性，因為區塊生產者可以在其釋出最終share之前停止釋放share，以阻止區塊變為可恢復。
增強模型
推論3.在增強模型下，在每個客戶端低於 px(X ≥ 1) 的概率下，區塊生產者不能導致穩固性(定義1)以及一致性(定義2)，
其中c是客戶端的數量，d是阻止全節點恢復資料必須拒絕的請求數量。
證明。推論3的證明從推論2的證明開始，誠實的輕客戶端透過向全節點傳播這些share來收集足夠的share樣本，以恢復整個區塊資料。每一個客戶端在概率1−p1(X ≥ 1)時能夠滿足穩固性的要求。如果區塊資料是可用的，輕客戶端就不會收到欺詐證明，網路上也不會傳播欺詐證明，並且如果傳送了一個欺詐證明，則所有的輕客戶端最終會收到一個有效欺詐證明，以相同的概率滿足了一致性。
然而，增強模型假設所有樣本都請求經過一個完美的混合網路(即，請求之間是不可連線的)。並且接觸了第五章第四節中提出的選擇性share披露攻擊。增強模型消除了推論2中描述的‘第一批’客戶端的概率，因為區塊生產者無法區分哪些請求來自哪個客戶端(因為請求是不可能的)。此外，如果區塊生產者隨機地拒絕一些請求，則輕客戶端將統一地看到它們的一些示例請求被拒絕，並且每個輕客戶端因此將以相同的概率認為此區塊無效。
特別是，如果 c個輕客戶端每個樣本 0 < s < (k + 1)^2 share，區塊生產者觀察到總的(c·s)不可區分的請求。讓我們假設惡意區塊生產者必須至少拒絕d次請求以阻止全節點恢復區塊資料。輕客戶端觀察到其請求中至少一項(因此拒絕區塊)的概率是等式(12)中的px(X ≥ 1)。
等式(12)中的分子是計算的由輕客戶端發出的s次請求中被拒絕的請求i的方式數目，再乘以其他輕客戶端 c · s − s = s(c − 1) 發出的請求當中剩餘d − i請求的方式數量。而分母則是計算挑選總請求當中的d請求的方式總數。
與等式(1)類似，等式(12)會迅速增長，並顯示出如果區塊無效，輕客戶端則會拒絕掉此區塊(對於適當的d值)。其中d的值可以使用推論1來近似算出，並且它取決於s 和 c。為了讓讀者更好地瞭解這個概念，如果我們假設輕客戶端對區塊的每一個share進行集體取樣至少一次，那麼惡意區塊生產者必須拒絕不同share至少 (k + 1)^2次請求，才能阻止全節點恢復區塊資料，因為多個請求可以取樣相同的share，其中d ≥ (k + 1)^2;
六、效能與實現
我們實施了第五章內容中描述的資料可用性證明方案，以及第四章內容中描述的狀態轉移欺詐證明方案的原型。
表2:各種物件的最壞情況空間複雜度。p表示週期內的交易數量，w代表這些交易的驗證數量，d是dataLength的簡稱，s是狀態樹中的鍵值對的數量。
整個實現共2683行Go程式碼，並且我們將其以免費和開源的方式呈現給大家。
(2D Reed-Solomon Merkle tree data availability scheme: https://github.com/ musalbas/rsmt2d
State transition fraud proofs prototype: https://github.com/asonnino/ fraudproofs- prototype
Sparse Merkle tree library: https://github.com/musalbas/smt )
我們首先在第六章第一節中評估了方案的空間和時間複雜度，然後在第六章第二節中給出我們的實施效能基準。實驗使用的是英特爾 i5 1.3GHz的處理器，及16GB記憶體的膝上型電腦，然後使用的是SHA-256演算法進行雜湊處理。
6.1 時間與空間複雜度
表2顯示了不同物件的空間複雜度。我們觀察到狀態轉移欺詐證明的大小隨區塊和狀態的大小對數增長，可用性欺詐證明(以及具有軸根的區塊頭)至少與區塊大小的平方根成比例增長關係。
表3顯示了各種動作的時間複雜度。為了生成和驗證欺詐證明，我們注意到，由於稀疏Merkle樹具有靜態深度，驗證部分生成和驗證Merkle證明是O(1) 的。其中最昂貴的操作是生成可用性欺詐證明，因為拉格朗日插值需要O(k2)的時間來對具有k share的行/列進行編碼或解碼，但是透過基於快速傅立葉變換演算法(FFT)[22.33]，這可以把時間減少到O(k log(k)) 。
6.2基準
表4顯示了在網路上傳輸時各種物件的大小。我們觀察到，狀態欺詐證明的大小僅呈對數增長。
表3:各種動作最壞情況下的時間複雜度，其中 [G] 表示生成， [V]表示驗證。p表示週期中的交易數量，b表示區塊中的交易數量，w表示這些交易的驗證部分數量，d是dataLength的簡稱，而 s則是狀態樹的鍵值對的數量。為了生成和驗證狀態欺詐證明，我們假設處理每筆交易所花費的時間是相同的。為了生成欺詐證明，我們還納入了驗證區塊本身的成本。
表4:用於250KB以及1MB 區塊物件的說明性大小，假設一個週期由10筆交易組成，平均每筆交易大小為225位元組，並且保守地說，狀態樹中有230個非預設節點。
對於區塊的大小，這是因為週期中的交易數量保持了靜態，但是每個交易的Merkle證明大小略有增加。區塊大小影響可用性欺詐證明的大小，而軸根的影響則是最大的，因為單個行或列的大小與區塊大小的平方根成比例。
表5顯示了用於生成和驗證各種物件的計算時間;用於狀態欺詐證明生成的基準包括用於驗證區塊的時間。雖然在區塊大小的驗證上，它是線性的，但在我們的實施過程中，由於Merkle樹中每次更新需要256個雜湊操作，因此它具有高的常數因子。這可以透過使用SIMD指令[17]的SHA-256庫以及將樹分解為子樹[11]來實現改進，從而進行並行處理更新。或者，我們可以使用更為複雜的鍵值樹構造，例如帕特麗夏樹[41]
表5:計算用於各種動作的時間(平均超過10次重複動作)，其中 [G] 代表生成， [V] 代表驗證。我們假設一個週期內由10筆交易組成，平均交易的大小為225位元組，每一筆交易會在狀態樹中寫入一個key。
正如預期的那樣，驗證可用性欺詐證明要比生成更快。這是以為你生成需要檢查整個資料矩陣，而驗證只需要檢查一行或一列。注意，我們使用的是標準的RS演算法庫，這些演算法需要 O(k^2)時間來編碼/解碼，透過使用基於快速傅氏變換演算法，我們可以把時間降低到O(k log(k))。
七、討論
7.1 簡潔的計算證明
在計算的簡潔證明方面，我們已經取得了進展，包括zk- SNARKs [5] 以及最近的zk-STARKs [4]，這允許證明者證明，對於某些給定的 x 和y ，f(x,W) = y , 其中即使證明部分W是非常大的，並且計算時間f會是非常長的，證明本身只有對數或恆定的大小，並且只需要對數或恆定的時間來驗證。
對於將來的工作，我們可以要求區塊頭附帶這樣的證明，以表明它們是經過正確的擦除碼操作過的，消除欺詐證明的需要。還請注意，2維RS方案相對於1維方案的唯一顯著優點，在於更少的欺詐證明，因此如果使用簡明的證明，則切換回1維方案可能是最優的(對於n個share，如果使用快速傅立葉變換法 [22.33]，則構造合法的擦除程式碼只需要O(n log(n)) 計算時間)。
注意，雖然可使用區塊狀態根轉移函式的簡明證明計算，來消除對欺詐證明的需求，但它們並不能消除對可用性證明的需求。如果多數惡意的區塊生產者廣播了資料不可用的區塊，則它們可以拒絕誠實全節點構造完整最新狀態所需的資訊，併為涉及某些賬戶的交易生成驗證部分(即，Merkle分支)。這些惡意者透過防止建立驗證部分，使用不可用資料的區塊，可使賬戶永久不可訪問 [8]。 使用資訊理論參數列明，即使像密碼累加器這樣的構造，也不能消除驗證O(n)資料可用性的需求，它可以確保所有驗證部分都能夠被正確更新。
7.2 區域性可譯碼
關於該方案，消除對欺詐證明需求的另一個策略，是使用多維RS碼的區域性可譯碼功能 [43]。特別地，我們利用資料的Merkle根作為熵源，構造由一組偽隨機選擇的行與列(或用於更高維編碼的軸平行線)組成的“鄰近證明”(proof of proximity)，其中，驗證者可以驗證是否具有< k的度，從而概率地驗證所有軸平行線中具有非常高的百分比的< k的度，因此任何非軸平行線具有的度< d ∗ k.檔案，將從k∗…∗k擴充套件到(k∗2d)∗…∗(k∗2d)。
任何具有有效鄰近證明的區塊(頭)都是可接受的，即使擴充套件多項式資料的一小部分是不正確的。正因為如此，一個單一的Merkle分支，不再足以證明一個單一的值。相反，驗證者可選擇一個隨機的穿過該點的非軸平行線，並要求證明人提供至少線上的(3 /2)∗ d點。驗證者在期望的點計算正確的值，必要時進行糾錯。為了增加可靠性，驗證者可以選擇多個隨機非軸平行線。
該方案的優點在於，它不依賴於欺詐證明或昂貴的計算證明，但它也具有以下的缺點：
(i)它要求在網路上儲存更多的編碼資料，儘管這種情況下，由於大數量的share可減輕儲存在網路上每一個share的複製數，但其總體還是會儲存更多的編碼資料。
(ii)Merkle證明變大了兩個數量級。
八、相關工作
最初版的比特幣白皮書[26]簡要地提到了‘警報’的可能性，它是由全節點傳送而出的訊息，用於警告輕客戶端某個區塊是無效的，促使它們下載完整的區塊以驗證資料的不一致性。對此，白皮書進行了很少的探索，部分原因是資料可用性問題。
關於如何設計欺詐證明系統[32.38]，社羣已經有了線上討論，但是還沒有提出處理所有塊無效情況和資料可用性的完整設計。這些早期的系統，已在嘗試為建立違反協議規則的區塊(例如，雙花輸入，挖取高報酬區塊等)的每種可能方法設計欺詐證明，而本文將區塊鏈推論到僅具有一個欺詐證明的狀態轉移系統。
在資料可用性方面，Perard等人[29]已提議使用擦除編碼來允許輕客戶端自願貢獻以幫助儲存區塊鏈，而無需下載所有的區塊，然而，他們還沒有提出一種方案，可允許輕客戶端透過隨機取樣和錯誤生成擦除編碼的欺詐證明，來驗證資料是可用的。
九、結論
我們提出、實施並評估了一個完整的欺詐和資料可用性證明方案，並且根據附加的假設，網路中至少有一個誠實全節點在最大網路延遲內傳播欺詐證明，並且網路中具有最小數量的輕客戶端來共同恢復區塊，它使得輕客戶端幾乎可以得到全節點級別的安全保障。
致謝
Mustafa Al-Bassam得到了艾倫.圖靈研究所的獎學金資助，而Alberto Sonnino得到了歐洲委員會地平線2020 DECODE專案的資助，專案編號為732546.
感謝George Danezis, Alexander Hicks 和 Sarah Meiklejohn對論文數學論證的有益討論。
