Fraud and Data Availability Proofs

這篇文章是被Kimi啟發，所以去研讀並且節錄一些重點還有我對這篇paper的理解

輕節點(Light clients, SPV clients)在整個區塊鏈網路中只下載少部分的資料來驗證區塊是否合法，而這個做法相比於全節點驗證全部資料來說，必須假設共識演算法中只有包含有效的區塊資料同時也假設大部分的全節點是誠實的．

如果讓全節點能夠產生 Fraud Proofs 來證明區塊確實違反了共識協定的規則同時搭配概率抽樣的方法來驗證全部的區塊資料可供下載，就可以大大的降低誠實節點的數量假設；藉由能夠保證鏈上資料都是可得並且有效，Fraud and Data Availability Proofs會是擴容技術(e.g., sharding, bigger blocks)的一大重點．

Erasure code and Reed-Solomon Codes

糾刪碼是將原來長度為k的訊息編碼成為長度為k+m的訊息，而原來的訊息可取編碼後的訊息子集來還原，也就是說這個技術可以容忍m個分散式節點故障，這邊就不詳述了，可參考Kimi的文章

Fraud Proofs

1. Block Structure

一個block header應該要包含以下元素

• prevHash: 前一個block header的hash
• dataRoot: 資料(e.g., transactions)組成Merkle tree的root hash
• dataLength: 資料樹的葉節點數量
• stateRoot: 狀態樹的root hash
• additionalData: 額外的任意資料，像是nonce或是難度等等

2. State Root and Execution Trace Construction

transition function: 給一個state S並且去執行transaction T，成功則返回新的state S’ , 或者失敗了返回error

state witness: state tree中只有部分被transaction讀取或者改變的merkle proofs

rootTransition: 使用Merkle proofs來有效地表達一個子樹(root hash會跟整棵狀態樹一樣)

interRoot: rootTransition在一個區塊中執行每個transaction時產生暫時的state root，denote成trace

3. Data Root and Periods

shares: 資料樹的葉節點，包含一個完整個transaction, 部分的前一個transaction跟後一個transaction以及完整的transaction，這樣做法的好處是message parser不需要全部的message就可以建立message boundaries

利用parser將transactions取出之後就可以去驗證state transition是否正確

4. Proof of Invalid State Transition

一個不正常或者惡意的礦工可能會給出一個不正確的stateRoot，我們可以利用dataRoot下的資料(包含trace)來驗證部分的執行是有問題的；一個Fraud Proof 包含不正確state transition相關的shares, 這些shares的merkle proofs, 以及shares中的state witnesses

Verify function要檢查1. block hash跟client端存的是一樣的. 2. 每一個shares都在dataRoot底下. 3. parseShare執行完是整個區塊transition的子集. 4. 確認執行transaction後，trace_x會變成 trace_(x+1)，執行無誤

Data Availability Proofs

惡意的區塊產生者為了避免全節點產生Fraud Proof，可能會扣留著資料而只送出block header，等到過了很久之後才送出資料，這樣可能會造成未來的transactions rollback，所以對於輕節點來說，高度保證正確的資料可得性是非常必要的

這篇paper提出一個基於Reed-Solomon erasure coding的data availability scheme，這個scheme假設網路上有足夠多的輕節點可以產生足夠數量shares來恢復完整資料

1. Strawman 1D Reed-Solomon Availability Scheme

首先，block producer將區塊資料編碼成k個shares並且利用RS編碼將資料擴展成2k個new_shares，在前面的RS coding中得知我們只需要隨機取得k個new_shares就可以恢復原來的資料．

如果block producer沒有正確的利用RS coding來擴展資料，則就算new_shares資料都可得，也無法正確的恢復原來的資料，也就是說客戶端必須把所有的資料重新編碼一次來判斷block producer有沒有正確產生dataRoot，也因此需要區塊大小的空間O(n)資料．
PS: 我認為要讓其他的全節點做驗證，因為輕節點沒有全部transaction資料

如果使用多維度的編碼則可以將proof size降到O(n^(1/d))，d為維度大小，簡單用2維空間來做解釋，但是實際的scheme是可以用到更高維

2. 2D Reed-Solomon Encoded Merkle Tree Construction

• 首先，將raw data 切成 k * k 個 new_shares
• 利用RS coding 將原來的資料水平以及垂直擴展，再將垂直擴展的shares再做一次RS coding就像fig 4.圖示，最後產生一個Matrix M_i for block i
• 計算每一個row, column所組成Merkle tree的root hash

• 最後計算rowRoot跟columnRoot的hash

最後資料樹的資料長度會是 2 * (2k)² 元素(經過編碼的new_shares)，前半段的葉子點路徑包含row root，而後面一半則是包含column root；輕節點或是全節點可以透過所有的row root跟column root 去驗證 data root 是否正確，為了獲得資料可得性的保證，所有的輕節點都至少要下載區塊所有的row 及 column root，這樣才有辦法產生Fraud Proof

3. Random Sampling and Network Block Recovery

輕節點跟全節點協定如下

• 輕節點收到block header 以及 raw roots, column roots，驗證data root 是否正確，否則reject header
• 輕節點隨機取幾組座標(x, y)，並且寄給一個或多個全節點
• 全節點如果有這組座標的shares以及相關的merkle proof就回傳給輕節點
• 輕節點檢查這個shares 以及相應的 merkle proof是否屬於相應的row root樹或者是 column樹
• 輕節點把shares 跟相應的merkle proof gossip給其他與他相連並且沒有這些shares資料的全節點
• 如果所有的proofs 都通過檢驗，則這個block被認為是可得的

4. Selectively Share Disclosure

如果區塊產生者有選擇性的釋出shares，儘管這些shares是unrecoverable，但是這個區塊還是會被認為是available；所以可以藉由假設網路上有足夠多的誠實節點並且有超過(k+1)²個shares 會被匿名的sample request呼叫來解決這個問題，也可以利用enhanced network model來強制不同sample的request不能給同一個client，請求順序也是隨機分布的．

5. Fraud Proofs of Incorrectly Generated Extended Data

如果一個全節點拿到足夠多的shares去recover特定的row或是column，並且發現recovered data不正確，那他就必須提出一個merkle proof包含足夠的shares可以recover那個data．(包含每個shares的merkle proof)

結論

這篇paper提出了一個data availabilty的方法，在額外的一些假設下(至少有一個誠實的節點會提出Fraud Proof，一定數量的輕節點會共同來恢復區塊)，來讓輕節點的安全保證幾乎跟全節點一樣