本文探討了 KV-witness 區塊見證數據方案的解析算法、優缺點,以及網絡效率等方面。

原文標題:《引介 | 無狀態性:基於鍵值對的見證數據方案》
撰文:Igor Mandrigin
翻譯:阿劍

無狀態以太坊運動當前提議了一種區塊見證數據(witness)的格式,詳述見此處。這套區塊見證方案是基於操作碼(opcode)的,你可以理解爲一種小型的編程語言,可以使用少數幾個命令來生成 「默克爾多值證明」

本文研究了另一種區塊見證數據的建構方法,它基於一個鍵值對的列表,語義也更簡單。

在本文中我將嘗試回答下列問題:

  • 鍵值對見證數據(KV witness)是什麼樣的,與當前被提議的、基於操作碼的見證數據格式有何區別?
  • 鍵值對見證數據與操作碼見證數據相比,有什麼優點和缺點?
  • 從網絡帶寬的角度看,鍵值對見證數據方案的效率如何?

見證數據方案需滿足的)前提:

所有的區塊見證數據方案都必須滿足下列要求:

  • 正確(correctness)。保證節點可以執行來自以太坊主網的任意區塊。
  • 效率(efficiency)。轉移見證數據所需花費的網絡帶寬儘可能小。
  • 默克爾化(Merkelization)。必須支持合約代碼默克爾化(中文譯本)。
  • 無視狀態樹的格式(Arity-agnostic)。既支持十六進制默克爾樹,也支持二進制默克爾樹(中文譯本)。

語義

這一部分我先講講鍵值對見證格式的語義,還不會談到具體的數據佈局(byte layout)。

後面,我再講解我用在測試中的數據格式。

引介 | 無狀態性:基於鍵值對的見證數據方案

witness ::= header, body, proofs  
header ::= version : byte, trie_arity : byte  
body ::= array of [ { type: byte key : []byte, value : []byte } ]  
proofs ::= map { <type>: [ { prefix : []byte, hash : []byte } ] }

見證數據:數據體

見證數據的數據體由兩個元素構成:

1. 數據

「鍵」(key)可以是:賬戶的地址,storage key 或者 code key;而 「值」(value)可以是:賬戶、storage item 或者相應的代碼分塊(code chunk)。這一部分的數據體與用於驗證正確性的默克爾樹的格式完全無關。而且,即使用其它方式來驗證正確性,這一部分也不會改變。

2. 證據

鍵是默克爾路徑,而值是一個哈希值。證據的形式依賴於狀態樹的格式,所以十六進制樹和二進制樹下的證據將有所不同。這一語義使得我們能在同一個見證中包含多種類型的多值證明。所以,理論上來說,我們可以創建出一種既能支持十六進制狀態樹、又能支持二進制狀態樹的見證數據格式。

數據體按 key 的字典順序排序、存儲,以確保:

  • 更短的鍵在列表中總是排得前一些(在自頂向下重建默克爾樹時候會有用)
  • 當兩個數據的鍵相同時(賬戶地址可能和 code key 相同),總是把賬戶相關數據排在前面。

解析算法

  1. 檢查見證數據的版本,以及證據所用的默克爾樹格式(以確保證據的格式與區塊所需的狀態樹格式相匹配)
  2. 驗證見證數據的哈希值(如果有 「canonical witness」 的概念的話)
  3. 使用正確的格式創建一棵空的默克爾樹
  4. 遍歷數據,按讀取數據的順序爲這棵空默克爾樹插入數據(見證數據也應該以字典順序存儲)
  5. 插入證據到樹中
  6. 驗證根哈希值(應該與上一區塊的根哈希值一致)

好處 & 缺點

對比一下鍵值對見證格式與當前的操作碼見證格式的優缺點。

