原文標題:《無狀態以太坊:二進制狀態樹實驗》
原文來源:以太坊愛好者 作者: Igor Mandrigin
本文所用的數據和腳本都放在這個 github 代碼庫中:
https://github.com/mandrigin/ethereum-mainnet-bin-tries-data
什麼是「無狀態以太坊」?
如果您已經瞭解什麼是「無狀態以太坊」以及「區塊見證數據」,可以跳過這一段。
爲執行交易及驗證區塊,以太坊網絡的節點需要了解整條區塊鏈的當前狀態——也就是所有賬戶和合約的餘額和存儲數據。這些數據一般來說是存儲在 DB(數據庫文件)裏面的,在需要用於驗證時纔會加載到一棵默克爾樹中。
無狀態以太坊客戶端的工作思路則稍有區別。顧名思義,無狀態客戶端就是不使用硬盤 DB 來執行區塊(雖然客戶端中可能也維持着完整的狀態)。相反,無狀態客戶端依賴於「區塊見證數據(block witness)」——就是一段特殊的數據,它會跟相應的區塊一起傳播;擁有了這段數據,客戶端就可以重建出一個(代表部分狀態的)默克爾子樹,該分支足可用於執行該區塊中的所有交易。
你可以在這篇文章中讀到關於無狀態客戶端的更深入的描述:https://blog.ethereum.org/2019/12/30/eth1x-files-state-of-stateless-ethereum/
當然咯,需要傳播區塊見證數據就意味着無狀態客戶端的網絡要求要比普通節點更高。
-見證數據大小折線圖(區塊高度 500 萬到 850 萬)-
現在人們已經提出了很多降低見證數據規模的思路:使用 有效性/計算完整性 證明(包括但不限於零知識證明)、加入更多的壓縮手段,等等。其中一種辦法是將以太坊的默克爾樹(即用來表示以太坊的默克爾樹)從十六進制轉爲二進制。
這就是本文想要探討的問題。
爲什麼要使用二進制樹
默克爾樹的一大優良特性是,驗證樹根值(就是一個哈希值)正確與否並不要求你具有整棵樹所有的數據。只需把所有省略的非空路徑替代爲相應的哈希值就可以可。
那麼使用十六進制默克爾樹有什麼不好呢?
設想整棵樹都已填滿數據(即樹上的節點已幾乎沒有爲零的子節點)。要驗證一個區塊,我們只需要一小部分默克爾樹節點的數據。那麼,我們只需把其他路徑的數據替代爲哈希值就可以(讓這棵子樹變得可以驗證)了。
但是,每多加入一條哈希值,區塊見證數據就會大一些。
如果我們轉變爲二進制默克爾樹,這個問題就可以得到緩解——因爲默克爾樹上的每個節點都只有兩個子節點,所以至多隻有一個字節點需要被替換爲哈希值。(換句話來說,我們可以更早地開始「切割」默克爾樹的路徑,因爲我們的粒度是 1 比特,而不是十六進制下的 4 比特。)
這樣做也許能大幅降低見證數據的規模。
我們再舉例說明一下。
假設執行某個區塊只會影響一個賬戶:3B 路徑下的 Acc1(二進制爲 0011 1011)。整棵樹是全滿的(樹上的節點沒有爲零的子節點)。

