无状态性:基于键值对的见证数据方案

无状态性:基于键值对的见证数据方案

第12401篇文章无状态性:基于键值对的见证数据方案,说明解释了无状态性:基于键值对的见证数据方案,是很好的区块链入门技术文章网站,提供了相应的代码的进行解释,并且把原理说的很清晰

无状态以太坊运动当前提议了一种区块见证数据(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 {: [ { prefix : []byte, hash : []byte } ] }

见证数据 数据体

见证数据的数据体由两个元素构成:

1.数据“键”(key)可以是:账户的地址,storage key 或者 code key;而 “值”(value)可以是:账户、storage item 或者相应的代码分块(code chunk)。这一部分的数据体与用于验证正确性的默克尔树的格式完全无关。而且,即使用其它方式来验证正确性,这一部分也不会改变。

2.证据。键是默克尔路径,而值是一个哈希值。证据的形式依赖于状态树的格式,所以十六进制树和二进制树下的证据将有所不同。这一语义使得我们能在同一个见证中包含多种类型的多值证明。所以,理论上来说,我们可以创建出一种既能支持十六进制状态树、又能支持二进制状态树的见证数据格式。

数据体按 key 的字典顺序排序、存储,以确保:

更短的键在列表中总是排得前一些(在自顶向下重建默克尔树时候会有用)

当两个数据的键相同时(账户地址可能和 code key 相同),总是把账户相关数据排在前面。

解析算法

1.检查见证数据的版本,以及证据所用的默克尔树格式(以确保证据的格式与区块所需的状态树格式相匹配)

2.验证见证数据的哈希值(如果有 “canonical witness” 的概念的话)

3.使用正确的格式创建一棵空的默克尔树

4.遍历数据,按读取数据的顺序为这棵空默克尔树插入数据(见证数据也应该以字典顺序存储)

5.插入证据到树中

6.验证根哈希值(应该与上一区块的根哈希值一致)

好处 & 缺点

对比一下键值对见证格式与当前的操作码见证格式的优缺点。优点:

与 flat DB 数据库机构相匹配,所以如果 canonical witness 哈希值是有效的,就可以立即插入(不需要验证默克尔根值)

可以用于快照同步(snapshot sync)

witness 中的数据独立于我们所选的验证证据的方法:无论是默克尔树,还是多项式承诺,还是别的方法,都不会影响我们需要添加的数据。

缺点:

在二进制状态树下,可能会因为字节对齐(byte alignment)而需要占用更高的带宽(例如,证据的键为 0b01,只是两个比特,却需要占用一个字节的存储空间)

解析起来可能更慢

网络效率研究

KV Witness 的实现案例

我们首先必须证明这种格式能够实现正确性。它必须能执行以太坊主网上的所有区块。为此,我在 turbo-geth 代码库的一个分支里面实现了这种见证方案:kv-witness-research。这一实现是在谷歌云里面测试的,执行的是块高从 500 万到 800 万的以太坊主网区块。

如何重复我的实验?

你需要至少 200 GB 的可用硬盘空间,和至少 32GB 的内存(因为代码还在概念验证阶段,没怎么优化)。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 个字节,定长的字节数组

最终,见证数据看起来会长这样:

[………][     …  …  …]

优化:删除重复键前缀

键是一个由半字节(nibble)组成的默克尔路径,不是由字节组成的。对于十六进制默克尔树而言,一个半字节的长度是 4 个比特,对二进制默克尔树来说则是 1 个比特。因此,有时候键的字节长度并不是整数(举个例子,12 比特是 8.5 个字节)。键被编码为 []byte,这样就是字节对齐的(所以如果有一个键的长度在 4 个字节到 5 个字节之间,它总是会被补齐为 5 个字节)。同样地,可以加入一个额外的 “面罩” 在开头,指明在最后一个字节中,哪些比特是 1。

键 0xFF (1 byte): [00001000 11111111] <无状态性:基于键值对的见证数据方案 由www.b2bchain.cn 提供
文章整理自网络,只为个人学习与分享使用
链接地址https://www.b2bchain.cn/12401.html

区块链毕设网(www.a1fz.cn)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
a1fz.cn区块链面试课程设计代做网专注|以太坊Hyperledger fabric-计算机|java|毕业设计|代做平台 » 无状态性:基于键值对的见证数据方案

提供最优质的资源集合

立即查看 了解详情