Data Availability on Ethereum 2.0 Light Node

本來是要展開一個叫做「與大神(C.C. Liang)共筆系列」，無奈大神太忙，最終還是只能自幹，不過依舊感謝C.C. Liang提供素材跟觀念釐清

data availability 跟 fraud proof 對於區塊鏈交易量擴展，是很重要的兩項因素。當交易量大意味著資料量就變大（無論是shard chains或是加大block大小），而資料量越大，能夠運行全節點的人就會越少（因為硬體跟維護成本越高）。舉例來說，Ethereum 2.0 有1024 條鏈，不可能每個人都把1024條的資料都下載下來，更何況，這樣也失去分片的意義，但若某節點做shard A的validator，此時，需要跟shard B有所互動，不太可能把B的block都下載下來，太耗時也太佔空間，而且若如此設計，最終也會把全部的鏈都下載下來....。但是，若沒有全部的block那要怎麼驗證交易呢？！這就是data availability的重要性。

data availability以字面上來解釋就是資料的可取得性，也就是拿不拿得到資料，但不代表拿到的資料的有效的/正確的。那在討論data availability問題之前，先來認識fraud proofs（詐欺證明）。

在區塊鏈世界中，驗證資料方式可以分為validity proof(有效證明) 跟fraud proof兩種。validity proof就是現在區塊鏈的運作方式-「驗證資料是正確的，才能上鏈」，也就是當你需要轉帳時，礦工需要先驗證你的餘額是否足夠，確認你餘額是夠的（驗證資料是正確的）才會打包。而fraud proof則是相反，驗證者收到交易之後，經過一段時間若沒有人提出異議/挑戰，那就代表你送出的交易是沒問題的，這種方式驗證成本相對較低，也因此大部分L2方案選擇使用fraud proof作為資料驗證的方式。

而light clients只下載部分的資料（通常是block header），要如何能在運作上幾乎跟full node一樣可靠呢（'幾乎' 是因為light clients需要額外的一些假設）？就必須借助data availability跟fraud proof的的合作。

Fishermen

首先，要怎麼設計一個機制可以使大家都乖乖照劇本走....

1. 若有人提出無效的fraud proof，則沒收押金，

2. 若有人提出有效的fraud proof，送出無效資料的人會被沒收押金，而押金部份當作挑戰者（提出fraud proof的人）的獎勵。

接著，來看以下這兩個例子

Case 1:

T1: 攻擊者v1送出不完整的資料（等待被挑戰）

T2: v2送出fraud proof證明資料是無效的

T3: 攻擊者v1再補送剩下的資料

Case 2:

T1: v1送出正確的資料

T2: 攻擊者v2發出無效的fraud proof

source:  https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding

若在T3之後才下載資料來驗證，是無法判斷出兩個狀況的不同，因此在實作上會有問題。以上例來說，case1的v2要給獎勵嗎？1.若給了，則攻擊者就可以藉由發出無效的fraud proof來賺錢（因為case1跟case2是無法分辨的）。2.若要懲罰，那就沒有人願意提出fraud proof。3.若什麼事都不做，則提供了一個免費的DOS攻擊。因此，這種方式有個根本的問題，就是無法有效遏止攻擊者隱藏資料。而有一種攻擊叫做Griefing attacks，攻擊者不在乎押金被沒收，然後一直發出無效的fraud proof，會造成這個網路的部分癱瘓或是難以使用。

Reed-Solomon Erasure Code

延續上面的問題，若把block切成N個區塊，而light client 從網路中隨機去挑選某20個區塊來驗證是否正確(藉由block header中的merkle root來驗證)，當20個區塊都是有正確的，light clients就接受此塊，這個方法有很高的機率可以證明資料是有效的，但這種方式只驗證到部分的資料，並不是整個block，若攻擊者偽造的block只有極少的差距，例如有幾十或幾百的bytes，仍有機會避過這樣的驗證機制。而erasure code(糾刪碼)是可以解決這個問題的好方法！

