目前有一種針對無狀態以太坊中的區塊見證的提議格式，它在GitHub repo中有一個規範。它是基於操作碼，您可以想象只有一種命令可以生成Merkle Mupltiproof的小型程式語言。
這篇文章研究了區塊見證建設的另一種方法。它是基於鍵和值的列表，並且具有更簡單的語義。
在這篇文章中，我將嘗試回答以下問題：
1. 什麼是KV-Witness格式？它與當前提議的（基於操作碼的）見證格式有何不同？
2. 比較KV的優缺點是什麼？
3. 就網路頻寬而言，這種格式的效率如何？
要求
任何集體見證人必須滿足以下要求：
Correctness（正確性）：我們使用這種格式能夠正常運轉以太坊主網的任何區塊。
Efficiency（效率）：我們能夠使用最小的網路頻寬來轉移此見證人。
Merkelization（默克爾化）：見證人格式必須支援程式碼默克爾化。
Arity-agnostic（不可知論）：見證格式必須同時支援hexary和二進位制Merkle Tries。
語義
我在文章的這一部分描述的見證格式是語義。我不是在這裡談論確切的位元組佈局。
稍後，我將詳細介紹用於測試的見證人的精確二進位制格式。
witness::=header,body,proofsheader::=version:byte,trie_arity:bytebody::=arrayof[{type:bytekey:[]byte,value:[]byte}]proofs::=map{<type>:[{prefix:[]byte,hash:[]byte}]}
Witness body
Witness body 由2個元素組成：
1、Data.
金鑰可以是：帳戶地址，儲存金鑰或程式碼金鑰，值分別是帳戶，儲存專案或程式碼塊。Witness body的這一部分完全與用於驗證其正確性的Merkle Trie無關。此外，如果我們使用其他方法進行正確性檢查，則此部分不會更改。
2、Proof(s).
關鍵是Merkle路徑和雜湊的值。證明取決於trie arity，十六進位制和二進位制嘗試會有所不同。此語義允許在同一見證人中包含具有不同型別的多個證明。因此，從理論上講，我們可以做一個既支援十六進位制也支援二進位制的見證人。
body是按字母順序在字典上排序，請確保：
較短的鍵在列表的前面（因此我們從上到下重新構造了trie）；
當金鑰相同（account和code可能發生這種情況）時，account總是在第一位。
解析演算法
1. 驗證證人版本和證明Arity（確保證人證明Arity匹配該塊要求的Trie Arity）。
2. 驗證見證雜湊（如果存在規範的見證）。
3. 建立一個正確arity的空trie。
4. 遍歷資料，只需按順序將資料插入此trie（見證人應按字典順序排序）。
5. 在trie中插入證據。
6. 驗證根雜湊（應與上一個塊的根雜湊匹配）。
優點和缺點
下面是比較KV-Witness與當前基於操作碼的見證格式的優缺點列表。
優點
它與flat DB結構匹配，如果規範的見證雜湊有效，則可以立即插入（無需驗證Merkle根）。
它可以用於快照同步。
見證資料獨立於我們選擇的有效性證明方法：Merkle Tries或多項式承諾或其他。
缺點
由於位元組對齊（例如校驗金鑰0b01，即2位將佔用一個位元組的儲存空間），二進位制嘗試時可能會佔用更大的網路佔用空間。
證人解析可能會變慢。
頻寬效率研究
KV-Witness例項實施
我們需要能夠證明格式的正確性。它應該能夠在以太坊主網的所有區塊上執行。
為此，我已經在turbo-geth儲存庫的一個分支中實現了這種見證格式：kv-witness-research。
此實現已在5.000.000–8.000.000的以太坊主網上的Google Cloud中進行了測試。
如何重複實驗？
您至少需要200GB的可用空間和至少32gbs的RAM（該程式碼是PoC，而且最佳化程度不高）。
1）複製kv-witness-research branch of turbo-geth (commit aa6b4dc609b3d871c778597a71ac08601f17de53
2） （在我的例子中花了1天的時間）同步主網的header和body：執行./cmd/geth--syncmode staged--datadir~/stateless chaindata/
3） （在我的例子中花了17天）在這個資料上執行無狀態原型。
gorun./cmd/statestateless--blockSource~/stateless-chaindata/geth/chaindata--statefile~/kv_witness_statefile--witnessInterval5000000--statsfile~/stats_kv_witness.csv2>&1|teedebug.log
這樣您應該在stats_kv_witness.csv中獲得與本文件相同的統計資訊。
見證二進位制格式
見證人從包含版本：header的單位元組標頭開始。
然後，有一個見證人body，它由大小（1-4個位元組，取決於見證人元素的數量）和elements本身組成。
每個elements均以單位元組type開頭，其後為鍵欄位，該鍵欄位是任意大小的位元組陣列，其字首為大小位元組（就像body一樣），後跟實際資料。
資料取決於元素的型別：
對於儲存葉子，它是由位元組大小決定的任意大小的位元組陣列；
對於程式碼葉子，它也是一個任意大小的位元組陣列，並以大小位元組為字首；
為了證明，它是一個固定大小的32位元組雜湊值，沒有任何大小的字首；
對於帳戶來說，它更復雜，但基本上是：
標記位元組（掩碼，用於告知帳戶元素是否沒有預設值）
隨機數，8個位元組（如果隨機數！= 0）
balance（如果balance！= 0），任意大小的位元組陣列，以其大小為字首；
儲存根雜湊（如果不是空的根雜湊），32位元組，固定大小的位元組陣列；
程式碼雜湊（如果程式碼不為空），32位元組，固定大小的位元組陣列。
最後我們得到這樣的結果：this: [<header> <witness_elements_count> <element1_type> <element1_key_size> <element1_key_byte1> ... <element1_value_size> ... <element2_type> ...]
最佳化：刪除key(金鑰)字首重複資料
key是由半位元組組成的Merkle路徑，而不是全位元組。十六進位制trie的單個半位元組大小為4位，而二進位制trie的單個半位元組大小為1位。這樣，我們可以看到有時金鑰可以是非整數字節：（例如12位為8,5位元組）。
key編碼為[] byte，按位元組對齊（因此len在4到5位元組之間的金鑰將始終為5位元組）。同樣，一個附加的“掩碼”位元組被新增到開頭，以顯示最後一個位元組中哪些位是“active”。
a key 0xFF（1 byte）：[00001000 11111111] <== 8個有效位
a key 0b11（2 bits）：[00000010 11000000] <== 2個有效位
a key 0b10（2 bits）：[00000010 10000000] <== 2個有效位
a key 0b_10101010_01010101_1101（2 bytes 4 bits）：[11110000 10101010 01010101 11010000]
然後，我們可以新增一個簡單的最佳化，這樣我們可以減少重複字首在資料和證據。
為了提高壓縮效率，我們將資料和證明混合在同一有序對映中。
頭位元組的最高4位表示前一個鍵的位元組偏移量。
由於按我們的語義對keys進行了排序，因此我們可以使用前4個位元組來描述以下情況：
該key與上一個key相同，然後可以將整個key縮減為1個位元組：[10000000]
key與前一個key不共享任何位元組（[0000xxxxxxxxxxxx…]）
key與前一個共享多達14個字首位元組（[？？？？xxxx xxxxxxxx…]）：？？？是big-endian編碼的數字1（001）到14（1110）。
key與上一個共享15個或更多位元組（[1111xxxx ???????? xxxxxxxx ...]）：其中????????? 是15的補充。
15位元組將是[1111xxxx 00000000 ...]（15 + 0）
16位元組將是[1111xxxx 00000001 ...]（15 +1）
對於32個位元組，它將是[1111xxxx 00010001 ...]（15 + 17）
KV-Witness壓縮，括號中的數字表示從上一個key中重用多少位。
為了提供頻寬效率方面的全面影象，我們比較了三種證人，他們都在嘗試嘗試：
1) Opcode witness（操作碼見證人）,現有的。（資料來自我之前的實驗）。
2）KV Witness（未壓縮）：不刪除key字首重複資料。
3）KV Witness（壓縮）：包括刪除key字首重複資料。
在5.000.000–8.000.000的區塊上進行了測試。絕對大小比較
絕對大小比較。KV Witness（壓縮）的行為與Opcode witness（操作碼見證人）非常相似。
分位數分析（Quantile analysis）
結論
key字首重複資料刪除確實為KV見證人提供了重大改進。啟用它後，這兩種格式之間的數字幾乎相同。
KV Witness有很多優勢:
第一個主要的是它的簡單性。為資料格式（本質上是字典）制定規範要容易得多，然後是更復雜的幾乎是程式語言的方法。
第二個優點是證明在資料上在語義上是分開的，因此當我們想改變三元性（從六元到二進位制）或當我們想要完全改變證明機制時，使用KV-Witness方法需要的更改更少 。
我認為這絕對是證人規範標準的有力競爭者。
---------------------------------------
原文作者：Igor Mandrigin
譯者：鏈三豐
譯文出處：http://bitoken.world
---------------------------------------
