Data Availability on Ethereum 2.0 Light Node

-

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


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發出無效的詐欺證明
source: https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding

如果漁夫打了個盹，沒注意到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糾刪碼將資料延伸一倍，可得Ｎ = 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)），有興趣可以看論文中的公式推導。

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

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

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


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


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


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

感謝Ethereum Foundation Researcher, C.C. Liang（梁智程）的協助及建議，才能使文章順利完成。

references：
Fraud and Data Availability Proofs
Unsolved Problems in Blockchain Sharding
詐欺證明與有效證明


留言

張貼留言

這個網誌中的熱門文章

What's New in Ethereum Serenity (2.0)

-
圖片
Ethereum 2.0 已經正式改名為Ethereum Serenity 原本預計在今年(2018)上線的Hybrid POS(Casper FFG)跟sharding，因為遇到一些技術上的困難，所以把Hybrid POS改成單純POS，然後因為sharding跟POS有部份技術是重疊的，所以把POS跟sharding併在一起做（本來是分成兩個team作開發） Beacon Chain 在Ethereum Serenity的規劃中，在原本的POW chain之外多一個鏈叫做 Beacon chain ，是一個POS chain。在Beacon chain中有兩種角色 proposer 跟 attester ，proposer就是產塊的人，attester是驗證的人。而在POW chain上存入32 ETH，可以成為Beacon chain上的 validator ，而validator有權利產塊(proposer)，也會有機會被選attester。此外，延續了Casper FFG finality這個概念，也就是在finality之後的狀態就是正確的狀態（不可回復），不像POW一般需要6個塊的時間才能確認交易是不會被更改的（POW的狀態確認是機率，六個塊之後有"很高的機率"是無法被改變的，而finality就像是0跟1一樣，沒有中間）。 聽到這，好像覺得很簡單，但是在實作上會遇到幾個問題，首先，怎麼決定誰是proposer誰是attester，如果亂數的隨機性不夠，就很容易被遭到操控。接下來是，每次驗證都需要做一次簽名，因為32個ETH就可以當validator/attester，每次驗證可能會有10~20幾萬的簽章（ 簽章數量的預估方法 ），驗完簽章天都黑了 ＸＤ。 ＲＮＧ 針對亂數產生（ RNG , Random Number Generator），使用 RANDAO 跟 VDF ，RANDAO是個利用經濟獎勵的機制來產生亂數，原始的設計是在smart contract上，而在Beacin chain會直接實作這個邏輯。而VDF是一個delay function，因為速度的關係，基金會打算自己開發ASIC晶片。關於這RNG之後會再寫一篇 詳細解釋 。 Signature Aggregatio...
閱讀完整內容

瑞士滑雪分享2 - 策馬特

-
圖片
本篇同 上一篇 ，只介紹滑雪資訊，關於觀光資訊，就不在這裡詳述 一樣，我們先來介紹策馬特/馬特洪峰，這裡一樣是分兩區，Zermatt跟International，如下圖，左邊紅色框是 Zermatt ，而 International 是Zermatt+Italy，也就是 全山卷 ，在Zermatt賣的就這兩種票 在這我一樣只有滑兩天，就只買了Zermatt的票，所以不要再問我買International需要不要護照之類的問題，我不知道阿~~ XD 我住在Zermatt，這個鎮還滿大的，所以在挑住宿的時候需要注意一下，Zermatt的住宿非常的貴，比Grindelwald貴上許多，所以也有人選擇住下面的小鎮，再坐火車到Zermatt，至於住哪個小鎮或是便宜多少，我沒有研究，就不知道了。Zermatt火車站一出來，就有往山上的小火車，所以住下面的小鎮要上山滑雪，也算滿方便的。 Zermatt雪場分三區，最左邊Rothorn，中間Gornergrat，最右邊Matterhorn Glacier Paradise。 Rothorn ：要搭小火車上山，滿特別的，詳細介紹可參考 這篇網誌 ，離Zermatt火車站約10分鐘的路程。 Gornergrat ：一出火車站，對面就是車站了，小火車直接拉到山頂，相當方便 Gornergrat車站 Matterhorn Glacier Paradise ：上山纜車離市區相當遠，走路大約要20-25分鐘（有接駁巴士），需要轉2次纜車才能到山頂，要花不少時間，山頂非常冷，滑道很平緩，又冷又不好玩 三座山基本上可以互通，不需要回到小鎮再上山。這裡高度大都在2000-3000公尺，所以雪況比少女峰好很多，不過相當多的平路，對snowborders相當不友善....。 完整的地圖可參考： Zermatt ski map 雪票價格如下，這裡的雪票是用磁卡，所以會有5CHF的押金，最後記得去退（像我就忘了...@@） Zermatt/International ski pass (2014/15) ： Zermatt International (Zermatt - Cervinia) Days Adults You...
閱讀完整內容

動手實做零知識 - circom

-
圖片
零知識證明在過去一年越來越廣為人知，去年(2019)也有越來越多的專案是基於零知識證明。前年底提出的 zk rollup，目前由  Matter Labs  在開發，Matter Labs更在上個月（2019/12）發表了  ZK Sync ，解決了因為產生證明（proof）而延伸的延遲問題。此外  Iden3  跟 ConsenSys  也有 zk rollup 的專案。在以太坊研究論壇有基於 zk rollup 所衍生的 匿名 zk rollup 。 Semaphore 是一個基於零知識證明的一個訊號系統，發送者可以不揭露身份的狀況下廣播任何訊息(an arbitrary string)。 Semaphorejs 延續 Semaphore 的核心概念，並將整個概念更加完整化，從前端網頁到後端服務。這兩年才發表的 zk-STARKs，也在去年年初跟 0x 合作，推出基於 zk-STARKs 的 去中心化交易所 。 在技術上，去年下半年有新的論文，使用 DARK compiler 可以讓 SNARKs 達到公開性（Transparent）。還有 MARLIN, SONIC, PLONK 等可通用且可更新的可信設定（trusted setup）。STARKs 的 FRI 驗證方式也默默地跟 SNARKs 做結合。（東西越來越多，根本看不完 QQ） 這篇文章沒有要談高深的技術，只會介紹實做所需的知識。這篇會使用到 Iden3 所開發語言  circom  來幫助寫算數迴路 。藉由 circom，可以更輕鬆地實做零知識證明的程式。但在開始之前，先介紹一些基本觀念。 算數迴路 在實做零知識程式跟一般撰寫程式不同，需要先把問題轉成迴路，才去執行（實際上是把 問題 轉成 多項式 再轉成 迴路 ）。舉例來說，一個多項式 $x^3 + x +5$，會轉成像這樣的迴路 sym_1 = x * x // sym_1 = x^2 sym_2 = sym_1 * x // sym_2 = x^3 y = sym_2 + x // y = x^3 + x ~out = y + 5 ...
閱讀完整內容