何謂erasure code呢?! erasure code可以在資料部分遺失的狀況下，組回原本的資料(但無法容忍資料的篡改)，常用在網路通訊, 磁碟陣列或是DVD。可以想作是在原本的資料，再多加部份的備份，所以丟掉部分資料也沒關係。erasure code編碼方式有很多種，也分別適用不同領域，這邊使用的RS(Reed-Solomon) erasure code，是一種原理相較簡單的編碼方式。概念上就是用Lagrange 插值方式，長出多餘的備份資料。

假設，把block分成M個區塊，藉由RS erasure code把資料延伸為N個區塊(N > M)，因此只要N個中的M個就可以把資料還原，所以若有節點不提供資料或是部分資料遺失了，仍可還原block做驗證。

這邊做一個簡單的計算，先假設最簡單的狀況M=N，block大小1MB，每256bytes切成一個區塊，所以可得4096(M=4096)個區塊，然後，將全部區塊組成一個Merkle tree（會有12層）。接著，隨機取20個區塊來驗證，資料量將是

20 branches * (256 bytes + 12 Merkle tree intermediate hashes * 32 bytes per hash) = 12,800 bytes

而fraud proof的大小約是1.5MB

如果將資料延伸到多維度，例如二維。資料變為sqrt(M)*sqrt(M)的正方形（x = 0 ~ sqrt(M)-1, y = 0 ~ sqrt(M)-1），接著用2D RS erasure code將資料延伸一倍，可得Ｎ = 2*sqrt(M)，如下：

而Merkle tree的數量從原本的一個變成4*sqrt(M)個（每個row/column皆為一個Merkle tree，如下圖所示）

接著，回到上面的例子，1MB的block，每256bytes為一個區塊，所以可以得到64x64的正方形，共有4*64個Merkle tree，但是取樣數就需要有48個，因此資料量為：

48 branches * (256 bytes + 6 Merkle tree intermediate hashes * 32 bytes per hash) 

+ (128 Merkle roots * 32 bytes per hash) = 25,600 bytes

而fraud proof的大小約為12KB

這裡我們看到，資料量雖然變大了，但是fraud proof的資料大幅減少了，而且因為Merkle tree的層數減少許多，在效能上也有大幅的提升。下圖是論文中對於取樣數, 區塊數量跟light clients數的表格（s : 取樣數，k : sqrt(M)），有興趣可以看論文中的公式推導。

source: https://arxiv.org/pdf/1809.09044.pdf

------------------------------------------------------------------------------------------------------------------

但若在一般的網路模式下，會知道自己的鄰居們(peer nodes)是誰，所以對攻擊者來說，就有空間操控，某個light client來問資料就故意不給，或是有時給有時不給等等的擾亂light clients取得資料的穩定性。因此會需要搭配洋蔥網路服用，攻擊者就無法針對特定的light clients作擾亂。再加上fraud proof的挑戰，在整個設計中只需要保證網路中有一個誠實節點即可。

而Full nodes跟light nodes的溝通程序如下圖：

1. 有新block產生，light node會收到某個full node的通知，並且提供block header跟上述的每個row/column的merkle root
2. light node會隨機挑選(x, y)值給不同的full nodes
3. full nodes 接收到(x, y)座標後，提供對應的區塊，並註明此資料區塊是row還是column（因為同一個座標可以取row或是column的資料），若此full node沒資料，就繼續廣播給其他full nodes
4. light node接受到資料後，驗證區塊的merkle root和1.所提供的是否一致，若為一致，則標記為正確的資料，並等待挑戰（fraud proof）

這是目前Ethereum 2.0  light client的提案 ， #1194 是對於data availability proof效率不足的討論。

如果文章有錯誤的地方，歡迎糾正，若有說明不清的也歡迎提出。

references：

A note on data availability and erasure coding

Unsolved Problems in Blockchain Sharding