以太坊2.0輕節點上的資料可用性

買賣虛擬貨幣
data availability(資料可取得性) 跟fraud proof (詐欺證明)對於區塊鏈交易量擴充套件,是很重要的兩項因素。當交易量大意味著資料量就變大(無論是分片或是加大區塊大小),而資料量越大,能夠執行全節點的人就會越少(因為硬體跟維護成本越高)。舉例來說,Ethereum 2.0 有1024 條鏈,不可能每個人都把1024 條的資料都下載下來,更何況,這樣也失去分片的意義,但若某節點做分片A 的validator,此時,需要跟分片B 有所互動,不太可能把分片B的所有區塊都下載下來,太耗時也太佔空間,而且若如此設計,最終也會把全部的鏈都下載下來….。但是,若沒有全部的區塊那要怎麼驗證交易呢?!這就是「資料可取得性」的重要性。資料可取得性簡單來說就是拿不拿得到資料,但不代表拿到的資料的有效的/正確的。那在討論資料可取得性問題之前,先來認識詐欺證明。在區塊鏈世界中,驗證資料方式可以分為有效證明(validity proof)跟詐欺證明兩種。有效證明就是現在區塊鏈的運作方式-「驗證資料是正確的,才能上鍊」,也就是當你需要轉帳時,礦工需要先驗證你的餘額是否足夠,確認你餘額是夠的(驗證資料是正確的)才會打包。而詐欺證明則是相反,驗證者收到交易之後,經過一段時間若沒有人提出異議/挑戰,那就代表你送出的交易是沒問題的,這種方式驗證成本相對較低,也因此大部分L2方案選擇使用詐欺證明作為資料驗證的方式。而輕節點只下載部分的資料(通常是block header),要如何能在運作上幾乎跟全節點一樣可靠呢('幾乎'是因為輕節點需要額外的一些假設)?就必須藉助資料可取得性跟詐欺證明的的合作。

Fishermen


漁夫(fishermen)機制是一種很直覺的設計方式,就是漁夫們觀察著網路上的無效資料,發現後送出詐欺證明以得到獎勵。基本的獎懲機制如下,1.若有人提出無效的詐欺證明,則沒收押金,2.若有人提出有效的詐欺證明,送出無效資料的人會被沒收押金,而押金部份當作挑戰者(提出詐欺證明的人)的獎勵。但是,這種機制在這個情境會有問題。我們來看以下這兩個例子Case 1: 
T1:攻擊者v1送出不完整的資料(等待被挑戰)T2: v2送出詐欺證明證明資料是無效的T3:攻擊者v1再補送剩下的資料Case 2: T1: v1送出正確的資料

T2:攻擊者v2發出無效的詐欺證明

如果漁夫打了個盹,沒注意到T2 發生什麼事,到了T3 才來驗證,在這樣的狀況下是無法判斷出兩個的差異(因為T3 所能看見的就是”一份完整的資料”被提出”詐欺證明”,不知道其實case1 是後來補件的)。以上例來說,case1的v2 要給獎勵嗎?1.若給了,則攻擊者就可以藉由發出無效的詐欺證明來賺錢(因為兩著是無法分辨的)。2.若要懲罰,那就沒有人願意提出詐欺證明。3.若什麼事都不做,則提供了一個免費的DOS 攻擊。因此,這種方式有個根本的問題,就是無法有效遏止攻擊者隱藏資料(因為被發現了,再補件即可),也就無法判斷節點或是漁夫誰是惡意的。

Reed-Solomon Erasure Code

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

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

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

這邊做一個簡單的計算,先假設最簡單的狀況M=N,區塊大小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 
而詐欺證明的大小約是1.5MB

如果將資料延伸到多維度,例如二維。資料將變為sqrt(M)*sqrt(M) 的正方形(x = 0 ~ sqrt(M)-1, y = 0 ~ sqrt(M)-1),接著使用二維RS 糾刪碼將資料延伸一倍,可得N = 2*sqrt(M),如下:

而merkle tree 的數量從原本的一個變成4*sqrt(M) 個(每個欄列皆為一個merkle tree,如下圖所示)

接著,回到上面的例子,1MB的區塊,每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 
而詐欺證明的大小約為12KB

這裡我們看到,資料量雖然變大了,但是詐欺證明的資料大幅減少了,而且因為merkle tree 的層數減少許多,在效能上也有大幅的提升。下圖是論文中對於取樣數, 區段數量跟輕節點數的表格(s : 取樣數,k : sqrt(M)),有興趣可以看論文中的公式推導。

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

而全節點跟輕節點的溝通程式如下圖:

1. 有新區塊產生,輕節點會收到某個全節點的通知,並且提供block header跟上述的每個欄/列的merkle root
2. 輕節點會隨機挑選(x, y) 值給不同的全節點(x,y 分別對應二維糾刪碼的列跟欄)
3. 全節點接收到(x, y) 座標後,提供對應的區段,並註明此資料區塊是欄還是列(因為同一個座標可以取欄或是列的資料),若此全節點沒資料,就繼續廣播給其他全節點
4. 輕節點接受到資料後,驗證區塊的merkle root 和1.所提供的是否一致,若為一致,則標記為正確的資料,並等待挑戰(詐欺證明)

這是目前Ethereum 2.0 輕節點的提案,#1194是針對資料可得性證明效率不足的討論,主要的問題在於,二維的糾刪碼讓處理的資料量變大,也增加網路傳輸的負荷,再加上EIP1559,將使得區塊平均的負載量約只有50%,也就意味著需要填很多的0,讓二維糾刪碼徒增很多無意義的資料,這也是目前尚未解決的問題。

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

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;