迅雷链来信系列教程四｜区块链的区块结构与持久化

曾参与百度分布式计算和网络搜索架构建设，后任腾讯云高级工程师，主导大规模使用去中心化负载均衡系统，以及分布式消息队列等多项技术的开发服务、信鸽移动推送、应用加固。 . 在分布式计算领域拥有丰富的经验。

2015年加入迅雷，负责星域调度系统技术研发。 目前主导设计万科云和区块链商业解决方案，构建共享计算的区块链底层平台。 个人拥有多项分布式计算专利。

目前，区块链技术非常流行，据说区块链是一个公开透明、不可篡改、不依赖可信节点的系统。

那么数据是如何存储在区块链中的呢？ 区块链如何在没有中心信任节点的情况下快速证明数据的可靠性和正确性？ 如何在区块链上访问典型智能合约中的数据？ Laixin通过给出代码示例并使用最流行的语言来解释这些问题。

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

区块链是包含交易信息的有序前向引用块列表。 每个挖矿节点将交易打包成一个区块，然后分发到网络中达成共识，也就是说共识的最小单位是区块，而不是交易。 其实如果要做交易链也是可以的，但是达成共识的次数会增加一个数量级比特币的区块结构是如何的，这样区块链的性能就会大大降低。

区块链节点中的数据存在于何处？

在持久性方面，区块链数据可以直接存储在平面文件或简单的数据库系统中。 比特币和以太坊都将区块链数据存储在谷歌的 LevelDb 中。

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

Version：用于区分软件版本号 Previous Block Hash：指上一个区块头的哈希值。在比特币中，区块头的哈希值一般是临时计算的，不包含在区块头或区块中，但可以存储为索引以提高持久性期间的性能

Nonce、Difficulty Target 和 Timestamp：用于 pow 共识算法。

Merkle Root：是区块中所有交易的指纹，Merkle树的根。 交易在区块链节点之间传播，所有节点按照相同的算法（默克尔树）组合交易，从而判断交易是否完全一致，也用于轻量级钱包快速验证交易是否存在于块中。

什么是默克尔树和默克尔证明？

如上图，merkle树是一棵平衡树，树的根就是存储在区块头中的Merkle Root。 树的构建过程就是递归计算Hash的过程。 例如：首先Hash交易a得到Ha，Hash交易b得到Hb，然后前两个Hash（即Ha和Hb）得到Hab，其他节点也同理递归，最后得到Merkle根。

Merkle 树在区块链中有两个作用：

1. 看merkle root就可以知道区块中的所有交易是否相同

2、对于轻量级节点（不存储所有交易信息，只同步区块头），提供了一种快速验证交易中是否存在交易的方法。

merkle proof从某处向上遍历，计算出merkle Root需要经过的路径节点。 在上面的例子中，如果轻量级钱包想要验证区块中是否包含了Txb（红框），可以向全节点请求merkle proof来证明Txb的存在。 过程如下：

1、所有节点只需要返回黄色部分的节点信息（Ha和Hcd）

2. 轻节点执行计算Hash(Txb)=HbàHash(Ha+Hb)=HabàHash(Hab+Hcd)=Habcd，将计算出的merkleRoot（即Habcd）与已知的merkleRoot进行比较block header ，如果相同，则认为交易确实进入了区块。

在上图中的块中，只有少量的块。 如果区块包含很多交易，merkle proof只需要有log2(N)个节点，这时候merkle proof的优势就会非常明显。

以太坊中的 Merkle 树

在比特币中，系统底层不维护每个账户的余额，只维护UTXO（Unspent Transaction Outputs）。 账户之间的转账是通过交易完成的。 准确地说，比特币用户使用 UTXO 作为交易的输入，可以花费一个或多个 UTXO。

UTXO就像一张现钞，要么不用，要么全部用完，不能只花掉一部分。 例如，用户有一个价值 1 个比特币的 UTXO。 如果他想转 0.5 给某人，他可以创建一个交易，以这个价值 1 个比特币的 UTXO 作为输入，并生成另一个 0.5 个比特币。 OTXO作为本次交易的输出（给自己找零）。

比特币作为一个开放的底层系统，并不单独维护每个账户的余额，但比特币钱包可以记录每个用户拥有的UTXO，从而计算用户的余额。

与比特币相比，以太坊引入了额外的账户状态数据，如随机数、余额和合约数据，这些数据是区块链的关键数据，具有以下特点：

由于交易区块需要持续高效地更新，所有这些数据都可以高效地验证在不同节点之间是一致的。 在状态数据不断更新的过程中，需要保留数据数据的历史版本。

系统中每个节点执行相同的区块和交易后，这些节点对应的所有账户数据都相同，账户列表相同，账户对应的余额等数据也相同。 一般来说，这些账户数据就像一个状态机的状态。 每个节点执行同一个区块后，所达到的状态应该是完全一致的。 但是，这种状态并没有直接写入到区块中，因为这些数据可以通过区块和交易重新生成。 如果将它们写入块中，会增加块的大小，增加块同步的负担。

