Posted on 0 comments

技能解析以太坊无状况性区块见证数据计划:键值对见证

技能解析以太坊无状况性区块见证数据计划:键值对见证

本文探讨了 KV-witness 区块见证数据计划的解析算法、优缺陷,以及网络功率等方面。…以太坊,数据,技能,算法,默克尔树 以太坊 数据 技能 算法 默克尔树以太坊爱好者 图标 Logo以太坊爱好者区块链作者,团队,专栏,大众号,头条· ·阅览约 6 分钟

本文探讨了 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 相同),总是把账户相关数据排在前面。

解析算法

    查看见证数据的版别,以及依据所用的默克尔树格局(以保证依据的格局与区块所需的状况树格局相匹配)验证见证数据的哈希值(假如有 「canonical witness」 的概念的话)运用正确的格局创立一棵空的默克尔树遍历数据,按读取数据的次序为这棵空默克尔树刺进数据(见证数据也应该以字典次序存储)刺进依据到树中验证根哈希值(应该与上一区块的根哈希值一起)

长处 & 缺陷

比照一下键值对见证格局与当时的操作码见证格局的优缺陷。

长处

与 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 计划是见证数据规范的有力竞争者。

免责声明:作为区块链信息渠道,本站所发布文章仅代表作者个人观点,与链闻 ChainNews 态度无关。文章内的信息、定见等均仅供参考,并非作为或被视为实践出资主张。

[标签:作者]