-二進制狀態樹與十六進制狀態樹的比較-
如果說二進制狀態樹看起來有點嚇人,那只是因爲二進制樹我畫全了,但沒有把十六進制樹的所有代之以哈希值的節點都畫出來。
來數個數:
爲創建出一棵二進制狀態樹,見證數據需要包含 8 個哈希值,7 個分支節點和 1 個賬戶節點。也就是見證數據中有 16 個元素。
爲創建出一棵十六進制狀態樹,我們只需 1 個分支節點,1 個賬戶節點,但需要 30 個哈希值。也就是有 32 個元素。
所以,假設哈希值和分支節點在區塊見證數據中的所佔的空間是一樣大的(其實哈希值所佔的空間要更大一點),在我們的例子中,使用二進制樹所需的見證數據大小隻有十六進制下的一半。看起來不錯。
那麼,理論上就是這樣。
我們來看看實際情況是如何。我們直接拿以太坊主網的數據來看看吧。
開始實驗
先說最緊要的:我們怎麼知道自己構建出來的區塊見證數據是有用的呢?
測試方法如下:我們使用區塊見證數據來生成一棵默克爾子樹,在這棵樹上運行相應區塊中的所有交易,然後校驗結果是否與我們所知的一致。只要交易都能成功執行(Gas 夠用,軌跡相同(they have the same traces),等等),我們就可以斷定這個見證是足夠充分的。
-測試方法:1. 執行區塊;2. 從狀態樹中抽取出見證數據;3. 使用見證數據構造出一棵子樹;4. 禁用 DB 訪問、使用子樹來執行區塊(具體可見 github)-
其次,我們需要一些基準數據(用於比較)。因此,我們也使用 500 萬到 850 萬高度的區塊、在十六進制默克爾樹模式下生成了見證數據,並將見證數據大小的統計數據存在一個超級大的 csv 文件中。
我們嘗試的第一步是執行完一個區塊後就組裝出一棵十六進制樹,然後將它轉爲二進制樹,再從這棵二進制樹中提取出見證數據。
這種方法有幾個好處:易於實現,而且驗證 十六進制-二進制 的轉換也很簡單。
不過,我們遇到了兩個問題,而且其中一個還不小。
第一個,正如我們上面證明的那樣,比起二進制樹,十六進制樹包含更多的賬戶節點,如果我們先生成十六進制樹再轉換,得到的結果就跟在二進制樹模式下直接生成所得到的見證數據不一樣。
爲什麼呢?
因爲十六進制樹數據總是以 1/2 字節的速度增長,而二進制樹總是以 1 比特的速度增長,因此鍵(key)的長度可以是奇數位。
實際上,見證數據中還包含一些額外的擴展節點(EXTENSION node),它們還要稍微大一點。不過即便對內容較多的區塊(包含約 5000 條交易的區塊),體現在見證數據大小上的差別也非常之小(小於 5%)。
關鍵的是性能。隨着樹的規模增長,轉換的速度會越來越慢。
用更具體的數字來說明一下:在我們的 Google Compute Engine 虛擬機上,處理速度約爲每秒 0.16 個區塊,也就是每分鐘處理小於 10 個區塊,處理 100 萬個區塊要超過 3 個月!
所以,我們決定採取更復雜的辦法,開發出一個原生使用二進制默克爾樹的實驗性分支。也就是說,我們要把 turbo-geth 代碼庫例地所有十六進制狀態樹全部替換爲二進制樹,然後區塊就是基於二進制樹來執行的了。
這種辦法的不利之處在於,部分哈希值的校驗只能被忽略掉(區塊根哈希,有些時候的賬戶存儲樹根哈希,因爲我們的區塊鏈快照機制有所欠缺)。
但主要的驗證機制還是一樣的:我們需要能夠使用二進制樹來執行區塊、從見證數據中創建出默克爾子樹。
再來談談 key。
爲簡化起見,我們對 key 的編碼方式是非常低效的:1 byte per nibble;一個 key 的每一比特就要佔用 1 字節。這樣做大大簡化了代碼層面的改變,但區塊見證數據中的」key「部分會是我們使用 bitset 時候的 8 倍大(想了解區塊見證數據由哪些數據組成,請看《無狀態客戶端初探》)(編者注:中譯本見文末超鏈接)。
因此,在進一步分析中,我會假設 key 的編碼方式是最優的(使用 1 比特來編碼 1 比特的信息)。
Hex vs. Bin:結果
我的分析分爲兩段,總共分析了以太坊主網上的 200 萬個區塊。
區塊高度 500 萬到 650 萬
我在這個 github 庫裏面提供了使用 python 腳本來重複這一實驗的命令行:https://github.com/mandrigin/ethereum-mainnet-bin-tries-data
首先我們來分析一下數據集。
python百分位數。py hx -witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000調整
-一個箱型圖,箱體顯示上四分位到下四分位之間的數據,左右延伸出去的線條顯示上 1% 到下 1% 之間的數據(即排除了極端大和極端小的 1% 數據)
現在我們可以生成一些很酷的圖表了!
python xy-scatter-plot.py hx -witness-raw.csv
- XY 散點圖(已假設 key 以最優方式編碼)(橫軸爲 Hex 下見證數據大小,縱軸爲 Bin 下見證數據大小)-
可以看出,二進制見證數據的大小總是優於十六進制樹下的見證數據。
我們再加入另一個參數,用二進制見證數據大小除以十六進制見證數據大小,看看我們得到了怎樣的提升。
python大小改進-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000調整
-二進制見證數據的大小/十六進制見證數據的大小(值越小越好)-
爲更好地理解這張圖標,我們也輸出了平均值和百分位值。
平均值 = 0.51(平均來說節省了 49% 的空間)
P95 = 0.58(按節省程度排列,對於前 95% 的數據,至少節省了 42% 的空間)
P99 = 0.61(按節省程度排列,對 99% 的數據,至少節省了 39% 的空間)
在實際場景中這意味着什麼?
對於 99% 的區塊,見證數據的大小可以降低至少 39%。
對於 95% 的區塊,見證數據的大小可以降低至少 42%。
平均來說,見證數據可節省 49%。
我們也要考慮見證數據大小的絕對值。爲使數據變得可讀,我們每 1024 個區塊取滑動平均值。
python絕對-值-plot.py見證-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000調整
-依時間順序繪製的見證數據大小折線圖,縱軸單位爲 MB-
再來看看最新區塊的情況。
區塊高度 800 萬到 850 萬
python百分位。py hex- raw.csv bin-stats-8m-9m.csv 8000000 8500000調整
-箱型圖,箱表示上下四分位以內的數據,線表示上下 1% 以內的數據-