優點

  • 與 flat DB 數據庫機構相匹配,所以如果 canonical witness 哈希值是有效的,就可以立即插入(不需要驗證默克爾根值)
  • 可以用於快照同步(snapshot sync
  • witness 中的數據獨立於我們所選的驗證證據的方法:無論是默克爾樹,還是多項式承諾,還是別的方法,都不會影響我們需要添加的數據。

缺點

  • 在二進制狀態樹下,可能會因爲字節對齊(byte alignment)而需要佔用更高的帶寬(例如,證據的鍵爲 0b01,只是兩個比特,卻需要佔用一個字節的存儲空間)
  • 解析起來可能更慢

網絡效率研究

KV Witness 的實現案例

我們首先必須證明這種格式能夠實現正確性。它必須能執行以太坊主網上的所有區塊。

爲此,我在 turbo-geth 代碼庫的一個分支裏面實現了這種見證方案:kv-witness-research。

這一實現是在谷歌雲裏面測試的,執行的是塊高從 500 萬到 800 萬的以太坊主網區塊。

如何重複我的實驗?

你需要至少 200 GB 的可用硬盤空間,和至少 32 GB 的內存(因爲代碼還在概念驗證階段,沒怎麼優化)。

1)複製 turbo-geth 客戶端(commit 號爲 aa6b4dc609b3d871c778597a71ac08601f17de53)的 kv-witness-research 分支

2)同步主網的區塊頭和區塊體:go run ./cmd/geth --syncmode staged --datadir ~/stateless-chaindata/ (我花了一天時間)

3)以同步所得的數據運行無狀態客戶端的原型(我花了 17 天)

    go run ./cmd/state stateless --blockSource ~/stateless-chaindata/geth/chaindata --statefile ~/kv_witness_statefile --witnessInterval 5000000 --statsfile ~/stats_kv_witness.csv 2>&1 | tee debug.log

如此,在 stats_kv_witness.csv 文件中,你就能得出跟我在本文中所示的一模一樣的結果。

見證數據的格式

見證數據的開頭是一個單字節的數據頭(header),包含其版本信息。

然後就是數據體(body),由大小信息和元素(elements)本身組成;大小信息會佔用 1~4 個字節,具體要看元素的數量。

每一個元素都以一個字節的類型(type)開頭,然後是鍵(key)字段,是一個長度任意的字節數組;鍵字段的前綴是大小信息,然後是實際數據(就像數據體的佈局一樣)。

數據的形式取決於元素的類型:

  • 對於 storage 葉子節點,數據是任意長度的字節數組,前綴是其長度信息(size bytes);
  • 對代碼葉子節點,數據也是任意長度的字節數組,以長度信息爲前綴;
  • 對於證據,數據是一個定長的,32 字節的哈希值,不包含任何前綴信息。

以賬戶爲鍵的數據則更復雜一些,但主要的數據包括:

  • flag (辨識該賬戶元素是否具有默認值)
  • nonce (如果不爲零),需要 8 個字節
  • 餘額(如果不爲零),任意長度的字節數組,前綴爲其長度
  • 存儲根哈希值(如果不爲空),32 個字節,定長的字節數組
  • 代碼哈希值(如果不爲空),32 個字節,定長的字節數組

最終,見證數據看起來會長這樣:

[<header> <witness_elements_count> <element1_type> <element1_key_size> <element1_key_byte1> ... <element1_value_size> ... <element2_type> ...]

[< 數據頭 > < 元素數量 > < 元素 1_類型 > < 元素 1_鍵長度 > < 元素 1_鍵_字節 1> ... < 元素 1_值長度 > ... < 元素 2_類型 > ...]

引介 | 無狀態性:基於鍵值對的見證數據方案

優化:刪除重複鍵前綴

鍵是一個由半字節(nibble)組成的默克爾路徑,不是由字節組成的。對於十六進制默克爾樹而言,一個半字節的長度是 4 個比特,對二進制默克爾樹來說則是 1 個比特。因此,有時候鍵的字節長度並不是整數(舉個例子,12 比特是 8.5 個字節)。

