文章阅读页通栏

KV-Witness会不会是另一种高效区块见证方法?

来源: 区块链研究实验室 作者:链三丰
目前有一种针对无状态以太坊中的区块见证的提议格式,它在GitHub repo中有一个规范。它是基于操作码,您可以想象只有一种命令可以生成Merkle Mupltiproof的......
目前有一种针对无状态以太坊中的区块见证的提议格式,它在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 { <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天)在这个数据上运行无状态原型。

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,它由大小(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)

为了提供带宽效率方面的全面图像,我们比较了三种证人,他们都在尝试尝试:

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方法需要的更改更少 。

我认为这绝对是证人规范标准的有力竞争者。

关键词: KV-Witness  区块见证  
0/300