當然咯，需要傳播區塊見證資料就意味著無狀態客戶端的網路要求要比普通節點更高。
現在人們已經提出了很多降低見證資料規模的思路：使用 有效性/計算完整性 證明（包括但不限於零知識證明）、加入更多的壓縮手段，等等。其中一種辦法是將以太坊的默克爾樹（即用來表示以太坊的默克爾樹）從十六進位制轉為二進位制。
這就是本文想要探討的問題。
為什麼要使用二進位制樹
默克爾樹的一大優良特性是，驗證樹根值（就是一個雜湊值）正確與否並不要求你具有整棵樹所有的資料。只需把所有省略的非空路徑替代為相應的雜湊值就可以可。
那麼使用十六進位制默克爾樹有什麼不好呢？
設想整棵樹都已填滿資料（即樹上的節點已幾乎沒有為零的子節點）。要驗證一個區塊，我們只需要一小部分默克爾樹節點的資料。那麼，我們只需把其他路徑的資料替代為雜湊值就可以（讓這棵子樹變得可以驗證）了。
但是，每多加入一條雜湊值，區塊見證資料就會大一些。
如果我們轉變為二進位制默克爾樹，這個問題就可以得到緩解 —— 因為默克爾樹上的每個節點都只有兩個子節點，所以至多隻有一個位元組點需要被替換為雜湊值。（換句話來說，我們可以更早地開始 “切割” 默克爾樹的路徑，因為我們的粒度是 1 位元，而不是十六進位制下的 4 位元。）
這樣做也許能大幅降低見證資料的規模。
我們再舉例說明一下。
假設執行某個區塊只會影響一個賬戶：3B 路徑下的 Acc1（二進位制為 0011 1011）。整棵樹是全滿的（樹上的節點沒有為零的子節點）。
-測試方法：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 percentile.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust
現在我們可以生成一些很酷的圖表了！
python xy-scatter-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust
- XY 散點圖（已假設 key 以最優方式編碼）(橫軸為 Hex 下見證資料大小，縱軸為 Bin 下見證資料大小）-
可以看出，二進位制見證資料的大小總是優於十六進位制樹下的見證資料。
我們再加入另一個引數，用二進位制見證資料大小除以十六進位制見證資料大小，看看我們得到了怎樣的提升。
python size-improvements-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust
為更好地理解這張圖示，我們也輸出了平均值和百分位值。
平均值 = 0.51 （平均來說節省了 49% 的空間） P95 = 0.58 （按節省程度排列，對於前 95% 的資料，至少節省了 42% 的空間） P99 = 0.61 （按節省程度排列，對 99% 的資料，至少節省了 39% 的空間）
在實際場景中這意味著什麼？
對於 99% 的區塊，見證資料的大小可以降低至少 39% 。
對於 95% 的區塊，見證資料的大小可以降低至少 42% 。
平均來說，見證資料可節省 49%。
我們也要考慮見證資料大小的絕對值。為使資料變得可讀，我們每 1024 個區塊取滑動平均值。
python absolute-values-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust
再來看看最新區塊的情況。
區塊高度 800 萬到 850 萬
python percentile.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust
還有 XY 散點圖。
python xy-scatter-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust
還有規模上的節約。
python size-improvements-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust
平均值 = 0.53 （平均來說節省了 47% 的空間）
P95 = 0.61 （按節省程度排列，對於前 95% 的資料，至少節省了 37% 的空間）
P99 = 0.66 （按節省程度排列，對 99% 的資料，至少節省了 34% 的空間）
最後，再來看看見證資料的絕對大小。
python absolute-values-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust
結論
在使用以太坊主網資料做過測試以後，我們可以看到，切換為二進位制樹模式可以大幅提升生成見證資料的效率（見證資料大小平均減少 47-49%）。
另一個結論是，這種提升並沒有理論上那麼顯著。原因可能在於主網區塊的實際資料（比想象中要複雜）。
也許，透過分析一些例外情況（也就是二進位制樹所得提升最少的情況），我們可以知道更多最佳化見證資料規模的辦法。
試著使用別的原始資料來跑跑 GitHub 中的指令碼吧：https://github.com/mandrigin/ethereum-mainnet-bin-tries-data
（文內提供了許多超連結，請點選閱讀原文到 EthFans 網站上獲取）
原文連結:
https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768
作者: Igor Mandrigin
翻譯: 阿劍
