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

D小游

今天我们邀请到迅雷链总工程师来鑫，详细介绍区块链的数据是如何存储的？区块链如何在没有中心信任节点的情况下，快速证明数据是可靠正确的？典型的智能合约中的数据在区块链上如何存取？

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

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

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

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

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

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

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

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

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

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

Version: 用于区分软件版本号

什么是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. 对于轻量节点来说（不存储所有的交易信息，只同步区块头）提供了快速验证一个交易是否存在交易中的方法。

如上图，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. 状态数据不断更新的过程中，历史版本的数据数据需要保留

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

如上所示，区块头中保存了三个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来说都是不可接受的。如下所示：

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

以太坊中的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的终点的话)

在上图中的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

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

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

1. Transaction trie

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

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

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

2. State Trie

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

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

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

3. storage trie

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

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

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

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

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