区块链研究实验室｜KV-Witness会不会是另一种高效区块见证方法？

目前有一种针对无状态以太坊中的区块见证的提议格式，它在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

---------------------------------------

本文来源：陀螺财经
原文标题：区块链研究实验室｜KV-Witness会不会是另一种高效区块见证方法？

—-

编译者/作者：陀螺财经

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。