如上图，区块头中保存了三棵默克尔树的根：

交易根：与比特币中的 Merkle Root 功能相同。 相当于交易在区块中的指纹。 用于快速验证交易是否相同，证明某笔交易的存在。

状态根：这棵树是存储帐户状态（余额、随机数等）的地方。 此外，它还存储存储根，这是存储合约数据的地方。 receipts root：与区块中合约相关的交易输出相关的事件。

默克尔帕特里夏树

在Transaction Root中，使用类似于比特币的二叉merkle树可以解决问题，因为它更适合处理队列数据，而且一旦构建就不会被修改。 但对于状态树来说，情况要复杂得多。 本质上，状态数据更像是一张地图，包括账户与账户状态之间的映射关系。 另外，状态树需要经常更新，经常插入或删除，所以重新计算Root的性能尤为重要。

Trie是一种用来存储文本字符的字典树，利用了词与词之间的共享前缀，所以又称为前缀树。 Trie树有时候很浪费空间，如下图，即使树只有两个词，如果两个词很长，那么树的节点就会变得很大，不管是用来存储的还是都不是cpu可以接受。 如下：

与Trie树相比，Patricia Trie将那些公共路径进行了压缩，以节省空间，提高效率，如下：

以太坊中的Merkle Patricia trie，顾名思义，是Patricia trie和Merkle Tree的组合比特币的区块结构是如何的，具有merkle tree和Patricia Trie的特点：

1、密码学安全，每个节点通过hash引用，hash用于在LevelDb中找到对应的存储数据；

2.像Patricia trie树，这些都可以根据Path找到对应的节点，找到值；

3.引入多种节点类型：

一种。 空节点（例如，当一棵树刚被创建为空时）

b. 叶子节点，最常见的[key, value]

C。 扩展节点，类似于叶子节点，但是值变成了指向其他节点的hash，[key, hash]

d. 分支节点，是一个长度为17的列表，前16个元素可能是十六进制字符，最后一个元素是value（如果这是路径的结尾）

例如：

上图中的 trie 包含 4 对键值。 需要注意的是，key是以16进制显示的，即a7占一个字节，11占一个字节等。

1. 第一层的Node为扩展节点，四个Key都有公共前缀a7，下一个节点指向分支节点

2. 第二层为分支节点。 由于密钥被转换为十六进制，因此每个分支最多有16个分支。 下标也用作路径查找的路径的一部分。 例如，下标为1的元素指向最左边的叶子节点（key-end为1355），到达叶子节点即完成key查找：扩展节点中的a7+分支节点下标1+叶子节点1355=a711355

3.叶子节点和扩展节点的区别。 上面提到，叶子节点和扩展节点都是有两个字段的节点，即[key, value]，存储中没有专门的字段来标识类型。 为了区分这两种节点类型和节省空间，在key上加了一个4bits（1个半字节）的flags前缀，flags的倒数第二位用来表示是叶子节点还是扩展节点。 另外，加上4bits后，key的长度可能不是偶数个半字节（存储只能按字节存储）。 为此，如果key为奇数个半字节，则在flags半字节后增加一个空半字节，并用flags的最低位表示是否有加法，详见上图左下角。

### 更深的 Merkle Patricia 树

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

下面将以代码片段的形式一一验证每一个trie的结构（前提是先在本地搭建好以太坊私链）。

1. Transaction trie如下，在本地环境发送交易并打入区块，查看区块的交易列表，TransactionsRoot和RawTransaction：

在trie包中写一个单独的测试函数，key是交易在区块中的索引，RLP代码，value是签名后的原始交易RawTransaction：

运行output即transactionsRoot得到的Hash为：

2. 状态树

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

在state包中写一个单独的测试函数，state trie的数据以trie节点的hash为key存储在leveldb中，所以整个state trie的entry key就是stateRoot。 状态树存储的数据路径是账户的哈希值，值是经过RLP编码的结构数据。 为了简单和节省空间，这里省略了错误检查。

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

3.存储树

对于以下合约，为了简单起见，合约中省略了构造函数等无关内容，部署后地址为：

当前最新区块的stateRoot为0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed。

To write a single test function in the state package, first create a trie with 0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed, get the storageRoot of the contract account 0x9ea9b9eeac924fd784b064dabf174a55113c4064, and then create the trie with ageRoot When fetching the internal data of the contract, the key is the hashed 32-字节索引，值为RLP编码后的值。

下面数据storedUint的输出为2018，与合约中的数据一致。 值得注意的是，storedString数据后面多了一个16进制的26（十进制为38），是字符串长度的两倍（19）。 有关详细信息，请参阅#layout-of-state-variables-in-storage。

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

文/来新