鍵被編碼爲 []byte,這樣就是字節對齊的(所以如果有一個鍵的長度在 4 個字節到 5 個字節之間,它總是會被補齊爲 5 個字節)。同樣地,可以加入一個額外的 「面罩」 在開頭,指明在最後一個字節中,哪些比特是 1。

  • 0xFF (1 byte): [00001000 11111111] <== 8 個重要比特
  • 0b11(2 bits): [00000010 11000000] <== 2 個重要比特
  • 0b10(2 bits): [00000010 10000000] <== 2 個重要比特
  • 0b_10101010_01010101_1101(2 bytes 4 bits): [11110000 10101010 01010101 11010000]

然後,我們可以加入一個簡單的優化措施,減少數據和證據中的重複前綴 。

爲提高壓縮效率,我們會在同一個有序映射中混合數據和證據。

引介 | 無狀態性:基於鍵值對的見證數據方案數據和證據將共同按字典順序排序和存儲

數據頭的前 4 個比特將用來說明前一個鍵的字節偏移量(The highest 4 bits of a header byte mean a byte offset of a previous key.)。

因爲在我們的語意中,鍵是排過序的,我們可以使用前 4 個字節來說明下列情況:

  • 本鍵與前一個鍵相同,整個鍵因此可以壓縮到 1 個字節: [10000000]
  • 本鍵與前一個鍵無任何一個字節是相同的([0000xxxx xxxxxxxx ...]
  • 本鍵與前一個鍵共享至多 14 個作爲前綴的字節 ([????xxxx xxxxxxxx ...]):開頭的 「?」 號表示 big-endian 編碼的數字,從 1 (001) 到 14 (1110) )
  • 本鍵與前一個鍵共享超過 15 個字節:([1111xxxx ???????? xxxxxxxx ...]),而中間的 」疑問號「 是對超過數量的說明
    • 如果恰好是 15 個字節,那就是 [1111xxxx 00000000 ... ] (15 + 0)
    • 如果是 16 個字節,那就是 [1111xxxx 00000001 ... ] (15 + 1)
    • 如果是 32 個字節,那就是 [1111xxxx 00010001 ... ] (15 + 17)

引介 | 無狀態性:基於鍵值對的見證數據方案KV-Witness 壓縮。括號中的數字表示要從前一個鍵中重用多少個比特

網絡效率研究結果

本結果的原始數據可以在此 GitHub 倉庫 中找到。

爲了在網絡效率角度得出一個全面的圖景,我比較了 3 種見證數據格式,統一用十六進制默克爾樹來運行:

1)基於操作碼的見證數據,就是現有的這個。(數據沿用自我的上一次實驗)

2)基於鍵值對的見證數據(未壓縮):沒有刪除重複的鍵前綴

3)基於鍵值對的見證數據(壓縮後)

測試的範圍是區塊高度從 500 萬到 800 萬的區塊。

絕對大小比較

引介 | 無狀態性:基於鍵值對的見證數據方案絕對大小的比較。壓縮後的 KV witness 與 opcode witness 表現非常相似。

量化分析

引介 | 無狀態性:基於鍵值對的見證數據方案

(單位:MB)平均值中值90 分位值95 分位值99 分位值最大值
基於操作碼的見證數據1.161.221.8722.2212.9
基於鍵值對的見證數據(未壓縮)1.421.482.282.452.745.58
基於鍵值對的見證數據(壓縮後)1.071.111.721.842.054.91

結論

刪除重複的鍵前綴爲 KV witness 帶來了相當大的提升。有了這個功能,它與基於操作碼的方案的帶寬消耗就幾乎相同了。

而基於鍵值對的方案還有許多優點。

最重要的優點是:簡潔。爲一種數據格式(本質上就是一個字典)撰寫詳述,要比爲一個幾乎是編程語言一樣的方法撰寫詳述簡單得多。

第二大優勢是,證據在語義上與數據是獨立的,所以,當我們想要改變狀態樹的形式(從十六進制轉爲二進制)、或者想要完全改變證據的機制時,KV-Witness 方法所需的變更要小得多。

我認爲,KV-witness 方案是見證數據標準的有力競爭者。