GameRes游资网

 找回密码
 立即注册
查看: 769|回复: 0

迅雷链总工程师来鑫:区块链的数据是如何存储的?

[复制链接]
发表于 2018-5-31 17:04:19 | 显示全部楼层 |阅读模式
今天我们邀请到迅雷链总工程师来鑫,详细介绍区块链的数据是如何存储的?区块链如何在没有中心信任节点的情况下,快速证明数据是可靠正确的?典型的智能合约中的数据在区块链上如何存取?

微信图片_20180531165837.jpg

其实如果需要做成交易链也是可以的,但是达成共识的次数就数量级的提升了,这样区块链的性能将会大打折扣。

区块链是有序的向前引用的包含交易信息的区块列表。每个挖矿节点将交易打包放到区块中,然后分发到网络中以达成共识,也就是说,达成共识的最小单元是区块,而不是交易。

区块链为什么叫区块链而不叫交易链?

那么区块链的数据是如何存储的?区块链如何在没有中心信任节点的情况下,快速证明数据是可靠正确的?典型的智能合约中的数据在区块链上如何存取?本次直播将给出代码例子,用最通俗的语言来阐释上面的问题。

当前,区块链技术大红大紫,都说区块链是公开透明的,不可篡改的且不依赖信任节点的系统。

比特币中的区块结构是怎样的?

在持久化方面,区块链数据可以直接存储在一个扁平的文件中,也可以存储在简单的数据库系统中,比特币和以太坊都区块链数据存储在google的LevelDb中。

区块链节点中的数据都存在哪里?

微信图片_20180531165845.png

Nonce、DifficultyTarget和Timestamp : 用在pow共识算法中,在此不作详细介绍。

Previous Block Hash:是指向前一个区块头的hash。在比特币中,区块头的hash一般都是临时算出,并没有包含在本区块头或者区块中,但在持久化的时候可以作为索引存储以提高性能。

Version: 用于区分软件版本号

微信图片_20180531165850.jpg

什么是MerkleTree 和Merkle Proof?

Merkle Root:是区块中所有交易的指纹,merkletree的树根。交易在区块链节点之间传播,所有节点都按相同的算法(merkletree)将交易组合起来,如此可以判断交易是否完全一致,此外也用于轻量钱包中快速验证一个交易是否存在于一个区块中。

过程为:

1. 全量节点只要返回黄色部分的节点信息(Ha与Hcd)

2. 轻量节点执行计算Hash(Txb)=Hb→Hash(Ha + Hb)=Hab→Hash(Hab + Hcd)=Habcd,计算出来的merkleRoot(也就是Habcd)跟已知区块头中的merkleRoot比较,如果一样则认为交易确实已经入块。

merkle proof从某处出发向上遍历,算出merkleRoot的所需要经过的路径节点。在上图的例子中,如果轻量钱包要验证Txb(红色方框)是否已经包含在区块中,可以向全量节点请求merkleProof,用于证明Txb的存在。

Merkle tree在区块链中有两个作用:

1. 仅仅看merkleroot就可以知道区块中的所有交易是不是一样的

2. 对于轻量节点来说(不存储所有的交易信息,只同步区块头)提供了快速验证一个交易是否存在交易中的方法。

微信图片_20180531165852.jpg

如上图,merkleTree是一颗平衡树,树根也就是Merkle Root存在区块头中。树的构建过程是递归地的计算Hash的过程,如:先是Hash交易a得到Ha,Hash交易b得到Hb,再Hash前两个Hash(也就是Ha和Hb)得到Hab,其他节点也是同理递归,最终得到MerkleRoot。

一个UTXO像一张现金纸币,要么不使用,要么全部使用,而不能只花一部分。举个例子来说,一个用户有一个价值1比特币的UTXO,如果他想转账0.5给某人,那他可以创建一个交易,以这个价值1比特币的UTXO为输入,另外产生0.5比特币的OTXO作为这个交易的输出(找零给自己)。

在比特币中,系统底层不维护每个账户的余额,只有UTXO(UnspentTransaction Outputs)。账户之间的转账通过交易完成,确切地说,比特币用户将UTXO作为交易的输入,可以花掉一个或者多个UTXO。

以太坊中的merkletree

在上图的区块中,仅仅存在少量的区块。如果区块所包含的交易很多,merkleproof仅仅需要带log2(N)个节点,此时merkleproof的优势就会变得非常明显。

比特币这个公开底层系统本身不单独维护每个账户的余额,不过比特币钱包可以记录每个用户所拥有的UTXO,这样计算出用户的余额。

以太坊相比比特币,额外引入了账号状态数据,比如nonce、余额balance和合约数据,这些是区块链的关键数据。

1. 随着交易的入块需要不断高效地更新

2. 所有的这些数据在不同节点之间能够高效地验证是一致的

3. 状态数据不断更新的过程中,历史版本的数据数据需要保留

系统中的每个节点执行完相同区块和交易后,那么这些节点中对应的所有账户数据都是一样的,账户列表相同,账户对应的余额等数据也相同。总的来说,这些账户数据就像状态机的状态,每个节点执行相同区块后,达到的状态应该是完全一致的。但是,这个状态并不是直接写到区块里面,因为这些数据都是可以由区块和交易重新产生的,如果写到区块里面会增加区块的大小,加重区块同步的负担。

微信图片_20180531165854.jpg

如上所示,区块头中保存了三个merkle tree的root:

tansaction root: 跟比特币中的Merkle Root作用相同,相当于区块中交易的指纹,用于快速验   证交易是否相同以及证明某个交易的存在。

state root: 这颗树是账户状态(余额和nonce等)存放的地方,除此之外,还保存着storage root,也就是合约数据保存的地方。

