目前有一种针对无状态以太坊中的区块见证的提议格式，它在GitHub repo中有一个规范。它是基于操作码，您可以想象只有一种命令可以生成Merkle Mupltiproof的小型编程语言。
这篇文章研究了区块见证建设的另一种方法。它是基于键和值的列表，并且具有更简单的语义。
在这篇文章中，我将尝试回答以下问题：
1. 什么是KV-Witness格式？它与当前提议的（基于操作码的）见证格式有何不同？
2. 比较KV的优缺点是什么？
3. 就网络带宽而言，这种格式的效率如何？
要求
任何集体见证人必须满足以下要求：
Correctness（正确性）：我们使用这种格式能够正常运转以太坊主网的任何区块。
Efficiency（效率）：我们能够使用最小的网络带宽来转移此见证人。
Merkelization（默克尔化）：见证人格式必须支持代码默克尔化。
Arity-agnostic（不可知论）：见证格式必须同时支持hexary和二进制Merkle Tries。
语义
我在文章的这一部分描述的见证格式是语义。我不是在这里谈论确切的字节布局。
稍后，我将详细介绍用于测试的见证人的精确二进制格式。
witness ::= header, body, proofs
header ::= version : byte, trie_arity : byte
body ::= array of [ { type: byte key : []byte, value : []byte } ]
proofs ::= map { : [ { 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天）在这个数据上运行无状态原型。
go run ./cmd/state stateless --blockSource ~/stateless-chaindata/geth/chaindata --statefile ~/kv_witness_statefile --witnessInterval5000000 --statsfile ~/stats_kv_witness.csv 2>&1 | tee debug.log
这样您应该在stats_kv_witness.csv中获得与本文档相同的统计信息。
见证二进制格式
见证人从包含版本：header的单字节标头开始。
然后，有一个见证人body，它由大小（1-4个字节，取决于见证人元素的数量）和elements本身组成。
每个elements均以单字节type开头，其后为键字段，该键字段是任意大小的字节数组，其前缀为大小字节（就像body一样），后跟实际数据。
数据取决于元素的类型：
对于存储叶子，它是由字节大小决定的任意大小的字节数组；
对于代码叶子，它也是一个任意大小的字节数组，并以大小字节为前缀；
为了证明，它是一个固定大小的32字节哈希值，没有任何大小的前缀；
对于帐户来说，它更复杂，但基本上是：
标记字节（掩码，用于告知帐户元素是否没有默认值）
随机数，8个字节（如果随机数！= 0）
balance（如果balance！= 0），任意大小的字节数组，以其大小为前缀；
存储根哈希（如果不是空的根哈希），32字节，固定大小的字节数组；
代码哈希（如果代码不为空），32字节，固定大小的字节数组。
最后我们得到这样的结果：this: [ ... ... ...]
优化：删除key(密钥)前缀重复数据
key是由半字节组成的Merkle路径，而不是全字节。十六进制trie的单个半字节大小为4位，而二进制trie的单个半字节大小为1位。这样，我们可以看到有时密钥可以是非整数字节：（例如12位为8,5字节）。
key编码为[] byte，按字节对齐（因此len在4到5字节之间的密钥将始终为5字节）。同样，一个附加的“掩码”字节被添加到开头，以显示最后一个字节中哪些位是“active”。
a key 0xFF（1 byte）：[00001000 11111111]
a key 0b11（2 bits）：[00000010 11000000]
a key 0b10（2 bits）：[00000010 10000000]
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
---------------------------------------