- 800 萬號到 850 萬號區塊的百分位分析-
還有 XY 散點圖。
python xy-scatter-plot.py hx -witness-raw.csv
還有規模上的節約。
python大小改進-plot.py見證-raw.csv bin-stats-8m-9m.csv 8000000 8500000調整
- XY 散點圖(已假設 key 以最優方式編碼)(橫軸爲 Hex 下見證數據大小,縱軸爲 Bin 下見證數據大小)-
平均值 = 0.53(平均來說節省了 47% 的空間)
P95 = 0.61(按節省程度排列,對於前 95% 的數據,至少節省了 37% 的空間)
P99 = 0.66(按節省程度排列,對 99% 的數據,至少節省了 34% 的空間)
最後,再來看看見證數據的絕對大小。
python絕對-值-plot.py見證-raw.csv
-依時間順序繪製的見證數據大小折線圖,縱軸單位爲 MB-
結論
在使用以太坊主網數據做過測試以後,我們可以看到,切換爲二進制樹模式可以大幅提升生成見證數據的效率(見證數據大小平均減少 47-49%)。
另一個結論是,這種提升並沒有理論上那麼顯著。原因可能在於主網區塊的實際數據(比想象中要複雜)。
也許,通過分析一些例外情況(也就是二進制樹所得提升最少的情況),我們可以知道更多優化見證數據規模的辦法。
試着使用別的原始數據來跑跑 GitHub 中的腳本吧:https://github.com/mandrigin/ethereum-mainnet-bin-tries-data
(完)
原文鏈接:https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768
來源鏈接:https://ethfans.org/posts/stateless-ethereum-binary-tries-experiment
歡迎加入律動 BlockBeats 官方社群:
Telegram 訂閱群:https://t.me/theblockbeats
Telegram 交流群:https://t.me/BlockBeats_App
Twitter 官方帳號:https://twitter.com/BlockBeatsAsia