receipts root:区块中合约相关的交易输出的事件。

Merkle Patriciatree

在Transaction Root中,用类似比特币的二进制merkle tree是能够解决问题的,因为它更适用于处理队列数据,一旦建好就不再修改。但是对于state tree,情况就复杂多了,本质上来说,状态数据更像一个map,包含着账号和账号状态的映射关系。除此之外,state tree还需要经常更新,经常插入或者删除,这样重新计算Root的性能就显得尤其重要。

Trie是一种字典树,用于存储文本字符,并利用了单词之间共享前缀的特点,所以也叫做前缀树。

Trie树在有些时候是比较浪费空间的,如下所示,即使这颗树只有两个词,如果这两个词很长,那么这颗树的节点也会变得非常多,无论是对于存储还是对于cpu来说都是不可接受的。如下所示:

微信图片_20180531165856.jpg

相比Trie树,Patricia Trie将那些公共的的路径压缩以节省空间和提高效率,如下所示:

微信图片_20180531165857.jpg

以太坊中的Merkle Patricia trie,顾名思义,它是Patricia trie和Merkle Tree的结合,即具有merkle tree的特性,也具有Patricia Trie的特征:

密码学安全,每个节点都都是按hash引用,hash用来在LevelDb中找对应的存储数据;

像Patricia trie树一样,这些可以根据Path来找对应的节点以找到value;

引入多种节点类型:

a. 空节点(比如说当一颗树刚刚创建为空的时候)

b. 叶子节点,最普通的[key, value]

c. 扩展节点,跟叶子节点类似,不过值变成了指向别的节点的hash,[key, hash]

d. 分支节点,是一个长度为17的列表,前16元素为可能的十六进制字符,最后一个元素为value(如果这是path的终点的话)

微信图片_20180531165900.jpg

在上图中的trie包含了4对key value,需要注意的是,key是按照16进制来显示的,也就是a7占用一个字节,11占用一个字节等等。

第一层的Node是扩展节点,4个Key都有公有的前缀a7,next node指向一个分支节点

第二层是一个分支节点,由于key转换成了十六进制,每个branch最多有16个分支。下标也作为path的一部分用于path查找。比如说下标为1的元素中指向最左边的叶子节点(key-end为1355),到叶子节点就完成了key搜索:扩展节点中a7 + 分支节点下标 1 + 叶子节点 1355 = a711355

叶子节点和扩展节点的区分。正如上面提到的,叶子节点和扩展节点都是两个字段的节点,也就是[key,value],存储中没有专门字段用来标识类型。

为了区分这两种节点类型并节省空间,在key中加入了4bits(1 nibble)的flags的前缀,用flags的倒数第二低的位指示是叶子节点还是扩展节点。此外,加入了4bits之后,key的长度还有可能不是偶数个nibble(存储中只能按字节存储),为此,如果key是奇数个nibble,在flags nibble之后再添加一个空的nibble,并且用flags的最低位表示是否有添加,详见上图左下角。

更深入的Merkle Patricia tree

更详细的字段关系如下图所示:

微信图片_20180531165902.jpg

下面将通过代码片段的形式,逐一验证各个trie的结构(前提条件是先在本地搭建起以太坊私有链)。

1. Transaction trie

如下所示,在本地环境发送交易并使之入块,查看区块的交易列表,TransactionsRoot和RawTransaction:

微信图片_20180531165904.jpg

在trie包中写单测函数,key为交易在区块中的index,RLP编码,value为签名过的原始交易RawTransaction:

微信图片_20180531165906.jpg

微信图片_20180531165908.jpg

运行输出得到的Hash,也即transactionsRoot为:0x1a65885367afcc561411fe68ed870e4952b11477ad5314de1ae8f26d48a03724,跟eth.getBlock(49).transactionsRoot得到的是一致的。

微信图片_20180531165909.jpg

2. State Trie

获取最新的区块的stateRoot,以及打印出账号0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的余额

微信图片_20180531165911.jpg

在state包中写单测函数,state trie的数据以trie节点hash为key存在leveldb中,所以整个state trie的入口key就是stateRoot。state tree中存储数据的path为account的hash,value为RLP编码过的结构体数据。为了简单起见和节省篇幅,这里省去了错误检查。

微信图片_20180531165913.jpg

运行输出得到0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的余额,跟eth.getBalance接口得到的结果是一致的。

微信图片_20180531165914.jpg

3. storage trie

如下合约,为了简单起见,合约中省去了构造函数等不相关的内容,部署后地址为:0x9ea9b9eeac924fd784b064dabf174a55113c4064。

微信图片_20180531165916.jpg

获取到当前最新块的stateRoot为0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed。

微信图片_20180531165918.jpg

在state包中写单测函数,首先获以0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed创建trie,取获取合约账号0x9ea9b9eeac924fd784b064dabf174a55113c4064的storageRoot,之后再以这个storageRoot创建trie。在取合约内部数据时,key为hash过的32字节index,value为RLP编码过的值。

微信图片_20180531165919.jpg

运行输出以下数据storedUint为2018,跟合约里的数据是一致的。值得注意的是storedString的数据后面多了一个十六进制的26(十进制为38),是字符串长度(19)的两倍,更多的细节请参见http://solidity.readthedocs.io/e ... ariables-in-storage

微信图片_20180531165921.jpg

同时,更复杂的数据结构如变长数组、map等规则会更加复杂,同时这里也忽略了一些字段打包存储等细节,但是都围绕着storageTrie,基本原理没有改变。


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|稿件投递|广告合作|关于本站|GameRes游资网 ( 闽ICP备05005107-1 )

GMT+8, 2018-8-16 23:35

快速回复 返回顶部 返回列表